Ta xét hai trường hợp: Trường hợp 1: k=l Như trong định lý hoặc ta tìm thấy một va chạm đỗi với h hoặc ta nhận được y = y’ song đIều này lạI bao hàm x = x’, dẫn đến mâu thuẫn. | Vietebooks Nguyễn Hoàng Cương Định lý Giả sử h Z2 n Z2 là hàm hash không va chạm mạnh. Khi đố hàm h U 7 m Z2 Z2 được xây dựng như trên hình là hàm hash không va chạm mạnh. Chứng minh Giả sử rằng ta có thể tìm được x x sao cho h x h x . Kí hiệu y x và y x y iy i Ta xét hai trường hợp Trường hợp 1 k l Như trong định lý hoặc ta tìm thấy một va chạm đỗi với h hoặc ta nhận được y y song điều này lại bao hàm x x dẫn đêh mâu thuẫn. Trường hợp2 k l Không mất tính tổng quát giả sử l k . trường hợp này xử lý theo kiểu tưong tự. Nêu giả thiêt ta không tìm thấy va chạm nào đối với h ta có dãy các phưong trình sau yk y l yk-1 y l-1 yi y l-k 1 Song điều này mâu thuẫn với tính chất không posfixx nêu ỏ trên. Từ đây ta kết luận rằng h là hạm không va chạm. Ta sẽ tổng kết hoá hai xây dựng trong phần này và số các ứng dụng của h cần thiết để tính h theo định lý sau Định lý Giả sửh Z2 n Z2 là hàm hash không va chạm mạnh ởđây m t 1. Khi đố tồn tại hàm không va chạm mạnh Trang 43 Vietebooks Nguyễn Hoàng Cương h . m Sô lần h được tính trong ước lượng h nhiều nhất bằng n m -1 -1 l nếu m t 2 2n 2 nếu m t 2 trong đố ỊxỊ n. các hàm hash dựa trên các hệ mật Cho đêh nay các phương pháp đã mô tả để đưa đêh nhứng hàm hash hầu như đều rất chậm đối với các ứng dụng thực tiễn. Một biện pháp khác là dùng các hệ thống mã hoá bí mật hiện có để xây dừng các hàm hash. Giả sử rằng P C K E D là một hệ thống mật mã an toàn về mặt tính toán. Để thuận tiện ta cũng giả thiêt rằng P C K Z2 đâychọn n 128 để xây ngăn chặn kiểu tấn công ngày sinh nhật. Điều này loại trừ việc dùng DES vì độ dài khoá của DES khác với độ dài bản rõ . Giả sử cho trước một xâu bit x trong đó xi e Z2 n 1 i nêu số bit trong x không phải là bội của n thì cần chèn thêm vào x theo cách nào đó. Chẳng hạn như cách làm trong nục . Để đơn giản ta sẽ bỏ qua điểm này . ý tưởng cơ bản là bắt đầu bằng một giá trị ban đầu cố định g0 IV và sau đó ta xây dựng g1 . gk theo quy tắc thiêt lập gi f xi .
