Giáo trình Cơ sở mật mã (Phần 2)

152 trang ngocly 120

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cơ sở mật mã (Phần 2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_co_so_mat_ma_phan_2.pdf

Nội dung text: Giáo trình Cơ sở mật mã (Phần 2)

Chương 3 - Mật mã khoá công khai CHƯƠNG 3. MẬT MÃ KHOÁ CÔNG KHAI Trước khi tìm hiểu hệ mật khóa công khai chúng ta ôn tập lại một số kiến thức về lý thuyết số. 3.1. SỐ HỌC MODULO 3.1.1. Số nguyên Tập các số nguyên: , 3, 2, 1,0,1,2,3, Z (3.1) Định nghĩa 3.1: Cho a,b Z , a là ước của b nếu c Z : b a.c . Ký hiệu a b Các tính chất chia hết a,b,c Z ta có: (i) a a . (ii) Nếu a b và b c thì a c (iii) Nếu a b và a c thì a bx cy với x,y Z (iv) Nếu a b và b a thì a b Định nghĩa 3.2: Thuật toán chia đối với các số nguyên: Nếu a và b là các số nguyên với b 1 thì a qb r, 0 r b q và r là duy nhất. Phần dư của phép chia PTITa và b được ký hiệu a modb r Thương của phép chia a và b được ký hiệu adivb q a a Ta có adivb , a modb a b b b Ví dụ 3.1: a 73,b 17 73div17 4, 73mod17 5 Định nghĩa 3.3: Ước chung. c là ước chung của a và b nếu c a & c b Định nghĩa 3.4: Ước chung lớn nhất (ƯCLN) Số nguyên dương d là ƯCLN của các số nguyên a và b (Ký hiệud (a,b) ) nếu: 78
Chương 3 - Mật mã khoá công khai (i) d là ước chung của a và b . (ii) Nếu có c a và c b thì c d . Như vậy a ,b là số nguyên dương lớn nhất ước của cả a và b không kể 0,0 0. Ví dụ 3.2: Các ước chung của 12 và 18 là 1, 2, 3, 6 12,18 6 Định nghĩa 3.5: Bội chung nhỏ nhất (BCNN) Số nguyên dương d là bội chung nhỏ nhất (BCNN) của các số nguyên a và b (Ký hiệu d BCNN (a,b)) nếu: (i) a d , b d . (ii) Nếu có a c , b c thì d c . Như vậy d là số nguyên dương nhỏ nhất là bội của cả a và b . Tính chất a .b BCNN a ,b (3.2) a ,b 12.18 Ví dụ 3.3: 12,18 6 BCNN 12,18 36 6 Định nghĩa 3.6: Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau nếu: a ,b 1 Định nghĩa 3.7: Số nguyên p 2 được gọi là số nguyên tố nếu các ước dương của nó chỉ là 1 và p . Ngược lại p được gọi là hợp số. Định lý 3.1: (Định lý cơ bảnPTIT của số học) Với mỗi số nguyên n 2 ta luôn phân tích được dưới dạng tích của luỹ thừa của các số nguyên tố. e1 e 2 ek n p1 p 2 pk (3.3) Trong đó pi là các số nguyên tố khác nhau và ei là các số nguyên dương. Hơn nữa phân tích trên là duy nhất. Định nghĩa 3.8: Với n 2 , hàm n được xác định là số các số nguyên trong khoảng 1,n  nguyên tố cùng nhau với n . Các tính chất của hàm n 79
Chương 3 - Mật mã khoá công khai Nếu p là số nguyên tố thì p p 1. Nếu m ,n 1 thì m .n m . n . e1 e2 ek Nếu n p1 p2 pk là phân tích ra thừa số nguyên tố của n thì: 1 1 1 n n 1 1  1 (3.4) p1 p2 pk Định lý 3.2: Với n 5: n n (3.5) 6ln lnn 3.1.2. Các thuật toán trong Z Cho a và b là các số nguyên không âm và nhỏ hơn hoặc bằng a b b a . Cần chú ý rằng số các bit trong biểu diễn nhị phân của n là lgn  1 và số này xấp xỉ bằng lgn . Số các phép toán bit đối với bốn phép toán cơ bản trên các số là cộng, trừ, nhân và chia sử dụng các thuật toán kinh điển được tóm lược trên bảng sau. Các kỹ thuật tinh tế hơn đối với các phép toán nhân và chia sẽ có độ phức tạp nhỏ hơn. Bảng 3.1. Độ phức tạp bit của các phép toán cơ bản trong Z Phép toán Độ phức tạp bit Cộng a b 0(lga lgb) 0(lgn ) Trừ a b 0(lga lgb) 0(lgn ) Nhân a .b 0 (lga).(lgb) 0 (lgn )2 Chia a qb r 0 (lga).(lgb) 0 (lgn )2 ƯCLN của 2 số nguyênPTIT a và b có thể được tính theo định lý sau: Định lý 3.3: e1 e2 ek 1 2 k Nếu a p1 p2 pk , b p1 p2 pk trong đó ei 0 , i 0 min e1 ,1 min e2 ,2 min ek ,k thì UCLN a ,b p1 p2 pk max e1 ,1 max e2 ,2 max ek ,k và BCNN a ,b p1 p2 pk Ví dụ 3.4: Cho a 4864 28.19 , b 3458 2.7.13.19 . Khi đó UCLN a ,b 4864,3458 2.19 38 BCNN a ,b 4864,3458 28.7.13.19 442624 Định lý 3.4: Nếu a và b là các số nguyên dương với a b thì: 80
Chương 3 - Mật mã khoá công khai UCLN a ,b UCLN b,a modb (3.6) Thuật toán Euclide sau sẽ cho ta cách tính ƯCLN rất hiệu quả mà không cần phải phân tích ra thừa số nguyên tố. Thuật toán Euclide Tính UCLN của 2 số nguyên VÀO : Hai số nguyên không âm a và b với a b RA : ƯCLN của a và b . (1) While b 0 do r  a modb , a b , b  r (2) Return (a). Định lý 3.5: Thuật toán trên có thời gian chạy chừng 0 (lgn )2 các phép toán bit. Ví dụ 3.5: Sau đây là các bước chia của thuật toán trên khi tính: 4864,3458 38 4864 1.3458 1406 3458 2.1406 646. 1406 2.646 76 646 5.114 38 76 2.38 0 Thuật toán trên có thể được mở rộng để không những chỉ tính được ƯCLN của 2 số nguyên a và b mà còn tính được các số nguyên x và y thoả mãn ax by d . Thuật toán Euclide mở rộng VÀO : Hai số nguyên không âm a và b với a b RA : d UCLN a ,bPTIT và các số nguyên x và y thoả mãn ax by d . Nếu b 0 thì đặt d  a , x 1 , y  0và return d,x,y (1) Đặt x 2 1 , x1  0 , y 2  0 , y1 1 (2) While b 0do 2.1 q  a /b ,r a qb,x  x 2 qx1 ,y  y 2 qy1 2.2 a b , b  r , x 2  x1 , x1  x , y 2  y1 , y1  y (3) Đặt d  a , x  x 2 , y  y 2 và return d,x,y Định lý 3.6: 2 Thuật toán trên có thời gian chạy cỡ 0( lgn ) các phép toán bit. 81
Chương 3 - Mật mã khoá công khai Ví dụ 3.6: Bảng 3.2 sau chỉ ra các bước của thuật toán trên với các giá trị vào a 4864và b 3458 Bảng 3.2. Thuật toán Euclide mở rộng với các đầu vào a 4864 và b 3458 y Q r x a b x1 x 2 y 2 y1 4864 3458 1 0 0 1 1 1406 1 1 3458 1406 0 1 1 1 2 646 2 3 1406 646 1 2 1 3 2 114 5 7 646 114 2 5 3 7 5 76 27 38 114 76 5 27 7 38 1 38 32 45 76 38 27 32 38 45 2 0 91 128 38 0 32 91 45 128 Bởi vậy ta có: UCLN 4864,3458 38 và 4864 32 3458 45 38 3.1.3. Các số nguyên modulo n Định nghĩa 3.9: Nếu a và b là các số nguyên thì a được gọi là đồng dư với b theo modulo (ký hiệu là a  b modn ) nếu n a b . Số nguyên n được gọi là modulo đồng dư. Ví dụ 3.7: 24  9mod5 vì 24 9 3.5 11  17 mod7 vì 11 17 4.7 Các tính chất Đối với a,a ,b,b ,c Z ta có: 1 1 PTIT (1) a b modn nếu và chỉ nếu a và b cũng có phần dư khi chia cho n . (2) Tính phản xạ : a  a modn . (3) Tính đối xứng : Nếu a b modn thì b  a modn Tính bắc cầu : Nếu a b modn và b  c modn thì a  c modn (4) Nếu a  a1 modn và b b1 modn thì a b  a1 b1 modn và a.b  a1.b1 modn 82
Chương 3 - Mật mã khoá công khai Lớp tương đương của một số nguyên a là tập các số nguyên đồng dư với a modulo n . Từ các tính chất (2), (3) và (5) ở trên ta có thể thấy rằng đối với n cố định, quan hệ đồng dư theo modulo n sẽ phân hoạch Z thành các lớp tương đương. Nếu a qn r với 0 r n thì a  r modn . Bởi vậy mỗi số nguyên a là đồng dư theo modulo n với một số nguyên duy nhất nằm trong khoảng từ 0 tới n 1, số này được gọi là thặng dư tối thiểu của a modn . Như vậy a và r có thể được dùng để biểu thị cho lớp tương đương này. Định nghĩa 3.10: Các số nguyên modulo n (ký hiêu Zn ) là tập (các lớp tương đương) của các số nguyên 0,1,2,,n 1. Các phép cộng, trừ, nhân trong Zn được thực hiện theo modulo n . Ví dụ 3.8: Z25 0,1,,24. Trong Z25 ta có: 13 16 4 vì 13 16 29  4 mod 25 Tương tự 13.16 8trong Z25 . Định nghĩa 3.11: (Phần tử nghịch đảo) Cho a Z n , phần tử nghịch đảo (ngược theo phép nhân) của a modn là một số nguyên x Z n sao cho: a x 1 modn Nếu x tồn tại thì nó là duy nhất, a được gọi là khả nghịch. Phần tử nghịch đảo của a được ký hiệu là a 1 . Định nghĩa 3.12: Phép chia của với a cho bmodn là tích của a và b 1 modn tích này được xác định nếu b là phần tử khả nghịch. Định lý 3.7: Cho a Z , khi đó a là khả nghịch nếu và chỉ nếu: a,n 1 n PTIT 1 Ví dụ 3.9: Các phần tử khả nghịch trong Z9 là 1, 2, 4, 5, 7 và 8. Chẳng hạn 4 7 vì 4.7 1 mod9 . Định lý 3.8: Cho d a,n , phương trình đồng dư ax b modn có nghiệm x nếu và chỉ nếu d b , trong trường hợp này có đúng d nghiệm nằm giữa 0 và n 1, những nghiệm này là tất cả các đồng dư theo modulo n d . 83
Chương 3 - Mật mã khoá công khai Định lý 3.9: (Phần dư China) Nếu các số nguyên n1,n 2 ,,n k là nguyên tố cùng nhau từng đôi một thì hệ các phương trình đồng dư: x  a1 modn1 x  a modn 2 2 x  ak modn k sẽ có nghiệm duy nhất theo modulo n n n1.n 2 n k Thuật toán Gausse Nghiệm x của hệ phương trình đồng dư trong định lý phần dư China có thể đươc tính bằng: k x aiN iM i modn (3.7) i 1 1 Trong đó N i n / n i và M i N i modn i 2 Các tính toán này có thể được thực hiện trong 0( lgn ) các phép toán trên bit. Ví dụ 3.10: Cặp phương trình đồng dư x  3 mod7 , x  7 mod13 có nghiệm duy nhất x  59 mod91 Định lý 3.10: Nếu n1,n 2 1 thì cặp phương trình đồng dư. x  a modn1 , x  a modn 2 có một nghiệm duy nhất x  a modn ,n PTIT1 2 Định nghĩa 3.13: * Nhóm nhân của Zn là Zn a Z n a,n 1 * Đặc biệt, nếu n là số nguyên tố thì Zn a 1 a n 1 Định nghĩa 3.14: * * * Cấp của Zn là số các phần tử trong Zn (ký hiệu Zn ) Theo định nghĩa của hàm Phi-Euler ta thấy: * Zn n (3.8) 84
Chương 3 - Mật mã khoá công khai * * * * Chú ý: nếu a Zn và b Zn thì a,b Zn và bởi vậy Zn là đóng đối với phép nhân. Định lý 3.11: Cho p là một số nguyên tố: * n (1) Định lý Euler: Nếu a Zn thì a 1 modn . (2) Nếu n là tích của các số nguyên khác nhau và nếu r  s mod (n ) thì a r  as modn đối với mọi số nguyên a . Nói một cách khác khi làm việc với modulo n thì các số mũ có thể được rút gọn theo modulo n . Định lý 3.12: Cho p là một số nguyên tố: (1) Định lý Ferma: Nếu a,p 1 thì a p 1 1 mod p . (2) Nếu r  s mod p 1 thì a r  as mod p đối với mọi số nguyên a . Nói một cách khác khi làm việc với modulo của một số nguyên tố p thì các luỹ thừa có thể được rút gọn theo modulo p 1. (3) Đặc biệt a p  a mod p với mọi số nguyên a . Định nghĩa 3.15: * Cho a Zn . Cấp của a (ký hiệu là ord a ) là số nguyên dương nhỏ nhất t sao cho at  1 modn . Định nghĩa 3.16: * s Cho a Zn , ord(a) t và a 1 modn khi đó t là ước của s . Đặc biệt t n . PTIT* Ví dụ 3.11: Cho n 21, khi đó Z21 1,2,4,5,8,10,11,13,16,17,19,20 * * Chú ý rằng 21 7 . 3 12 Z21 . Cấp của các phần tử trong Z21 được nêu trong bảng sau: * Bảng 3.3. Cấp của các phần tử trong Z21 * 1 2 4 5 8 10 11 13 16 17 19 20 a Z 21 ord a 1 6 3 6 2 6 6 2 3 6 6 2 85
Chương 3 - Mật mã khoá công khai Định nghĩa 3.17: * Cho Zn . Nếu cấp của là n thì được gọi là phần tử sinh hay phần tử * * * nguyên thuỷ của Zn . Nếu Zn có một phần tử sinh thì Zn được gọi là cyclic. * Các tính chất của các phần tử sinh của Zn * k k (1) Zn có phần tử sinh nếu và chỉ nếu n 2,4,p hoặc là 2p , trong đó p là một số * nguyên tố lẻ và k 1. Đặc biệt, nếu p là một số nguyên tố thì Zn có phần tử sinh. * (2) Nếu là một phần tử sinh của Zn thì: * i Zn { modn 0 i  n 1} (3.9) * i (3) Giả sử rằng là một phần tử sinh của Zn khi đó b modn cũng là một phần tử * * sinh của Z n nếu và chỉ nếu i, (n ) 1. Từ đó ta rút ra rằng nếu Zn là cyclic thì số các phần tử sinh là (n ) . * * n /p (4) Zn là một phần tử sinh của Zn nếu và chỉ nếu 1 modn đối với mỗi nguyên tố p của (n ) * Ví dụ 1.12: Z21 không là cyclic vì nó không chứa một phần tử có cấp  21 12 (Chú ý rằng 21 không thoả mãn điều kiện (1) ở trên). * Z25 là cyclic và có một phần tử sinh 2 Định nghĩa 3.18: * Cho a Zn , a được gọi là thặng dư bậc hai modulo n (hay bình phương của modulo * 2 n ) nếu tồn tại x Zn sao cho x  a modn . Nếu không tồn tại x như vậy thìa được gọi là thặng dư không bậc hai modn . Tập tất cả các thặng dư bậc hai modulo n được ký hiệu là Qn , còn tập tất cả các thặng PTITdư không bậc hai được ký hiệu là Qn . Cần chú ý rằng theo định * nghĩa 0 Zn . Bởi vậy 0 Qn và 0 Qn . Định lý 3.13: * * Cho p là một số nguyên tố và là một phần tử sinh của Zp . Khi đó a Zp là một thặng dư bậc hai modulo p nếu và chỉ nếu a i mod p , trong đó i là một số nguyên chẵn. Từ đó rút ra: p 1 p 1 Q và Q (3.10) p 2 p 2 86
Chương 3 - Mật mã khoá công khai * tức là một nửa số phần tử trong Zp là các thặng dư bậc hai và nửa còn lại thặng dư không bậc hai. * Ví dụ 3.12: 6 là một phần tử sinh của Z13 . Các luỹ thừa của được liệt kê ở bảng 3.4. sau đây: Bảng 3.4. i 1 2 3 4 5 6 7 8 9 10 11 12 i mod13 6 10 8 9 2 12 7 3 5 4 11 1 Bởi vậy Q13 {1,3,4,9,10,12} , Q 13 {2,5,6,7,8,11} Định lý 3.14: * Cho n là tích của hai số nguyên tố lẻ khác nhau q và p , n p.q , khi đó a Zn là một thặng dư bậc hai modulo n nếu và chỉ nếu a Qp và a Qq . Điều đó dẫn tới: p 1 q 1 Q Q .Q n q p 4 3 p 1 q 1 và Q n 4 Ví dụ 3.13: Cho n 21. Khi đó : Q21 {1,4,16} Q 21 {2,5,8,10,11,13,17,19,20} Định nghĩa 3.19: * 2 Cho a Qn , nếu x Zn thoả mãn x  a modn thì x được gọi là căn bậc hai của a modn . Định lý 3.15: (Số các căn bậcPTIT hai). Nếu p là một số nguyên tố lẻ và a Qn thì a được gọi là căn bậc hai theo modulo p . e1 e2 ek Tổng quát hơn, cho n p1 p2 pk , trong đó pi là các số nguyên tố lẻ phân biệt và k ei 1. Nếu a Qn thì có đúng 2 căn bậc hai khác nhau theo modulon . Ví dụ 3.14: - Các căn bậc 2 của 12mod37 là 7 và 30. - Các căn bậc 2 của 121mod315 là 11, 74, 101, 151, 164, 214, 241 và 304. 87
Chương 3 - Mật mã khoá công khai 3.1.4. Các thuật toán trong Zn Cho n là một số nguyên dương. Các phần tử của Zn sẽ được biểu thị bởi các số nguyên Q21 0,1,2, ,n 1. Ta thấy rằng, nếu a,b Z n thì a b a b n a b modn (3.11) a b r a b n Bởi vậy phép cộng (và trừ) theo modulo có thể thực hiện được mà không cần phép chia dài. Phép nhân modulo của a và b có thể được thực hiện bằng cách nhân các số nguyên thông thường rồi lấy phần dư của kết quả sau khi chia cho n . Các phần tử nghịch đảo trong Zn có thể được tính bằng cách dùng thuật toán Euclide mở rộng được mô tả dưới đây. 3.1.4.1. Thuật toán (Tính các nghịch đảo trong Zn ) VÀO : a Z n RA : a 1 modn (nếu tồn tại). (1) Dùng thuật toán Euclide mở rộng để tìm các số nguyên x và y sao cho ax ny d trong đó d a,n . (2) Nếu d 1 thì a 1 modn không tồn tại. Ngược lại return x . Phép luỹ thừa theo modulo có thể được thực hiện có hiệu quả bằng thuật toán nhân và bình phương có lặp. Đây là một thuật toán rất quan trọng trong nhiều thủ tục mật mã. Cho biểu diễn nhị phân của k là: t i ki 2 trong đó mỗi ki 0,1 khi đó i PTIT0 t 0 k0 1 k1 t kt a k a ki 2i a 2 a 2  a 2 (3.12) i 0 3.1.4.2. Thuật toán nhân và bình phương có lặp để lấy luỹ thừa trong Zn VÀO : a Zn và số nguyên k, 0 k n có biểu diễn nhị phân: t i k ki 2 i 0 RA : a k modn (1) Đặt b 1. Nếu k 0 thì return b 88
Chương 3 - Mật mã khoá công khai (2) Đặt A a . (3) Nếu k0 1 thì đặt b  a . (4) For i from 1 to t do (4.1). Đặt A  A 2 modn . (4.2). Nếu ki 1 thì đặt b  A.bmodn (5) Return (b) Ví dụ 3.15: Bảng 3.5 sau chỉ ra các bước tính toán 5596 mod1234 1013 Bảng 3.5. Tính 5596 mod1234 i 0 1 2 3 4 5 6 7 8 9 ki 0 0 1 0 1 0 1 0 0 1 A 5 25 625 681 1011 369 421 779 947 925 b 1 1 625 625 67 67 1059 1059 1059 1013 Số các phép toán bit đối với phép toán cơ bản trong Zn được tóm lược trong bảng 3.6 dưới đây. Bảng 3.6. Độ phức tạp bit của các phép toán cơ bản trong Z n Phép toán Độ phức tạp bit Cộng modulo a b 0(lgn ) Trừ modulo a b 0(lgn ) Nhân modulo a .b 0 (lgn )2 Nghịch đảo moduloPTIT a 1 modn 0 (lgn )2 Luỹ thừa modulo a k modn , k n 0 (lgn )3 3.1.5. Các ký hiệu Legendre và Jacobi Ký hiệu Legendre là một công cụ hữu ích để xem xét liệu một số nguyên a có là một thặng dư bậc hai theo modulo của một số nguyên tố p hay không. 89
Chương 3 - Mật mã khoá công khai 3.1.5.1. Ký hiệu Legendre Định nghĩa 3.20: a Cho p là một số nguyên tố lẻ và a là một số nguyên. Ký hiệu Legendre được xác p định như sau: 0 p a a 1 a Qp (3.13) p 1 a Q p 3.1.5.2. Các tính chất của ký hiệu Legendre Cho p là một số nguyên tố lẻ và a,b Z . Khi đó ký hiệu Legendre có các tính chất sau: a p 1 /2 1 1 p 1 /2 (1)  a mod p . Đặc biệt 1 và 1 Bởi vậy p p p 1 Qp nếu p  1 mod 4 và 1 Q p nếu p  3 mod 4 2 a.b a b * a (2)  . . Bởi vậy nếu a Z p thì 1. p p p p a b (3) Nếu a b mod p thì . p p 2 p 2 1 /8 2 2 (4) 1 . Bởi vậy 1 nếu p 1 hoặc 7 mod8 và 1 nếu p p p p  3 hoặc 5 mod8 . (5) Luật thuận nghịch bPTITậc 2: Giả sử p là một số nguyên tố lẻ khác với q , khi đó: p q p 1 q 1 /4 1 q p p q Nói một cách khác trừ phi cả p và q là đồng dư với 3 mod 4 , trong q p p q trường hợp này . q p Dấu hiệu Jacobi là tổng quát hoá của ký hiệu Legendre đối với các số nguyên lẻ n không nhất thiết là một số nguyên tố. 90
Chương 3 - Mật mã khoá công khai 3.1.5.3. Ký hiệu Jacobi Định nghĩa 3.21: e1 e2 ek Cho n 3 là các số nguyên tố có phân tích n p1 .p2 pk . Khi đó ký hiệu Jacobi a được định nghĩa là n e1 e2 ek a a a a  (3.14) n p1 p2 pk Ta thấy rằng nếu n là một số nguyên tố thì ký hiệu Jacobi chính là ký hiệu Legendre. 3.1.5.4. Các tính chất của ký hiệu Jacobi Cho n 3 là các số nguyên tố a,b Z . Khi đó ký hiệu Jacobi có các tính chất sau: a a (1) 0,1 hoặc 1. Hơn nữa 0 nếu và chỉ nếu UCLN a,n 1. n n 2 a.b a b * a (2)  . . Bởi vậy a Z n thì 1 n n n n a a a (3)  . . m .n m n a b (4) Nếu a b modn thì . n n 1 (5) 1 n 1 n 1 /2 1 (6) 1 . Bởi vậy: 1 nếu n  1 mod 4 n n 1 PTIT 1 nếu n  3 mod 4 n 2 n 2 1 /8 2 (7) 1 . Bởi vậy: 1 nếu n  1hoặc 7 mod8 n n 2 1 nếu n  3hoặc 5 mod8 n m n m 1 n 1 /4 (8) 1 n m 91
Chương 3 - Mật mã khoá công khai m n Nói một cách khác trừ phi cả hai số m và n đều đồng dư với 3 mod 4 , n m m n trong trường hợp này . n m e Từ các tính chất của ký hiệu Jacobi ta thấy rằng n lẻ và a 2 a1 trong đó a1 là một số lẻ thì: e e a 2 a1 2 n moda1 a1 1 n 1 /4 1 n n n n a1 a Từ công thức này ta có thể xây dựng thuật toán đệ quy sau để tính mà không cần n phải phân tích n ra các thừa số nguyên tố . 3.1.5.5. Thuật toán tính toán ký hiệu Jacobi (và ký hiệu Legendre) JACOBI a,n VÀO : Số nguyên lẻ n 3 số nguyên a, 0 a n a RA : Ký hiệu Jacobi (Sẽ là ký hiệu Legendre khi n là số nguyên tố) n (1) Nếu a 0 thì return 0 (2) Nếu a 1 thì return 1 e (3) Viết a 2 a1 , trong đó a1 là một số lẻ (4) Nếu e chẵn thì đặt s 1. Ngược lại hãy đặt s 1 nếu n 1 hoặc 7 mod8 (5) Nếu n  3 mod 4 và a  3 mod 4 thì đặt s  s PTIT1 (6) Đặt r1  n moda1 (7) Return s.JA COBI n1,a1 2 Thuật toán trên có thời gian chạy chừng 0( lgn ) các phép toán bit. 3.1.5.6. Nhận xét (tìm các thặng dư bậc hai theo modulo của số nguyên tố p) * Cho p là một số nguyên tố lẻ. Mặc dù đã biết rằng một nửa các phần tử trong Zp là các thặng dư không bậc hai theo modulo p nhưng không có một thuật toán xác định theo thời gian đa thức nào được biết để tìm. 92
Chương 3 - Mật mã khoá công khai Một thuật toán ngẫu nhiên tìm một thặng dư không bậc hai là chọn ngẫu nhiên các số * a nguyên a Zp cho tới khi số đó thoả mãn 1. Phép lặp đối với số được chọn trước p khi tìm được một thặng dư bậc hai là 2 và bởi vậy thuật toán được thực hiện theo thời gian đa thức. 3.1.5.7. Ví dụ tính toán ký hiệu Jacobi 158 Cho a 158 và n 235 . Thuật toán trên tính như sau: 235 158 2 79 235 78.234/4 77 1 1 235 235 235 79 79 77 76.78/4 2 1 1 79 77 a Khác với ký hiệu Legendre, ký hiệu Jacobi không cho biết liệu a có phải là một n a thặng dư bậc 2 theo modulo n hay không. Sự thực là nếu a Qn thì 1 Tuy nhiên n a 1 thì không có nghĩa là a Qn . n 3.1.5.8. Ví dụ (Các thặng dư bậc 2 và không bậc 2) * Bảng 3.7. Các ký hiệu Jacobi của các phần tử trong Z21 * 1 2 4 5 8 10 11 13 16 17 19 20 a Z21 a 2 modn 1 4 16 4 1 16 16 1 4 16 4 1 a 1 1 1 1 1 1 1 1 1 1 1 1 3 PTIT a 1 1 1 1 1 1 1 1 1 1 1 1 7 a 1 1 1 1 1 1 1 1 1 1 1 1 21 * Bảng 1.6 liệt kê các phần tử trong Z21 và các ký hiệu Jacobi của chúng. Từ ví dụ trong 5 phần c ta có Q21 {1,4,16}. Ta thấy rằng 1 nhưng 5 Q21 . 21 93
Chương 3 - Mật mã khoá công khai Định nghĩa 3.22: * a  Cho n 3 là các số nguyên tố lẻ và cho J n a Z n 1 tập các thặng dư giả n  ˆ bậc 3 theo modulo n (Ký hiệu Qn ) được định nghĩa là tập J n Qn . Định lý 3.16: Cho n p.q là tích của hai số nguyên tố lẻ khác nhau. Khi đó:  Qn Qn p 1 q 1 / 4 (3.15) tức là một nửa các phần tử trong J n là các thặng dư giả bậc hai. 3.1.6. Các số nguyên Blum Định nghĩa 3.23: Số nguyên Blum là một hợp số có dạng n p.q , trong đó p và q là các số nguyên tố khác nhau và thoả mãn: p  3mod 4 (3.16) q  3mod 4 Định lý 3.17: Cho n p.q là một số nguyên Blum và cho a Qn . Khi đó a có đúng 4 căn bậc hai modulon và chỉ có một số nằm trong Qn . Định nghĩa 3.24: Cho n là một số nguyên Blum và cho a Qn . Căn bậc hai duy nhất của a nằm trong Qn được gọi là căn bậc hai chính a modn . 3.1.7. Ví dụ (Số nguyên Blum) Đối với số nguyên Blum n 21. Ta có J {1,4,5,16,17,20} và Q {5,17,20}. PTITn n Bốn căn bậc 2 của a 4 là 2, 5, 16 và 19, trong đó chỉ có 16 là cũng nằmg trong Qn . Bởi vậy 16 là căn bậc 2 chính của 4mod 21. Định lý 3.18: Nếu n p.q là một số nguyên Blum thì ánh xạ. 2  :Qn Qn được xác định bởi  x x modn là một phép hoán vị. 1 p 1 q 1 4/8 Ánh xạ ngược của  là:  x x modn . 94
Chương 3 - Mật mã khoá công khai 3.2. GIỚI THIỆU VỀ MẬT MÃ KHOÁ CÔNG KHAI Trong mô hình mật mã cổ điển trước đây mà hiện nay đang được nghiên cứu Alice (người gửi) và Bob (người nhận) chọn một cách bí mật khoá K. Sau đó dùng K để tạo luật mã hoá ek và luật giải mã dk . Trong hệ mật này dk hoặc giống ek hoặc dễ dàng nhận được từ nó (ví dụ trong hệ DES quá trình giải mã hoàn toàn tương tự như quá trình mã nhưng thủ tục khoá ngược lại). Các hệ mật thuộc loại này được gọi là hệ khoá bí mật, nếu để lộ ek thì làm cho hệ thống mất an toàn. Nhược điểm của hệ mật này là nó yêu cầu phải có thông tin trước về khoá K giữa Alice và Bob qua một kênh an toàn trước khi gửi một bản mã bất kỳ. Trên thực tế điều này rất khó đảm bảo. Chẳng hạn khi Alice và Bob ở cách xa nhau và họ chỉ có thể liên lạc với nhau bằng thư tín điện tử (E.mail). Trong tình huống đó Alice và Bob không thể tạo một kênh bảo mật với giá phải chăng. Ý tưởng xây dựng một hệ mật khoá công khai (hay dùng chung) là tìm một hệ mật không có khả năng tính toán để xác định dk khi biết ek . Nếu thực hiện được như vậy thì quy tắc mã ek có thể được công khai bằng cách công bố nó trong một danh bạ (bởi vậy nên có thuật ngữ hệ mật khoá công khai). Ưu điểm của hệ mật khoá công khai là ở chỗ Alice (hoặc bất kỳ ai) có thể gửi một bản tin đã mã cho Bob (mà không cần thông tin trước về khoá mật) bằng cách dùng mật mã công khai ek . Người nhận A sẽ là người duy nhất có thể giải được bản mã này bằng sử dụng luật giải bí mật dk của mình. Có thể hình dung hệ mật này tương tự như sau. Alice đặt một vật vào một hộp kim loại và rồi khoá nó lại bằng một khoá số do Bob để lại. Chỉ có Bob là người duy nhất có thể mở được hộp vì chỉ có anh ta mới biết tổ hợp mã của khoá số của mình. Ý tưởng về một hệ mật khoá công khai được Diffie và Hellman đưa ra vào năm 1976. Còn việc hiện thực hoá nó thì do Rivesrt, Shamir và Adleman đưa ra lần đầu tiên vào năm 1977, họ đã tạo nên hệ mật nổi tiếng RSA (sẽ được nghiên cứu trong chương này). Một chú ý quan trọng là một hệ mật khoá công khai không bao giờ có thể đảm bảo được độ mật tuyệt đối (an toàn vô điều kiện). Sở dĩ như vậy vì đối phương khi nghiên cứu một bản mã, anh ta có thể mã lần lượtPTIT các bản tin rõ bằng luật mã hoá công khai ek cho tới khi anh ta tìm được bản rõ duy nhất M đảm bảo C ek M . Bản rõ này chính là kết quả giải mã. Bởi vậy, ta chỉ nghiên cứu độ mật về mặt tính toán của các hệ mật này. Một khái niệm có ích khi nghiên cứu hệ mật khoá công khai là khái niệm về hàm cửa sập một chiều. Ta sẽ định nghĩa khái niệm này một cách không hình thức. Hàm mã khoá công khai ek của Bob phải là một hàm dễ tính toán. Song việc tìm hàm ngược (hàm giải mã) rất khó khăn (đối với bất kỳ ai không phải là Bob). Đặc tính dễ tính toán hàm ngược thường được gọi là đặc tính một chiều. Bởi vậy điều kiện cần thiết là ek phải là hàm một chiều (tính thuận đơn giản, nhưng tính ngược rất phức tạp). Các hàm một chiều đóng vai trò quan trọng trong mật mã học, chúng rất quan trọng trong các hệ mật khoá công khai và trong nhiều lĩnh vực khác. Đáng tiếc là mặc dù có rất 95
Chương 3 - Mật mã khoá công khai nhiều hàm được coi là hàm một chiều nhưng cho đến nay vẫn không tồn tại một hàm nào có thể chứng minh được là hàm một chiều. Sau đây là một ví dụ về một hàm được coi là hàm một chiều. Giả sử n là tích của hai số nguyên tố lớn p và q , giả sử b là một số nguyên dương. Khi đó ta xác định ánh xạ b f : Zn Zn là f (x ) x modn (với b và n đã được chọn thích hợp thì đây chính là hàm mã RSA, sau này ta sẽ nói nhiều hơn về nó). Để xây dựng một hệ mật khoá công khai thì việc tìm được một hàm một chiều vẫn chưa đủ. Ta không muốn ek là hàm một chiều đối với Bob vì anh ta phải có khả năng giải mã các bản tin nhận được một cách hiệu quả. Điều cần thiết là Bob phải có một cửa sập chứa thông tin bí mật cho phép dễ dàng tìm hàm của ek . Như vậy Bob có thể giải mã một cách hữu hiệu vì anh ta có một hiểu biết tuyệt mật nào đó về K. Bởi vậy một hàm được gọi là cửa sập một chiều nếu nó là một hàm một chiều và nó trở nên dễ tính ngược nếu biết một cửa sập nhất định. 3.3. SƠ ĐỒ CHỨC NĂNG CỦA HỆ MẬT KHÓA CÔNG KHAI Thám mã (Oscar) A (Alice) Encryption Decryption B (Bob) M C C M Nguồn tin Mã hóa Kênh mở Giải mã Nhận tin K K C B RB Hình 3.1. Sơ đồ chức năng hệ mật khóa công khai Sơ đồ truyền tin bí mật từ A đến B sử dụng mật mã khóa công khai được mô ta trong Hình 3.1, trong đó: + M : bản tin rõ + C : Bản mã + K là khóa công khai của B (khóa mã hóa) được lấy trên kênh mở. C B PTIT + K là khóa bí mật của B (Khóa giải mã). RB Hàm mã hóa là một ánh xạ 1:1: C E M ,K (3.17) C B Và hàm giải mã: M E 1 C ,K (3.18) RB Theo sơ đồ của hệ mật khóa công khai ta thấy các ưu điểm là: - Không cần hai khóa bí mật. - Không cần kênh an toàn riêng 96
Chương 3 - Mật mã khoá công khai - Biết khóa mã hóa trên kênh mở nhưng rất khó giải mã, tức là biết K nhưng rất C B khó suy ra được K (độ khó ở đây chính là độ phức tạp tính toán hoặc tài RB nguyên và thời gian tính toán) Các nghiên cứu trên thế giới từ năm 1976 cho đến nay đã đưa ra được 5 bài toán một chiều như sau: - Bài toán logarit rời rạc - Bài toán phân tích thừa số (gắn với hệ mật nổi tiếng RSA) - Bài toán xếp ba lô - Bài toán mã sửa sai - Bài toán xây dựng hệ mật trên đường cong elliptic. Trong phần tiếp theo dưới sẽ lần lượt tìm hiểu từng bài toán một chiều và ứng dụng trong các hệ mật liên quan. 3.4. BÀI TOÁN LOGARIT RỜI RẠC VÀ CÁC HỆ MẬT LIÊN QUAN 3.4.1. Bài toán logarit rời rạc 3.4.1.1. Bài toán logarit trên trường số thực R + Bài toán thuận: Hàm số y a x với a,x R , việc tính toán hàm mũ này có thể được thực hiện dễ dàng bằng thuật toán nhân và bình phương. + Bài toán ngược: như ta đã biết phép tính ngược của hàm mũ chính là hàm logarit y loga x , việc tính toán hàm ngược logarit này sẽ khó khăn hơn nhiều so với hàm thuận. Tuy nhiên, cả hai phép hãm mũ và logarit đều là các hàm đồng biến cho nên có thể xác định giá trị tương đối của hàm logarit được (như Hình 3.2). y y a x y x y log x PTIT1 a 0 1 x x Hình 3.2. Đồ thị hàm y a và y loga x Một số tính chất của hàm logarit. + y loga bc loga b loga c b + y log log b log c a c a a + loga 1 0 97
Chương 3 - Mật mã khoá công khai 1 + y loga x loga x 3.4.1.2. Bài toán logarit trên trường hữu hạn Xét vành Zp với p là số nguyên tố. Theo định lý 2.7 nếu p là nguyên tố thì ¢ p là một trường ( ¢ p GF(2) ). * Tập tất cả các phần tử khác không của trường sẽ tạo nên một nhóm nhân xyclic ¢ p . * ¢ p ¢ p 0 1,2, ,p 1 x * + Bài toán thuận: y a mod p, a,x ¢ p Ví dụ 3.16: Xét p 19,a 2 ta có các giá trị y a x như trong Bảng 3.8 x * Bảng 3.8. Các giá trị của y 2 mod19 trên ¢ 19 x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2x 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 Chú ý: + Nếu a là một phần tử nguyên thủy thì a x sẽ đi qua tất cả các phần tử của nhóm. + Nếu a là phần tử nguyên thủy thì ai cũng là nguyên thủy với i,p 1 1 ( p là số nguyên tố). Trong ví dụ 3.16 các giá trị của i thỏa mãn i,18 1 là i 1,5,7,11,13,17 . Số lượng các giá trị của i bằng giá trị hàm p 1 . N i p 1 18 6 Cách tính hàm Phi-Euler như trình bày tại mục 1.1.12. Như vậy trong nhóm ¢PTIT* có 6 phần tử nguyên thủy: 19 2 21; 13 25; 14 27 ; 15 211; 3 213; 10 217 (3.19) Các phần tử nguyên thủy này tạo thành các cặp nghịch đảo như sau: 2,10  2 10 1 13,3  13 3 1 14,15  14 15 1 * + Bài toán ngược: y loga x, a,x ¢ p Từ bảng 3.8 ta tính được hàm ngược log2 x như trong bàng 3.9. 98
Chương 3 - Mật mã khoá công khai * Bảng 3.9. Giá trị log2 x mod19 trên ¢ 19 x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2x 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 18 1 13 2 16 14 6 3 8 17 12 15 5 7 11 4 10 9 log2 x 18 Chú ý: vì 2 1 nên log2 1 18 . Một số tính chất của hàm logarit rời rạc. + y loga bc loga b loga c mod p 1 b + y log log b log c mod p 1 a c a a + log x log x p 1 log x a 1 a a + loga 1 0 p 1 (coi 0 p 1) Nhận xét: Từ hai Bảng 3.8 và Bảng 3.9 ta thấy hai hàm thuận và ngược đều không phải hảm đồng biến, khi biết bài toán thuận thì mời tim được bài toán ngược. Do đó việc giải bài toán ngược giống bài toán vét cạn, phải thử lần lượt các trường hợp. Việc xác định logarit của một phần tử bất kỳ trong trường là bài toán khó giải. + Bài toán logarit rời rạc * * Cho ¢ p với p là số nguyên tố, là một phần tử nguyên thủy ¢ p . * Yêu cầu tìm y log x với ,x ¢ p . * Nhận xét: x ¢ p thì: - Bài toán có nghiệm khi là phần tử nguyên thủy. - Bài toán có thể khôngPTIT có nghiệm khi bất kỳ. Ví dụ 3.17: Với trường hợp p 19 ta đa tính được 6 phần tử nguyên thủy như trong (3.19) ta sẽ đi tính bài toan logarit rời rạc với cơ số là 6 phần tử nguyên thủy này. Tuy nhiên ta có thể áp dụng tính chất của hàm logarit rời rạc: log x log x p 1 log x , hay log 1 x log x p 1 a 1 a a a a để tính logarit với cơ số là các cặp số nghịch đảo. Tức là 2,10 là cặp số nghịch đảo, khi đó log10 x p 1 log2 x 18 log2 x .Tương tự 13,3 và 14,15 là các cặp nghịch đảo nên log3 x 18 log13 x và log15 x 18 log14 x . Với quy tắc như thế có thể tính được các giá trị logarit như trong Bảng 3.10. 99
Chương 3 - Mật mã khoá công khai * Bảng 3.10. Bài toán logarit rời rạc trên ¢ 19 x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2x 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 18 1 13 2 16 14 6 3 8 17 12 15 5 7 11 4 10 9 log2 x 18 17 5 16 2 4 12 15 10 1 6 3 13 11 7 14 8 9 log10 x 13x 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 1 18 11 17 4 14 10 12 15 16 7 6 3 1 5 13 8 2 9 log13 x 18 7 1 14 4 8 6 3 2 11 12 15 17 13 5 10 16 9 log3 x 14x 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 1 18 13 7 8 10 2 6 3 14 5 12 15 11 1 17 16 4 9 log14 x 18 5 11 10 8 16 12 15 4 13 6 3 7 17 1 2 14 9 log15 x Có thể tính 13x thông qua 2x , ta thấy rằng 13 25 do đó 13x 25x , tương tự như thế 14x 27x . 3.4.2. Một số hệ mật xây dựng trên bài toán logarit rời rạc 3.4.2.1. Trao đổi và thỏa thuận khóa Diffie-Hellman Giả sử A và B muốn liên lạc sử dụng hệ mật khoá bí mật. Để thoả thuận một khoá K chung cho cả hai bên qua một kênh không an toàn mà không ai khác có thể biết được, A và B có thể dùng thủ tục thoả thuận khoá Diffie -Hellman sau: * Chọn trước một số nguyên tố p thích hợp và một phần tử nguyên thủy ¢ p . Cặp số p, tạo thành khóa công khai. Quá trình trao đổi khóaPTIT được thực hiện như sau: A B + A chọn một số nguyên x bí mật thỏa + B chọn một số nguyên y bí mật thỏa mãn 1 x p 1 và tính: mãn 1 y p 1 và tính: x Gửi cho B Gửi cho A mod p y mod p Sau đó A gửi giá trị này cho B. Sau đó B gửi giá trị này cho A. + A nhận y mod p và tính ra khóa dùng + B nhận x mod p và tính ra khóa dùng chung: chung: 100
Chương 3 - Mật mã khoá công khai K (a y )x mod p xy mod p K (a x )y mod p xy mod p Ví dụ 3.18: Giả sử A và B chọn p 19 và 2 A B + A chọn một số nguyên x 3 và tính: + B chọn một số nguyên y 5và tính: 23 mod19 8 , sau đó A gửi 8 cho B 25 mod19 13, B gửi giá trị 13 cho A. + A nhận 13 và tính ra khóa dùng chung: + B nhận 8 và tính ra khóa dùng chung: K 133 mod19 12 K 85 mod19 12 Nhận xét: + Thám mã biết ,p nhưng không biết x,y , nếu muốn biết khóa dùng chung K xy mod p thì thám mã phải giải bài toán logarit (bài toán ngược) để tìm x và y . + Tuy nhiên việc thỏa thuận theo phương thức này sẽ chịu phép tấn công "kẻ đứng giữa" (Man in the midle). Thám mã đứng giữa sẽ giả mạo B để thỏa thuận khóa K1 dùng chung với A, đồng thời thám mã giả danh A để thỏa thuận khóa K2 dùng chung với B. Thám mã liên lạc với A bằng khóa K1, giải mã để lấy cắp thông tin của A, sau đó lại mã hóa thông tin của A bằng khóa K2 để liên lạc với B (và tương tự như thế theo chiều từ B đến A). Hai bên A và B vẫn nhận đúng thông tin tưởng là liên lạc đúng với nhau, nhưng thực tế là liên lạc với thám mã. Đây là điểm yếu của phương pháp thỏa thuận khóa kiểu này, để khắc phục người ta sử dụng các phương pháp xác thực (sẽ được trình bày sau). Thám mã K1 K2 A B' A' B Hình 3.3. Phép tấn công kẻ đứng giữa 3.4.2.2. Hệ mật Omura-Massey a) Sơ đồ hệ mật Omura – MasseyPTIT Ý tưởng của hệ mật Omura – Massey được mô tả trong Hình 3.4. Hai bên liên lạc A và B sử dụng hai khóa bí mật khác nhau là K A và K B , đầu tiên bản tin M được A mã hóa bằng khóa bí mật của A là K A và gửi bản mã cho B, tất nhiên trên đường truyền thám mã không thể có được bản tin M vì không có khóa K A . Bên B nhận được bản mã lại thực hiện mã hóa một lần nữa bằng khóa K B và gửi lại bản mã mới cho A. Khi A nhận lại bản mã thì tiến hành giải mã bằng khóa K A , lúc này bản tin M chỉ được mã hóa bằng khóa K B . A gửi bản mã này cho B, bên B nhận được và tiến hành giải mã bằng khóa K B để lấy lại bản tin M. 101
Chương 3 - Mật mã khoá công khai Hình 3.4. Lưu đồ hệ mật Omura - Massey Hệ mật này về cơ bản rất an toàn, tuy nhiên nó có một nhược điểm là bản mã truyền giữa A và B phải được thực hiện 3 lần, tức là tốc độ mã thấp hay dung lượng thông tin cần truyền sẽ tăng lên. b) Hệ mật Omura – Massey xây dựng trên bài toán logarit rời rạc Hai bên liên lạc A và B chọn trước ¢ p , với p là số nguyên tố. Tạo khóa: Hai bên liên lạc A và B tạo cho mình khóa bí mật như sau: A chọn m ,n ngẫu nhiên thỏa mãn mn  1mod p 1. Khóa bí mật của A là m ,n B chọn u,v ngẫu nhiên thỏa mãn uv 1mod p 1 Khóa bí mật của B là u,v Giả sử A cần gửi một bản tin M cho B, quá trình truyền tin bảo mật sử dụng hệ mật Omura – Massey được mô tả như Hình 3.5: A B m ,n PTIT u ,v + A tính M m mod p và gửi cho B + B nhận M n mod p và tính u M m mod p B gửi giá trị này cho A m u + A nhận M mod p và tính: (M mu )n mod p M u mod p và gửi cho B + B nhận M u mod p và giải mã ra v bản tin M: M u mod p M Hình 3.5. Mô tả hệ mật Omura – Massey sử dụng bài toán logarit rời rạc. 102
Chương 4 - Hàm băm, xác thực và chữ ký số CHƯƠNG 4. HÀM BĂM, XÁC THỰC VÀ CHỮ KÝ SỐ 4.1. CÁC HÀM BĂM VÀ TÍNH TOÀN VẸN CỦA DỮ LIỆU 4.1.1. Khái niệm về hàm băm Các hàm băm đóng vai trò cơ bản trong mật mã hiện đại. Hàm băm sẽ tạo ra một đầu ra có độ dài cố định từ bản tin đầu vào. Đầu ra này được định nghĩa là mã băm (kết quả băm, giá trị băm). Nói một cách chính xác hơn, hàm băm h sẽ tạo ra ánh xạ các xâu bit có độ dài hữu hạn tuỳ ý thành các xâu bit có độ dài n cố định. n Xét xâu bit x Z 2 và một ánh xạ: m h :x y Z 2 (4.1) Trong đó: n m nhận giá trị bất kỳ, còn m const Hàm y h(x ) được gọi là hàm băm (hay mã băm, tóm lược thông báo) Hàm băm h là một ánh xạ đầu ra có độ dài m cố định h :D R và D R điều này có nghĩa là không thể tránh khỏi các va chạm (tức là cùng một giá trị đầu ra có thể có nhiều bộ giá trị vào khác nhau). Nếu hàm h là ngẫu nhiên theo nghĩa tất cả các đầu ra là đồng xác suất thì có chừng 2n m các đầu vào ánh xạ tới mỗi đầu ra (n : số bit đầu vào, m : số bit đầu ra, n m ) và 2 đầu vào được chọn ngẫu nhiên sẽ có cùng đầu ra với xác suất 2 m (không phụ thuộc vào n ). Ý tưởng cơ bản của việc sử dụng các hàm băm trong mật mã là sử dụng chúng như một ảnh biểu diễn rút gọn (đôi khi còn được gọi là vết, dấu tay số hay tóm lược thông báo) của một xâu vào và có thể được dùng như thể nó chính là xâu vào đó. Các hàm băm được dùng cho các sơ đồ chữ ký số kết hợp với việc đảm bảo tính toàn vẹn của dữ liệu, khi đó bản tin trước hết được băm và rồi giá trị băm (được xem như đại diện cho bản tin) sẽ được ký thay choPTIT vị trí bản tin gốc. Một lớp các hàm băm được gọi là các mã xác thực thông báo (MAC - Message Authentication Codes) sẽ cho phép xác thực thông báo bằng kỹ thuật đối xứng (mật mã cổ điển). Các thuật toán MAC sử dụng 2 đầu vào (bao gồm bản tin và một khoá bí mật) để tạo ra một đầu ra có kích cỡ cố định (n bit) với ý đồ đảm bảo rằng nếu không biết khoá thì việc tạo ra cùng một đầu ra là không khả thi. MAC có thể được dùng để đảm bảo tính toàn vẹn của dữ liệu, xác thực tính nguyên bản của số liệu cũng như định danh trong sơ đồ mật mã cổ điển. Một ứng dụng điển hình của hàm băm (không dùng khoá) để đảm bảo tính toàn vẹn của dữ liệu có thể được mô tả như sau: Giá trị băm tương ứng với một bản tin riêng x sẽ được tính ở thời điểm T1 . Tính toàn vẹn của giá trị băm này (chứ không phải là bản thân bản tin) sẽ được bảo vệ theo một cách 139
Chương 4 - Hàm băm, xác thực và chữ ký số nào đó. Ở thời điểm tiếp theo sau T 2 phép kiểm tra sau sẽ được tiến hành để xác định xem liệu thông báo có bị sửa đổi hay không, tức là xem liệu bản tin x có giống bản tin gốc hay không. Giá trị băm của x sẽ được tính toán và so sánh với giá trị băm đã được bảo vệ, nếu chúng bằng nhau thì bên thu sẽ chấp nhận rằng x và x là như nhau và như vậy có nghĩa là bản tin đã không bị sửa đổi. Như vậy vấn đề đảm bảo tính vẹn toàn của một bản tin lớn sẽ được gui về đảm bảo cho một giá trị băm có kích cỡ cố định (và nhỏ). Ứng dụng trên thường được gọi là mã phát hiện sự sửa đổi (MDC - Manipulation Detection Codes). 4.1.2. Các định nghĩa, tính chất cơ bản và phân loại hàm băm 4.1.2.1. Định nghĩa hàm băm Định nghĩa 4.1: Hàm băm là một ánh xạ h(x ) thỏa mãn hai tính chất: a) Tính chất nén: h sẽ ánh xạ một đầu vào x có độ dài bit hữu hạn tuỳ ý tới một đầu ra h(x ) có độ dài bit m hữu hạn. b) Tính chất dễ dàng tính toán: Với h cho trước và một đầu vào x , có thể dễ dàng tính được h(x ) . 4.1.2.2. Một số tính chất của các hàm băm không có khoá Giả sử h là một hàm băm không có khoá, x và x là các đầu vào và y và y là các đầu ra tương ứng. Ngoài hai tính chất cơ bản trên hàm băm mật mã còn có 3 tính chất sau: a) Tính khó tính toán nghịch ảnh: Đối với hầu hết các đầu ra được xác định trước, không có khả năng tính toán để tìm một đầu vào bất kỳ mà khi băm sẽ cho ra đầu ra tương ứng (Tức là tìm một nghịch ảnh x sao cho h(x ) y với y cho trước và không biến đầu vào tương ứng). b) Khó tìm nghịch ảnh thứ hai: Không có khả năng tính toán để tìm một đầu vào đã cho trước: Tức là với x cho trước phải tìm x x sao cho h(x )PTIT h(x ) c) Tính khó va chạm. Không có khả năng về tính toán để tìm hai đầu vào khác nhau bất kỳ x x để h(x ) h(x ) . 4.1.2.3. Định nghĩa hàm băm một chiều (OWHF - oneway hash function) Định nghĩa 4.2: Định nghĩa hàm băm một chiều (OWHF - oneway hash function) là một hàm băm (ngoài hai tính chất cơ bản) có tính chất bổ sung là: - Khó tìm nghịch ảnh - Khó tìm nghịch ảnh thứ hai. 4.1.2.4. Định nghĩa hàm băm khó va chạm (CRHF: Collision resistant HF) Định nghĩa 4.3: Định nghĩa hàm băm khó va chạm (CRHF: Collision resistant HF) là một hàm băm (ngoài hai tính chất cơ bản) có tính chất bổ sung là: 140
Chương 4 - Hàm băm, xác thực và chữ ký số - Khó tìm nghịch ảnh thứ hai - Khó và chạm 4.1.2.5. Chú ý về các thuật ngữ Khó tìm nghịch ảnh  Một chiều Khó tìm nghịch ảnh thứ hai  Khó va chạm yếu. Khó va chạm  Khó va chạm mạnh OWHF  Hàm băm một chiều yếu. CRHF  Hàm băm một chiều mạnh. Ví dụ: r bit kiểm tra của một mã xyclic (n,k) với k r có thể coi là một hàm băm thoả mãn hai tính chất cơ bản (dễ tính toán và nén). Tuy nhiên nó không thoả mãn tính chất khó tìm nghịch ảnh thứ hai. 4.1.2.6. Phân loại các hàm băm mật mã và ứng dụng Hàm băm Hàm băm không có khóa Hàm băm có khóa Các ứng Các ứng MDC MAC dụng khác dụng khác OWHF CRHF Hình 4.1. Phân loại hàm băm MDC: Manipullation Detection Code – Mã phát hiện sửa đổi MAC: Message Authentication Code – Mã xác thực thông báo. 4.1.3. Các hàm băm không có khóa (MDC) Các hàm băm không khóaPTIT dựa trên mật mã khối Định nghĩa 4.4: Mật mã khối n,r là một mã khối xác định một hàm khả nghịch từ các bản rõ n bit sang các bản mã n bit bằng cách sử dụng một khoá r bit. Nếu E là một phép mã hoá như vậy thì E k (x) ký hiệu cho phép mã hoá x bằng khoá k . Định nghĩa 4.5: Cho h là một hàm băm có lặp h được xây dựng từ một mật mã khối với hàm nén  thực hiện s phép mã hoá khối để xử lý từng khối bản tin n bit. Khi đó tốc độ của là 1 s . 141
Chương 4 - Hàm băm, xác thực và chữ ký số 4.1.3.1. MDC độ dài đơn Ba sơ đồ trong Hình 4.2 dưới đây có liên quan chặt chẽ với các hàm băm độ dài đơn, xây dựng trên các mật mã khối. Các sơ đồ này có sử dụng các thành phần được xác định trước như sau: Một mật mã khối n bit khởi sinh E k được tham số hoá bằng một khoá đối xứng k . Một hàm g ánh xạ n bit vào thành khoá k sử dụng cho E (Nếu các khoá cho E cũng có độ dài n thì g có thể là hàm đồng nhất). Một giá trị ban đầu cố định IV (Init Vector) thích hợp để dùng với E. Hình 4.2. Một số phương pháp xây dựng hàm băm đơn Thuật toán băm Matyas - Mayer – Oseas (M-M-O) VÀO: Xâu bit x RA : Mã băm n bit của x Đầu vào x được phân chia thành các khối n bit và được độn nếu cần thiết nhằm tạo khối cuối cùng hoàn chỉnh. Ta được t khối n bit: x (x1,x 2 , ,xt ) . Phải xác định trước một giá trị ban đầu n bit (ký hiệu IV). Đầu ra là H t được xác định như sau: H 0 IV H i E g H 1 xi  xi , 1 i t PTIT i Thuật toán băm Davies - Mayer (D-M) VÀO: Xâu bit x RA : Mã băm n bit của x Đầu vào x được phân thành các khối k bit (k là kích thước khoá) và được độn nếu cần thiết để tạo khối cuối cùng hoàn chỉnh. Biểu thị thông báo đã độn thành t khối k bit: x (x1,x 2 , ,xt ) . Xác định trước một giá trị ban đầu n bit (ký hiệu IV). Đầu ra là H t được xác định như sau: H 0 IV H E H  H , 1 i t i xi i i 1 142
Chương 4 - Hàm băm, xác thực và chữ ký số Thuật toán băm Miyaguchi - Preneel Sơ đồ này tương tự như M-M-O ngoại trừ H i 1 (đầu ra ở giai đoạn trước) được cộng modulo 2 với tín hiệu ra ở giai đoạn hiện thời. Như vậy: H 0 IV H i E xi  xi H i 1, 1 i t g Hi 1 Nhận xét: Sơ đồ D-M có thể coi là sơ đồ đối ngẫu với sơ đồ M - M - O theo nghĩa xi và H i 1 đổi lẫn vai trò. 4.1.3.2. MDC độ dài kép: MDC-2 và MDC- 4 MDC-2 và MDC- 4 là các mã phát hiện sự sửa đổi yêu cầu tương ứng là 2 và 4 phép toán mã hoá khối trên mỗi khối đầu vào hàm băm. Chúng sử dụng 2 hoặc 4 phép lặp của sơ đồ M - M - O để tạo ra hàm băm có dộ dài kép. Khi dùng DES chúng sẽ tạo ra mã băm 128 bit. Tuy nhiên trong cấu trúc tổng quát có thể dùng các hệ mật mã khối khác MDC-2 và MDC4 sử dụng các thành phần xác định như sau: DES được dùng làm mật mã khối E k có đầu vào/ ra 64 bit và được tham số hoá bằng khoá k 56 bit. Hai hàm g và g ánh xạ các giá trị 64 bit U thành các khoá DES 56 bit như sau: Cho U u1u 2 u64 , xoá mọi bit thứ 8 bắt đầu từ u8 và đặt các bit thứ 2 và thứ 3 về "10" đối với g và "01" đối với g . g U u110u 4u5u6u 7u9u10 u63 g U u101u 4u5u 6u7u9u10 u63 Đồng thời điều này cũng phải đảm bảo rằng chúng không phải là các khoá DES yếu hoặc nửa yếu vì các khoá loại này có bit thứ hai bằng bit thứ ba. Đồng thời điều này cũng đảm bảo yêu cầu bảo mật là g IV g IV . Thuật toán MDC -2 có PTITthể được mô tả theo sơ đồ sau: Hình 4.3. Sơ đồ hàm băm MDC – 2 143
Chương 4 - Hàm băm, xác thực và chữ ký số Thuật toán MDC - 2 VÀO: Xâu bit x có độ dài r 64t với t 2 . RA : Mã băm 128 bit của x Phân x thành các khối 64 bit xi : (x1,x 2 , ,xt ) . ~ Chọn các hằng số không bí mật IV và IV từ một tập các giá trị khuyến nghị đã được mô tả trước. Tập ngầm định các giá trị cho trước này là (ở dạng HEXA) IV 0x5252525252525252 ~ IV 0x2525252525252525 Ký hiệu là phép ghép và là các nửa 32 bit phải và trái của C i  Đầu ra h x H t || H t được xác định như sau: (với 1 i t ) L  R H 0 IV , ki g H i 1 , C i E k x i  xi , H i C i ||C i i  L R H IV , k i g(H ), C E (x )  x , H C ||C 0 i 1 i ki i i i i i Thuật toán MDC - 4 có thể được mô tả theo sơ đồ sau: PTIT Hình 4.4. Sơ đồ hàm băm MDC – 4 4.1.4. Các hàm băm có khoá (MAC) Định nghĩa 4.6: Định nghĩa thuật toán mã xác thực thông báo (MAC). Thuật toán MAC là một họ các hàm hk (được tham số hoá bằng một khoá bí mật k ) có các tính chất sau: a) Dễ dàng tính toán: Với hk đã biết và giá trị k cho trước và một đầu vào x , hk (x ) có thể được tính dễ dàng (hk (x ) được gọi là giá trị MAC hay MAC). b) Nén: hk ánh xạ một đầu vào x có độ dài bit hữu hạn tuỳ tới một đầu ra hk (x ) có độ dài bit n cố định. 144
Chương 4 - Hàm băm, xác thực và chữ ký số c) Khó tính toán: Với các cặp giá trị xi ,hk (xi ) không có khả năng tính một cặp xi ,hk (xi ) với x xi (kể cả có khả năng hk (x ) hk (xi ) với một i nào đó). Nếu tính chất c không thoả mãn thì thuật toán được coi là giả mạo MAC. Các hàm băm có khoá được sử dụng để xác thực thông báo và thường được gọi là các thuật toán tạo mã xác thực thông báo (MAC). MAC dựa trên các mật mã khối. Thuật toán VÀO: Dữ liệu x , mật mã khối E, khoá MAC bí mật k của E. RA : n bit MAC trên x (n là độ dài khối của E) 1) Độn và chia khối: Độn thêm các bit vào x nếu cần. Chia dữ liệu đã độn thành từng khối n bit: x1,x 2 , ,xt . 2) Xử lý theo chế độ CBC. Ký hiệu E k là phép mã hoá E với khoá k . Tính khối H t như sau: H1  E k x1 H i  K k H i 1  xi 2 i t 3) Xử lý thêm để tăng sức mạnh của MAC Dùng một khoá bí mật thứ hai k ' k . Tính ' 1 ' H t  E k ' H t , H t E k H t 4) Kết thúc: MAC là khối n bit H t PTIT Hình 4.5. Thuật toán MAC dùng CBC 4.1.5. Tính toàn vẹn của dữ liệu và xác thực thông báo Định nghĩa 4.7: Tính toàn vẹn của dữ liệu là tính chất đảm bảo dữ liệu không bị sửa đổi một cách bất hợp pháp kể từ khi dữ liệu được tạo ra, được phát hoặc được lưu giữ bởi một nguồn được xác định. 145
Chương 4 - Hàm băm, xác thực và chữ ký số Định nghĩa 4.8: Xác thực tính nguyên bản của dữ liệu là một kiểu xác thực đảm bảo một bên liên lạc được chứng thực là nguồn thực sự tạo ra dữ liệu đó ở một thời điểm nào đó trong quá khứ. Xác thực thông báo là một thuật ngữ được dùng tương đương với xác thực nguyên gốc của dữ liệu. Có ba phương pháp cung cấp tính toàn vẹn của dữ liệu bằng cách dùng các hàm băm. a) Chỉ dùng MAC: Khoá bí mật Thông báo Thuật toán MAC Kênh không an toàn Thông báo MAC b) Dùng MDC và mã hoá: Thông báo Thuật toán MDC Khoá bí mật Thông báo MDC Thuật toán mã hoá Kênh không an toàn Thông báo MDC c) Sử dụng MDC và kênh tin cậy Thông báo Thuật toán MDC Kênh tin cậy MDC PTITKênh không an toàn Các phương pháp đảm bảo xác thực tính nguyên vẹn của dữ liệu. Dùng MAC. Dùng các sơ đồ chữ ký số. Gắn (trước khi mã hoá) một giá trị thẻ xác thực bí mật vào văn bản được mã. 4.2. CHỮ KÝ SỐ Trong quá trình làm việc với các văn bản bằng giấy chúng ta sử dụng chữ ký tươi, các yêu cầu cơ bản quan trọng của chữ ký tươi bao gồm: + Ngắn gọn (ngắn hơn văn bản cần ký) 146
Chương 4 - Hàm băm, xác thực và chữ ký số + Là đại diện duy nhất cho người ký. + Khó bắt chước. Khi làm việc qua mạng, do không gặp trực tiếp nên phải dùng chữ ký điện tử và nó cũng thỏa mãn các yêu cầu như chữ ký tươi. Tuy nhiên chữ ký số gắn với từng văn bản. Nếu dùng hàm băm không khóa để làm chữ ký thì ai cũng làm được, còn dùng hàm băm có khóa thì phải trao đổi khóa, có thể giả mạo được. 4.2.1. Sơ đồ chữ ký số Để thực hiện được chữ ký số, người ta xây dựng trên cơ sở kết hợp mã hoá khoá công khai với hàm băm như được mô tả trong Hình 4.6. Hình 4.6. Sơ đồ chữ ký số Trong sơ đồ Hình 4.6, quá trình tạo chữ ký số của A như sau: Bên A cần tạo chữ ký số cho thông báo M (văn bản cần ký), đầu tiên A băm M bằng hàm băm không khóa (MDC) được mã băm đầu ra HMDC, mã băm này được mã hóa bằng một hệ mật khóa công khai bằng khóa bí mật K của A, kết quả được chữ ký số của A là DS . PTITRA A Cuối cùng chữ ký số này được ghép với thông báo M và gửi đến cho B. Bên nhận B tiến hành kiểm tra chữ ký số: Tách chữa ký số DSA khỏi thông báo M. Dùng khóa công khai của A là K CA để giải mã DSA thu được mã băm HMDC của thông báo M của A khi chưa truyền qua kênh mở. Tiến hành băm thông báo M theo đúng thuật toán của A để có được mã băm H MDC của thông báo M đã truyền qua kênh mở. So sánh hai mã băm HMDC và H MDC để xác thực thông báo M. Trong sơ đồ chữ ký số ta nhận thấy rằng việc sử dụng hàm băm là để xác thực nội dung thông báo M, còn hệ mật khóa công khai dùng để xác thực chủ thể nội dung (Bên A) 147
Chương 4 - Hàm băm, xác thực và chữ ký số 4.2.2. Sơ đồ chữ ký số RSA. Có thể coi bài toán xác thực là bài toán "đối ngẫu" với bài toán bảo mật. Vì vậy, sử dụng ngược thuật toán RSA ta có thể có được một sơ đồ chữ ký số RSA như sau: Hình 4.7. Sơ đồ chữ ký số RSA không bảo mật Tạo chữ ký số: + Băm thông báo M: H MDC h(M ) d A + Mã hóa mã băm bằng khóa bí mật dA để tạo chữ ký số: DS A h(M ) mod nA + Ghép chữ ký số với thông báo: M || DS A Kiểm tra chữ ký số: + Tách DSA khỏi thông báo M + Giải mã DSA bằng khóa công khai của A (eA ) để tìm mã băm: eA d A HMDC h(M ) h(M) mod nA + Băm thông báo nhận được: H h(M ) MDC + So sánh hai mã băm H và H để kiểm tra chữ ký số. PTITMDC MDC Sơ đồ chữ ký số trong Hình 4.7 là sơ đồ không bảo mật, khi cần bảo mật cả thông báo M người ta sử dụng sơ đồ Hình 4.8. Trong sơ đồ Hình 4.8, sau khi A tạo được chữ ký số DSA và ghép với thông báo M, thì chúng được mã hóa bằng hệ mật RSA với khóa công khai của B (eB ) và sau đó gửi đến B. Bên B sẽ tiến hành giải mã bằng khóa bí mật của B (dB ) trước khi kiểm tra chữ ký số. 148
Chương 4 - Hàm băm, xác thực và chữ ký số Hình 4.8. Sơ đồ chữ ký số RSA có bảo mật 4.3. HỆ MẬT DỰA TRÊN ĐỊNH DANH 4.3.1. Ý tưởng cơ bản Hệ mật dựa trên định danh do Shamin đề xuất [16] là một hệ mật bất đối xứng trong đó thông tin định danh của thực thể (tên riêng) đóng vai trò khoá công khai của nó. Trung tâm xác thực T được sử dụng để tính khoá riêng tương ứng của thực thể này. Trong các hệ mật khoá công khai thông thường mỗi người sử dụng có một cặp khoá (s,P ) trong đó s là khoá bí mật (chỉ có người dùng này biết) còn P là khoá công khai mà mọi người đều có thể biết. Như vậy, các khoá công khai không cần phải giữ kín mà cần công bố rộng rãi. Tuy nhiên tính công khai này lại trở thành đối tượng cho các tấn công tích cực như việc thay khoá công khai giả vào vị trí khoá công khai thực trong danh bạ. Bởi vậy, ngoài cặp khoá (s,P ) ta cần phải có chuỗi định danh I và không một dấu hiệu đảm bảo G để biết rằng P thực sự là khoá công khai của người dùng I và không phải là một kẻ giả mạo. Khi ta sử dụng các hệ mật dựa trên định danh, khoá công khai sẽ tương đương với định danh (P I ) . Còn dấu hiệu đảm bảo sẽ tương đương với khoá bí mật (tức là G s ). Hệ thống này có nhiều đặc tính tốt do không phải lưu trữ chứng chỉ để kiểm tra. Sau khi tính khoá riêngPTIT của một người dùng T sẽ chuyển khoá riêng cho người dùng đó trên một kênh riêng an toàn. khoá riêng này được tính không chỉ từ thông tin định danh của thực thể mà còn phải là một hàm của một thông tin riêng nào đó chỉ có T mới biết (Khoá riêng của T). Đây là điều cần thiết nhằm tránh giả mạo và bắt chước. Điều chủ yếu là chỉ T mới có khả năng tạo các khoá riêng hợp lệ phù hợp với thông tin định danh. 4.3.2. Sơ đồ trao đổi khoá Okamoto-Tanaka Phần này mô tả tóm lược sơ đồ trao đổi khoá Okamoto-Tanaka [17] là một hệ thống phân phối khoá dựa trên định danh. Sơ đồ này gồm 3 pha sau: Pha chuẩn bị. 149
Chương 4 - Hàm băm, xác thực và chữ ký số Trung tâm xác thực tin cậy chọn 2 số nguyên tố p và q và đưa công khai các giá trị * * * n,g và e , trong đó n pq , g là phần tử sinh của cả Z p và Zq , còn e Z(n ) . Ở đây, hàm Carmichael của n được xác định như sau: (n ) BCNN p 1,q 1 * Cho d Z(n ) là khoá bí mật của trung tâm thỏa mãn điều kiện: ed 1mod(n ) Trung tâm T d d sB IDB sA IDA Người dùng Người dùng Alice Bob rA rB x A sA .g x B sB .g r e A e rB W K A B IDB x B W K BA IDAxA Hình 4.9. Sơ đồ trao đổi khoá Okamoto-Tanaka Pha tham gia của người dùng. Cho IDi là thông tin định danh của người dùng thứ i i A,B ,C , . Cho si là khoá bí mật của người dùng i thoả mãn: PTITs  ID d modn i i Sau đó trung tâm T sẽ công bố e,n ,g,IDi và phân phát si tới mỗi người dùng i qua một kênh an toàn (hoặc bằng cách dùng thẻ). Pha tạo khoá chung. Ta giả sử ở đây rằng hai người dùng Alice và Bob muốn chia sẻ một khoá chung (chẳng hạn để dùng cho một hệ mật khoá bí mật). Trước tiên Alice tạo một số ngẫu nhiên r và tính: A rA x A  sAg modn và gửi nó cho Bob. 150
Chương 4 - Hàm băm, xác thực và chữ ký số Tương tự, Bob tạo một số ngẫu nhiên rB và tính: rB x B  sB g modn và gửi nó cho Alice. Tiếp theo, Alice tính: e rA W K AB IDB x B modn Tương tự, Bob tính e rB W K BA IDAx A modn WKAB và WKBA sẽ dùng làm khoá chung vì: e rA W K AB IDB x B modn rA rB e IDB (sB g ) rA d e rBe IDB (IDB ) .g ge.rB .rA WK BA modn PTIT 151
Chương 3 - Mật mã khoá công khai Ví dụ 3.19: Hai bên liên lạc A và B chọn p 19 . Tạo khóa: + A chọn (m ,n ) (11,5) thỏa mãn 11 5 55 1mod18 . + B chọn (u,v) (7,13) thỏa mãn 7 13 91 1mod18 Giả sử A cần gửi bản tin M 6 cho B. Quá trình truyền tin thực hiện như sau: A 11,5 B 7,13 + A tính 611 mod19 17 và gửi cho B + B nhận 17 và tính: 177 mod19 5 + A nhận 5 và tính: B gửi 5 cho A 55 mod19 9 và gửi 9 cho B + B nhận 9 và giải mã ra bản tin M: 513 mod19 6 M Nhận xét: - Để tìm bản tin M thám mã phải giải bài toán logarit rời rạc, với trường hợp p lớn thì đây là hệ mật an toàn. - Để truyền bản tin M thì phải thực hiện truyền 3 lần, do đó tốc độ mã Rm· 1 3 (thấp). Vì vậy hệ mật này chỉ thích hợp khi truyền các bản tin ngắn hoặc truyền khóa, phân phối khóa cho hệ mật khóa bí mật. 3.4.2.3. Hệ mật Elgamal a) Tạo khóa Mỗi bên liên lạc A,B tạo cho mình một cặp khóa công khai – bí mật theo các bước sau: Bước 1: Chọn một số nguyên tố p lớn và là một phần tử nguyên thủy ¢ * PTIT p Bước 2: Chọn một số nguyên a ngẫu nhiên với 1 a p 1 và tính a mod p Bước 3: + Khóa công khai là bộ 3 số: p, , a + Khóa bí mật là: a b) Mã hóa Giả sử B cần gửi bản tin M cho A, B sẽ thực hiện các bước sau: Bước 1: B nhận khóa công khai của A: p, , a Bước 2: B chọn số nguyên k ngẫu nhiên với 1 k p 1 và tính: 103
Chương 3 - Mật mã khoá công khai k  mod p (3.20) a k  M mod p Giả sử bản tin đã được biểu thị dưới dạng một số nguyên M trong dải 1,,p 1 . Phép tính mũ trong (3.20) được tính bằng thuật toán nhân và bình phương theo modulo. Bước 3: B gửi bản mã C  , cho A. Ta thấy bản mã C được ghép từ  và  nên nó có độ dài bit bằng 2 lần độ dài của M, đây là nhược điểm của hệ mật này. c) Giải mã A nhận bản mã C từ B và tiến hành giải mã theo các bước sau: Bước 1: A sử dụng khóa bí mật a để tính:  p 1 a mod p ak mod p . (Chú ý  p 1 a  a ( k ) a ak ) Bước 2: A khôi phục bản rõ bằng cách tính:  p 1 a mod p M ak ak mod p M Ví dụ 3.20: Tạo khoá. * Bước 1: A chọn p 17 và phần tử nguyên thủy 3 của ¢ 17 . Bước 2: A chọn khóa bí mật a 6 và tính a mod p 36 mod17 15 Bước 3: + Khóa công khai của A là bộ 3 số: p, , a 17,3,15 + Khóa bí mật của A là: a 6 Mã hoá PTIT Giả sử B cần gửi bản tin M 7 cho A. Bước 1: B nhận khóa công khai của A: p, , a 17,3,15 . Bước 2: B chọn số nguyên k 4 và tính: k 4  mod p 3 mod17 13 a k 4  M mod p 7.(15) mod17 10 Bước 3: B gửi bản mã C  , 13,10 cho A. 104
Chương 3 - Mật mã khoá công khai Giải mã A nhận bản mã C  , 13,10 và tiến hành giải mã. Bước 1: A sử dụng khóa bí mật a 6 để tính:  p 1 a mod p 1310 mod17 16 Bước 2: A khôi phục bản rõ bằng cách tính:  p 1 a mod p 10.16mod17 7 M Nhận xét: - Để tìm khóa bí mật a (từ a ) thám mã phải giải bài toán logarit rời rạc (tính a a log ), với trường hợp p lớn thì không thể giải được, hệ mật là an toàn. - Hiệu quả truyền tin thấp, vì tốc độ mã chỉ đạt Rm· 1 2 3.5. BÀI TOÁN PHÂN TÍCH THỪA SỐ VÀ HỆ MẬT RSA 3.5.1. Bài toán phân tích thừa số Theo định lý 1.1, với mỗi số nguyên n 2 ta luôn phân tích n được dưới dạng tích của luỹ thừa của các số nguyên tố và phân tích này là duy nhất như sau: e1 e 2 ek n p1 p 2 pk (3.21) Trong đó pi là các số nguyên tố khác nhau và ei là các số nguyên dương. Nếu n là tích của hai số nguyên tố n pq , trong đó p,q là hai số nguyên tố lớn có độ lớn xấp xỉ nhau, thì việc phân tích n thành tích của p và q là bài toán khó. Hay là, nếu ta biết p,q thì tính n rất đơn giản, nhưng ngược lại biết n thì rất khó tìm p và q . 3.5.2. Hệ mật RSA (Rivest – Shamir – Adleman) 3.5.2.1. Tạo khóa PTIT Mỗi bên liên lạc A và B tự tạo cho mình một cặp khóa công khai – bí mật theo các bước sau đây: Bước 1: Chọn 2 số nguyên tố lớn p và q có độ lớn tương đương. Bước 2: Tính n pq và (n ) (pq) (p 1)(q 1) Bước 3: Chọn một số nguyên e ngẫu nhiên với 1 e (n ) thỏa mãn: e, (n ) 1 Bước 4: Tính số nguyên duy nhất d , 1 d (n ) thỏa mãn ed 1mod (n ) . (Có thể sử dụng thuật toán Euclide mở rộng để tìm d ) Bước 5: + Khóa công khai công khai của A là cặp số: (n,e) 105
Chương 3 - Mật mã khoá công khai + Khóa bí mật của A là số d . Chú ý: Các số nguyên e và d trong thuật toán tạo khoá RSA được gọi là số mũ mã hoá và số mũ giải mã còn số n được gọi là modulus. Ta thấy e và d là hai số nghịch đảo nên vai trò của chúng là giống nhau, tức là nếu khóa công khai là (n,e) thì khóa bí mật là d , ngược lại nếu khóa công khai là (n,d) thì khóa bí mật sẽ là e 3.5.2.2. Mã hóa Giả sử B cần gửi bản tin M cho A (với M n ), B thực hiện các bước sau: Bước 1: B nhận khóa công khai của A (n,e) . Bước 2: B tính (mã hóa): C  M e modn (3.22) Bước 3: B gửi bản mã C cho A. 3.5.2.3. Giải mã A nhận bản mã C từ B và tiến hành giải mã: C d modn M ed modn M (3.23) Nhận xét: - Thám mã có e muốn biết d thì phải biết (n ) , mà muốn biết (n ) thì thám mã phải thực hiện bài toán phân tích thừa số n pq để biết p và q . Khi p và q là các số nguyên tố lớn thì thám mã không thể giải được. - Hiệu quả truyền tin của RSA cao ( Rm· 1). - Thuật toán RSA có tính bền vững, vì các lý do trên mà RSA là một trong các hệ mật được sử dụng rộng rãi trong vòng hơn 30 năm qua. Chú ý (Số mũ vạn năng) Số  BCNN p 1,qPTIT 1 đôi khi được gọi là số mũ vạn năng của n ,  có thể được dùng thay cho p 1 q 1 khi tạo khoá RSA. Cần chú ý rằng  là ước thực sự của . Sử dụng  có thể thu được số mũ giải mã d nhỏ hơn (làm cho giải mã nhanh hơn). Tuy nhiên, nếu p và q được chọn ngẫu nhiên thì UCNN p 1,q 1 sẽ khá nhỏ và bởi vậy  và  sẽ là các số có kích thước xấp xỉ. 3.5.2.4. Một số ví dụ Ví dụ 3.21: Xây dựng các tham số cho hệ mật RSA (Tạo khoá) Bước 1: A chọn p 7 và q 17 . Bước 2: A tính: 106
Chương 3 - Mật mã khoá công khai + n pq 7 17 119 + (n ) (p 1)(q 1) 6 16 96 Bước 3: A chọn e 5 thỏa mãn (5,96) 1 vì (5,6) 1; (5,16) 1 Bước 4: Tính d thỏa mãn: ed 1mod (n ) 5d 1mod96 (3.24) Với các giá trị p,q còn nhỏ ta có thể giải phương trình đồng dư để tìm d . Từ biểu thức (3.24) ta có phương trình sau: 5d 1 k96 1 4.96 Với k 4 tìm được: d 77 5 Bước 5: + Khóa công khai của A là: 119,5 + Khóa bí mật của A là: 77 Cũng có thể chọn khóa công khai là 119,77 và khóa bí mật là 5. Ví dụ 3.22: Xây dựng một hệ mật RSA để gửi bản tin M = CRYPTOGRAPH từ B đến A. Tạo khóa: Bước 1: A chọn p 43,q 59 . Bước 2: A tính n pq 43 59 2537 Và (n ) (p 1)(q 1) 42 58 2436 Bước 3: A chọn e 1357 Bước 4: A tính ra d e 1 1357 1 517 Bước 5: + Khóa côngPTIT khai của A: n,e 2537,1357 + Khóa bí mật của A: d 517 Mã hóa: Bên B biến đổi bản tin M = CRYPTOGRAPH như sau: Biểu diễn dạng Hexa của M: M = C R Y P T O G R A P H MHEX = 43 52 59 50 54 4F 47 52 41 50 48 Các giá trị hexa của các ký tự lấy từ bảng mã ASCII, ví dụ chữ cái C có mã hexa tương ứng là 43. 107
Chương 3 - Mật mã khoá công khai Sau đó chuyển đổi các số hexa thành số nhị phân, ví dụ số 43 gồm 2 số hexa là 4 và 3, khi chuyển sang nhị phân ta chuyển từng số một: số 4Hex  0100Bin , số 3Hex  0011Bin và như thế số 43 sẽ chuyển thành 8 bit nhị phân tương ứng là: 43Hex  0100.0011Bin . Tiến hành chuyển đổi toàn bộ 11 chữ cái của M ta được biễu diễn nhị phân tương ứng của M như sau: M Bin 01000011.01010010.01011001 01010000.01001000 (8 11 88bit ) 43 52 59 50 48 Có một chú ý là khi mã hóa thì giá trị M n , với n tính được ở trên ta thấy: n 2537 2048 211 như vậy mỗi lần chỉ mã hóa được tối đa 11 bit thông tin. Chuỗi bit của bản tin rõ gồm 88 bit, vậy B chia thành 8 khối, mỗi khối 11 bit như sau: M Bin 01000011010.10010010110 00001001000 M1 M 2 M 8 Tiếp theo B sẽ chuyển 8 khối 11 bit (M 1 M 8 ) thành giá trị thập phân tương ứng: M Dec 5 38.1 174.6 72.1 348.1 955.1 353.4 2.7 2 M1 M 2 M 3 M 4 M 5 M 6 M 7 M 8 B tiến hành mã hóa từng khối M i để có các khối bản mã C i tương ứng như sau: e 1357 C 1 M 1 modn 538 mod 2537 905 e 1357 C 2 M 2 modn 1174 mod 2537 1307 C M e modn 6721357 mod 2537 1040 3 3 e 1357 C 4 M 4 modn 1348 mod 2537 1987 e 1357 C 5 M 5 modn 1955 mod 2537 750 C M e modn 13531357 mod 2537 1567 6 6 C M e modn 421357 mod 2537 1590 7 7 C M e modn 721357 mod 2537 1093 8 PTIT8 Cuối cùng B sẽ biến đổi các bản mã C i thành các bit nhị phân và ghép lại thành chuỗi 88 bit và truyền chuỗi bit này đến A. Giải mã: A nhận chuỗi các bit bản mã do B gửi lại tách thành các khối 11 bit và biến đổi thành giá trị thập phân tương ứng để có các khối bản mã C i . Tiếp theo A sẽ giải mã cho từng khối bản mã C i để có các khối M i theo nguyên tắc giải mã: d M i C i modn d 517 Ví dụ: M 1 C 1 modn 905 mod 2537 538 108
Chương 3 - Mật mã khoá công khai Sau khi đã giải mã hết 8 khối C i , A có 8 khối M i và A sẽ thực hiện theo quy trình ngược lại bên B để có bản tin rõ cuối cùng là M = CRYPTOGRAPH Việc mã hóa và giải mã của hệ mật RSA đều dựa vào hàm mũ, trong trường hợp các số mũ lớn, để tính toán được người ta sử dụng thuật toán nhân và bình phương để tính hàm lũy thừa modulo. Thuật toán này đã được trình bày trong mục 3.1.4.2. 3.5.3. Vấn đề điểm bất động trong RSA Xét một ánh xạ y f (x ) (phép mã hóa trong hệ mật), tồn tại các điểm x mà sau khi mã hóa bản tin không thay đổi, tức là: x : x f (x ) Các điểm này gọi là các điểm bất động. y y x y f (x ) x Các điểm bất động Hình 3.6. Các điểm bất động của y f (x ) Hệ mật RSA cũng tồn tại các điểm bất động. Ví dụ 3.23: Xét hệ mật RSA với các tham số: (n,e) 35,17 với p 5,q 7 . Giả sử bản tin M 8 , ta thấy: PTITC M e modn 817mod35 8 Tức là M C như vậy là không che giấu được thông tin. Số các điểm bất động của một hệ mật RSA được xác định theo định lý sau đây: Định lý 3.19: Với hệ mật RSA có tham số khóa công khai là n,e với n p.q thì số bản tin không thể che giấu được (số điểm bất động) tính như sau: N 1 UCLN e 1,p 1 1 UCLN e 1,q 1 (3.25) Ví dụ 3.24: + Với hệ mật RSA có n,e 35,3 với p 5,q 7 thì số bản tin không che giấu được là: 109
Chương 3 - Mật mã khoá công khai N 1 UCLN 2,4 1 UCLN 2,6 9 Các điểm bất động là: M 0,1,6,14,15,20,21,29,34 Như vậy xác suất gặp phải các bản tin không che giấu được khoảng 1 4. + Vẫn hệ hệ mật RSA như trên nhưng ta thay đổi sốe : n,e 35,17 thì lúc này số bản tin không che giấu được là: N 1 UCLN 16,4 1 UCLN 16,6 15 Các điểm bất động là: M 0,1,6,7,8,13,14,15,20,21,22,27,28,29,34 Và xác suất gặp phải các bản tin không che giấu được khoảng gần 1 2. 3.5.4. Hệ mật Rabin 3.5.4.1. Tạo khoá Mỗi bên liên lạc tạo cho mình một khoá công khai và một khoá bí mật tương ứng theo các bước sau: Bước 1: Tạo 2 số nguyên tố lớn, ngẫu nhiên và phân biệt p và q có kích thước xấp xỉ nhau. Bước 2: Tính n pq . Bước 3: + Khoá công khai là n . + Khoá bí mật là các cặp số p,q . 3.5.4.2. Mã hóa B cần gửi bản tin M cho A, phải thực hiện các bước sau: Bước 1: Nhận khoá công khai của A: n Bước 2: Tính C M 2 PTITmodn . Bước 3: B gửi bản mã C cho A. 3.5.4.3. Giải mã: Để khôi phục bản rõ M từ C , A phải thực hiện các bước sau: Bước 1: Tìm 4 căn bậc hai của C modn là M 1,M 2 ,M 3,M 4 . Bước 2: Thông báo cho người gửi là một trong 4 giá trị M 1,M 2 ,M 3,M 4 . Bằng một cách nào đó A sẽ quyết định M là giá trị nào. Chú ý: 110
Chương 3 - Mật mã khoá công khai Tìm các căn bậc 2 của C modn, n pq khi p  q  3mod 4 . Trong trường hợp này, việc tìm 4 căn bậc 2 của C modn được thực hiện khá đơn giản như sau: Sử dụng thuật toán Euclide mở rộng để tìm các số nguyên a và b thoả mãn: ap bq 1. Chú ý rằng a và b có thể được tính trong giai đoạn tạo khoá. Tính r C p 1 4 mod p . Tính s C q 1 4 modq . Tính x aps bqr modn . Tính y aps bqr modn . Bốn giá trị căn bậc 2 của C modn là: x, x modn,y và y modn Ví dụ 3.25: * Tạo khoá. Bước 1: Bên A chọn hai số nguyên tố p 277,q 331. Bước 2: A tính n pq 91687 Bước 3: + Khoá công khai của A là n 91687 . + Khoá bí mật của A là cặp số ( p 277,q 331). * Mã hoá Giả sử rằng 6 bit cuối cùng của bản tin gốc được lặp lại trước khi thực hiện mã hoá. Việc thêm vào độ thừa này nhằm giúp cho bên giải mã nhận biết được bản mã đúng. Để mã hoá bản tin 10 bit M 1001111001, B sẽ lặp lại 6 bit cuối cùng của M để có được bản tin 16 bit sau: M 1001111001111001, biểu diễn thập phân tương ứng là M 40596. dec PTIT Bước 1: B nhận khóa công khai của A: n 91687 2 2 Bước 2: B tính C M modn 40596 mod91687 62111 Bước 3: B gửi C cho A. * Giải mã Để giải mã bản mã C , A thực hiện: Bước 1: Tính bốn giá trị căn bậc 2 củaC modn M 1 69654, M 2 22033, M 3 40596, M 4 51118 Biểu diễn nhị phân tương ứng của các số trên là: 111
Chương 3 - Mật mã khoá công khai M 10001000000010110, M 101011000010001 1 2 M 3 1001111001111001, M 4 1100011110101110 Vì chỉ có M 3 mới có độ thừa cần thiết nên A sẽ giải mã C bằng M 3 và khôi phục lại bản tin gốc là M 1001111001. Đánh giá hiệu quả Thuật toán mã hoá Rabin là một thuật toán cực nhanh vì nó chỉ cần thực hiện một phép bình phương modulo đơn giản. Trong khi đó, chẳng hạn với thuật toán RSA có e 3 phải cần tới một phép nhân modulo và một phép bình phương modulo. Thuật toán giải mã Rabin có chậm hơn thuật toán mã hoá, tuy nhiên về mặt tốc độ nó cung tương đương với thuật toán giải mã RSA. 3.6. BÀI TOÁN XẾP BA LÔ VÀ HỆ MẬT MERKLE – HELLMAN 3.6.1. Bài toán xếp ba lô 3.6.1.1. Dãy siêu tăng Định nghĩa 3.25: Dãy siêu tăng i 1 Dãy các số nguyên dương a1,a2 , ,an được gọi là dãy siêu tăng nếu ai a j với j 1 i, 2 i n Ví dụ: dãy số 1,2,4,8,16,32,64,128 3.6.1.2. Bài toán xếp balô Cho một tập hợp các gói có các trọng lượng khác nhau, liệu có thể xếp một số gói này vào ba lô để ba lô có một trọng lượng cho trước hay không. Về mặt hình thức ta có thể phát biểu bài toán trên như sau: Cho tập các giá trị M ,M , ,M và một tổng S. Hãy tính các giá trị b để: 1 PTIT2 n i S b1M 1 b2M 2 bn M n với bi 0,1 bi 1: Có nghĩa là gói M i được xếp vào ba lô. bi 0: Có nghĩa là gói M i không được xếp vào ba lô. Bài toán có 2n phương án ( 2n vectơ nhị phân b ), bài toán với n lớn (vài trăm) thì không thể giải ở thời gian thực, hay đây là bài toán khó. 112
Chương 3 - Mật mã khoá công khai 3.6.1.3. Giải bài toán xếp ba lô trong trường hợp dãy siêu tăng. Trong trường hợp M M 1,M 2 , ,M n là một dãy siêu tăng thì việc tìm b b1,b2 , ,bn tương đương như bài toán tìm biểu diễn nhị phân của một số S. Biểu diễn này sẽ tìm được sau tối đa là n bước (độ phức tạp tương đương n ). Thuật toán giải: VÀO: Dãy siêu tăng M M 1,M 2 , ,M n  và một số nguyên S là tổng của một tập con trong M n RA : b1,b2 , ,bn trong đó bi 0,1 sao cho: biM i S (Phương án sắp xếp) i 1 Bước 1: i  n Bước 2: Chừng nào i 1 hãy thực hiện: Nếu S M i thì bi 1 và S  S Mi ngược lại: b  0 i i  i 1 Bước 3: Return (b ) Ví dụ 3.26: Cho M 1,2,4,8,16,32,64 ; S 57 , hãy tìm phương án sắp xếp b : n 7 Bước 1: i 7 Bước 2: i 7 : 57 64 b7 0,i 6 i 6 : 57 32 b 1, S 57 32 25; i 5 PTIT6 i 5 : 25 16 b5 1, S 25 16 9; i 4 i 4 : 9 8 b4 1, S 9 8 1; i 3 i 3: 1 4 b3 0; i 2 i 2 : 1 2 b2 0; i 1 i 1: 1 1 b1 1, S 1 1 0; i 0 Bước 3: ta có phương án sắp xếp: b b1,b2 , ,b7 1,0,0,1,1,1,0 113
Chương 3 - Mật mã khoá công khai 3.6.2. Hệ mật Merkle - Hellman Hệ này và các hệ liên quan dựa trên tính khó giải của bài toán tổng các tập con (bài toán này là bài toán NP đầy đủ - là một lớp khá lớn các bài toán không có giải thuật được biết trong thời gian đa thức). Tuy nhiên tất cả các hệ mật xếp ba lô khác nhau đều đã bị chứng tỏ là không mật (ngoại trừ hệ mật Chor-Rivest). 3.6.2.1. Thuật toán tạo khoá Mỗi bên liên lạc tạo cho mình một cặp khóa khoá công khai - khoá bí mật theo các bước sau đây: Bước 1: Chọn một dãy siêu tăng M 1,M 2 , ,M n  và một giá trị modulo M thỏa mãn: n M M i (M là phần tử thứ n 1 của dãy siêu tăng) i 1 Bước 2: Chọn một số nguyên ngẫu nhiên W 1 W M sao cho W ,M 1. (Dễ nhất là chọn M là số nguyên tố) Bước 3: Tính ai W M i modM , với i 1,2, ,n Bước 4: + Khóa công khai: A a1,a2 , ,an + Khóa bí mật: M ,W , M 1,M 2 , ,M n  3.6.2.2. Mã hóa: B cần gửi bản tin m m 1,m 2 , ,m n , m i 0,1 cho A. B thực hiện các bước sau: Bước 1: B nhận khóa công khai của A: M ,W , M 1,M 2 , ,M n  n Bước 2: B tính C m iai i 1 Bước 3: B gửi bản mã CPTIT cho A. 3.6.2.3. Giải mã A nhận bản mã C và tiến hành giải mã theo các bước sau: n 1 Bước 1: A tính d W C modM m iM i i 1 n n n 1 1 1 (Chú ý: d W C W m iai W m iW M i m iM i ) i 1 i 1 i 1 Do W ,M 1 nên sẽ W 1 việc tìm W 1 có thể theo thuật toán Euclid mở rộng. Bước 2: Sử dụng thuật giải bài toán xếp ba lô trong trường hợp dãy siêu tăng để tính 114
Chương 3 - Mật mã khoá công khai n d m iM i i 1 Và tìm lại được m m 1,m 2 , ,m n Ví dụ 3.27: Bên A tạo khóa: Bước 1: A chọn ngẫu nhiên các giá trị M i trong các dải số sau để tạo dãy siêu tăng: M 1 1,16, M 2 17,32, M 3 33,64, M 4 113,128 A có dãy siêu tăng: M 5,23,57,119 4 do M i 204 nên A chọn M 257 (nguyên tố). i 1 Bước 2: Chọn W 113, W 1 vì (113,257) 1, và tính được W 1 W (M ) 1 modM 113255 mod 257 116 Bước 3: Tính ai W M i modM , với i 1,2,3,4 a1 113.5mod 257 51 a 113.23mod 257 29 2 a3 113.57mod 257 16 a4 113.119mod 257 83 Bước 4: + Khóa công khai: A a1,a2 ,a3,a4 51,29,16,83 + Khóa bí mật: M ,W , M 1,M 2 , ,M n  257,113, 5,23,57,119 Mã hóa: B cần gửi bản tin m PTIT(1,1,0,1) cho A. Bước 1: B nhận khóa công khai của A: 257,113, 5,23,57,119 n Bước 2: B tính C m iai 1 51 1 29 0 16 1 83 163 i 1 Bước 3: B gửi bản mã C 163 cho A. Giải mã: A nhận bản tin C 163 và giải mã: Bước 1: A tính d W 1C modM 116.163mod 257 147 Bước 2: Sử dụng thuật giải bài toán xếp ba lô trong trường hợp dãy siêu tăng để tính 115
Chương 3 - Mật mã khoá công khai n d m iM i 147 i 1 i 4 147 119 m 4 1, S 147 119 28, i 3 i 3: 28 57 m 3 0; i 2 i 2 : 28 23 m 2 1; S 28 23 5; i 1 i 1: 5 5 m 1 1, S 1 1 0; i 0 Và bản tin sau giải mã là: m m1,m 2 ,m 3,m 4 1,1,0,1 3.6.3. Hệ mật Chor-Rivest (CR) Hệ mật CR là hệ mật khoá công khai xếp ba lô duy nhất hiện nay không sử dụng phép nhân modulo để ngụy trang bài toán tổng tập con. 3.6.3.1. Tạo khóa Mỗi bên liên lạc tạo một khoá công khai và một khoá riêng tương ứng. A thực hiện các bước sau: h (1) Chọn một trường hữu hạn Fq có đặc số q , trong đó q p ,p h và đối với nó bài toán logarit rời rạc là khó giải. (2) Chọn một đa thức bất khả quy định chuẩn ngẫu nhiên  x bậc h trên Z p . Các phần tử của Fq sẽ được biểu diễn bằng các đa thức trong Z p x  có bậc nhỏ hơn h với phép nhân được thực hiện theo mod  x . (3) Chọn một phần tử nguyên thuỷ ngẫu nhiên g x của Fq . (4) Với mỗi phần tử của trường cơ sở i Z p , tìm logarit rời rạc ai logg x x i của các phần tử x i theo cơ số g x . (5) Chọn một phép hoánPTIT vị ngẫu nhiên trên các số nguyên 1,2,,p 1 . (6) Chọn một số nguyên ngẫu nhiên d , 0 d ph 2 (7) Tính C a d mod ph 1 ,0 i p 1. i i (8) Khoá công khai của A là C 0 ,C 1 ,,C p 1 ,p ,h Khoá riêng của A là  x ,g x , ,d . 3.6.3.2. Mã hoá B cần mã hoá thông báo m để gửi cho A. B thực hiện các bước sau: (1) Nhập khoá công khai của A C 0 ,C 1 ,,C p 1 ,p ,h 116
Chương 3 - Mật mã khoá công khai p (2) Biểu diễn thông báo như một xâu bit có độ dài lg trong đó: h p p! . h h! p h ! (3) Xem m như là biểu diễn nhị phân của một số nguyên. Biến đổi số nguyên này thành môt véctơ nhị phân M M 0 ,M 1 ,,M p 1 có độ dài p và có đúng h con 1 như sau: (a) Đặt l  h (b) For i from 1 to n do: P i p i Nếu m thì đặt M i 1 1,m  m ,l  l 1. l l Nếu không thì đặt n M i 1  0 CY : 1 n 0 0 0 0 l 1 l p 1 h (4) Tính C M ici mod p 1 . i 1 (5) Gửi bản mã C cho A. 3.6.3.3. Giải mã Để khôi phục bản mã rõ m từ C, A phải thực hiện các bước sau: (1) Tính r c hd mod ph 1 (2) Tính u x gr x mod  x (3) Tính s x u x  x là một đa thức định chuẩn h trên Z . PTITp (4) Phân tích s x thành các nhân tử bậc nhất trên Z p . h s x  x t j trong đó t j Z p j 1 1 (5) Các thành phần có giá trị 1 của vectơ M có các chỉ số là t j với 1 j h . Các thành phần còn lại bằng 0 (6) Thông báo m được khôi phục lại từ M như sau a) Đặt m  0,l  h b) For i from 1 to p do: 117
Chương 3 - Mật mã khoá công khai p i Nếu M i 1 1 thì đặt m  m ,l  l 1. l Chứng minh hoạt động giải mã: Ta thấy u x g 2 x mod  x p 1 c hd M c hd  i i  g x  g x i 0 p 1 M a d hd  i i  g x i 0 p 1 M a  i i  g x i 0 mod  x p 1 M i p 1 M i a u x  g x i  x i mod  x   i 0 i 0 p 1 M i Vì  x i và s x là các đa thức định chuẩn bậc h và đồng dư với nhau theo i 0 p 1 modulo  x nên s(x ) u(x ) f (x ) (x (i))M i i 0 1 Bởi vậy tất cả các căn bậc h của s x đều nằm trong Z p và áp dụng đối với các căn này ta sẽ có các toạ độ của M là 1 Ví dụ 3.28: Tạo khoá: A thực hiện các bước sau: (1) Chọn p 7 và h 4. 4 3 2 (2) Chọn đa thức bất khả quy  x x 3x 5x 6x 2 có bậc 4 trên Z 7 . Các phần tử của trường hữu hạn F được biểu diễn bằng các đa thức trong PTIT74 Z 7 x . (3) Chọn phần tử nguyên thuỷ ngẫu nhiên g x 3x 3 3x 2 6 . (4) Tính các logarit rời rạc sau: 118
Chương 3 - Mật mã khoá công khai a0 logg x x 1028 a1 logg x x 1 1935 a2 logg x x 2 2054 a3 logg x x 3 1008 a4 logg x x 4 379 a5 logg x x 5 1780 a6 logg x x 6 223 (5) Chọn phép hoán vị ngẫu nhiên trên 0,1,2,3,4,5,6 như sau: 0 6 3 2 5 5 1 4 4 1 6 3 2 0 (6) Chọn số nguyên ngẫu nhiên d 1702 (7) Tính C 0 a6 d mod 2400 1925 C 1 a4 d mod 2400 2081 C 2 a0 d mod 2400 330 C 3 a2 d mod 2400 1356 C 4 a1 d mod 2400 1237 C 5 a5 d mod 2400 1082 C 6 a3 d mod 2400 310 (8) Khoá công khai của A là C 0 ,C 1 ,C 2 ,C 3 ,C 4 ,C 5 ,C 6 ,p 7,h 4 Khoá bí mật củaPTIT A là  x ,g x , ,d Mã hoá: Để mã hoá bản tin m 22 gửi cho A, B làm như sau: (1) Nhận khoá công khai của A. 7 (2) Biểu diễn m như một xâu bit độ dài 5: m 10110 (Chú ý rằng lg 5) 4 (3) Dùng phương pháp đã nêu ở trên bước c trong thuật toán trên để biến đổi m thành véctơ nhị phân M có độ dài M: M 1,0,1,1,0,0,1 (4) Tính C C 0 C 2 C 3 C 6 mod 2400 1521 (5) Gửi C 1521 cho A Giải mã 119
Chương 3 - Mật mã khoá công khai A nhận bản mã C và giải mã: (1) Tính r c hd mod 2400 1913 1913 (2) Tính u x g x mod  x x 3 3x 2 2x 5 (3) Tính g x u x  x x 4 4x 3 x 2 x (4) Phân tích s x x x 2 x 3 x 6 (Do đó t1 0,t 2 2,t3 3,t 4 6 ) (5) Các thành phần của M bằng 1 có các chỉ số 1 0 2 1 2 3 1 3 6 1 6 0 Bởi vậy M 1,0,1,1,0,0,1 (6) Sử dụng bước 6 trong thuật toán giải mã để biến đổi M thành số nguyên m 22 và như vậy khôi phục được bản rõ ban đầu Chú ý: Hệ mật này được xem là an toàn nếu không bị lộ khoá bí mật. Có thể mở rộng hệ mật này cho trường hợp Z p với p là luỹ thừa của một số nguyên tố . Để làm cho bài toán logarit rời rạc là dễ giải, các tham số p và h phải chọn sao cho q ph 1 chỉ có các nhân tử có giá trị nhỏ. Trong thực tế kích thước khuyến nghị của các tham số là p 200,h 25 (Ví dụ p 197 và h 24 ) Trở ngại lớn nhất của thuật toán là khoá công khai với kích thước chừng p.h log p bit là quá lớn. Ví dụ với p 197 và h 24 khoá công khai có chừng 36.000 bit. 3.7. BÀI TOÁN MÃ SỬA SAI VÀ HỆ MẬT McELIECE 3.7.1. Bài toán mã sửa sai PTIT Định nghĩa 3.26: Giải sử k,n là các số nguyên dương và k n . Mã C n,k là một không gian k chiều n của ¢ 2 (không gian véctơ của tất cả các véctơ nhị phân n chiều). Ma trận sinh Gk n của mã C n,k là ma trận nhị phân có kich thước k n , các hàng của ma trận này tạo nên cơ sở của C. T Ma trận H r n với r n k là ma trận kiểm tra, với: G.H 0 120
Chương 3 - Mật mã khoá công khai n Giả sử y,z ¢ 2 , trong đó y y1,y 2 , ,yn và z z1,z 2 , ,zn . Ta xác định khoảng cách Hamming: d y,z i :1 i n,yi zi  tức là số các toạ độ mà ở đó y và z khác nhau. Khoảng cách mã được định nghĩa như sau: d min d y,z  (3.26) với y,z là hai từ mã khác nhau. Mã sửa sai C n,k có khoảng cách d được ký hiệu là mã C n,k,d . Mã sửa sai được dùng để sửa các sai ngẫu nhiên xảy ra khi truyền số liệu (nhị phân) qua kênh có nhiễu. Điều đó được thực hiện như sau: Giả sử G là một ma trận sinh đối với mã C n,k,d , x là véctơ nhị phân k chiều cần truyền đi. Người gửi Alice sẽ mã hoá x thành một véctơ n chiều y xG rồi truyền y qua kênh. Có hai phương pháp giải mã: * Phương pháp “người láng giềng gẫn nhất” e x y u y e x Mã hóa Kênh Giải mã k x ¢ 2 là bản tin đầu vào (k bit) n y ¢ 2 là từ mã đầu ra (n bit): y xG Giả sử Bob nhận được véctơ n chiều u không giống y , Bob sẽ giải mã u bằng chiến thuật giải mã "người láng giềng gần nhất". Theo chiến thuật này, Bob sẽ giải mã tất cả 2k véctơ đầu vào x để được tập từ mã C 2k véctơ, sau đó so sánh tập này với véctơ thu được u để tìm thấy y có khoảng cáchPTIT tới u nhỏ nhất. Và từ đó sẽ xác định véctơ k chiều x sao cho y x G . Bob hy vọng y y và do đó x x (tức là Bob tin rằng các sai số trên đường truyền đã được sửa). Dễ dàng thấy rằng, nếu sai số trên đường truyền nhiều nhất là d 1 2 thì trên thực tế chiến thuật này sẽ sửa được tất cả các sai. Vì C 2k khi Bob so sánh u với mỗi từ mã, anh ta phải kiểm tra 2k véctơ là một số lớn theo hàm mũ. Nói cách khác, thuật toán này không phải là thuật toán chạy trong thời gian đa thức. Hay độ phức tạp của thuật toán theo hàm mũ, và khi giá trị k lớn thì nó sẽ là bài toán khó giải. * Phương pháp giải mã theo syndrom 121
Chương 3 - Mật mã khoá công khai Một biện pháp khác (tạo cơ sở cho nhiều thuật toán giải mã thực tế) dựa trên khái niệm về syndrom. Các hàng của ma trận kiểm tra H sẽ tạo cơ sở cho các phần bù trực giao của C (ký hiệu là C  ) và được gọi là mã đối ngẫu với C . Nói cách khác, các hàng của H là những véctơ độc lập tuyến tính, còn GH T 0 là một ma trận 0 cấp k r .  k r   n T Cho véctơ y ¢ 2 , ta xác định syndrom của y là s(y) yH . Syndrom s(y) là một véctơ hàng có r n k thành phần. Định lý 3.20: Giả sử C là một bộ mã n,k có ma trận sinh G và ma trận kiểm tra tính chẵn lẻ H . n T Khi đó y ¢ 2 là một từ mã khi và chỉ khi yH 00 0. n T T T Hơn nữa nếu y C ,e ¢ 2 và u y e thì uH eH hay s(u) s(e) uH . Định lý trên phát biểu rằng syndrom chỉ phụ thuộc vào các sai số mà không phụ thuộc vào từ mã cụ thể nào được truyền đi. Điều này gợi ý tới một cách giải mã gọi là giải mã theo syndrom. Trước tiên Bob tính s(u) uH T nếu s(u) 0, thì anh ta có từ mã đúng y u và tìm ra x . Nếu không thì Bob sẽ lần lượt tạo tất cả các véctơ sai e có trọng số 1. Với mỗi véctơ này, Bob tính s(e) eH T , nếu có một véctơ e nào đó thoả mãn s(e) eH T s(u) thì Bob sẽ có từ mã đúng là y u e và từ sẽ tìm lại được x . Nếu không có e nào thỏa mãn Bob tiếp tục làm như thế với các vectơ sai có trọng số 2,3, , d 1 2 để tìm ra e thỏa mãn s(e) s(u) . Số các trường hợp sai N e t , tính như sau (với t là số sai khả sửa t d 1 2 ): t i N e C n (3.27) i 0 Như vậy, khi giải mã theo syndrom Bob phải so sánh s(u) với s(e) trong N e trường hợp. Và theo (3.27) độ phức PTITtạp của bài toán tương đương 2r , tức là vẫn theo hàm mũ, khi r lớn thì bài toán là khó giải. 3.7.2. Hệ mật McEliece 3.7.2.1. Tạo khóa Mỗi bên liên lạc tạo cho mình một cặp khóa công khai - khóa bí mật theo các bước sau: Bước 1: Chọn một mã tuyến tính sửa sai n,k,d (khuyến nghị k n 2) với ma trên sinh G , bộ mã có một thuật toán giải mã hiệu quả. Bước 2: 122
Chương 3 - Mật mã khoá công khai 1 + Chọn ma trận hoán vị Pn cấp n n , sao cho tồn tại ma trận nghịch đảo Pn 1 với: Pn Pn I (với I là ma trận đơn vị). Mỗi hàng và mỗi cột của Pn chỉ có duy nhất một con số 1. 1 1 + Chọn một ma trận khả nghịch S k k S , SS I Bước 3: Tính G SGP Bước 4: + Khóa công khai: G ,t . + Khóa bí mật: S ,P ,G Chú ý: Các tham số của mã Goppa có dạng n 2v ,d 2t 1 và k n vt . Để áp dụng trong thực tế cho một hệ mật khoá công khai, McEliece đề nghị chọn v 10 và t 50 . Điều này ứng với mã Goppa 1024,524,101 . Mỗi bản rõ m là một véctơ nhị phân cấp 524 và mỗi bản mã C là một véctơ nhị phân cấp 1024. Khoá công khai G là một ma trận nhị phân cấp 524 x1024 . 3.7.2.2. Mã hóa Giả sử B cần gửi bản tin m cho A, B thực hiện các bước sau: Bước 1: B nhận khóa công khai của A: G ,t Bước 2: B tính y mG xG , x m n Bước 3: B chọn e ¢ 2 thỏa mãn W (e) t Bước 4: B tính c y e (Chèn thêm véctơ sai) Bước 5: B gửi bản mã c cho A. 3.7.2.3. Giải mã A nhận bản mã c từ B PTITvà tiến hành giải mã theo các bước sau: Bước 1: A tính: u c.P 1 y e P 1 yP 1 eP 1 xG P 1 eP 1 xSGPP 1 eP 1 xSG eP 1 Hay u x G eP 1 y e Trong đó: e eP 1 là một véctơ sai nào đó. Bước 2: A giải mã sửa sai từ mã u để tìm x . Bước 3: A tính x x S 1 x m để lấy lại bản tin rõ. 123
Chương 3 - Mật mã khoá công khai Ví dụ 3.29: * Tạo khóa: Bên A tạo khóa. Bước 1: Chọn mã tuyến tính sửa sai n,k,d 7,4,3 , với ma trận sinh: 1 0 0 0 1 1 0 0 1 0 0 1 0 1 G 0 0 1 0 0 1 1 0 0 0 1 1 1 1 d 1 Và t 1 2 Bước 2: + Chọn ma trận hoán vị Pn : 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 Pn 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 + Chọn một ma trận khả nghịch S k k : 1 1 0 1 1 0 0 1 S 0 1 1 1 1 1 0 0 Bước 3: Tính G SGP PTIT1 1 1 1 0 0 0 1 1 0 0 1 0 0 G 1 0 0 1 1 0 1 0 1 0 1 1 1 0 Bước 4: + Khóa công khai: G ,t . + Khóa bí mật: S ,P ,G * Mã hóa: Giả sử B cần gửi bản tin m x 1 1 0 1 cho A. Bước 1: B nhận khóa công khai của A: G ,t 124
Chương 3 - Mật mã khoá công khai Bước 2: B tính y mG 1 1 1 1 0 0 0 1 1 0 0 1 0 0 y 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 Bước 3: B chọn véctơ sai e 0 0 0 0 1 0 0 có W (e) 1 t Bước 4: B tính c y e c 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 Bước 5: B gửi bản mã c cho A. * Giải mã: Khi A nhận được bản mã c , A tiến hành giải mã: Bước 1: A tính u cP 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 u 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 Bước 2: B giải mã u y e bằng phương pháp syndrom tìm được: y 1 0 0 0 1 1 0 Cần để ý là e ' e do phép nhân với P 1 Sau đó B lập x 1 0PTIT0 0 (bốn thành phần đầu tiên của y , vì mã sửa sai là mã hệ thống). Bước 3: Cuối cùng B tính ra bản rõ: 1 1 0 1 1 1 0 0 x x S 1 0 0 0 1 1 0 1 m 0 1 1 1 1 0 0 1 125
Chương 3 - Mật mã khoá công khai 3.8. ĐƯỜNG CONG ELLIPTIC VÀ CÁC HỆ MẬT LIÊN QUAN 3.8.1. Các đường cong Elliptic. Một đường cong Elliptic là một phương trình bậc 3 có dạng sau: y 2 axy by x 3 cx 2 dx e (3.28) Trong đó a,b,c,d,e là các số thực. Trên các đường cong E ta xác định một phép cộng đặc biệt với một điểm O được gọi là điểm vô cực. Nếu trên đường thẳng cắt đường cong E ở ba điểm thì tổng của chúng bằng điểm vô cực O (điểm O này có vai trò như phần tử đơn vị trong phép cộng này). Hình 3.7 sau mô tả các đường cong E y 2 x 3 2x 5 và y 2 x 3 2x 1 Hình 3.7. Các đường cong y 2 x 3 2x 5 và y 2 x 3 2x 1 3.8.2. Các đường cong Elliptic trên trường Galois Định nghĩa 3.27: Đường cong Elliptic trên trường hữu hạn Z p (với p là số nguyên tố) dạng Weiestrass được mô tả như sau: PTITy 2  x 3 ax bmod p (3.29) với x Z p ; a,b nguyên dương. Điều kiện tồn tại là: 4a 3 27b2 mod p 0 (3.30) Ví dụ 3.30: Xét p 17 và đường cong elliptic: y 2  x 3 x 1mod17. 4 27 mod17 14 0 đảm bảo điều kiện tồn tại. Xác định các thặng dư bậc 2: Q17 126
Chương 3 - Mật mã khoá công khai i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 i 2 1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 Vậy Q17 1,4,9,16,8,2,15,13 và các căn bậc hai: 1 1,16 ; 4 2,15 ; 9 3,14 ; 16 4,13 ; 8 5,12 ; 2 6,11 ; 15 7,10 ; 13 8,9 Chú ý: Việc tính thặng dư bậc 2 và các căn bậc 2 theo các định nghĩa 3.18, 3.19; và các định lý 4.14 và 3.15. Từ đây tính được các cặp giá trị x,y trên đường cong elliptic như bảng dưới: x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 y 2 1 3 11 14 1 12 2 11 11 8 8 0 7 1 5 8 16 2 Y N N N Y N Y N N Y Y N N Y N Y Y y Q17 ? 1 1 6 5 5 0 1 5 4 y1 16 16 11 12 12 0 16 12 13 y 2 2 Chú ý: mặc dù y 0 không thuộc Q17 nhưng số 0 có căn bậc hai chính là 0. Từ đây ta có được nhóm cộng E17 (1,1) gồm 18 phần tử trên đường cong elliptic y 2  x 3 x 1mod17 như sau: E17 (1,1) 0,1 , 0,16 , 4,1 , 4,16 , 6,6 , 6,11 , 9,5 , 9,12 , 10,5 10,12 , 11,0 , 13,1 , 13,16 , 15,5 , 15,12 , 16,4 , 16,13 ,0 y PTIT x Hình 3.8. Tọa độ các điểm của nhóm cộng trên đường cong elliptic y 2  x 3 x 1mod17 127
Chương 3 - Mật mã khoá công khai Trong nhóm cộng này có thêm phần tử cuối cùng là phần tử zero 0 .Nhóm này có cấp bằng 18 và có 6 phần tử nguyên thủy  18 6 để tạo nhóm cyclic. Tọa độ các điểm của nhóm được mô tả trong Hình 3.8 3.8.3. Các phép toán cộng và nhân trên các nhóm E Giả sử P x1,y1 , Q x 2 ,y 2 là các điểm trong nhóm E p a,b , 0 là điểm vô cực. Các quy tắc đối với phép cộng trên nhóm con E p a,b như sau: (1) P 0 0 P P . (2) Nếu x 2 x1 và y 2 y1 tức là P x1,y1 và Q x 2 ,y 2 x1, y1 P thì P Q 0. (3) Nếu Q P thì tổng P Q K x 3,y3 với tọa độ x 3 ,y3 của K xác định như sau: x  2 x x mod p 3 1 2 (3.31) y3  x1 x 3 y1 mod p Trong đó: y 2 y1 mod p , nÕu P Q x 2 x1  (3.32) 3x 2 a 1 mod p , nÕu P Q 2y1 * Cách xây dựng nhóm cộng trên đường cong elliptic Các phần tử của nhóm được tính như sau: - Phần tử zero: 0 , nằm ngoài tập hợp. - Các phần tử khác tính theo quy tắc phép cộng các điểm trên đường cong Elliptic như trình bày trên đây. PTIT Ví dụ 3.31: Xây dựng nhóm E p a,b E17 1,1 từ phần tử nguyên thủy P 0,1 và tìm tất cả các phần tử nguyên thủy của nhóm. Theo nguyên tắc tính các điểm ở biểu thức (3.31) và (3.32) ta tính được các điểm của nhóm cộng như sau. + Điểm P 0,1 + Điểm 2P P P 3.0 1  2 1 mod17 9mod17 x 81mod17 13,y 1 2.1 3 3 128
Chương 3 - Mật mã khoá công khai Vậy 2P 13,1 Chú ý: số 2 và 9 là hai số nghịch đảo, có nhiều cách tính nghịch đảo, sau đây là một * cách tính theo nhóm nhân Z17 có phần tử sinh là 3. * Bảng 3.11. Nhóm nhân Z17 với phần tử sinh 3 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 3i mod17 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 1 + Điểm 3P P 2P 0 x 3 13mod17 4  0 12 y3 1mod17 16 3P 4,16 + Điểm 4P P 3P 15 1 x 3 9  15.4 mod17 15.13mod17 8 4 y 3 12 4P 9,12 + Điểm 5P P 4P 15 1 x 3 16  15.9 mod17 15.6mod17 5 9 y 3 4 5P 16,4 + Điểm 6P P 5P 3 x 3 10  3.16 1 3.16mod17 14 16 y 12 PTIT 3 6P 10,12 + Điểm 7P P 6P 11 1 x 3 6  11.10 11.12mod17 13 10 y3 6 7P 6,6 + Điểm 8P P 7P 5 x 3 15  5.6 1 5.3mod17 15 6 y3 12 129
Chương 3 - Mật mã khoá công khai 7P 15,12 + Điểm 9P P 8P 11 1 x 3 11  11.15 11.8mod17 3 15 y 3 0 9P 11,0 Từ điểm 10P trở đi có thể tính theo quy tắc sau: P x,y P x, y + Điểm 10P 8P 10P (15, 12) 10P (15,5) . (Chú ý: 12mod17  5mod17 ) + Điểm 11P 7P 11P (6, 6) 11P (6,11) . + Điểm 12P 6P 12P (10, 12) 12P (10,5) . + Điểm 13P 5P 13P (16, 4) 13P (16,13) . + Điểm 14P 4P 14P (9, 12) 14P (9,5) . + Điểm 15P 3P 15P (4, 16) 15P (4,1) . + Điểm 16P 2P 16P (13, 1) 16P (13,16) . + Điểm 17P P 17P (0, 1) 17P (0,16) . + Điểm 18P 0 . Các điểm nguyên thủy của nhóm nhân được xác định như sau: Nếu P là một điểm nguyên thủy thì kP sẽ là nguyên thủy với k, E p a,b 1 Trong ví dụ này ta có E17 1,1 18 vậy các điểm nguyên thủy kP có k,18 1, hay k 1,5,7,11,13,17. Các điểm nguyên thủy lPTITà: P ,5P ,7P ,11P ,13P ,17P (6 điểm) 3.8.4. Các hệ mật trên đường cong elliptic 3.8.4.1. Trao đổi thỏa thuận khóa Diffie - Hellman Xét nhóm E p a,b trên đường cong elliptic và P là điểm nguyên thủy P E p a,b . Quá trình trao đổi khóa diễn ra như sau: A B + A chọn ngẫu nhiên x với điều kiện: + B chọn ngẫu nhiên y với điều kiện: 1 x #E a,b sau đó A tính xP và p 1 y #E p a,b sau đó A tính yP và gửi cho B. gửi cho A. 130
Chương 3 - Mật mã khoá công khai + A nhận yP và tính ra khóa dùng chung: + B nhận xP và tính ra khóa dùng chung: K x yP xyP K y xP xyP Ví dụ 3.32: Xét E17 1,1 và điểm nguyên thủy P 0,1 (Nhóm E17 1,1 như đã tính ở ví dụ 3.31) A B + A chọn ngẫu nhiên x 3 và tính: + B chọn ngẫu nhiên y 5 và tính: 3P 4,6 và gửi cho B. 5P 16,4 và gửi cho A. + A nhận 5P và tính ra khóa dùng chung: + B nhận 3P và tính ra khóa dùng chung: K 3 5P 15P 4,1 K 5 3P 15P 4,1 3.8.4.2. Hệ mật Omura – Massey Tạo khóa: + Hai bên liên lạc chọn trước nhóm E p a,b làm khóa công khai + Khóa bí mật tạo như sau: - A chọn ngẫu nhiên hai số m ,n làm khóa bí mật, sao cho m n #E p a,b - B chọn ngẫu nhiên hai số u,v làm khóa bí mật, sao cho u v #E p a,b Giả sử A cần gửi bản tin M cho B, quá trình truyền tin bảo mật diễn ra như sau: A m ,n B u ,v + A tính mP M và gửi cho B + B nhận mP M và tính PTIT mP M uP và gửi lại A. + A nhận mP M uP và tính: + B nhận M uP và giải mã ra bản tin: M uP vP M mP M uP nP M uP và gửi cho B. Ví dụ 3.33: Xét E17 1,1 và điểm nguyên thủy P 0,1 (Nhóm E17 1,1 như đã tính ở ví dụ 3.31). Bản tin M 4,16 3P (Chú ý phải có phép biến đổi bản tin thành một trong các điểm thuộc E17 (1,1) ) + Khóa công khai: E17 1,1 131
Chương 3 - Mật mã khoá công khai + Khóa bí mật: - A chọn ngẫu nhiên hai số m ,n 3,15 với m n 18 #E17 1,1 - B chọn ngẫu nhiên hai số u,v 5,13 với u v 18 #E17 1,1 Quá trình truyền tin bảo mật: A 3,15 B 5,13 + A tính + B nhận 6P 10,12 và tính mP M 3P 3P 6P 10,12 6P 5P 11P 6,11 và gửi lại A. và gửi cho B + A nhận 11P 6,11 và tính: + B nhận 8P 15,12 và giải mã ra bản tin: 11P 15P 8P 15,12 và gửi cho B. 8P 13P 3P 4,16 M 3.8.4.3. Hệ mật Elgamal a) Tạo khóa Mỗi bên liên lạc tạo cho mình một cặp khóa công khai – bí mật theo các bước sau: Bước 1: Chọn nhóm E p a,b và điểm nguyên thủy P Bước 2: Chọn ngẫu nhiên a với 1 a #E p a,b và tính aP Q Bước 3: + Khóa công khai: E p (a,b),P , Q + Khóa bí mật: a b) Mã hóa Giả sử B cần gửi bản tinPTIT M cho A, B thực hiện các bước sau: Bước 1: B nhận khóa công khai cả A : E p (a,b),P , Q Bước 2: B chọn k ngẫu nhiên 1 k #E p a,b và tính:  kP  M kQ Bước 3: B gửi bản mã C  , cho A. c) Giải mã A nhận bản mã C  , và giải mã theo các bước: Bước 1: A tính a akP kQ 132
Chương 3 - Mật mã khoá công khai Bước 2: A tính  kQ M kQ kQ M Ví dụ 3.34: Xét E17 1,1 và điểm nguyên thủy P 0,1 (Nhóm E17 1,1 như đã tính ở ví dụ 3.31). Bản tin M 15,5 10P * Bên A tạo khóa: Bước 1: A chọn a 3 và tính aP 3P 4,16 Q Bước 2: + Khóa công khai của A: E17 1,1 ,P 0,1 ,Q 4,16 + Khóa bí mật: a 3 * Mã hóa: B gửi bản tin M 10P (15,5) cho A Bước 1: B nhận khóa công khai cả A : E17 1,1 ,P 0,1 ,Q 4,16 Bước 2: B chọn k 5 ngẫu nhiên và tính:  kP 5P 16,4  M kQ 10P 5Q 10P 5 3P 7P 6,6 Bước 3: B gửi bản mã C  , 5P ,7P cho A. * Giải mã: A nhận bản mã C 5P ,7P và giải mã theo các bước: Bước 1: A tính a 3 5P 15P 4,1 Bước 2: A tính  kQ 7P 15P 10P 15,5 M 3.8.5. Độ an toàn của hệ mật trên đường cong Elliptic Sức mạnh ECC nằm ở PTITsự khó khăn đối với thám mã khi phải xác định số ngẫu nhiên bí mật k từ kP và P. Phương pháp nhanh nhất để giải bài tóan này là phương pháp phân tích S - Pollard. Để phá ECC độ phức tạp tính toán khi dùng phương pháp S – Pollard là 3,8.1010 MIPS - năm với kích thước khóa 150 bit (đây là số năm cần thiết với một hệ thống tính toán có tốc độ hàng triệu lệnh/giây). Để so sánh với phương pháp nhanh nhất phá RSA (là phương pháp sàng trừng số để phân tích hợp số n thành tích của 2 số nguyên tố p và q ) ta thấy rằng với n có kích thước 768 bit độ phức tạp tính toán là: 2.108MIPS - năm , với n có kích thước 1024 bit, độ phức tạp tính toân là 3.1011 năm . Nếu độ dài khóa của RSA tăng lên tới 2048 bit thì cần 3.1020 MIPS - năm, trong khi đó với ECC chỉ cần độ dài khóa là 234 bit đã phải yêu cầu tới 1,6.1028MIPS - năm. 133
Chương 3 - Mật mã khoá công khai 3.9. ƯU VÀ NHƯỢC ĐIỂM CỦA MẬT MÃ KHÓA CÔNG KHAI 3.9.1. Ưu điểm + Mật mã khóa công khai không sử dụng kênh an toàn riêng để truyền khóa. + Dễ sinh khóa, bảo vệ và lưu trữ khóa. + Dễ xây dựng các dịch vụ an toàn khác như: xác thực, chữ ký số So sánh với mật mã khóa bí mật như bảng sau (giả sử ta xét n người dùng trên mạng): Bảng 3.12. So sánh số lượng khóa của mật mã khóa bí mật và mật mã khóa công khai n người dùng Số khóa cần tạo Số khóa cần lưu trữ Mật mã khóa bí mật n n 1 n 1 2 Mật mã khóa công khai 2n 1 3.9.2. Nhược điểm + Nói chung mật mã khóa công khai phức tạp (phải xây dựng trên các trường lớn, mạch điện phức tạp, thời gian xử lý chậm hơn so với mật mã khóa bí mật) + Hiệu quả không cao (nói chung các hệ mật khóa công khai có tốc độ mã thấp) Từ các nhược điểm này ta thấy mật mã khóa công khai khó thực hiện cho các dịch vụ nhạy cảm với độ trễ hoặc các dịch vụ di động. 3.10. XÂY DỰNG CÁC CHƯƠNG TRÌNH ỨNG DỤNG KIẾN TRÚC PGP (PGP – Pretty Good Privacy: tạm dịch là “Riêng tư tốt đẹp”) Từ các ưu và nhược điểm của mật mã khóa công khai và mật mã khóa bí mật, người ta kết hợp ưu điểm của hai loại mật mã này xây dựng nên một cấu trúc truyền tin PGP như Hình 3.9: Thám mã Bản mã của A PTIT B bản tin C C Mã hóa khóa M M Giải mã khóa Kênh mở bí mật bí mật M Bản mã của M C K khóa C K Khóa bí Khóa bí mật K mật K Mã hóa khóa Giải mã khóa công khai công khai Sinh khóa Khóa công khai Khóa bí mật của B: K CB của B: K RB Hình 3.9. Sơ đồ kiến trúc PGP 134
Chương 3 - Mật mã khoá công khai Trong sơ đồ này, bản tin M được truyền đi bảo mật sử dụng mật mã khóa bí mật với khóa là K. Khóa bí mật K được mã hóa bằng hệ mật khóa công khai từ A đến B (sử dụng khóa công khai và bí mật của B). Việc mã hóa bản tin bằng mật mã khóa bí mật sẽ có ưu điểm tốc độ mã hóa nhanh, hiệu quả cao, còn việc truyền khóa sử dụng mật mã khóa công khai là để thay thế kênh an toàn tiết kiệm chi phí. BÀI TẬP CHƯƠNG 3 Bài 3.1: Sử dụng thuật toán Euclide mở rộng để tìm ước chung lớn nhất của hai số a 1573, b 308 . Bài 3.2: Hãy tính 332 mod 23 bằng cách dùng thuật toán nhân và bình phương có lặp. Bài 3.3: Hãy tính các căn bậc hai của 12 mod 37 . * Bài 3.4: Tìm tất cả các phần tử nguyên thuỷ của nhóm nhân Z19 . * Bài 3.5: Tìm phần tử nghịch đảo của 3 trong Z31 . Bài 3.6: Với m ,n ,s N và pi là các số nguyên tố. Hãy chứng minh các tính chất sau của hàm Phi-Euler s s 1 a) p p 1 . p b) m ,n m n nếu UCLN m ,n 1. 1 1 e1 e1 c) n m 1 1 trong đó m p1 pr là phân tích của m thành tích p1 pr của thừa số nguyên tố. Bài 3.7: Hãy tính 490 vàPTIT 768 . Bài 3.8: Giải hệ phương trình đồng dư sau: 5x  20mod6 6x  6mod5 4x  5mod77 Bài 3.9: Hãy dùng thuật toán Euclide mở rộng để tính các phần tử nghịch đảo sau: a) 17 1 mod 101 b) 357 1 mod 1234 c) 3125 1 mod9987 Bài 3.10: Ta nghiên cứu một số tính chất của các phần tử nguyên thuỷ: 135
Chương 3 - Mật mã khoá công khai a) 97 là một số nguyên tố. Hãy chứng minh rằng x 0 là một phần tử nguyên thuỷ theo modulo 97 khi và chỉ khi: x 32 1mod97 và x 48 1mod97 b) Hãy dùng phương pháp này để tìm phần tử nguyên thuỷ nhỏ nhất theo modulo 97 . c) Giả sử p là một số nguyên tố và p 1 có phân tích ra luỹ thừa của các nguyên tố sau: n ei p 1 pi i 1 Ở đây pi là các số nguyên tố khác nhau. Hãy chứng tỏ rằng x 0 là một phần tử nguyên thuỷ theo modulo p khi và chỉ khi x p 1 pi 1mod p với 1 i n . * Bài 3.11: Cho ¢ 13 , biết 2 là phần tử nguyên thuỷ của ¢ 13 . Hãy: * a) Tìm tất cả các phần tử nguyên thuỷ của ¢ 13 * b) Giải bài toán logarit rời rạc: Tìm log y với là phần tử nguyên thuỷ, y ¢ 13 * c) Tìm các thặng dư bậc 2 của ¢ 13 Bài 3.12: Giải bài 3.11 trong các trường hợp sau: * a) ¢ 19 , biết 2 là phần tử nguyên thuỷ của ¢ 19 . * b) ¢ 23 , biết 5 là phần tử nguyên thuỷ của ¢ 23 . * c) ¢ 29 , biết 2 là phần tử nguyên thuỷ của ¢ 29 . Bài 3.13: Tính khoá chung trong thủ tục thoả thuận khoá Diffie – Hellman với các trường hợp sau: (với p -nguyên tố, là phần tử nguyên thủy). * a) p 11, 7 Z11 . * PTIT b) p 17, 6 Z17 . * c) p 19, 10 Z19 . * d) p 23, 11 Z 23 . * e) p 29, 8 Z 29 . Bài 3.14: Hãy xây dựng hệ mật Omura-Massey để thực hiện việc truyền khoá bí mật k từ A đến B: - Tính số các trường hợp có thể lựa chọn tham số của hệ - Lấy 1 ví dụ với khoá được chọn bởi A là k 5 136