Giáo trình Tin học đại cương - Chương IV: Các hệ mật mã khoá công khai

Nội dung text: Giáo trình Tin học đại cương - Chương IV: Các hệ mật mã khoá công khai

1. CHƯƠNG IV Các hệ mật mã khoá công khai 4.1. Giới thiệu mở đầu. 4.1.1. Sự ra đời của mật mã khoá công khai. Trong ch−ơng I ta đã giới thiệu qua định nghĩa của các khái niệm hệ mật mã khoá đối xứng và hệ mật mã khoá công khai. Sự ra đời của khái niệm hệ mật mã khoá công khai là một tiến bộ có tính chất b−ớc ngoặt trong lịch sử mật mã nói chung, gắn liền với sự phát triển của khoa học tính toán hiện đại. Ng−ời ta có thể xem thời điểm khởi đầu của b−ớc ngoặt đó là sự xuất hiện ý t−ởng của W. Diffie và M.E. Hellman đ−ợc trình bày vào tháng sáu năm 1976 tại Hội nghị quốc gia hàng năm của AFIPS (Hoa kỳ) trong bài Multiuser cryptographic techniques. Trong bài đó, cùng với ý t−ởng chung, hai tác giả cũng đã đ−a ra những thí dụ cụ thể để thực hiện ý t−ởng đó, và mặc dù các thí dụ ch−a có ý nghĩa thuyết phục ngay đối với tác giả, thì ý t−ởng về các hệ mật mã khoá công khai cũng đã rất rõ ràng và có sức hấp dẫn đối với nhiều ng−ời. Và ngay sau đó, công việc tìm kiếm những thể hiện cụ thể có khả năng ứng dụng trong thực tế đã bắt đầu thu hút sự quan tâm của nhiều chuyên gia. Một năm sau, năm 1977, R.L. Rivest, A. Shamir và L.M. Adleman đề xuất một hệ cụ thể về mật mã khoá công khai mà độ an toàn của hệ dựa vào bài toán khó “phân tích số nguyên thành thừa số nguyên tố”, hệ này về sau trở thành một hệ nổi tiếng và mang tên là hệ RSA, đ−ợc sử dụng rộng rãi trong thực tiễn bảo mật và an toàn thông tin. Cũng vào thời gian đó, M.O. Rabin cũng đề xuất một hệ mật mã khoá công khai dựa vào cùng bài toán số học khó nói trên. Liên tiếp sau đó, nhiều hệ mật mã khóa công khai đ−ợc đề xuất, mà khá nổi tiếng và đ−ợc quan tâm nhiều là các hệ: hệ McEliece đ−ợc đ−a ra năm 1978 dựa trên độ NP-khó của bài toán giải mã đối với các hệ mã cyclic tuyến tính, hệ Merkle- Hellman dựa trên tính NP- đầy đủ của bài toán xếp ba lô(knapsack problem), hệ mật mã nổi tiếng ElGamal dựa trên độ khó của bài toán lôgarit rời rạc, hệ này về sau đ−ợc mở rộng để phát triển nhiều 92
2. hệ t−ơng tự dựa trên độ khó của các bài toán t−ơng tự lôgarit rời rạc trên các cấu trúc nhóm cyclic hữu hạn, nhóm các điểm nguyên trên đ−ờng cong eliptic, v.v Để tăng độ bảo mật, hệ mật mã ElGamal còn dùng với t− cách đầu vào cho thuật toán lập mật mã của mình, ngoài khoá công khai và bản rõ, một yếu tố ngẫu nhiên đ−ợc chọn tuỳ ý, điều đó làm cho hệ mật mã trở thành một hệ mật mã xác suất khoá công khai. Một số hệ mật mã xác suất khoá công khai cũng đ−ợc phát triển sau đó bởi Goldwasser-Micali và Blum- Goldwasser. Tất cả các hệ mật mã khoá công khai kể trên sẽ đ−ợc trình bày trong ch−ơng này cùng với một số tính chất liên quan của chúng. 4.1.2. Một số bài toán cơ bản. Sau đây ta sẽ nhắc lại một số bài toán số học đ−ợc sử dụng đến khi xây dựng các hệ mật mã khoá công khai nh− nói ở trên. Các bài toán này phần lớn đã đ−ợc trình bày trong ch−ơng II, một số đ−ợc phát triển thêm cho các ứng dụng trực tiếp khi xây dựng các hệ mã cụ thể, ta liệt kê d−ới đây một lần để thuận tiện cho các chỉ dẫn về sau. Bài toán phân tích số nguyên (thành thừa số nguyên tố): Cho số nguyên d−ơng n , tìm tất cả các −ớc số nguyên tố của αα12 αk nó, hay là tìm dạng phân tích chính tắc của n = pp12. pk , trong đó pi là các số nguyên tố từng cặp khác nhau và các αi ≥ 1. Bài toán này có liên hệ mật thiết với các bài toán thử tính nguyên tố hay thử tính hợp số của một số nguyên, nh−ng với những gì mà ta biết đến nay, nó d−ờng nh− khó hơn nhiều so với hai bài toán thử tính nguyên tố và tính hợp số. Trong lý thuyết mật mã, bài toán này th−ờng đ−ợc sử dụng với các dữ liệu n là số nguyên Blum, tức các số nguyên d−ơng có dạng tích của hai số nguyên tố lớn nào đó. Bài toán RSA (Rivest-Shamir-Adleman) : Cho số nguyên d−ơng n là tích của hai số nguyên tố lẻ khác nhau, một số nguyên d−ơng e sao cho gcd(e,φ (n)) =1, và một số nguyên c ; tìm một số nguyên m sao cho mce ≡ (mod n) . Điều kiện gcd(e,φ (n)) =1 bảo đảm cho việc với mỗi số nguyên c ∈ {0,1, ,n -1} có đúng một số m ∈ {0,1, ,n -1} sao cho mce ≡ (mod n) . Dễ thấy rằng nếu biết hai thừa số nguyên tố của n, tức là biết n =p.q thì sẽ biết φ (n) = (p -1)(q -1), và từ đó, do gcd(e,φ (n)) =1 sẽ 93
3. tìm đ−ợc d =e -1modφ (n), và do đó sẽ tìm đ−ợc m =c d modn. Nh− vậy, bài toán RSA có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Tuy rằng cho đến nay ch−a có một chứng minh nào cho việc qui dẫn ng−ợc lại nh−ng nhiều ng−ời vẫn tin rằng hai bài toán đó là t−ơng đ−ơng với nhau về độ phức tạp tính toán. Bài toán thặng d− bậc hai : Cho một số nguyên lẻ n là hợp số, và một số nguyên a ∈Jn , ⎛a⎞ tập tất cả các số a có ký hiệu Jacobi ⎜ ⎟=1. Hãy quyết định xem a có ⎝⎠⎜n⎟ là thặng d− bậc hai theo modn hay không? Trong lý thuyết mật mã, bài toán này cũng th−ờng đ−ợc xét với tr−ờng hợp n là số nguyên Blum, tức n là tích của hai số nguyên tố p và q , n =p.q. Ta chú ý rằng trong tr−ờng hợp này, nếu a ∈Jn , ⎛⎞a thì a là thặng d− bậc hai theo modn khi và chỉ khi ⎜ ⎟=1, điều kiện ⎝⎠⎜ p⎟ này có thể thử đ−ợc dễ dàng vì nó t−ơng đ−ơng với điều kiện a (p - 1)/2≡ 1 (modp). Nh− vậy, trong tr−ờng hợp này, bài toán thặng d− bậc hai có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Mặt khác, nếu không biết cách phân tích n thành thừa số nguyên tố thì cho đến nay, không có cách nào giải đ−ợc bài toán thặng d− bậc hai trong thời gian đa thức. Điều đó củng cố thêm niềm tin rằng bài toán thặng d− bậc hai và bài toán phân tích số nguyên là có độ khó t−ơng đ−ơng nhau. Bài toán tìm căn bậc hai modn : Cho một số nguyên lẻ n là hợp số Blum, và một số a ∈Qn , tức a là một thặng d− bậc hai theo modn . Hãy tìm một căn bậc hai của a theo modn, tức tìm x sao cho x 2≡ a (modn). Nếu biết phân tích n thành thừa số nguyên tố, n =p.q , thì bằng cách giải các ph−ơng trình x 2≡ a theo các modp và modq, rồi sau đó kết hợp các nghiệm của chúng lại theo định lý số d− Trung quốc ta sẽ đ−ợc nghiệm theo modn , tức là căn bậc hai của a theo modn cần tìm. Vì mỗi ph−ơng trình x 2≡ a theo modp và modq có hai nghiệm (t−ơng ứng theo modp và modq ), nên kết hợp lại ta đ−ợc bốn nghiệm, tức bốn căn bậc hai của a theo modn. Ng−ời ta đã tìm đ−ợc một số thuật toán t−ơng đối đơn giản (trong thời gian đa thức) giải ph−ơng trình x 2≡ a (modp) với p là số nguyên tố. 94
4. Nh− vậy, bài toán tìm căn bậc hai modn có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Ng−ợc lại, nếu có thuật toán  giải bài toán tìm căn bậc hai modn thì cũng có thể xây dựng một thuật toán giải bài toán phân tích số nguyên nh− sau: Chọn ngẫu nhiên một số x với gcd(x,n) =1, và tính a =x2modn. Dùng thuật toán  cho a để tìm một căn bậc hai modn của a. Gọi căn bậc hai tìm đ−ợc đó là y. Nếu y ≡ ±x (modn), thì phép thử coi nh− thất bại, và ta phải chọn tiếp một số x khác. còn nếu y ≢ ±x (modn), thì gcd(x-y, n) chắc chắn là một −ớc số không tầm th−ờng của n, cụ thể là p hay là q. Vì n có 4 căn bậc hai modn nên xác suất của thành công ở mỗi lần thử là 1/2, và do đó số trung bình (kỳ vọng toán học) các phép thử để thu đ−ợc một thừa số p hayq của n là 2, từ đó ta thu đ−ợc một thuật toán giải bài toán phân tích số nguyên (Blum) với thời gian trung bình đa thức. Tóm lại, theo một nghĩa không chặt chẽ lắm, ta có thể xem hai bài toán phân tích số nguyên và tìm căn bậc hai modn là khó t−ơng đ−ơng nhau. Bài toán lôgarit rời rạc : Cho số nguyên tố p, một phần tử nguyên thuỷ α theo modp ∗ ∗ (hay α là phần tử nguyên thuỷ của Z p ), và một phần tử β ∈ Z p .Tìm số nguyên x (0≤ x ≤ p - 2) sao cho α x ≡ β (modp). Trong mục 2.4.3 ta đã giới thiệu qua bài toán này, và biết rằng trong tr−ờng hợp chung, cho đến nay ch−a có một thuật toán nào giải bài toán này trong thời gian đa thức. Bài toán này cũng đ−ợc suy rộng cho các nhóm cyclic hữu hạn nh− sau: Bài toán lôgarit rời rạc suy rộng : Cho một nhóm cyclic hữu hạn G cấp n, một phần tử sinh (nguyên thuỷ) α của G, và một phần tử β ∈G. Tìm số nguyên x (0≤ x ≤ n - 1) sao cho α x = β. Các nhóm đ−ợc quan tâm nhiều nhất trong lý thuyết mật mã ∗ là: nhóm nhân của tr−ờng hữu hạn GF (p) - đẳng cấu với nhóm Z p F∗ m của tr−ờng Zp ,nhóm nhân 2m của tr−ờng hữu hạn GF (2 ), nhóm ∗ nhân Zan =≤{ :0 a≤n−1,gcd(a,n) =1} của tr−ờng Zn với n là hợp số, nhóm gồm các điểm trên một đ−ờng cong elliptic xác định trên một tr−ờng hữu hạn, v.v Bài toán Diffie-Hellman : Cho số nguyên tố p, một phần tử nguyên thuỷ α theo modp ∗ a b (tức phần tử sinh của Z p ), và các phần tử α mod p và α mod p . 95
5. Hãy tìm giá trị α ab mod p . Có thể chứng minh đ−ợc rằng bài toán Diffie-Hellman qui dẫn đ−ợc về bài toán lôgarit rời rạc trong thời gian đa thức. Thực vậy, giả sử có thuật toán  giải bài toán lôgarit rời rạc. Khi đó, cho một bộ dữ liệu vào của bài toán Diffie-Hellman gồm p, α ,α a mod p và α b mod p ; tr−ớc hết dùng thuật toán  cho (p, α ,α a mod p ) ta tìm đ−ợc a , và sau đó tính đ−ợc αab mod p =(αb )a mod p.Ng−ời ta cũng chứng minh đ−ợc hai bài toán lôgarit rời rạc và Diffie- Hellman là t−ơng đ−ơng về mặt tính toán trong một số tr−ờng hợp, ví dụ p -1 là B-mịn với B = O ((lnp)c ),c là hằng số. T−ơng tự nh− với bài toán lôgarit rời rạc, ta cũng có thể định nghĩa các bài toán Diffie-Hellman suy rộng cho các nhóm cyclic hữu hạn khác. Bài toán tổng tập con (hay bài toán KNAPSACK) : Cho một tập các số nguyên d−ơng {aa12, , ,an} và một số nguyên d−ơng s. Hãy xác định xem có hay không một tập con các aj mà tổng của chúng bằng s. Một cách t−ơng đ−ơng, hãy xác định n ∈{ } ≤ ≤ n) ax = s. xem có hay không các xi 0,1 (1 i sao cho ∑i=1 ii Bài toán này là một bài toán NP- đầy đủ, tức là thuộc lớp những bài toán khó mà cho đến nay ch−a tìm đ−ợc thuật toán giải chúng trong thời gian đa thức ! Bài toán giải mã đối với mã tuyến tính : Mã tuyến tính là một lớp mã truyền tin có tính chất tự sửa sai đ−ợc sử dụng trong kỹ thuật truyền tin số hoá. Không đi vào chi tiết của lớp mã này, ta có thể phát biểu trực tiếp bài toán giải mã đối với mã tuyến tính nh− sau: Cho một ma trận cấp n xm A=(aij) gồm các thành phần là 0 hoặc 1, một vectơ y =(y1,y2, ,ym) các giá trị 0 và 1, và một số nguyên d−ơng K. Hỏi: có hay không một vectơ x =(x1,x2, ,xn) gồm các số 0 hoặc 1 và có không nhiều hơn K số 1 sao cho với mọi j (1≤ j ≤ m): n ∑ xaii.(j≡ yjmod2) ? i=1 Chú ý rằng ở đây, x là vectơ thông tin, và y là vectơ mã, phép giải mã là tìm lại x khi nhận đ−ợc y, bài toán này tiếc thay lại là một bài toán khó; Berlekamp, McEliece và Tilborg năm 1978 đã chứng minh nó thuộc lớp các bài toán NP- đầy đủ ! 96
6. 4.2. Hệ mật mã khoá công khai RSA. 4.2.1. Mô tả hệ mật mã RSA. Sơ đồ chung của hệ mật mã khoá công khai đ−ợc cho bởi S = (P , C , K , E , D ) (1) trong đó P là tập ký tự bản rõ, C là tập ký tự bản mã, K là tập các khoá K , mỗi khoá K gồm có hai phần K =(K’,K''), K' là khoá công khai dành cho việc lập mật mã, còn K'' là khoá bí mật dành cho việc giải mã. Với mỗi ký tự bản rõ x∈P , thuật toán lập mã E cho ta ký tự mã t−ơng ứng y =E (K', x) ∈ C , và với ký tự mã y thuật toán giải mã D sẽ cho ta lại ký tự bản rõ x : D (K'', y) = D (K'', E (K', x)) =x. Để xây dựng một hệ mật mã khoá công khai RSA, ta chọn tr−ớc một số nguyên n =p.q là tích của hai số nguyên tố lớn, chọn một số e sao cho gcd(e, φ (n)) =1, và tính số d sao cho e.d ≡ 1(modφ (n)). Mỗi cặp K =(K’,K''), với K' =(n,e) và K'' = d sẽ là một cặp khoá của một hệ mật mã RSA cụ thể cho một ng−ời tham gia. Nh− vậy, sơ đồ chung của hệ mật mã RSA đ−ợc định nghĩa bởi danh sách (1), trong đó: P = C = Zn , trong đó n là một số nguyên Blum, tức là tích của hai số nguyên tố; K = {K =(K’,K''): K' =(n,e) và K'' = d, gcd(e, φ (n)) =1, e.d ≡ 1(modφ (n))}; E và D đ−ợc xác định bởi: E (K', x) = xe modn, với mọi x ∈P , D (K'', y) = yd modn, với mọi y ∈C . Để chứng tỏ định nghĩa trên là hợp thức, ta phải chứng minh rằng với mọi cặp khoá K =(K' ,K'' ), và mọi x ∈P , ta đều có D (K'', E (K', x)) = x . Thực vậy, do e.d ≡ 1(modφ (n)) ta có thể viết e.d = t .φ (n) +1. Nếu x nguyên tố với n , thì dùng định lý Euler (xem 2.1.3) ta có D (K'', E (K', x)) = xed≡ xxtnφφ()+1≡=tn().(xmodn) x. Nếu x không nguyên tố với n , thì do n =p.q , hoặc x chia hết cho p và nguyên tố với q, hoặc x chia hết cho q và nguyên tố với p, và φ (n) =(p -1).(q -1),trong cả hai tr−ờng hợp ta đều có xtnφ ()+1≡ xp(mod ), xtnφ ()+1≡ xq(mod ); 97
7. từ đó suy ra xtnφ ()+1≡ x(mod n), tức D (K'', E (K', x)) =x. Thí dụ: Giả sử chọn n =p.q = 2357.2551 = 6012707, ta sẽ có φ (n) = (p -1).(q -1)=2356.2550 = 6007800. Chọn e = 3674911, và tính đ−ợc d = 422191 sao cho e.d ≡ 1(modφ (n)). Một ng−ời dùng A có thể chọn khoá công khai là K' =(n =6012707, e = 3674911) và giữ khoá bí mật K'' =d =422191. Một đối tác B muốn gửi cho A một thông báo x =5234673, sẽ dùng khoá công khai để tạo bản mật mã y =xe = 52346733674911mod6012707 = 3650502. A nhận đ−ợc y, giải mã sẽ đ−ợc bản rõ x =3650502422191mod 6012707 =5234673. 4.2.2. Thực hiện hệ mật mã RSA. Để thực hiện hệ mật mã RSA cho một mạng truyền tin bảo mật, ngoài việc xây dựng các ch−ơng trình tính toán hàm E (với tham biến đầu vào là n ,e và x) và hàm D (với tham biến đầu vào là n ,d và y), ta còn phải chọn cho mỗi ng−ời tham gia một bộ (n,e,d) để tạo các khoá công khai K' và khoá bí mật K'' . Hệ mã của mỗi ng−ời tham gia chỉ có khả năng bảo mật khi n =p.q là số nguyên rất lớn (và do đó p,q cũng phải là những số nguyên tố rất lớn); rất lớn có nghĩa là p,q phải có biểu diễn thập phân cỡ hơn 100 chữ số, do đó n có cỡ hơn 200 chữ số thập phân, hay n ≥ 10200! Tính toán các số e,d , hay thực hiện các hàm E , D , đều chủ yếu là thực hiện các phép tính số học trên các số nguyên rất lớn; về vấn đề này trong mấy chục năm qua, khoa lập trình máy tính đã đề xuất nhiều ch−ơng trình máy tính làm việc rất có hiệu quả, ta có thể tham khảo để sử dụng khi thực thi các hệ mật mã RSA cũng nh− nhiều hệ mật mã khác. 4.2.3. Tính bảo mật của mật mã RSA. Bài toán thám mã (khi chỉ biết bản mã) đối với mật mã RSA là: biết khoá công khai K' =(n,e), biết bản mã y =x e modn, tìm x. Bài toán này chính là bài toán RSA đ−ợc trình bày trong mục 4.1.2. Trong mục đó ta đã chứng tỏ rằng nếu biết hai thừa số p,q của n thì dễ tìm đ−ợc x từ y, và nói chung có bằng chứng để coi rằng bài toán RSA (hay bài toán thám mã RSA) là có độ khó t−ơng đ−ơng với bài toán phân tích số nguyên (Blum) thành thừa số nguyên tố. Do đó, giữ tuyệt mật khoá bí mật d , hay giữ tuyệt mật các thừa số p,q , là có ý nghĩa rất quyết định đến việc bảo vệ tính an toàn của hệ mật mã RSA. Một mạng truyền tin bảo mật sử dụng sơ đồ các hệ mật mã RSA đ−ợc xem là an toàn, nếu tuân thủ các điều kiện cơ bản: mỗi 98
8. ng−ời tham gia phải độc lập lựa chọn các tham số n, e,d của riêng mình, chọn n cũng có nghĩa là chọn các thừa số p,q của n (n =p.q), và do có p,q nên tính đ−ợc φ (n) = (p -1).(q -1), và từ đó tìm đ−ợc e,d t−ơng đối dễ dàng; nh−ng cũng chính vì vậy mà sau khi đã chọn thì mỗi ng−ời tham gia phải giữ tuyệt đối bí mật các giá trị p,q,d , chỉ công bố khoá công khai (n,e) mà thôi. Tuy nhiên, đó là điều kiện chung, còn trong thực tế vẫn có thể còn nhiều sơ hở mà ng−ời thám mã có thể lợi dụng để tấn công vào tính bảo mật của các hệ mã RSA khó mà l−ờng tr−ớc hết đ−ợc; sau đây là một số tr−ờng hợp đơn giản đã biết mà ta cần chú ý: 1.Dùng môđuyn n chung. Giả sử có hai ng−ời tham gia A và B cùng sử dụng một môđuyn chung n trong khoá công khai của mình, chẳng hạn A chọn khoá công khai (n,e) và giữ khoá bí mật d, B chọn khoá công khai (n,a) và giữ khoá bí mật b. Một ng−ời tham gia thứ ba C gửi một văn bản cần bảo mật x đến cả A và B thì dùng các khoá công khai nói trên để gửi đến A bản mật mã y =x emodn và gửi đến B bản mật mã z =xa mod n . Ta sẽ chứng tỏ rằng một ng−ời thám mã O có thể dựa vào những thông tin n,e,a,y,z trên đ−ờng công khai mà phát hiện ra bản rõ x nh− sau: a. Tính c = e -1moda, b. Sau đó tính h = (ce -1)/a , c. Và ta đ−ợc x = yc (z h)-1 modn. Thực vậy, theo định nghĩa trên, ce -1 chia hết cho a, và tiếp theo ta có: yc (z h)-1modn = x ec . (xa(1ce−−)/a ) 1mod nx= ce.(xce−1)−1mod n= x. Nh− vậy, trong tr−ờng hợp này việc truyền tin bảo mật không còn an toàn nữa. Vì vậy, ta cần nhớ khi dùng các hệ RSA để tổ chức mạng truyền tin bảo mật, cần tránh dùng môđuyn n chung cho các ng−ời tham gia khác nhau! 2. Dùng số mũ lập mã e bé. Để cho việc tính toán hàm lập mã đ−ợc hiệu quả, ta dễ có xu h−ớng chọn số mũ e của hàm lập mã là một số nguyên bé, chẳng hạn e =3. Tuy nhiên, nếu trong một mạng truyền tin bảo mật dùng các hệ mật mã RSA, nếu có nhiều ng−ời cùng chọn số mũ lập mã e bé giống nhau thì sẽ có nguy cơ bị tấn công bởi việc thám mã nh− sau : Giả sử có ba ng−ời tham gia chọn ba khoá công khai là (n1, e), (n2, e), (n3, e) với cùng số mũ e =3. Một ng−ời tham gia A muốn gửi một thông báo x cho cả ba ng−ời 3 đó, và để bảo mật, gửi bản mã ci = x modni cho ng−ời thứ i. Ba môđuyn ni là khác nhau, và có phần chắc là từng cặp nguyên tố với nhau. Một ng−ời thám mã có thể dùng định lý số d− Trung quốc để tìm một số m (0≤ m ≤ n1n2n3) thoả mãn 99
9. ⎧mc≡ 11mod n ⎪ ⎨mc≡ 22mod n ⎪ ⎩mc≡ 33mod n 3 3 Vì x ≤ ni , nên x ≤ n1n2n3 , do đó ắt có m =x . Vậy là ta đã đ−a đ−ợc bài toán tìm căn bậc ba theo nghĩa đồng d− modni về bài toán tìm căn bậc ba theo nghĩa số học thông th−ờng: tìm căn bậc ba của m ta đ−ợc x, tức đ−ợc bản rõ! Với những lý do khác, ng−ời ta đã có những bằng chứng để chứng tỏ rằng hệ RSA cũng không bảo đảm an toàn nếu ta dùng các khoá có số mũ giải mã d là số nguyên bé, dù rằng khi đó thuật toán giải mã có làm việc hiệu quả hơn. Vì thế, khi sử dụng các hệ mật mã RSA, để bảo đảm an toàn ta nên chọn các số mũ e và d là những số nguyên lớn, có kích cỡ lớn gần nh− bản thân số n. 3. Lợi dụng tính nhân của hàm lập mã. Ta chú ý rằng hàm lập mã f (x) = x emodn có tính nhân (multiplicative property), nghĩa là f (x.y) = f (x).f (y). Dựa vào tính chất đó, ta thấy rằng nếu c là mật mã của bản rõ x, thì cc= .mue odn sẽ là mật mã của bản rõ xu. Do đó, khi lấy đ−ợc bản mật mã c , để phát hiện bản rõ x ng−ời thám mã có thể chọn ngẫu nhiên một số u rồi tạo ra bản mã c ,và nếu ng−ời thám mã có khả năng thám mã theo kiểu ô có bản mã đ−ợc chọn ằ (xem 1.5.1), tức có khả năng với c đ−ợc chọn tìm ra bản rõ t−ơng ứng là x =xu ,thì bản rõ gốc cần phát hiện sẽ là x = x.mu−1 odn. Tất nhiên, khả năng ng−ời thám mã có năng lực giải quyết bài toán thám mã theo kiểu có bản mã đ−ợc chọn là rất hiếm, nh−ng dầu sao đấy cũng là một tr−ờng hợp mà vấn đề bảo mật dễ bị tấn công, ta không thể không tính đến để tìm cách tránh! 4. Tấn công bằng cách lặp phép mã. Ta cũng chú ý rằng hàm e lập mã f (x) = x modn là một phép hoán vị trên tập Zn ={0,1, ,n -1}, do đó với mọi c ∈Zn nếu ta thực hiện lặp phép lập mã để đ−ợc ee2 ei cc01==,ccmod n,c2=cmod n, ,ci =cmod n, ek ắt sẽ tìm đ−ợc số k ≥ 1 sao cho cck = mod n=c. Nếu c là bản mã của một bản rõ x nào đó, c =x emodn, thì ng−ời thám mã có thể xuất phát từ c thực hiện lặp phép lập mã nh− trên sẽ tìm đ−ợc số k ≥ 1 bé nhất sao cho ck =c . Và khi đó ta sẽ có số hạng tr−ớc đó ck -1=x, là bản rõ cần phát hiện. Thuật toán về hình thức là khá đơn giản, nh−ng hiệu quả thực hiện không đáng hy vọng lắm, vì số phép lặp cần thực hiện nói chung có thể là rất lớn, cỡ bằng số các phép hoán vị trên Zn , tức là bằng n !, với số n có khoảng 200 chữ số thập phân. Trên thực tế, phỏng theo thuật toán nói trên ta có thể dễ dàng có một thuật toán phân tích n thành thừa số nguyên tố, mà một thuật 100
10. toán nh− vậy làm việc có hiệu quả thiết thực, nh− đã trình bày trong một phần trên, là ch−a có! Vì vậy, nguy cơ bị thám mã bằng thuật toán đơn giản nói trên đối với tính an toàn của hệ mật mã RSA là không đáng ngại lắm. 5. Về khả năng che giấu của bản mật mã. Mật mã, sở dĩ nó giữ đ−ợc bí mật, là do khả năng che giấu thông tin của nó, tức là biết bản mã y khó lòng tìm đ−ợc thông tin nào để phát hiện ra bản rõ x. Một cách thô thiển, ta nói bản rõ x là không che giấu đ−ợc qua e phép lập mật mã RSA eK (x) =x modn, nếu eK (x) =x. Nói cách khác, x là không che giấu đ−ợc nếu bản mã của x cũng chính là x. Tiếc rằng với bất kỳ hệ mật mã RSA nào cũng có những bản rõ không che giấu đ−ợc, đó là những bản rõ x = -1, 0, 1 modn (vì số mũ e luôn luôn là số lẻ). Ng−ời ta chứng minh đ−ợc rằng nếu n =p.q, thì số các bản rõ x ∈Zn không che giấu đ−ợc là bằng (1+gcd(e -1, p -1)).(1+gcd(e -1, q -1)). Vì e -1, p -1, q -1 là các số chẵn, nên số đó ít nhất là 9, nên mỗi hệ RSA có ít nhất 9 bản rõ không che giấu đ−ợc. Tuy nhiên, th−ờng n, và do đó cả p và q, đều rất lớn, nên tỷ lệ các bản rõ không che giấu đ−ợc nói chung là bé không đáng kể, và do đó khả năng gặp các bản rõ không che giấu đ−ợc không tạo nên một nguy cơ đáng kể nào đối với việc dùng các hệ mật mã RSA. 4.3. Hệ mật mã khoá công khai Rabin. 4.3.1. Mô tả hệ mật mã Rabin. Sơ đồ hệ mật mã khoá công khai Rabin đ−ợc cho bởi S = (P , C , K , E , D ), trong đó: P =C = Zn , trong đó n là một số nguyên Blum, n =p.q, với p và q là hai số nguyên tố có tính chất p ≡ 3(mod4), q ≡ 3(mod4), K = {K = (K', K'') : K' =(n,B), K'' =(p,q), 0≤B ≤ n –1}, các thuật toán E và D đ−ợc xác định bởi E (K' ,x) = x (x +B) modn , BB2 D (K'',y) = +−ynmod . 42 (ký hiệu căn bậc hai sẽ đ−ợc giải thích sau). 101
11. Trong một mạng truyền tin bảo mật với sơ đồ mật mã Rabin, mỗi ng−ời tham gia chọn cho mình các yếu tố n,B,p,q để lập nên khoá công khai và khoá bí mật của mình. Ta chú ý rằng với mỗi bộ khoá K, các thuật toán eK′ = E (K' ,.) và dK′′ = D (K'',.) không lập thành một cặp song ánh, cụ thể là eK′ không phải là một đơn ánh, vì nếu w là một căn bậc hai của 1 theo B B modn thì e (w(x + ) - ) = e (x), mà ta có đến 4 căn bậc hai của K′ 2 2 K′ 1 theo modn ,tức là ta có 4 giá trị khác nhau của đối số x cho cùng một giá trị eK′ (x). Bây giờ nói đến thuật toán giải mã dK′′ = D (K'',.). Đặt C = 2 B /4 +y, ta có dK′′ (y) = CB− /2modn, do đó để có dK′′ (y), ta cần tính C modn, tức cần giải ph−ơng trình z 2≡ C modn . Ph−ơng trình đó t−ơng đ−ơng với hệ thống gồm hai ph−ơng trình sau đây: ⎪⎧zC2 ≡ mod p, (2) ⎨ 2 ⎩⎪zC≡ mod q. p−1 q−1 Vì p và q là các số nguyên tố nên ta có Cp2 ≡1mod ,Cq2 ≡1mod . p+1q+1 Theo giả thiết, p ≡ 3(mod4) và q ≡ 3(mod4), nên va` là các 44 số nguyên; và ta có pq++11 (±≡CC44)22(mod p), (±C) ≡C(mod q). Do đó,ph−ơng trình z 2≡ C modn , hay hệ ph−ơng trình (2), có 4 nghiệm theo modn , t−ơng ứng với 4 hệ ph−ơng trình sau đây : ⎪⎪⎧⎧zC≡≡(1pp++)/4(mod p) zC(1)/4(mod p) ⎨⎨(1qq++)/4 (1)/4 ⎩⎩⎪⎪zC≡≡(mod q) z−C (mod q) ⎪⎪⎧⎧zC≡− (1pp++)/4(mod p) z≡−C(1)/4(mod p) ⎨⎨(1qq++)/4 (1)/4 ⎩⎩⎪⎪zC≡≡(mod q) z−C (mod q) Cả 4 nghiệm của 4 hệ ph−ơng trình đó theo modn đều đ−ợc viết chung d−ới một ký hiệu là C modn, và vì vậy thuật toán giải mã dK′′ (y) thực tế sẽ cho ta 4 giá trị khác nhau theo modn mà bản rõ là một trong 4 giá trị đó. Việc chọn giá trị nào trong 4 giá trị tìm đ−ợc làm bản rõ là tuỳ thuộc vào những đặc tr−ng khác của bản rõ mà ng−ời giải mã nhận biết (thí dụ bản rõ d−ới dạng số phải có biểu diễn nhị phân là mã của một văn bản tiếng Anh thông th−ờng). 102
12. Thí dụ : Giả sử n =77 = 7.11, B =9 (ở đây p =7, q =11). Ta có 2 eK′ (x) = x + 9x mod77, dK′′ (y) = 1+−y 43mod 77 , vì 2-1=39mod77, 9.2-1 =9.39 =43mod77, B 2=4mod77, B 2/4 =1mod 77. 2 Với x =44 ta có eK′ (x) = 44 +9.44 =2332 =22mod77, bản mã t−ơng ứng với x là y = 22. Bây giờ giải mã với bản mã y =22, bằng thủ tục nói trên ta có thể tìm đ−ợc 4 giá trị của 11+=y +22=23 theo mod77 là 10,67,32,45, từ đó 4 giá trị có thể có của dK′′ (y) là dK′′ (y) = 44, 24, 66, 2. Bản rõ nằm trong 4 giá trị đó, trong tr−ờng hợp này là 44. 4.3.2. Tính an toàn của hệ mật mã Rabin. Trong định nghĩa của hệ mật mã Rabin, khoá công khai là (n,B), khoá bí mật là (p,q) tức là cặp thừa số nguyên tố của n . Nh− vậy, tính an toàn của hệ mật mã nằm ở việc giữ bí mật các thừa số p và q. Định nghĩa của phép giải mã cũng cho ta thấy rằng yếu tố có ý nghĩa quyết định trong phép giải mã là việc tính căn bậc hai của một số theo modn. Trong mục 4.1.2 bài toán tìm căn bậc hai theo modn (với n là hợp số Blum) đã đ−ợc chứng tỏ là có độ khó t−ơng đ−ơng với bài toán phâ n tích n thành thừa số nguyên tố. Vì vậy, bài toán giải mã đối với hệ mật mã Rabin, cũng là bài toán giữ bí mật khoá bí mật (p,q), và bài toán phân tích số nguyên thành thừa số nguyên tố là có độ khó t−ơng đ−ơng nhau. Và đó cũng là yếu tố bảo đảm tính an toàn của hệ mật mã Rabin ! 4.4. Hệ mật mã khoá công khai ElGamal. 4.4.1. Mô tả hệ mật mã ElGamal. Hệ mật mã ElGamal đ−ợc T. ElGamal đề xuất năm 1985, dựa vào độ phức tạp của bài toán tính lôgarit rời rạc, và sau đó đã nhanh chóng đ−ợc sử dụng rộng rãi không những trong vấn đề bảo mật truyền tin mà còn trong các vấn đề xác nhận và chữ ký điện tử. Sơ đồ hệ mật mã khoá công khai ElGamal đ−ợc cho bởi S = (P , C , K , E , D ), ∗ ∗ ∗ trong đó: P = Z p , C = Z p ì Z p , với p là một số nguyên tố; K ={K = (K', K'') : K' =(p,α ,β) , K'' = a , β ≡ α a modp}, 103
13. ∗ ở đây α là một phần tử nguyên thuỷ theo modp, tức của Z p . Các thuật toán lập mã eK′ = E (K' ,.) và giải mã dK′′ = D (K'',.) ∗ đ−ợc xác định nh− sau: Với mỗi x∈P = Z p , để lập mật mã cho x tr−ớc hết ta chọn thêm một số ngẫu nhiên k ∈ Zp -1 rồi tính: k ⎪⎧yp1 =α mod , e (x,k ) = (y , y ), với K′ 1 2 ⎨ k ⎩⎪yx2 = .mβ odp. Với mọi số ngẫu nhiên k bất kỳ, ta đều xem eK′ (x,k ) là mật mã của x. Và thuật toán giải mã đ−ợc xác định bởi a −1 dK′′ (y1, y 2) = yy21.( ) mod p. Các phép lập mật mã và giải mã đ−ợc xác định nh− vậy là ∗ hợp thức, vì ta có với mọi x∈P = Z p và mọi k ∈ Zp -1 : kk.1a−−kk dK′′ ( eK′ (x,k )) = x βα( )modpx= .β.βmodpx= . Ta chú ý rằng trong một mạng truyền thông bảo mật với việc dùng sơ đồ mật mã ElGamal, mỗi ng−ời tham gia tự chọn cho mình các tham số p,α, a, rồi tính β, sau đó lập và công bố khoá công khai K' =(p,α ,β), nh−ng phải giữ tuyệt mật khoá bí mật K'' = a. Bài toán biết khoá công khai tìm ra khoá bí mật chính là bài toán tính lôgarit rời rạc đ−ợc kể đến trong mục 4.1.2, một bài toán khó cho đến nay ch−a có một thuật toán nào làm việc trong thời gian đa thức giải đ−ợc nó. Thí dụ : Chọn p = 2579, α =2, a =765, ta tính đ−ợc β = 2765 = 949 mod2579. Ta có khoá công khai (2579, 2, 949) và khoá bí mật 765. Giả sử để lập mật mã cho x =1299, ta chọn ngẫu nhiên k =853, sẽ có 853 853 eK′ (1299, 853) = (2 , 1299. 949 )mod2579 = (453, 2396). Và giải mã ta đ−ợc lại 765 -1 dK′′ (453, 2396) = 2396. (453 ) mod2579 = 1299. 4.4.2. Tính an toàn của hệ mật mã ElGamal. Nh− đã trình bày ở trên, nếu ta xem tính an toàn của hệ mật mã ElGamal là ở việc giữ tuyệt mật khoá bí mật K'', thì ta có thể yên tâm vì bài toán phát hiện khoá bí mật có độ khó t−ơng đ−ơng với bài toán tính lôgarit rời rạc, mà bài toán này thì nh− ở các mục 4.1.2 và 2.4.3 đã chứng tỏ, cho đến nay ch−a có một thuật toán nào làm việc trong thời gian đa thức giải đ−ợc nó. Có một điều cảnh báo là nên chú ý chọn môđuyn p là số nguyên tố sao cho p -1 có ít nhất một −ớc số nguyên tố lớn (xem 2.4.3). Điều đó là thực hiện đ−ợc 104
14. nếu số nguuyên tố p đ−ợc chọn là số nguyên tố Sophie Germain (tức có dạng 2q +1, với q cũng là số nguyên tố lớn). Ngoài ra, còn có khả năng khoá bí mật K'' = a bị lộ do cẩu thả trong việc sử dụng số ngẫu nhiên k, đặc biệt là khi để lộ số k đ−ợc dùng. Thực vậy, nếu để lộ số k, thì khoá bí mật a đ−ợc tính ra ngay theo công thức sau đây: −1 ax= ( −−ky21)ymod( p1). Nh− vậy,một ng−ời thám mã có khả năng tấn công theo kiểu “biết cả bản rõ” (xem 1.5.1) có thể phát hiện ra khoá a nếu biết k . Một tr−ờng hợp khác làm mất tính an toàn của hệ mật mã ElGamal là việc dùng cùng một số k cho nhiều lần lập mật mã. Thực vậy, giả sử dùng cùng một số ngẫu nhiên k cho hai lần lập mã, một lần cho x1 , một lần cho x2 , và đ−ợc các bản mã t−ơng ứng (y1,y2) và (z1,z2). Vì cùng dùng một số k nên y1=z1. Và do đó theo công thức lập mã ta có z2/y2 = x2/x1, tức là x2 = x1.z2/y2. Nh− vậy, một ng−ời thám mã, một lần “biết cả bản rõ” dễ dàng phát hiện đ−ợc bản rõ trong các lần sau. 4.4.3. Các hệ mật mã t−ơng tự ElGamal. Hệ mật mã ElGamal đ−ợc xây dựng dựa trên các yếu tố : ∗ ∗ một nhóm hữu hạn cyclic ( Z p ), một phần tử nguyên thuỷ (α ∈ Z p ) sao cho bài toán tính lôgarit rời rạc (tính a = logαβ , tức cho β tìm a sao cho β = α a modp) là rất khó thực hiện. Vì vậy, nếu có đủ các yếu tố đó thì ta có thể xây dựng các hệ mật mã t−ơng tự ElGamal. Nh− vậy, sơ đồ của một hệ mật mã t−ơng tự ElGamal đ−ợc cho bởi S = (P , C , K , E , D ), trong đó: P =G, C =GìG, với G là một nhóm cyclic hữu hạn; K ={K = (K', K'') : K' =(G,α ,β) , K'' = a , β = α a }, ở đây α là một phần tử nguyên thuỷ của nhóm G. Các thuật toán lập mã eK′ = E (K' ,.) và giải mã dK′′ = D (K'',.) đ−ợc xác định nh− sau: Với mỗi x∈P =G, để lập mật mã cho x tr−ớc hết ta chọn thêm một số ngẫu nhiên k (0 ≤≤kG) rồi tính: k ⎪⎧y1 =α e (x,k ) = (y , y ), với K′ 1 2 ⎨ k ⎩⎪yx2 = .β Với mọi số ngẫu nhiên k bất kỳ, ta đều xem eK′ (x,k ) là mật mã của x. Và thuật toán giải mã đ−ợc xác định bởi a −1 dK′′ (y1, y 2) = yy21.( ) mod p. Phép nhân trong các biểu thức nói trên đều là phép nhân của G. 105
15. Có hai lớp nhóm th−ờng đ−ợc sử dụng để xây dựng các hệ mật mã t−ơng tự ElGamal là nhóm nhân của tr−ờng Galois GF(pn) và nhóm cộng của một đ−ờng cong elliptic xác định trên một tr−ờng hữu hạn. 1. Nhóm nhân của tr−ờng Galois GF(pn) : Tr−ờng Galois n GF(p ) là tr−ờng của các đa thức với hệ số trong Zp lấy theo môđuyn là một đa thức bậc n bất khả qui; với phép cộng và phép nhân là phép cộng và phép nhân đa thức theo môđuyn đó. Tr−ờng có pn phần tử, có thể xem mỗi phần tử là một đa thức bậc n -1 với hệ số thuộc Zp = {0,1,2, ,p -1}, thậm chí là một vectơ n chiều mà các thành phần là các hệ số của đa thức đó. Tập tất cả các đa thức khác 0 lập thành nhóm nhân của tr−ờng GF (pn),và ng−ời ta chứng minh đ−ợc rằng nhóm nhân đó là cyclic. Nh− vậy, nhóm G = GF (pn){0} là nhóm cyclic cấp pn-1. ta có thể chọn một phần tử nguyên thuỷ của nhóm đó, và thiết lập bài toán lôgarit rời rạc t−ơng ứng, từ đó xây dựng đ−ợc hệ mật mã t−ơng tự ElGamal. 2. Nhóm cộng của đ−ờng cong elliptic : Giả sử p là một số 2 3 nguyên tố > 3. Đ−ờng cong elliptic y =x +a.x+b trên Zp , trong đó 3 2 a,b ∈Zp là các hằng số thoả mãn 4a +27b ≢ 0 (modp), đ−ợc định nghĩa là tập hợp tất cả các điểm (x,y)∈ Zp ì Zp thoả mãn ph−ơng trình y2≡ x3+a.x+b (modp), cùng với một phần tử đặc biệt mà ta ký hiệu là O . Tập hợp đó đ−ợc ký hiệu là E. Trên tập E ta xác định một phép cộng nh− sau : Giả sử P =(x1, y1) và Q = (x2, y2) là hai điểm của E. Nếu x1=x2 và y1= -y2 thì ta định nghĩa P +Q =O ; nếu không thì P +Q = (x3, y3), trong đó 2 x3 = λ -x1-x2 , y3 = λ (x1-x3) - y1 , với ⎪⎧()yy21− /(x2−≠x1),khiPQ; λ = ⎨ 2 ⎩⎪(3x11+ ay) / 2 , khiP= Q. Ngoài ra, ta định nghĩa thêm : P +O = O+P = P. Tập E với phép toán cộng đó lập thành một nhóm. Nếu ⎢E ⎢=q là số nguyên tố thì nhóm cộng đó là nhóm cyclic, và mọi phần tử khác không (≠O ) đều là phần tử nguyên thuỷ. Ta nhớ rằng trong tr−ờng hợp này, phần tử nghịch đảo là phần tử đối, phép nâng lên luỹ thừa n là phép nhân với số n , phép lôgarit t−ơng ứng với một kiểu phép chia. Ta có thể xuất phát từ nhóm E này để xây dựng hệ mật mã t−ơng tự ElGamal. 106
16. 4.5. Các hệ mật mã dựa trên các bài toán NP-đầy đủ. 4.5.1. Nguyên tắc chung. Nh− đã giới thiệu trong ch−ơng II, các bài toán NP-đầy đủ là các bài toán mà cho đến nay ch−a tìm đ−ợc một thuật toán với độ phức tạp tính toán đa thức nào để giải chúng. Và tính ô khóằ của các bài toán đó lại đ−ợc bảo đảm bằng sự kiện là chỉ cần có một thuật toán với độ phức tạp đa thức giải một bài toán NP-đầy đủ nào đó thì lập tức mọi bài toán NP-đầy đủ đều giải đ−ợc trong thời gian đa thức. Đối với một số bài toán NP-đầy đủ, tuy không có thuật toán với độ phức tạp đa thức để giải đối với mọi dữ liệu của bài toán, nh−ng có thể có một lớp các dữ liệu mà đối với chúng có thuật toán để giải với thời gian chấp nhận đ−ợc. Với những bài toán nh− vậy ta có thể sử dụng để xây dựng các hệ mật mã khoá công khai với nguyên tắc chung nh− sau : Hệ mật mã sẽ có phép giải mã t−ơng đ−ơng với việc tìm lời giải cho bài toán NP-đầy đủ đó; tuy nhiên có một thủ tục để biến một dữ liệu nói chung của bài toán NP-đầy đủ đó thành một dữ liệu thuộc lớp đặc biệt mà đối với nó có thể giải đ−ợc bởi một thuật toán với độ phức tạp thời gian chấp nhận đ−ợc. Nh− vậy, ta đã biến đ−ợc phép lập mã thành một hàm ô cửa sập một phía ằ, và đó là cơ sở để xây dựng hệ mật mã khoá công khai t−ơng ứng. Ta sẽ xét sau đây hai tr−ờng hợp xây dựng đ−ợc các hệ mật mã khoá công khai theo cách nh− vậy : một là hệ mật mã Merkle- Hellman dựa trên bài toán sắp ba lô (hay bài toán tổng tập con), và hai là hệ mật mã Mc-Eliece dựa trên bài toán giải mã tuyến tính tự sửa sai. 4.5.2. Hệ mật mã Merkle-Hellman. Bài toán sắp ba lô (tức bài toán KNAPSACK, cũng đ−ợc gọi là bài toán tổng tập con) đ−ợc đặt ra nh− sau: Cho một tập các số nguyên d−ơng {aa12, , ,an} và một số nguyên d−ơng s. Hãy xác định xem có hay không một tập con các aj mà tổng của chúng bằng s. Một cách t−ơng đ−ơng, hãy xác định xem có hay không các xi n ∈{ } ≤ ≤ n) ax = s. 0,1 (1 i sao cho ∑i=1 ii 107
17. Bài toán này là NP-đầy đủ, tuy nhiên nếu ta hạn chế bài toán trên các dữ liệu I =({aa12, , ,an} ,T ), trong đó {aa12, , ,an} là dãy siêu tăng, tức là dãy thoả mãn điều kiện j−1 ∀=jn2,3, , : aji>∑a, i=1 thì việc tìm trả lời là khá dễ dàng, chẳng hạn có thể bằng thuật toán đơn giản d−ới đây: 1. for i =n downto 1 do if T > ai then T = T – ai , xi = 1, else xi = 0 n 2. if ∑ xii.a= T then X = (x1, , xn ) is the solution of problem, i=1 else there is no solution. Bây giờ, để chuẩn bị xây dựng một sơ đồ mật mã Merkle-Hellman, ta chọn tr−ớc một số nguyên d−ơng n và một số nguyên tố p đủ lớn. Với mỗi ng−ời tham gia sẽ đ−ợc chọn một bộ khoá K = (K', K''), trong đó khoá bí mật K'' = (A, p, a) gồm một dãy siêu tăng A= n {aa12, , ,an} thoả mãn ∑ ai < p, và một số a, 1< a < p ; khoá công i=1 khai K' = {b1, ,bn} với bi = a.ai modp. Sơ đồ hệ mật mã Merkle-Hellman đ−ợc định nghĩa bởi S = (P , C , K , E , D ), trong đó P = {0,1}n , C ={0,1, ,n(p -1)}, K là tập các bộ khoá K = (K', K'') nh− đ−ợc xây dựng ở trên. Các thuật toán lập mật mã và giải mã đ−ợc xác định bởi: Với mọi x = (x1, , xn ) ∈ P thuật toán lập mã cho ta n E (K', x) = ∑ xi.bi ; i=1 và với mọi y∈C , ta tính z =a-1.y modp, rồi sau đó giải bài toán sắp balô đối với dữ liệu I =({aa12, , ,an} ,z ) ta sẽ đ−ợc lời giải (x1, , xn ) , lời giải đó là giá trị của D (K'', y). Thí dụ: Chọn n =6, khoá bí mật có p = 737, A={12, 17, 33, 74, 157, 316}, a =635. Tính đ−ợc khoá công khai là {250, 477, 319, 559, 200, 196}. Với bản rõ x = 101101 ta có bản mã t−ơng ứng là y = 1324. Để giải mã, tr−ớc hết tính z = a-1.y modp = 635-1.1324 mod737 = 435, sau đó giải bài toán sắp balô với dãy siêu tăng A và z ta đ−ợc 435 = 12 + 33 + 74 + 316, tức đ−ợc lời giải x = (1,0,1,1,0,1). 108
18. Hệ mật mã Merkle-Hellman đ−ợc đề xuất khá sớm, từ năm 1978, đến năm 1985 Shamir tìm đ−ợc một ph−ơng pháp thám mã trong thời gian đa thức dựa vào một thuật toán của Lenstra giải bài toán qui hoạch động. Tuy nhiên, sau đó, vào năm 1988, Chor và Rivest có đ−a ra một cách khác xây dựng hệ mật mã cũng dựa vào bài toán sắp balô, cho đến nay vẫn giữ đ−ợc an toàn. 4.5.3. Hệ mật mã McEliece. Hệ mật mã McEliece đ−ợc xây dựng dựa vào tính NP-đầy đủ của bài toán giải mã tuyến tính tự sửa sai (trong lý thuyết truyền tin). Bài toán đ−ợc đặt ra nh− sau: giả sử nguồn tin là tập các từ k bit nhị phân, tức tập hợp {0,1}k, đ−ợc truyền đi trên một kênh có nhiễu, tức là nếu truyền trực tiếp các dãy từ k bit thì thông tin mà ta nhận đ−ợc có thể bị sai lệch và ta không nhận đ−ợc đúng thông tin đ−ợc truyền đi. Để khắc phục những sai lệch đó ng−ời ta tìm cách mã hoá nguồn tin gốc bằng cách thêm cho mỗi từ k bit mang thông tin một số bit dùng để tự hiệu chỉnh, tức là thực hiện một phép mã hoá biến mỗi từ k bit ban đầu thành một từ n bit, với n > k, đ−ợc gọi là từ mã. Phép mã hoá tuyến tính là phép mã hoá đ−ợc thực hiện bằng cách nhân từ k bit ban đầu x với một ma trận G cấp kìn để đ−ợc từ mã n bit y, y =x.G (các phép toán cộng và nhân đ−ợc thực hiện theo mod2). Ta định nghĩa khoảng cách Hamming giữa hai từ mã n bit là số các vị trí mà tại đó hai từ mã có giá trị khác nhau; khoảng cách d của hệ mã là khoảng cách Hamming bé nhất giữa hai từ mã bất kỳ. Nh− vậy, một hệ mã tuyến tính đ−ợc xác định bởi một ma trận G (gọi là ma trận sinh), và đ−ợc đặc tr−ng bởi ba số [n,k,d ]. Nếu d = 2t +1, thì hệ mã có khả năng tự sửa sai đến t sai ngẫu nhiên nhiễm phải do nhiễu của kênh truyền. Tuy nhiên, việc tự sửa sai (tức là khi nhận đ−ợc từ mã có thể có đến t sai ta tìm lại đ−ợc đúng từ k bit thông tin ban đầu) của các hệ mã tuyến tính nh− vậy nói chung khá phức tạp, và bài toán giải mã tuyến tính tự sửa sai đã đ−ợc chứng minh là một bài toán NP-khó, tức cho đến nay ch−a biết có thuật toán nào làm việc trong thời gian đa thức giải đ−ợc nó. Mặc dầu vậy, ng−ời ta đã tìm đ−ợc một số lớp riêng các hệ mã tuyến tính mà đối với chúng có thể xây dựng đ−ợc những thuật toán giải mã tự sửa sai làm việc có hiệu quả, các hệ mã Goppa là một lớp nh− vậy. Hệ mã Goppa là một loại hệ mã tuyến tính có các đặc tr−ng n = 2m, d =2t +1, k =n -mt , có ma trận sinh G cấp kìn đ−ợc xây dựng dựa trên một số tính chất đại số của tr−ờng GF(2n)-mà ở đây ta không đi vào các chi tiết. Để có một hệ mật mã McEliece, tr−ớc hết ta chọn một hệ mã Goppa với ma trận sinh G và các đặc tr−ng trên, sau đó dùng một 109
19. ma trận S khả nghịch cấp kìk trên Z2 và một ma trận hoán vị P cấp n ìn (cũng có các phần tử trong Z2) để biến hệ mã Goppa với ma trận sinh G thành một hệ mã tuyến tính “phổ biến” với ma trận sinh G* =SGP; vậy là đã biến hệ mã Goppa có thuật toán giải mã hiệu quả thành một hệ mã tuyến tính nói chung mà ta chỉ biết việc giải mã tự sửa sai đối với nó là NP-khó. Hệ mật mã mà ta xây dựng sẽ có thuật toán giải mã là “dễ” đối với ng−ời trong cuộc nh− giải mã Goppa, và là “khó” đối với ng−ời ngoài nh− giải mã tuyến tính nói chung! Nh− vậy, một hệ mật mã khoá công khai McEliece đ−ợc xác định bởi S = (P , C , K , E , D ), trong đó P ={0,1}k, C = {0,1}n , K là tập hợp các bộ khoá K = (K', K''), với khoá bí mật K'' = (G,S,P ) gồm một ma trận sinh G của một hệ mã Goppa, một ma trận khả nghịch S cấp kìk trên Z2 và một ma trận hoán vị P cấp n ìn ; khoá công khai K' = G* là ma trận “đã đ−ợc biến đổi” nói trên. Thuật toán lập mật mã E (K',.): P →C đ−ợc xác định bởi E (K', x) = x. G* + e , trong đó e ∈ {0,1}n là một vectơ ngẫu nhiên có trọng số t , tức có t thành phần là 1. Thuật toán giải mã D (K'',.) đ−ợc thực hiện theo ba b−ớc nh− sau với mọi y ∈C = {0,1}n : –1 1. Tính y1 = y.P , 2. Giải mã Goppa đối với y1, giả sử đ−ợc x1. -1 3. Tính D (K'', y) = x1. S . Dễ thử lại rằng các thuật toán lập mật mã và giải mã xác định nh− trên là hợp thức, vì với mọi x ∈ P ={0,1}k, ta đều có D (K'', E (K', x)) = x , Đẳng thức đó đúng với mọi vectơ e bất kỳ có trọng số ≤ t . Hệ mật mã này cũng t−ơng tự nh− hệ mật mã ElGamal ở chỗ khi lập mật mã ta có thể chọn thêm cho dữ liệu vào một yếu tố ngẫu nhiên; về sau ta sẽ gọi những hệ mật mã nh− vậy là hệ mật mã xác suất. Yếu tố chủ yếu bảo đảm tính an toàn của các hệ mật mã McEliece là ở chỗ từ khoá công khai G* khó phát hiện ra khoá bí mật (G,S,P ) và ở tính NP-khó của bài toán giải mã tuyến tính tự sửa sai nói chung. Cũng cần nhớ rằng độ an toàn còn phụ thuộc vào việc chọn các tham số k,n,t đủ lớn; theo gợi ý của các nghiên cứu thực nghiệm thì đủ lớn có nghĩa là n ≈ 1024, k ≈ 644, t ≈ 38. Với những đòi hỏi đó thì kích cỡ của các ma trận G, S, P và G* sẽ quá 110
20. lớn, khá bất tiện cho việc thực thi trong thực tế, vì vậy mà các hệ mật mã McEliece ch−a đ−ợc sử dụng phổ biến lắm. 4.6. Các hệ mật mã xác suất khoá công khai. 4.6.1. Đặt vấn đề và định nghĩa. Mật mã xác suất là một ý t−ởng đ−ợc đề xuất bởi Goldwasser và Micali từ năm 1984, xuất phát từ yêu cầu giải quyết một vấn đề sau đây: Giả thiết ta có một hệ mật mã khoá công khai, và ta muốn lập mật mã cho bản rõ chỉ gồm một bit. Điều đó th−ờng gặp khi ta muốn bí mật truyền đi một thông tin chỉ có nội dung là có hoặc không, tức là một thông tin đặc biệt quan trọng nh−ng chỉ gồm một bit. Nếu ta dùng một hệ mật mã khoá công khai thông th−ờng, thì bản mật mã đ−ợc truyền đi sẽ là eK′ (0) hoặc eK′ (1), một ng−ời thám mã có thể không biết cách giải mã, nh−ng lại hoàn toàn có thể tính tr−ớc các giá trị eK′ (0) và eK′ (1), và khi lấy đ−ợc bản mã truyền đi trên kênh truyền tin công cộng, chỉ cần so sánh bản mã nhận đ−ợc đó với hai bản eK′ (0) và eK′ (1) đã đ−ợc tính sẵn là đủ biết đ−ợc thông tin mật đ−ợc truyền đi là 0 hay là 1. Các hệ mật mã khoá công khai sở dĩ có đ−ợc tính bảo mật là vì từ thông tin về bản mã khó lòng khai thác đ−ợc thông tin gì về bản rõ, nh−ng rõ ràng điều đó không còn đ−ợc bảo đảm nếu số các bản rõ là rất ít, chẳng hạn nh− khi các bản rõ có độ dài cực ngắn, hay nh− tr−ờng hợp trên, số các bản rõ chỉ là hai, cụ thể là 0 và 1. Mục đích của việc xây dựng mật mã xác suất là để bảo đảm không một thông tin nào về bản rõ có thể khai thác đ−ợc (trong thời gian đa thức) từ bản mã; điều này, đối với các hệ mật mã khoá công khai, có thể đ−ợc thực hiện bằng cách tạo cho một bản rõ nhiều bản mã khác nhau thu đ−ợc một cách ngẫu nhiên với việc sử dụng các số ngẫu nhiên trong tiến trình lập mã. Sau đây là định nghĩa về một hệ mật mã xác suất khoá công khai: Định nghĩa. Một hệ mật mã xác suất khoá công khai đ−ợc xác định bởi một bộ S = (P , C , K , E , D, R ), trong đó P , C , K đ−ợc hiểu nh− đối với các hệ mật mã khoá công khai thông th−ờng, R là một tập các phần tử ngẫu nhiên, và với mỗi K = (K', K'')∈K , thuật toán lập mật mã eK′ = E (K' ,.): P ìR →C và giải mã dK′′ = D (K'',.): C →P thoả mãn đẳng thức: với mọi x ∈P , r ∈R , dK′′ ( eK′ (x,r )) = x. Ngoài ra, ta mong muốn một điều kiện an toàn nh− trong định nghĩa sau đây đ−ợc thoả mãn: ta ký hiệu pK,x là phân bố xác 111
21. suất trên tập C , trong đó pK,x(y) là xác suất của việc y là bản mã khi biết K là khoá và x là bản rõ (xác suất đ−ợc tính cho tất cả r ∈R ). Ta nói hai phân bố xác suất p1 và p2 trên C là ε-phân biệt đ−ợc nếu có một thuật toán ε-phân biệt hai phân bố xác suất đó, tức là một thuật toán A : C → {0,1} thoả mãn tính chất ⎢EA(p1) - EA(p2)⎢≥ ε, trong đó EA(pi) = ∑ pyi ().p(A(y)= 1). y∈C Bây giờ điều kiện an toàn đ−ợc phát biểu nh− sau: Hệ mật mã xác suất khoá công khai S là an toàn nếu có ε>0 sao cho với mọi K ∈K p và mọi x ≠ x' , các phân bố xác suất pK,x và Kx, , là không ε-phân biệt đ−ợc. 4.6.2. Hệ mật mã xác suất Goldwasser-Micali. Sau đây là mô tả sơ đồ của hệ mật mã xác suất khoá công khai trên tập văn bản một bit do Goldwasser và Micali đề xuất năm 1984. Một hệ nh− vậy đ−ợc cho bởi một danh sách S = (P , C , K , E , D, R ), ∗ trong đó P ={0,1}, C = R = Zn , n =p.q là tích của hai số nguyên tố lớn, K là tập hợp các bộ khoá K = (K', K''), trong đó khoá công khai j K' = (n ,m) với m ∈QJnn= −Qn là một giả thặng d− bậc hai modn, và khoá bí mật K'' = (p,q ). Các thuật toán lập mật mã và giải mã đ−ợc xác định bởi x 2 eK′ (x,r ) = m .r modn , ⎪⎧0, khi y ∈Qn dK′′ (y) = ⎨ ⎩⎪1, khi y ∈Qn với mọi x ∈P , r ∈R , y ∈C . Hệ mật mã Goldwasser-Micali lập mật mã cho bản rõ một bit: mật mã của bit 0 luôn luôn là một thặng d− bậc hai modn , và mật mã của bit 1 là một giả thặng d− bậc hai modn . Việc giải mã là khá dễ dàng khi ta biết khoá bí mật K'' = (p,q ). Thực vậy, với mọi ⎛⎞y y∈Qn∪ Qn ta có ⎜⎟= 1. Vì biết K'' = (p,q ), nên ta tính đ−ợc ⎝⎠n ⎛⎞y p−1 ⎜⎟= yp2 mod , ⎝⎠p ⎛⎞y và do đó dễ thử đ−ợc yQ∈ n ⇔⎜⎟=1, và tính đ−ợc dK′′ (y). ⎝⎠p 112
22. 4.6.3.Hệ mật mã xác suất Blum-Goldwasser. Hệ mật mã xác suất khoá công khai Blum-Goldwasser đ−ợc xây dựng trên nền của các hệ mật mã theo dòng với dòng khoá là dãy số giả ngẫu nhiên Blum-Blum-Shub (xem 3.3.3), yểu tố ngẫu nhiên r ∈R ở đây sẽ đ−ợc sử dụng nh− mầm sinh ra dãy số giả ngẫu nhiên của dòng khoá đó. Sơ đồ của hệ mật mã xác suất khoá công khai Blum-Goldwasser đ−ợc cho bởi danh sách S = (P , C , K , E , D, R ), ∗ ∗ trong đó P = Z2 , C = Z2 ì Zn , R =Qn , n = p.q là tích của hai số nguyên tố lớn với pq≡ ≡ 3mod4;K là tập hợp các bộ khoá K = (K', K''), trong đó khoá công khai K' = n, và khoá bí mật K'' = (p,q ). Thuật toán lập mã eK′ = E (K' ,.) : P ìR →C đ−ợc tính theo các b−ớc sau: 1. Cho x =(x1, ,xl)∈P và r ∈R . Từ mầm r theo thuật toán Blum-Blum-Shub tính dãy số (s0 ,s1, ,sl +1) theo công thức ⎪⎧sr0 = , ⎨ 2 ⎩⎪ssii+1 = mod n, sau đó tính dãy số giả ngẫu nhiên (z1, ,zl) bởi zi =si mod2. 2.Tính y =(y1, ,yl) với yi = xi +zi mod2 (1≤ i ≤ l ). 3. Bản mã là eK′ (x ,r ) = (y, sl+1) =(y1, ,yl ;sl+1). Thuật toán giải mã dK′′ = D (K'',.): C →P đ−ợc thực hiện theo các b−ớc sau đây sau khi nhận đ−ợc bản mã (y1, ,yl ;sl+1) : 1. Tính l+1 ap1 = (( +−1) / 4) mod( p1), l+1 aq2 = (( +−1) / 4) mod(q1). aa12 2. Tính bs11==ll++mod p, b2s1mod q. 3. Tìm s0 =r bằng cách giải hệ ph−ơng trình ⎧sb01≡ mod p ⎨ ⎩sb02≡ mod q 4. Với s0 theo thuật toán BBS ta tìm lại đ−ợc dãy bit (z1, ,zl). 5. Cuối cùng ta đ−ợc dK′′ (y1, ,yl ;sl+1) = (x1, ,xl), với xi = yi +zi mod2 (1≤ i ≤ l ). Nh− vậy là hệ mật mã Blum-Goldwasser đã đ−ợc định nghĩa đầy đủ. Ta chú ý rằng nếu bản rõ x gồm l bit thì trong bản mã t−ơng ứng, ngoài các bit mã y1, ,yl ta phải gửi thêm số sl+1, số 113
23. đó đ−ợc sử dụng trong các b−ớc 1-3 của thuật toán giải mã để tìm lại mầm s0 cần thiết cho việc tìm dòng khoá ngẫu nhiên (z1, ,zl). Ta chứng minh rằng số s0 tính đ−ợc theo thuật toán giải mã đúng là mầm s0 mà ta cần tìm. Thực vậy, theo định nghĩa, ta có với mọi i =0,1, ,l +1, si đều là thặng d− bậc hai, và với mọi i =0, ,l , si đều là căn bậc hai của si+1 theo modn ; điều đó cũng đúng đối với modp và modq. Vì p ≡ 3 mod4, nên mỗi thặng d− bậc hai x theo modp đều có duy nhất một căn bậc hai modp cũng là thặng d− bậc hai modp, đó là x(p+1)/4modp. Thực vậy, vì x(p+1)/2≡ x modp, nên ±x(p+1)/4modp là căn bậc hai theo modp của x ; mặt khác ta lại có (1p+ )/4 (1p+ )/4 ⎛⎞x⎛⎞x (p+1)/4 ⎜⎟=⎜⎟ =1, nên x modp cũng là một thặng d− bậc ⎝⎠pp⎝⎠ hai modp. Từ nhận xét đó ta suy ra với mọi i (i = 0,1, ,l ): (1p+ )/4 ssii≡ +1 (mod p), do đó, l+1 (( p+1)/ 4) a1 ss01==ll++mod ps1mod p. Xét t−ơng tự đối với q, ta cũng đ−ợc a2 ss01= l+ mod q. Vậy số s0 tính theo các b−ớc 1-3 của thuật toán giải mã đúng là mầm s 0=r mà ta cần tìm. Các thuật toán lập mật mã và giải mã nh− đ−ợc định nghĩa ở trên là hợp thức. Thí dụ : Chọn n = 192649 = 383.503. Cho bản rõ x = 11010011010011101101. (l = 20) Giả sử chọn ngẫu nhiên s 0=r = 20749. Ta tính đ−ợc dãy z : z = 11001110000100111010. Ta tính thêm đ−ợc s 21=94739, và bản mã đ−ợc gửi đi là eK′ (x ,r ) = (y, sl+1) = (y, 94739), trong đó y = 00011101010111010111. Để giải mã, tr−ớc hết ta tìm s 0 từ s21 = 94739. Ta có (p +1)/4 =96, (q +1)/4 =126. Theo thuật toán giải mã: 21 a 1 = 96 mod382 =266, 21 a 2 = 126 mod502 = 486. Từ đó tính đ−ợc 266 b 1 = 94739 mod383 =67, 486 b 2 = 94739 mod503 = 126. Giải hệ ph−ơng trình đồng d−: ⎪⎧s0 ≡67(mod 383) ⎨ ⎩⎪s0 ≡126(mod503) 114
24. ta đ−ợc s 0=20749, từ đó tính lại đ−ợc dãy z, cộng mod2 từng bit với y ta lại thu đ−ợc bản rõ x . 115
25. CHƯƠNG V Bài toán xác nhận và chữ ký điện tử 5.1. Bài toán xác nhận và sơ đồ chữ ký. 5.1.1. Đặt vấn đề. Trong ch−ơng I, tiết 1.3, ta đã liệt kê một số bài toán chủ yếu về an toàn thông tin, trong đó ngoài bài toán quan trọng nhất là bảo mật thông tin thì các bài toán kế tiếp là: xác nhận thông báo và xác nhận ng−ời gửi (cùng với thông báo), x−ng danh và xác nhận danh tính của một chủ thể giao dịch, v.v Bài toán bảo mật đ−ợc đáp ứng bằng các giải pháp mật mã đã là nội dung của các ch−ơng III và IV, trong ch−ơng này và ch−ơng sau ta sẽ đề cập đến các bài toán xác nhận và nhận thức kể trên, ch−ơng V này sẽ dành cho bài toán xác nhận thông báo và ng−ời gửi thông báo, ch−ơng VI tiếp theo sẽ xét bài toán x−ng danh và xác nhận danh tính. Trong cách thức truyền thống, thông báo đ−ợc truyền đi trong giao dịch th−ờng d−ới dạng các văn bản viết tay hoặc đánh máy đ−ợc kèm thêm chữ ký (viết tay) của ng−ời gửi ở bên d−ới văn bản. Chữ ký đó là bằng chứng xác nhận thông báo đúng là của ng−ời ký, tức là của chủ thể giao dịch, và nếu tờ giấy mang văn bản không bị cắt, dán, tẩy, xoá, thì tính toàn vẹn của thông báo cũng đ−ợc chứng thực bởi chữ ký đó. Chữ ký viết tay có nhiều −u điểm quen thuộc nh− dễ kiểm thử, không sao chép đ−ợc, chữ ký của một ng−ời là giống nhau trên nhiều văn bản, nh−ng mỗi chữ ký gắn liền với một văn bản cụ thể, v.v Khi chuyển sang cách thức truyền tin bằng ph−ơng tiện hiện đại, các thông báo đ−ợc truyền đi trên các mạng truyền tin số hoá, bản thân các thông báo cũng đ−ợc biểu diễn d−ới dạng số hoá, tức d−ới dạng các dãy bit nhị phân, “chữ ký” nếu có cũng ở d−ới dạng các dãy bit, thì các mối quan hệ tự nhiên kể trên không còn giữ đ−ợc nữa. Chẳng hạn, “chữ ký” của một ng−ời gửi trên những văn bản khác nhau phải thể hiện đ−ợc sự gắn kết trách nhiệm của 115
26. ng−ời gửi đối với từng văn bản đó thì tất yếu phải khác nhau chứ không thể là những đoạn bit giống nhau nh− các chữ ký giống nhau trên các văn bản thông th−ờng. Chữ ký viết tay có thể đ−ợc kiểm thử bằng cách so sánh với nguyên mẫu, nh−ng “chữ ký” điện tử thì không thể có “nguyên mẫu” để mà so sánh, việc kiểm thử phải đ−ợc thực hiện bằng những thuật toán đặc biệt. Một vấn đề nữa là việc sao chép một văn bản cùng chữ ký. Nếu là văn bản cùng chữ ký viết tay thì dễ phân biệt bản gốc với bản sao, do đó khó mà dùng lại đ−ợc một văn bản có chữ ký thật. Còn với văn bản điện tử cùng chữ ký điện tử thì có thể nhân bản sao chép tuỳ thích, khó mà phân biệt đ−ợc bản gốc với bản sao, cho nên nguy cơ dùng lại nhiều lần là có thực, do đó cần có những biện pháp để tránh nguy cơ đó. Một “chữ ký”, nếu muốn thể hiện đ−ợc trách nhiệm của ng−ời gửi trên toàn văn bản, thì phải mang đ−ợc một chút gắn bó nào đó với từng bit thông tin của văn bản, vì vậy, theo hình dung ban đầu, độ dài của chữ ký cũng phải dài theo độ dài của văn bản; để có đ−ợc “chữ ký ngắn” nh− trong tr−ờng hợp viết tay ng−ời ta phải dùng một kỹ thuật riêng gọi là hàm băm mà ta sẽ trình bày ở cuối ch−ơng. Bây giờ, tr−ớc hết ta sẽ giới thiệu định nghĩa về sơ đồ chữ ký (điện tử). 5.1.2. Định nghĩa sơ đồ chữ ký. Định nghĩa 5.1. Một sơ đồ chữ ký S là một bộ năm S = (P, A, K, S, V ), trong đó: P là một tập hữu hạn các thông báo có thể có, A là một tập hữu hạn các chữ ký có thể có, K là một tập hữu hạn các khoá, mỗi khoá K ∈ K gồm có hai phần K =(K’,K''), K' là khoá bí mật dành cho việc ký, còn K'' là khoá công khai dành cho việc kiểm thử chữ ký. Với mỗi K =(K’,K''), trong S có một thuật toán ký sigK ' :P → A , và trong Vcó một thuật toán kiểm thử verK " : P ìA →{đúng,sai} thoả mãn điều kiện sau đây đối với mọi thông báo x∈P và mọi chữ ký y∈A : verK " (x, y) = đúng ⇔ y = sigK ' (x ). Với sơ đồ trên, mỗi chủ thể sở hữu một bộ khoá K =(K’,K''), công bố công khai khoá K'' để mọi ng−ời có thể kiểm thử chữ ký của mình, và giữ bí mật khoá K’ để thực hiện chữ ký trên các thông báo mà 116
27. mình muốn gửi đi. Các hàm verK " và sigK ' (khi biết K’ ) phải tính đ−ợc một cách dễ dàng (trong thời gian đa thức), tuy nhiên hàm y =sigK ' (x ) là khó tính đ−ợc nếu không biết K’ - điều đó bảo đảm bí mật cho việc ký, cũng tức là bảo đảm chống giả mạo chữ ký. Bài toán xác nhận với chữ ký điện tử, theo một nghĩa nào đó, có thể xem là ô đối ngẫu ằ với bài toán bảo mật bằng mật mã, nh− đ−ợc minh hoạ bởi thí dụ sơ đồ chữ ký RSA, đối ngẫu với sơ đồ mật mã RSA, d−ới đây : 5.1.3. Sơ đồ chữ ký RSA. Sơ đồ chữ ký RSA đ−ợc cho bởi bộ năm S = (P, A, K, S, V ), trong đó P =A =Zn , với n =p.q là tích của hai số nguyên tố lớn p,q, K là tập các cặp khoá K =(K’,K''), với K’ = a và K'' = (n,b), a và b là ∗ hai số thuộc Zn thoả mãn a.b ≡ 1(modφ(n)). Các hàm sigK ' và verK " đ−ợc xác định nh− sau: a sigK ' (x) = x modn , b verK′′ (x,y ) = đúng ⇔ x ≡ y (modn ). Dễ chứng minh đ−ợc rằng sơ đồ đ−ợc định nghĩa nh− vậy là hợp thức, tức là với mọi x∈P và mọi chữ ký y∈A: verK " (x, y) = đúng ⇔ y = sigK ' (x ). Chú ý rằng tuy hai vấn đề xác nhận và bảo mật theo sơ đồ RSA là có bề ngoài giống nhau, nh−ng nội dung của chúng là hoàn toàn khác nhau: Khi A gửi thông báo x cho B, để B có căn cứ xác nhận đó đúng thực là thông báo do A gửi, A phải gửi kèm theo chữ ký sigK ' (x), tức là A gửi cho B (x, sigK ' (x)), trong các thông tin gửi đi đó, thông báo x hoàn toàn không đ−ợc giữ bí mật. Cũng t−ơng tự nh− vậy, nếu dùng sơ đồ mật mã RSA, khi một chủ thể A nhận đ−ợc một bản mật mã eK′ (x) từ B thì A chỉ biết rằng thông báo x đ−ợc bảo mật, chứ không có gì để xác nhận x là của B. Nếu ta muốn hệ truyền tin của ta vừa có tính bảo mật vừa có tính xác nhận, thì ta phải sử dụng đồng thời cả hai hệ mật mã và xác nhận (bằng chữ ký). Giả sử trên mạng truyền tin công cộng, ta có cả hai hệ mật mã khoá công khai S1 và hệ xác nhận bằng chữ ký S 2. Giả sử B có bộ khoá mật mã K = (K', K'') với K' = (n, e) và K'' = d trong hệ S1, và A có bộ khoá chữ ký KKs =(,s′ Ks′′ ) với Ks′ = a và Ks′′ = (,nb)trong hệ S 2. A có thể gửi đến B một thông báo vừa bảo 117
28. mật vừa có chữ ký để xác nhận nh− sau: A ký trên thông báo x tr−ớc, rồi thay cho việc gửi đến B văn bản cùng chữ ký (x, sig (x)) Ks′ thì A sẽ gửi cho B bản mật mã của văn bản đó đ−ợc lập theo khoá công khai của B, tức là gửi cho B e ((x, sig (x)). Nhận đ−ợc văn K′ Ks′ bản mật mã đó B sẽ dùng thuật toán giải mã dK′′ của mình để thu đ−ợc (x, sig (x)), sau đó dùng thuật toán kiểm thử chữ ký công Ks′ khai ver của A để xác nhận chữ ký sig (x) đúng là của A trên x. Ks′′ Ks′ 5.2. Sơ đồ chữ ký ElGamal và chuẩn chữ ký điện tử. 5.2.1. Sơ đồ chữ ký ElGamal. Sơ đồ chữ ký ElGamal đ−ợc đề xuất năm 1985, gần nh− đồng thời với sơ đồ hệ mật mã ElGamal, cũng dựa trên độ khó của bài toán lôgarit rời rạc. Sơ đồ đ−ợc thiết kế đặc biệt cho mục đích ký trên các văn bản điện tử, đ−ợc mô tả nh− một hệ S = (P, A, K, S, V), ∗ ∗ trong đó P =Z p , A =Z p ì Z p−1 , với p là một số nguyên tố sao cho ∗ bài toán tính lôgarit rời rạc trong Z p là rất khó. Tập hợp K gồm các ∗ cặp khoá K =(K’,K''), với K’ = a là một số thuộc Z p , K'' =(p, α, β ), α ∗ a là một phần tử nguyên thuỷ của Z p , và β = α modp. K’ là khoá bí mật dùng để ký, và K'' là khoá công khai dùng để kiểm thử chữ ký. Các thuật toán ký và kiểm thử chữ ký đ−ợc xác định nh− sau: Với mỗi thông báo x, để tạo chữ ký trên x ta chọn thêm môt số ngẫu ∗ nhiên k ∈ Z p−1 , rồi tính sigK ' (x,k ) = (,γ δ ), với γ = α k modp, δ=−(x aγ).k−1 mod(p -1). Thuật toán kiểm thử đ−ợc định nghĩa bởi: γ δ x verK " (x, (,γ δ )) = đúng ⇔ β .γ ≡ α (modp). Dễ thấy rằng sơ đồ chữ ký đ−ợc định nghĩa nh− trên là hợp thức. Thực vậy, nếu sigK ' (x,k ) = (,γ δ ),thì ta có : β γ.γ δ ≡ αaγ.αkδ modp ≡ α x modp, vì kδ +aγ ≡ x mod(p -1). Do đó, verK " (x, (,γ δ )) = đúng. 118
29. Thí dụ: Giả sử p = 467, α = 2, a = 127. Khi đó β = 2127mod467=132. ∗ -1 Cho x =100; ta chọn ngẫu nhiên k =213 (∈ Z466 ) và đ−ợc k mod466 =431. Chữ ký trên văn bản x =100 với số ngẫu nhiên k =213 là (γ, δ), trong đó γ =2213mod467 = 29 và δ = (100 - 127.29).431mod466 =51. Để kiểm thử ta tính : β γ.γ δ = 13229.2951 ≡ 189 (mod467), α x = 2100 ≡ 189 (mod467), hai giá trị đó đồng d− với nhau theo mod467, chữ ký(γ, δ)=(29,51) đ−ợc xác nhận là đúng. 5.2.2. Tính an toàn của sơ đồ chữ ký ElGamal. Sơ đồ chữ ký ElGamal đ−ợc xem là an toàn, nếu việc ký trên một văn bản là không thể giả mạo đ−ợc, nói cách khác, không thể có một ng−ời nào ngoài chủ thể hợp pháp có thể giả mạo chữ ký của chủ thể hợp pháp đó trên một văn bản bất kỳ. Vì vậy, việc giữ bí mật khoá K′ = a dùng để tạo chữ ký là có ý nghĩa quyết định đối với việc bảo đảm tính an toàn của chữ ký. Có thể để lộ khoá bí mật K′ = a trong những tr−ờng hợp nào, và có thể không để lộ Ka′ = mà vẫn giả mạo chữ ký đ−ợc không? Ta sẽ xét sau đây một vài tr−ờng hợp đơn giản : 1) Khả năng để lộ khoá K′ = a: Cũng nh− đối với sơ đồ hệ mật mã ElGamal, khoá bí mật a có thể bị phát hiện trong tr−ờng hợp để lộ số ngẫu nhiên k ở một lần ký nào đó, hoặc sử dụng cùng một số ngẫu nhiên k ở hai lần ký khác nhau. Nếu số ngẫu nhiên k đ−ợc sử dụng khi ký trên văn bản x bị lộ, thì khoá bí mật K′ = a đ−ợc tính theo công thức sau đây: a = (x - kδ ). γ -1 mod(p –1). Bây giờ ta xét tr−ờng hợp dùng cùng một số ngẫu nhiên k cho hai lần ký khác nhau, chẳng hạn cho x1 và x2. Khi đó ta có chữ ký trên x1 là (γ ,δ 1), trên x2 là (γ ,δ 2), với thành phần thứ nhất bằng nhau (và bằng γ =α k modp), và các chữ ký đó thoả mãn β γ .γδ1≡αx1(modp), β γ .γδ2≡αx2(modp). Từ đó ta có αγxx1−−2≡≡δ12δαk(δ1−δ2)(modp), điều đó t−ơng đ−ơng với x 1 - x2 ≡ k (δ1 - δ 2) (mod(p -1)). Đặt d = gcd(δ1 - δ 2, p -1). Cả ba số δ1 - δ 2, p -1 và x 1 - x2 đều chia hết cho d, ta đặt 119
30. xx− δ −δ p −1 xp′′==12,,δ 12 ′=. ddd Khi đó đồng d− thức ở trên trở thành x′ ≡ k.δ ′ (mod p′ ). Vì gcd (,δ ′p′)=1, nên có thể tính ε = δ ′−1 mod p′ , và sau đó giá trị k theo mod p′ : k = x′.ε mod p′ , tức là k = x′.ε + ip.′ mod(p -1) với i là một giá trị nào đó, 0≤ i ≤ d –1. Thử lần l−ợt điều kiện γ = α k modp với các giá trị đó của i , ta sẽ tìm đ−ợc k ;sau đó từ k tính đ−ợc a cần tìm. 2) Khả năng giả mạo chữ ký trên một văn bản cho tr−ớc : Giả sử chủ thể A chọn sơ đồ chữ ký ElGamal với cặp khoá K =(K’,K''), trrong đó K′ = a là khoá bí mật. Một ng−ời ngoài O không biết khoá bí mật K′ = a mà muốn giả mạo chữ ký của A trên một văn bản x thì phải có khả năng tạo ra đ−ợc chữ ký (γ,δ ) mà không cần biết a. Có hai cách : hoặc chọn tr−ớc γ rồi tìm δ t−ơng ứng, hoặc ng−ợc lại, chọn tr−ớc δ rồi tìm γ t−ơng ứng. Nếu chọn tr−ớc γ rồi tìm δ , thì δ phải là −1 δ=−(x akγ)mod(p -1) = ( ()xa− γ logγ α mod(p -1) xx−γ −γ = logαγ(α βα).log =logγαβmod(p -1); đó là một bài toán tính lôgarit rời rạc, mà ta biết rằng rất khó. Nếu chọn tr−ớc δ rồi tìm γ thì phải giải ph−ơng trình β γδ.γ≡ αx modp với ẩn số γ . Ta ch−a biết có cách giải hữu hiệu nào không, nh−ng chắc là không dễ hơn bài toán tính lôgarit rời rạc. Nh− vậy, ta có thể tin rằng khả năng giả mạo chữ ký trên một văn bản cho tr−ớc khi không biết khoá bí mật K′ = a là rất ít, do đó không có ảnh h−ởng đáng kể đến tính an toàn của sơ đồ chữ ký. 3)Giả mạo chữ ký cùng với văn bản đ−ợc ký : Có một khả năng giả mạo khác là giả mạo cả văn bản gửi đi x cùng với chữ ký (γ,δ ) trên x. Khả năng đó xẩy ra khi kẻ giả mạo chọn đ−ợc x và (γ,δ ) thoả mãn điều kiện kiểm thử, cụ thể khi chọn đ−ợc x,γ,δ có dạng sau đây : γ = αβi. jmodp, 120
31. δγ=− . j−1 mod(p -1), x =−γ ij−1 mod(p -1), trong đó i, j là các số nguyên sao cho 0≤ i, j ≤ p –2, gcd(j, p –1) = 1, và j –1 đ−ợc tính theo mod(p –1). Thực vậy, khi đó ta có −1 βγγδ.(≡ βγαijβ)−γ. jmodp −1 ≡ β γ .α−ijγ.β−γ modp ≡α x modp , tức điều kiện kiểm thử đ−ợc thoả mãn, (γ,δ ) có thể đ−ợc xác nhận hợp thức là chữ ký trên x. Có thể có một cách giả mạo khác nữa, nếu kẻ giả mạo sử dụng chữ ký đúng (γ,δ ) trên một văn bản x có từ tr−ớc để tạo ra một chữ ký (,λ à)mới cho một văn bản “mới” x′ nh− sau: λ =γαhi βj modp, à =δλ(hjγ −δ )−1 mod(p -1), x′=+λ()hx iδγ(h −jδ)−1 mod(p -1). Có thể thử lại rằng điều kiện kiểm thử đúng đối với “chữ ký” (,λ à)và “văn bản” x′ , tức là β λà.λ≡αx′ modp. Cả hai cách giả mạo nói trên đều cho chữ ký thoả mãn điều kiện kiểm thử đối với văn bản t−ơng ứng, tuy nhiên văn bản đó không phải là văn bản đ−ợc chọn theo ý muốn của ng−ời giả mạo, cho nên khả năng sử dụng các cách giả mạo đó trong thực tế cũng không có giá trị , do đó không thể gây nguy hại đáng kể cho tính an toàn của sơ đồ chữ ký nói chung. 5.2.3. Chuẩn chữ ký số (Digital Signature Standard). Chuẩn chữ ký số (DSS) đ−ợc đề xuất từ năm 1991 và đ−ợc chấp nhận vào cuối năm 1994 để sử dụng trong một số lĩnh vực giao dịch điện tử tại Hoa kỳ. DSS dựa vào sơ đồ chữ ký ElGamal, với một vài sửa đổi. Để bảo đảm an toàn , số nguyên tố p cần phải đủ lớn, biểu diễn nhị phân của p phải có từ 512 bit trở lên (cụ thể từ 512 đến 1024 bit, số bit là một bội của 64). Tuy nhiên, độ dài chữ ký theo sơ đồ ElGamal là gấp đôi số bit của p, mà trong nhiều ứng dụng ng−ời ta lại mong muốn có chữ ký độ dài ngắn, nên giải pháp sửa đổi đ−ợc đề xuất là: trong khi vẫn dùng p lớn với độ dài biểu diễn 512 bit trở lên, thì sẽ hạn chế độ dài của γ và δ trong chữ ký (γ,δ ) vào khoảng 160 bit (nh− vậy cả chữ ký sẽ có độ dài khoảng 320 bit); điều này đ−ợc thực hiện bằng cách dùng một nhóm con ∗ ∗ ∗ cyclic Zq của Z p thay cho chính bản thân Z p , do đó mọi tính toán 121
32. ∗ vẫn đ−ợc thực hiện nh− trong Z p nh−ng các dữ liệu và thành phần ∗ chữ ký lại thuộc Zq . Ta đ−ợc sơ đồ chuẩn chữ ký số DSS nh− mô tả sau đây: Chọn p là một số nguyên tố lớn có độ dài biểu diễn ≥ 512 bit sao cho bài toán tính logarit rời rạc trong Zp là khó, q là một −ớc số ∗ nguyên tố của p -1, có độ dài biểu diễn cỡ 160 bit. Gọi α ∈ Z p là một căn bậc q của 1 theo modp. ∗ ∗ ∗ ∗ a Đặt P =Z p , A = Zq ì Zq . Chọn a∈ Zq và tính β ≡ α modp. Xác định khoá K =(K’,K''), trong đó khoá bí mật K’ = a, và khoá công khai K'' = (p,q,α,β). Thuật toán ký và thuật toán kiểm thử đ−ợc ∗ định nghĩa nh− sau: Với x ∈ P =Z p , ta chọn thêm một số ngẫu nhiên k (0≤k ≤ q -1), và định nghĩa chữ ký sigK ' (x,k ) = (,γ δ ), trong đó γ =(α k modp) modq, δ=+(x aγ).k−1 modq. Thuật toán kiểm thử đ−ợc định nghĩa bởi: e1e2 verK " (x, (,γ δ )) = đúng ⇔ (.α β modp)modq = γ , −1 −1 trong đó ex1 = .δ modq và e2 = γ .δ modq. Chú ý rằng ta phải có δ ≠ 0 modq để có thể tính đ−ợc δ -1modq dùng trong thuật toán kiểm thử, vì vậy nếu chọn k mà đ−ợc δ ≡ 0 modq thì phải chọn lại số k khác để có đ−ợc δ ≠ 0 modq. 5.3. Hàm băm và chữ ký. 5.3.1. Hàm băm (hash function). Trong các phần trên, ta đã giới thiệu một vài sơ đồ chữ ký điện tử. Theo các sơ đồ đó, chữ ký đ−ợc xác định cho từng khối của văn bản, và nếu văn bản gồm nhiều khối thì chữ ký cho toàn văn bản cũng phải do ghép chữ ký trên từng khối lại với nhau mà thành; mà chữ ký trên từng khối văn bản th−ờng có độ dài bằng (hoặc thậm chí gấp đôi) độ dài của khối văn bản, do đó chữ ký chung cũng có độ dài t−ơng đ−ơng với độ dài văn bản. Đó là một điều bất tiện. Ta mong muốn, nh− trong tr−ờng hợp viết tay, chữ ký chỉ có độ dài ngắn và hạn chế cho dù văn bản có thể dài bao nhiêu cũng đ−ợc. Đối với chữ ký điện tử, vì chữ ký phải đ−ợc “ký” cho từng bit của văn bản, nên muốn có chữ ký độ dài hạn chế trên văn bản có độ dài tuỳ ý thì phải tìm cách rút ngắn độ dài văn bản. Nh−ng bản thân văn bản không thể rút ngắn đ−ợc, nên chỉ còn cách là tìm cho mỗi văn bản một bản “tóm l−ợc” có độ dài hạn chế, rồi thay cho việc ký trên toàn bộ văn bản, ta ký trên bản tóm l−ợc 122
33. đó, xem chữ ký trên bản tóm l−ợc có t− cách là chữ ký trên văn bản. Giả sử Σ là tập hợp tất cả các văn bản có thể có (tất nhiên, trong một lĩnh vực nào đó), và ∆ là tập hợp tất cả các bản “tóm l−ợc” có thể đ−ợc sử dụng. Việc tìm cho mỗi văn bản một bản tóm l−ợc t−ơng ứng xác định một hàm h : Σ → ∆. Một hàm h nh− vậy ng−ời ta gọi là một hàm băm (hash function). Thông th−ờng, Σ là tập hợp các dãy bit có độ dài tuỳ ý, và ∆ là tập hợp các dãy bit có một độ dài n cố định, nên ng−ời ta cũng định nghĩa hàm băm là các hàm h : Σ → ∗ n ∆ với các tập hợp Σ và ∆ đó (tức các hàm h : {0,1} → {0,1} ). Dùng hàm băm h , ta xem z = h(x) là “tóm l−ợc” của x , đại diện cho x, và ta sẽ xem chữ ký trên z là chữ ký trên văn bản x ; vì z có độ dài hạn chế, nên chữ ký trên x cũng có độ dài hạn chế. Một vấn đề đ−ợc đặt ra là: vậy hàm h : Σ → ∆ phải thoả mãn những điều kiện gì để h(x) xứng đáng đ−ợc xem là đại diện của x trong việc tạo lập chữ ký ? Hai điều kiện sau đây th−ờng đ−ợc ng−ời ta xem là hai điều kiện chủ yếu cho một hàm băm: 1. Hàm băm phải là hàm một phía, nghĩa là cho x tính z = h(x) là việc dễ, nh−ng ng−ợc lại, biết z tính x là việc cực khó (có thể qui −ớc dễ hay khó theo nghĩa tính đ−ợc trong thời gian đa thức hay không). 2. Hàm băm phải là hàm không va chạm mạnh theo nghĩa sau đây: không có thuật toán tính đ−ợc trong thời gian đa thức giải bài toán “ tìm x1 và x2 thuộc Σ sao cho x1 ≠ x2 và h (x1) =h (x2)”; nói cách khác, tìm hai văn bản khác nhau có cùng một đại diện là cực kỳ khó. (Còn có một khái niệm không va chạm yếu đ−ợc định nghĩa nh− sau: Cho x ∈Σ. Hàm h là không va chạm yếu đối với x nếu rất khó tìm đ−ợc x′ ∈Σ, x′ ≠ x và h ( x′ ) = h (x )). Ta mong muốn độ dài của chữ ký là ngắn, tức là độ dài của các tóm l−ợc cũng ngắn. Nh−ng ngắn bao nhiêu là vừa? Ngắn bao nhiêu thì có thể bảo đảm tính không va chạm mạnh? Và ở đây ta gặp một kiểu “tấn công”, th−ờng đ−ợc gọi là “tấn công ngày sinh” có liên quan đến khả năng va chạm mạnh, nói rằng trong một nhóm gồm 23 ng−ời đ−ợc chọn một cách ngẫu nhiên thì ít nhất có hai ng−ời có cùng ngày sinh (tức có va chạm mạnh!). Một cách tổng quát, ng−ời ta chứng minh đ−ợc rằng: Nếu có tất cả n bản tóm l−ợc, 1 và kn≈ 2ln ,thì trong k văn bản đ−ợc chọn ngẫu nhiên có ít 1−ε nhất một va chạm mạnh (tức có x′ ≠ x và h ( x′ ) = h (x )) với xác suất ε. 123
34. 1 Khi ε = , ta có k≈ 1,17 n. Trong tr−ờng hợp ngày sinh, ta 2 có n =365, do đó k ≈ 22,3 ≈ 23. Trở lại với vấn đề chọn độ dài (của biểu diễn nhị phân) cho các tóm l−ợc, nếu ta lấy chẳng hạn độ dài 40 bit, thì n = 240, và do đó từ k ≈ 220 (khoảng một triệu) văn bản sẽ có một va chạm mạnh với xác suất 1/2, nh− vậy khó bảo đảm đ−ợc an toàn. Nh−ng nếu ta lấy dộ dài của bản tóm l−ợc là 128, tức n =2128, thì va chạm mạnh có thể xẩy ra với xác suất 1/2 khi số các văn bản có thể là k ≈ 264, một con số khá lớn (so với số văn bản có thể nẩy sinh trong thực tế), do đó hy vọng tính an toàn sẽ đ−ợc bảo đảm. Có thể vì vậy mà trong chuẩn DSS ng−ời ta chọn độ dài của các tóm l−ợc là 160 bit. 5.3.2. Hàm băm Chaum-van Heijst-Pfitzmann. D−ới đây ta sẽ giới thiệu một thí dụ cụ thể về một hàm băm đ−ợc xây dựng dựa trên tính khó của bài toán lôgarit rời rạc, do các tác giả Chaum, van Heijst và Pfitzmann đề xuất năm 1992. Hàm băm đó đ−ợc xây dựng nh− sau: Giả sử p là một số nguyên tố lớn dạng Sophie Germain, tức có dạng p = 2q +1, trong đó q cũng là số nguyên tố. Chọn α và β là ∗ hai phần tử nguyên thuỷ của Z p . Việc tính logα β , khi biết α và β , là rất khó. Hàm băm hZ:qqì→Z Zp−{0}đ−ợc định nghĩa nh− sau: với mọi x12, x∈ Zq ta có x1x2 hx(,12x)=α .β modp. Ta gọi hàm băm h đ−ợc định nghĩa nh− vậy là hàm băm Chaum-van Heijst-Pfitzmann. Hàm băm đó có các tính chất là hàm một phía và không va chạm mạnh nh− yêu cầu đối với một hàm băm. Tính một phía của hàm đó đ−ợc suy ra từ tính một phía của hàm lôgarit rời rạc. Còn tính không va chạm mạnh của h đ−ợc chứng minh bởi định lý sau đây : Nếu biết một va chạm mạnh đối với h thì có thể tính đ−ợc logα β một cách có hiệu quả. Giả sử có một va chạm hx(,12x)= h(x3,x4), trong đó (x1,x2) ≠ (x3,x4). Nh− vậy ta có α xx12.βα≡ x3 .βx4(modp), tức là αxx13− ≡ βx4−x2 (modp). Đặt d =gcd(x4 - x2, p -1). Vì p -1 = 2q và q là số nguyên tố, nên ta có d ∈ {1,2,q, p -1}. Ta xét lần l−ợt bốn khả năng đó của d. -1 Giả sử d =1. Khi đó, đặt y = (x4 - x2) mod(p -1), ta có 124
35. ββ≡ (xx42− )y(modp) ≡ α (xx13− )y (modp), và ta có thể tính logarit rời rạc logα β nh− sau : -1 logα β = (x1 - x3)(x4 - x2) mod(p –1). Bây giờ giả sử d = 2. Vì p -1 = 2q và q là số lẻ, ta phải có -1 gcd(x4 - x2, q) =1. Cũng đặt y = (x4 - x2) modq, ta có (x4 - x2)y = kq +1 với k là một số nguyên nào đó, và ta có β ()xx42− y≡ β kq+1 (modp) ≡−(1)k β (modp) (vì β q ≡−1(modp)) ≡ ±β (modp). Nh− vậy ta có β()xx42− y≡ α(xx13− )y(modp) ≡ ±β (modp). Từ đó suy ra logα β = (x13− x)ymod(p -1) hay là logα β = (x13− x)y+q mod(p -1). Có thể thử để xác định giá trị nào trong hai giá trị đó đúng là logα β . Bây giờ ta xét trr−ờng hợp d =q. Vì 0 ≤ x2 , x4 ≤ q -1, nên -(q -1) ≤ x4 - x2 ≤ q -1. Do đó không thể có gcd(x4 - x2, p -1) = q, tr−ờng hợp này không thể xẩy ra. Cuối cùng là tr−ờng hợp d = p -1. Điều này chỉ xẩy ra nếu x2 = x4. Nh−ng khi đó ta có α xx12βα≡ x3 βx2(modp) α x1 ≡α x3 (modp) và x1=x3. Nh− vậy (x1, x2) = (x3, x4), mâu thuẫn với giả thiết. Vậy tr−ờng hợp này cũng không thể xẩy ra. Định lý nói trên đ−ợc chứng minh. Hàm băm Chaum-van Heijst-Pfitzmann là không va chạm mạnh. Chú ý rằng nếu p có độ dài biểu diễn nhị phân là t bit, tức Zp t là tập con của ∆ ={0,1} , thì q có độ dài t -1 bit, và ZqìZq là tập con của Σ = {0,1}m với m =2(t -1). Hàm băm h đ−ợc định nghĩa ở trên có thể xem là hàm h : Σ → ∆. Với mục đích chữ ký, ta muốn có những hàm băm h : Σ → ∆ với ∆ là tập các từ có số bit hạn chế, nh−ng Σ lại là tập các từ có độ dài tuỳ ý. Muốn vậy, ta phải có khả năng mở rộng hàm băm; định lý sau đây cho ta khả năng đó. 125
36. 5.3.3. Mở rộng hàm băm. mt Bây giờ giả sử h : Z2→ Z2 (ở đây Z2 ={0,1}) là một hàm băm không va chạm mạnh thoả mãn m ≥ t +1 (hàm băm trong mục trên thoã mãn điều kiện đó). Ta sẽ dùng h để xây dựng một hàm băm ∗∗ t hZ: 2→ Z2 nh− sau : ∗ Giả sử x ∈ Z2 , ta cắt x thành các đoạn có cùng độ dài l bit, trong đó l = m-t-1, nếu đoạn cuối cùng ch−a có đủ l bit, thì ta bổ sung thêm các bit 0 cho đủ, và để ghi nhớ sự bổ sung đó (chẳng hạn là d bit) ta thêm cho x một đoạn cuối xk +1 là biểu diễn nhị phân l bit ∗ của số d . Nh− vậy mỗi x ∈ Z2 đ−ợc viết lại d−ới dạng x = x1x2 xkxk +1, l trong đó với mọi i =1,2, ,k, k +1, xi ∈ Z2 (ta chú ý rằng nếu biết x d−ới dạng này ta sẽ khôi phục lại đ−ợc x ở dạng gốc ban đầu). Ta t ∗ định nghĩa một cách đệ qui dãy từ g1, g2, , gk +1∈ Z2 và hàm h nh− sau : t +1 g1 = h (0 x1), gi+1=h (gi1xi+1) (i =1, ,k) ∗ h (x) = gk+1 . Nh− vậy, giá trị của hàm băm h∗ là một từ có độ dài t bit. Ng−ời ta chứng minh đ−ợc định lý sau đây : Nếu hàm băm h có tính chất không va chạm mạnh thì hàm băm mở rộng h∗ cũng có tính chất không va chạm mạnh. 5.3.4. Xây dựng hàm băm từ các hệ mật mã. Có một ph−ơng pháp chung để xây dựng hàm băm là sử dụng các hệ mật mã khoá đối xứng. Giả sử (P , C , K , E , D ) là một hệ mật mã khoá đối xứng mà độ an toàn đã đ−ợc thử nghiệm. Để tiện n trình bày, ta có thể giả thiết rằng P =C =K = Z2 . Nên chọn n khá lớn, cỡ n ≥ 128 để tránh kiểu “tấn công ngày sinh”. Chẳng hạn, có thể chọn hệ mật mã đó là hệ DES (có thể với những điều chỉnh cần thiết để có độ dài các ký tự trong P , C , K thích hợp). Xuất phát từ n n n hàm lập mật mã E ta xác định một hàm f : Z2 ì Z2 → Z2 sao cho với n n mọi (x ,y) ∈ Z2 ì Z2 , giá trị của f(x, y) đ−ợc tính theo x, y và hàm E . ∗ Bây giờ giả sử cho x ∈ Z2 . Nh− trong mục trên, ta có thể viết x d−ới dạng ghép nối liên tiếp của k đoạn ký tự, mỗi đoạn có n bit : x = x1x2 xk . n Tiếp đó, ta chọn một giá trị ban đầu g0∈ Z2 , và xây dựng tiếp g1, g2, ,gk theo qui tắc 126
37. gi = f (xi , gi -1) với i =1,2, ,k. Và cuối cùng, ta định nghĩa giá trị hàm băm h (x ) = gk . Hàm băm h ∗ n đ−ợc định nghĩa nh− vậy là một hàm ánh xạ Z2 vào Z2 ; trong tr−ờng hợp chung có thể không bảo đảm tính an toàn, nh−ng ng−ời ta đã chứng tỏ đ−ợc rằng nó là an toàn trong các tr−ờng hợp hàm f đ−ợc chọn nh− sau: f (x, y) = x ⊕ E (y,x), f (x, y) = x ⊕ y ⊕E (y,x), f (x, y) = x ⊕ E (y,x ⊕ y), f (x, y) = x ⊕ y ⊕E (y,x ⊕ y) , trong đó ⊕ là phép cộng mod2 từng cặp bit một của hai từ có số bit bằng nhau. 5.4. Một số sơ đồ chữ ký khác. 5.4.1. Sơ đồ chữ ký Rabin. T−ơng t− nh− sơ đồ chữ ký RSA, sơ đồ chữ ký Rabin cũng sử dụng số nguyên n là tích của hai số nguyên tố lớn p và q, n =p.q , với hàm một phía ở đây là hàm lấy bình ph−ơng của một số nguyên theo modn, có hàm ng−ợc là hàm tìm căn bậc hai theo modn, một hàm không tính đ−ợc một cách dễ dàng nếu không biết các thừa số p ,q của n. Nh− vậy, một cách đại thể, sơ đồ chữ ký Rabin có thể đ−ợc mô tả là một bộ S = (P, A, K, S, V), trong đó P= Qn , A = Zn , K là tập các cặp khoá K =(K’,K''), trong đó K'' = n là khoá công khai dùng để kiểm thử chữ ký,n là tích của hai số nguyên tố lớn p và q, n =p.q , với p ≡ q ≡ 3 (mod4), còn K’ = d với d = (n -p -q +5)/8 là khoá bí mật dùng để ký. Các hàm sigK ' và verK " đ−ợc xác định nh− sau: d sigK ' (x) = x modn , 2 verK′′ (x,y ) = đúng ⇔ x ≡ y (modn ). Ta chú ý rằng nếu p và q đ−ợc chọn với tính chất nói trên thì với d mọi x ∈P =Qn , x modn là một căn bậc hai của x theo modn, vì (1pq−−)(1)+4 (1pq−−)(1) 2 +1 x2d ≡≡xx8 4 ≡x (modn) ; và các hàm sigK ' và verK " đ−ợc định nghĩa nh− trên là hợp thức. Y t−ởng cơ bản về một sơ đồ chữ ký Rabin chỉ đơn giản là nh− thế, tuy nhiên để có một sơ đồ chữ ký dùng đ−ợc trong thực tế, 127
38. ng−ời ta muốn tập các văn bản P không hạn chế trong Qn , mà rộng rãi hơn, là Zn chẳng hạn, nh−ng để đ−ợc nh− vậy, ta phải dùng thêm một hàm R để chuyển một x ∈P ban đầu về một giá trị m nào đó có quan hệ gần gũi với một thặng d− bậc hai theo modn để sơ đồ chữ ký theo ý t−ởng nói trên có thể vận hành đ−ợc. Để thực hiện đ−ợc một sơ đồ chữ ký sửa đổi nh− vậy, ng−ời ta sẽ dùng một bổ đề toán học sau đây: Bổ đề 5.4.1. Giả sử p và q là các số nguyên tố khác nhau cùng đồng d− với 3 theo mod4, và n = p.q. Khi đó ta có: 1) Nếu gcd(x,n) =1, thì x(1pq−−)(1)/2≡1 (modn) (np−−q+5)/8 2) Nếu x ∈Qn , thì x modn là một căn bậc hai của x theo modn. ⎛⎞x 3) Nếu x là số nguyên có ⎜⎟= 1, và d =(n -p -q +5)/8, thì ⎝⎠n ⎧x,,khi x ∈Qn x2d modn = ⎨ ⎩nx−∉,.khixQn ⎛⎞2 4) Nếu p ≠ q (mod8) thì ⎜⎟= −1. Do đó, nhân một số ⎝⎠n nguyên x bất kỳ với 2 hay với 2-1modn đều đảo ng−ợc ký hiệu Jacobi của x. Ng−ời đọc có thể tự chứng minh lấy bổ đề trên. Bây giờ một sơ đồ chữ ký Rabin sửa đổi có thể đ−ợc xây dựng nh− sau : Tr−ớc hết ta xác định cho mỗi thực thể tham gia một cặp khoá K =(K’,K''), với khoá công khai K’ = n, khoá bí mật K'' = (p,q) hay = d = (n -p -q +5)/8,trong đóp và q là hai số nguyên tố có tính chất p ≡ 3(mod8) và q ≡ 7(mod8),n =p.q ;p và q đ−ợc chọn và giữ bí mật. Thực thể A có khoá K =(K’,K'') sẽ tạo chữ ký trên một văn bản x (x∈Zn , x ≤ (n -6)/16) bằng các b−ớc sau đây : a. Tính m =R(x) =16x +6. ⎛⎞m b. Tính ký hiệu Jacobi J = ⎜⎟. ⎝⎠n c. Nếu J =1 thì tính s =md modn, nếu J = -1 thì tính s =(m/2)d modn. d. s là chữ ký của A trên x. Việc kiểm thử chữ ký s của A bằng cách dùng khóa công khai n đ−ợc thực hiện bởi các b−ớc sau đây: a. Tính m*=s 2modn b. Nếu m*≡ 6(mod8), thì lấy m =m*, nếu m*≡ 3(mod8), thì lấy m =2m*, nếu m*≡ 7(mod8), thì lấy m =n -m*, 128
39. nếu m*≡ 2(mod8), thì lấy m =2(n -m *). c. Thử điều kiện m ≡ 6 (mod16), nếu sai thì bác bỏ chữ ký. d. Nếu điều kiện trên đúng thì lấy x = R -1(m) = (m -6)/16. (Theo định nghĩa của phép kiểm thử thì ta có thể viết điều d là: thuật toán kiểm thử xác nhận s là chữ ký của A trên văn bản x nếu x = R -1(m) = (m -6)/16). Ta có thể chứng minh tính hợp thức của các thuật toán ký và kiểm thử nh− sau: Các b−ớc tạo chữ ký b-c cho ta chữ ký Rabin của v =m hay v =m/2 tuỳ theo ký hiệu Jacobi bằng 1 hay không. Theo điều 4 của bổ đề 5.4.1, có đúng một khả năng hoặc m, hoặc m/2 có giá trị ký hiệu Jacobi bằng 1. Giá trị v đ−ợc ký là ≡ 3 hoặc ≡ 6 (mod8). Theo điều 3 của bổ đề đó, s 2modn =v hoặc = n -v là tuỳ theo v∈Qn hay không. Vì n ≡ 5 (mod8), có thể xác định một cách duy nhất một trong hai tr−ờng hợp đó. Thí dụ: Giả thử chọn p =19, q =31, do đó n =589 và d =68. A có khoá công khai n =589 và khoá bí mật d =68. Không gian ký gồm các giá trị của m ứng với các giá trị x = 0,1,2, ,32,33 cùng với các giá trị của ký hiệu Jacobi t−ơng ứng đ−ợc cho bởi bảng sau đây: m 6 22 54 70 86 102 118 134 150 ⎛⎞m -1 1 -1 -1 1 1 1 1 -1 ⎜⎟ ⎝⎠589 m 166 182 198 214 230 246 262 278 294 ⎛⎞m 1 -1 1 1 1 1 -1 1 -1 ⎜⎟ ⎝⎠589 m 326 358 374 390 406 422 438 454 470 ⎛m ⎞ -1 -1 -1 -1 -1 1 1 1 -1 ⎜⎟ ⎝⎠589 m 486 502 518 534 550 566 582 ⎛m ⎞ -1 1 -1 -1 1 -1 1 ⎜⎟ ⎝⎠589 Ta tạo chữ ký với thông báo x =12. Tính m = R(12) =198, ⎛⎞m ⎛198 ⎞ 68 ⎜⎟=⎜ ⎟=1, và s = 198 mod589 = 102. Chữ ký là s =102. ⎝⎠n ⎝589 ⎠ Dùng thuật toán kiểm thử ta có: m* = s 2modn = 1022mod589 =391. Vì m* ≡ 7 (mod8), ta lấy m =n -m*= 589-391=198. Cuối cùng, tính x = R -1(m) = (198-6)/16 =12, và chữ ký đ−ợc xác nhận. 129
40. 5.4.2. Sơ đồ chữ ký Fiat-Shamir. Mỗi sơ đồ chữ ký Fiat-Shamir sử dụng một hàm băm h : ∗ k Z2→ Z2,biến mọi dãy ký tự nhị phân x độ dài tuỳ ý thành một dãy có độ dài k bit, đ−ợc gọi là “tóm l−ợc” của x . Mỗi thực thể A tạo cho mình cặp khoá K =(K’,K'') bằng cách: chọn hai số nguyên tố khác nhau p và q, và đặt n =p.q ; sau đó chọn ∗ ngẫu nhiên k số nguyên khác nhau s1, , sk ∈ Zn , và tính với mỗi j −2 (1≤ j ≤ k) vj = sj modn. Xác định khoá bí mật K’ là bộ k (s1, , sk ), và khoá công khai K'' là gồm bộ k (v1, ,vk) và môđuyn n. ∗ k Lấy P = Z2 , A = Z2 ì Zn , và xác định các thuật toán ký và kiểm thử nh− sau: ∗ Để tạo chữ ký trên văn bản x ∈P = Z2 , A chọn ngẫu nhiên 2 một số nguyên d−ơng r ∈Zn , tính u =r modn , tính e =(e1, , ek ) = h(x & u), trong đó x & u là dãy ký tự nhị phân thu đ−ợc bằng cách nối ghép biểu diến nhị phân của số u tiếp sau biểu diễn nhị phân của số x. Chữ ký của A trên x đ−ợc định nghĩa là (e,s ), trong đó k sr= . se j ∏ j=1 j modn. Để kiểm thử (e,s ) có đúng là chữ ký của A trên x hay không, ta dùng khoá công khai (v1, ,vk) và môđuyn n để tính k ws= 2. ve j ∏ j=1 j modn , rồi tính e’ = h(x & w); và xác nhận (e,s ) đúng là chữ ký của A trên x khi và chỉ khi e = e’ . Dễ chứng minh rằng nếu (e,s ) là chữ ký của A trên x thì e = e’, và ng−ợc lại, tức các thuật toán ký và kiểm thử xác định nh− trên là hợp thức. 5.4.3. Sơ đồ chữ ký Schnorr. Sơ đồ chữ ký Schnorr cũng đ−ợc xây dựng t−ơng tự nh− sơ đồ Fiat-Shamir, nh−ng ở đây ta dùng một hàm băm một phía dựa trên bài toán khó tính lôgarit rời rạc. Mỗi thực thể A tạo cho mình cặp khoá K =(K’,K'') bằng cách: Chọn một số nguyên tố lớn p, một số nguyên tố q là −ớc số của ∗ p -1, một phần tử α cấp q của Z p , và một số a , 1≤ a ≤ q -1. Giữ K’=a là khoá bí mật , và công bố khoá công khai K'' = (p,q,α,r), trong đó r =α a modp. ∗ ∗ Chọn một hàm băm h : Z2 → Zq . Lấy P = Z2 và A = Zqqì Z . 130
41. ∗ Để ký trên một thông báo x ∈P =Z2 A chọn thêm một số k ngẫu nhiên k ∈ Zq và tính y =α modp, e = hx()& yvà s = ae+k modq. Chữ ký của A trên x đ−ợc xác định là cặp số (s, e). Để kiểm thử xem cặp số (s, e) có đúng là chữ ký của A trên x hay không, ta dùng khoá công khai K'' = (p,q,α,r) để tính v= α sr−e modp và eh′ = ()x& v, và xác nhận (s, e) đúng là chữ ký của A trên x khi và chỉ khi ee′ = . Ta có thể chứng minh rằng các thuật toán ký và kiểm thử xác định nh− ậy là hợp thức. Thực vậy, nếu chữ ký(s, e) đ−ợc ký bởi A trên x, thì v= α sr−e modp = α sα −ae modp =α k modp =y, do đó eh′ = ()x& v= hx(& y)=e. Ng−ợc lại, cũng dễ chứng tỏ rằng nếu e′ =e thì (s, e) đúng là chữ ký của A trên x. 5.5.Chữ ký không phủ định đ−ợc và không chối bỏ đ−ợc 5.5.1. Đặt vấn đề. Trong các phần tr−ớc ta đã trình bày một vài sơ đồ chữ ký điện tử ; trong các sơ đồ đó, việc kiểm thử tính đúng đắn của chữ kýlà do ng−ời nhận thực hiện. Nh− vậy, cả văn bản cùng chữ ký có thể đ−ợc sao chép và tán phát cho nhiều ng−ời mà không đ−ợc phép của ng−ời gửi. Để tránh khả năng đó, ng−ời ta đ−a ra các sơ đồ chữ ký không phủ định đ−ợc với một yêu cầu là chữ ký không thể đ−ợc kiểm thử nếu không có sự hợp tác của ng−ời ký. Sự hợp tác đó đ−ợc thực hiện thông qua một giao thức mời hỏi và trả lời giữa ng−ời nhận và ng−ời gửi (cũng là ng−ời ký), gọi là giao thức kiểm thử. Khi chữ ký đòi hỏi đ−ợc xác nhận bằng một giao thức kiểm thử thì một vấn đề khác lại nẩy sinh là làm thế nào để ngăn cản ng−ời ký chối bỏ một chữ ký mà anh ta đã ký bằng cách tuyên bố rằng chữ ký đó là giả mạo? Để đáp ứng yêu cầu đó, cần có thêm một giao thức chối bỏ, thông qua giao thức này ng−ời ký có thể chứng minh một chữ ký không phải của mình đúng thực là giả mạo. Nếu anh ta từ chối không tham gia giao thức đó thì có bằng chứng để chứng tỏ rằng anh ta không chứng minh đ−ợc đó là chữ ký giả mạo, tức không chối bỏ đ−ợc chữ ký của mình! Nh− vậy, một sơ đồ chữ ký không phủ định đ−ợc sẽ gồm ba phần : một thuật toán ký, một giao thức kiểm thử và một giao thức chối bỏ. 5.5.2. Sơ đồ chữ ký Chaum-van Antverpen. Sơ đồ chữ ký không phủ định đ−ợc đầu tiên đ−ợc Chaum và van Antverpen đề xuất năm 1989. Một chủ thể A chọn một số nguyên tố dạng Sophie Germain p =2q +1, trong đó q cũng là số 131
42. ∗ nguyên tố; chọn α ∈ Z p là một phần tử cấp q . Gọi G là nhóm con ∗ (theo phép nhân) cấp q sinh bởi α của Z p . Sơ đồ chữ ký Chaum - van Antverpen của A gồm có: P =A =G, cặp khoá K =(K’,K'') gồm có khoá bí mật K’ = a và khoá công khai K'' = (p,α, a, β), trong đó α là một số nguyên d−ơng < p -1, và β = α a modp. Thuật toán ký: A ký trên văn bản x ∈P =G với chữ ký a y = sigK′ ()x = x modp. Giao thức kiểm thử : Với văn bản x và chữ ký y ng−ời nhận B cùng ng−ời ký A thực hiện giao thức kiểm thử sau đây: ∗ e1e2 1. B chọn ngẫu nhiên hai số ee12,,∈Zq tính cy= .β modp và gửi c cho A, −1 2. A tính dc= a modq modp và gửi d cho B. 3. B chấp nhận y là chữ ký của A trên x nếu dx≡ ee12.mα odp . Giao thức chối bỏ: gồm các b−ớc sau đây: ∗ e1e2 1. B chọn ngẫu nhiên hai số ee12,,∈Zq tính cy= .β modp và gửi c cho A, −1 2. A tính dc= a modq modp và gửi d cho B, ee 3. B thử điều kiện d ≢ x 12.(α modp ). ∗ f1f2 4.B chọn tiếp hai số f12,,f∈Zq tính Cy= .β modp và gửi C cho A, −1 5. A tính DC= a modq modp và gửi D cho B, ff 6. B thử điều kiện D ≢ x 12.(α modp). 7. B kết luận y là chữ ký giả mạo, nếu ()dα−−ef21≡(Dαf2)e1(modp). 5.5.3. Tính hợp thức của các giao thức. Ta sẽ chứng minh hai định lý sau đây để chứng tỏ tính hợp thức của các giao thức kiểm thử và chối bỏ của sơ đồ chữ ký Chaum-van Antverpen. Định lý 5.5.1. a)Nếu y đúng là chữ ký của A trên x, tức y a ≡x modp,thì việc B chấp nhận y là chữ ký của A trên x theo giao thức kiểm thử là đúng. a b) Nếu y ≢x (modp), tức y không phải là chữ ký của A trên x, thì việc B, theo giao thức kiểm thử, chấp nhận y là chữ ký của A trên x, có thể xẩy ra với xác suất 1/q. a a−1 Chứng minh. a) Giả sử y ≡x modp. Khi đó, yx≡ (mod p ). (chú ý rằng tất cả các số mũ đều đ−ợc tính theo modq). Ta cũng có 132
43. −1 βαa ≡ (mod p ).Do đó, −1 −−11 dc≡≡a yea12β ea ≡xe1α e2(modp), và theo giao thức kiểm thử, B chấp nhận y là chữ ký của A trên x, việc chấp nhận đó là đúng. a b)Bây giờ giả thử y ≢x (modp). Tr−ớc hêt ta chú ý rằng mỗi lời mời hỏi c t−ơng ứng với đúng q cặp (e1, e2), vì y và β là các phần tử của nhóm nhân G cấp q. Khi A nhận đ−ợc câu hỏi c , A không có cách gì để biết là B đã dùng cặp (e1, e2) nào trong q cặp có thể đó. Ta a chứng minh rằng, do y ≢x (modp), nên trong q cặp đó chỉ có đúng một cặp thoả mãn đồng d− thức dx≡ e1α e2(modp). Thực vậy, ta có ijkl thể đặt cd==α ,,ααx=,y=α với i, j, k, l ∈ Zq ,vì α là phần tử sinh của G ,và hai đồng d− thức cy≡ ee12β (modp ) và dx≡ e1α e2(modp) t−ơng đ−ơng với hai ph−ơng trình il≡ e+ ae(modq ) 12 j ≡+kqee12(mod ). a Từ giả thiết y ≢x (modp) suy ra l – ak ≢ 0 (modq), tức định thức của hệ ph−ơng trình nói trên (với các ẩn số e1, e2) là ≢ 0 (modq). Nh− vậy, mỗi d ∈G là câu trả lời đúng (theo giao thức kiểm thử) chỉ với a một cặp (e1, e2) trong q cặp có thể. Vì vậy, nếu y ≢x (modp) , thì xác suất để B chấp nhận y là chữ ký của A trên x (theo giao thức) là bằng 1/q. Định lý đ−ợc chứng minh. Đối với giao thức chối bỏ, ta có định lý sau đây : a Định lý 5.5.2. a) Nếu y ≢x (modp), và cả A,B đều tuân theo giao thức chối bỏ, thì ()dα−ef21≡(Dα−f2)e1(modp), tức giao thức cho kết quả chính xác. a b) Nếu y ≡x modp, A và B đều tuân theo giao thức, và có ee d ≢ x 12.(α modp). ff D ≢ x 12.(α modp). Khi đó, đồng d− thức ()dα−−ef21≡(Dαf2)e1(modp) đúng với xác suất 1/q , tức nếu y đúng là chữ ký của A trên x, thì theo giao thức, B có thể kết luận rằng nó là giả mạo (một cách sai lầm) với xác suất 1/q. a Chứng minh. a) Giả thử y ≢ x (mod p ), và A,B cùng thực hiện giao thức chối bỏ. Do y không là chữ ký của A trên x nên B sẽ kiểm thử đúng các bất đồng d− thức trong các b−ớc 3 và 6 của giao thức. Vì β ≡ α a (modp), nên ta có −1 ()dyαβ−−ef21≡ ((e1e2)a αe2)f1(modp) 133
44. −−11 ≡ yae11fβαe2a f1 −e2f1(modp) −1 ≡ yea1f1(modp). T−ơng tự, ta cũng có −1 ()Dα − f21e≡ ye1af1(modp). Nh− vậy, đồng d− thức ở điểm 7 của giao thức đ−ợc nghiệm đúng, và kết luận y là chữ ký giả mạo của A trên x là chính xác, không thể bác bỏ đ−ợc. b) Bây giờ giả thiết y≡ xa (modp), và A, B cùng thực hiện 1/ee1− 2/e1 giao thức chối bỏ. Đặt xd0 = α modp , ta có a ae//1−ae2e1 ee12a//e1−ae2e1 a xd0 ≡ .α ≢ ()x αα ≡ x≡ y(modp). Theo điểm b) trong định lý 5.5.1, B có thể chấp nhận y là chữ ký của A trên x0 , tức là có đồng d− thức f1f2 Dx≡ 0 α (modp), với xác suất 1/q. Nh−ng đồng d− thức đó t−ơng đ−ơng với đồng d− thức ()dα−ef21≡(Dα−f2)e1(modp), tức đồng d− thức này cũng có thể xẩy ra với xác suất 1/q. Định lý đ−ợc chứng minh. Ta chú ý rằng trong giao thức chối bỏ, cặp (e1, e2) đ−ợc sử a dụng để tạo ra x0 với x0 ≢y(modp); còn cặp (f1, f2) đ−ợc dùng để kiểm thử xem y có là chữ ký của A trên x0 hay không. Thí dụ minh hoạ. Chọn p = 467, q =233 (p = 2q +1), α =4 là ∗ phần tử sinh của một nhóm con G cấp 233 của Z467 . Chọn a =101, khi đó ta có β =α amodp = 4101mod467 =449. A có cặp khoá K =(K’,K'') với K’ =101, và K'' = (467, 4, 449). Giả thử A ký trên văn bản x =119 với chữ ký y = 119101mod467 =129. 1)B có thể dùng giao thức kiểm thử để biết y có đúng là chữ ký của A trên x hay không nh− sau: B chọn ngẫu nhiên e1=38, e2=397, và tính c =13; A sẽ trả lời lại bằng d =9. B thử điều kiện dx≡ ee12.mα odp , tức là 9 ≡ 11938.4397(mod467). Đồng d− thức đó đúng. B chấp nhận 129 đúng là chữ ký của A trên văn bản 119. 2) Bây giờ ta thử thực hiện giao thức chối bỏ. Giả thử A gửi văn bản x =286 với chữ ký y = 83. B chọn ngẫu nhiên e1=45, e2=237, rồi tính c =305 và gửi cho A; A trả lời lại bằng d =109. B thử điều ee kiện d≢ x 12.(α modp ), điều kiện đó đ−ợc thoả mãn vì 134
45. 109≠149(=28645.4237mod467). B lại tiếp tục phần sau của giao thức bằng cách chọn ngẫu nhiên f1 =125, f2 =9, và tính C =270, gửi cho A, ff A trả lời lại bằng D =68. B lại thử điều kiện D≢ x 12.(α modp ) , điều kiện này cũng đ−ợc thoả mãn vì 68≠25(=286125.49mod467). Bây giờ B lại thử điều kiện cuối cùng của giao thức bằng cách tính (dα −ef21) ≡≡(109.4−237) )125 188(mod 467) (Dα − fe21) ≡≡(68.4−94) 5 188(mod 467) Hai giá trị đó bằng nhau. B có thể kết luận y không phải là chữ ký của A trên x với xác suất sai lầm là 1/233! Thí dụ này đ−ợc trình bày với mục đích minh hoạ, nên chỉ sử dụng các số nguyên tố p, q bé cho dễ tính. Trong thực tế ứng dụng, để bảo đảm tính an toàn, ta phải dùng các số p, q rất lớn, chẳng hạn phải là các số có biểu diễn nhị phân cỡ 512 bit, khi đó ta có q ≥ 2510, tức là 1/q ≤ 2-510, một xác suất rất bé, có thể bỏ qua; và vì vậy, các yêu cầu đối với các giao thức kiểm thử và giao thức chối bỏ nh− đề cập đến trong phần đặt vấn đề (5.5.1) có thể xem là đ−ợc thoả mãn. 135
46. CHƯƠNG VI Các sơ đồ x−ng danh và xác nhận danh tính 6.1. Vấn đề x−ng danh. Trong ch−ơng tr−ớc ta đã thấy các kỹ thuật mật mã có thể đ−ợc ứng dụng để xây dựng nhiều giải pháp an toàn cho vấn đề xác nhận các thông báo cùng với ng−ời gửi trên các mạng truyền tin công cộng. Trong ch−ơng này ta sẽ xét việc ứng dụng cũng các kỹ thuật đó cho bài toán xây dựng các sơ đồ x−ng danh và xác nhận danh tính, cũng là một bài toán quan trọng và th−ờng gặp trong mọi hoạt động giao l−u thông tin, đặc biệt giao l−u qua mạng. Việc x−ng danh và xác nhận danh tính của một ng−ời th−ờng là cần thiết trong những tình huống nh−: - Để rút tiền từ các máy rút tiền tự động (ATM), ta cần x−ng danh bằng cách dùng một thẻ rút tiền cùng với một số PIN (số x−ng danh cá nhân) của mình - Để mua hàng hoặc thanh toán một khoản tiền qua mạng điện thoại, ta cần thông báo số thẻ tín dụng (cùng ngày hết hạn) của mình. - Để truy nhập vào một máy tính trên một mạng, ta cần khai báo tên ng−ời dùng cùng mật hiệu (password) của mình. - v.v Trong thực tế cuộc sống, việc x−ng danh theo thói quen th−ờng không đòi hỏi tính an toàn, chẳng hạn các số PIN, mật khẩu th−ờng không có gì để bảo đảm là đ−ợc giữ kín, ng−ời ngoài không biết đ−ợc. Tuy nhiên, cuộc sống càng ngày càng đ−ợc tin học hoá, phần lớn các giao dịch đ−ợc thực hiện trên các mạng tin học, việc xem th−ờng các yêu cầu về an toàn trong các khâu x−ng danh và xác nhận danh tính là không thể tiếp tục đ−ợc; cần phải có những giải pháp bảo đảm tính an toàn cho các hoạt động đó. Mục tiêu an toàn của việc x−ng danh là bảo đảm sao cho khi “nghe” một chủ thể A x−ng danh với một chủ thể B, bất kỳ một ai 136
47. khác A cũng không thể sau đó mạo mhận mình là A, kể cả chính B cũng không thể mạo x−ng mình là A sau khi đ−ợc A x−ng danh với mình. Nói cách khác, A muốn chứng minh để đ−ợc đối tác xác nhận danh tính của mình mà không để lộ bất cứ thông tin nào về việc chứng minh danh tính đó. Việc x−ng danh th−ờng phải thông qua một giao thức hỏi- đáp nào đó, qua giao thức đó, để B có thể xác nhận danh tính của A, B đặt cho A một câu hỏi; A phải trả lời, trong trả lời đó A phải chứng tỏ cho B biết là A có sở hữu một bí mật riêng A mới có, điều đó thuyết phục B tin chắc rằng ng−ời trả lời đúng là A và do đó xác nhận danh tính của A. Vấn đề khó ở đây là A phải làm cho B biết là A có sở hữu một bí mật chỉ riêng A mới có, nh−ng lại không đ−ợc lộ cho B biết cái bí mật riêng A mới có đó là cái gì. Mặt khác, để cho việc “A có sở hữu một bí mật của riêng A” đó là đáng tin (dù là không biết) thì cần đ−ợc chứng thực bởi một bên thứ ba nào đó,chẳng hạn bởi một cơ quan đ−ợc uỷ thác (trusted authority). Tất nhiên cơ quan đ−ợc uỷ thác này cũng không biết bản thân bí mật của A, nh−ng biết và chứng nhận A là chủ sở hữu của một yếu tố công khai mà việc A sử dụng nó chứng tỏ A có cái bí mật nói trên. Trong tiết ngay sau đây ta sẽ giới thiệu một sơ đồ x−ng danh điển hình để minh hoạ các ý t−ởng nói trên. 6.2. Sơ đồ x−ng danh Schnorr. Trong sơ đồ x−ng danh này có sự tham gia của một cơ quan đ−ợc uỷ thác mà ta ký hiệu là TA. TA sẽ chọn các tham số cho sơ đồ x−ng danh nh− sau: - một số nguyên tố lớn p sao cho bài toán tính lôgarit rời rạc theo modp là rất khó; và một −ớc số nguyên tố q của p -1 (ng−ời ta khuyên nên chọn p ≥ 2512 và q ≥ 2140 ). ∗ - một phần tử α ∈Z p có cấp q (một phần tử α nh− vậy có thể lấy là một luỹ thừa bậc (p -1)/q của một phần tử nguyên thuỷ theo modp. - một tham số an toàn t sao cho q ≥ 2t. Có thể lấy t =40. - TA chọn cho mình một sơ đồ chữ ký gồm một thuật toán ký(bí mật) sigTA và một thuật toán kiểm thử (công khai)verTA. - một hàm băm an toàn (một phía và không va chạm mạnh). Ta giả thiết là mọi thông tin đều đ−ợc “tóm l−ợc” bởi hàm băm tr−ớc khi đ−ợc ký; tuy nhiên trong mô tả sau đây để cho đơn giản ta sẽ bỏ qua các b−ớc sử dụng hàm băm. Các tham số p, q, α, thuật toán kiểm thử verTA và hàm băm đều có thể đ−ợc công bố công khai. 137
48. Bây giờ, một chủ thể A cần x−ng danh sẽ yêu cầu TA cấp cho mình một chứng chỉ. Thủ tục cấp chứng chỉ cho A đ−ợc tiến hành nh− sau: 1.TA xác lập các thông tin về danh tính của A nh− họ,tên, ngày sinh, số chứng minh hoặc hộ chiếu, v.v d−ới dạng một dãy ký tự mà ta ký hiệu là I A hay ID(A). 2. A chọn bí mật một số ngẫu nhiên a (0≤ a ≤ q-1), tính v = α −a mod p và chuyển số v cho TA. 3. TA tạo chữ ký s =sigTA(IA, v) và cấp cho A chứng chỉ C(A) = (ID(A), v, s ). Nh− vậy, chứng chỉ mà TA cấp cho A gồm (IA, v) và chữ ký của TA trên thông tin (IA, v) đó. Chú ý rằng TA cấp chứng chỉ cho A mà hoàn toàn không biết gì về thông tin bí mật của A là số a. Bây giờ, với chứng chỉ C(A) đó, A có thể x−ng danh với bất kỳ đối tác B nào bằng cách cùng B thực hiện một giao thức xác nhận danh tính nh− sau: 1. A chọn thêm một số ngẫu nhiên k (0≤ k ≤ q-1), tính γα= k modp , và gửi cho B các thông tin C(A) và γ. 2. B kiểm thử chữ ký của TA trong chứng chỉ C(A) bởi hệ thức verTA(ID(A), v, s) =đúng. Kiểm thử xong, B chọn một số ngẫu nhiên r (1≤ r ≤ 2t ) và gửi r cho A. 3. A tính y =k +ar modq và gửi y cho B. 4. B thử điều kiện γα≡ yvr(modp) và nếu điều kiện đó đ−ợc thoả mãn thì xác nhận danh tính của A. Thực hiện giao thức đó, A sẽ chứng minh đ−ợc danh tính của mình, vì α yrvv≡ ααk++arr≡karα−ar≡αk(modp) ≡ γ (modp), tức điều kiện mà B cần thử là đúng. Sơ đồ x−ng danh cùng với giao thức xác nhận danh tính nh− mô tả ở trên có các tính chất đáp ứng các yêu cầu nh− đề ra từ phần đặt vấn đề ở tiết 6.1. Điều vừa chứng minh ở trên chứng tỏ rằng nếu A tuân thủ giao thức thì B xác nhận danh tính của A là đúng (B tin rằng A quả thực có sở hữu một bí mật a, dù B cũng không biết cái bí mật a đó là số nào). Bây giờ ta xét khả năng một ng−ời O muốn giả danh A để giao dịch với B. Khả năng thứ nhất là O tạo ra một chứng chỉ giả mạo với danh tính của A, một chứng chỉ nh− vậy có dạng 138
49. C’(A) = (ID(A), v, s’), trong đó v ≠ v. Để tạo ra một chứng chỉ nh− vậy thì O phải tạo ra đ−ợc s là chữ ký của TA trên (ID(A), v), O không biết thuật toán ký sigTA nên không thể tạo ra chữ ký đúng của TA đ−ợc, và nếu lấy s’ là một chữ ký giả mạo, thì khi thực hiện điểm 2 của giao thức xác nhận danh tính thể nào B cũng phát hiện ra. Khả năng thứ hai là O vẫn dùng chứng chỉ thật C(A) của A, tự chọn một số k và tính số γ t−ơng ứng theo điểm 1 của giao thức xác nhận danh tính. Vấn đề ở đây là khi B gửi đến số r , O phải trả lời lại bằng một số y sao cho điều kiện γα≡ yvr(modp) đ−ợc nghiệm đúng. Điều này xem ra là rất khó, ít nhất cũng khó nh− là O biết bí mật về số a của A vậy. Thực vậy, giả sử O có khả năng nói trên, khi đó ta cho hai lần hỏi r1 và r 2 O sẽ có hai trả lời y1 và y2, và ta có γα≡≡yr11vvαy2r2(mod p) , từ đó suy ra α yy12−≡ vr2−r1( modp). Vì v = α -a, ta có y1 – y2 ≡ a(r2 – r1) (modq). t t Vì q là số nguyên tố > 2 và 0< ⎟r2 - r1⎟ < 2 , nên gcd(r2 - r1, q) =1, và −1 O có thể tính đ−ợc ay=−()12y(r2−r1)modq . Thí dụ : Lấy p =88667, q = 1031 và t =10. Phần tử α = 70322 có cấp q ∗ trong Z p . Giả sử A chọn số mũ bí mật là a = 755, khi đó v = 13136. A và B có thể thực hiện giao thức xác định danh tính nh− sau: A chọn k = 543, và tính γ =70322543mod88667 =84109 rồi gửi γ cho B. Giả sử B gửi r =1000 cho A, A trả lời lại bằng y =k +ar modq = =543+755.1000mod1031 = 851. B thử điều kiện γα≡ yvr(modp), trong tr−ờng hợp này là: 84109 ≡ 70322851131361000 (mod 88667), đó là đồng d− thức đúng. B xác nhận danh tính của A. Bây giờ vẫn với các tham số trên, giả thiết O có khả năng trả lời đúng hai câu hỏi r1=1000 và r2=19 của B bằng y1=851 và y2=454. Khi đó O có thể tính đ−ợc −1 ay=−()12y(r2−r1)modq = (851-454)(19-1000)-1 mod1031 = 755, đúng là số bí mật của A. Sơ đồ x−ng danh Schnorr, với giao thức xác nhận danh tính nh− định nghĩa ở trên, là có tính chất đầy đủ (việc có bí mật a bảo đảm A chứng minh đ−ợc danh tính của mình), và đúng đắn ( việc giả danh A thành công cũng khó nh− biết bí mật của A); tuy nhiên nh− vừa trình bày trong thí dụ trên, sơ đồ đó ch−a phải là an toàn, 139
50. việc giả danh là khó nếu O không hề biết gì về sơ đồ x−ng danh đó, chứ nếu, chẳng hạn, O đã đ−ợc A x−ng danh với ít nhất hai lần (tức hai lần biết đ−ợc hai cặp số (r1, y1) và (r2, y2)) thì có khả năng O phát hiện đ−ợc bí mật của A, nh− vậy việc x−ng danh của A không còn an toàn nữa! Để khắc phục điểm yếu đó của sơ đồ Schnorr, Okamoto đã đề xuất một sửa đổi làm cho sơ đồ trở nên an toàn, sửa đổi này dựa trên tính khó của một bài toán đặc biệt về tính lôgarit rời rạc. Ta trình bày trong tiết sau đây sơ đồ đ−ợc sửa đổi đó. 6.3. Sơ đồ x−ng danh Okamoto. Cũng nh− đối với sơ đồ Schnorr, sơ đồ x−ng danh Okamoto cần có một cơ quan uỷ thác TA để cấp chứng chỉ cho các ng−ời tham gia. TA chọ tr−ớc các số nguyên tố p và q nh− đối với sơ đồ ∗ Schnorr. Sau đó, TA chọn hai số αα12,∈ Z p ,cùng có cấp q . Giá trị c = log α (tức giá trị c sao cho α c = α ) đ−ợc giữ tuyệt mật đối α1 2 12 với mọi ng−ời tham gia, kể cả A; nói cách khác, ta giả thiết rằng việc tính ra c là cực kỳ khó đối với bất kỳ ai (chẳng hạn, A,O, hoặc thậm chí liên minh của A và O, ). Thủ tục cấp chứng chỉ cho A đ−ợc tiến hành nh− sau: 1. TA xác lập các thông tin về danh tính của A d−ới dạng một dãy ký tự mà ta ký hiệu là I A hay ID(A). 2. A chọn bí mật hai số ngẫu nhiên a1, a2 (0≤ a1, a2 ≤ q-1), tính −−aa12 v = αα12mod p , và chuyển số v cho TA. 3. TA tạo chữ ký s =sigTA(IA, v) và cấp cho A chứng chỉ C(A) = (ID(A), v, s ). Bây giờ, với chứng chỉ C(A) đó, A có thể x−ng danh với bất kỳ đối tác B nào bằng cách cùng B thực hiện một giao thức xác nhận danh tính nh− sau: 1. A chọn thêm hai số ngẫu nhiên k1,k2 (0≤ k1,k2 ≤ q-1), tính kk12 γα= 12αmodp , và gửi cho B các thông tin C(A) và γ. 2. B kiểm thử chữ ký của TA trong chứng chỉ C(A) bởi hệ thức verTA(ID(A), v, s) =đúng. Kiểm thử xong, B chọn một số ngẫu nhiên r (1≤ r ≤ 2t ) và gửi r cho A. 3. A tính y1 =k1 +a1r modq , y2 =k2 +a2r modq , và gửi y1,y2 cho B. 4. B thử điều kiện 140
51. yy12r γα≡ 12αv (modp) và nếu điều kiện đó đ−ợc thoả mãn thì xác nhận danh tính của A. Thực hiện giao thức đó, A sẽ chứng minh đ−ợc danh tính của mình, vì y12y r k1++a1r k2ar2−a1r −ar2 αα12v ≡ α1 α2 α1α2(modp) k1k2 ≡ α1α2(modp) ≡ γ (modp) tức điều kiện mà B cần thử là đúng. Nh− vậy, do biết cặp số bí mật (a1, a2), nên A có thể thực hiện thông suốt giao thức xác nhận để chứng minh danh tính của mình. Ng−ợc lại, một ng−ời khác A, do không biết cặp số bí mật (a1, a2), nên khó có khả năng tính đúng đ−ợc (y1,y2) để trả lời B ở b−ớc 3 của giao thức, tức là không v−ợt qua đ−ợc sự kiểm thử của giao thức để mạo nhận mình là A. Bây giờ giả sử có một ng−ời O có thể thực hiện thông suốt giao thức xác nhận để có thể đ−ợc mạo nhận là A, chẳng hạn ít nhất hai lần. Điều đó có nghĩa là O biết đ−ợc hai số r ≠ s và hai cặp số (y1,y2), (z1,z2) sao cho yy12rz1z2s γα≡12αv≡α1α2v(modp). Đặt −1 by11=−()z1(r−s)modq, −1 bq2 =−()yz22(r−s)mod , ta sẽ đ−ợc −b1−b2 v ≡ α1α2(modp), do đó −bb12−−a1−a2 α12αα≡ 1α2(modp), tức là ab− 11 b2−a2 α1≡ α2(modp). Giả thiết rằng O và A liên minh với nhau, khi đó biết đ−ợc cả các số a1, a2, b1, b2. Nếu giả thiết (a1, a2) ≠ (b1, b2) thì a2 ≠ b2 , và -1 (b2 - a2) modq tồn tại, và lôgarit rời rạc c đ−ợc tính bởi ca==log α ( −b)(b−a)−1 modq. α1 21122 Nh− vậy, nếu O có thể thực hiện thông suốt giao thức xác nhận để đ−ợc mạo nhận là A thì khi O và A liên minh với nhau có thể tìm đ−ợc khá dễ dàng lôgarit rời rạc c. Nh−ng từ đầu ta đã giả thiết việc tìm ra c là cực kỳ khó đối với bất kỳ ai (là A, là O, thậm chí là liên minh của A và O, ), nên cũng sẽ cực kỳ khó để O thực hiện đ−ợc thông suốt giao thức xác nhận với mục đích mạo x−ng là A. Vậy là ta đã chứng minh đ−ợc tính an toàn của sơ đồ x−ng danh 141
52. Okamoto với giao thức xác nhận danh tính nh− mô tả ở trên. Trong chứng minh đó còn một số chỗ tinh tế cần đuợc bổ sung thêm, chẳng hạn nh− vì sao có thể giả thiết (a1, a2) ≠ (b1, b2), thực ra ng−ời ta đã chứng minh đ−ợc rằng xác suất của khả năng (a1, a2) = (b1, b2) là rất bé, không đáng kể. Tuy nhiên, để đơn giản trình bày, xin phép đ−ợc bỏ qua một vài chi tiết chứng minh tinh tế đó. 6.4. Sơ đồ x−ng danh Guillou-Quisquater. Sơ đồ Guillou-Quisquater cũng đ−ợc xây dựng theo cùng một cách thức nh− các sơ đồ Schnorr và Okamoto kể trên, nh−ng bài toán khó mà ta dựa vào ở đây không phải là bài toán tính lôgarit rời rạc mà là bài toán RSA. Sơ đồ cũng cần có sự tham gia của một cơ quan uỷ thác TA để cấp chứng chỉ cho các ng−ời tham gia. TA chọn hai số nguyên tố lớn p và q và tính tích n =pq, giữ bí mật p ,q và công khai n. Các tham số đó đ−ợc chọn sao cho bài toán phân tích n thành thừa số là rất khó. TA cũng chọn thêm một số b là số nguyên tố có độ lớn khoảng 240 nh− là một tham số an toàn. Số b cũng đ−ợc xem là số mũ thoả mãn điều kiện RSA, nghĩa là việc tính v =ub modn là dễ, nh−ng việc tính ng−ợc u từ v là rất khó, nếu không biết p,q. Thủ tục cấp chứng chỉ cho một ng−ời tham gia A đ−ợc tiến hành nh− sau: 1.TA xác lập các thông tin về danh tính của A d−ới dạng một dãy ký tự mà ta ký hiệu là I A hay ID(A). 2. A chọn bí mật một số ngẫu nhiên u (0≤ u ≤ n-1), tính vn= ()u −1 b mod, và chuyển số v cho TA. 3. TA tạo chữ ký s =sigTA(IA, v) và cấp cho A chứng chỉ C(A) = (ID(A), v, s ). Nh− vậy, chứng chỉ mà TA cấp cho A gồm (IA, v) và chữ ký của TA trên thông tin (IA, v) đó. Chú ý rằng TA cấp chứng chỉ cho A mà có thể không biết gì về thông tin bí mật của A là số u. Bây giờ, với chứng chỉ C(A) đó, A có thể x−ng danh với bất kỳ đối tác B nào bằng cách cùng B thực hiện một giao thức xác nhận danh tính nh− sau: 1. A chọn thêm một số ngẫu nhiên k (0≤ k ≤ n-1), tính γ = k b modn , và gửi cho B các thông tin C(A) và γ. 2. B kiểm thử chữ ký của TA trong chứng chỉ C(A) bởi hệ thức verTA(ID(A), v, s) =đúng. Kiểm thử xong, B chọn một số ngẫu nhiên r (1≤ r ≤ b -1 ) và gửi r cho A. 142