Nghịch lý sinh nhật và toán học đằng sau các vụ va chạm Hash

Bạn có bao giờ tự hỏi xác suất để hai người trong cùng một phòng có cùng ngày sinh là bao nhiêu không? Nếu bạn đang ở một mình, xác suất đó chắc chắn bằng không. Và càng có nhiều người, khả năng trùng lặp càng cao. Nhưng bạn có tin rằng trong một phòng chỉ có 23 người, đã có tới 50% khả năng để hai người trong đó cùng sinh nhật vào một ngày?

Đây là một ví dụ kinh điển về "Nghịch lý sinh nhật", một khái niệm toán học thú vị không chỉ dừng lại ở các trò chơi xác suất mà còn đóng vai trò cốt lõi trong lĩnh vực an ninh mạng và cấu trúc dữ liệu, cụ thể là trong các vấn đề liên quan đến va chạm Hash (hash collisions).

Toán học cơ bản của sự trùng lặp

Để tính xác suất để ít nhất hai người có cùng ngày sinh, chúng ta thường tính theo hướng ngược lại: xác suất để không ai có cùng ngày sinh.

Nếu có 365 ngày trong một năm (bỏ qua năm nhuận), người đầu tiên có thể sinh vào bất kỳ ngày nào. Người thứ hai phải sinh vào một ngày khác người đầu tiên, nên chỉ còn 364 lựa chọn. Người thứ ba còn 363 lựa chọn, và cứ thế.

Công thức xác suất để không có sự trùng lặp trong một nhóm n người là:

[P(\text{không trùng}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \dots \frac{365-n+1}{365}]

Khi áp dụng cho n = 23, kết quả P(không trùng) xấp xỉ 0,4927. Điều này có nghĩa là xác suất để có ít nhất một cặp trùng lặp là (1 - 0,4927 = 0,5073), hay hơn 50%.

Vượt ra ngoài các cặp đôi: Góc nhìn của Richard von Mises

Các công thức trên thường chỉ dùng để tìm một cặp trùng lặp. Nhưng nếu chúng ta muốn biết xác suất để 3 người trong nhóm 60 người có cùng ngày sinh thì sao?

Vào những năm 1930, các nhân viên của một văn phòng toán học tại một công ty bảo hiểm đã cố gắng tính toán điều này khi họ phát hiện ra 3 đồng nghiệp sinh cùng ngày. Phương pháp tính ban đầu của họ cho ra kết quả cực kỳ thấp, chỉ khoảng 0,0006 (xảy ra khoảng một lần trong 1500-2000 nhóm). Tuy nhiên, kết quả này về mặt kỹ thuật là đúng nhưng lại sai về mặt ngữ cảnh.

Năm 1939, nhà toán học người Áo Richard von Mises đã chỉ ra sai lầm trong tư duy của họ. Các nhân viên đó đang cố tính xác suất của một sự kiện cụ thể: 3 người sinh vào một ngày đã chọn trước đó. Nhưng câu hỏi đúng đắn cần đặt ra là: "Tần suất chúng ta mong đợi loại sự kiện này xảy ra nói chung là bao nhiêu?"

Von Mises đã thay đổi góc nhìn từ "sự kiện cụ thể" sang "xác suất chiếm chỗ" (occupancy probability). Thay vì chọn một cái hộp cụ thể để xem có 3 quả bóng rơi vào đó không, ông quan sát tất cả 365 cái hộp để xem có bao nhiêu cái hộp chứa 3 quả bóng.

Công thức kỳ vọng mới cho thấy, với nhóm 60 người, giá trị kỳ vọng để có một bộ ba trùng ngày sinh là khoảng 0,22. Nghĩa là trung bình cứ mỗi 4-5 nhóm 60 người thì sẽ có một nhóm có hiện tượng này. Rất khác biệt so với con số "vài phần nghìn" ban đầu!

Áp dụng vào Công nghệ: Va chạm Hash và Bảng băm

Tại sao vấn đề sinh nhật này lại quan trọng với các lập trình viên và kỹ sư bảo mật? Bởi vì toán học đằng sau nghịch lý sinh nhật chính là toán học đằng sau các va chạm trong bảng băm (hash table).

Hãy tưởng tượng:

• 365 ngày trong năm tương ứng với số lượng ô nhớ (buckets) trong bảng băm.
• Người trong phòng tương ứng với các khóa (keys) hoặc dữ liệu cần lưu trữ.
• Ngày sinh tương ứng với giá trị băm (hash value).

Khi chúng ta chèn dữ liệu vào bảng băm, chúng ta "ném" các quả bóng (dữ liệu) vào các hộp (ô nhớ). Va chạm xảy ra khi hai quả bóng rơi vào cùng một hộp. Hiểu được xác suất này giúp các kỹ sư tối ưu hóa kích thước của bảng băm để giảm thiểu va chạm, từ đó tăng tốc độ truy xuất dữ liệu.

Birthday Attack: Mối đe dọa trong An ninh mạng

Trong lĩnh vực an ninh mạng, nguyên lý này được sử dụng trong một loại tấn công đặc biệt gọi là Birthday Attack (Tấn công sinh nhật). Đây là một dạng tấn công vét cạn (brute-force) nhằm tạo ra va chạm trong các hàm băm mật mã.

Kẻ tấn công không cần tìm một đầu vào cụ thể để khớp với một giá trị băm đã có sẵn (việc này cực kỳ khó). Thay vào đó, chúng chỉ cần tạo ra hai đầu vào ngẫu nhiên bất kỳ sao cho chúng có cùng giá trị băm.

Nhờ vào nghịch lý sinh nhật, kẻ tấn công không cần cố gắng (2^{256}) lần để phá vỡ SHA-256. Thay vào đó, chúng chỉ cần khoảng (\sqrt{2^{256}} = 2^{128}) lần thử. Mặc dù (2^{128}) vẫn là một con số khổng lồ, nhưng nó nhỏ hơn rất nhiều so với không gian tìm kiếm ban đầu, khiến cho việc tấn công trở nên khả thi hơn về mặt lý thuyết nếu thuật toán băm không đủ mạnh.

Kết luận

Nghịch lý sinh nhật không chỉ là một câu đố vui vẻ trong các lớp toán học. Nó là một minh chứng đẹp đẽ cho việc cách chúng ta định nghĩa vấn đề có thể thay đổi hoàn toàn kết quả. Trong thế giới kỹ thuật số, sự hiểu biết về xác suất chiếm chỗ và va chạm là nền tảng thiết yếu để thiết kế ra các hệ thống phần mềm an toàn, hiệu quả và có khả năng chống chịu trước các cuộc tấn công mạng.

Tiếp theo khi bạn thiết kế một bảng băm hoặc chọn một thuật toán băm cho hệ thống của mình, hãy nhớ rằng: những va chạm đó không phải là ngẫu nhiên hoàn toàn, mà là những quy luật toán học tất yếu mà chúng ta phải tính toán kỹ lưỡng.