Chương 7: Các hàm hash

Bạn đọc có thể thấy rằng các sơ dồ chữ kí trong chương 6 chỉ chophé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.
Nội dung trích xuất từ tài liệu:
Chương 7: Các hàm hash chương 7 các hàm hash7.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ỉ chophé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ànhnhiều đoạn 160 bit, sau đó kí lên các đoạn đó độc lập nhau. Điều này cũngtươ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àigấ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ạntrong 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àykhô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ôngkhai nhanh. Hàm này lấy một bức điện có độ dài tuỳ ý và tạo ra một bảntó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àmHash đượ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ómlượ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ướchế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 bit7.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ự antoàn của sơ đồ chữ kí vì nó là bản tóm lược thông báo được chữ kí khôngphả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ố tinhschấ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ì đượcBob 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ứcmộ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ínhkhô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 choh (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ạocá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ẫunhiên như vậy. Sau đó anh ta tìm x sao cho z= h(x). Nếu làm được như vậythì (x,y) là bức điện giả mạo hợp lệ. Để tránh được tấn công này, h cầnthoả 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ôngbá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àmtí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ướctươ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à  ≥ 2 . X 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âubít có độ dài log2 và phần tử của Z được mã hoá như một xâu bít có độ Xdài log2 ...