01/10/2018, 09:51
Về mặt lý thuyết, giá trị băm có thể bị trùng không?
Chào mọi người, mình đang tìm hiểu về hàm băm, và thắc mắc một điều là về mặt lý thuyết các giá trị băm có thể bị trùng không ạ. Mình đã hỏi các bạn mình, ai cũng đinh ninh là không ạ. Nhưng mình nghĩ là có vì mình có đọc một tài liệu, một số có nói về hiện tượng xung đột (collision). Nhờ mọi người giúp mình phân biệt với ạ.
Bài liên quan
thì đúng, collision chính là nhiều bản gốc khác nhau cùng cho ra một bản băm.
Ví dụ mình vừa tìm được trên crypto.stackexchange.com:
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa20
0a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea24dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa20
2a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2Có chung bản hash MD5: 008ee33a9d58b51cfeb425b0959121c9
Collision là tất yếu, vì nếu collision không tồn tại, hàm băm sẽ là đơn ánh. Và về lý thuyết, đơn ánh nào cũng có thể suy ngược lại được, đơn giản hay phức tạp.
MDx hay SHA1 là 2 thuật toán đã xuất hiện sự trùng lặp và trong bảo mật người ta đã khuyên loại bỏ k dùng 2 thuật toán ấy nữa.
Về mặt lí thuyết thì vẫn có đụng (do số khả năng của input nhiều hơn số khả năng output), vấn đề trong crypto là có dễ tìm ra hay không, nếu dễ hơn tỉ lệ lí thuyết quá nhiều thì dùng cái khác vậy
Hoàn toàn có thể trùng, MD5 có độ dài 128 bit tức là có 2^128 trường hợp của giá trị băm. Đầu vào là tập hợp giá trị tùy ý không có giới hạn số lượng mà đầu ra lại bị giới hạn thì dĩ nhiên nó sẽ trùng