Giáo trình Lý thuyết mật mã - Chương 6: Các sơ đồ chữ kí số - Nguyễn Hoàng Cương

Nội dung text: Giáo trình Lý thuyết mật mã - Chương 6: Các sơ đồ chữ kí số - Nguyễn Hoàng Cương

1. Vietebooks Nguyễn Hoàng Cương Ch−ơng 6 Các sơ đồ chữ kí số 6.1 giới thiệu. Trong ch−ơng này, chúng ta xem xét các sơ đồ chữ kí số (còn đ−ợc gọi là chữ kí số ). Chữ kí viết tay thông th−ờng trên tàI liệu th−ờng đ−ợc dùng để xác ng−ời kí nó. Chữ kí đ−ợc dùng hàng ngày chẳng hạn nh− trên một bức th− nhận tiền từ nhà băng, kí hợp đồng Sơ đồ chữ kí là ph−ơng pháp kí một bức điện l−u d−ới dang điện từ. Chẳng hạn một bức điện có ký hiệu đ−ợc truyền trên mạng máy tinh. Ch−ơng trình này nghiên cứu vài sơ đồ chữ kí. Ta sẽ thảo luận trên một vàI khác biệt cơ bản giửa các chữ kí thông th−ờng và chữ kí số. Đầu tiên là một vấn đề kí một tài liệu. Với chữ kí thông th−ờng, nó là một phần vật lý của tài liệu. Tuy nhiên, một chữ kí số không gắn theo kiểu vật lý vào bức điện nên thuật toán đ−ợc dùng phải ”không nhìn thấy” theo cách nào đó trên bức điện. Thứ hai là vấn đề về kiểm tra. Chữ kí thông th−ờng đ−ợc kiểm tra bằng cách so sánh nó với các chữ kí xác thực khác. ví dụ, ai đó kí một tấm séc để mua hàng, ng−ời bán phải so sánh chữ kí trên mảnh giấy với chữ kí nằm ở mặt sau của thẻ tín dụng để kiểm tra. Dĩ nhiên, đây không phải là ph−ơg pháp an toàn vì nó dể dàng giả mạo. Mắt khác, các chữ kí số có thể đ−ợc kiểm tra nhờ dùng một thuật toán kiểm tra công khai. Nh− vậy, bất kỳ ai cũng có thể kiểm tra d−ợc chữ kí số. Việc dùng một sơ đồ chữ kí an toàn có thể sẽ ngăn chặn d−ợc khả năng giả mạo. Sự khác biệt cơ bản khác giữa chữ kí số và chữ kí thông th−ờng bản copy tài liệu đ−ợc kí băng chữ kí số đồng nhất với bản gốc, còn copy tài liệu có chữ kí trên giấy th−ờng có thể khác với bản gốc. Điều này có nghĩa là phải cẩn thận ngăn chăn một bức kí số khỏi bị dung lạI. Ví dụ, Bob kí một bức điện xác nhận Alice có khả năng làm điều đó một lần. Vì thế, bản thân bức điện cần chứa thông tin (chẳng hạn nh− ngày tháng) để ngăn nó khỏi bị dung lại. Một sơ đồ chữ kí số th−ờng chứa hai thành phần: thuật toán kí và thuật toán xác minh. Bob có thể kí điện x dùng thuật toán kí an toàn. Chữ kí sig(x) nhận đ−ợc có thể kiểm tra bằng thuật toán xác minh công khai ver. Khi cho tr−ớc cặp (x,y), thuật toán xác minh có giá trị TRUE hay FALSE tuỳ thuộc vào chữ kí đ−ợc thực nh− thế nào. D−ới đây là định nghĩa hình thức của chữ kí: Định nghĩa 6.1 Trang 1
2. Vietebooks Nguyễn Hoàng Cương Một sơ đồ chữ kí số là bộ 5( P,A, K,S,V) thoả mãn các điều kiện d−ới đây: 1. P là tập hữu hạn các bức điện có thể. 2. A là tập hữu hạn các chữ kí có thể. 3. K không gian khoá là tập hữu hạn các khoá có thể. 4. Với mỗi K thuộc K tồn tạI một thuật toán kí sigk ∈ S và là một thuật toán xác minh verk∈ V. Mỗi sigk : P → A và verk: Pìa →{true,false} là những hàm sao cho mỗi bức điện x∈ P và mối chữ kí y∈ a thoả mãn ph−ơng trình d−ới đây. True nếu y=sig(x) verk False nếu y# sig(x) Với mỗi k thuộc K hàm sigk và verk là các hàm thơì than đa thức. Verk sẽ là hàm công khai sigk là mật. Không thể dể dàng tính toán để giả mạo chữ kí của Bob trên bức điện x. Nghĩa là x cho tr−ớc, chỉ có Bob mới có thể tính đ−ợc y để verk = True. Một sơ đồ chữ kí không thể an toàn vô điều kiện vì Oscar có thể kiểm tra tất cả các chữ số y có thể có trên bức điện x nhờ dùng thuât toán ver công khai cho đến khi anh ta tìm thấy một chữ kí đúng. Vi thế, nếu có đủ thời gian. Oscar luôn luôn có thể giả mạo chữ kí của Bob. Nh− vậy, giống nh− tr−ờng hợp hệ thống mã khoá công khai, mục đích của chúng ta là tìm các sơ đồ chữ kí số an toan về mặt tính toán. Xem thấy rằng, hệ thống mã khoá công khai RSA có thể dùng làm sơ đồ chữ kí số, Xem hình 6.1. Nh− vậy, Bob kí bức điện x dùng qui tắc giải mã RSA là dk,. Bob là ng−ời tạo ra chữ kí vì dk = sigk là mật. Thuật toán xác minh dùng qui tắc mã RSA ek. Bất kì ai củng có xác minh chữ kí vi ek đ−ợc công khai. Chú ý rằng, ai đó có thể giả mạo chữ kí của Bob trên một bức điện “ ngẩu nhiên” x bằng cách tìm x=ek(y) với y nào đó; khi đó y= sigk(x). Một pháp xung quanh vấn đề khó khăn này là yêu cầu bức điện ch−a đủ phần d− để chữ kí giả mạo kiểu này không t−ơng ứng với bức điện đây nghĩa là x trừ một xác suất rất bé. Có thể dùng các hàm hash trong việc kết nối với các sơ đồ chữ kí số sẽ loại trừ đ−ợc ph−ơng pháp giả mạo này (các hàm hash đ−ợc xét trong ch−ơng 7). Hình 6.1 sơ đồ chữ kí RSA Trang 2
3. Vietebooks Nguyễn Hoàng Cương Cho n= pq, p và q là các số nguyên tố. Cho p =a= Zn và định nghĩa p= {(n,p,q,a,b):=n=pq,p và q là nguyên tố, ab ≡ 1(mod( φ (n))) }. Các giá trị n và b là công khai, ta địng nghĩa : a sigk(x)= x mod n và ver (x,y)= true ⇔ x ≡ y b (mod n) k (x,y ∈ Z ) n Cuối cùng, ta xét tóm tắt các kết hợp chữ kí và mã khoá công khai. Giả sử rằng, Alice tính toán ch− kí của ta y= sigAlice(x) và sau đó mã cả x và y bằng hàm mã khoá công khai eBob của Bob, khi đó cô ta nhận đ−ợc z = eBob(x,y). Bản mã z sẽ đ−ợc truyền tới Bob. Khi Bob nhận đ−ợc z, anh ta sẽ tr−ớc hết sẽ giải mã hàm dBob để nhận đ−ợc (x,y). Sau đó anh ta dung hàm xác minh công khai của Alice để kiểm tra xem verAlice(x,y) có bằng True hay không. Song nếu đầu tiên Alice mã x rồi sau đó mới kí tên bản mã nhận đ−ợc thì sao?. Khi đó cô tính : y= sigAlice(eBob(x)). Alice sẽ truyền cặp (z,y) tới Bob. Bob sẽ giải mã z, nhận x và sau đó xác minh chữ kí y trên x nhờ dùng verAlice. Một vấn đề tiểm ẩn trong biện pháp này là nếu Oscar nhận đ−ợc cặp (x,y) kiểu này, đ−ợc ta có thay chữ kí y của Alice bằng chữ kí của mình. , y = sigOscar(eBob(x)). (chú ý rằng,Oscar có thể kí bản mã eBob(x) ngay cả khi anh ta không biết bản rõ x). Khi đó nếu Oscar truyền(x, y’ ) đến Bob thì chữ kí Oscar đ−ợc Bob xác minh bằng verOscar và Bob có thể suy ra rằng, bản rõ x xuất phát từ Oscar. Do khó khăn này, hầu hết ng−ời sử dụng đ−ợc khuyến nghị nếu kí tr−ớc khi mã. 6.2 sơ đồ chữ kí ELGAMAL Sau đây ta sẽ mô tả sơ đồ chữ kí Elgamal đã từng d−ới thiệu trong bài báo năm 1985. Bản cả tiến của sơ đồ này đã đ−ợc Viện Tiêu chuẩn và Công Nghệ Quốc Gia Mỹ (NIST) chấp nhận làm chữ kí số. Sơ đồ Elgamal (E.) đ−ợc Trang 3
4. Vietebooks Nguyễn Hoàng Cương thiết kế với mục đích dành riêng cho chữ kí số, khác sơ đồ RSA dùng cho cả hệ thống mã khoá công khai lẫn chữ kí số. Sơ đồ E, là không tất định giống nh− hệ thống mã khoá công khai Elgamal. Điều này có nghĩa là có nhiều chữ kí hợp lệ trên bức điện cho tr−ơc bất kỳ. Thuật toán xác minh phải cố khải năng chấp nhận bất kì chữ kí hợp lệ khi xác thực. Sơ đồ E. đ−ợc môt tả trên hình 6.2 Nếu chữ kí đ−ợc thiết lập đúng khi xác minh sẽ thành công vì : γ δ γ γ β γ ≡ αa αk (mod p) ≡ αx(mod p) là ở đây ta dùng hệ thức : a γ+ k δ ≡ x (mod p-1) Hình 6.2 sơ đồ chữ kí số Elgamal. Cho p là số nguyên tố sao cho bài toán log rời rạc trên Zp là khó và giả * * sử α ∈ Zn là phần tử nguyên thuỷ p = Zp , a = Zp ì Zp-1 và định nghĩa : a K ={(p,α ,a,β ):β ≡ α (mod p)}. Giá trị p,α ,β là công khai, còn a là mật. Với K = (p,α ,a,β ) và một số ngẫu nhiên (mật) k∈ Zp-1. định nghĩa : Sigk(x,y) =(γ ,δ), trong đó γ = αk mod p -1 và δ =(x-a) k mod (p-1). Với x,γ ∈ Zp và δ ∈ Zp-1 , ta định nghĩa : γ δ x Ver(x,γ ,δ ) = true ⇔ β γ ≡ α (mod p). Bob tính chữ kí bằng cách dùng cả gía trị mật a (là một phần của khoá) lẫn số ngẫu nhiên mật k (dùng để kí lên bức điện x ). Việc xác minh có thực hiện duy nhất bằng thông báo tin công khai. Chúng ta hãy xét một ví dụ nhỏ minh hoạ. Ví dụ 6.1 Trang 4
5. Vietebooks Nguyễn Hoàng Cương Giả sử cho p = 467, α =2,a = 127; khi đó: a β = α mod p = 2127 mod 467 = 132 Nếu Bob muốn kí lên bức điện x = 100 và chọn số ngẫu nhiên k =213 (chú ý là UCLN(213,466) =1 và 213-1 mod 466 = 431. Khi đó γ =2213 mod 467 = 29 và δ =(100-127 ì 29) 431 mod 466 = 51. Bất kỳ ai củng có thể xác minh chữ kí bằng các kiểm tra : 13229 2951 ≡ 189 (mod 467) và 2100 ≡ 189 (mod 467) Vì thế chữ kí là hợp lệ. Xét độ mật của sơ đồ chữ kí E. Giả sử, Oscar thử giả mạo chữ kí trên bức điện x cho tr−ớc không biết a. Nếu Oscar chọn γ và sau đó thử tìm giá trị x -γ. δ t−ơng ứng, anh ta phải tính logarithm rời rạc logγ α β Mặt khác, nếu đầu tiên ta chọn δ và sau đó thử tim γ và thử giải ph−ơng trình: γ δ β γ ≡ αx(mod p). để tìm γ. Đây là bài toán ch−a có lời giải nào: Tuy nhiên, d−ờng nh− nó ch−a đ−ợc gắn với đến bài toán đã nghiên cứu kĩ nào nên vẫn có khả năng có cách nào đó để tính δ và γ đồng thời để (δ, γ)là một chữ kí. Hiện thời không ai tìm đ−ợc cách giải song củng ai không khẳng định đ−ợc rằng nó không thể giải đ−ợc. Nếu Oscar chọn δ và γ và sau đó tự giải tìm x, anh ta sẽ phảI đối mặt với bài toán logarithm rời rạc, tức bài toán tính logα ??? Vì thế Oscar không thể kí một bức điện ngẫu nhiên bằng biện pháp này. Tuy nhiên, có một cách để Oscar có thể kí lên bức điện ngẫu nhiên bằng việc chọn γ, δ và x đồng thời: giả thiết i và j là các số nguyên 0 ≤ i ≤ p-2, 0 ≤ j ≤ p-2 và UCLN(j,p-2) = 1. Khi đó thực hiện các tính toán sau: i j γ = α β mod p δ = -γ j-1 mod (p-1) x = -γ i j-1 mod (p-1) trong đó j-1 đ−ợc tính theo modulo (p-1) (ở đây đòi hỏi j nguyên tố cùng nhau với p-1). Trang 5
6. Vietebooks Nguyễn Hoàng Cương Ta nói rằng (γ, δ )là chữ kí hợp lệ của x. Điều này đ−ợc chứng minh qua việc kiểm tra xác minh : ???? Ta sẽ minh hoạ bằng một ví dụ : Ví dụ 6.2. Giống nh− ví dụ tr−ớc cho p = 467, α = 2, β =132. Giả sữ Oscar chọn i = 99,j = 179; khi đó j-1 mod (p-1) = 151. Anh ta tính toán nh− sau: γ = 299132197 mod 467 = 117 δ =-117 ì151 mod 466 = 51. x = 99 ì 41 mod 466 = 331 Khi đó (117, 41) là chữ kí hợp lệ trên bức điện 331 h− thế đã xác minh qua phép kiểm tra sau: 132117 11741 ≡ 303 (mod 467) và 2331 ≡ 303 (mod 467) Vì thế chữ kí là hợp lệ. Sau đây là kiểu giả mạo thứ hai trong đó Oscar bắt đầu bằng bức điện đ−ợc Bob kí tr−ớc đây. Giả sử (γ, δ ) là chữ kí hợp lệ trên x. Khi đó Oscar có khả năng kí lên nhiều bức điện khác nhau. Giả sử i, j, h là các số nguyên, 0 ≤ h, i, j ≤ p-2 và UCLN (h γ - j δ, p-1) = 1. Ta thực hiện tính toán sau: λ = γh αi βj mod p μ = δλ(hγ -jδ)-1 mod (p-1) x, = λ(hx+iδ ) -1 mod (p-1), trong đó (hγ -jδ)-1 đ−ợc tính theo modulo (p-1). Khi đó dễ dàng kiểm tra điệu kiện xác minh : μ β λ λ ≡ αx’ (mod p) vì thế (λ, μ)là chữ kí hợp lệ của x’. Cả hai ph−ơng pháp trên đều tạo các chữ kí giả mạo hợp lệ song không xuất hiện khả năng đối ph−ơng giả mạo chữ kí trên bức điện có sự lựu chọn của chính họ mà không phải giải bài toán logarithm rời rạc, vì thế không có gì nguy hiểm về độ an toàn của sơ đồ chữ kí Elgamal. Trang 6
7. Vietebooks Nguyễn Hoàng Cương Cuối cùng, ta sẽ nêu vài cách có thể phái đ−ợc sơ đồ này nếu không áp dụng nó một cách cẩn thận (có một số ví dụ nữa về khiếm khuyết của giao thức, một số trong đó là xét trong ch−ơng 4). Tr−ớc hết, giá trị k ngẫu nhiên đ−ợc dùng để tính chữ kí phải giữ kín không để lộ. vì nếu k bị lộ, khá đơn giản để tính : A = (x-k γ )δ-1 mod (p-1). Dĩ nhiên, một khi a bị lộ thì hệ thống bị phá và Oscar có thể dễ dang giả mạo chữ kí. Một kiểu dung sai sơ đồ nữa là dùng cùng giá trị k để kí hai bức điện khác nhau. điều này cùng tạo thuận lợi cho Oscar tinh a và phá hệ thống. Sau đây là cách thực hiện. Giả sử (γ, δ1) là chữ kí trên x1 và (γ, δ2) là chữ kí trên x2. Khi đó ta có: γ β γδ1 ≡ αx1 (mod p) γ δ và β γ 2 ≡ αx2(modp). Nh− vậy δ δ αx1-x2 ≡ α 1- 2 (mod p). Nếu viết γ = αk, ta nhận đ−ợc ph−ơng trình tìm k ch−a biết sau. x -x k(δ -δ ) α 1 2 ≡ α 1 2 (mod p) t−ơng đ−ơng với ph−ơng trình x1- x2 ≡ k( δ1- δ2) (mod p-1). Bây giờ giả sử d =UCLN(δ1- δ2, p-1). Vì d | (p-1) và d | (δ1-δ2) nên suy ra d | (x1-x2). Ta định nghĩa: ’ x = (x1- x2)/d ’ δ = (δ1- δ2)/d p’ = ( p -1 )/d Khi đó đồngd− thức trở thành: x’ ≡ k δ’ (mod p’ ) vì UCLN(δ’, p’ ) = 1,nên có thể tính: ε = (δ’)-1 mod p’ Khi đó giá trị k xác định theo modulo p’ sẽ là: Trang 7
8. Vietebooks Nguyễn Hoàng Cương k = x’ ε mod p’ Ph−ơng trình này cho d giá trị có thể của k k = x’ ε +i p’ mod p với i nào đó, 0 ≤ i ≤ d-1. Trong số d giá trị có có thế này, có thể xác định đ−ợc một giá trị đúng duy nhất qua việc kiểm tra điều kiện γ ≡ αk (mod p) 6.3 chuẩn chữ kí số. Chuẩn chữ kí số(DSS) là phiên bản cải tiến của sơ đồ chữ kí Elgamal. Nó đ−ợc công bố trong Hồ Sơ trong liên bang vào ngày 19/5/94 và đ−ợc làm chuẩn vào 1/12/94 tuy đã đ−ợc đề xuất từ 8/91. Tr−ớc hết ta sẽ nêu ra những thay đổi của nó so với sơ đồ Elgamal và sau đó sẽ mô tả cách thực hiện nó. Trong nhiều tinh huống, thông báo có thể mã và giải mã chỉ một lần nên nó phù hợp cho việc dùng với hệ mật Bất kì (an toàn tại thời điểm đ−ợc mã). Song trên thực tế, nhiều khi một bức điện đ−ợc dùng làm một tài liệu đối chứng, chẳng hạn nh− bản hợp đồng hay một chúc th− và vì thế cần xác minh chữ kí sau nhiều năm kể từ lúc bức điện đ−ợc kí. Bởi vậy, điều quan trọng là có ph−ơng án dự phòng liên quan đến sự an toàn của sơ đồ chữ kí khi đối mặt với hệ thống mã. Vì sơ đồ Elgamal không an toàn hơn bài toán logarithm rời rạc nên cần dung modulo p lớn. Chắc chắn p cần ít nhất là 512 bít và nhiều ng−ời nhất trí là p nên lấy p=1024 bít để có độ an toàn tốt. Tuy nhiên, khi chỉ lấy modulo p =512 thì chữ kí sẽ có 1024 bít. Đối với nhiều ứng dụng dùng thẻ thông minh thì cần lại có chữ kí ngắn hơn. DSS cải tiến sơ đồ Elgamal theo h−ớng sao cho một bức điện 160 bít đ−ợc kí bằng chữ * kí 302 bít song lại p = 512 bít. Khi đó hệ thống làm việc trong nhóm con Zn kích th−ớc 2160. Độ mật của hệ thống dựa trên sự an toàn của việc tìm các * logarithm rời rạc trong nhóm con Zn . Sự thay đổi đầu tiên là thay dấu “ - “ bằng “+” trong định nghĩa δ, vì thế: δ = (x +α γ )k-1 mod (p-1) Trang 8
9. Vietebooks Nguyễn Hoàng Cương thay đổi kéo theo thay đổi điều kiện xác minh nh− sau: γ δ αx β ≡ γ (mod p) (6.1) Nếu UCLN (x + αγ, p-1) =1thì δ-1 mod (p-1) tồn tại và ta có thể thay đổi điều kiện (6.1) nh− sau: -1 -1 αxδ βγδ ≡ γ (mod )p (6.2) Đây là thay đổi chủ yếu trong DSS. Giả sử q là số nguyên tố 160 bít sao cho q | (q-1) và α là căn bậc q của một modulo p. (Dễ dàng xây dựng một α nh− (p-1)/q vậy: cho α0 là phần tử nguyên thuỷ của Zp và định nghĩa α = α0 mod p). Khi đó β và γ cũng sẽ là căn bậc q của 1. vì thế các số mũ Bất kỳ của α, β và γ có thể rút gọn theo modulo q mà không ảnh h−ởng đến điều kiện xác minh (6.2). Điều rắc rối ở đây là γ xuất hiện d−ới dạng số mũ ở vế trái của (6.2) song không nh− vậy ở vế phải. Vì thế, nếu γ rút gọn theo modulo q thì cũng phải rút gọn toàn bộ vế trái của (6.2) theo modulo q để thực hiện phép kiểm tra. Nhận xét rằng, sơ đồ (6.1) sẽ không làm việc nếu thực hiện rút gọn theo modulo q trên (6.1). DSS đ−ợc mô tả đầy đủ trong hinh 6.3. Chú ý cần có δ ≡ 0 (mod q) vì giá trị δ-1 mod q cần thiết để xác minh chữ kí (điều này t−ơng với yêu cầu UCLN(δ, p-1 ) =1 khi biến đổi (6.1) thành (6.2). Nếu Bob tính δ ≡ 0 (mod q) theo thuật toán chữ kí, anh ta sẽ loại đi và xây dựng chữ kí mới với số ngẫu nhiên k mới. Cần chỉ ra rằng, điều này có thể không gần vấn đề trên thực tế: xác xuất để δ ≡ 0 (mod q) chắc sẽ xảy ra cở 2- 160 nên nó sẽ hầu nh− không bao giờ xảy ra. D−ới đây là một ví dụ minh hoạ nhỏ Hình 6.3. Chuẩn chữ kí số. Trang 9
10. Vietebooks Nguyễn Hoàng Cương Giả sử p là số nguyên tố 512 bít sao cho bài toán logarithm rời rạc trong Z khong Giải đ−ợc, cho p là số nguyê n tố 160 bít là −ớc của (p-1). p Giả thiết α ∈ Zp là căn bậc q của 1modulo p: Cho p =Z p . a = Zqì Z p và định nghĩa : a A = {(p,q,α ,a,β ) : β ≡ α (mod p)} các số p, q, α và β là công khai, có a mật. Với K = (p,q, α ,a,β )và với một số ngẫu nhiên (mật) k ,1 ≤ k ≤ q-1, ta định nghĩa: sigk (x,k) = (γ ,δ) k trong đó γ =(α mod p) mod q và δ = (x +a γ )k-1 mod q Với x ∈ Zp và γ ,δ ∈ Zq , qua trình xác minh sẽ hoàn toàn sau các tính toán : -1 e1= xδ mod q -1 e2= γδ mod q e1 e2 verk(x, γ, δ) = true ⇔( α β mod p) mod q = γ Ví dụ 6.3: Giả sử q =101, p = 78 q+1 =7879.3 là phần tử nguyên thuỷ trong Z7879 nên ta có thể lấy: α = 378 mod 7879 =170 Giả sử a =75, khi đó : β = αa mod 7879 = 4576 Bây giờ giả sữ Bob muốn kí bức điện x = 1234 và anh ta chọn số ngẫu nhiên k =50, vì thế : k-1 mod 101 = 99 khi đó γ =(17030 mod 7879) mod 101 = 2518 mod 101 = 94 và δ = (1234 +75 ì 94) mod 101 = 96 Chữ kí (94, 97) trên bức điện 1234 đ−ợc xác minh bằng các tính toán sau: δ-1 = 97-1 mod 101 =25 Trang 10
11. Vietebooks Nguyễn Hoàng Cương e1 = 1234 ì 25mod 101 = 45 e2 = 94 ì 25 mod 101 =27 (17045 456727 mod 7879)mod =2518 mod 101 = 94 vì thế chữ kí hợp lệ. Khi DSS đ−ợc đề xuất năm 1991, đã có một vài chỉ trích đ−a ra. Một ý kiến cho rằng, việc xử lý lựa chọn của NIST là không công khai. Tiêu chuẫn đã đ−ợc Cục An ninh Quốc gia (NSA) phát triển mà không có sự tham gia của khôi công nghiệp Mỹ. Bất chấp những −u thế của sơ đồ, nhiều ng−ời đã đóng chặt cửa không tiếp nhận. Còn những chỉ trích về mặt kĩ thuật thì chủ yếu là về kích th−ớc modulo p bị cố định = 512 bít. Nhiều ng−ời muốn kích th−ớc này có thể thay đổi đ−ợc nếu cần, có thể dùng kích cỡ lớn hơn. Đáp ứng những đòi hỏi này, NIST đã chọn tiêu chuẩn cho phép có nhiều cở modulo, nghĩa là cỡ modulo bất kì chia hết cho 64 trong phạm vi từ 512 đến 1024 bít. Một phàn nàn khác về DSS là chữ kí đ−ợc tạo ra nhanh hơn việc xác minh nó. Trong khi đó, nếu dùng RSA làm sơ đồ chữ kí với số mũ xác minh công khai nhỏ hơn (chẳng hạn = 3) thì có thể xác minh nhanh hơn nhiều so với việc lập chữ kí. Điều này dẫn đến hai vấn đề liên quan đến những ứng dụng của sơ đồ chữ kí: 1.Bức điện chỉ đ−ợc kí một lần, song nhiều khi lại cần xác minh chữ kí nhiều lần trong nhiều năm. Điều này lại gợi ý nhu cầu có thuật toán xác minh nhanh hơn. 2.Những kiểu máy tính nào có thể dùng để kí và xác minh ?. Nhiều ứng dụng, chẳng hạn các thẻ thông minh có khả năng xử lý hạn chế lại liên lạc với máy tính mạnh hơn. Vi thế có nhu cầu nh−ng thiết kế một sơ đồ để có thực hiện trên thẻ một vài tính toán. Tuy nhiên, có những tình huống cần hệ thống mình tạo chữ kí, trong những tình huống khác lại cần thẻ thông minh xác minh chữ kí. Vì thế có thể đ−a ra giải pháp xác định ở đây. Sự đáp ứng của NIST đối với yêu cầu về số lần tạo xác minh chữ kí thực ra không có vấn đề gì ngoài yêu cầu về tốc độ, miễn là cả hai thể thực hiện đủ nhanh. Trang 11
12. Vietebooks Nguyễn Hoàng Cương 6.4 chữ kí một lần Trong phần, này chúng ta mô tả cách thiết lập đơn giản một sơ đồ chữ kí một lần từ hàm một chiều. Thuật ngữ “một lần” có nghĩa là bức điện đ−ợc kí chỉ một lần (dĩ nhiên chữ kí có thể xác minh nhiều lần tuỳ ý). Sơ đồ mô tả là sơ đồ chữ kí Lamport nêu hình 6.4. Sơ đồ làm viêc nh− sau: Bức điện đ−ợc kí là một bức điện nhị phân k bít. Một bít đ−ợc kí riêng biệt nhau. Giá trị zi,j t−ơng ứng với bít thứ i của bức điện có giá trị j (j =0,1). Mỗi zi,j là ảnh h−ởng đến yi,j d−ới tác động của hàm một chiều f. Bít thứ i của bức điện đ−ợc kí nhờ là ảnh gốc(nghịch ảnh - priemage) yi,j của zi,j (t−ơng ứng với bít thứ i của bức điện ). Việc xác minh chỉ đơn giản là kiểm tra xem mỗi phần tử trong chữ kí có là ảnh gốc của phần tử Hình 6.4. Sơ đồ chữ kí Lamport Cho k là số nguyên d−ơng và cho p = {0,1}k . Giả sử f:Y ặ Z là hàm một chiều và cho a = Yk . Cho y ∈ Y đ−ợc chọn ngẫu nhiên. i,j 1 ≤ i ≤ k, j =0,1 và giả sử zi,j = f(yi,j ). Khoá K gồm 2k giá trị y và 2k giá trị z. Các giá trị của i giữ bí mật trong khi các giá trị của z công khai. Với K = (y ,z : 1 ≤ i ≤ k,j =0,1) , ta định nghĩa : i,j i,j sigk( x1 . xk ) = (????tự đánh vào) và verk(x1 . xk ,a1 . ak) = true ⇔ f(ai) =????tự đánh vào khoá công khai thích hợp hay không. Sau đây sẽ minh hoạ sơ đồ bằng việc xem xét một thực hiện dùng hàm mũ f(x) = αx mod p. α là một phần tử nguyên thuỷ modulo p. Ví dụ 6.4 7879 là số nguyên tố và 3 là phần tử nguyên thuỷ thuộc Z7879. Định nghĩa: f(x) = 3x mod 7879 Giã sử Bob muốn kí một bức điện có 3 bít. Anh ta chọn 6 số tự nhiên (mật) Trang 12
13. Vietebooks Nguyễn Hoàng Cương y1,0 = 5831 y2,1 = 2467 y1,1 = 735 y3,0 = 4285 y2,0 = 803 y3,1 = 6449 Khi đó, anh ta tính các ảnh của y d−ới hàm f z1,0 = 2009 z2,1 = 4721 z1,1 = 3810 z3,0 = 268 z2,0 = 4672 z3,1 = 5731 Các ảnh của z này đ−ợc công khai. Bây giờ giả sử Bob muốn ký bức điện x = (1, 1, 0) chữ kí trên x là: (y1,1, y2,1, y3,0) = (735, 2467, 4285) Để xác minh chữ kí, chỉ cần tính toán nh− sau: 3735 mod 7879 = 3810 34675 mod 7879 = 4721 24285 mod 7879 = 268 Vì thế, chữ kí hợp lệ. Oscar không thể giả mạo chữ kí vì anh ta không thể đảo đ−ợc hàm một chiều f(x) để có các giá trị y mật. Tuy nhiên, sơ đồ đ−ợc dùng để kí chỉ một bức điện. Bởi vì nếu cho tr−ớc chữ kí của 2 bức điện khác nhau. Oscar sẽ dễ dàng xây dựng chữ kí cho bức điện khác. Ví dụ, giã sử các bức điện (0, 1, 1) và (1, 0, 1) đều đ−ợc kí bằng cùng một sơ đồ. Bức điện (0, 1, 1) có chữ kí (y1,0, y2,1, y3,1) còn bức điện (1,0,1) có chữ kí (y1,1, y2,0, y3,1). Nếu cho tr−ớc 2 chữ kí này, Oscar có thể xây dựng các chữ kí của bức điện (1,1,1) là (y1,1, y2,1, y3,1) và chữ kí cho bức điện (0,0,10 là (y1,0, y2,0, y3,1). Mặc dù sơ đồ này hoàn toàn tốt song nó không đ−ợc sử dụng trong thực do kích th−ớc chữ kí. Ví dụ, nếu ta dùng hàm số mũ modulo nh− trong ví dụ ở trên thì yêu cầu an toàn đòi hỏi p dài ít nhất 512 bít. Điều này, có nghĩa mỗi bít của bức điện chữ kí dùng 512 bít. Kết quả chữ kí dài hơn bức điện 512 lần. Bây giờ xét một cải tiến của Bos và Chaum cho phép chữ kí ngăn hơn một chút song không giảm độ mật. Trong sơ đồ Lamport, lý do Oscar không thể giả mão chữ kí trên bức điện (thứ hai) khi biết chữ kí ở bức điện là: các Trang 13
14. Vietebooks Nguyễn Hoàng Cương ảnh của y (t−ơng ứng với một bức điện ) không bao giờ là tập con của các ảnh của y (t−ơng ứng với bức điện khác). Giả sử ta có tập b gồm các tập con của B sao cho B1 ⊆ B2 chỉ khi B1 = B2 với mọi B1, B2 ∈ b. Khi đó b đ−ợc gọi là thoả mãn tính chất Sperner. Cho tr−ớc một tập B có lực l−ợng n chẵn, khi đó kích th−ớc cực đại của tập b ⎛2n⎞ gồm các tập con B có tính chất Sperner là ⎜ ⎟ . Điều này dễ dàng nhận ⎜n ⎟ ⎝ ⎠ đ−ợc bằng cách lấy tất cả các tập con n của B: rõ ràng không có tập con n nào nhận đ−ợc trong tập con n khác Bây giờ, giã sử ta muốn ki một bức điện k bít nh− tr−ớc đây, ta chọn n đủ lớn để. ⎛2n⎞ 2k ≤ ⎜ ⎟ ⎜n ⎟ ⎝ ⎠ k Cho | B | =n và giả sữ b chỉ tập các tập con n của B. Giả sử φ:{0,1} ặ b là đơn ánh trong công khai đă biết. Khi đó, có thể liên kết mỗi bức điện có thể với một con n trong b. Ta sẽ có 2n giá trị của y, và 2n giá trị của z và mỗi bức điện đ−ợc kí bằng n ảnh của y. Hình 6.5 mô tả đầy đủ sơ đồ Bos- chaum. Hình 6.5 Sơ đồ chữ kí Bos - chaum. Cho k là số nguyên d−ơng và giả sử p={0,1}k. Cho n là số nguyên k ⎛2n⎞ sao cho 2 ≤ ⎜ ⎟ và B là tập có lực l−ợng n và cho ⎝n ⎠ φ: {0,1}k ặ b là một đơn ánh , trong đó b là tập tất cả các con n của B. Giả sử f: YặZ là hàm một chiều và A = Zn. Cho ?????????????? Trang 14
15. Vietebooks Nguyễn Hoàng Cương Ưu điểm của sơ đồ Bos- chaum là các chữ kí ngăn hơn sơ đồ Lamport. ⎛8⎞ Ví dụ, ta muốn ký một bức điện 6 bit (k = 6). Vì 26 =64 và ⎜ ⎟ =70 nên có ⎝2⎠ thể lấy n =4 và bức điện 6 bit đ−ợc kí bằng 4 giá trị của y so với 6 của sơ đồ Lamport. Nh− vậy khoá k sẽ ngắn hơn, nó gồm 8 giá trị của z so với 12 của sơ đồ Lamport. Sơ đồ Bos-Chaum đòi hỏi hàm đơn ánh φ để kết hợp tập con n của tập 2n với mỗi x nhị phân bội k (x1 . xk). Ta sẽ đ−a ra một thuật toán đơn giản để thực hiện điều này (hinh 6.6). Ví dụ, áp dụng thuật toán này với x = (0,1,0,0,1,1) sẽ tạo ra. φ(x) = {2,4,6,8} Nói chung, n trong sơ đồ Bos-Chaum lớn bao nhiêu so với k ?. Ta cần ⎛2n⎞ thoả mãn bất ph−ơng trình 2k ≤ ⎜ .⎟ Nếu đánh giá hệ số của nhị thức ⎝n ⎠ ⎛2n⎞ ⎜ ⎟ = (2n)!/(n!)2 ⎜2 ⎟ ⎝ ⎠ Hình 6.6 Tính φ trong sơ đồ Bos - chaum 1. X = k 2i-2 ∑i−1 xi 2. φ(x) = 0 3. t = 2n 4. e = n 5. While t > 0 do 6. t = t - 1 ⎛t ⎞ 7. if x > ⎜ ⎟ then ⎜e⎟ ⎝ ⎠ ⎛t ⎞ 8. x = x - ⎜ ⎟ ⎝e⎠ 9. e = e -1 10. φ(x) = φ(x) ∪ {t+1} Trang 15
16. Vietebooks Nguyễn Hoàng Cương 2n băng công thức Stirling 2 / π n . Sau vài phép biến đổi đơn giản, bất kỳ đẳng thức trở thành k ≤ 2n -log2 (πn)/2 Một cách gần đúng, n ≈ k/2. Nh− vậy, ta đã giảm đ−ợc khoảng 50% kích th−ớc chữ kí bằng sơ đồ Bos - chaum. 6.5 các Chữ kí không chối đ−ợc Các chữ kí không chối đ−ợc do Chaum và Antwerpen đ−a ra từ năm 1989. Chúng có vài đặc điểm mới. Nguyên thuỷ nhất trong các chữ kí này là chữ kí không thể xác minh đ−ợc nếu không hợp tác với ng−ời ký là Bob. Nh− vậy sẽ bảo đ−ợc Bob tr−ớc khả năng các tài liệu đ−ợc anh ta ký bị nhân đôi và phân phối bằng ph−ơng pháp điện tử mà không có sự đồng ý của anh ta. Việc xác minh đ−ợc thực hiên bằng giao thức yêu cầu và đáp ứng (Challege and repotocol). Song liệu có cần sự hợp tác của Bob để xác minh chữ kí (nhằm ngăn chặn Bob từ chối không nhận đã ký tr−ớc đó) không? Bob có thể truyền thống chữ kí hợp lệ là giả mạo và từ chối xác minh nó, hoặc thực hiện giao thức theo cách để chữ kí không thể đ−ợc xác minh. Để ngăn chặn tình huống này xảy ra, sơ đồ chữ kí không chối đ−ợc đã kết hợp giao thức từ chối (theo giao thức này, Bob có thể chứng minh chữ kí là giả mạo). Nh− vậy, Bob sẽ có khả năng chứng minh tr−ớc toà rằng chữ kí bị lừa dối trên thực tế là giả mạo. (Nếu anh ta không chấp nhận tham vào giao thức từ chối, điều này đ−ợc xem nh− bằng chứng chứng tỏ chữ kí trên thực tế là thật). Nh− vậy, sơ đồ chữ kí không chối đ−ợc gồm 3 thành phần: thuật toán ký, giao thức xác minh và giao thức từ chối (disavowal). Đầu tiên ta sẽ đ−a ra thuật toán ký và giao thức xác minh của sơ đồ chữ kí không từ chối đ−ợc của chaum - VanAntwerpen trên hình 6.7. Xét vai trò của p và q trong sơ đồ này. Sơ đồ tồn tại trong Zp; tuy vậy * cần có khả năng tính toán theo nhóm nhân con G của Zp có bậc nguyên tố. Củ thể, ta có khả năng tính đ−ợc các phần tử nghịch đảo Modulo |G| - là lý do giải thích tại sao |G| phải là số nguyên tố. Để tiện lợi, lấy p=2q+1, q là số Trang 16
17. Vietebooks Nguyễn Hoàng Cương nguyên tố. Theo cách này, nhóm con G lớn đến mức có thể là điều đáng mong muốn vì cả bức điện lẫn chữ kí đều là phần tử thuộc G. Tr−ớc hết, cần chứng minh rằng, Alice sẽ chấp nhận một chữ kí hợp lệ. Trong các tính toán sau đây, tất cả các số mũ đ−ợc rút gọn theo modulo q. Đầu tiên, nhận xét: -1 d ≡ cα (mod p) Hình 6.7. Sơ đồ chữ kí không chấp nhận chaum - Van Antwerpen. Cho p =2q +1 là số nguyên tố sao cho q là nguyên tố và bài toán logarithm rời rạc trong Zp là không thể giải đ−ợc. Giả sử α ∈ Zp là phần tử a bậc q. Cho 1 ≤ a ≤ q-1 và đ−ợc định nghĩa β = α mod p. Giả sử G biểu nhóm * con bội Z bậc q (G là gồm các thặng d− bình th−ờng modulo p). Cho p p = A = G và định nghĩa : a K ={p, α, a, β ): β ≡α (mod p)} Các giá trị p, α và β công khai, còn a mật. Với k = (p, α, a, β ) và x ∈G , định nghĩa : y = sig (x) = xa mod p k Với x,y ∈ G, việc xác minh đ−ợc thực hiện qua giao thức sau: * 1. Alice chọn e1,e2 ngẫu nhiên, e1,e2∈ Zp 2. Alice tính c = ye1βe2 mod p và gửi cho no đến Bob 3. Bob tính d = ca mod q mod p và gữi nó cho Alice 4. Alice chấp nhận y là chữ kí hợp lệ khi và chỉ khi e e d ≡x 1α 2 (mod p) Vì: β ≡ αa (mod p) Ta có: ????Chua viết T−ơng tự y = xa (mod p) có nghĩa là: Trang 17
18. Vietebooks Nguyễn Hoàng Cương ?????????? ch−a viết Vì thế d ≡ xe1αe2 (mod p) nh− mong muốn. D−ới đây là một ví dụ nhỏ. Ví dụ 6.5 Giả sử lấy p = 467, vì 2 là phần tử nguyên thuỷ nên 22 =4 là phần tử sinh của G, các thặng d− bình ph−ơng modulo 467. Vì thế ta có thể lấy α =4. Giả thiết a = 101, khi đó β = αa mod 467 =499 Bob sẽ ký bức điện x= 119 với chữ ký y = 119101 mod 467 = 129 Bây giờ giả sử Alice muốn xác minh chữ ký y, cô ta chọn các số ngẫu nhiên chẳng hạn e1=38, e2=397. Cô tính c=13, ngay lúc đó Bob sẽ trả lời với d =9,Alice kiểm tra câu trả lời bằng việc xác minh xem: 11938 4397 =9 (mod 467) vì thế Alice chấp nhận chữ ký là hợp lệ. Tiếp theo, ta chứng minh rằng, Bob không thể lừa Alice chấp nhận chữ ký giả mạo (Fradulart) nh− là chữ ký hợp lệ trừ một xác suất rất bé. Kết quả này không phụ thuộc vào bất kỳ giả thiết tính toán nào, điều đó có nghĩa độ an toàn là vô điều kiện. Định lý 6.1 Nếu y ≡ xa (mod p) thì Alice sẽ nhận y nh− la một chữ ký hợp lệ trên x với xác xuất 1/q. Chứng minh Tr−ớc hết, nhânj xét rằng mỗi yêu cầu (challenge) c có thể t−ơng ứng chính xác với q cặp đ−ợc sắp (e1,e2) (đó là vì cả y lẫn β đều là các phần tử của nhóm nhân G có bậc nguyên tố q). Bây giờ, khi Bob nhận đ−ợc yêu cầu c, anh ta không có cách nào để biết về q cặp đ−ợc sắp (e1,e2) có thể mà Alice đã Trang 18
19. Vietebooks Nguyễn Hoàng Cương dùng để xây dựng c. Ta nói rằng, nếu y ≡ xa (mod p) thì đáp dụng ứng (respond) d ∈G mà Bob có thể là sẽ chỉ phủ hợp chính xác một trong q cặp đ−ợc (e1,e2). Vì α sinh ra G, nên ta có thể viết một phần tữ bất kỳ thuộc G nh− một số mũ của α, trong đó số mũ đ−ợc xác minh duy nhất theo modulo q. Vì thế i j k l có thể viết c =α ,d =α , x =α và y =α với i, j, k, l ∈ Zp và mọi phép tính số học là theo modulo q. Xét 2 đồng d− thức sau: c ≡ ye1βe2(mod p) d ≡ xe1αe2(mod p) Hệ thống này t−ơng đ−ơng hệ đồng thức sau: i ≡ l e1 +a e2 (mod q) j ≡ k e1 + e2 (mod q) Bầy giờ giả thiết rằng: y ≡ xa (mod p) Comment [NVH1]: nên rút ra : l ≡a k (mod q) Vì thế, ma trận hệ số của các đồng d− thức theo modulo q này có định thức khác 0 và nh− vây tồi tại nghiệm duy nhất cho hệ thống thống. Nghiã là, mỗi d∈G là một đáp ứng với một trong q cặp (e1,e2) đ−ợc sắp có thể. Hệ thống quả là, xác suất để Bob đ−a cho Alice một đáp ứng(trả lời) d cần đ−ợc xác minh đúng bằng 1/q. Định lý đ−ợc chứng minh. Hình 6.8. Thủ tục từ chối. 1. Alice chọn e ,e một cách ngẫu nhiên, e ,e ∈Z * 1 2 1 2 q e1 e2 2. Alice tính c = y β mod p và gửi nó cho Bob. 3. Bob tính d = ? 4. Alice xác minh xem d có ≡ xe1αe2(mod p) không * 5. Alice chọn f1,f2 ngẫu nhiên , f1,f2∈ Zq f1 f2 6. Alice tính C = y β mod p và gửi cho Bob 7. Bob tính D = ???????? f f 8. Alice xác minh xem D có ≡ x 1α 2(mod p) không 9. Alice kết luận rằng y là giả mạo khi và chỉ khi (d α-e2)f1 ≡ (D α-f2)e1 (mod p) Trang 19
20. Vietebooks Nguyễn Hoàng Cương Bây giờ quay trở lại giao thức từ chối. Giao thức này gồm hai 2 thực hiện giao thức xác minh và đ−ợc nêu trong hình 6.8. Các b−ớc 1- 4 và 5- 8 gồm 2 lần thực hiện không thành công giao thức xác minh. B−ớc 9 b−ớc “tính kiểm tra phù hợp” cho Alice xác định xem liệu có phải đang lập các câu trả lời của anh ta theo thứ tự chỉ ra hay không. D−ới đây là ví dụ minh hoạ. Ví dụ 6.6 Nh− tr−ớc đây, giả sử p = 467, α = 4, a = 101, và β = 449. Giả thiết bức điện x = 286 đ−ợc ký y = 83 và Bob muốn thiết phục Alice rằng chữ ký không hợp lệ. Giả sử Alice bắt đầu bằng việc chọn các giá trị ngẫu nhiên e1=45, e2=237. Alice tính c =305 và Bob trả lời d = 109. Sau đó Alice tính 2861254237 mod 467 =149 Vì 149 # 109 nên Alice thực hiện b−ớc 5 của giao thức. Bây giờ giả sử Alice chọn giá trị ngẫu nhiên f1= 125, f2= 9. Alice tính C = 270 và Bob trả lời với D =68. Alice tính 18612549 mod 467 =25 Vì 25 # 68 nên Alice tiếp tục sang b−ớc 9 của giao thức kiểm tra tính phù hợp. B−ớc kiểm tra này thành công vì: (109 ì4-9)125 ≡ 188 (mod 467) và (68 ì4-9)45 ≡ 188 (mod 467) Vì thế Alice tin rằng chữ ký không hợp lệ. Bây giờ, ta phải chứng minh hai vấn đề: 1. Bob có thể thuyết phục Alice rằng, chữ ký không hợp lệ là giả mạo. 2. Bob không thể là Alice tin rằng chữ ký không hợp lệ là giả mạo trừ một xác suất rất bé. Định lý 6.2 Nếu y ≡ xa (mod p) và cả Alice lẫn Bob thực hiện theo giao thức từ chối thì (d α-e2)f1 ≡ (D α-f2)e1 (mod p) Chứng minh: Dùng các yếu tố d ≡ ??? Trang 20
21. Vietebooks Nguyễn Hoàng Cương c ≡ ye1βe2(mod p) và β ≡ αa (mod p) Ta có: (d α-e2)f1 ≡ ???? T−ợng tự, dùng các yếu tố D ≡ ???? (D α-f2)e1 ≡ ye1 f2 (mod p) vì thế phép kiểm tra tính phù hợp trong b−ớc 9 thành công. Bây giờ xét xác suất để Bob có thể thử từ chối một chữ ký hợp lệ. Tr−ờng hợp này không giả thiết Bob thực hiên theo thủ tục. Nghĩa là Bob có thể không xây d−ng D Và d nh− trong giao thức. Vì thế trong định lý tiếp theo chỉ là giả thiết rằng, Bob có thể tạo ra các D và d thoả mãn điều kiện trong các b−ớc 4,8và 9 của giao thức nêu trên hình 6.8. Định lý 6.3 Giả sử y ≡ xa (mod p) và Alice thực hiện theo giao thức từ chối. Nếu d ≡ xe1 αe2(mod p) ƒ ƒ và D ≡ x 1 α 2(mod p) thì xác suất để: ƒ ƒ (dα-e2) 1 ≡ (Dα- 2)e1 (mod p) = 1-1/q chứng minh: giả sử rằng, các đồng d− thức sau đ−ợc thoả mãn y ≡ αa (mod p) d ≡ xe1 αe2(mod p) ƒ ƒ D≡ x 1 α 2(mod p) ƒ ƒ (dα-e2) 1 ≡ (Dα- 2)e1 (mod p) ta sẽ nhận đ−ợc mâu thuẩn nh− trình bay sau đây: có thể viết lại b−ớc 9- b−ớc kiểm tra tính phù hợp nh− sau ƒ1 ƒ2 D ≡ d0 α 1/e1 -e2/e1 trong đó d0 = d α mod p là giá trị chỉ phụ thuộc vào các b−ớc 1- 4 trong giao thức. áp dụng định lý 6.1, ta kết luận đ−ợc y là chữ ký hợp lệ đối với d0 với xác suất 1- 1/q. Song ta đã giả thiết y là chữ ký hợp lệ đối với x, nghĩa là là ta có (với xác suất cao) a a x ≡ d0 (mod p) có nghĩa là x = d0 Trang 21
22. Vietebooks Nguyễn Hoàng Cương Tuy nhiên do d ≡ xe1 αe2(mod p) có nghĩa là x ≡ d1/e1α-e2/e1(mod p) Và từ chỗ 1/e1 -e2/e1 d0 ≡ d α (mod p) suy ra x # d0 ⇒ ta nhận đ−ợc mâu thuẩn. Nh− vậy Bob có thể lừa dối Alice theo cách này với xác suất 1/q. 6.6 các chữ ký fail- stop Sơ đồ chữ ký Fail- stop dùng để tăng độ mật tr−ớc khả năng một đối thủ mạnh có thể giả mạo chữ ký. Nếu Oscar khả năng giả mạo chữ ký của Bob thì Bob có khả năng chứng minh đ−ợc (với xác suất cao) rằng chữ ký của Oscar là giả mạo. Phần này sẽ mô tả một sơ đồ Fail- stop do Van Heyst va Pedersen đua ra năm 1992. Đầu là sơ đồ chữ ký 1 lần (chỉ một bức điện có thể ký bằng một cho tr−ớc chỉ 1 lần). Hệ thống gồm các thuật toán ký, thuật toán xác minh và thuật toán “chứng minh giả mạo”. Hình 6.9 mô tả các thuật toán ký và xác minh của sơ đồ Fail- stop của Van Heyst va Pedersen. Không khó khăn nhận thấy rằng, chữ ký do Bob tao ra sẽ thoả mãn điều kiện xác minh nên ta lại trở các kía cạnh an toàn toàn của sơ đồ này và các thức làm việc của tính chất Fail- Safe (tự động ngừng khi có sai số). Tr−ớc hết, ta thiết lập vài yếu tố quan trọng có liên quan đến các khoá của sơ đồ. Đầu tiên đ−a ra một định nghĩa: Hai khoá (γ1, γ2, a1, a2, b1, b2) và (γ1’, γ2’, a1’, a2’, b1’, b2’) là t−ơng đ−ơng nếu γ1 =γ1’,γ2= γ2’. Và dễ dàng nhận thấy tồi tại q2 khoá trong lớp t−ơng đ−ơng bất kỳ. Sau đây là vài bổ đề. Trang 22
23. Vietebooks Nguyễn Hoàng Cương Bổ đề 6.4 Giả sử K và K’là các khoá t−ơng đ−ơng và giả thiết chữ ký verK(x,y) = true(đúng). Khi đó chữ ký verK’(x,y) = true. Chứng minh Giả sử K =(γ1, γ2, a1, a2, b1, b2) và K’= (γ1’, γ2’, a1’, a2’, b1’, b2’) trong đó : a1 a2 a’1 a’2 γ1= α β mod p =α β mod p b1 b2 b’1 b’2 γ2= α β mod p =α β mod p Giả sử x đ−ợc bằng cách dùng K và tạo ra các chữ ký y =(y1, y2) trong đó: y1= a1+xb1mod q y2= a2+xb2mod q Hình 6.9 Sơ đồ chữ ký Fail- stop. Cho p = 2q+1 là số nguyên tố sao q là nguyên tố và bài toán * logarithm rời rạc trong Zp là khó giải. cho α ∈Zp là phần tử bậc q. Giả a0 sử 1 ≤ a0 ≤ q-1và định nghĩa β =α mod p. Các giá trị p, q, α, β và a0 đều do ng− ời có thẩm quyền (đ−ợc tin cậy) chọn. Các số p, q, α và β công khai và cố định còn a0 đ−ợc giữ bí mật. Cho p =Zp và a = Zqì Zq. khoá có dạng: K =(γ , γ , a , a , b , b ) 1 2 1 2 1 2 trong đó a1, a2, b1, b2∈ Zq a1 a2 γ1= α β mod p b1 b2 còn γ2= α β mod p Với K =(γ , γ , a , a , b , b ) và x ∈Z *, ta định nghĩa 1 2 1 2 1 2 p sigk(x) =(y1, y2) trong đó y1= a1+xb1mod q còn y = a +xb mod q 2 2 2 Z ì Z Với y =(y1, y2) ∈ q q ta có: x y1 y2 Xác minh ver(x,y) = true ⇔ γ1γ2 ≡ α β (mod p) Trang 23
24. Vietebooks Nguyễn Hoàng Cương Bây giờ giả sử ta xác minh y bằng cách dùng K’ αy1βy2 ≡ αa’1+ xb’1βa’ + xb’2 (mod p) ≡ αa’1βa’2 (αb’1βb’2 )x (mod p) x ≡ γ1γ2 mod p Nh− vậy, y cũng sẽ đ−ợc xác minh bằng K’. Bổ đề 6.5 Giả sử K là khoá còn y = sigK’(x). Khi đó tồn tại đúng q khoá K’ t−ơng đ−ơng với K sao cho y= sigK’(x). Chứng minh Giả sử γ1và γ2là các thành phần công khai của K. Ta muốn xác định số bội 4 (a1, a2, b1, b2)sao cho các đồng d− thức sau đây đ−ợc thoả mãn. a1 a2 γ1≡ α β (mod p) b1 b2 γ2≡ α β (mod p) y1≡ a1+xb1(mod q) y2≡ a2+xb2(mod q). Vì α sinh ra G nên tồn tại các số mũ duy nhất c1, c2, a0 ∈ Zq sao cho c1 γ1≡ α (mod p) c2 γ2≡ α (mod p) và β ≡ αa0 (mod p) vì thế nó điều kiện cần và đủ để hệ các đồng d− thức sau đây đ−ợc thoả mãn: c1≡ a1+a0a2(mod q) c2≡ b1+a0b2(mod q) y1≡ a1+ xb1(mod q) y2≡ a2+ xb2(mod q) Hệ thống này có thể viết d−ới dạng ph−ơng trình ma trận trong Zq nh− sau: ⎛ 1 a 0 0 ⎞ ⎛a ⎞ ⎛c ⎞ ⎜ 0 ⎟ ⎜ 1 ⎟ ⎜ 1 ⎟ ⎜ 0 0 1 a ⎟ ⎜a ⎟ ⎜c ⎟ 0 ⎜ 2 ⎟ ⎜ 2 ⎟ ⎜ ⎟ = 1 0 x 0 ⎜b ⎟ ⎜y ⎟ ⎜ ⎟ ⎜ 1 ⎟ ⎜ 1 ⎟ ⎜0 1 0 x ⎟ ⎜b ⎟ ⎜y ⎟ ⎝ ⎠ ⎝ 2 ⎠ ⎝ 2 ⎠ Trang 24
25. Vietebooks Nguyễn Hoàng Cương có thể thấy ma trận hệ thống số của ph−ơng trình có hạng là 3( hạng của một ma trận là số cực đậi của các hàng độc lập tuyến tính mà nó có). Rõ ràng, hạng ít nhất bằng 3 vì các hàng 1, 2 và 4 là độc lập tuyến tính trên Zp. còn hạng nhiều nhất cũng bằng 3 vì: r1 +x r2-r3-a0r4= (0,0,0,0). Với r1 chỉ hàng thứ i của ma trận. Hệ ph−ơng trình này có ít nhâts một nghiệm nhận đ−ợc bằng cách dùng khoá K.Vì hàng của ma trận hệ số bằng 3 nên suy ra rằng chiều của không gian nghiệm là 4-3=1 và có chính xác q nghiệm. T−ơng tự nh− vậy ta có thể chứng minh đ−ợc kết qủa sau: Bổ đề 6.6 ’ Giả sử K là khoá y=sigK(x) còn verK (x’,y’)=true, trong đó x # x. Khi đó ’ tồn tại ít nhất một khoá K t−ơng đ−ơng với K sao cho y=sigK’(x) và y’= ’ sigK’(x ) Ta hãy làm sáng tỏ hai bổ đề trên về độ mật của sơ đồ. Khi cho tr−ớc y là chữ kí hợp lệ của x, sẽ tồn tại q khoá có thể để x sẽ đ−ợc kí bằng y. Song với bức điện bất kì x’≠ x, q khoá này sẽ tạo ra q khoá khác nhau trên x’. Điều đó dẫn đến định lí sau đây: Định lí 6.7: ’ ’ Nếu cho tr−ớc sigK(x)=y và x ≠ x. Oscar có thể tính sig K(x ) với xác suất là 1/q. Chú ý rằng, định lí này không phụ thuộc vào khả năng tính toán của Oscar: Mức an toàn qui định đạt đ−ợc vì Oscar không thể nói về q khoá có thể mà Bob đang dùng. Nh− vậy độ an toàn ở đây là vô điều kiện. Tiếp tục xem xét về khái niệm Fail- Stop. Khi cho tr−ớc chữ ký y trên bức điện x. Oscar không thể tính ra đ−ợc chữ ký y’ của Bob trên bức điện x’ khác. Điều này cũng có thể hiểu rằng, Oscar có thể tính đ−ợc chữ ký giả mạo Trang 25
26. Vietebooks Nguyễn Hoàng Cương ’’ ’ y = sigK(x )(sẽ đ−ợc chứng minh ). Tuy nhiên, nếu đ−a cho Bob một chữ ký giả mạo hợp lệ, thì anh ta có thể tạo ra “một bằng chứng về sự giả mạo ” với xác suất 1-1/q. Bằng chứng về sự giả mạo là giá trị a0=logα β (chỉ ng−ời có thẩm quyền trung tâm biết ). ’ ’’ ’ ’’ ’’ ’ Giả sử Bob sở hữu cặp (x ,y ) sao cho ver(x ,y )= true và y ≠sigK(x ). Nghĩa là: x’ y”1 y”2 γ1γ2 ≡ α β (mod p) ’’ ’’ ’’ ’ ’ trong đó :y =(y 1,y 2). Bây giờ Bob có thể tính chữ ký của mình trên x là y = ’ ’ (y 1,y2 ). Khi đó : x’ y’1 y’2 γ1γ2 ≡ α β (mod p) vì thế αy”1βy”2 ≡ αy’1βy’2(mod p) Nếu viết β = αa0mod p, ta có : αy”1+ a0 y”2 ≡ αy’1+ a0 y’2(mod p) hay: ’ ’ y”+a0y”2 ≡ y 1+a0y (mod q) hoặc: ’’ ’ ’ y 1- y1 ≡ a0(y’2-y”2 )(mod q) ’ ’’ ’ ’ ’’ -1 Xét thấy y 1≡ y 2(mod q) vì y là giả mạo. Vì thế (y 2-y 2) mod q tồn tại và ’’ ’ ’ ’’ -1 a0 =logα β = (y 1-y 1) (y 2-y 2) mod q Dĩ nhiên, bằng việc chấp nhận bằng chứng về sự giả mạo nh− vậy,ta giả thiết Bob không thểt ự tính đ−ợc logarithm rời rạc logα β. Đây là gải thiết về mặt tính toán. Cuối cùng, chú ý rằng,sơ đồ chữ kí là một lần vì khóa k của Bob có thể tính dễ dàng nếu hai bức điện đều dùng K để ký. D−ới đây là ví dụ minh hoạ cách Bob tạo một bằng chứng về sự giả mạo. Trang 26
27. Vietebooks Nguyễn Hoàng Cương Vi dụ 6.7 * Cho p=4367=2.1733+1. Phần tử α =4 có bậc là 1733 trong Z3467 Giả sử ao =1567, ta có: β = 41567 mod 346=514 (Bob biết α và β song không biết a0). Giả sử Bob tập khoá bằng cách dùng a1 = 888, a2 = 1042, b1 = 786, b2 = 999. Khi đó 888 1024 γ 1=4 514 mod 3476=3405 786 999 và γ 2=4 514 mod 3476=2281 Tiếp theo, giả sử Bob nhận đ−ợc chữ kí giả mạo (822,55) trênê bức điện 3383. Đây là chữ ký hơp lệ vì thoả mãn điều kiện xác minh. 3405 ì 22813384≡ 2282 (mod 3476) và 482251455≡ 2282(mod 3476) Mặt khác đây không phải là chữ kí đã đ−ợc Bob xây dựng. Bob có thể tíng chữ kí của mình nh− sau: (888+3383ì786 mod 1733.1024+3383ì999 mod 1733 )=(1504.1291) Sau đó anh ta tính tiếp log rời rạc bí mật -1 a0 =(822-1504)(1291-55) mod 1733 =1567. Đây là bằng chứng về sự giả mạo. 6.7 các chú giải về tμi liệu dẫn Mitchell, Piper và Wild [MPW 92] đã đ−a ra một tổng quan đầy đủ về các sơ đồ chữ kí. Bài này cũng có hai ph−ơng pháp giả mạo chữ kí của Elgamal mà ta đã đ−a ra trong 6.2. Sơ đồ chữ kí Elgamal đã đ−ợc nêu trong [EL 85], tiêu chuẩn chữ kí số đ−ợc công bố đầu tiên vào 8/1991 bởi NIST và đ−ợc chấp nhận làm tiêu chuẩn vào 12/94 [NBS 94]. Một cuộc thoả luận dài về DSS và những cuộc tranh cãi xung quanh nó vào 7/1992 đ−ợc đăng trên Communication of the ACM. Sơ đồ Lamport đ−ợc mô tả trong bài báo của Diffie_Hellman [DH 76] năm 1976. Bản cải tiến củaBob và Chaum đ−ợc nêu trong [BC 93]. Sơ đồ chữ Trang 27
28. Vietebooks Nguyễn Hoàng Cương kí không chối nêu trong mục 6.5 do Chaum và Van Antwerpen đ−a ra trong [CVA 90]. Sơ đồ chữ kí Fail-Stop trong mục 6.6 là của Van Heyst và Pederson [VHP 93]. Một số ví dụ về các sơ đồ chữ kí “phá đ−ợc ”gồm các sơ đồ của ông Schorss- Sshamir[OSS 85](cũng bị phá bởi Estes EAKMM 86) và sơ đồ hoán vị Birational của Shamir [SH94] (bị Coppessnuth, Steru và Vandeney CSV 94). Cuối cùng ESIGN là sơ đồ chữ kí của Fujioka.Okamoto và Meyaguchi [FOM 91]. Một số phiên bản của sơ đồ này đã bị phá. Song một sửa đổi trong [FOM 91] lại không bị phá. bài tập 6.1. Giả thiết Bob đang dùng sơ dồ Elgamal, anh ta kí hai bức điện x1 và x2 bằng chữ kí (γ, δ 1) và (γ, δ 2) t−ơng ứng (giá trị này của γ giống nhau trong cả hai chữ kí ). Cũng giả sử UCLN (γ 1-γ 2,p-1)=1. a) Hãy cho biết cách tính k hiệu quả khi biết thông tin này b) Hãy mô tả cách sơ đồ chữ kí có thể bị phá. c) Giả sử p=31847, α =5, và β =25703. Tính k và a khi cho tr−ớc chữ kí (2397 2,31396 ) vói bức điện x=8990 và chữ kí (23972, 20481 trên bứ c điện x=31415) 6.2. Giả sử I thực hiên sơ đò Elgamal với p=31847, α =5,và β =26379. Hãy viết ph−ơng trìng thực hiện công việc sau: a) Xác minh chữ kí (20679,11082 ) trên bức điện x=20543 b) Xác định số mũ mật a bằng cách dùng thuật toán tối −u hoá thời gian - bộ nhớ của Shark, sau dó xác định giá trị k ngẫu nhiên dùng trong việc kí lên bức điện x. 6.3. Giả sử Bob dùng sơ đố chữ kí Elgamal nh− trong ví dụ 6.1:p=467,α =2 β=132.Giả sử Bob kí lên bức điện x=100 bằng chữ kí (29,51).Hãy tính chữ kí giả mạo mà Oscar có thể lập bằng cách dùng h=100,i=45 và j =293.Hãy kiểm tra xem chữ ký vừa nhận đ−ợc có thoả mãn điều kiện xác minh không. 6.4. Chứng minh rằng ph−ơng pháp giả mạo thứ hai trên sơ đồ Elgamal (mô tả trong mục 6.2) cũng tạo ra chữ kí thoả mãn điều kiện xác minh. Trang 28
29. Vietebooks Nguyễn Hoàng Cương 6.5. Sau đây là ph−ơng án của sơ đồ Elgamal :Khoá đ−ợc xây dựng t−ơng tự * theo mghĩa nh− tr−ớc đây:Bob chọn α ∈ Zp là phần tử nguyên thuỷ. a là số mũ mật (0 ≤ a ≤ p-2) sao cho UCLN (a,p-1) =1 và α a mod p. Khoá K = (α, a, β ), ở đây α và β công khai còn a mật. Cho x∈ Z p là bức điện đ−ợc kí. Bob tính chữ kí sig (x)=(γ, δ ), trong đó: γ =α k mod p còn δ =(x-k γ)a-1 mod (p-1). Sự khác nhau duy nhất so với sơ đồ Elgamal ban đầu là ở cách tính δ. Hãy trả lời các câu hỏi sau liên quan đến sơ đồ cải tiến này: a) Mô tả cách xác minh một chữ kí (γ, δ ) trên bức điện x bằng cách dùng công khai khoá của Bob. b) Mô tả −u điểm về mặt tính toán của sơ đồ cải tiến. c) So sánh tóm tắt độ an toàn của sơ đồ cải tiến và sơ đồ ban đầu. 6.6. Giả sử Bob dùng DSS với q = 101, p = 7879, α = 170, a = 75 còn β = 4567 nh− trong ví dụ 6.3. Xác định chữ kí của Bob trên bức điện x=5011, bằng cách dùng giá trị ngẫu nhiên k =49 và chỉ ra cách xác minh chữ kí nhận đ−ợc. 6.7. Trong sơ đồ Lamport,giả sử rằng hai bức điện x và x’ bội k (k-tuple) đều do Bob kí. Cho l = d(x,x’) là toạ độ trên đó x và x ‘ khác nhau. Hãy chỉ ra cách Oscar có thể kí 2l -2 bức điện mới. 6.8. Trong sơ đồ Bob-Chaum với k = 6, n = 4, giả sử rằng các bức điện x = (0, 1,0,0,1,1) và x’ = (1,1,0,1,1) đều đ−ợc kí. Xác định bức điện mới đ−ợc Oscar kí khi biết chữ kí trên x và x’. 6.9. Trong sơ đồ Bob- Chaum, giả sử rằng hia bức điện x và x’ là các bội k ’ đều do Bob kí Cho l =⏐φ(x)∪φ(x )⏐. Hãy chỉ ra cách Oscar có thể kí ⎛ l ⎞ -2 ⎜ ⎟ ⎜ n ⎟ bức điện mới. ⎝ ⎠ 6.10. Giă sử Bob đang dùng chữ kí không chối đ−ợc của Chaum –Van Antwerpen nh− trong ví dụ 6.5. Nghĩa là p = 467, α = 4, a = 101, β = 449. Giả sử Bob đ−ợc trình chữ kí y = 25 trên bức điện x =157 và anh ta muốn chứng minh rằng nó giả mạo. Giả sử số ngẫu nhiên của Alice là e1 = 46, e2 = 123, f1 =198, f2 =11 trong thủ tục từ chối. Hãy tính các yêu cầu c, d, của Alice và các câu trả lời C, D của Bob; chỉ ra rằng phép kiểm tra tính phù hợp của Alice sẽ thành công. Trang 29
30. Vietebooks Nguyễn Hoàng Cương 6.11. Chứng minh rằng, mỗi lớp t−ơng đ−ơng các khoá trong sơ đồ chữ kí Fail-Stop của Pedersen-Van Hðyt chứa q2 khoá. 6.12. Giả sử Bob đang dùng sơ đồ chữ kí Fail-Stop của Pedersen-Van Heyst với p = 3467, α =4, a 0=1567 và β =514 (dĩ nhiên Bob không biết giá trị a0). a) Dùng yếu tố a0 =1567, xác định tất cả các khoá có thể : K = (γ1, γ2, a1, a2, b1, b2) sao cho sig K(42) =(1118,1449) b) Gái sử sigK(42) =(1118,1449) và sigK(969) =(899,471). Không cần dùng điều kịên a0 =1567. Hãy xác định K (điều này sẽ chứng tỏ sơ đồ là dùng một lần). 6.13. Gải sử Bob dùng sơ đồ Fail-Stop của Pedersen-Van Heyst vơi p =5087, α =25, β =1866. Giả sử K =(5065, 5067,144,874,1873,2345) và Bob tìm chữ kí (2219,458) đ−ợc giả mạo trên bức điện 4785 a) Chứng minh rằng, chữ kí giả mạo này thoả mãn điều kiện xác minh nên nó là chữ kí hợp lệ. b) Chỉ ra cách Bob tính “ bằng chứng giả mạo a0 khi cho tr−ớc chữ kí giả mạo này. ” ch−ơng 7 các hμm hash 7.1 các chũ kí vμ hμm hash. Bạn đọc có thể thấy rằng các sơ dồ chữ kí trong ch−ơng 6 chỉ cho phép kí các bức điện nhỏ.Ví dụ, khi dùng DSS, bức điện 160 bit sẽ đ−ợc kí bằng chữ kí dài 320 bít. Trên thực tế ta cần các bức điện dài hơn nhiều. Chẳng hạn, một tài liệu về pháp luật có thể dài nhiều Megabyte. Một cách đơn giản để gải bài toán này là chặt các bức điện dài thành nhiều đoạn 160 bit, sau đó kí lên các đoạn đó độc lập nhau. Điều này cũng Trang 30
31. Vietebooks Nguyễn Hoàng Cương t−ơng tự nh− mã một chuôĩ dài bản rõ bằng cách mã của mỗi kí tự bản rõ độc lập nhau bằng cùng một bản khoá. (Ví dụ: chế độ ECB trong DES). Biện pháp này có một số vấ đề trong việc tạo ra các chữ kí số. Tr−ớc hết, với một bức điện dài, ta kết thúc bằng một chữ kí rất lớn ( dài gấp đôi bức điện gốc trong tr−ờng hợp DSS). Nh−ợc điểm khác là các sơ đồ chữ kí “an toàn” lại chậm vì chúng dùng các pháp số học phức tạp nh− số mũ modulo. Tuy nhiên, vấn đề nghiêm trọng hơn với phép toán này là búc điện đã kí có thể bị sắp xếp lại các đoạn khác nhau,hoặc một số đoạn trong chúng có thể bị loại bỏ và bức điện nhận đ−ợc vẫn phải xác minh đ−ợc. Ta cần bảo vệ sự nguyên vẹn của toàn bộ bức điện và điều này không thể thực hiện đ−ợc bằng cách kí độc lập từng mẩu nhỏ của chúng. Giải pháp cho tất cả các vấn đề này là dùng hàm Hash mã khoá công khai nhanh. Hàm này lấy một bức điện có độ dài tuỳ ý và tạo ra một bản tóm l−ợc thông báo có kích th−ớc qui định (160 bit nếu dùng DSS). Sau đó bản tóm l−ợc thông báo sẽ đ−ợc kí. Vơi DSS, việc dùng hàm Hash đ−ợc biểu diễn trê hình 7.1. Khi Bob muốn kí bức điện x, tr−ớc tiên anh ta xây dựng một bnr tóm l−ợc thông báo z = h(x) và sau đó tính y = sigK (z ). Bob truyền cặp ( x, y) trên kênh. Xét thấy có thể thực hiện xác minh (bởi ai đó ) bằng cách tr−ớc hết khôi phục bản tóm l−ợc thông báo z =h (x) bằng hàm h công khai và sau đó kiểm tra xem verk (x,y) có = true, hay không. Hình 7.1.Kí một bản tóm l−ợc thông báo Bức điện :x độ dài tuỳ ý ↓ bản tóm l−ợc thông báo:z = h (x) 160 bit ↓ Chữ kí y = sig K(z) 320 bit Trang 31
32. Vietebooks Nguyễn Hoàng Cương 7.2. hμm hash không va chạm Chúng ta cần chú ý rằng,việc dùng hàm hash h không làm giảm sự an toàn của sơ đồ chữ kí vì nó là bản tóm l−ợc thông báo đ−ợc chữ kí không phải là bức điện. Điều cần thiết đối với h là cần thoả mãn một số tính chất nào đó để tranh sự giả mạo. Kiểu tấn công thông th−ờng nhất là Oscar bắt đầu bằng một bức diện đ−ợc kí hợp lệ (x, y), y =sigK(h (x)),(Cặp (x, y) là bức điện bất kì đ−ợc Bob kí tr−ớc đó). Sau đó anh ta tính z = h(x) và thử tìm x ≠ x’ sao cho h(x’) = h(x). Nếu Oscar làm đ−ợc nh− vậy, (x’, y) sẽ là bức điện kí hợp lệ, tức một bức điện giả mạo. Để tránh kiểu tấn công này, h cần thoả mãn tính không va chạm nh− sau: Định nghĩa 7.1 Hàm hash h là hàm không va chạm yếu nếu khi cho tr−ớc một bức điện x, không thể tiến hành về mặt tính toán để tìm một bức điện x ≠ x’ sao cho h (x’) = h(x). Một tấn công kiểu khác nh− sau: Tr−ớc hết Oscar tìm hai bức điện x ≠ x’ sao cho h(x) =h(x’). Sau đó Oscar đ−a x cho Bob và thyết phục Bob kí bản tóm l−ợc thông báo h(x) để nhận đ−ợc y. Khi đố (x’,y) là thông báo (bức điện ) giả mạo hợp lệ. Đây là lí do đ−a ra một tính chất không va chạm khác. Định nghĩa 7.2. Hàm Hash h là không va chạm mạnh nếu không có khả năng tính toán để tìm ra bức điênk x và x’ sao cho x ≠ x’ và h(x) = h(x’). Nhận xét rằng: không va chạm mạnh bao hàm va chạm yếu. Còn đây là kiểu tấn công thứ 3: Nh− đã nói ở phần 6.2 việc giả mạo các chữ kí trên bản tóm l−ợc thông báo z ngẫu nhiên th−ờng xảy ra với sơ đồ chữ kí. Giả sử Oscar tính chữ kí trên bản tóm l−ợc thông báo z ngẫu nhiên nh− vậy. Sau đó anh ta tìm x sao cho z= h(x). Nếu làm đ−ợc nh− vậy thì (x,y) là bức điện giả mạo hợp lệ. Để tránh đ−ợc tấn công này, h cần thoả mãn tính chất một chiều (nh− trong hệ mã khoá công khai và sơ đồ Lamport). Định nghĩa 7.3. Hàm Hash h là một chiều nếu khi cho tr−ớc một bản tóm l−ợc thông báo z, không thể thực hiện về mặt tính toán để tìm bức điện x sao cho h(x) = z. Trang 32
33. Vietebooks Nguyễn Hoàng Cương Bây giờ ta sẽ chứng minh rằng, tính chất không va chạm mạnh bao hàm tính một chiều bằng phản chứng. Đặc biệt ta sẽ chứng minh rằng, có thể dùng thuật toán đảo với hàm Hash nh− một ch−ơng trình con (giả định ) trong thuật toán xác suất Las Vegas để tìm các va chạm. Sự rút gọn này có thể thực hiện với một giả thiết yếu về kích th−ớc t−ơng đối của vùng và miền (domain and range) của hàm Hash. Ta cũng sẽ giả thiết tiếp là hàm Hash h: X→Z, X,Z là các tập hữu hạn và ⏐X⏐ ≥ 2⏐Z⏐. Đây là giả thiết hợp lí :Nếu xem một phần tử của X đ−ợc mã nh− một xâu bít có độ dài log2⏐X⏐ và phần tử của Z đ−ợc mã hoá nh− một xâu bít có độ dài log2⏐X⏐ thì bản tóm l−ợc thông báo z = h(x) ít nhất cũng ngắn hơn bức điện x một bít (ta sẽ quan tâm đến tình huống vùng X là vô hạn vì khi đó có thể xem xét các bức điện dài tuỳ ý. Lập luận đó của ta cũng áp dụng cho tình huống này). Tiếp tục giả thiết là ta có một thuật toán đảo đối với h, nghĩa là có một thuật toán A chấp nhận nh− đầu vào bản tóm l−ợc thông báo z∈Z và tìm một phần tử A(z) ∈ X sao cho h(A(z)) = z. Ta sẽ chứng minh địng lí d−ới đây: Định lí 7.1: Giả sử h: X→Z là hàm Hash, trong đó ⏐X⏐và⏐Z⏐ hữu hạn và ⏐X⏐≥ 2⏐Z⏐. Cho A là thuật toán đảo đối với h. Khi đó tồn tại một thuật toán Las Vagas xác suất tìm đ−ợc một va chạm đối với h với xác suất ít nhất là1/2. Chứng minh : Xét thuật toán B đ−a ra trong hình 7.2. Rõ ràng B là một thuật toán xác suất kiểu Las Vegas vì nó hoạc tìm thấy một va chạm, hoặc cho câu trả lời không. Vấn đề còn lại là ta phải tịnh xac suất thành công, Với x bất kỳ thuộc X, định nghĩa x ∼ x1 nếu h(x) = h(x1). Dễ thấy rằng, ∼ là quan hệ t−ơng đ−ơng. Ta định nghĩa: [x] = {x1∈X: x ∼x1} Mỗi lớp t−ơng đ−ơng [x] chứa ảnh đảo của một phần tử thuộc Z nên số các lớp t−ơng đ−ơng nhiều nhất là ⏐Z⏐. Kí hiệu tập các lớp t−ơng đ−ơng là C. Bây giờ giả sử, x là phần tử ∈X đ−ợc chọn trong b−ớc 1. Với giá trị x này, sẽ có⏐[x]⏐giá trị x1 có thể cho phép trở lại b−ớc 3. ⏐[x]⏐-1 các giá trị x1 này khác với x và nh− vậy b−ớc 4 thành công. (Chú ý rằng thuật thoán A Trang 33
34. Vietebooks Nguyễn Hoàng Cương không biết biểu diễn các lớp t−ơng đ−ơng [x] đã chon trong b−ớc 1). Nh− vậy, khi cho tr−ớc lựa chọn cụ thể x∈X, xác suất thành công là (⏐[x)⏐-1/⏐[x]⏐. Hình.7.2 Dùng thuật toán đảo A để tìm các va chạm cho hàm Hash 1.chọn một ssó ngẫu nhiên x ∈X 2.Tính z=h(x) 3.Tinh x1= A(Z) 4. if x1 ≠ x then x và x1 va chạm d−ới h (thành công) else Quit (sai) Xác suất thành công của thuật toán B bằng trung bình cộng tất cả các lựa chon x có thể: P(thành công) = (1/⏐X⏐)∑x∈X(⏐[x]⏐-1)/⏐[x]⏐ = (1/⏐X⏐) ∑c∈C∑x∈C(⏐c⏐-1)/⏐c⏐ = 1/⏐X⏐∑c∈C(⏐c⏐-1) = (1/⏐X⏐) ∑c∈C⏐c⏐ - ∑ c∈C1 >= (⏐X -⏐Z⏐⏐) / ⏐X⏐ >= ((⏐X⏐ -⏐Z⏐)/2) /⏐X⏐ = ẵ Nh− vậy, ta đã xây dựng thuật toán Las Vegas có xác suất thành công ít nhất bằng 1/2. Vì thế, đó là điều kiện đủ để hàm Hash thoả mãn tính chất không va chạm mạnh vì nó bao hàm hai tính chất khác.Phần còn lại của ch−ơng này ta chỉ quan tâm đến các hàm Hash không va chạm mạnh. 7.3 tấn công ngày sinh nhật(birthday) Trong phần này, ta sẽ xác định điều kiện an toàn cần thít ch hàm Hash và điều kiện này chỉ phụ thuộc vào lực l−ợng của tập Z (t−ơng đ−ơng về kích th−ớc của bảng thông báo ).Điều kiện cần thiết nà rút ra t− ph−ơng pháp tìm kiếm đơn giản ác va chạm mà ng−ời ta đã biết đến d−ới cái tên tấn công ngày sinh nhật (birthday ph−ơng pháparradox), trong bài toán:một nhóm 23 ng−ời ngẫu nhiên, có ít nhất 2 ng−ời có ngày sinh trùng nhau với xác suất ít nhất là1/2.(Dĩ nhiên, đây ch−a phải là nghịch lí,song đó là trực giác đối lập có thể Trang 34
35. Vietebooks Nguyễn Hoàng Cương xảy ra). Còn lí do của thuật ngữ “tấn công ngày sinh nhật ” sẽ rõ ràng khi ta tiếp tuch trình bày. Nh− tr−ớc đây, ta hãy giả sử rằng :h:X→Z là hàm Hash, X,Z hữu hạn và ⏐X⏐ >=2⏐Z⏐.Địng nghĩa ⏐X⏐ = m và⏐Z⏐ = n.Không khó khăn nhận thấy rằng, có ít nhất n va chạm và vấn đề đằt ra là cách tìm chúng. Biện pháp đơn sơ nhất là chọn k phần tử ngẫu nhiên phân biệt x1,x2 xk ∈X, tính z1 = h(x1),1<= i <= k và sau đó xác định xem liệu có xảy ra va chạm nào không (bằng cách, chẳng hạn nh− sáp xếp lại các zi). Quá trình này t−ơng tự với việc ném k quả bóng vào thùng và sau đó kiểm tra xem liệu có thùng nào chứa ít nhất hai quả hay không (k qủa bóng t−ơng đ−ơng với k giá trị xi ngẫu nhiên và n thùng t−ơng ứng với n phần tử có thể trong Z). Ta sẽ giới hạn d−ới của xác suất tìm thấy một va chạm theo ph−ơng pháp này.Do chỉ quan tâm đến giới hạn d−ới về xác suất va chạm nên ta sẽ giả sử rằng ⏐h-1 (z)⏐≈ m/n với mọi z ∈Z. (đây là giả thiết hợp lí :Nếu các ảnh đảo không xấp xỉ bằng nhau thì xác suất tìm thấy một va chạm sẽ tăng lên ). Vì các ảnh đảo đều có kích th−ớc bằng nhau và các xi đ−ợc chọn một cách ngẫu nhiên nên các z i nhận đ−ợc có thể xem nh− các phần tử ngẫu nhiên của Z. Song việc tính toán xác suất để các phần tử ngẫu nhiên z1, z2, zk ∈Z là riêng biệt khá đơn giản.Xét các zi theo thứ tự z1, ,zk. Phép chọn z1 đầu tiên là tuỳ ý. Xác suất để z2≠z1 là 1-1/n; xác suất để z3 ≠ z1 và z2 là 1- 2/n. vv Vì thế ta −ớc l−ợng xác suất để không có va chạm nào là: (1-1/n)(1-2/n) (1-(k-1/n)) = (1-1/n) Nếu x là số thực nhỏ thì 1- x ≈ e-x. Ước l−ợng này nhận d−ợc từ hai số hạng đầu tiên của cá chuỗi khai triển. e-x = 1 - x + x2/2! - x3/3! Khi đó xác suất không có va chạm nào là : k −1 i k −1 ∏∏(1 − ) ≈ e-1/n = e -k(k-1)/n i=1 n i=1 Vì thế ta −ớc l−ợng xác suất để có ít nhất một va chạm là 1-e-k(k-1)/n Nếu kí hiệu xác suất này là ε thì có thể giải ph−ơng trình đối với k (nh− một hàm của n và ε) 1-e-k(k-1)/n ≈ 1 -ε -k(k-1)/n ≈ ln(1-ε) Trang 35
36. Vietebooks Nguyễn Hoàng Cương k2 - k ≈ nln 1/(1-ε) Nếu bỏ qua số hạng k thì : 1 k= nln 1−ε Nếu lấy ε = 0.5 thì k ≈ 1.17 n Điều này nói lên rằng, việc chặt (băm) trên n phần tử ngẫu nhiên của X sẽ tạo ra một va chạm với xác suấtt 50%. Chú ý rằng, cách chọn ε khác sẽ dẫn đến hệ số hằng số khác song k vẫn tỷ lên với n . Nếu X là tập ng−ời,Y là tập gồm 365 ngỳ trong năm (không nhuận tức tháng 2 có 29 ngày) còn h(x) là ngày sinh nhật của x, khi đó ta sẽ giả guyết bằng nhgịch lý ngày sinh nhật. Lấy n = 365, ta nhận đ−ợc k ≈ 22,3. Vì vậy, nh− đã nêu ở trên, sẽ có ít nhất 2 ng−ời có ngày sinh nhật trùng nhau trong 23 ng−ời ngẫu nhiên với xác suất ít nhất bằng 1/2. Tấn công ngày sonh nhật đặt giới hạn cho các kích th−ớc các bản tóm l−ợc thông báo. bản tóm l−ợc thông báo 40 bit sẽ không an toàn vì có thể tìm thấy một va chạm với xác suất 1/2 trên 220 (khoảng1.000.000)đoạn chặt ngẫu nhiên. Từ đây cho thấy rằng, kích th−ớc tối thiểu chấp nhận đ−ợc của bản tóm l−ợc thông báo là 128 bit (tấn công ngày sinh nhật cần trên 264 đoạn chặt trong tr−ờng hợp này). Đó chính là lý do chọn bản tóm l−ợc thông báo dài 160 bit trong sơ đồ DSS. Hình7.3. Hàm hash chaum-Van heyst-Plitzmann. Giả sử p là số nguyên tố lớn và q =(p-1)/2 cũng là số nguyên tố. Cho α và β là hai phần tử nguyên thuỷ của Zp. Giá trị log β không công khai và giả sử rằng không có khả năng α tính toán đ−ợc giá trị của nó. Hàm Hash: h: {0, ,q-1}ì{0, ,q-1} → Zp\ {0} đ−ợc định nghĩa nh− sau: x x h(x1,x2) =α 1β 2 mod p Trang 36
37. Vietebooks Nguyễn Hoàng Cương 7.3. hàm hash logarithm rời rạc Trong phần này ta sẽ mô tả một hàm Hash do Chaum-Van Heyst và Pfĩtmann đ−a ra. Hàm này an toàn do không thể tính đ−ợc logarithm rời rạc. Hàm Hast này không đủ nhanh để dùng trong thực tế song nó đơn giản và cho một ví dụ tốt về một hàm Hash có thể an toàn d−ới giả thuyết tính toán hợp lý nào số. Hàm Hash Caum-Van Heyst- Pfĩtmann đ−ợc nêt trong hình 7.3. Sau đây sẽ chứng minh một định lý liên quan đến sự an toàn của hàm Hast này. Định lý 7.2. Nếu cho tr−ớc một va chạm với hàm Hash Chaum-Van Heyst-Pfĩtmann h có thể tính đ−ợc logarithm rời rạc logαβ một cách có hiệu quả. Chứng minh Giả sử cho tr−ớc va chạm h(x1,x2) = h(x3,x4) trong đó (x1,x2) ≠ (x3,x4). Nh− vậy ta có đồng d− thức sau: αx1βx2 = αx3βx4 hay αx1βx2 ≡ αx3βx4 (mod p) Ta kí hiệu D = UCLN (x4-x2,p-1) Vì p-1 =2q ,q là số nguyên tố nên d ∈ {1, 2, q, p-1}. Vì thế, ta có 4 xác suất với d sẽ xem xét lần l−ợt dwois đây. Tr−ớc hết ,giả sử d =1 ,khi đó cho -1 y= (x4-x2) mod (p-1) ta có β ≡ β(x4-x2)y(mod p) ≡ α(x1-x2)y(mod p) Vì thế, có thể tính loarithm rời rạc logαβ nh− sau: -1 logαβ = (x1-x3) (x4-x2) mod (p-1) Tiếp theo, giả sử d=2. Vì p-1 =2q, lẻ nên UCLN(x4-x2,q) =1. Giả sử: -1 y=(x4-x2) mod q Trang 37
38. Vietebooks Nguyễn Hoàng Cương xét thấy (x4-x2)y = kq+1 với số nguyên k nào đó. Vì thế ta có: β(x4-x2)y ≡ βkq+1 (mod p) ≡ (-1)k β (mod p) ≡ ± β (mod p) Vì βq ≡-1(mod p) Nên α(x4-x2)y ≡ β (x1-x3) (mod p) ≡ ± β (mod p) Từ đó suy ra rằng: logαβ = (x1-x3)y mod (p-1) logαβ = (x1-x3)y mod (p-1) Ta có thể dễ dàng kiểm tra thấy một trong hai xác suất trên là đúng. Vì thế nh− trong tr−ờng hợp d =1, ta tính đ−ợc logαβ. Xác suất tiếp theo là d = q. Tuy nhiên q-1≥ x1≥ 0 và q-1≥ x3≥ 0 nên (q-1) ≥ x4-x2 ≥ -(q-1) do vậy UCLN(x4-x2,p-1) không thể bằng q, nói cách khác tr−ờng hợp này không xảy ra. Xác suất cuối cùng là d = p-1. Điều nàychỉ xảy ra khi x2 =x4. Song khi đó ta có αx1βx2 ≡ αx3βx4 (mod p) nên αx1 ≡ αx3 (mod p) và x1 =x2. Nh− vậy (x1,x2) = (x3,x4) ⇒ mâu thuẫn. Nh− vậy tr−ờng hợp này cũng không thể có. Vì ta đã xem xét tất cả các giá trị có thể đối với d nên có thể kết luận rằng ,hàm Hash h là không va chạm mạnh miễn là không thể tính đ−ợc logarithm rời rạc logαβ trong Zp. Ta sẽ minh hoạ lý thuyết nêu trên bằng một ví dụ. Ví dụ 7.1 Giả sử p =12347 (vì thế q = 6173), α = 2, β = 8461. Giả sử ta đ−ợc đ−a tr−ớc một va chạm α5692 β 144 ≡ α212 β4214 (mod 12347) Nh− vậy x1 = 5692, x2 = 144, x3 = 212, x4 = 4214. Xét thấy UCLN (x4 -x2,p-1) =2 nên ta bắt đầu bằng việc tính -1 y = (x4 - x2) mod q = (4214 - 144)-1 mod 6173 = 4312 Trang 38
39. Vietebooks Nguyễn Hoàng Cương Tiếp theo tính y = (x1- x3) mod (p-1) = (5692 - 212) 4312 mod 12346 = 11862 Xét thấy đó là tr−ờng hợp mà logαβ ∈ {y’,y’+q mod (p-1)}. Vì αy mod p =212346 = 9998 nên ta kết luận rằng: logαβ = y’ + q mod (p-1) = 11862 + 6173 mod 12346 = 5689 nh− phép kiểm tra, ta có thể xác minh thấy rằng 25689 = 8461 (mod 12347) Vì thế , ta các định đ−ợc logαβ. 7.5.các hàm hash mở rộng Cho đến lúc này, ta đã xét các hàm Hash trong vùng hữu hạn. Bây giờ ta nghiên xéu cách có thể mở rộng một hàm Hash không va chạm mạnh từ vùng hữu hạn sang vùng vô hạn. Điều này cho phép ký các bức điện có độ dài tuỳ ý. m t Gỉa sử h: (Z2) → (Z2) là một hàm hash không va chạm mạnh ,trong đó m ≥t- t 1. Ta sẽ dùng h đêu xây dựng hàm hash không va chạm mạnh h: X →(Z2) trong đó ∞ t X =(Z2) iU=m Tr−ớc tiên xét tr−ờng hợp m ≥ t+2. Ta sẽ xem các phần tử của X nh− các xây bit. |x| chỉ độ dàI của x (tức số các bit trong x) và x||y ký hiệu sự kết hợp các xây x và y. Giả sử |x| = n > m. Có thể biểu thị x nh− một chuỗi kết hợp. X = x1||x2|| ||xk Trong đó |x1| =|x2| = = |xk-1| = m- t-1 và |xk| = m- t- 1- d Hình 7.4. Mở rộng hàm hash h thành h* (m ≥t+2) Trang 39
40. Vietebooks Nguyễn Hoàng Cương 1. For i= 1 to k-1 do yi = xi d 2. yk = xk ||0 3. cho y là biểu diễn nhị phân của d k+1 4. gi = h(0I+1||y1) 5. for i=1 to k do g +1 = h(g ||1||y +1) i i i 6. h*(x) = gk +1 Trong đó m- t- 2 ≥ d ≥0. Vì thế ta có n k= ⎡ ⎤ ⎣⎢m − t −1⎦⎥ Ta định nghĩa h*(x) theo thuật toán biểu kiễn trong hình 7.4. Kí hiệu y(x) = y1||y2|| ||yk-1 Nhận xét rằng yk đ−ợc lập từ xk bằng cách chèn thêm d số 0 vào bên phảI để tất cả các khối yi (k ≥ i ≥ 1)đều có chiều dàI m-t-1. Cũng nh− trong b−ớc 3 yk+1 sẽ đ−ợc đệm thêm về bên tráI các số 0 sao cho |yk+1| = m-t-1. Để băm nhỏ x ,tr−ớc hết ta xây dựng hàm y(x) và sau đó “chế biến” các khối y1 yk+1 theo một khuôn mẫu cụ thể. Điều quan trọng là y(x) ≠y(x’) khi x≠x. Thực tế yk+1 đ−ợc định nghĩa theo cách các phép ánh xạ x → y(x)là một đơn ánh. Định lý sau đây chứng minh rằng h* là an toàn khi h an toàn. Định lý 7.3 n Giả sử h: (Z2) →(Z2) là hàm hash không va chạm mạnhm≥ t+2. Khi đó ∞ t t hàm h*: Ui=m (Z2) →(Z2) đ−ợc xây dựng nh− trên hình 7.4 là hàm hash không và chạm mạnh. Chứng minh: Giả sử rằng ,ta có thể tìm đ−ợc x ≠x’ sao cho h*(x) = h*(x’). Nếu cho tr−ớc một cặp nh− vậy, ta sẽ chỉ ra cách có thể tìm đ−ợc một va chạm đối với Trang 40
41. Vietebooks Nguyễn Hoàng Cương h trong thời gian đa thức. Vì h đ−ợc giả thiết là không va chạm mạnh nên dẫn đến một mâu thuẫn nh− vậy h sẽ đ−ợc chứng minh là không va chạm mạnh. Kí hiệu y(x)= y1|| ||yk+1 Và y(x’) = y1’|| ||yk+1’ ở đây x và x’ đ−ợc đệm thêm d và d’ số 0 t−ơng ứng trong b−ớc 2. Kí hiệu tiếp các giá trị đ−ợc tính trong các b−ớc 4 và 5 là g1,g2 ,gk+1 và g1’, ,gk+1’ t−ơng ứng. Chúng ta sẽ đồng nhất hai tr−ờng hợp tuỳ thuộc vào việc có hay không |x| ≡|x’| (mod m-t-1). Tr−ờng hợp1: |x| ≠|x’| (mod m-t-1) Tại đây d ≠d’ và yk+1 ≠y’k+1. Ta có: H(gk||1||yk+1) = gk+1 =h*(x) = h*(x’) =g’l+1 = h(g’l+1||1||y’l+1) là một va chạm đối với h vì yk+1 ≠ y’k+1. Tr−ờng hợp2: |x| ≡|x’| (mod m-t-1) Ta chia tr−ờng hợp này thành hai tr−ờng hợp con: Tr−ờng hợp 2a: |x| = |x’|. Tạ đây ta có k= l và yk+1 = y’k+1. Ta vắt đầu nh− trong tr−ờng hợp 1: h(gk||1||yk+1) = gk+1 = h*(x) = h*(x’) = h(g’k||1||y’k+1) Nếu gk = g’k thì ta tìm thấy một va chạm đối với h, vì thế giả sử gk = g’k khi đó ta sẽ có: h(gk-1||1||yk) = gk =g’k Trang 41
42. Vietebooks Nguyễn Hoàng Cương i+1 =h(0||y1) Hoặc là tìm thấy một va chạm đối với h hoặc gk-1 =g’k-1 và yk = y’k. Giả sử không tìm thấy va chạm nào ,ta tiếp tục thực hiện ng−ợc các b−ớc cho đến khi cuối cùng nhận đ−ợc : h(0i+1||y1) = g1 =g’i-k+1 =g(g’i-k||1||y’i-k+1). i+1 Nh−ng bit thứ (t+1) của 0 ||y1 bằng 0 và bit thứ (t+1) của g’i-k+1||1||y’i-k+1 bằng 1. Vì thế ta tịm thấy một va chạm đối với h. Vì đã xét hết các tr−ờng hợp có thể nên ta có kết luận mong muốn. Cấu trúc của hình 7.4 chỉ đ−ợc dùng khi m>= t+2. Bây giờ ta hãy xem xét tình huống trong đó m = t+1. Cần dùng một cấu trúc khác cho h. Nh− tr−ớc đây, giả sử |x|=n>m. Tr−ớc hết ta mã x theo cách đặc biệt. Cách này dùng hàm f có định nghĩa nh− sau: f(0) = 0 f(1) = 01 Thuật toán để xây dựng h*(x)đ−ợc miêu tả trong hình 7.5 Phép mã x→y = y(x) đ−ợc định nghĩa trong v−ớc 1 thoả mãn hai tính chất quan trọng sau: 1. nếu x ≠x’ thì y(x)≠ y(x’) (tức là x→ y(x) là một đơn ánh) 2. Không tồn tạI hai chuỗi x≠ x’ và chuỗi z sao cho y(x)= z||y(x’). Nói cách khác không cho phép mã hoá nào là fpsstix của phép mã khác. ĐIều này dễ dàng thấy đ−ợc do chuỗi y(x) bắt đầu bằng 11 và không tồn tạI hai số 1 liên tiếp trong phần còn lạI của chuỗi). Hình 7.5 Mở rộng hàm hash h thành h* (m = t+1) 1. Giả sử y = y1y2 yk = 11||f(x1)|| ||f(xn) 1 2. g1 = h(0 ||y1) 3. for i=1 to k-1 do gi+1 = h(gi||yi+1) 4. h*(x) = gk Trang 42
43. Vietebooks Nguyễn Hoàng Cương Định lý 7.4 n Giả sử h: (Z2) →(Z2) là hàm hash không va chạm mạnh. Khi đó hàm ∞ t t h*: Ui=m (Z2) →(Z2) đ−ợc xây dựng nh− trên hình 7.5 là hàm hash không va chạm mạnh. Chứng minh: Giả sử rằng ta có thể tìm đ−ợc x ≠x’ sao cho h*(x)=h*(x’). Kí hiệu: y(x) = y1y2 yk và y(x’) = y’1y’2 y’l Ta xét hai tr−ờng hợp: Tr−ờng hợp 1: k=l Nh− trong định lý 7.3 hoặc ta tìm thấy một va chạm đỗi với h hoặc ta nhận đ−ợc y = y’ song đIều này lạI bao hàm x = x’, dẫn đến mâu thuẫn. Tr−ờng hợp2: k≠ l Không mất tính tổng quát ,giả sử l>k . tr−ờng hợp này xử lý theo kiểu t−ơng tự. Nếu giả thiết ta không tìm thấy va chạm nào đối với h ,ta có dãy các ph−ơng trình sau: yk = y’l yk-1 = y’l-1 y1 = y’l-k+1 Song đIều này mâu thuẫn với tính chất “không posfixx” nêu ở trên. Từ đây ta kết luận rằng h* là hạm không va chạm. Ta sẽ tổng kết hoá hai xây dựng trong phần này và số các ứng dụng của h cần thiết để tính h* theo định lý sau: Định lý 7.5 n Giả sử h: (Z2) →(Z2) là hàm hash không va chạm mạnh,ở đây m>=t+1. Khi đó tồn tạI hàm không va chạm mạnh Trang 43
44. Vietebooks Nguyễn Hoàng Cương ∞ t t h*: Ui=m (Z2) →(Z2) Số lần h đ−ợc tính trong −ớc l−ợng h* nhiều nhất bằng : ⎡ n ⎤ l +⎢ ⎥ nếu m>=t+2 ⎣m − t −1⎦ 2n +2 nếu m= t+2 trong đó |x|=n. 7.6 các hàm hash dựa trên các hệ mật Cho đến nay, các ph−ơng pháp đã mô tả để đ−a đến nhứng hàm hash hầu nh− đều rất chậm đối với các ứng dụng thực tiễn. Một biện pháp khác là dùng các hệ thống mã hoá bí mật hiện có để xây dừng các hàm hash. Giả sử rằng (P,C,K,E,D) là một hệ thống mật mã an toàn về mặt tính toán. Để thuận n tiện ta cũng giả thiết rằng P = C = K = (Z2) .ở đâychọn n>=128 để xây ngăn chặn kiểu tấn công ngày sinh nhật. ĐIều này loạI trừ việc dùng DES (vì độ dài khoá của DES khác với độ dài bản rõ). Giả sử cho tr−ớc một xâu bit: x= x1||x2|| ||xk n trong đó xi ∈ (Z2) , 1≤ i ≤ (nếu số bit trong x không phải là bội của n thì cần chèn thêm vào x theo cách nào đó. Chẳng hạn nh− cách làm trong nục 7.5. Để đơn giản ta sẽ bỏ qua đIểm này). ý t−ởng cơ bản là bắt đầu bằng một “giá trị ban đầu” cố định g0 =IV và sau đó ta xây dựng g1, ,gk theo quy tắc thiết lập : gi = f(xi,gi-1). ở đây f là hàm kết hợp toàn bộ các phép mã hoá của hệ mật đ−ợc dùng. Cuối cùng ta định nghĩa bản tóm l−ợc của thông báo h(x) =gk. Vài hàm hash kiểu này đã đ−ợc đề xuất và nhiều loại trong chúng tỏ ra không an toàn (không phụ thuộc vào việc liệu hệ mật cơ bản có an toàn hay không ). Tuy nhiên , có 4 ph−ơng án khác nhau có vẻ an toàn của sơ đồ này : gi = e gi-1 (xi) ⊕ xi Trang 44
45. Vietebooks Nguyễn Hoàng Cương gi = e gi-1 (xi) ⊕ xI ⊕ gi-1 gi = e gi-1 (xi ⊕ gi-1) ⊕ xI gi = e gi-1 (xi ⊕ gi-1) ⊕ xI ⊕ gi-1. 7.7 Hàm hash MD4. Hàm hash MD4 đ−ợc Riverst đề xuất năm 1990 và một hiên bản mạnh là MD5 cũng đ−ợc đ−a ra năm 1991. Chuẩn hàm hash an toàn (hay SHS) phức tạp hơn song cũng d−a tên các ph−ơng pháp t−ơng tự. Nó đ−ợc công bố trong hồ sơ liên bang năm 1992 và đ−ợc chấp nhận làm tiêu chuẩn vào ngày 11/5/1993. Tất cả các hàm hash trên đều rất nhanh nên trên thực tế chúng dùng để kí các bức điện dài. Trong phần này sẽ mô tả chi tiết MD4 và thảo luận một số cảI tiến dùng trong MD5 và SHS. Cho tr−ớc một xâu bit tr−ớc hết ta tạo một mạng: M = M[0] M[1] M[N-1] . trong đó M[i] là xâu bit có độ dàI 32 và N ≡ 0 mod 16. Ta sẽ gọi M[i] là từ. M đ−ợc xây dựng từ x bằng thuật toán trong hình 7.6. Hình 7.6 Xây dựng M trong MD4 1. d = 447-(|x| mod 512) 2. giả sử l là kí hiệu biểu diễn nhị phân của |x| mod 264.|l| = 64 3. M = x||1||0d||l Trong việc xây dựng M, ta gắn số 1 ssơn lẻ vào x, sau đó sẽ gài thêm các số 0 đủ để độ dài trở nên đồng d− với 448 modulo 512.,cuối cùng nối thêm 64 bit ch−a biểu diễn nhị phân về độ dàI (ban đầu) của x(đ−ợc rút gọn theo móulo 264 nếu cần). Xâu kết quả M có độ dàI chia hết cho 512. Vì thế khi chặt M thành các từ 32 bit , số từ nhận đ−ợc là N-sẽ chia hết cho 16. Bây giờ, tiếp tục xây dựng bản tóm l−ợc thông báo 128 bit. Hình 7.7 đ−a ra mô tả thuật toán ở mức cao. Bản tóm l−ợc thông báo đ−ợc xây dựng nh− sự kết nối 4 từ A,B,C và D mà ta sẽ gọi là các thanh ghi. Bốn thanh ghi đ−ợc khởi động nh− trong b−ớc 1. Tiếp theo ta xử lí bảng M 16 bit từ cùng lúc. Trong mỗi vòng lặp ở b−ớc 2, đầu tiên lấy 16 từ “tiếp theo” của M và l−u Trang 45
46. Vietebooks Nguyễn Hoàng Cương chúng trong bảng X (b−ớc 3). Các giá trị của bốn thanh ghi dịch sau đó sẽ đ−ợc l−u lại (b−ớc 4). Sau đó ta sẽ thực hiện ba vòng “băm” (hash). Mỗi vaòng gồm một phép toán thực hiện trên một trong 16 từ trong X. Các phép toán đ−ợc thực hiện trong ba vòng tạo ra các giá trị mới trong bốn thanh ghi. Cuối cùng ,bốn thanh ghi đ−ợc update (cập nhật) trong b−ớc 8 bằng cách cộng ng−ợc các giá trị l−u tr−ớc đó trong b−ớc 4. Phép cộng này đ−ợc xác định là cộng các số nguyên d−ơng ,đ−ợc rút gọn theo modelo 232. Ba vòng trong MD4 là khác nhau (không giông nh− DES. 16 vòng đều nh− nhau). Tr−ớc hết ta sẽ mô tả vàI phép toán khác nhau trong ba vòng này. Trong phần sau,ta kí hiệu X và Y là các từ đầu vào và mỗi phép toán sẽ tạo ra một từ đầu ra. D−ới đây là phép toán đ−ợc dùng: X∧Y là phép “AND” theo bit giữa X và Y X∨Y là phép “OR” theo bit giữa X và Y X⊕Y là phép “XOR” theo bit giữa X và Y ơX chỉ phần bù của X X+Y là phép cộng theo modulo 232. X = s >=0). Chú ý rằng, tất cả các phép toán trên đều tất nhanh và chỉ có phép số học duy nhất đ−ợc dùng là phép cộng modulo 232. Nếu MD4 đ−ợc ứng dụng thì cần tính đến kiến trúc cơ bản của máy tính mà nó chạy trên đó để thực hiện chính xác phép cộng. Giả sử a1a2a3a4 là 4 byte trong từ xem mỗi ai,nh− một số nguyên trong dảI 0-255 đ−ợc biểu diễn d−ới dạng nhị phân. Trong kiến trúc kiểu endian lớn (chẳng hạn nh− trên trạm Sunsparc) từ này biểu diễn số nguyên. 24 16 8 a12 + a22 + a32 + a4 Trong kiến trúc kiểu endian nhỏ (chẳng hạn họ intel 80xxx). Từ này biểu diễn số nguyên: 24 16 8 a42 + + a3 2 + a2 2 +a1 MD4 giả thiết dùng kiến trúc kiểu endian nhỏ. ĐIều quan trọng là bản tóm l−ợc thông báo độc lập với kiến trúc cơ bản. Vì thể nếu muốn chạy MD4 trên máy tính endian lớn cần thực hiện phép cộng X+Y nh− sau: 1. Trao đổi x1 và x4; x2 và x3; y1 và y4; y2 và y3 2. Tính Z = X+Y mod 232 3. Trao đổi z1 và z4 ; z2 và z3. Trang 46
47. Vietebooks Nguyễn Hoàng Cương Hình 7.7 hàm hash MD4 1. A= 67452301 (hệ hexa) B = efcdab89 (hệ hexa) C = 98badcfe (hệ hexa) D = 10325476 (hệ hexa) 2. for i = 0 to N/16-1 do 3. for i = 1 to 15 do X[i] = M[16i+j] 4. AA = A BB = B CC = C DD = D 5. round1 6. round2 7. round3 8. A = A+AA B = B+ BB C = C + CC D = D + DD Các vòng 1, 2 và 3 của MD4 dùng t−ơng ứng ba hàm f, g, và h. Mỗi hàm này là một hàm boolean tính theo bit dùng 2 từ làm đầu vào và tạo ra một từ tại đẩu ra. Chúng đ−ợc xác định nh− sau: f(X,Y,Z) = (X∧Y) ∨((-X)∧Z) g(X,Y,Z) = (X∧Y) ∨(X∧Z) ∨(Y∧Z) h(X,Y,Z) = X⊕ Y⊕ Z Các hình 7.8-7.10 sẽ mô tả đầy đủ các vòng 1,2 và 3 của MD4. MD4 đ−ợc thiết kế chạy rất nhanh và quả thực phần mềm chạy trên máy Sun SPARC có tốc độ 1.4 Mbyte/s. Mặt khác, khó có thể nói đIều gì cụ thể về độ mật của hàm hash, chẳng hạn nh− MD4 vì nó không dựa trên vàI toán khó đã nghiên cứu kĩ (ví dụ nh− phân tích nhân tử trên bàI toán logarithm rời rạc). Vì thế trong tr−ờng hợp Dé sự tin cậy vào độ an toàn của hệ thống chỉ có thể đạt đ−ợc về thời gian và nh− vậy có thể hi vọng hệ thống vừa đ−ợc nghiên cứu và không tìm thấy sự không an toàn nào. Trang 47
48. Vietebooks Nguyễn Hoàng Cương Hình 7.8 : Vòng 1 của MD4 .(round 1) 1. A = (A+ f(B,C,D) + X[0]) << 3 2. D = (D + f(A,B,C) +X[1]) << 7 3. C = (C + f(D,A,C) +X[2]) << 11 4. B = (B + f(C,D,A) +X[3]) << 19 5. A = (A + f(B,C,D) +X[4]) << 3 6. D = (D + f(A,B,C) +X[5]) << 7 7. C = (C + f(D,A,C) +X[6]) << 11 8. B = (B + f(C,D,A) +X[7]) << 19 9. A = (A + f(B,C,D) +X[8]) << 3 10. D = (D + f(A,B,C) +X[9]) << 7 11. C = (C + f(D,A,C) +X[10]) << 11 12. B = (B + f(C,D,A) +X[11]) << 19 13. A = (A + f(B,C,D) +X[12]) << 3 14. D = (D + f(A,B,C) +X[13]) << 7 15. C = (C + f(D,A,C) +X[14]) << 11 16. B = (B + f(C,D,A) +X[15]) << 19 Mặc dù MD4 vẫn ch−a bị phá song các phiên bản yếu cho phép bỏ qua hoặc vòng thứ nhất hoặc thứ ba dều có thể bị phá không khó khăn gì. nghĩa là dễ dàng tìn thấy các va chạm đối với các phiên bản chỉ có hai vòng. Phiên vản mạnh của MD5 là MD5 đ−ợc công bố năm 1991. MD5 dùng vòng thay cho ba và chậm hơn 30% so với MD4 (khoảng 0.9 Mbyte/s trên cùng máy). Chuẩn hàm hash an toàn phức tạp và chậm hơn. Ta sẽ không mô tả đầy đủ song sẽ chỉ ra một vàI cảI tiến trên nó. 1. SHS đ−ợc thiết kế để chạy trên máy kiến trúc endian lớn hơn là trên máy endian nhỏ. 2. SHA tạo ra các bản tóm l−ợc thông báo 5 thanh ghi (160 bit). 3. SHS xử lí 16 từ của bức điện cùng một lúc nh− MD4. Tuy nhiên, 16 từ tr−ớc tiên đ−ợc ”mở rộng” thành 80 từ ,sau đó thực hiện một dãy 80 phép tính ,mỗi phép tính trên một từ. Hình 7.9 Vòng 2 củaMD4. Trang 48
49. Vietebooks Nguyễn Hoàng Cương 1. A = (A +g(B,C,D) + X[0] + 5A827999) <<3 2. D = (D +g(A,B,C) + X[4] + 5A827999) <<5 3. C = (C +g(D,A,B) + X[8] + 5A827999) <<9 4. B = (B +g(C,D,A) + X[12] + 5A827999) <<13 5. A = (A +g(B,C,D) + X[1] + 5A827999) <<3 6. D = (D +g(A,B,C) + X[1] + 5A827999) <<5 7. C = (C +g(D,A,B) + X[5] + 5A827999) <<9 8. B = (B +g(C,D,A) + X[13] + 5A827999) <<13 9. A = (A +g(B,C,D) + X[2] + 5A827999) <<3 10. D = (D +g(A,B,C) + X[6] + 5A827999) <<5 11. C = (C +g(D,A,B) + X[10] + 5A827999) <<9 12. B = (B +g(C,D,A) + X[14] + 5A827999) <<13 13. A = (A +g(B,C,D) + X[3] + 5A827999) <<3 14. D = (D +g(A,B,C) + X[7] + 5A827999) <<5 15. C = (C +g(D,A,B) + X[11] + 5A827999) <<9 16. B = (B +g(C,D,A) + X[15] + 5A827999) <<13 Dùng hàm mở rộng sau đây: Cho tr−ớc 16 từ X[0] X[15], ta tính thêm 64 từ nữa theo quan hệ đệ quy. X[j] = X[j-3]⊕ X[j-8]⊕ X[j-14]⊕ X[j-16], 79 ≥ j ≥ 16 7.1 Kết quả của ph−ơng trình (7.1) là mỗi một trong các từ X[16] X[79] đ−ợc thiết lập bằng cách cộng ⊕ với một tập con xác định nào đó của các từ X[0] X[15]. Ví dụ: Ta có: X[16] = X[0] ⊕X[2]⊕X[8]⊕X[13] X[17] = X[1] ⊕X[3]⊕X[9]⊕X[14] X[18] = X[2] ⊕X[4]⊕X[10]⊕X[15] X[19] = X[0] ⊕X[2]⊕X[3]⊕X[5]⊕X[8]⊕X[11]⊕X[13] X[79] = X[1] ⊕X[4]⊕X[15]⊕X[8]⊕X[12]⊕X[13]. Một đề xuất đòi hỏi sửa lại SHS liên quan đến hàm mở rộng trong đó đề nghị đặt lại ph−ơng trình 7.1 nh− sau: X[j] = X[j-3] ⊕X[j-8]⊕X[j-14]⊕X[j-16] <<1; 79≥ j ≥ 16 (7.2) Trang 49
50. Vietebooks Nguyễn Hoàng Cương Hình 7.10 : Vòng ba của MD4. 1. A = (A + h(B,C,D) + X[0] + 6ED9EBA1) <<3 2. D = (D + h(A,B,C) + X[8] + 6ED9EBA1) <<9 3. C = (C + h(D,A,B) + X[4] + 6ED9EBA1) << 11 4. B = (B + h(C,D,A) + X[12] + 6ED9EBA1) << 15 5. A = (A + h(B,C,D) + X[2] + 6ED9EBA1) <<3 6. D = (D + h(A,B,C) + X[10] + 6ED9EBA1) <<9 7. C = (C + h(D,A,B) + X[6] + 6ED9EBA1) << 11 8. B = (B + h(C,D,A) + X[14] + 6ED9EBA1) << 15 9. A = (A + h(B,C,D) + X[1] + 6ED9EBA1) <<3 10. D = (D + h(A,B,C) + X[9] + 6ED9EBA1) <<9 11. C = (C + h(D,A,B) + X[13] + 6ED9EBA1) << 11 12. B = (B + h(C,D,A) + X[13] + 6ED9EBA1) << 15 13. A = (A + h(B,C,D) + X[3] + 6ED9EBA1) <<3 14. D = (D + h(A,B,C) + X[11] + 6ED9EBA1) <<9 15. C = (C + h(D,A,B) + X[7] + 6ED9EBA1) << 11 16. B = (B + h(C,D,A) + X[15] + 6ED9EBA1) << 15 Nh− tr−ớc đây , toán tử ’’<<1’’ là phép dịch vòng trái một vị trí. 7.8 nhãn thời gian (timestamping). Một khó khăn trong sơ đồ chữ kí là thuật toán kí có thể bị tổn th−ơng. Chẳng hạn, giả sử Oscar có khả năng xác định số mũ mật a của Bob trên bất kì bức điện nào mà anh ta muốn. Song còn vấn đề khác (có thể nghiêm trọng hơn )là : từ đây ng−ời ta sẽ đặt câu hởi về tính xác thực của tất cả các bức điện mà Bob kí, kể cả những bức điện mà anh ta kí tr−ớc khi Oscar đánh cắp đ−ợc thuật toán. Từ đây lại có thể nảy sinh tình huống không mong muốn khác : giả sử Bob kí một bức điện và sau đó từ chối là đã không kí nó. Bob có thể công khai thuật toán kí của mình sau đó công bố rằng chữ kí của anh ta trên bức điện đang nói trên là giả mạo. Trang 50
51. Vietebooks Nguyễn Hoàng Cương Lí do có các kiểu sự kiện này là do không có các nào các định bức điện đ−ợc kí khi nào. Nhãn thời gian có thể cung cấp bằng chứng rằng, bức điện đã đ−ợc kí vào thời điểm cụ thể nào đó. Khì đó nế thuật toán kí của Bob có nh−ợc điểm (bị tổn th−ơng) thì bất kì chữ kí nào anh ta kí tr−ớc đó sẽ không còn hợp lệ. ĐIều này giống với kiểu thực hiên các thẻ tín dụng: Nếu ai đó làm mất thẻ tín dụng và thông báo cho nhà băng đã phát hành thì thẻ mất hiệu lực. Song các cuộc mua bán thực hiện tr−ớc khi mất nó thì vẫn không bị ảnh h−ởng. Trong phần này sẽ mô tả một vàI ph−ơng pháp gắn nhãn thời gian. Tr−ớc hết,nhận xét rằng, Bob có thể tạo ra một nhãn thời gian có sức thuyết phục trên chữ kí của anh ta. Đầu tiên, Bob nhận đ−ợc một thông tin “hiện thời “ có sẵn công khai nào đó, thông tin này không thể dự đoán đ−ợc tr−ớc khi nó xảy ra. Ví dụ thông tin chứa tất cả các lợi thế về môn bóng chày của các liên minh chính từ ngày tr−ớc đó, hay các giá trị của tất cả cổ phần đwocj lên danh sách trong sở giao dịch chứng khoán NewYork. Ta kí hiệu thông tin này bằng chữ pub. Bây giờ giả sử Bob muốn dán nhãn thời gian trên chữ kí của mình trên bức điện x. Giả thiết rằng, h là hàm hash công khai biết tr−ớc. Bob sẽ thực hiện theo thuật toán trong hình 7.11.Sau đây là cách sơ đồ làm việc : sự có mặt của thông tin pub có nghĩa là bob không thể tạo ra đ−ợc y tr−ớc ngày đang nói đến. Còn một thực tế là y công bố trong một tờ báo ra ngày tiếp theo chứng tỏ rằng bob đã không tính y sau ngày đ−ợc nói đến. Vì thế chữ kí y của bob bị hạn chế trong thời hạn một ngày. Cũng nhận xét thấy rằng, bob không để lộ bức điện x trong sơ đồ này vì chỉ có x đ−ợc công bố Nếu cần bob có thể chứng minh rằng x là bức điện mà anh ta đã kí và dán nhãn thời gian một cách đơn giản là làm lộ nó. Cũng không khó khăn tạo ra tạo ra các nhãn thời gian nếu có một cơ quan dịch vụ dán nhãn đáng tin cậy. Bob có thể tính z = h(x) và y = sigk (z) và sau đó gửi (z và x ) đến cơ quan làm dịch vụ dán nhãn thời gian (TSS). TSS sau đó sẽ gắn ngày D và kí (đánh dấu)bộ ba (z,y,D). Công việc này sẽ hoàn hảo miễn là thuật toán kí của TSS an toàn và TSS không thể bị mua chuộc để lùi ngày dãn nhãn của thời gian. (chú ý rằng ph−ơng pháp này chỉ đ−ợc thiết lập khi bob đã kí một bức điện tr−ớc một thời gian nào đó. Nếu bob muốn thiết lập cáI anh ta đã kí nó sau ngày nào đó ,anh ta có thể kết hợp thông tin công khai pub nào đó nh− ph−ơng pháp tr−ớc đó). Hình 7.11 :Dán nhãn thời gian lên chữ kí trên bức điện x. Trang 51
52. Vietebooks Nguyễn Hoàng Cương 1. Bob tính z = h(x). 2. Bob tính z’ = h(z ||pub). 3. Bob tính y = sigk(z’). 4. Bob công bố (z,pub,y) trên tờ báo ra ngày hôm sau. Nếu nh− không muốn tin vô điều kiện vào TSS thì có thể tăng độ an toàn lên bằng cách liên kết các thông báo đã dán nhãn thời gian. Trong sơ độ nh− vậy, bob sẽ gửi một bộ ba đ−ợc xếp thứ tự (z,x,ID)(Bob) cho TSS. ở đây, z là bản tóm l−ợc thông báo của bức điện x,y là chữ kí của bob trên z ,còn ID(Bob) là thông tin định danh của Bob. TSS sẽ dãn nhãn thời gian một chuỗi bộ ba có dạng này. Kí hiệu (zn,yn,IDn) là bộ ba thứ tự n đ−ợc TSS dán nhãn thời gian và cho tn là kí hiệu thời gian lúc thực hiện yêu cầu thứ n. Hình 7.12: Dán nhãn thời gian (zn,yn,IDn). 1. TSS tính Ln = (tn-1,IDn-1,Zn-1yn-1,h(Ln-1)) 2. TSS tính C = (n, t , z , ID , L ) n n n n n 3. TSS tính Sn = sigTSS (h (Cn)) 4. TSS gửi (C , S , ID ) cho ID . n n n n TSS sẽ dán nhãn thời gian lên bộ ba thứ n bằng fthuật toán nêu trên hình 7.12. Ln là “thông tin liên kết để nối yêu cầu thứ n vào yêu cầu tr−ớc đó. (L0 đ−ợc chọn làm thông tin gia nào đó (đ−ợc xác định tr−ớc đây)để quá trình đ−ợc bắt đầu)”. Bây giờ nếu đ−ợc yêu cầu (challenge). Bob có thể để lộ bức điện xn của mình, và sau đó có thể xác minh yn. Tiếp theo , các minh chữ kí sn của TSS. Nếu muốn thì có thể đòi IDn-1 hoặc IDn+1 để tạo ra nhãn thời gian (Cn-1, Sn-1, IDn) và (Cn+1, Sn+1, IDn+2) t−ơng ứng của chúng. Các chữ kí của TSS có thể đ−ợc kiểm tra theo nhãn thời gian này. Dĩ nhiên , quá trình này có thể tiếp tục tới mức mong muốn, tr−ớc hay sau đó. Trang 52
53. Vietebooks Nguyễn Hoàng Cương 7.9.các chú ý về tμi liệu dẫn Hàm hash log rời rạc đ−ợc mô tả trong mục 7.4 là của chaum , van heijst và pfitzmann [CvHP92]. Còn hàm hash có thể chứng mình đwocj là an toàn liễn là hợp số n không thể phân tích thành nhân t− là do gibson [Gib91] đ−a ra (bài tập 7.4 có mô tả sơ đồ này). Cơ sở cho việc m mở rộng hàm hash trong mục 7.5 là của Damgard [DA90] Merkle cũng đ−a ra các ph−ơng pháp t−ơng tự [ME90]. Các thông tin liên qua tới việc xây dựng các hàm hash dựa trên các hệ thông mã khoá bí mật. Bạn đọc có thể xem trong [PGV94] của Preneel, Govaerts và Vandewalle. Thuật toán MD4 đ−ợc đ−a ra trong [Ri91] của Rivest, còn tiêu chuẩn hash an toàn đ−ợc mô tả trong [NBS93]. Tấn công hai trong ba vòng MD4 là của Boer và Bossalaer [DBB92]. Các hàm hash gần đây kể cả N-hash là của [MOI90] và Snefru [ME90A]. Ngoài ra có thể tìm thấy tổng quan về kĩ thuật băm trong Preneel, Govaerts, Vandewalle [PGV93]. Bài tập Trang 53