Xác suất va chạm băm python

Chúng ta sẽ xem xét cách sử dụng Nghịch lý sinh nhật khi ước tính khả năng chống va chạm của hàm băm. Hướng dẫn này sẽ chỉ ra rằng một ước tính tốt là một hàm băm n-bit sẽ ngẫu nhiên va chạm với các giá trị băm ngẫu nhiên n/2-bit

Bước 1. Hiểu một hàm băm

Hàm băm là hàm một chiều với kích thước đầu ra cố định. Nghĩa là, đầu ra có cùng kích thước và rất khó tìm được hai mâm cặp đầu vào riêng biệt cho cùng một đầu ra

Hàm băm là bất kỳ hàm nào có thể được sử dụng để ánh xạ dữ liệu có kích thước tùy ý thành các giá trị có kích thước cố định.  

https. // vi. wikipedia. org/wiki/Hash_function

Có lẽ ví dụ nổi tiếng nhất về hàm băm là MD5. Nó được thiết kế để sử dụng như một hàm băm mật mã, nhưng đã được phát hiện là có nhiều lỗ hổng

Điều này có nghĩa là bạn không nên sử dụng hàm băm MD5?

mà phụ thuộc. Nếu bạn sử dụng nó trong thiết lập mật mã, câu trả lời là Không sử dụng

Mặt khác, hàm băm thường được sử dụng để tính toán các định danh. Với mục đích đó, nó cũng phụ thuộc vào việc bạn có nên sử dụng nó hay không

Đây là nơi Nghịch lý Sinh nhật xuất hiện

Bước 2. Các hàm băm và Nghịch lý sinh nhật có liên quan như thế nào?

Câu hỏi hay. Đầu tiên hãy nhớ lại những gì Nghịch lý Sinh nhật nói

…trong một nhóm ngẫu nhiên gồm 23 người, có khoảng 50% khả năng hai người có cùng ngày sinh

http. //www. learnpythonwithrune. org/sinh nhật-nghịch lý-bởi-ví dụ-nó-không-là-nghịch lý/

Làm thế nào điều đó có thể liên quan đến hàm băm?

Với 23 người, chúng tôi có 50% khả năng va chạm [hai người có cùng ngày sinh]

Do đó, nếu chúng ta có thì các hàm băm của chúng ta sẽ ánh xạ dữ liệu tới một ngày trong năm dương lịch. Tức là, nó ánh xạ hàm băm [dữ liệu] -> [0, 364], sau đó đưa ra 23 giá trị hàm băm, chúng ta có 50% cơ hội xảy ra xung đột

Nhưng bạn cũng biết rằng hàm băm của chúng tôi ánh xạ tới hơn 365 giá trị riêng biệt. Trên thực tế, MD5 ánh xạ tới 2^128 giá trị riêng biệt

Một ví dụ sẽ được đánh giá cao bây giờ. Chúng ta hãy tạo một hàm băm đơn giản hóa, gọi nó là MD5′ [md5-prime], ánh xạ giống như MD5, nhưng chỉ sử dụng byte đầu tiên của kết quả

Nghĩa là, chúng ta có MD5′[data] -> [0, 255]

Chắc chắn, theo nguyên tắc chuồng bồ câu, chúng ta sẽ hết các giá trị có thể có sau 256 lần nhập dữ liệu riêng biệt vào MD5′ và xảy ra xung đột

import hashlib
import os

lookup_table = {}
collision_count = 0
for _ in range[256]:
    random_binary = os.urandom[16]
    result = hashlib.md5[random_binary].digest[]
    result = result[:1]
    if result in lookup_table:
        print["Collision"]
        print[random_binary, result]
        print[lookup_table[result], result]
        collision_count += 1
    else:
        lookup_table[result] = random_binary
print["Number of collisions:", collision_count]

lookup_table được sử dụng để lưu trữ các giá trị băm đã thấy. Chúng tôi sẽ lặp lại trên 256 [ít hơn một giá trị có thể có của hàm băm MD5′ của chúng tôi]. Lấy một số dữ liệu ngẫu nhiên và băm nó bằng md5 và chỉ sử dụng byte đầu tiên [8 bit]. Nếu kết quả đã tồn tại trong lookup_table thì chúng ta có xung đột, nếu không thì hãy thêm nó vào lookup_table của chúng ta

Đối với một lần chạy ngẫu nhiên này, tôi đã nhận được 87 va chạm. Kỳ vọng?

Chúng ta hãy thử sử dụng Nghịch lý sinh nhật để ước tính có bao nhiêu giá trị băm mà chúng ta cần để có xung đột hàm băm MD5′ của chúng ta

Một ước tính sơ bộ được sử dụng rộng rãi là căn bậc hai của số kết quả có thể xảy ra sẽ cho 50% khả năng va chạm [xem]

Nghĩa là, đối với MD5′[data] -> [0, 255], sqrt[256] = 16. Hãy thử điều đó

import hashlib
import os

collision = 0
for _ in range[1000]:
    lookup_table = {}
    for _ in range[16]:
        random_binary = os.urandom[16]
        result = hashlib.md5[random_binary].digest[]
        result = result[:1]
        if result not in lookup_table:
            lookup_table[result] = random_binary
        else:
            collision += 1
            break
print["Number of collisions:", collision, "out of", 1000]

Cung cấp cho một số như thế này

Number of collisions: 391 out of 1000

Đó là ở cấp thấp hơn, nhưng vẫn là một xấp xỉ hợp lý

Bước 3. Sử dụng cấu trúc dữ liệu chính xác để tra cứu trong

Chỉ cần làm rõ. Chúng tôi sẽ không tìm thấy va chạm trên hàm băm MD5 đầy đủ, nhưng chúng tôi sẽ thử xem ước tính va chạm có hợp lý không

Điều này đòi hỏi phải thực hiện nhiều tính toán và chúng tôi muốn đảm bảo rằng chúng tôi không gặp phải nút thắt cổ chai khi sử dụng cấu trúc dữ liệu sai

Python dict phải là một bảng băm với phép chèn và tra cứu dự kiến ​​O[1]. Tuy nhiên, trường hợp xấu nhất là O[n] đối với các hoạt động này, đây sẽ là một chi phí lớn để thực hiện trên đường đi. Do đó, trước tiên chúng tôi sẽ kiểm tra xem từ điển có thời gian chèn và tra cứu O[1] cho các trường hợp sử dụng mà chúng tôi có ở đây không