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 ạ.
Về mặt lý thuyết, giá trị băm có thể bị trùng không?
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:
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2
Có 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.
3 Likes
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.
1 Like
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 
2 Likes
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 
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?