Mật mã cổ điển- Chương 7

Tham khảo tài liệu mật mã cổ điển- chương 7, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Mật mã cổ điển- Chương 7 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í trongchươ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àihơ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ặtcá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ũ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ảnkhoá. (Ví dụ: chế độ ECB trong DES). Biện pháp này có một số vấ đề trong việc tạo racác chữ kí số. Trước hết, với một bức điện dài, takế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ùngcác pháp số học phức tạp như số mũ modulo. Tuynhiê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ácnhau,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. Tacầ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í độclậ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àmHash 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ượcthông báo có kích thước qui định (160 bit nếu dùngDSS). Sau đó bản tóm lược thông báo sẽ được kí. VơiDSS, 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 taxâ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ởiai đó ) bằng cách trước hết khôi phục bản tóm lượcthô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 hkhô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ãnmộ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 đầubằ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ìmx ≠ 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ầnthoả 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 khicho 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ếtOscar 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ạmkhác.Định ngh ĩ a 7.2. Hàm Hash h là không va chạm mạnh nếu khôngcó 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ạmyế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ượcthô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ượcthông báo z ngẫu nhiên như vậy. Sau đó anh ta tìm xsao 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ôngnày, h cần thoả mãn tính chất một chiều (như tronghệ 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ộtbản tóm lược thông báo z, không thể thực hiện về mặttí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ôngva 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ậttoá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ìmcá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ữuhạn và  ≥ 2 . Đây là giả thiết hợp lí :Nếu xem X Zmột phần tử của X được mã như một xâu bít có độ dàilog2 và phần tử của Z được mã hoá như một xâu bít Xcó độ dài log2 thì bản tóm lược thông báo z = h(x) Xít nhất cũng ngắn hơn bức điện x một bít (ta sẽ quantâ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 tacũ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ấpnhận như đầu vào bản tóm lược thông báo z∈Z và tìmmộ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 đó  và hữu X Zhạn và X≥ 2 . Cho A là thuật toán đảo đối với h. ZKhi đó tồn tại một thuật toán Las Vagas xác suấttìm được một va chạm đối với h với xác suất ít nhấtlà1/2.Chứng minh : Xét thuật toán B đưa ra trong hình 7.2. Rõ ràngB 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ờikhông. Vấn đề còn lại là ta phải tịnh xac suất thànhcông, Với x bất kỳ thuộc X, định ngh ĩ a x ∼ x1 ...