›

Bài giảng các hàm Hash - Nguyễn Hoàng Cương

pdf 24 trang huongle 2840
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng các hàm Hash - Nguyễn Hoàng Cương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

  • pdfbai_giang_cac_ham_hash_nguyen_hoang_cuong.pdf

Nội dung text: Bài giảng các hàm Hash - Nguyễn Hoàng Cương

  1. Vietebooks Nguyễn Hoàng Cương 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 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. Trang 1
  2. Vietebooks Nguyễn Hoàng Cươ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 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ố tinhs 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’). Trang 2
  3. Vietebooks Nguyễn Hoàng Cương 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. 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 : Trang 3
  4. Vietebooks Nguyễn Hoàng Cương 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 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. Trang 4
  5. Vietebooks Nguyễn Hoàng Cương 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ể 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) Trang 5
  6. Vietebooks Nguyễn Hoàng Cương 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-ε) 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. Trang 6
  7. Vietebooks Nguyễn Hoàng Cương 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 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) Trang 7
  8. Vietebooks Nguyễn Hoàng Cương 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 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) Trang 8
  9. Vietebooks Nguyễn Hoàng Cương 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 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 đó Trang 9
  10. Vietebooks Nguyễn Hoàng Cương ∞ 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) 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 Trang 10
  11. Vietebooks Nguyễn Hoàng Cương 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 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) Trang 11
  12. Vietebooks Nguyễn Hoàng Cương 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 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: Trang 12
  13. Vietebooks Nguyễn Hoàng Cương 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) = g Định lý 7.4 k 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: Trang 13
  14. Vietebooks Nguyễn Hoàng Cương 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 ∞ 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 Trang 14
  15. Vietebooks Nguyễn Hoàng Cương 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 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 Trang 15
  16. Vietebooks Nguyễn Hoàng Cương 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 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 Trang 16
  17. Vietebooks Nguyễn Hoàng Cương 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. 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 Trang 17
  18. Vietebooks Nguyễn Hoàng Cương 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. 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 Trang 18
  19. Vietebooks Nguyễn Hoàng Cương 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. 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 Trang 19
  20. Vietebooks Nguyễn Hoàng Cương 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) 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 Trang 20
  21. Vietebooks Nguyễn Hoàng Cương 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. 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ỏ Trang 21
  22. Vietebooks Nguyễn Hoàng Cương 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. 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 L = (t ,ID ,Z y ,h(L )) n n-1 n-1 n-1 n-1 n-1 2. TSS tính Cn = (n, tn, zn, IDn, Ln) 3. TSS tính Sn = sigTSS (h (Cn)) 4. TSS gửi (Cn, Sn, IDn ) cho IDn. Trang 22
  23. Vietebooks Nguyễn Hoàng Cương 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 đó. 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 7.1. Giả sử h: X →Y là hàm hash. Với y bất kỳ ∈Y, cho: Trang 23
  24. Vietebooks Nguyễn Hoàng Cương h-1(y) = { x: h(x) = y} -1 và ký hiệu sy = | h (y)|. Định nghĩa N = Trang 24