Tài liệu Kỹ thuật lập trình - Chương 11: Hàm hash

Hàm hash có vai trò rất quan trọng, ngoài tránh được sự giả mạo chữ ký, nó còn giúp cho quá trình ký diễn ra nhanh hơn rất nhiều, bởi hàm hash có tốc độ lớn, nhưng quan trọng nhất là nó làm chữ ký ngắn đi rất nhiều điều này có vai trò rất quan trọng trong thực tế khi làm việc với số lượng lớn các chữ ký. Cùng tham khảo tài liệu để nắm kiến thức về hàm hash.
Nội dung trích xuất từ tài liệu:
Tài liệu Kỹ thuật lập trình - Chương 11: Hàm hash Chương 11 HÀM HASH 11.1 Tổng quan về hàm Hash Đây là hàm có tham số đầu vào là văn bản có chiều dài bất kỳ và chiều ra là một bảntóm lượt có chiều dài cố định. Như đã nói trong phần chữ ký số, hàm hash có vai trò rất quan trọng, ngoài tránhđược sự giả mạo chữ ký, nó còn giúp cho quá trình ký diễn ra nhanh hơn rất nhiều, bởihàm hash có tốc độ lớn, nhưng quan trọng nhất là nó làm chữ ký ngắn đi rất nhiều điềunày có vai trò rất quan trọng trong thực tế khi làm việc với số lượng lớn các chữ ký. Để tạo ra hàm Hash thì hàm hash phải thỏa mãn các yêu cầu sau: 1. Đối số của hàm hash là bản tin có chiều dài bất kỳ; 2. Giá trị của hàm hash có chiều dài không đổi; 3. Hàm H(x) cần phải có tính toán hiệu quả, tức là thuật toán Hash khi thực hiện trên phần cứng và phần mềm cần phải có công suất lớn. Phải đảm bảo được rằng quá trình ký và kiểm tra lên giá trị của hàm hash nhanh hơn so với quá trình ký và kiểm tra trên bản thân bản tin; 4. Cho y là giá trị của hàm hash, thì khó về mặt tính toán đ ể tìm đ ược x th ỏa h(x)=y, tức là hàm hash phải là hàm một chiều; 5. Hàm hash là hàm không va chạm, tức là khi cho trước bản tin x, không thể thực hiện được về mặt tính toán để tìm được bản x’ ≠ x sao cho h(x)=h(x’). 6. Hàm hash là hàm không va chạm mạnh, khi không thể thực hiện được về mặt tính toán để tìm được hai bản tin x và x’, với x’ ≠ x mà h(x)=h(x’). Cấu trúc chung của hàm băm Hash gồm các phần sau: 1. Cho trước một thông điệp M có độ dài bất kỳ. Tùy theo thuật toán được sử dụng, chúng ta có thể cần thêm thông điệp các bit để nhận được thông điệp có độ dài là bội số của chiều dài cố định cho trước để phục vụ cho việc tính toán. Chia thông điệp thành từng khối có kích thước bằng nhau tức là M=( M1, M2, …Ms). 2. Gọi Hi là trạng thái có kích thước n bit, n là chiều dài của giá trị hàm băm, F là hàm nén thực hiện thao tác trộn khối dữ liệu với trạng thái hiện hành: • Khởi tạo H0, bằng véc tơ khởi tạo nào đó. • Thực hiện trộn: Hi=F(Hi-1,Mi), i∈ [1,s]. 3. Giá trị của Hs là giá trị của hàm băm. Nếu hàm hash được cho là bền vững, khi có một sự thay đổi bất kỳ đối số của nó( tức là bản tin đầu vào) thì giá trị của nó cũng thay đổi ngẫu nhiên, tức là mỗi bít trongn bít có xác suất bị thay đổi là ½. Một phương pháp tấn công đơn gi ản trên hàm mộtchiều hash là lựa chọn bản tin sao cho giá trị hàm hash của nó bằng với giá trị hàm hashđã cho hay nói cách khác đây là phương pháp véc cạn, chúng ta gọi số lượng bản tin cầnchọn là N mà thỏa mãn được điều trên. Chúng ta thấy xác suất để giá trị hàm hash c ủamột bản tin bất kỳ không trùng với giá trị H đã cho bằng 1 − 2 − n , n là chiều dài của giá trịhàm hash. Như thế xác suất để không một bản tin nào từ N bản tin khác nhau mà giá trịcủa bản tin đó không trùng với H bằng p = (1 − 2 − n ) . Xác suất để tồn tại một bản tin Nmà giá trị hàm hash của nó bằng H cho trước là: p = 1 − p = 1 − (1 − 2− n ) N . Sử dụng công thức Niutơn, chúng ta nhận được giá trị gần đúng sau: N ( N − 1) 2 N ( N − 1)( N − 2) 3 (1 − x) N = 1 − Nx + x − x ... ≈ 1 − Nx , nếu như x nhỏ, 2! 3! Nên chúng ta có: p ≈ N ⋅ 2 − n và N ≈ p ⋅ 2 n . Khi p=1/2, chúng ta có N ≈ 2n −1 . Với kỹ thuật tính toán hiện nay thì n=64 thì tấn công có thể thực hiện được nếu có tài nguyên đủ lớn cho tính toán. Nếu như n > 96 thi được xem là an toàn đối với cách tấn công này, thế nhưng còn nhiều cách tân công khác, nên khuyến cáo chọn giá trị n ≥ 128 . 11.2 Hàm băm MD4 Hàm hash MD4 được Rivest đề xuất năm 1990. Chúng ta xem miêu tả thuật tóanMD4. Đầu vào: Bản tin M có chiều dài nhỏ hơn 264. 1. Mở rộng bản tin: Thêm các bít vào bản tin để bản tin có chiều dài là bội c ủa 512. Quá trình thêm diễn ra như sau. Thêm bít 1 vào cuối bản tin, sau đó thêm vào một số bít 0 để nhận bản tin có chiều dài là đồng dư với 448 modulo 512, và cuối cùng thêm vào 64 bít, 64bít này biểu diễn chiều dài của bản tin ban đầu. Bản tin được thêm vào bao gồm các khối M1, M2, … , Mn, chiều dài mỗi khối là 32 bít. 2. Khởi tạo các biến: A=67452301 B=EFCDAB89 C=98BADCFE D=10325476 3. i=1 4. for j=1 to 16 do X[j]=M[16i+j] 5. AA=A;BB=B;CC=C;DD=D; 6. round1 7. round2 8. round3 9. Nếu i < n/16 thì i=i+1 và quay về bước 4. 10. A=A+AA;B=B+BB;C=C+CC;D=D+DD;Đầu ra: 128 bít là liên kết của 4 từ 32 bít:A|B|C|D.Trong 3 vòng “round1”, “round2”,”round3” sử dụng 3 hàm bool sau: f(X,Y,Z)=(X^Y)v(( ¬ X)^Z). g(X,Y,Z)=(X^Y)v(X^Z)v(Y^Z). h(X,Y,Z)=X ⊕ Y ⊕ Z.Round1 được miêu tả như sau: 1. A=(A+f(B,C,D)+X[1])Round2 được miêu tả như sau: 1. A=(A+g(B,C,D)+X[1]+5A827999) 15. C=(C+h(D,A,B)+X[15] +6ED9EBA1)7. FF (c, d, a, b, X[7], S13, 0xa8304613);8. FF (b, c, d, a, X[8], S14, 0xfd469501);9. FF (a, b, c, d, X[9], S11, 0x698098d8);10. FF (d, a, b, c, X[10],S12, 0x8b44f7af);11. FF (c, d, a, b, X[11],S13, 0xffff5bb1);12. FF (b, c, d, a, X[12],S14, 0x895cd7be);13. FF (a, b, c, d, X[13],S11, 0x6b901122);14. FF (d, a, b, c, X[14],S12, 0xfd987193);15. FF (c, d, a, b, X[15],S13, 0xa679438e);16. FF (b, c, d, a, X[16],S14, 0x49b40821);Round 21. GG (a, b, c, d, X[2], S21, 0xf61e2562);2. GG (d, a, b, c, X[7], S22, 0xc040b340);3. GG (c, d, a, b, X[12],S23, 0x265e5a51);4. GG (b, c, d, a, X[1], S24, 0xe9b6c7aa);5. GG (a, b, c, d, X[6], S21, 0xd62f105d);6. GG (d, a, b, c, X[11],S22, 0x244145 ...