Tài liệu Luận văn Nghiên cứu và xây dựng ứng dụng bảo mật trên PDA: Luận văn
Nghiên cứu và xây dựng ứng
dụng bảo mật trên PDA
KH
OA
C
NT
T –
Đ
H
KH
TN
i
Lời cảm ơn
Chúng em cảm ơn khoa Công nghệ Thông tin, trường Đại học Khoa học Tự
nhiên Thành phố Hồ Chí Minh đã tạo điều kiện cho chúng em thực hiện đề tài.
Chúng con gởi tất cả lòng biết ơn và sự kính trọng của chúng con đến cha mẹ
cùng toàn thể gia đình, những người đã sinh thành, dưỡng dục và là chỗ dựa vững
chắc cho chúng con vượt qua mọi khó khăn.
Chúng em trân trọng biết ơn thầy Dương Anh Đức, thầy Trần Minh Triết đã
tận tình hướng dẫn, chỉ bảo chúng em để chúng em thực hiện tốt đề tài luận văn tốt
nghiệp.
Chúng em cảm ơn quý thầy cô đã giảng dạy, trang bị những kiến thức quý
báu cho chúng em trong những năm học vừa qua.
Xin chân thành cảm ơn các anh chị, bạn bè đã nhiệt tình giúp đỡ, động viên
chúng tôi trong thời gian học tập và nghiên cứu.
Mặc dù chúng em đã nỗ lực hoàn thành luận văn trong phạm vi và khả năng
cho phép nhưng chắc chắn luận văn vẫn...
169 trang |
Chia sẻ: haohao | Lượt xem: 1325 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn Nghiên cứu và xây dựng ứng dụng bảo mật trên PDA, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Luận văn
Nghiên cứu và xây dựng ứng
dụng bảo mật trên PDA
KH
OA
C
NT
T –
Đ
H
KH
TN
i
Lời cảm ơn
Chúng em cảm ơn khoa Công nghệ Thông tin, trường Đại học Khoa học Tự
nhiên Thành phố Hồ Chí Minh đã tạo điều kiện cho chúng em thực hiện đề tài.
Chúng con gởi tất cả lòng biết ơn và sự kính trọng của chúng con đến cha mẹ
cùng toàn thể gia đình, những người đã sinh thành, dưỡng dục và là chỗ dựa vững
chắc cho chúng con vượt qua mọi khó khăn.
Chúng em trân trọng biết ơn thầy Dương Anh Đức, thầy Trần Minh Triết đã
tận tình hướng dẫn, chỉ bảo chúng em để chúng em thực hiện tốt đề tài luận văn tốt
nghiệp.
Chúng em cảm ơn quý thầy cô đã giảng dạy, trang bị những kiến thức quý
báu cho chúng em trong những năm học vừa qua.
Xin chân thành cảm ơn các anh chị, bạn bè đã nhiệt tình giúp đỡ, động viên
chúng tôi trong thời gian học tập và nghiên cứu.
Mặc dù chúng em đã nỗ lực hoàn thành luận văn trong phạm vi và khả năng
cho phép nhưng chắc chắn luận văn vẫn còn nhiều thiếu sót. Chúng em rất mong
nhận được sự thông cảm, góp ý và tận tình chỉ bảo của quý thầy cô và các bạn.
Tp. Hồ Chí Minh, 07/2004
Nhóm sinh viên thực hiện
Văn Đức Phương Hồng – Nguyễn Minh Huy
KH
OA
C
NT
T –
Đ
H
KH
TN
ii
Lời mở đầu
Ngày nay, công nghệ thông tin và các sản phẩm công nghệ thông tin đã góp
phần giúp cuộc sống của con người thoải mái hơn. Liên lạc giữa các cá nhân và tổ
chức trở nên thuận tiện, từ đó lượng thông tin, dữ liệu giao dịch tăng nhanh về số
lượng lẫn chất lượng.
Trước sự bùng nổ thông tin, việc bảo mật các dữ liệu nhạy cảm giữ vai trò rất
quan trọng. Với sự ra đời của các thiết bị di động cầm tay và các thiết bị hỗ trợ cá
nhân kỹ thuật số, thông tin có thể được quản lý dễ dàng ở mọi lúc mọi nơi. Sự cơ
động của các thiết bị đem lại nhiều tiện lợi cho người sử dụng nhưng đồng thời
cũng mang lại những rủi ro cao khi dữ liệu trong các thiết bị bị mất hoặc bị lấy cắp.
Do đó nhu cầu về ứng dụng mã hóa và bảo mật trên các thiết bị là cần thiết.
Trên thực tế, việc bảo mật trên thiết bị di động chưa được quan tâm rộng rãi.
Các hệ thống bảo mật trên thiết bị di động chỉ giới hạn ở các chức năng bảo mật
được cung cấp tích hợp trong phần cứng thiết bị. Một số ít ứng dụng phần mềm mã
hóa bảo mật trên thiết bị di động có giá thành cao nhưng độ bảo mật ở mức trung
bình.
Với lý do trên, chúng em đã thực hiện đề tài "Nghiên cứu và xây dựng ứng
dụng bảo mật trên PDA" nhằm nghiên cứu, thử nghiệm về các phương pháp, thuật
toán mã hóa bảo mật đồng thời cũng nghiên cứu khả năng đưa chức năng mã hóa
vào ứng dụng trên thiết bị hỗ trợ cá nhân kỹ thuật số. Dựa trên cơ sở lý thuyết đã
nghiên cứu, chúng em thực hiện xây dựng bộ thư viện SPDA Cryptolib với các
thuật toán được xem là mới và hiệu quả hiện nay. Bộ thư viện là công cụ giúp các
lập trình viên có thể thực hiện mã hóa bảo mật trên thiết bị. Sử dụng thư viện đã xây
dựng, chúng em thực hiện ứng dụng Pocket Secure Data với các chức năng giúp
người dùng có thể thực hiện mã hóa, giải mã thông tin, tạo và xác nhận chữ ký điện
tử một cách nhanh chóng và thuận tiện.
KH
OA
C
NT
T –
Đ
H
KH
TN
iii
Nội dung luận văn được trình bày trong 10 chương; trong đó, 6 chương đầu
trình bày các vấn đề về lý thuyết mã hóa và giới thiệu về thiết bị trợ giúp cá nhân kỹ
thuật số; 4 chương cuối tập trung vào bộ thư viện SPDA Cryptolib và ứng dụng
Pocket Secure Data.
· Chương 1. Tổng quan: Giới thiệu về mã hóa và xác định mục tiêu đề tài.
· Chương 2. Mã hóa quy ước: Giới thiệu tóm tắt một số phương pháp mã hóa
quy ước.
· Chương 3. Mã hóa khóa công khai.: Trình bày một số phương pháp mã
hóa khóa công khai.
· Chương 4. Các thuật toán hàm băm và chữ ký điện tử: Trình bày các
thuật toán trong chuẩn hàm băm an toàn và giới thiệu về chữ ký điện tử
· Chương 5. Tổng quan về PDA và môi trường phát triển .NET Compact
Framework: Giới thiệu về thiết bị PDA và trình bày về môi trường phát
triển .NET Compact Framework.
· Chương 6. Xây dựng ứng dụng bảo mật trên PDA - vấn đề và giải
pháp: Trình bày các vấn đề gặp phải khi xây dựng ứng dụng bảo mật trên
PDA và các giải pháp đề nghị.
· Chương 7. Xây dựng bộ thư viện SPDA Cryptolib: Giới thiệu bộ thư viện
SPDA Cryptolib .
· Chương 8. Xây dựng ứng dụng Pocket Secure Data: Giới thiệu ứng dụng
Pocket Secure Data.
· Chương 9. Cài đặt và triển khai ứng dụng
· Chương 10. Tổng kết: Tóm tắt vấn đề đã nghiên cứu thực hiện và hướng
phát triển trong tương lai.
KH
OA
C
NT
T –
Đ
H
KH
TN
iv
Mục lục
Trang
Lời cảm ơn ............................................................................................................... i
Lời mở đầu .............................................................................................................. ii
Mục lục ............................................................................................................. iv
Danh sách hình........................................................................................................ vii
Danh sách bảng ........................................................................................................ ix
Một số khái niệm và thuật ngữ ................................................................................ x
Chương 1. Tổng quan............................................................................................ 2
1.1. Giới thiệu ..................................................................................................... 2
1.1.1. Khái niệm mật mã học.......................................................................... 2
1.1.2. Các định nghĩa ...................................................................................... 2
1.1.3. Các loại mã hóa .................................................................................... 3
1.2. Mục tiêu của đề tài ....................................................................................... 3
Chương 2. Mã hóa quy ước .................................................................................. 3
2.1. Giới thiệu mã hóa quy ước........................................................................... 3
2.1.1. Hệ thống mã hóa quy ước..................................................................... 3
2.1.2. Các thuật toán mã hóa quy ước ............................................................ 3
2.2. Các thuật toán ứng viên AES và Rijndael ................................................... 3
2.2.1. Các thuật toán ứng viên AES ............................................................... 3
2.2.2. Thuật toán Rijndael .............................................................................. 3
2.3. Đánh giá các phương pháp mã hóa quy ước................................................ 3
Chương 3. Mã hóa khóa công khai. ..................................................................... 3
3.1. Giới thiệu mã hóa khóa công khai ............................................................... 3
3.2. Phương pháp RSA ....................................................................................... 3
3.2.1. Mô hình mã hóa dữ liệu với RSA......................................................... 3
3.2.2. Mô hình trao đổi khóa theo RSA.......................................................... 3
3.3. Phương pháp ECC (Elliptic Curve Cryptography) ...................................... 3
3.3.1. Lý thuyết Elliptic Curve ....................................................................... 3
3.3.2. Áp dụng lý thuyết Elliptic Curve vào mã hóa ..................................... 3
3.4. Đánh giá các phương pháp mã hóa khóa công khai .................................... 3
3.4.1. Ứng dụng của mã hóa khóa công khai ................................................. 3
3.4.2. So sánh giữa các phương pháp mã hóa khóa công khai....................... 3
Chương 4. Các thuật toán hàm băm và chữ ký điện tử ..................................... 3
4.1. Các thuật toán hàm băm............................................................................... 3
4.1.1. Giới thiệu hàm băm .............................................................................. 3
4.1.2. Giới thiệu các chuẩn thuật toán hàm băm Secure Hash Standard(SHS)
trong FIPS180-2 (02/2004) ................................................................................. 3
4.1.3. Giới thiệu đề xuất hàm băm mới AES–HASH của Bram Cohen......... 3
4.2. Chữ ký điện tử.............................................................................................. 3
4.2.1. Mô hình chữ ký điện tử theo RSA........................................................ 3
KH
OA
C
NT
T –
Đ
H
KH
TN
v
4.2.2. Thuật toán chữ ký điện tử DSA........................................................... 3
4.2.3. Thuật toán chữ ký điện tử trên Elliptic Curve (ECDSA) ..................... 3
Chương 5. Tổng quan về PDA và môi trường phát triển .NET Compact
Framework .............................................................................................................. 3
5.1. Tìm hiểu thiết bị PDA.................................................................................. 3
5.1.1. Đặc điểm của PDA ............................................................................... 3
5.1.2. Các hạn chế của PDA ........................................................................... 3
5.2. Tổng quan về WindowCE và Pocket PC ..................................................... 3
5.2.1. Giới thiệu hệ điều hành Windows CE.................................................. 3
5.2.2. Giới thiệu Pocket PC ............................................................................ 3
5.3. Giới thiệu .NET Compact Framework......................................................... 3
Chương 6. Xây dựng ứng dụng bảo mật trên PDA - vấn đề và giải pháp .... 3
6.1. Các vấn đề khi xây dựng ứng dụng bảo mật trên PDA ............................... 3
6.1.1. Khả năng tính toán................................................................................ 3
6.1.2. Khả năng lưu trữ ................................................................................... 3
6.1.3. Khả năng tương tác giữa người sử dụng và thiết bị ............................. 3
6.1.4. Mức độ hỗ trợ của các thư viện lập trình ............................................. 3
6.2. Các giải pháp cụ thể ..................................................................................... 3
6.2.1. CryptoAPI............................................................................................. 3
6.2.2. Xây dựng bộ thư viện SPDA Cryptolib ............................................... 3
Chương 7. Xây dựng bộ thư viện SPDA Cryptolib............................................ 3
7.1. Phát biểu bài toán......................................................................................... 3
7.2. Kiến trúc bộ thư viện ................................................................................... 3
7.2.1. Sơ đồ kiến trúc bộ thư viện .................................................................. 3
7.2.2. Danh sách các lớp trong thư viện ......................................................... 3
Chương 8. Xây dựng ứng dụng Pocket Secure Data.......................................... 3
8.1. Phát biểu bài toán......................................................................................... 3
8.2. Phân tích yêu cầu ......................................................................................... 3
8.2.1. Bảng chú giải ........................................................................................ 3
8.2.2. Các yêu cầu chức năng ........................................................................ 3
8.2.3. Các yêu cầu phi chức năng................................................................... 3
8.3. Sơ đồ Usecase .............................................................................................. 3
8.3.1. Một số đặc tả Usecase chính ................................................................ 3
8.3.2. Một số sơ đồ tuần tự chính ................................................................... 3
8.4. Sơ đồ lớp ...................................................................................................... 3
8.4.1. Phân hệ client ....................................................................................... 3
8.4.2. Phân hệ server....................................................................................... 3
8.5. Thiết kế dữ liệu ............................................................................................ 3
8.5.1. Sơ đồ dữ liệu......................................................................................... 3
8.5.2. Mô tả dữ liệu......................................................................................... 3
8.5.3. Ràng buộc toàn vẹn .............................................................................. 3
8.6. Thiết kế giao diện......................................................................................... 3
8.6.1. Sơ đồ màn hình..................................................................................... 3
KH
OA
C
NT
T –
Đ
H
KH
TN
vi
8.6.2. Màn hình phân hệ server ...................................................................... 3
8.6.3. Màn hình phân hệ client ....................................................................... 3
Chương 9. Cài đặt và triển khai ứng dụng ......................................................... 3
9.1. Môi trường cài đặt........................................................................................ 3
9.2. Mô hình cài đặt ............................................................................................ 3
9.3. Kết quả thử nghiệm...................................................................................... 3
Chương 10. Tổng kết ............................................................................................... 3
10.1. Kết luận .................................................................................................... 3
10.2. Hướng phát triển ...................................................................................... 3
Phụ lục .............................................................................................................. 3
Tài liệu tham khảo .................................................................................................... 3
KH
OA
C
NT
T –
Đ
H
KH
TN
vii
Danh sách hình
Hình 2-1: Mô hình hệ thống mã hóa quy ước. ........................................................... 3
Hình 2-2: Sơ đồ quá trình mã hóa dữ liệu bằng phương pháp DES........................... 3
Hình 3-1: Mô hình hệ thống mã hóa khóa công khai. ................................................ 3
Hình 3-2: Một ví dụ về elliptic curve. ........................................................................ 3
Hình 3-3: Điểm ở vô cực. ........................................................................................... 3
Hình 3-4: Phép cộng trên elliptic curve...................................................................... 3
Hình 3-5: Phép nhân đôi trên elliptic curve................................................................ 3
Hình 3-6: Mô hình CA tập trung. ............................................................................... 3
Hình 3-7: Mô hình CA phân cấp. ............................................................................... 3
Hình 3-8: Mô hình CA Web of Trust. ....................................................................... 3
Hình 3-9: So sánh mức độ bảo mật giữa ECC, RSA / DSA....................................... 3
Hình 7-1: Class diagram của thư viện SPDA Cryptolib ............................................ 3
Hình 8-1: Usecase diagram của ứng dụng Pocket Secure Data. ................................ 3
Hình 8-2: Class diagram trên phân hệ client .............................................................. 3
Hình 8-3: Class diagram trên phân hệ server. ........................................................... 3
Hình 8-4: Sơ đồ thiết kế dữ liệu của Pocket Secure Data. ......................................... 3
Hình 8-5: Sơ đồ màn hình phân hệ server. ................................................................. 3
Hình 8-6: Sơ đồ màn hình phân hệ client. .................................................................. 3
Hình 8-7: Màn hình chính Server. .............................................................................. 3
Hình 8-8: Màn hình User Registration. ...................................................................... 3
Hình 8-9: Màn hình User Management ...................................................................... 3
Hình 8-10: Màn hình Server Settings. ........................................................................ 3
Hình 8-11: Màn hình chính Client.............................................................................. 3
Hình 8-12: Màn hình Cipher....................................................................................... 3
Hình 8-13: Màn hình KeyExchange. .......................................................................... 3
Hình 8-14:Màn hình Signature ................................................................................... 3
Hình 8-15: Màn hình Key Generator.......................................................................... 3
KH
OA
C
NT
T –
Đ
H
KH
TN
viii
Hình 8-16: Màn hình Group Management. ................................................................ 3
Hình 8-17: Màn hình Find Contact............................................................................. 3
Hình 9-1:Mô hình cài đặt thư viện và ứng dụng. ....................................................... 3
KH
OA
C
NT
T –
Đ
H
KH
TN
ix
Danh sách bảng
Bảng 2-1: Các hàm và ký hiệu sử dụng trong phương pháp Rijndael........................ 3
Bảng 3-1: So sánh các phép toán trên elliptic trên tọa độ Affine và tọa độ chiếu . ... 3
Bảng 3-2: So sánh kích thước khóa giữa mã hóa quy ước và mã hóa khóa công khai
với cùng mức độ bảo mật. ................................................................................... 3
Bảng 3-3: So sánh kích thước khóa RSA và ECC với cùng độ bảo mật.................... 3
Bảng 4-1:Các tính chất của các thuật toán băm an toàn............................................. 3
Bảng 7-1: Danh sách các lớp trong thư viện SPDA Cryptolib .................................. 3
Bảng 8-1: Danh sách các Usecase. ............................................................................. 3
Bảng 8-2: Chi tiết các màn hình ở phân hệ client....................................................... 3
Bảng 9-1: Kết quả mã hóa thử nghiệm trên Desktop và PDA. .................................. 3
Bảng 9-2: Kết quả thử nghiệm tạo khóa RSA và ECC .............................................. 3
KH
OA
C
NT
T –
Đ
H
KH
TN
x
Một số khái niệm và thuật ngữ
PDA Thiết bị trợ giúp cá nhân kỹ thuật số - Personal Digital
Assistant.
NIST Viện Tiêu chuẩn và Công nghệ Hoa Kỳ - National
Institute of Standard and Technology.
FIPS Federal Information Processing Standard Publications
NSA National Security Agency.
DES Chuẩn mã hóa dữ liệu – Data Encryption Standard.
AES Chuẩn mã hóa nâng cao – Advanced Encryption
Standard.
SHA Thuật toán băm an toàn – Secure Hash Algorithm.
SHS Chuẩn băm an toàn – Secure Hash Standard.
ECC Phương pháp mã hóa theo đưòng cong elip - Elliptic
Curve Cryptography
ECDH Elliptic Curve Diffie – Hellman.
DSA Thuật toán chữ ký điện tử - Digital Signature Algorithm.
ECDSA Elliptic Curve Digital Signature Algorithm.
SSL Giao thức kết nối an toàn - Socket Secure Layer.
Khóa công khai Public key – khóa được công bố rộng rãi cho mọi người,
sử dụng trong mã hóa khóa công khai.
Khóa riêng Private key – khóa của một cá nhân được giữ bí mật, có
quan hệ với khóa công khai, sử dụng trong mã hóa khóa
công khai.
Khóa bí mật Secret key – khóa quy ước sử dụng trong mã hóa quy
ước.
Mã hóa quy ước Conventional cryptography - Còn gọi là mã hóa đối xứng
(symmetric cryptography), hệ thống mã hóa sử dụng cùng
một khóa cho mã hóa và giải mã.
Mã hóa khóa công khai Public key cryptography – còn gọi là mã hóa bất đối xứng
(asymmetric cryptography), hệ thống mã hóa sử dụng một
cặp khóa để mã hoá và giải mã.
Trao đổi khóa Key exchange – phương pháp để trao đổi các thông tin
khóa bí mật giữa các đối tác.
KH
OA
C
NT
T –
Đ
H
KH
TN
xi
Chữ ký điện tử Digital Signature - dãy bit phát sinh từ dữ liệu và khóa
gởi kèm với dữ liệu khi trao đổi nhằm để xác nhận nguồn
gốc dữ liệu, xác nhận tính toàn vẹn của dữ liệu.
ECDLP Bài toán logarit rời rạc trên Elliptic curve - Elliptic Curve
Discrete Logarithm Problem.
CryptoAPI Bộ thư viện các hàm mã hóa ứng dụng trên Windows CE
- Cryptographic Application Programming Interface.
.NET CF .NET Compact Framework.
SPDA Security on Personal Digital Assistant.
KH
OA
C
NT
T –
Đ
H
KH
TN
1
Phần 1:
Mở đầu
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 1 Tổng quan
2
Chương 1. Tổng quan
1.1. Giới thiệu
1.1.1. Khái niệm mật mã học
Mật mã học là ngành khoa học ứng dụng toán học vào việc đảm bảo an toàn
thông tin. Mật mã học giữ vai trò quan trọng và có nhiều ứng dụng trong đời sống
xã hội từ lĩnh vực an ninh quân sự , đến các lĩnh vực dân sự như kinh tế, ngân hàng,
thương mại....
Đối tượng nghiên cứu của mật mã học là các kỹ thuật để mã hóa và bảo mật
thông tin.
1.1.2. Các định nghĩa
Định nghĩa 1.1: Một hệ thống mã hóa (cryptosystem) [8] là một bộ-năm (P, C, K,
E, D) thỏa mãn các điều kiện sau:
1. Tập nguồn P là tập hợp hữu hạn tất cả các mẩu tin nguồn cần mã hóa có thể
có
2. Tập đích C là tập hợp hữu hạn tất cả các mẩu tin có thể có sau khi mã hóa
3. Tập khóa K là tập hợp hữu hạn các khóa có thể được sử dụng
4. Với mỗi khóa kÎK, tồn tại luật mã hóa ekÎE và luật giải mã dkÎD tương
ứng. Luật mã hóa ek: P ® C và luật giải mã ek: C ® P là hai ánh xạ thỏa
mãn
( )( ) ,k kd e x x x P= " Î ( 1.1)
Tính chất 4 là tính chất chính và quan trọng của một hệ thống mã hóa. Tính chất này
bảo đảm việc mã hóa một mẩu tin xÎP bằng luật mã hóa ekÎE có thể được giải mã
chính xác bằng luật dkÎD.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 1 Tổng quan
3
Định nghĩa 1.2: Zm được định nghĩa là tập hợp {0, 1, ..., m-1}, được trang bị phép
cộng (ký hiệu +) và phép nhân (ký hiệu là ´). Phép cộng và phép nhân trong Zm
được thực hiện tương tự như trong Z, ngoại trừ kết quả tính theo modulo m.
1.1.3. Các loại mã hóa
1.1.3.1. Mã hóa quy ước
Mã hóa quy ước (hay còn gọi mã hóa đối xứng ) là hệ thống mã hóa sử dụng
cùng một khóa gọi là khóa bí mật (secret key / symmetric key) để thực hiện mã hóa
hay giải mã thông tin. Việc bảo mật thông tin tùy thuộc vào việc bảo mật khóa bí
mật.
Phương pháp mã hóa quy ước DES được đưa vào sử dụng từ năm 1977 đã
không còn được xem là an toàn khi tốc độ xử lý tính toán của các bộ vi xử lý ngày
càng tăng nhanh chóng. Tháng 10/2000, Viện Tiêu chuẩn và Công nghệ Hoa Kỳ
NIST đã công bố chuẩn mã hóa mở rộng AES và quyết định chọn thuật toán
Rijndael làm phương pháp mã hóa quy ước đại diện cho AES.
1.1.3.2. Mã hóa khóa công khai
Mã hoá khóa công khai (hay còn gọi mã hóa bất đối xứng) là hệ thống mã hóa
sử dụng một cặp khóa để mã hóa và giải mã thông tin. Một khóa được công bố rộng
rãi (khóa công khai) để mã hóa thông tin, khóa tương ứng còn lại được giữ bí mật
(khóa riêng ) để giải mã thông tin.
Lợi ích lớn nhất của mã hóa khóa công khai chính là giúp người sử dụng
tránh các rủi ro khi trao đổi khóa. Một số hệ thống mã hóa khóa công khai bao gồm:
Diffie-Hellman (Whitfield Diffie - Martin Hellman ), RSA (Rivest – Shamir –
Adleman), Elgamal (Tahel Elgamal), DSA (David Kravitz) và ECC (Neal Koblitz -
Victor Miller). Trong số đó, RSA được sử dụng rộng rãi nhất và những năm gần
đây, ECC đang thu hút được sự quan tâm nghiên cứu của các nhà khoa học trên thế
giới.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 1 Tổng quan
4
Mã hóa khóa công khai là nền tảng của nhiều ứng dụng bảo mật có ý nghĩa
quan trọng trong đời sống xã hội như: chữ ký điện tử, chứng nhận điện tử, an toàn
trong truyền dữ liệu trên mạng (SSL).
1.2. Mục tiêu của đề tài
Ngày nay, các thiết bị trợ giúp cá nhân kỹ thuật số đang dần trở nên quen
thuộc và được người sử dụng ưa chuộng. Tuy nhiên, mức độ bảo mật của các thiết
bị phụ thuộc rất nhiều vào nhà cung cấp phần cứng. Dữ liệu của người sử dụng chưa
được đảm bảo an toàn. Những giải pháp phầm mềm cho công việc bảo mật trên
PDA hiện tại trên thế giới có chi phí rất cao cùng với độ bảo mật chỉ ở mức trung
bình.
Đề tài "Nghiên cứu và xây dựng ứng dụng bảo mật trên PDA" được thực
hiện với mục đích tìm hiểu, nghiên cứu và thử nghiệm các phương pháp mã hóa quy
ước và mã hóa khóa công khai cùng với các phương pháp ký và xác nhận chữ ký
điện tử. Đồng thời, chúng em cũng tìm hiểu các thuật toán mã hóa quy ước là ứng
viên của chuẩn mã hóa nâng cao AES, thuật toán mã hóa khóa công khai ECC và
các thuật toán hàm băm mới SHA-224, AES-Hash đang nhận được sự quan tâm của
các nhà khoa học trong thời gian gần đây.
Trên cơ sở lý thuyết nghiên cứu được, chúng em thực hiện xây dựng một bộ
thư viện mã hóa SPDA Cryptolib trên thiết bị PDA. Bộ thư viện SPDA Cryptolib sẽ
cung cấp các thuật toán mã hóa thông dụng và mới nhất hiện nay bên cạnh khả năng
hỗ trợ lập trình trên thiết bị PDA. Sử dụng thư viện mã hóa SPDA Cryptolib, chúng
em đã thực hiện ứng dụng Pocket Secure Data cung cấp các chức năng về mã hóa,
chữ ký điện tử và quản lý khóa cho người sử dụng PDA. Ứng dụng sẽ hoạt động
trên hai phân hệ: máy tính cá nhân để bàn và máy PDA.
KH
OA
C
NT
T –
Đ
H
KH
TN
5
Phần 2:
Lý thuyết
mã hoá
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
6
Chương 2. Mã hóa quy ước
Dẫn nhập: Chương 1 chúng ta đã tìm hiểu tổng quan về mật mã học, nội dung
chương 2 sẽ giới thiệu chi tiết hơn về hệ thống mã hóa quy ước với các thuật toán
mã hóa quy ước. Đặc biệt chương 2 sẽ đề cập cụ thể hơn về chuẩn mã hóa quy ước
mở rộng AES và các thuật toán ứng viên của AES. Chương 2 cũng sẽ trình bày
đánh giá về các phương pháp mã hóa quy ước.
2.1. Giới thiệu mã hóa quy ước
2.1.1. Hệ thống mã hóa quy ước
Hệ thống mã hóa quy ước là hệ thống mã hóa trong đó quy trình mã hóa và
giải mã đều sử dụng chung một khóa gọi là khóa bí mật. Việc bảo mật thông tin phụ
thuộc vào việc bảo mật khóa.
Xét mô hình hệ thống mã hóa quy ước sau:
Hình 2-1: Mô hình hệ thống mã hóa quy ước.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
7
Dữ liệu nguồn x được người gởi A mã hóa bằng thuật toán mã hóa quy ước
với khóa bí mật k được thống nhất trước giữa người gởi A và người nhận B. Dữ liệu
sau khi mã hóa y sẽ đuợc truyền cho người nhận B. Người nhận B sử dụng khóa bí
mật k để giải mã y để có được thông điệp nguồn x ban đầu.
Nếu một người C có được khóa bí mật k thì C sẽ có khả năng giải mã tất cả
dữ liệu A mã hóa bằng khóa k và gởi cho B. Do đó vấn đề an toàn bảo mật thông tin
được mã hóa phụ thuộc vào việc giữ bí mật nội dung mã khóa k.
2.1.2. Các thuật toán mã hóa quy ước
Các thuật toán mã hóa quy ước được phân thành 2 loại: mã hóa theo ký tự và
mã hóa theo khối.
2.1.2.1. Mã hóa theo ký tự
Mã hóa theo ký tự là phương pháp mã hóa bằng cách thay thế từng ký tự
trong thông điệp nguồn thành một ký tự khác trong tập ký tự mã hóa.
Dạng mã hóa quy ước theo ký tự đã xuất hiện từ thời đế chế La mã dưới sự
chỉ huy của Caesar. Một số phương pháp mã hóa theo ký tự được biết đến bao
gồm[8]:
· Shift Cipher: Thông điệp được mã hóa bằng cách dịch chuyển (xoay vòng)
từng ký tự đi k vị trí trong Zn. Trong trường hợp đặc biệt k = 3, phương pháp
Shift Cipher được gọi là phương pháp mã hóa Caesar.
· Substitution Cipher: Khóa k Î K là tập hợp hoán vị các phần tử trong tập
nguồn P. Hàm mã hóa thực hiện ánh xạ một ký tự trong thông điệp nguồn
vào khóa k. Hàm giải mã là ánh xạ ngược của hàm mã hóa.
· Affine Cipher: Khoá k là một bộ (a, b) sao cho ax + b = y (mod n) có
nghiệm duy nhất. Trong đó a và n nguyên tố cùng nhau. Gọi f(n) là số phần
tử trong Zn, nguyên tố cùng nhau với n, ta có n khả năng xác định b, f(n) khả
năng xác định a nên không gian khóa K có n ´ f(n) phần tử.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
8
Giá trị y = ax + b chính là dữ liệu sau khi mã hóa của x tương ứng. Để giải
mã, cần tìm giá trị a-1 Î Z sử dụng thuật toán Euclid mở rộng. Do đó:
x = (a-1(y – b)) mod n. ( 2.1)
· Multiplicative Cipher: Cho P = C = Zn, K = {k Î Zn: gcd(k, n) = 1}.
Với mỗi khóa kÎZn, định nghĩa:
ek(x) = kx mod n và dk(y) = k–1y mod n với x, y Î Zn ( 2.2)
Các phương pháp mã hóa quy ước theo ký tự đơn giản, có không gian khóa tương
đối nhỏ và các ký tự trùng nhau rất dễ bị phát hiện . Do đó các phương pháp này
không còn được an toàn trong điều kiện tốc độ xử lý của máy tính tăng nhanh như
hiện nay.
2.1.2.2. Mã hóa theo khối
Mã hóa theo khối là phương pháp chia thông điệp cần mã hóa thành những khối
thông điệp có độ dài cố định. Một hàm mã hóa sẽ thao tác trên từng khối thông điệp
để trả về thông điệp đã mã hóa.
· Vigenere Cipher: Sử dụng từ khoá k là một dãy có m phần tử. Phương pháp
Vigenere Cipher chính là áp dụng m phép Shift Cipher luân phiên nhau theo
chu kỳ.
· Hill Cipher: Mỗi phần tử xÎP là một bộ m thành phần, tập nguồn P = Zn ´
Zn. Khóa k gồm m tổ hợp tuyến tính của m thành phần trong mỗi phần tử x.
Như vậy không gian khóa K chính là tập hợp các ma trận m ´ m khả nghịch.
Thao tác mã hóa là thực hiện phép nhân ma trận:
( ) ( )
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
è
æ
==
mmmm
m
m
mk
kkk
kk
kkk
xxxxkxe
,2,1,
,21,2
,12,11,1
21 ,...,,
( 2.3)
với x=(x1, x2, ..., xm) Î P
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
9
Để giải mã cần tìm ma trận nghịch đảo k-1 của khóa k và thực hiện phép tính
toán sau: dk(y) = yk–1. Lưu ý là tất cả các phép toán số học đều được thực hiện trên
Zn.
· Permutation Cipher: Mỗi phần tử xÎP là một bộ m thành phần, tập nguồn
P = Zn ´ Zn. Khóa k Î K là tập hợp hoán vị m thành phần trong phần tử x.
Hàm mã hóa thực hiện ánh xạ một ký tự trong thông điệp nguồn vào khóa k.
Hàm giải mã là ánh xạ ngược của hàm mã hóa.
· Data Encryption Standard (DES):
Khoảng những năm 1970, tiến sĩ Horst Feistel đã đặt nền móng đầu tiên cho
chuẩn mã hóa dữ liệu DES với phương pháp mã hóa Feistel Cipher. Vào năm 1976
cơ quan bảo mật quốc gia Hoa Kỳ (NSA) đã công nhận DES dựa trên Feistel Cipher
là chuẩn mã hóa dữ liệu. DES được công bố trong tài liệu FIPS của NIST[20]. Kích
thước khóa của DES ban đầu là 128 bit nhưng tại bản công bố FIPS kích thước
khóa được rút xuống còn 56 bit.[6]
DES có kích thước khối 64 bit. DES thực hiện mã hóa dữ liệu qua 16 vòng lặp
mã hóa, mỗi vòng sử dụng một khóa chu kỳ 48 bit thu được từ khóa 56 bit ban đầu.
DES sử dụng 8 bảng hằng số Sbox để thao tác. Quá trình mã hóa của DES có thể
được tóm tắt như sau:
Biểu diễn thông điệp nguồn xÎP bằng dãy 64bit. Khóa k có 56bit. Thực hiện mã
hóa theo 3 giai đoạn:
- Tạo dãy 64 bit bằng cách hoán vị x theo hoán vị IP.
- Thực hiện 16 vòng lặp từ 64 bit thu được và 56 bit của khoá k (chỉ sử dụng
48 bit của khoá k trong mỗi vòng lặp). 64 bit kết quả thu được qua mỗi vòng
lặp sẽ là đầu vào cho vòng lặp sau.
- Sau 16 vòng lặp, áp dụng hoán vị ngược IP-1 cho 64bit thu được. Kết quả
cuối cùng chính là khối dữ liệu đã mã hóa y.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
10
Hình 2-2: Sơ đồ quá trình mã hóa dữ liệu bằng phương pháp DES.
Quá trình giải mã chính là thực hiện theo thứ tự đảo ngược các thao tác của quá
trình mã hóa.
Do tốc độ tính toán của máy tính ngày càng tăng cao và DES đã được sự quan
tâm chú ý của các nhà khoa học lẫn những người phá mã (cryptanalyst) nên DES
nhanh chóng trở nên không an toàn. Năm 1997, một dự án đã tiến hành bẻ khóa
DES chưa đến 3 ngày với chi phí thấp hơn 250.000 dollars. Và vào năm 1999, một
mạng máy tính gồm 100.000 máy có thể giải mã một thư tín mã hóa DES chưa đầy
24 giờ.[6]
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
11
Trong quá trình tìm kiếm các thuật toán mới an toàn hơn DES, Tripple DES ra
đời như một biến thể của DES. Tripple DES thực hiện 3 lần thuật toán DES với 3
khoá khác nhau và với trình tự khác nhau. Trình tự thực hiện phổ biến là EDE
(Encrypt – Decrypt – Encrypt), thực hiện xen kẽ mã hóa với giải mã (lưu ý là khóa
trong từng giai đoạn thực hiện khác nhau).
· Advanced Encryption Standard (AES):
Để tìm kiếm một phương pháp mã hóa quy ước mới với độ an toàn cao hơn DES,
NIST đã công bố một chuẩn mã hóa mới, thay thế cho chuẩn DES. Thuật toán đại
diện cho chuẩn mã hóa nâng cao AES (Advanced Encryption Standard) sẽ là thuật
toán mã hóa quy ước, sử dụng miễn phí trên toàn thế giới. Chuẩn AES bao gồm các
yêu cầu sau[8]:
· Thuật toán mã hóa theo khối 128 bit.
· Chiều dài khóa 128 bit, 192 bit và 256 bit.
· Không có khóa yếu.
· Hiệu quả trên hệ thống Intel Pentium Pro và trên các nền phần cứng và phần
mềm khác.
· Thiết kế dễ dàng (hỗ trợ chiều dài khóa linh hoạt, có thể triển khai ứng dụng
rộng rãi trên các nền và các ứng dụng khác nhau).
· Thiết kế đơn giản: phân tích đánh giá và cài đặt dễ dàng.
· Chấp nhận bất kỳ chiều dài khóa lên đến 256 bit.
· Mã hóa dữ liệu thấp hơn 500 chu kỳ đồng hồ cho mỗi khối trên Intel
Pentium, Pentium Pro và Pentium II đối với phiên bản tối ưu của thuật toán.
· Có khả năng thiết lập khóa 128 bit (cho tốc độ mã hóa tối ưu) nhỏ hơn thời
gian đòi hỏi để mã hóa các khối 32 bit trên Pentium, Pentium Pro và Pentium
II.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
12
· Không chứa bất kỳ phép toán nào làm nó giảm khả năng trên các bộ vi xử lý
8 bit, 16 bit, 32 bit và 64 bit.
· Không bao hàm bất kỳ phần tử nào làm nó giảm khả năng của phần cứng.
· Thời gian mã hóa dữ liệu rất thấp dưới 10/1000 giây trên bộ vi xử lý 8 bit.
· Có thể thực hiện trên bộ vi xử lý 8 bit với 64 byte bộ nhớ RAM.
Sau khi thực hiện 2 lần tuyển chọn, có 5 thuật toán được vào vòng chung kết,
gồm có: MARS, RC6, SERPENT, TWOFISH và RIJNDAEL. Các thuật toán này
đều đạt các yêu cầu của AES nên được gọi chung là các thuật toán ứng viên AES.
Các thuật toán ứng viên AES có độ an toàn cao, chi phí thực hiện thấp.
2.2. Các thuật toán ứng viên AES và Rijndael
2.2.1. Các thuật toán ứng viên AES
2.2.1.1. MARS
Thuật toán Mars được đề xuất bởi đơn vị Tổ chức máy tính thương mại quốc
tế (International Business Machines Corporation) .[11]
MARS là thuật toán mã hóa khóa đối xứng hỗ trợ kích thước khối dữ liệu 128bit và
cho phép sử dụng mã khóa có kích thước thay đổi được. Dữ liệu đầu vào và kết quả
trả về của MARS là 4 từ 32bit. Khóa của MARS có kích thước 128bit. Tất cả các
thao tác tính toán số học trong MARS đều được thực hiện trên các từ 32bit.
Quá trình mã hóa của MARS bao gồm các công việc:
- Cộng khóa: cộng các từ của khóa với các từ của khối dữ liệu.
- 8 chu kỳ trộn tới không khóa.
- 8 chu kỳ trộn tới có khóa.
- 8 chu kỳ trộn lùi có khóa.
- 8 chu kỳ trộn lùi không khóa.
- Trừ khóa: trừ các từ của khóa với các từ của khối dữ liệu sau khi đã
thực hiện trộn..
Quá trình giải mã của MARS là nghịch đảo của quá trình mã hóa.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
13
2.2.1.2. SERPENT
Thuật toán SERPENT được đề xuất bởi đơn vị Private, của các tác giả Ross
Anderson, Eli Biham and Lars Knudsen.[11]
SERPENT là một hệ thống 32 chu kỳ thực hiện trên 4 từ 32 bit, do đó kích
thước khối của SERPENT là 128 bit. Các giá trị dùng trong việc mã hóa được xem
như các dòng bit. Ứng với mỗi từ 32-bit, chỉ số bit được đánh từ 0 đến 31, các khối
128-bit có chỉ số từ 0 đến 127 và các khóa 256-bit có chỉ số từ 0 đến 255.
SERPENT mã hóa một văn bản ban đầu P 128 bit thành một văn bản mã hóa
C 128 bit qua 32 chu kỳ với sự điều khiển của 33 khóa chu kỳ 128 bit. Quy trình mã
hóa SERPENT được thực hiện như sau:
· Khởi tạo và phân bố khóa ban đầu thành 33 khóa chu kỳ.
· Thực hiện phép hoán vị đầu
· Thực hiện 32 chu kỳ, mỗi chu kỳ bao gồm một phép trộn khóa, một lần áp
dụng các S–box và một phép biến đổi tuyến tính (cho tất cả các chu kỳ trừ
chu kỳ cuối). Ở chu kỳ cuối cùng, phép biến đổi tuyến tính này được thay thế
bằng một phép trộn khóa
· Thực hiện phép hoán vị cuối.
Quá trình giải mã SERPENT sử dụng các Sbox nghịch đảo, thực hiện các phép
biến đổi tuyến tính nghịch đảo và các khóa chu kỳ được sử dụng cũng theo thứ tự
ngược lại.
2.2.1.3. RC6
Thuật toán RC6 được đề xuất bởi Phòng thí nghiệm RSA (RSA
Laboratories), của các tác giả Ronald L. Rivest, Matt Robshaw, Ray Sidney, Yiqun
Lisa Yin.[11]
RC6 sử dụng các tham số hệ thống w bit từ, r chu kỳ mã hóa và kích thước
khóa b (tính theo đơn vị byte). Tuy nhiên để phù hợp với các tiêu chuẩn của AES,
RC6 chọn giá trị các tham số là w = 32, r = 20 và b = 16 / 24 / 32 bytes.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
14
RC6 chia khối mã hóa thành 4 từ w-bit A, B, C, D và mã hóa văn bản qua các
giai đoạn:
· Khởi tạo và phân bố khóa chính thành 2r + 4 khóa chu kỳ được giữ lại trong
S[i] (0 £ i £ 2r + 4).
· Cộng khóa chu kỳ S[0] và S[1] vào các từ B, C.
· Thực hiện 20 chu kỳ mã hóa gồm các phép toán quay trái, phép cộng, nhân
và xor giá trị từ.
· Cộng khóa chu kỳ S[2r + 2] và S[2r + 3] vào các từ A, D.
Quy trình giải mã của RC6 là nghịch đảo của quy trình mã hóa.
2.2.1.4. TWOFISH
Thuật toán TWOFISH được đề xuất bởi Counterpane Systems, của các tác
giả Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall and
Niels Ferguson.[11]
TWOFISH được thiết kế để thỏa mãn các tiêu chuẩn của AES. TWOFISH hỗ
trợ kích thước khóa tối đa 256 bit.
Tóm tắt quy trình mã hóa TWOFISH:
· Khởi tạo và phân bố khóa: tạo 40 khóa chu kỳ và 4 Sbox, các Sbox phụ
thuộc khóa.
· Input Whitening: Khối dữ liệu ban đầu đựợc chia thành 4 từ 32 bit A,B,C,D.
Thực hiện XOR 4 khóa chu kỳ đầu tiên với A, B, C, D.
· Thực hiện 16 vòng lặp, trong mỗi vòng lặp thực hiện các thao tác XOR, quay
trái, quay phải dữ liệu đồng thời sử dụng các Sbox phụ thuộc khóa.
· Output Whitening: XOR các từ dữ liệu với 4 khóa chu kỳ mở rộng.
Quy trình mã hóa và giải mã của thuật toán TWOFISH tương tự như nhau. Tuy
nhiên, quy trình giải mã đòi hỏi áp dụng các khóa chu kỳ theo thứ tự đảo ngược.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
15
2.2.2. Thuật toán Rijndael
Tháng 11/2001, NIST công bố tài liệu FIPS-197, công nhận Rijndael là thuật
toán đại diện cho chuẩn mã hóa mở rộng AES.[17] Rijndael đã vượt qua 4 thuật
toán ứng viên còn lại (RC6, MARS, SERPENT, TWOFISH) để trở thành chuẩn mã
hóa quy ước mới nhất hiện nay. Thuật toán Rijndael do hai nhà khoa học Vincent
Rijmen và Joan Daeman cung cấp.
Phương pháp Rijndael mã hóa theo khối. Kích thước khối và kích thước khóa
thay đổi linh hoạt 128, 192, 256 bit nhờ vậy Rijndael thích hợp với nhiều hệ thống
mã hóa khác nhau từ các máy tính cá nhân đến smart-cards.
Thuật toán Rijndael được xem là thuật toán có độ an toàn rất cao và có nhiều
ưu điểm nhưng với sự phát triển mạnh mẽ của ngành công nghiệp máy tính không
loại trừ nguy cơ thuật toán Rijndael bị phá vỡ. Do đó hiện nay các nhà khoa học
đang tìm cách cải tiến mở rộng thuật toán Rijndael để tăng độ an toàn. Các phiên
bản mở rộng 256/384/512-bit[1][2][3][4][5] và phiên bản mở rộng 512/768/1024-bit
đều được xây dựng trên cở sở lý thuyết của thuật toán Rijndael nguyên thủy nhưng có
khả năng xử lý khóa và khối dữ liệu lớn hơn nhiều lần so với phiên bản gốc.[7]
Đơn vị thông tin được xử lý trong thuật toán Rijndael là byte. Mỗi byte có thể
được biểu diễn bằng nhiều cách khác nhau: dạng nhị phân
({b7b6b5b4b3b2b1b0}), dạng thập lục phân ({h1h0}) hay dạng đa thức có các
hệ số nhị phân å
=
7
0i
i
i xb .
Các thao tác tính toán của thuật toán AES được thực hiện trên các ma trận hai
chiều gọi là trạng thái (state). Mỗi state gồm 4 hàng Nb cột trong đó Nb là kết quả
của phép chia kích thước khối dữ liệu cho 32. Đối với AES, Nb = 4.
Khóa cũng được biểu diễn dưới dạng ma trận hai chiều gồm 4 hàng Nk cột
trong đó Nk là kết quả chia kích thước khóa cho 32. Mỗi chu kỳ mã hóa / giải mã sử
dụng một khóa phát sinh từ khóa chính gọi là khóa chu kỳ. Có tất cả Nr + 1 khóa
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
16
chu kỳ. Hàm phát sinh bảng mã khóa mở rộng (KeyExpansion) phụ thuộc vào
giá trị Nk, chi tiết hàm KeyExpansion được mô tả trong phụ lục A.
Ý nghĩa
STT Tên
Phiên bản nguyên thủy Phiên bản mở rộng
1 AddRoundKey Thực hiện việc cộng mã khóa của chu kỳ vào trạng thái
hiện hành.
2 SubBytes Thay thế phi tuyến từng byte trong trạng thái hiện hành.
Dùng bảng thay thế SBox.
3 InvSubBytes Phép biến đổi ngược của SubBytes.
4 MixColumns Trộn thông tin từng cột trong trạng thái hiện hành.
5 InvMixColumn
s
Phép biến đổi ngược của MixColumn.
6 ShiftRows Dịch chuyển xoay vòng từng dòng của trạng thái hiện
hành với di số tương ứng khác nhau.
7 InvShiftRows Phép biến đổi ngược của ShiftRows.
Mã khóa chính. Được biểu diễn bằng ma trận: 8 K
4 dòng ´ Nk cột 8 dòng ´ Nk cột
Trạng thái. Được biểu diễn bằng một ma trận : 9 State
4 dòng ´ Nb cột 8 dòng ´ Nb cột
Số lượng cột trong trạng thái. Nb Î{4,6,8}. (AES: Nb =
4)
9 Nb
Nb = độ dài khối / 32 Nb = độ dài khối / 64
Số lượng các từ 32bit trong Mã khóa chính K.
NkÎ{4,6,8}
10 Nk
Nk = Độ dài khóa / 32 Nk = Độ dài khóa / 64
11 Nr Số lượng chu kỳ. Nr = max(Nb, Nk) + 6
12 RotWord Dịch chuyển xoay vòng 4 bytes thành phần của từ 32 bit.
13 SubWord Nhận vào một từ 4 byte. Áp dụng phép thay thế dựa vào
SBox cho từng byte. Trả về từ 4 byte đã được thay thế.
14 XOR Phép toán Exclusive-OR
15 Å Phép toán Exclusive-OR
16 Ä Phép nhân 2 đa thức (bậc < 4) modulo cho đa thức x4+1.
17 · Phép nhân trên trường hữu hạn.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
17
Bảng 2-1: Các hàm và ký hiệu sử dụng trong phương pháp Rijndael.
2.2.2.1. Quy trình mã hóa Rijndael:
· Thực hiện thao tác AddRoundKey đầu tiên trước khi thực hiện các chu kỳ
mã hóa.
· Nr–1 chu kỳ mã hóa bình thường: mỗi chu kỳ bao gồm 4 bước biến đổi liên
tiếp nhau: SubBytes, ShiftRows, MixColumns, và AddRoundKey.
· Thực hiện chu kỳ mã hóa cuối cùng: trong chu kỳ này thao tác MixColumns
được bỏ qua.
v Thuật toán mã hóa Rijndael :
· Dữ liệu vào:
inputBlock: khối dữ liệu cần mã hóa.
inputBlockSize: kích thước khối dữ liệu cần mã hóa.
cipherKey: khóa chính.
cipherKeySize: kích thước khóa chính.
· Dữ liệu ra:
outputBlock: khối dữ liệu đã được mã hóa.
Thuật toán 2.1: Thuật toán mã hoá theo phương pháp Rijndael.
state = inputBlock
cycleCount = max(inputBlockSize, cipherKeySize) + 6
AddRoundKey(state, createCycleKey(cipherKey, 1))
For i = 1 to cycleCount - 1 do
SubBytes(state)
ShiftRows(state)
MixColumns(state)
AddRoundKey(state, createCycleKey(cipherKey, i))
end for
SubBytes(state)
ShiftRows(state)
AddRoundKey(state, createCycleKey(cipherKey, cycleCount))
outputBlock = state
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
18
2.2.2.2. Quy trình giải mã Rijndael
Quy trình giải mã có thể được thực hiện theo với trình tự các phép biến đổi
ngược hoàn toàn tương đương với quy trình mã hóa[8]. Các thao tác ShiftRows,
MixColumns, SubBytes lần lượt được thay thế bằng các thao tác InvShiftRows,
InvMixColumns, InvSubBytes.
Quá trình giải mã được tóm tắt như sau:
· Thực hiện AddRoundKey
· Thực hiện Nr-1 chu kỳ giải mã bình thường, mỗi chu kỳ gồm 4 bước biến
đổi liên tiếp sau: InvShiftRows, InvSubBytes, AddRoundKey,
InvMixColumns.
· Thực hiện chu kì mã hóa cuối cùng, giống Nr-1 chu kỳ trên nhưng bỏ qua
bước InvMixColumns.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
19
v Thuật toán giải mã Rijndael
· Input:
inputBlock: khối dữ liệu cần giải mã.
inputBlockSize: kích thước khối dữ liệu cần giải mã.
cipherKey: khóa chính.
cipherKeySize: kích thước khóa chính.
· Output:
outputBlock: khối dữ liệu đã được giải mã.
Thuật toán 2.2: Thuật toán giải mã theo phương pháp Rijndael.
2.2.2.3. Đánh giá phương pháp Rijndael
Phương pháp Rijndael có các ưu điểm sau[8]:
· Mã chương trình ngắn gọn, ít tốn bộ nhớ nên dễ dàng áp dụng vào các thiết
bị có lượng bộ nhớ giới hạn như thẻ thông minh.
· Quá trình mã hóa và giải mã có thể chạy tốt trên các hệ thống xử lý song
song.
· Kích thước khối dữ liệu linh hoạt 128 / 192 / 256 bit, có thể thay đổi cho phù
hợp từng hệ thống cụ thể
state = inputBlock
cycleCount = max(inputBlockSize, cipherKeySize) + 6
AddRoundKey(state, createCycleKey(cipherKey, cycleCount))
For i = cycleCount - 1 to 1 do
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, createCycleKey(cipherKey, i))
MixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, createCycleKey(cipherKey, 1))
outputBlock = state
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 2 Mã hóa quy ước
20
.Phương pháp Rijndael vẫn còn một số hạn chế:
· Thời gian giải mã dài hơn thời gian mã hóa.
· Bảng Sbox của quá trình giải mã và quá trình mã hóa khác nhau nên cần tốn
bộ nhớ để lưu.
· Không tận dụng được các đoạn mã của quá trình mã hóa vào quá trình giải
mã. Điều này dẫn đến hạn chế khi cài đặt phương pháp Rijndael sử dụng
phần cứng thiết bị.
2.3. Đánh giá các phương pháp mã hóa quy ước
Mã hóa quy ước sử dụng cùng một khóa để mã hóa và giải mã thông tin, do đó
để đảm bảo bảo mật thông tin chỉ những người có liên quan mới được biết khóa bí
mật. Mặc dù hệ thống mã hóa quy ước cung cấp khá nhiều thuật toán mã hóa có độ
bảo mật rất cao nhưng mã hóa quy ước có các hạn chế sau:
· Hạn chế về khả năng trao đổi khóa: Do khóa để giải mã và mã hóa cần phải
được biết giữa người gởi và người nhận thông tin nên phát sinh vấn đề an
toàn khi truyền khóa. Nếu khóa quy ước bị lấy cắp trong quá trình truyền
khóa thì thông tin được mã hóa bằng khóa đó không còn được bảo mật an
toàn. Ngoài ra với mã hóa quy ước không thể đảm bảo nguồn gốc thông tin
được gởi đến do không thể biết được khóa có bị mất cắp hay không.
· Hạn chế về khả năng quản lý khóa: Đối với từng người cần liên lạc và với
từng nội dung thông tin cần phải có một khóa quy ước để mã hóa và giải mã.
Do đó nếu trên một mạng liên lạc lớn, số lượng khóa cần phải lưu giữ rất
nhiều nên nảy sinh vấn đề quản lý khóa quy ước và bảo mật thiết bị lưu trữ
khóa quy ước.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
21
Chương 3. Mã hóa khóa công khai.
Dẫn nhập: Chương 3 giới thiệu về hệ thống mã hóa khóa công khai với hai thuật
toán mã hoá khóa công khai RSA và ECC. Chương 3 đề cập đến lý thuyết toán học
nền tảng của phương pháp mã hóa công khai Elliptic Curve cùng với việc ứng dụng
lý thuyết này vào mã hóa. Chương 3 cũng trình bày phần đánh giá, so sánh và ứng
dụng của các phương pháp mã hóa khóa công khai.
3.1. Giới thiệu mã hóa khóa công khai
Vấn đề phát sinh trong mã hóa quy ước là việc quy ước chung khóa bí mật k
giữa người gởi A và người nhận B. Như vậy, bài toán bảo mật dữ liệu sẽ được đưa
về bài toán bảo mật khóa bí mật k khi liên lạc truyền khóa giữa A và B. Tuy nhiên,
rất khó có thể bảo đảm được sự an toàn của kênh liên lạc nên khóa k vẫn có thể bị
phát hiện bởi người C.
Ý tưởng về khóa công khai được Martin Hellman, Ralph Merkle, and
Whitfield Diffie tại Đại học Stanford vào năm 1976. Một hệ thống khóa công khai
sử dụng hai loại khóa trong cùng một cặp khóa: khóa công khai được công bố rộng
rãi và được sử dụng trong mã hóa thông tin, khóa bí mật chỉ do một người nắm giữ
và được sử dụng để giải mã thông tin đã được mã hóa bằng khóa công khai. Các
phương pháp mã hóa này khai thác những ánh xạ f mà việc thực hiện ánh xạ ngược
f –1 rất khó so với việc thực hiện ánh xạ f.[8]
Năm 1977, trên báo "The Scientific American", Ronald L. Rivest, Adi Shamir
và Leonard M. Adleman đã giới thiệu phương pháp RSA là một phương pháp mã
hóa khóa công khai sử dụng trong mã hóa và chữ ký điện tử. RSA nhanh chóng trở
thành chuẩn mã hóa khóa công khai trên toàn thế giới do tính an toàn và khả năng
ứng dụng của nó.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
22
Xét mô hình mã hóa khóa công khai sau:
Hình 3-1: Mô hình hệ thống mã hóa khóa công khai.
Người gởi A sử dụng khóa công khai pk của người nhận B để mã hóa dữ liệu
gốc x. Dữ liệu sau khi được mã hóa y được truyền cho B. Người nhận B sau khi
nhận được y sẽ sử dụng khóa riêng sk của mình để giải mã dữ liệu và nhận lại dữ
liệu nguồn x ban đầu.
Nếu một người C có được dữ liệu đã mã hóa y và khóa công khai pk thì C vẫn
không thể giải mã được y. Do khóa riêng sk được giữ bí mật hoàn toàn, chỉ có người
B biết được sk và sk không được giao dịch hay truyền đi nên rủi ro dẫn đến việc
khóa riêng sk bị đánh cắp là rất thấp. Đây chính là ưu điểm nổi bật của mã hóa khóa
công khai.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
23
3.2. Phương pháp RSA
Phương pháp RSA là một phương pháp mã hóa khóa công khai phổ biến trên
thế giới hiện nay. RSA được xem là phương pháp an toàn, và có khả năng ứng dụng
rộng rãi trong các lĩnh vực. Dựa vào nền tảng lý thuyết về phân tích thừa số nguyên
tố của số nguyên lớn, phương pháp RSA được ứng dụng vào các mô hình mã hóa,
mô hình truyền nhận khóa và mô hình chữ ký điện tử. Phương pháp RSA đòi hỏi
mỗi thực thể sở hữu một cặp khóa công khai – khóa riêng để sử dụng cho tất cả mô
hình mã hóa.
v Quá trình tạo khóa công khai như sau:
· Tạo ngẫu nhiên hai giá trị số nguyên tố lớn khác nhau p và q.
· Tính giá trị n = p´q và f(n) = (p–1) (q–1).
· Chọn số mũ công khai e (1 < e < f(n)) nguyên tố cùng nhau với f(n).
· Tính số mũ bí mật d sao cho e´d º 1 (mod f(n)).
· Giá trị khóa công khai chính là (n, e). Giá trị khóa riêng là d.
trong đó :
n RSA modulus.
e số mũ mã hóa (encryption exponent)
d số mũ giải mã (decryption exponent)
Nếu hệ thống RSA sử dụng số n có chiều dài k bit thì được gọi là hệ thống RSA k-
bit.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
24
3.2.1. Mô hình mã hóa dữ liệu với RSA
Gọi (n, e) là khóa công khai, d là khóa riêng của người nhận B. Người gởi A có nhu
cần mã hóa và gởi thông điệp m cho người nhận B.
v Quá trình mã hóa:
· A nhận giá trị khóa công khai của B
· Biểu diễn thông điệp m dưới dạng một số nguyên trong khoảng [0..n-1]. Nếu
thông điệp m quá dài, chia m thành từng khối có kích thước phù hợp để mã
hóa.
· Tính giá trị c = me mod n.
· A chuyển thông điệp đã mã hóa c cho B
v Quá trình giải mã:
· B nhận thông điệp c đã mã hóa.
· Sử dụng khóa riêng d để tính giá trị m = cd mod n.
3.2.2. Mô hình trao đổi khóa theo RSA
Một trong những ứng dụng của phương pháp RSA là dùng nó trong việc trao đổi
khóa. Trong mô hình này, giả sử A cần trao đổi khóa bí mật K với B, A sẽ tiến hành
các bước như sau:
· A nhận khóa công khai (n, e) từ B.
· A dùng khóa công khai này để mã hóa khóa bí mật K bằng phương pháp
RSA:
modeY K n=
· Khóa bí mật đã được mã hóa Y được chuyển cho B.
· B dùng khóa riêng d để giải mã Y bằng phương pháp RSA:
moddK Y n=
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
25
3.3. Phương pháp ECC (Elliptic Curve Cryptography)
3.3.1. Lý thuyết Elliptic Curve
Hệ thống mã hóa khóa công khai dựa trên việc sử dụng các bài toán khó giải
quyết. Vấn đề khó ở đây chính là việc số lượng phép tính cần thiết để tìm ra một lời
giải cho bài toán là rất lớn. Trong lịch sử 20 năm của ngành mã hóa quy ước đã có
nhiều đề xuất khác nhau cho dạng bài toán như vậy, tuy nhiên chỉ có hai trong số
các đề xuất đó còn tồn tại vững đến ngày này. Hai bài toán đó bao gồm: bài toán
logarit rời rạc (The discrete logarithm problem) và bài toán phân tích thừa số của số
nguyên.
Cho đến năm 1985, hai nhà khoa học Neal Koblitz và Victor S. Miller đã
độc lập nghiên cứu và đưa ra đề xuất ứng dụng lý thuyết toán học elliptic curve
(đường cong elip) trên trường số hữu hạn (finite field)[21].
Elliptic curve – cũng như đại số hình học – được nghiên cứu rộng rãi trong
vòng 150 năm trở lại đây và đã đạt được một số lý thuyết có giá trị.1 Elliptic Curve
được phát hiện lần đầu vào thế kỷ 17 dưới dạng công thức Diophantine:y2 – x3 = c
với c Î Z.
Tính bảo mật của hệ thống mã hóa sử dụng elliptic curve dựa trên điểm mấu
chốt là độ phức tạp của bài toán logarit rời rạc trong hệ thống đại số. Trong suốt 10
năm gần đây, bài toán này nhận được sự quan tâm chú ý rộng rãi của các nhà toán
học hàng đầu trên thế giới. Không giống như bài toán logarit rời rạc trên trường hữu
hạn hoặc bài toán phân tích thừa số của số nguyên, bài toán logarit rời rạc trên
elliptic curve chưa có thuật toán nào có thời gian thực hiện nhỏ hơn cấp lũy thừa.
Thuật toán tốt nhất được biết cho đến hôm nay tốn thời gian thực hiện cấp lũy
thừa.[22]
Nội dung phần này đề cập đến một số lý thuyết về elliptic curve.
1
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
26
3.3.1.1. Công thức Weierstrasse và Elliptic curve
Gọi K là một trường hữu hạn hoặc vô hạn. Một đường cong elliptic curve
được định nghĩa trên trường K bằng công thức Weierstrass:
y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 ( 3.1)
trong đó a1, a2, a3, a4, a6 Î K.
Elliptic curve trên trường K được ký hiệu E(K). Số lượng các điểm nguyên
trên E ký hiệu là #E(K), có khi chỉ đơn giản là #E. Đối với từng trường khác nhau,
công thức Weierstrass (1) có thể được biến đổi và đơn giản hóa thành các dạng khác
nhau. Một đường elliptic curve là tập hợp các điểm thỏa công thức ( 3.1)
Hình 3-2: Một ví dụ về elliptic curve.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
27
3.3.1.2. Elliptic Curve trên trường R2
Elliptic curve E trên trường số thực R là tập hợp các điểm dưới dạng (x, y)
với x, y, a4,a6 Î R thoả mãn công thức: y2 = x3 + a4x + a6 ( 3.2)
cùng với một điểm đặc biệt O được gọi là điểm tại vô cực (cũng là phần tử identity).
Cặp giá trị x, y đại diện cho một điểm trên elliptic curve và tạo nên mặt phẳng tọa
độ 2 chiều (affine) R´R. Elliptic curve E trên R2 được gọi là định nghĩa trên R, ký
hiệu là E(R). Elliptic curve trên số thực có thể dùng để thể hiện một nhóm (E(R), +)
bao gồm tập hợp các điểm (x, y) Î R ´ R với phép cộng + trên E(R).
3.3.1.2.1. Phép cộng
Phép cộng điểm (ESUM, cũng được gọi là phép cộng curve) được định nghĩa
trên tập E(R) của các điểm (x, y). Điểm tại vô cực O là điểm cộng với bất kỳ điểm
nào cũng sẽ ra chính điểm đó.
Như vậy,." P = (x, y) Î E(R), P + O = O + P = P:
" P(x, y) Î E(R) : ±y = 643 axax ++ ( 3.3)
Như vậy, với 1 giá trị x ta sẽ có 2 giá trị toạ độ y.
Điểm (x, -y) ký hiệu là -PÎE(R), được gọi là điểm đối của P với:
P + (- P) = (x, y) + (x, -y) = O ( 3.4)
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
28
Hình 3-3: Điểm ở vô cực.
Phép cộng trên E(R) đựợc định nghĩa theo phương diện hình học. Giả sử có 2 điểm
phân biệt P và Q, P, Q Î E(R). Phép cộng trên nhóm elliptic curve là P+Q=R,
RÎE(R).
Hình 3-4: Phép cộng trên elliptic curve.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
29
Để tìm điểm R, ta nối R và Q bằng đường thẳng L. Đường thẳng L sẽ cắt E
tại 3 điểm P, Q và -R(x, y). Điểm R(x, -y) sẽ có tung độ là giá trị đối của y.
Thể hiện phép cộng elliptic curve dưới dạng đại số, ta có:
P = (x1, y1)
Q = (x2, y2) ( 3.5)
R = P + Q = (x3, y3)
trong đó P, Q, R Î E(R) và:
x3 = q 2 – x1 – x2
y3 = q (x1 + x3) – y1 ( 3.6)
q =
12
12
xx
yy
-
-
nếu P ≠ Q ( 3.7)
hoặc q =
1
4
2
1
2
3
y
ax +
nếu P = Q ( 3.8)
v Thuật toán cộng elliptic curve có thể được thể hiện như sau:
Thuật toán 3.1: Thuật toán cộng điểm Elliptic Curve.
INPUT: Đường elip E(R)với các tham số a4, a6 Î E(R) ,
Điểm P = (x1, y1)ÎE(R) và Q = (x2, y2)ÎE(R)
OUTPUT: R=P+Q, R = (x3, y3)ÎE(R)
1. Nếu P = O , thì R < - Q và trả về giá trị R
2. Nếu Q = O , thì R <- P và trả về giá trị R
3. Nếu x1 = x2 thì
3.1 Nếu y1 = y2 thì
q <-
1
4
2
1
2
3
y
ax +
3.2 Ngược lại nếu y1 = - y2 thì
R <- O và trả về R,
Ngược lại
q <-
12
12
xx
yy
-
-
4. x3 = q2 – x1 – x2
5. y3 = q(x1 + x3) – y1
6. Trả về(x3, y3) = R
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
30
3.3.1.2.2. Phép nhân đôi
Trong phép cộng, nếu cộng 2 điểm P, Q Î E(R) với P = Q thì đường thẳng L
sẽ là tiếp tuyến của elliptic curve tại điểm P. Trường hợp này điểm –R sẽ là giao
điểm còn lại của L với E. Lúc đó R = 2P.
Hình 3-5: Phép nhân đôi trên elliptic curve.
3.3.1.3. Elliptic curve trên trường hữu hạn
Elliptic curve được xây dựng trên các trường hữu hạn. Có hai trường hữu hạn
có thể được sử dụng: Trường hữu hạn Fq với q là số nguyên tố hoặc q là 2m (m là số
nguyên).
Tùy thuộc vào trường hữu hạn Fq với mỗi bậc của q, tồn tại nhiều elliptic
curve, do đó với một trường hữu hạn cố định có q phần tử và q lớn, có nhiều sự lựa
chọn nhóm elliptic curve.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
31
3.3.1.3.1. Elliptic trên Fp (p là số nguyên tố)
Cho p là số nguyên tố (p > 3), Cho a, b Î Fp sao cho 4a3 + 27b2 ≠ 0 trong
trường Fp. Một elliptic curve E(Fp) trên Fp (được định nghĩa bởi các tham số a và b)
là một tập hợp các cặp giá trị (x, y) (x, y Î Fp) thỏa công thức
y2 = x3 + ax + b ( 3.9)
cùng với một điểm O – gọi là điểm tại vô cực. Số lượng điểm của E(Fp) là #E(Fp)
thỏa định lý Hasse như sau:
ppFEpp p 21)(#21 ++££-+ ( 3.10)
Các phép toán của elliptic curve trên Fp cũng tương tự với E(R), thay vì tính
toán trên số thực, các phép tính được thực hiện trên modulo số nguyên tố lớn. Tập
hợp các điểm trên E(Fp) tạo thành một nhóm tuân theo các luật như sau:
1. Tính đóng: " a, b Î G, a + b Î G.
2. Tính kết hợp: Các phép toán trong nhóm có tính kết hợp.
Do đó, (a + b) + c = a + (b + c).
3. Tính đồng nhất: có một giá trị 0 Î G sao cho a + 0 = 0 + a = a " a Î G.
4. Tính đối: " a Î G, tồn tại –a Î G gọi là số đối của a,
sao cho –a + a = a + -a = 0.
Bậc của một điểm A trên E(Fp) là một số nguyên dương r sao cho:
O
r
AAA =+++ ...
( 3.11)
3.3.1.3.2. Elliptic curve trên mF2
Một elliptic curve E( mF2 ) trên mF2 được định nghĩa bởi các tham số a, b Î
mF2 , b≠ 0 là tập các điểm (x, y) với x Î mF2 , y Î mF2 thỏa công thức:
y2 + xy = x3 + ax2 + b ( 3.12)
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
32
cùng với điểm O là điểm tại vô cực. Số lượng các điểm thuộc E( mF2 ) ký hiệu
#E( mF2 ) thoả định lý Hasse:
qqFEqq m 21)(#21 2 ++££-+ ( 3.13)
trong đó q = 2m. Ngoài ra, #E( mF2 ) là số chẵn.
Tập hợp các điểm thuộc E( mF2 ) tạo thành một nhóm tuân theo các luật sau:
1. O + O = O.
2. (x, y) + O = (x, y) "(x, y) Î E( mF2 ).
3. (x, y) + (x, x + y) = O "(x, y) Î E( mF2 ). (Khi đó (x, x + y) là điểm
đối của (x, y) trên E( mF2 )).
Việc xử lý được thực hiện trên 2 hệ toạ độ khác nhau: hệ toạ độ affine và hệ
toạ độ quy chiếu. Với các hệ toạ độ khác nhau, việc tính toán trên đường cong cũng
khác nhau.
v Các phép toán Elliptic Curve trong hệ tọa độ Affine
Hệ mã hóa elliptic curve dựa trên vấn đề logarit rời rạc trên E( mF2 ) và các
tính toán cơ bản trên elliptic curve . Phép nhân được thể hiện là một dãy các phép
cộng và phép nhân đôi các điểm của elliptic curve.Giống như EC trên số thực, phép
cộng và phép nhân đôi được định nghĩa trên hệ toạ độ.
Xét đường elliptic curve E trên mF2 trong hệ toạ độ affine [23] và P, Q là 2
điểm trên E( mF2 ). Cho P = (x1, y1), Q = (x2, y2) thì điểm đối của P là – P = (x1, y1 +
x1) Î E( mF2 ).
Nếu Q ≠ -P thì P + Q = R = (x3, y3) Î E( mF2 ).
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
33
Nếu P ≠ Q:
ï
ï
ï
î
ïï
ï
í
ì
+++=
++++=
+
+
=
13313
221
2
3
21
21
)( yxxxy
axxx
xx
yy
q
qq
q
( 3.14)
Nếu P = Q thì
ï
ï
ï
î
ïï
ï
í
ì
++=
++=
+=
3
2
13
2
2
3
1
1
1
)1( xxy
ax
x
x
y
q
qq
q
( 3.15)
Thuật toán:
Thuật toán 3.2: Thuật toán cộng điểm trong hệ toạ độ Affine.
INPUT: Đường cong elip E( mF2 )với các tham số a2,a6 Î mF2 ,
Điểm P = (x1, y1) Î E( mF2 ) và Q = (x2, y2) Î E( mF2 )
OUTPUT: R=P+Q, R = (x3, y3) Î E ( mF2 )
1. Nếu P = O , thì R <- Q và trả về giá trị R
2. Nếu Q = O , thì R <- P và trả về giá trị R
3. Nếu x1 = x2 thì
3.1 Nếu y1 = y2 thì
1
1
1 x
x
y
+¬q và x3 <- q2 + q + a2
3.2 Ngược lại nếu y2 = x1 + y1
R <- O và trả về R,
Ngược lại
21
21
xx
yy
+
+
¬q
4. x3 <- q2 + q + x1 + x2 + a2
5. y3 <- (x1 + x3)q + x3 + y1
6. Trả về (x3, y3) = R
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
34
v Các phép toán Elliptic Curve trong hệ tọa độ chiếu.
Đường cong E( mF2 )có thể được xem là tương đương với tập hợp các điểm
E'( mF2 ) trên mặt phẳng quy chiếu P
2( mF2 ) thỏa mãn công thức:
y2z + xyz = x3 + a2x2z2 + a6z3. ( 3.16)
Sử dụng hệ toạ độ quy chiếu [23], thao tác tính nghịch đảo cần cho phép
cộng và phép nhân đôi điểm trong hệ affine có thể được loại bỏ.
v Chuyển đổi giữa hệ toạ độ Affine và hệ toạ độ chiếu
Với mọi điểm (a, b) Î E( mF2 ) trong hệ toạ độ affine có thể được xem là bộ
ba (x, y, z) trong E'( mF2 ) trong hệ quy chiếu với x = a, y = b, z = 1. Hơn nữa, một
điểm (tx, ty, tz) trong hệ quy chiếu với t ≠ 0 được xem như trùng với điểm (x, y, z).
Như vậy, chuyển đổi giữa hệ affine và hệ quy chiếu như sau:
M(a, b) = M'(a, b, 1) ( 3.17)
N(p, q, r) = N'( 1,,
r
q
r
p
) = N(
r
q
r
p , ) ( 3.18)
v Các phép toán Curve trong hệ toạ độ chiếu
Phương pháp trình bày công thức của phép cộng và nhân đôi trong hệ quy
chiếu tương tự với hệ affine.
Cho P' = (x1: y1 : z1) Î E'( mF2 ), Q' = (x2 : y2 : z2) Î E'( mF2 ) và P' ≠ - Q' trong
đó P', Q' thuộc hệ toạ độ quy chiếu.
Do P' = (x1 / z1 : y1 / z1 : 1), ta có thể áp dụng công thức cộng và nhân cho
điểm P(x1/z1, y1/ z1) và Q (x2, y2) cho E( mF2 ) trong hệ affine để tìm
P' + Q' = R' (x'3: y'3: 1)
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
35
Từ đó ta có:
1
1
33
1
1
3
2
1
2
2
3
')'('
'
z
yxx
z
x
A
By
a
z
A
A
B
A
Bx
+++=
+++=
( 3.19)
Trong đó A = (x2z1 + x1) và B = (y2z1 + y1). Đặt z3 = A3z1 và x3 = x'3z3, y3 =
y'3z3, nếu P + Q = (x3: y3: z3) thì:
x3 = AD,
y3 = CD + A2(Bx1 + Ay1) ( 3.20)
z3 = A3z1
Với C = A + B và D = A2(A + a2z1) + z1BC.
Tương tự 2P = (x3 : y3 : z3) với
x3 = AB,
y3 = x14A + B(x12 + y1z1 + A) ( 3.21)
z3 = A3
Trong đó A = x1z1 và B = a6z14 + x14. Điểm kết quả có thể được chuyển trở lại
sang hệ affine bằng cách nhân với z3-1. Như vậy sẽ không có thao tác tính nghịch
đảo trong hệ quy chiếu. Do đó chỉ cần 1 phép nghịch đảo sau một dãy các phép
cộng và nhân đôi để chuyển sang hệ affine.
Tọa độ affine Tọa độ chiếu
Thao tác
ESUM EDBL ESUM EDBL
Nhân 2 2 13 7
Nghịch đảo 1 1 0 0
Bảng 3-1: So sánh các phép toán trên elliptic trên tọa độ Affine và tọa độ chiếu .
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
36
3.3.1.3.3. Phép nhân Curve
Phép nhân được định nghĩa như một dãy các phép cộng và nhân đôi.
Q = c´P =
c
P...PP +++
( 3.22)
v Thuật toán cho hệ toạ độ affine
Thuật toán 3.3: Thuật toán nhân điểm trong hệ toạ độ Affine.
v Thuật toán cho hệ toạ độ quy chiếu.
Thuật toán 3.4: Thuật toán nhân điểm trong hệ tọa độ chiếu.
INPUT: P Î E( mF2 ) and c Î mF2
OUTPUT: Q=cP
1. å == iini bc 20 , bi Î {0, 1}, bn = 1
2. Biểu diễn P trong hệ tọa độ chiếu: P'
3. Set Q' <- P'
4. For i from n-1 downto 0
4.1 Q' <- Q' + Q' (Projective EDBL)
4.2 Nếu bi = 1 thì
Q' <- Q' + P' (Projective ESUM)
5. Biểu diễn Q' trong hệ tọa độ affine Q
6. Trả về Q
INPUT: P Î E( mF2 ) and c Î mF2
OUTPUT: Q=c´P
1. å == iini bc 20 , bi Î {0, 1}, bn = 1
2. Q <- P
3. For i from n-1 downto 0
3.1 Set Q <- Q + Q (Affine EDBL)
3.2 If bi = 1 then
Set Q <- Q + P (Affine ESUM)
4. Trả về Q
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
37
3.3.1.4. Bài toán Logarit rời rạc trên Elliptic Curve
Bài toán: Cho E là một đường elliptic curve và P Î E là một điểm có bậc n. Cho
điểm Q Î E, tìm số nguyên dương m ( 2 <= m <= n - 2 ) thỏa mãn công thức Q =
m´P
Để giải bài toán này, hiện nay chưa có thuật toán nào được xem là hiệu quả.
Các thuật toán được đưa ra đều có chi phí về tốc độ tính toán rất lớn. Nói cách khác,
để giải bài toán logarit rời rạc trên Elliptic Curve cần phải kiểm tra tất cả các giá trị
mÎ[2..n-2] (vét cạn). Nếu điểm P được chọn lựa cẩn thận với n rất lớn, việc giải bài
toán ECDLP được xem như không khả thi với thời gian cho phép. Việc giải quyết
ECDLP thật sự khó khăn hơn việc giải quyết bài toán logarit rời rạc trên trường số
nguyên thông thường[24]1.
3.3.2. Áp dụng lý thuyết Elliptic Curve vào mã hóa
Các lý thuyết toán học nền tảng của Elliptic Curve được các nhà khoa học áp dụng
khá hiệu quả vào lĩnh vực mã hóa, bảo mật (Elliptic Curve Cryptography - ECC).
Elliptic Curve được sử dụng để mã hóa dữ liệu, trao đổi khóa, và ký nhận điện tử .
3.3.2.1. Mã hóa dữ liệu với Elliptic Curve
Mô hình mã hóa dữ liệu với Elliptic Curve (Elliptic Curve Encryption
Scheme - ECES) bao gồm 2 thao tác: mã hóa và giải mã .
Trước khi thực hiện việc mã hóa dữ liệu với Elliptic Curve, người gởi và người
nhận cần phải sở hữu một cặp khóa công khai – khóa riêng. Các giá trị sau được
quy ước chung giữa người gởi và người nhận, gọi là các tham số chung của hệ
thống mã hóa:
· Đưòng cong elliptic curve E.
· Điểm P, P Î E. Điểm P có bậc n (n´P = O).
1 trang 41, Digital Signatures – Mohan Atreya, Ben Hammond, Stephen Paine, Paul Starrett, Stephen Wu,
RSA Press McGraw-Hill, 2002.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
38
v Quá trình tạo khóa được thực hiện như sau:
· Chọn một số nguyên bất kỳ d, d Î [2, n-2]. Số nguyên này chính là khóa
riêng
· Tính giá trị của điểm Q = d´P. QÎ E. Q chính là khóa công khai.
3.3.2.1.1. Thao tác mã hóa
Thao tác mã hóa sẽ mã hóa một thông điệp bằng khóa công khai của người
nhận và các tham số đường cong đã được quy ước thống nhất chung giữa người gởi
(B) và người nhận (A).
v Trình tự mã hóa được thực hiện như sau:
1. B sử dụng khóa công khai của A (QA).
2. B chọn một số nguyên bất kỳ k Î [2, n-2].
3. B tính giá trị của điểm (x1, y1) = k´P.
4. B tính giá trị của điểm (x2, y2) = k´QA. x2 là giá trị bí mật sẽ được sử dụng để
tạo khóa mã hóa thông điệp.
5. B tạo mặt nạ (mask) Y từ giá trị bí mật x2. Giá trị của Y được tạo thành từ
một hàm mask generation. Tùy theo việc cài đặt hàm mask generation mà Y
sẽ có giá trị khác nhau. Y chính là khóa quy ước để mã hóa thông điệp.
6. B tính giá trị C = Y Å M. C chính là thông điệp đã được mã hóa.
7. B gởi cho A thông điệp đã mã hóa C cùng với giá trị (x1, y1).
v Lưu ý:
· Giá trị k và (x1, y1) được tạo ra không phải khóa riêng và khóa công khai để
giao dịch của B. Đây là cặp khóa công khai – khóa riêng được phát sinh nhất
thời (one-time key pair) nhằm mã hóa thông điệp. Mỗi một thông điệp mã
hóa nên sử dụng một cặp khóa công khai – khóa riêng được phát sinh ngẫu
nhiên.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
39
· Việc mã hóa dữ liệu của ECES được thực hiện bằng toán tử eXclusive – OR
khóa và thông điệp. Điều này sẽ làm giảm độ bảo mật của thuật toán mã
hóa. Trên thực tế các hệ thống mã hóa bằng Elliptic curve thay bước thực
hiện XOR thông điệp bằng cách kết hợp với một thuật toán mã hóa quy ước
hiệu quả hơn (ví dụ ECAES: kết hợp ECES với AES).[22]
3.3.2.1.2. Thao tác giải mã
Bằng việc sử dụng các tham số quy ước kết hợp với khóa bí mật của người
nhận (A) và giá trị (x1, y1), A thực hiện giải mã thông điệp được mã hóa bằng
ECES (C) theo trình tự sau:
Trình tự giải mã:
1. A nhận giá trị (x1, y1).
2. A tính giá trị của điểm (x2, y2) = d´(x1, y1). x2 là giá trị bí mật sẽ được sử
dụng để tạo khóa giải mã thông điệp.
3. Sử dụng cùng một hàm tạo mặt nạ (mask function) như đã sử dụng ở giai
đoạn mã hóa, A tạo mặt nạ Y từ giá trị bí mật x2. Y chính là khóa bí mật để
giải mã.
4. A giải mã thông điệp C để lấy thông điệp M ban đầu bằng cách tính giá trị
M = C Å Y
3.3.2.2. Trao đổi khóa theo phương pháp Diffie - Hellman sử dụng
Elliptic Curve (ECDH)
v Mô hình trao đổi khóa Diffie-Hellman
Năm 1976, Whitfield Diffie và Martin Hellman đã đưa ra một giao thức để
trao đổi các giá trị khóa quy ước giữa các đối tác trên đường truyền có độ bảo mật
trung bình. Sự ra đời của giao thức trao đổi khóa Diffie-Hellman được xem là bước
mở đầu cho lĩnh vực mã hóa khóa công khai.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
40
Giao thức này dựa trên nguyên lý của bài toán logarit rời rạc trên trường số
nguyên hữu hạn. Các thao tác thực hiện trao đổi khóa Diffie-Hellman giữa hai đối
tác A và B như sau:
1. A và B thống nhất các giá trị g và số nguyên tố p < g.
2. A chọn một số ngẫu nhiên m. A tính giá trị QA = gm và gởi QA cho B.
3. B chọn một số ngẫu nhiên n. B tính giá trị QB = gn và gởi QB cho A.
4. A nhận được QB và tính giá trị k = (QB)m = gn´m.
5. B nhận được QA và tính giá trị k = (QA)n = gm´n.
k chính là giá trị bí mật được quy ước chung.
v Mô hình trao đổi khóa Elliptic Curve Diffie - Hellman
Mô hình trao đổi khóa Elliptic curve Diffie-Hellman tương tự mô hình trao
đổi khóa Diffie-Hellman. ECDH cũng dựa vào nguyên lý của bài toán logarit rời rạc
nhưng ápdụng trên đường elliptic curve. Mô hình này dùng để thiết lập một hoặc
nhiều khóa quy ước chung giữa hai đối tác A và B.
Các thao tác để trao đổi khóa bằng ECDH được thực hiện như sau:
1. A và B thống nhất các tham số sẽ sử dụng như: đường elliptic curve E, và
điểm P(x, y)
2. A chọn một giá trị m ngẫu nhiên. A tính giá trị điểm QA = m´P và gởi QA
cho B.
3. B chọn một giá trị n ngẫu nhiên. B tính giá trị điểm QB = n´P và gởi QB cho
A.
4. A nhận được QB và tính giá trị G = m´QB = m´n´P.
5. B nhận được QA và tính giá trị G = n´QA = n´m´P.
Giá trị G = m´n´P chính là giá trị bí mật được quy ước chung.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
41
Giả sử có một người C tấn công vào đường truyền và lấy được các giá trị QA,
QB, E, P, C cần lấy được m hoặc n để tìm G = m´n´P. Điều đó chính là C phải giải
bài toán logarit rời rạc trên elliptic curve. Giải bài toán này đòi hỏi chi phí tính toán
tương đương với sử dụng thuật toán vét cạn trên elliptic curve.
3.4. Đánh giá các phương pháp mã hóa khóa công khai
Hệ thống mã hóa khóa công khai ra đời đã giải quyết các hạn chế của mã hóa
quy ước. Mã hóa khóa công khai sử dụng một cặp khóa, một khóa (thông thường là
khóa riêng) dùng để mã hóa và một khóa (khóa riêng) dùng để giải mã. Mã hóa
khóa công khai giúp tránh bị tấn công khi trao đổi khóa do khóa để giải mã (khóa
riêng) không cần phải truyền hoặc chia sẻ với người khác. Ngoài ra, mỗi người chỉ
cần sở hữu một cặp khóa công khai – khóa riêng và người gởi thông tin chỉ cần giữ
khóa công khai của người nhận do đó số lượng khóa cần phải quản lý giảm khá
nhiều. Mỗi người chỉ cần lưu trữ bảo mật một khóa riêng của chính mình.
Tuy nhiên, do nhu cầu mã hóa và giải mã bằng hai khóa khác nhau trong cùng
một cặp khóa nên để đảm bảo bảo mật, kích thước khóa công khai – khóa riêng lớn
hơn rất nhiều so với khóa công khai. Do đó tốc độ mã hóa khóa công khai chậm hơn
tốc độ mã hóa khóa quy ước. Tốc độ mã hóa bằng phần mềm của thuật toán DES
nhanh hơn khoảng 100 lần so với mã hóa RSA với cùng mức độ bảo mật[26].
Kích thước khóa (tính bằng bit)
Khóa công khai 56 80 112 128 192 256
RSA/DSA 512 1K 2K 3K 7.5K 15K
ECC 160 224 256 384 512
Bảng 3-2: So sánh kích thước khóa giữa mã hóa quy ước và mã hóa khóa công khai với cùng mức độ
bảo mật.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
42
3.4.1. Ứng dụng của mã hóa khóa công khai
Với đặc điểm mã hóa và giải mã bằng hai khóa khác nhau, các phương pháp
mã hóa khóa công khai ngoài chức năng mã hóa thông tin còn được áp dụng trong
rất nhiều chức năng ứng dụng khác.
3.4.1.1. Trao đổi khóa
Trao đổi khóa là ứng dụng chính của mã hóa khóa công khai. Mục đích của
trao đổi khóa là sử dụng mã hóa khóa công khai để chuyển tải một khóa quy ước
cho phương pháp giải mã bí mật. Do mã hóa khóa công khai có tốc độ mã hóa chậm
nên để mã hóa lượng thông tin lớn cần phải sử dụng phương pháp mã hóa quy ước.
Mã hóa khóa công khai mã hóa khóa quy ước được sử dụng có kích thước khá nhỏ
nên tốc độ thực hiện sẽ nhanh hơn.
3.4.1.2. Chữ ký điện tử
Mục đích chữ ký điện tử là đảm bảo tính chất chống chối bỏ trách nhiệm và
xác nhận nguồn gốc thông tin. Chữ ký điện tử tương tự chữ ký viết tay có tính năng
đảm bảo nguồn gốc cho thông tin và xác nhận nội dung cũng như trách nhiệm trên
nội dung của thông tin. Chữ ký điện tử sử dụng mã hóa khóa công khai để mã hóa
và giải mã thông điệp rút gọn của dữ liệu nhằm xác thực dữ liệu được trao đổi. Phần
4.2 sẽ trình bày chi tiết hơn về chữ ký điện tử.
3.4.1.3. Chứng nhận điện tử
Trong mã hóa khóa công khai, khóa công khai được trao đổi rộng rãi giữa
các đối tác. Chính vì lý do này nên khi nhận được một khóa công khai do một người
khác gửi đến, người nhận thường băn khoăn không biết đây có phải là khóa công
khai của chính người mà mình muốn trao đổi hay không. Chứng nhận khóa công
khai và tổ chức chứng nhận khóa công khai (Certificate Authority - CA) ra đời với
mục đích xác nhận tính hợp lệ và nguồn gốc của khóa công khai được sử dụng. Một
chứng nhận điện tử bao gồm các thông tin cơ bản về khóa công khai, tổ chức cấp
khóa công khai, người sở hữu khóa và ngày hết hạn của khóa. Việc chứng nhận
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
43
khóa công khai được thực hiện qua trung gian các tổ chức chứng nhận theo 3 mô
hình: phân cấp, tập trung và Web of Trust[6].
Hình 3-6: Mô hình CA tập trung.
CA Trung öông
CA Chi nhaùnh CA Chi nhaùnh
CA CA CA CA
Ngöôøi söû duïng
Hình 3-7: Mô hình CA phân cấp.
AB
C
D E
F
Hình 3-8: Mô hình CA Web of Trust.
3.4.2. So sánh giữa các phương pháp mã hóa khóa công khai
Mã hóa khóa công khai dựa trên hai vấn đề lớn của toán học là bài toán
logarit rời rạc và bài toán phân tích thừa số của số nguyên. Phương pháp RSA dựa
trên bài toán phân tích thừa số của số nguyên tố và đã được đưa ra từ cuối thập niên
70. Phương pháp ECC dựa trên bài toán logarit rời rạc trên trường số của đường
elliptic curve (ECDLP) chỉ mới được đưa ra từ năm 1985.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
44
Một ưu điểm của ECC là khả năng bảo mật cao với kích thước khóa nhỏ dựa
vào mức độ khó giải quyết của vấn đề ECDLP. Đây chính là một tính chất rất hữu
ích đối với xu hướng ngày nay là tìm ra phương pháp tăng độ bảo mật của mã hóa
khóa công khai với kích thước khóa được rút gọn.[32] Kích thước khóa nhỏ hơn
giúp thu gọn được kích thước của chứng nhận giao dịch trên mạng và giảm kích
thước tham số của hệ thống mã hóa. Kích thước khóa nhỏ giúp các hệ thống bảo
mật dựa trên ECC giảm thời gian tạo khóa. Thời gian tạo khóa thường rất lớn ở các
hệ thống RSA[26].
Thời gian cần để tấn
công vào khóa
(đơn vị: năm)
Kích thước khóa
RSA / DSA
Kích thước
khóa
ECC
Tỉ lệ kích thước
khóa RSA : ECC
104 512 106 5:1
108 768 132 6:1
1011 1024 160 7:1
1020 2048 210 10:1
1078 21000 600 35:1
Bảng 3-3: So sánh kích thước khóa RSA và ECC với cùng độ bảo mật
COMPARISON OF SECURITY
LEVELS of ECC and RSA / DSA
0
500
1000
1500
2000
2500
3000
51000 4E+07 2E+12 4E+16 7E+23
Time to break key (MIPS years)
K
ey
Si
ze
(b
its
)
RSA/DSA
ECC
Hình 3-9: So sánh mức độ bảo mật giữa ECC, RSA / DSA.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 3 Mã hóa khóa công khai.
45
Do có kích thước khóa nhỏ và khả năng phát sinh khóa rất nhanh nên ECC rất
đưọc quan tâm để áp dụng cho các ứng dụng trên môi trường giới hạn về thông
lượng truyền dữ liệu, giới hạn về khả năng tính toán, khả năng lưu trữ. ECC thích
hợp với các thiết bị di động kỹ thuật số như handheld, PDA, điện thoại di động và
thẻ thông minh (smart card).
Các hệ thống ECC đã và đang được một số công ty lớn về viễn thông và bảo
mật trên thế giới quan tâm phát triển. Nổi bật trong số đó là Certicom (Canada) kết
hợp với đại học Waterloo đã nghiên cứu và xem ECC như là chiến lược phát triển
bảo mật chính của công ty. Certicom cung cấp dịch vụ bảo mật dựa trên ECC.
Ngoài ra, một số công ty khác như Siemens (Đức), Matsushita (Nhật), Thompson
(Pháp) cũng nghiên cứu phát triển ECC. Mới đây, RSA Security Laboratory –
phòng thí nghiệm chính của RSA – đã bắt đầu nghiên cứu và đưa ECC vào sản
phẩm của mình.[31]
Tuy nhiên, ECC vẫn có một số hạn chế nhất định. Hạn chế lớn nhất hiện nay là
việc chọn sử dụng các tham số đường cong và điểm quy ước chung như thế nào để
thật sự đạt được độ bảo mật cần thiết. Hầu hết các đường cong được đưa ra đều thất
bại khi áp dụng vào thực tiễn. Do đó hiện nay số lượng đường cong thật sự được sử
dụng không được phong phú. NIST đề xuất một số đường cong elliptic curve đã
được kiểm định là an toàn để đưa vào sử dụng thực tế trong tài liệu FIPS 186-2.
Ngoài ra, đối với các tham số mang giá trị nhỏ, mức độ bảo mật của ECC không
bằng RSA (khi e = 3). Đối với một số trường hợp RSA vẫn là lựa chọn tốt do RSA
đã chứng minh được tính ổn định trong một khoảng thời gian khá dài[12].
ECC vẫn còn non trẻ và cần được kiểm định trong tương lai tuy nhiên ECC
cung cấp khả năng ứng dụng rất lớn trong lĩnh vực mã hóa khóa công khai trên các
thiết bị di động và smart card. Tương lai ECC sẽ được nghiên cứu đưa vào thực tiễn
phổ biến hơn.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
46
Chương 4. Các thuật toán hàm băm và chữ ký điện tử
Dẫn nhập: Chương 4 trình bày về hàm băm và các thuật toán hàm băm mới theo
chuẩn hàm băm an toàn SHS và giới thiệu về thuật toán băm AES-HASH. Chương 4
cũng trình bày về chữ ký điện tử và các thuật toán chữ ký điện tử phổ biến hiện nay
gồm RSA, DSA, ECDSA.
4.1. Các thuật toán hàm băm
4.1.1. Giới thiệu hàm băm
Hàm băm là hàm toán học chuyển đổi một thông điệp có độ dài bất kỳ thành
một dãy bit có độ dài cố định (độ dài cố định tùy thuộc vào thuật toán băm). Dãy bit
này được gọi là message digest (thông điệp rút gọn) đại diện cho thông điệp ban
đầu. Hàm băm là một hàm một chiều (one-way function) do đó rất khó để lấy lại
thông điệp ban đầu từ message digest. Các thuật toán này cho phép xác định được
tính toàn vẹn dữ liệu của thông điệp: mọi thay đổi dù là nhỏ nhất của thông điệp đều
cho kết quả thông điệp rút gọn khác nhau. Tính chất này hữu ích trong việc phát
sinh, kiểm tra chữ ký điện tử, các đoạn mã chứng nhận thông điệp và phát sinh số
ngẫu nhiên.
Hàm băm là nền tảng cho nhiều ứng dụng mã hóa. Có nhiều thuật toán để
thực hiện hàm băm, trong số đó SHA-1 và MD5 được sử dụng phổ biến và đáng tin
cậy. Ngày 26/08/2002, Học viện Quốc gia về Chuẩn hóa và Công nghệ của Hoa Kỳ
(National Institute of Standard and Technology - NIST) đã đề xuất hệ thống chuẩn
hàm băm an toàn (Secure Hash Standard) gồm 4 thuật toán hàm băm SHA-1, SHA-
256, SHA-384, SHA-512. Đến 25/03/2004, NIST đã chấp nhận thêm thuật toán
hàm băm SHA-224 vào hệ thống chuẩn hàm băm. Các thuật toán hàm băm do NIST
đề xuất được đặc tả trong tài liệu FIPS180-2[19]
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
47
4.1.2. Giới thiệu các chuẩn thuật toán hàm băm Secure Hash
Standard(SHS) trong FIPS180-2 (02/2004)
Chuẩn SHS đặc tả 5 thuật toán băm an toàn SHA-1, SHA-2241, SHA-256,
SHA-384 và SHA-512.
Sự khác biệt chính của các thuật toán là số lượng bit bảo mật của dữ liệu
được băm – điều này có ảnh hưởng trực tiếp đến chiều dài của thông điệp rút gọn.
Khi một thuật toán băm đuợc sử dụng kết hợp với thuật toán khác đòi hỏi phải cho
kết quả số lượng bit tương ứng. Ví dụ, nếu một thông điệp được ký với thuật toán
chữ ký điện tử cung cấp 128 bit thì thuật toán chữ ký đó có thể đòi hỏi sử dụng một
thuật toán băm an toàn cung cấp 128 bit như SHA-256.
Ngoài ra, các thuật toán khác nhau về kích thước khối và kích thước từ dữ
liệu (word size) được sử dụng. Bảng 4-1 thể hiện các tính chất cơ bản của bốn thuật
toán băm an toàn.
Kích thước (đơn vị: bit) Thuật
toán Thông điệp Khối Từ Thông điệp
rút gọn
Độ an toàn2
(đơn vị: bit)
SHA-1 < 264 512 32 160 80
SHA-224 < 264 512 32 224 112
SHA-256 < 264 512 32 256 128
SHA-384 < 2128 1024 64 384 192
SHA-512 < 2128 1024 64 512 256
Bảng 4-1:Các tính chất của các thuật toán băm an toàn.
1 Đây là thuật toán hàm băm vừa được NIST công nhận thành chuẩn hàm băm an toàn vào 02/2004.
2 "Độ an toàn" là việc sử dụng phương pháp tấn công vào thông điệp rút gọn kích thuớc n, đòi hỏi xử lý xấp
xỉ 2n/2.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
48
4.1.2.1. Ý tuởng của các thuật toán hàm băm SHA
Các thuật toán hàm băm SHA gồm 2 buớc: tiền xử lý và tính toán giá trị băm.
· Bước tiền xử lý bao gồm các thao tác:
o Mở rộng thông điệp (Padding Message)
o Phân tích thông điệp đã mở rộng thành các khối m bit.
o Khởi tạo giá trị băm ban đầu.
· Bước tính toán giá trị băm bao gồm các thao tác:
o Làm N lần các công việc sau:
§ Tạo bảng phân bố thông điệp (message schedule) từ khối thứ i.
§ Dùng message schedule cùng với các hàm, hằng số, các thao
tác trên word để tạo ra giá trị băm i.
o Sử dụng giá trị băm cuối cùng để tạo thông điệp rút gọn.
4.1.2.2. Các tham số, ký hiệu và các thuật ngữ được sử dụng trong
SHA.
v Tham số:
a, b,c , ...,h Các biến là các từ w bit sử dụng trong việc tính toán giá trị
băm H(i).
H(i) Giá trị băm thứ i. H(0) là giá trị băm khởi đầu. H(N) là giá trị
băm cuối cùng và được sử dụng để xác định thông điệp rút
gọn.
Kt Hằng số sử dụng cho vòng lặp thứ t trong việc thực hiện băm.
k Số lượng các số 0 thêm vào thông điệp trong giai đoạn mở
rộng thông điệp.
l Chiều dài thông điệp M (tính bằng đơn vị bit).
m Số bit trong một khối thông điệp, M(t).
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
49
M(i) Khối thông điệp i, với giá trị m bit.
M(i)j Từ thứ j của khối thông điệp thứ i, M(t)0 là từ cực trái của khối
thông điệp i.
n Số lượng bit được dịch chuyển khi xử lý một từ.
N Số lượng khối trong thông điệp mở rộng.
T w-bit từ tạm sử dụng trong việc thực hiện băm.
w Số lượng bit trong một từ.
Wt Từ w-bit thứ t của bảng phân bố thông điệp.
v Ký hiệu:
Các ký hiệu sau được sử dụng trong SHA và xử lý trên các từ w-bit.
^ Thao tác AND trên bit.
Ú Thao tác OR trên bit.
Å Thao tác XOR trên bit.
Ø Thao tác đảo bit.
+ Thao tác cộng modulo 2w
<< Thao tác dịch trái, x << n loại bỏ n bit cực trái của từ x và
thêm n bit 0 vào bên phải của kết quả.
>> Thao tác dịch phải, x >> n loại bỏ n bit cực phải của từ x và
thêm n bit 0 vào bên trái của kết quả.
v Thuật ngữ:
Các thuật ngữ liên quan đến chuỗi bit và số nguyên được sử dụng:
a. Một ký số thập lục (hexa) là một phần tử trong tập hợp {0, 1,..., 9, a, ..., f}.
Một ký số thập lục biểu diễn một chuỗi 4-bit. Ví dụ, ký số thập lục "7" biểu
diễn chuỗi 4-bit "0111", ký số hexa "a" biểu diễn chuỗi 4 bit "1010".
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
50
b. Một từ là một chuỗi w-bit có thể được biểu diễn dưới dạng một dãy các ký số
hexa. Để chuyển đổi một từ sang ký số hexa, mỗi chuỗi 4-bit được chuyển
sand giá trị hexa tương ứng như phần (a). Ví dụ, chuỗi 32-bit
1010 0001 0000 0011 1111 1110 0010 0011
có thể được biểu diễn như sau "a103fe23", và chuỗi 64 bit
1010 0001 0000 0011 1111 1110 0010 0011
0011 0010 1110 1111 0011 0000 0001 1010
có thể được biểu diễn như sau "a103fe2332ef301a"
c. Quy ước "big-endian" được sử dụng trong tài liệu này khi biểu diễn từ có 32
và 64 bit . Do đó với mỗi từ, bit đầu tiên nằm ở vị trí cực trái.
d. Một số nguyên có thể được biểu diễn dưới dạng một từ hoặc một cặp từ. Một
từ biểu diễn độ dài thông điệp theo bit, l, được sử dụng trong thao tác mở
rộng thông điệp (phần 4.1.2.3.2).
Một số nguyên nằm trong khoảng 0 và 232-1 có thể được biểu diễn
bằmg một từ 32-bit. 4 bit cuối cùng của số nguyên được biểu diễn bằng ký số
hexa cực phải của từ. Ví dụ số nguyên 291 = 28 + 25 + 21 + 20 = 258 + 32 + 2
+ 1 được biểu diễn bằng từ hexa 0x00000123.
Tương tự, số nguyên trong khoảng 0 và 264-1 có thể biểu diễn bằng từ
64-bit.
Nếu Z là một số nguyên, 0 <= Z < 264 thì Z = 232X + Y, trong đó 0 <= X <
232 và 0 <= Y < 232. Do X và Y có thể được biểu diễn bằng từ 32-bit x và y,
nên số nguyên Z cũng có thể biểu diễn bằng một cặp từ (x, y). Tính chất này
được sử dụng trong SHA-1 và SHA-256.
Nếu Z là một số nguyên, 0 <= Z < 2128 thì Z = 264X + Y, trong đó 0
<= X < 264 và 0 <= Y < 264. Do X và Y có thể được biểu diễn bằng từ 64-bit
x và y, nên số nguyên Z cũng có thể biểu diễn bằng một cặp từ (x, y). Tính
chất này được sử dụng trong SHA-384 và SHA-512.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
51
e. Trong thuật toán băm an toàn, kích thước của khối thông điệp m bit dựa vào
thuật toán sau:
i. Đối với SHA-1 và SHA-256, mỗi khối thông điệp có 512 bit biểu diễn
dưới dạng một dãy 16 từ 32-bit.
ii. Đối với SHA-384 và SHA-512, mỗi khối thông điệp có 1024 bit biểu
diễn dưới dạng một dãy 16 từ 64-bit.
Các thao tác xử lý dưới đây đuợc áp dụng cho từ w-bit trong cả 5 thuật toán:
SHA-1, SHA-224 và SHA-256 thao tác trên từ 32-bit (w = 32), SHA-384 và SHA-
512 thao tác trên từ 64-bit (w = 64).
a. Các phép toán luân lý trên bit: Ù, Ú, Å và Ø
b. Phép cộng modulo 2w.
Phép cộng x + y được định nghĩa như sau. Từ x và y biểu diễn số nguyên X
và Y trong đó 0 <= X < 2w và 0 <= Y < 2w.
Z = (X + Y) mod 2w. ( 4.1)
thì 0 <= Z < 2w. Biến đổi số nguyên Z thành từ z, ta có z = x + y.
c. Phép toán dịch phải SHRn(x) với x là từ w-bit và n là số nguyên 0<= n<w
định nghĩa như sau
SHRn(x) = x >> n. ( 4.2)
Phép toán này được sử dụng trong SHA-256, SHA-384 và SHA-512.
d. Phép toán quay phải ROTRn(x) với x là từ w-bit và n là số nguyên 0<=n<w,
được định nghĩa như sau:
ROTRn(x) = (x >> n) Ú (x <<w – n) ( 4.3)
Như vậy, ROTRn(x) tương đương cho một thao tác xoay vòng từ x về
phía phải n vị trí.
Phép toán này được sử dụng trong SHA-256, SHA-384 và SHA-512.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
52
e. Phép toán quay trái ROTLn(x) với x là từ w-bit và n là số nguyên 0<=n<w,
được định nghĩa như sau:
ROTLn(x) = (x >w – n) ( 4.4)
Như vậy, ROTLn(x) tương đương cho một thao tác xoay vòng từ x về
phía trái n vị trí. Phép toán này được sử dụng trong SHA-1.
f. Lưu ý rằng các phép toán sau là tương đương với w là không đổi.
ROTLn(x) » ROTRw-n(x)
ROTRn(x) » ROTLw-n(x). ( 4.5)
4.1.2.3. Các thao tác tiền xử lý trong các thuật toán hàm băm
4.1.2.3.1. Các hàm xử lý
v SHA-1:
ï
ï
î
ï
ï
í
ì
££ÅÅ=
££ÙÅÙÅÙ=
££ÅÅ=
££ÙØÅÙ=
=
7960),,parity(
5940)()()(),,maj(
3920),,parity(
190)()(),,ch(
),,(f j
jzyxzyx
jzyzxyxzyx
jzyxzyx
jzxyxzyx
zyx
v SHA-224 và SHA-256:
)(SHR)(ROTR)(ROTR)(
)(SHR)(ROTR)(ROTR)(
)(ROTR)(ROTR)(ROTR)(
)(ROTR)(ROTR)(ROTR)(
)()()(),,maj(
ch(
101917256
1
3187256
0
25116256
1
22132256
0
xxxz
xxxz
xxxx
xxxx
zyzxyxzyz
z)x(y)(x z) y, x,
ÅÅ=
ÅÅ=
ÅÅ=
ÅÅ=
ÙÅÙÅÙ=
ÙØÅÙ=
å
å
s
s
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
53
v SHA-384 và SHA-512:
)(SHR)(ROTR)(ROTR)(
)(SHR)(ROTR)(ROTR)(
)(ROTR)(ROTR)(ROTR)(
)(ROTR)(ROTR)(ROTR)(
)()()(),,maj(
ch(
66119512
1
781512
0
411814512
1
293428512
0
xxxz
xxxz
xxxx
xxxx
zyzxyxzyz
z)x(y)(x z) y, x,
ÅÅ=
ÅÅ=
ÅÅ=
ÅÅ=
ÙÅÙÅÙ=
ÙØÅÙ=
å
å
s
s
4.1.2.3.2. Mở rộng thông điệp
Thông điệp M được mở rộng trước khi thực hiện băm. Mục đích của việc mở
rộng này là để đảm bảo thông điệp mở rộng có độ dài là bội số của 512 hoặc 1024
bit tùy thuộc vào thuật toán.
v SHA-1, SHA-224 và SHA-256:
Giả sử độ dài của thông điệp M là l bit. Thêm bit 1 vào cuối thông điệp, theo
sau là k bit 0 (k là số không âm nhỏ nhất sao cho )512(mod4481 º++ kl . Sau đó
thêm khối 64 bit là biểu diễn nhị phân của l .
Ví dụ, thông điệp (8-bit ASCII) "abc" có độ dài 8x3=24, do đó thông điệp
được mở rộng bằng 1 bit "1", 448-(24+1) = 423 bit "0" và chiều dài thông điệp trở
thành thông điệp mở rộng 512 bit.
64
24
423
011000...0000..001011000110110001001100001
=lcba
Chiều dài của thông điệp mở rộng đã trở thành một bội số của 512 bit.
v SHA-384 và SHA-512
Giả sử độ dài của thông điệp M là l bit. Thêm bit 1 vào cuối thông điệp, theo
sau là k bit 0 (k là số không âm nhỏ nhất sao cho )1024(mod8961 º++ kl . Sau đó
thêm khối 128 bit là biểu diễn nhị phân của l .
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
54
Ví dụ, thông điệp (8-bit ASCII) "abc" có độ dài 8x3=24, do đó thông điệp
được mở rộng bằng 1 bit "1", 896-(24+1) = 871 bit "0" và chiều dài thông điệp trở
thành thông điệp mở rộng 1024 bit.
128
24
01100000
871
00001011000110110001001100001
=lcba
.....
Chiều dài của thông điệp mở rộng đã trở thành một bội số của 1024 bit.
4.1.2.3.3. Phân tích thông điệp đã mở rộng
Sau khi thông điệp đã mở rộng, thông điệp cần được phân tích thành N khối m-
bit trước khi thực hiện băm.
Đối với SHA-1 và SHA-256, thông điệp mở rộng được phân tích thành N khối
512-bit M(1), M(2),..., M(N). Do đó 512 bit của khối dữ liệu đầu vào có thể được thể
hiện bằng 16 từ 32-bit, )(0
iM chứa 32 bit đầu của khối thông điệp i, )(1
iM chứa 32 bit
kế tiếp...
Đối với SHA-384 và SHA-512, thông điệp mở rộng được phân tích thành N
khối 1024-bit M(1), M(2),..., M(N). Do đó 1024 bit của khối dữ liệu đầu vào có thể
được thể hiện bằng 16 từ 64-bit, )(0iM chứa 64 bit đầu của khối thông điệp i,
)(
1
iM chứa 64 bit kế tiếp...
4.1.2.3.4. Khởi tạo giá trị băm
Giá trị băm là một chuỗi bit có kích thước bằng kích thước message digest
(trừ SHA-384) gồm các words ghép lại. Trong đó ( )ijH là word j trong giá trị băm ở
lần lặp i, với 0 <= i <= N (số block có được sau khi chia văn bản được đệm) và
0 <= j <= số word trong giá trị băm – 1. Trước khi thực hiện băm, với mỗi thuật
toán băm an toàn, giá trị băm ban đầu H(0) phải được thiết lập. Kích thước và số
lượng từ trong H(0) tùy thuộc vào kích thước thông điệp rút gọn.
Các giá trị băm ban đầu của các thuật toán SHA được trình bày trong phần
phụ lục B.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
55
4.1.2.4. Thuật toán của bước tính toán giá trị băm:
v SHA-1
SHA-1 được sử dụng để băm thông điệp M dài l bit 6420 <£ l . Thuật toán sử
dụng
a. Một bảng phân bố thông điệp gồm 80 từ 32-bit
b. 5 biến 32 bit.
c. Một giá trị băm gồm 5 từ 32-bit.
Kết quả của SHA-1 là thông điệp rút gọn 160-bit.
Các từ của bảng phân bố thông điệp được ký hiệu W0, W1, ..., W79. 5 biến ký
hiệu a, b, c, d, và e. Các từ của giá trị băm ký hiệu )(4
)(
1
)(
0 ,....,,
iii HHH , H(0) giữ giá
trị băm ban đầu, được thay thế bằng các giá trị băm thành công H(i) sau khi mỗi khối
thông điệp được xử lý và kết thúc bằng giá trị băm cuối cùng H(N). SHA-1 cũng sử
dụng một từ đơn tạm T.
Với i = 1 đến N:
{
Chuẩn bị bảng phân bố thông điệp {Wt}:
ïî
ï
í
ì
££ÅÅÅ
££
=
---- 7916(
150
161483
1
)(
tWWWWROTL
tM
W
tttt
i
t
t
Khởi tạo 5 biến ban đầu a, b, c, d và e, với giá trị băm thứ i-1:
a = )1(0 -iH
b = )1(1 -iH
c = )1(2 -iH
d = )1(3 -iH
e = )1(4 -iH
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
56
Với t = 0 đến 79:
{
T = ROTL5(a) + ft(b,c,d) + e + Kt + Wt
e = d
d = c
c = ROTL30(b)
b = a
a = T
}
Tính giá trị băm H(i) của vòng lặp thứ i
)(
0
iH = a + )1(0
-iH
)(
1
iH = b + )1(1
-iH
)(
2
iH = c + )1(2
-iH
)(
3
iH = d + )1(3
-iH
)(
4
iH = e + )1(4
-iH
}
Sau khi lặp 4 bước trên N lần ( sau khi xử lý M(N)), thông điệp rút gọn 160-bit của
thông điệp M là
)(
4
)(
3
)(
2
)(
1
)(
0
NNNNN HHHHH
Ký hiệu || chỉ phép nối chuỗi bit theo thứ tự đã định.
v SHA–224
SHA-224 được sử dụng để băm thông điệp M dài l bit 6420 <£ l . Thuật toán
sử dụng
a. Một bảng phân bố thông điệp gồm 64 từ 32-bit
b. 8 biến 32 bit.
c. Một giá trị băm gồm 8 từ 32-bit.
Kết quả của SHA-224 là thông điệp rút gọn 224-bit.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
57
Các từ của bảng phân bố thông điệp được ký hiệu W0, W1, ..., W63. 8 biến ký
hiệu a, b, c, d, e, f, g và h. Các từ của giá trị băm ký hiệu )(7
)(
1
)(
0 ,....,,
iii HHH , H(0)
giữ giá trị băm ban đầu, được thay thế bằng các giá trị băm thành công H(i) sau khi
mỗi khối thông điệp được xử lý và kết thúc bằng giá trị băm cuối cùng H(N). SHA-
224 cũng sử dụng hai từ đơn tạm T1, T2.
Với i = 0 đến N
{
Chuẩn bị bảng phân bố thông điệp {Wt}
ïî
ï
í
ì
££+++
££
=
---- 6316)()(
150
1615
}256{
072
}256{
1
)(
tWWWW
tM
W
tttt
i
t
t ss
Khởi tạo 8 biến a, b, c, d, e, f, g, h với giá trị băm thứ i-1
a = )1(0
-iH
b = )1(1
-iH
c = )1(2
-iH
d = )1(3
-iH
e = )1(4
-iH
f = )1(5
-iH
g = )1(6
-iH
h = )1(7
-iH
Với t = 0 đến 63:
{
T1 = h + tt WKgfeChe +++å
}256{}256{
1 ),,()(
T2 = ),,()(}256{0 cbaMaja +å
h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1 + T2
}
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
58
Tính giá trị băm H(i) của vòng lặp thứ i
)(
0
iH = a + )1(0
-iH
)(
1
iH = b + )1(1
-iH
)(
2
iH = c + )1(2 -iH
)(
3
iH = d + )1(3
-iH
)(
4
iH = e + )1(4
-iH
)(
5
iH = f + )1(5
-iH
)(
6
iH = g + )1(6
-iH
)(
7
iH = h + )1(7
-iH
}
Sau khi lặp 4 bước trên N lần ( sau khi xử lý M(N)), thông điệp rút gọn 224-bit
của thông điệp M là
)(
6
)(
5
)(
4
)(
3
)(
2
)(
1
)(
0
NNNNNNN HHHHHHH
v SHA-256
SHA-256 được sử dụng để băm thông điệp M dài l bit 6420 <£ l . Thuật toán
sử dụng
a. Một bảng phân bố thông điệp gồm 64 từ 32-bit
b. 8 biến 32 bit.
c. Một giá trị băm gồm 8 từ 32-bit.
Kết quả của SHA-256 là thông điệp rút gọn 256-bit.
Các từ của bảng phân bố thông điệp được ký hiệu W0, W1, ..., W63. 8 biến ký
hiệu a, b, c, d, e, f, g và h. Các từ của giá trị băm ký hiệu )(7
)(
1
)(
0 ,....,,
iii HHH , H(0)
giữ giá trị băm ban đầu, được thay thế bằng các giá trị băm thành công H(i) sau khi
mỗi khối thông điệp được xử lý và kết thúc bằng giá trị băm cuối cùng H(N). SHA-
256 cũng sử dụng hai từ đơn tạm T1, T2.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
59
Với i = 0 đến N
{ Chuẩn bị bảng phân bố thông điệp {Wt}
ïî
ï
í
ì
££+++
££
=
---- 6316)()(
150
1615
}256{
072
}256{
1
)(
tWWWW
tM
W
tttt
i
t
t
ss
Khởi tạo 8 biến a, b, c, d, e, f, g, h với giá trị băm thứ i-1
a = )1(0
-iH
b = )1(1
-iH
c = )1(2
-iH
d = )1(3
-iH
e = )1(4
-iH
f = )1(5
-iH
g = )1(6
-iH
h = )1(7
-iH
Với t = 0 đến 63:
{ T1 = h + tt WKgfeChe +++å
}256{}256{
1 ),,()(
T2 = ),,()(}256{0 cbaMaja +å
h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1 + T2
}
Tính giá trị băm H(i) của vòng lặp thứ i
)(
0
iH = a + )1(0
-iH
)(
1
iH = b + )1(1
-iH
)(
2
iH = c + )1(2
-iH
)(
3
iH = d + )1(3
-iH
)(
4
iH = e + )1(4
-iH
)(
5
iH = f + )1(5
-iH
)(
6
iH = g + )1(6
-iH
)(
7
iH = h + )1(7
-iH
}
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
60
Sau khi lặp 4 bước trên N lần ( sau khi xử lý M(N)), thông điệp rút gọn 256-bit
của thông điệp M là
)(
7
)(
6
)(
5
)(
4
)(
3
)(
2
)(
1
)(
0
NNNNNNNN HHHHHHHH
v SHA-384
SHA-384 được sử dụng để băm thông điệp M dài l bit 12820 <£ l . Thuật toán
sử dụng
a. Một bảng phân bố thông điệp gồm 80 từ 64-bit
b. 8 biến 64 bit.
c. Một giá trị băm gồm 8 từ 64-bit.
Kết quả của SHA-384 là thông điệp rút gọn 384-bit.
Các từ của bảng phân bố thông điệp được ký hiệu W0, W1, ..., W79. 8 biến ký
hiệu a, b, c, d, e, f, g và h. Các từ của giá trị băm ký hiệu )(7
)(
1
)(
0 ,....,,
iii HHH , H(0)
giữ giá trị băm ban đầu, được thay thế bằng các giá trị băm thành công H(i) sau khi
mỗi khối thông điệp được xử lý và kết thúc bằng giá trị băm cuối cùng H(N). SHA-
384 cũng sử dụng hai từ đơn tạm T1, T2.
Với i = 1 đến N
{ Chuẩn bị bảng phân bố thông điệp {Wt}
ïî
ï
í
ì
££+++
££
=
---- 7916)()(
150
1615
}512{
072
}512{
1
)(
tWWWW
tM
W
tttt
i
t
t
ss
Khởi tạo 8 biến a, b, c, d, e, f, g, h với giá trị băm thứ i-1
a = )1(0
-iH
b = )1(1
-iH
c = )1(2
-iH
d = )1(3
-iH
e = )1(4
-iH
f = )1(5
-iH
g = )1(6
-iH
h = )1(7
-iH
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
61
Với t = 0 đến 63:
{
T1 = h + tt WKgfeChe +++å
}512{}512{
1 ),,()(
T2 = ),,()(}512{0 cbaMaja +å
h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1 + T2
}
Tính giá trị băm H(i) của vòng lặp thứ i
)(
0
iH = a + )1(0
-iH
)(
1
iH = b + )1(1
-iH
)(
2
iH = c + )1(2
-iH
)(
3
iH = d + )1(3
-iH
)(
4
iH = e + )1(4
-iH
)(
5
iH = f + )1(5
-iH
)(
6
iH = g + )1(6
-iH
)(
7
iH = h + )1(7
-iH
}
Sau khi lặp 4 bước trên N lần ( sau khi xử lý M(N)), thông điệp rút gọn 384-bit
của thông điệp M là
)(
5
)(
4
)(
3
)(
2
)(
1
)(
0
NNNNNN HHHHHH
v SHA-512
SHA-512 được sử dụng để băm thông điệp M dài l bit 12820 <£ l . Thuật toán
sử dụng
a. Một bảng phân bố thông điệp gồm 80 từ 64-bit
b. 8 biến 64 bit.
c. Một giá trị băm gồm 8 từ 64-bit.
Kết quả của SHA-512 là thông điệp rút gọn 512-bit.
KH
OA
C
NT
T –
Đ
H
KH
TN
Chương 4 Các thuật toán hàm băm và chữ ký điện tử
62
Các từ của bảng phân bố thông điệp được ký hiệu W0, W1, ..., W79. 8 biến ký
hiệu a, b, c, d, e, f, g và h. Các từ của giá trị băm ký hiệu )(7
)(
1
)(
0 ,....,,
iii HHH , H(0)
giữ giá trị băm ban đầu, được thay thế bằng các giá trị băm thành công H(i) sau khi
mỗi khối thông điệp
Các file đính kèm theo tài liệu này:
- Luận văn-Nghiên cứu và xây dựng ứng dụng bảo mật trên PDA.pdf