Chapter 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ỉ 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.
Nội dung trích xuất từ tài liệu:
Chapter 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ỉ cho phépkí các bức điện nhỏ.Ví dụ, khi dùng DSS, bức điện 160 bit sẽ được kí bằngchữ 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õ độclậ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ướchế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í “antoà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ằngcá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ản tómlượ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ước hếtkhô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ự an toàncủ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 đượckí 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ạmnhư 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ệnx, 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ảntó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ácchữ 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ínhchấ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à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ùngthuật toán đảo với hàm Hash như một chương trình con (giả định ) trong thuậttoá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ếttiế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àilog2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 ...