Download miễn phí Một số nghiên cứu về hàm băm và giao thức mật mã
Mục lục
Trang
Nghiên cứu về thám mã MD4, Trần Hồng Thái 1
Va chạm vi sai của SHA-0, Florent Chaboud và Antoiene Joux, Crypto’98 31
Phân tích SHA-1 trong chế độ mã hoá, Helena Handchuh, Lars R. Knudsen
và Matthew J. Robshaw, CT-RSA 200148
Các hàm băm dựa trên mã khối: ph-ơng pháp thiết kế, Bart Preneel, René
Govaerts, Joó Vandewalle, CRYPTO’9364
Nguyên tắc thiết kế cho hàm băm, Ivan Bjerre Damgard, Eurocrypt’91 75
Hàm băm nhanh an toàn dựa trên mã sửa sai, Lars Knudsen và Bart
Preneel, Crypto’9787
Độ mật của hàm băm lặp dựa trên mã khối, Walter Hohl, Xuejia Lai,
Thomas Meier, Christian Waldvogel, Crypto 93102
Phân phối và thoả thuận khoá, Nguyễn Quốc Toàn 115
Xác thực và trao đổi khoá có xác thực, Whitfield Diffie, Paul C. Van
Oorschot và Michael J. Wierner,Design, Codes and Cryptography, 192123
Cập nhật thông tin về hàm băm SHA-1 145
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
suất lớn hơn)(
1
mP
.
Chứng minh:
Giả sử bổ đề là sai. Cho thuật toán ∆ có thể tính ngược f với xác xuất ít nhất
½+1/P(m), chúng ta chọn x phân bố đều và cho f(x) như là đầu vào của ∆. Nếu ∆
là thành công, chúng ta được y sao cho f(x) = f(y). Giả sử A là sự kiện rằng tạo
ảnh của f(x) có kích cỡ ít nhất bằng 2. {0,1}m ít nhất lớn gấp 2 lần so với ảnh của
f, và A xảy ra với xác suất lớn hơn ½. Cho nên, theo giả thuyết cho ∆, nó thành
công với xác xuất ít nhất 1/P(m) khi A xảy ra. Rõ ràng là, việc ∆ chọn phần tử nào
trong số các tạo ảnh của f(x) để đưa cho chúng ta là không tương quan với việc
77
chọn x (khi cho f(x)). Cho nên x ≠ y với xác xuất ít nhất bằng ½, nếu như A xảy ra
và ∆ là thành công.
Với khẳng địng thứ hai, chú ý rằng nếu Pf là phân bố đều, thì thành công của ∆ là
không tương quan với việc xảy ra của A. Nếu m-t = O(m), thì A xảy ra với xác
xuất áp đảo. Trong trường hợp ngược lại, ∆ cho chúng ta va chạm với xác xuất cơ
bản là 1/P(m).
Cuối cùng, chúng ta định nghĩa khái niệm về họ hàm băm không va chạm.
Định nghĩa 2.2
Họ hàm băm không va chạm H là họ vô hạn các tập hữu hạn { } và hàm bị
chặn đa thức t: N→ N. Phần tử của H
∞=1mmH
m là hàm h: {0,1}m → {0,1}t(m), và được gọi
là trường hợp riêng của H có kích thước m. H cần có các tính chất sau:
1. Cho giá trị của m, có thuật toán thời gian đa thức xác suất (theo m) Θ với đầu
vào m chọn được một trường hợp riêng của H có kích thước m một cách ngẫu
nhiên.
2. Với mỗi trường hợp riêng h ∈ Hm và x ∈ {0,1}*, h(x) là dễ tính, tức là tính
được trong thời gian đa thức theo cả m và |x|.
3. Khi cho một trường hợp riêng h ∈H được chọn ngẫu nhiên như trong 1), khó
tìm được x, y ∈ {0,1}*, sao cho h(x)=h(y) và x ≠ y.
Một cách hình thức: Với mỗi thuật toán ∆ thời gian đa thức xác suất, và đa
thức bất kỳ P, xét tập con các trường hợp riêng h kích thước m, mà đối với nó ∆
có xác xuất ít nhất 1/P(m) cho ra x ≠ y sao cho h(x) =h(y). Giả sử ε(m) là xã suất
để cho Θ chọn một trong các trường hợp riêng đó. Như một hàm số của m, ε(m) sẽ
tiến tới 0 nhanh hơn bất kỳ một phân số nào có mẫu số là đa thức.
3. Các kiến thiết cơ sở
Kết quả chính trong phần này là họ các hàm băm không va chạm có thể được kiến
thiết từ họ hàm băm không va chạm kích thước cố định.
Định lý 3.1
Giả sử F là họ hàm băm không va chạm độ dài cố định ánh xạ m bit vào t(m) bit.
Khi đó tồn tại họ hàm băm không va chạm H ánh xạ chuỗi có độ dài bất kỳ vào
các chuỗi t(m)-bit.
Giả sử h là một trường hợp riêng của H có kích thước m. Việc tính h với đầu vào
có kích thước n có thể làm trong nhiều nhất n/(m-t(m)+1)+1 bước khi dùng 1 bộ
xử lý (chúng ta tính hàm trong F như là một bước).
78
Chứng minh.
Với mỗi trường hợp riêng f ∈F với kích thước m, chúng ta sẽ kiến thiết trường
hợp riêng của h ∈H kích thước m. Đặt t=t(m). Với các chuỗi bit a, b, chúng ta ký
hiệu a||b là phép nối của a và b.
Việc kiến thiết được chia ra làm 2 trường hợp: trước hết là trường hợp m-t > 1, sau
đó là trường hợp m-t=1.
Chúng ta mô tả xem hàm h được tính như thế nào đối với đầu vào x ∈ {0,1}*:
Chúng ta chia x ra thành các khối m-t-1 bit. Nếu khối cuối cùng là chưa đủ thì ta
thêm 0 vào. Giả sử d là số các số 0 cần thiết. Giả sử các khối được ký hiệu bởi
x1,x2,...,xn/(m-t-1), với n=|x| (là độ dài sau khi padding).
Chúng ta thêm vào dãy này một khối nữa xn/(m-t-1)_+1 có (m-t-1) bit, nó chứa biểu
diễn nhị phân của d, nó có tiền tố là một số thích hợp các số 0.
Sau đó, ta định nghĩa dãy các khối có t bit h0, h1,...bởi:
h1 = f(0t+1||x1)
hi+1= f(hi ||1||xi+1)
Cuối cùng, đặt h(x)= hn/(n-m)+1.
Việc kiểm tra rằng H thoả mãn các điều kiện 1 và 2 trong Định nghĩa 2.2 là dễ.
Còn với điều kiện 3, giả thuyết ngược lại rằng chúng ta có thuật toán ∆ có thể tìm
x≠ x’ sao cho h(x) =h(x’).
Giả sử hi, xi (tương ứng ) là các kết quả trung gian trong việc tính h(x) (tương
ứng h(x’)).
'' , ii xh
Nếu |x| ≠ |x’| mod (m-t) thì sẽ có xn/(m-t)+1≠ x’n’/(m-t)+1, cho nên h(x)=h(x’) cho chúng
ta ngay lập tức va chạm của f. Cho nên bây giờ chúng ta giả thiết rằng |x| =|x’|
mod (m-t) và không mất tính tổng quát rằng |x’| ≥ |x|.
Hãy xem xét đẳng thức:
h(x)= f(hn/(m-t)||xn/(m-t)+1) = f(h’n’/(m-t)||x’n’/(m-t)+1) = h(x’)
Nếu hn/(m-t)||xn/(m-t)+1 ≠ h’n’/(m-t)||x’n’/(m-t)+1, chúng ta có va chạm của f, và thế là
xong. Nếu không, chúng ta xét thay vào đó đẳng thức
f(hn/(m-t)-1||xn/(m-t)) = f(h’n’/(m-t)-1||x’n’/(m-t))
và lặp lại lập luận. Rõ ràng là quá trình này cần dừng bằng cách hay là tạo ra
va chạm của f (vì x ≠ x’), hay là thiết lập ra đẳng thức
0t+1||x1 = h’i||1||x’i+1,
79
điều này là không thể.
Tóm lại, chúng ta có một phép suy dẫn, nó biến đổi ∆ thành một thuật toán tìm va
chạm cho f. Giả sử ∆ thao tác nhiều nhất T(m) bit. Thế thì x và x’ cần có độ
dài nhỏ hơn T(m).
Khi đó cả phép suy dẫn chiếm thời gian O(T(m)F(m)), với F(m) là thời gian cần
thiết để tính một giá trị của f, đặc biệt, nếu T là đa thức, thì cả phép suy dẫn sẽ
trong thời gian đa thức. Điều này cuối cùng mâu thuẫn với điều kiện 3 trong Định
nghĩa 2.1.
Cuối cùng, chúng ta bàn đến trường hợp m-t=1. Dễ dàng, nhưng là giải pháp
không hiệu quả đó là việc mã prefix-free tất cả các bản tin trước khi đem băm, sau
đó sử dụng kiến thiết tương tự như ở trên, thay đổi định nghĩa của h bằng
h1 = f(0t||x1)
hi+1 = f(hi||xi+1)
Ở đây, tất nhiên xi là các khối 1-bit. Cái đó có thể chứng minh là an toàn theo như
cùng một cách như trên.
Nếu f thoả mãn điều kiện thức hai trong Bổ đề 2.1, thì có một giải pháp hiệu quả
hơn: chúng ta chọn chuỗi y0 dài t-bit theo phân bố đều và định nghĩa:
h1 = f(y0||x1)
hi+1= f(hi||xi+1)
lần này không cần mã prefix free cho x. Lập luận ở trên sẽ chỉ ra rằng va
chạm cho h hay sẽ đem lại va chạm cho f hay tạo ảnh của y0. Nhưng khi đó
chúng ta sử dụng Bổ đề 2.1.
Các chú ý:
Phiên bản cuối của phép kiến thiết sử dụng Bổ đề 2.1, nó sẽ chỉ không làm việc
khi m-t=1, nhưng sẽ làm việc khi Pf là gần với phân bố đều, hay m-t = 0(m).
Điều này cần nhận biết bởi vì phiên bản này cho phép băm nhiều hơn 1 bit mỗi
lần áp dụng hàm f so với kiến thiết tổng quát, nên nó hiệu quả hơn một chút.
•
• Mẹo trong chứng minh ở trên là việc ghép khối thêm vào bản tin chỉ cần để
đảm bảo rằng chúng ta có thể nhận thấy sự khác biệt giữa các bản tin mà cần
phải thêm vào d số 0 với các bản tin kết thúc đơn giản bằng d số 0 trước khi
padding. Trong nhiều ứng dụng, hoàn toàn chấp nhận được là các số 0 phía sau
trong khối cuối cùng là bỏ qua được, trong trường hợp đó phần đó của kiến
thiết có thể bỏ qua.
Chúng ta hãy xem mối liên quan giữa Định lý 3.1 và các hàm băm đã biết. Trong
[Da], các hàm băm được kiến thiết từ các cặp claw-free các hoán vị, tức là các
80
hoán vị (f0, f1) có cùng miền xác định D, sao cho việc tìm x ≠ y và f0(x) =f1(y) là
bài toán khó. Chúng ta có thể kiến thiết trườn...