01/10/2018, 08:17
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?
Bài liên quan
Người ta khuyên không nên chế crypto hash hay crypto nói chung
p/s: MD5 128 bits bạn 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