Tính xác suất trùng nhau giữa hai hash value

Mọi người chắc quen với MD5 hash function. Vấn đề mình hỏi hôm nay cũng rất đơn giản:

Dùng MD5 hash function để tạo ra 2 hash value (32 bits), khả năng để 2 hash này giống nhau 8 bits đầu tiên là bao nhiêu?

Vì output của MD5 luôn là 32 bits, nên mình muốn lấy 8 bits đầu thôi cho nó… ngắn, nhưng không biết nếu làm vậy thì khả năng collision có tăng lên không?

1 Like

Người ta khuyên không nên chế crypto hash hay crypto nói chung :smiley:

p/s: MD5 128 bits bạn :slight_smile: nếu bạn chỉ cần hash table chứ ko cần crypto thì có nhiều hàm nhanh hơn.

Collision là khả năng trùng nhau khi 2 message khác nhau nhưng khi hash thì kết quả lại trùng nhau.
Với MD5 sử dụng hexadecimal cho mỗi kí tự tức là 1 byte = 8 bits sẽ là có 2 ký tự (1 hexadicmal = 4 bits). Thì với MD5 64 bit thì tỉ lệ collision là 2^-128 và 32 bits là 2^-64. Nhưng khi cắt 8 bits đầu tiên thì tỉ lệ sẽ thành 2^-16 tức là ~ 0.001% tỉ lệ trùng.

Và dựa theo Birthday Paradox thì tỉ lệ trùng sẽ tăng lên 1% khi bạn có ít nhất 9300 cặp messages, và sẽ là 25% nếu là 50000. LINK Birthday Paradox

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?