Gần đây, season 3 của Alice in Borderland đã được ra mắt trên Netflix. Trong muôn vàn content về bộ phim ở trên mạng, tôi vô tình bắt gặp hình ảnh này. Nó khiến tôi nhớ lại tháng ngày học môn An toàn thông tin ở Đại học, với những Bloom Filter hay Birthday Paradox.

Bạn có tin không? Chỉ cần 23 người trong một phòng, xác suất để ít nhất hai người có cùng ngày sinh đã vượt quá 50%. Và với 78 người, con số này lên tới 99.9%! Đây không phải là phép thuật, mà là một định luật toán học nổi tiếng có tên Nghịch Lý Sinh Nhật (Birthday Paradox).

Trước hết, ta cần hiểu lý do tại sao nó lại được gọi là một nghịch lý: Với 365 ngày trong năm, bản năng mách bảo chúng ta rằng phải cần khoảng 182 người (một nửa của 365) để xác suất đạt 50%. Nhưng thực tế, con số đó chỉ là 23 – một con số thực sự rất nhỏ so với 182. Sự chênh lệch khổng lồ giữa trực giác và toán học này khiến nó trở nên “nghịch lý”.

Lời giải

Chìa khóa để giải quyết nghịch lý này là tính xác suất phần bù – tức là tính xác suất không có ai trùng ngày sinh, sau đó lấy 1 trừ đi.

• Bước 1: Giả định đơn giản hóa
  Giả sử một năm có 365 ngày và xác suất sinh nhật của mỗi người là đồng đều (bỏ qua ngày nhuận, mùa sinh,…).
• Bước 2: Tính xác suất KHÔNG có ai trùng sinh nhật
  • Người thứ nhất: có thể chọn bất kỳ ngày nào trong 365 ngày. Xác suất không trùng: 365/365.
  • Người thứ hai: phải chọn một ngày khác người thứ nhất. Còn 364 lựa chọn. Xác suất: 364/365.
  • Người thứ ba: phải khác hai người đầu. Còn 363 lựa chọn. Xác suất: 363/365.
  • …
  • Người thứ n: còn (365 - (n - 1))/365 lựa chọn.
    Vậy, xác suất để tất cả n người đều có sinh nhật khác nhau là:
    P(\text{không trùng})=\frac{365}{365}\times \frac{364}{365}\times \frac{363}{365}\times…\times\frac{(365 - (n - 1))}{365}
• Bước 3: Tính xác suất CÓ ÍT NHẤT một cặp trùng nhau
  Đơn giản là lấy 1 trừ đi xác suất không trùng:

P(\text{ít nhất một cặp trùng}) = 1-P(\text{không trùng})

Hay:

P(n) = 1-\frac{365!}{(365-n)! \times 365^{n}}

“Bóc tách” con số với bảng tính mẫu

Hãy cùng áp dụng công thức cho các con số trong bức ảnh:

• Với n = 23 người:
  P(23)=1-\frac{365}{365}\times \frac{364}{365}\times \frac{363}{365}\times…\times\frac{343}{365}\approx 0.5073 hay 50.73%
• Với n = 78 người:
  P(78) = 1 - 0.00074 \approx 0.99926 hay 99.93%
• Với n = 183 người:
  P(183) = 1 - 0.00074 \approx 0.9999999999(gần như chắc chắn 100%)
• Với n = 365 người (Định luật Dirictlet):
  Với 365 người, không thể đảm bảo 100% có trùng (về lý thuyết, họ vẫn có thể sinh vào các ngày khác nhau nếu may mắn), nhưng xác suất trùng lặp là cực kỳ cao. Chỉ khi có 366 người (nhiều hơn số ngày trong năm), theo Nguyên lý Dirichlet, chắc chắn có ít nhất một cặp trùng sinh nhật.

Đi tìm công thức tổng quát

Gọi:

• N: số khả năng (ví dụ: 365 ngày).
• k: số đối tượng (số người).

Trong thực tế, ta rất khó có thể tính trực tiếp phép giai thừa được. Cho nên, thông thường ta sẽ sử dụng công thức xấp xỉ như sau:

P(collision)\approx1-e^{-\frac{k^{2}}{2N}}

Ai không quan tâm lắm tới toán học thì có thể next qua mục này, còn ai mà tò mò giống mình thì hẵng đọc. Cũng dễ hiểu thôi, không khó quá như mình tưởng.

Quay trở lại từ công thức của phần trước, ta có:

P(\text{không trùng})=\frac{N}{N}\times \frac{N-1}{N}\times \frac{N-2}{N}\times…\times\frac{(N- (k - 1))}{N}
= \prod_{i=0}^{k-1}(1-\frac{i}{N})

Lấy logarit:

\ln P(\text{không trùng})
= \sum_{i=0}^{k-1}\ln(1-\frac{i}{N})

Biết rằng, k << N cho nên \frac{i}{N}\approx0. Sử dụng công thức khai triển Taylor với x\approx0 ta có:

\ln (1-x) \approx -x

Dẫn tới:

\ln P(\text{không trùng})\approx \sum_{i=0}^{k-1}(-\frac{i}{N})
=-\frac{1}{N}\sum_{i=0}^{k-1}i = -\frac{1}{N}\cdot \frac{k(k-1)}{2}

Kết quả

P(\text{không trùng})\approx e^{-\frac{k(k-1)}{2N}}\approx e^{-\frac{k^{2}}{2N}}

Và do đó:

P(\text{ít nhất một cặp trùng})\approx 1-e^{-\frac{k^{2}}{2N}}

Ứng dụng thực tế

Birthday Paradox không chỉ dừng lại ở những bữa tiệc sinh nhật. Nó là nền tảng cho nhiều vấn đề quan trọng trong lĩnh vực an ninh mạng.

Mình không định “múa rìu qua mắt thợ” trước các chuyên gia bảo mật đâu, nên sẽ lấy ví dụ gần gũi nhất — thứ mà ai đọc đến đây chắc chắn đều từng trải qua: đăng nhập tài khoản.

Thông thường, hệ thống không bao giờ lưu mật khẩu gốc trong cơ sở dữ liệu. Thay vào đó, nó lưu phiên bản đã mã hóa (hash). Lý do đơn giản: nếu ai đó (dù là dev hay hacker) lỡ tay hay cố tình xem dữ liệu trong database, họ cũng không thể đọc được mật khẩu thật.

Nhưng chuyện không dừng ở đó. Chỉ hash mật khẩu thôi là chưa đủ an toàn.
Giả sử một hacker biết được mật khẩu của một user — ví dụ “123456”. Hắn có thể truy vấn để tìm ra tất cả tài khoản khác dùng cùng mật khẩu này. Chưa kể, nếu hắn có sẵn một bảng băm (rainbow table), hắn chỉ cần so khớp là ra hàng loạt mật khẩu trong nháy mắt.

Đó là lý do vì sao chúng ta thêm “muối” (salt) vào mỗi mật khẩu trước khi mã hóa. Mỗi user sẽ có một salt riêng biệt, khiến cho ngay cả khi hai người dùng cùng mật khẩu, kết quả hash của họ vẫn hoàn toàn khác nhau. Nói cách khác, salt chính là thứ khiến hacker không thể dùng “một công thức chung cho tất cả” được nữa.

hashed_password= hash(salt + plain_password)

Vậy salt cần có kích thước là bao nhiêu để xác suất 2 salt trùng nhau gần như bằng 0.

Giờ thì quay lại với Birthday Paradox — “nhân vật chính” của bài này. Giả sử hệ thống của bạn có 1 tỷ user => Tương ứng k=10^{9}.

P(\text{collision})\approx 1-e^{-\frac{k^{2}}{2N}}

Như ta đã thấy, với salt ≥ 12 bytes: xác suất va chạm cực kỳ nhỏ (10⁻¹² trở xuống), về thực tế là không thể xảy ra. Tuy nhiên trong nghiên cứu và triển khai an ninh, ta vẫn phải xét song song các yếu tố thực thi và các cách tấn công khác để đánh giá độ an toàn tổng thể – việc này nằm ngoài phạm vi của bài viết.

Lời kết

Birthday Paradox là một minh chứng hoàn hảo cho thấy trực giác của con người có thể dễ dàng bị đánh lừa bởi những con số. Nó dạy cho chúng ta một bài học quan trọng: trong một thế giới phức tạp và kết nối, những điều tưởng chừng rất hiếm gặp thực chất lại có xác suất xảy ra cao một cách đáng kinh ngạc.

Lần tới, khi tham dự một sự kiện có hơn 23 người, bạn hãy thử thách bản thân tìm một người có cùng ngày sinh. Rất có thể, bạn sẽ không chỉ ngạc nhiên vì kết quả, mà còn có một câu chuyện thú vị về toán học để chia sẻ với mọi người.