Điểm:1

Đây có phải là cả hai xác suất va chạm trong cuộc tấn công sinh nhật?

lá cờ in
Tim

Về cuộc tấn công sinh nhật, sách Kỹ thuật mật mã nói:

Nói chung, nếu một phần tử có thể nhận N giá trị khác nhau, thì bạn có thể mong đợi vụ va chạm đầu tiên sau khi chọn khoảng $\sqrt{N}$ ngẫu nhiên phần tử. Chúng tôi đang bỏ qua các chi tiết chính xác ở đây, nhưng $\sqrt{N}$ Là khá gần. Đối với nghịch lý sinh nhật, chúng ta có N = 365 và $\sqrt{N} \khoảng 19$. Số lượng người cần thiết trước khi có cơ hội sinh nhật trùng lặp vượt quá 50% trên thực tế là 23, nhưng $\sqrt{N}$ đã gần đủ cho các mục đích của chúng tôi và là phép tính gần đúng mà các nhà mật mã học thường sử dụng.

Một cách để xem xét điều này là nếu bạn chọn $k$ các phần tử, sau đó có $k(k - 1)/2$ cặp phần tử, mỗi phần tử có một $1/N$ cơ hội trở thành một cặp có giá trị bằng nhau. Vì vậy, cơ hội để tìm thấy một va chạm gần $k(k - 1)/2N$. Khi nào $k = \sqrt{N}$, cơ hội này là gần 50%.

wikipedia nói:

Ví dụ, hãy xem xét kịch bản trong đó một giáo viên có một lớp gồm 30 học sinh (n = 30) hỏi ngày sinh của mọi người (để đơn giản, bỏ qua năm nhuận) để xác định xem có hai học sinh nào có cùng ngày sinh hay không (tương ứng với xung đột băm như được mô tả thêm). Theo trực giác, cơ hội này có vẻ nhỏ. Phản trực giác, xác suất để ít nhất một học sinh có cùng ngày sinh với bất kỳ học sinh nào khác vào bất kỳ ngày nào là khoảng 70% (với n = 30), từ công thức ${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$.

mà có thể được diễn đạt lại về mặt ngôn ngữ trong Kỹ thuật mật mã:

$$1 - \frac{N!}{(N-k)! * N^k}$$

Có phải nó bằng với những điều sau đây từ Kỹ thuật mật mã:

$$ (k(k-1))/(2N) $$

Tại sao?

kelalaka avatar
lá cờ in
Đó là về xấp xỉ mà bạn không nhận thấy trên trang Wikipedia. và các trò lừa bịp có thể là [Tỷ lệ va chạm đối với hàm băm có đầu ra 256 bit là bao nhiêu?](https://crypto.stackexchange.com/q/39641/18298) và [Xác suất va chạm của cuộc tấn công sinh nhật trong Giới thiệu về hiện đại Mật mã học](https://crypto.stackexchange.com/a/72791/18298) và [Ở giới hạn dưới cho vấn đề sinh nhật](https://crypto.stackexchange.com/q/64584/18298) và [Cái gì là lỗi trong xấp xỉ xác suất va chạm này?](https://crypto.stackexchange.com/q/66328/18298) và một số lỗi khác không được liệt kê...
kelalaka avatar
lá cờ in
Trang Wiki: [Bài toán sinh nhật - Xấp xỉ](https://en.wikipedia.org/wiki/Birthday_problem#Approxximations)
Tim avatar
lá cờ in
Tim
Cảm ơn. @kelalaka. Tôi không tìm thấy (k(kâ1))/(2N) trong các liên kết. Tôi có nhớ nó không?
kelalaka avatar
lá cờ in
Xem `Điều này ổn với mức thấp` trong câu trả lời 101 liên kết đầu tiên...
Tim avatar
lá cờ in
Tim
@kelalaka Cảm ơn. Cuốn sách trong bài đăng của tôi dường như giải thích (k(kâ1))/(2N) theo một cách khác. Các cặp có hai giá trị bằng nhau có phải là các sự kiện rời nhau không?
kelalaka avatar
lá cờ in
Đầu tiên, nó chọn các giá trị $k$ ngẫu nhiên thống nhất, sau đó tạo thành cặp trong đó mỗi giá trị có $1/N$ cơ hội va chạm....
fgrieu avatar
lá cờ ng
Nguồn gốc của phép tính gần đúng nằm trong [_Bài toán sinh nhật đối với hàm băm mật mã, 101_](https://crypto.stackexchange.com/a/39644/555). Coi chừng sử dụng $(k,n)$ trong đó câu hỏi hiện tại sử dụng $(N,k)$.
Tim avatar
lá cờ in
Tim
@fgrieu Cảm ơn. Tôi vẫn có cùng một câu hỏi. Cuốn sách trong bài đăng của tôi dường như giải thích (k(kâ1))/(2N) theo một cách khác với câu trả lời của bạn. Làm thế nào tôi sẽ hiểu nó từ 1/N cho mỗi cặp? Các cặp có hai giá trị bằng nhau có phải là các sự kiện rời nhau không? Phần nào trong dẫn xuất của nó là gần đúng?
Điểm:2
lá cờ ng

Câu hỏi hỏi làm thế nào chúng ta đi từ $\displaystyle p=1 - \frac{N!}{(N-k)!\,N^k}$ cho xác suất va chạm của $k$ các giá trị ngẫu nhiên thống nhất giữa $N$, gần đúng $\displaystyle p\approx\frac{k(k-1)}{2N}$ (giả sử $k$ là nhỏ so với $\sqrt N$ ).

Đầu tiên chúng ta quay lại $\displaystyle1-p=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, đó là cách $p$ đã được xác định ở nơi đầu tiên. Sau đó, chúng tôi lấy logarit ở cả hai bên và sử dụng nó $u>0,v>0\implies\ln(u\,v)=\ln(u)+\ln(v)$ để có được $$\displaystyle\ln(1-p)=\sum_{j=0}^{k-1}{\ln\left(1-\frac j N\right)}$$

cho nhỏ $|x|$, nó giữ $\ln(1+x)\xấp xỉ x$. Áp dụng điều này cho $x=p$ ở phía bên trái và $\displaystyle x=\frac j N$ ở phía bên phải, chúng tôi nhận được $\displaystyle p\approx\sum_{j=0}^{k-1}\frac j N$. Chúng tôi viết lại điều này như $\displaystyle p\approx\frac 1 N\sum_{j=0}^{k-1}j$.

Bây giờ chúng ta sử dụng tổng các số nguyên không âm nhỏ hơn $k$$\displaystyle\frac{k\,(k-1)}2$ và nhận được mong muốn $\displaystyle p\approx\frac{k(k-1)}{2N}$.

Không có bằng chứng: xấp xỉ này của $p$ luôn luôn là dư thừa. Nó tắt ít hơn $+28\%$ khi nào $k\le\sqrt N$, ít hơn $+14\%$ khi nào $k\le\sqrt{2N}$, ít hơn $+7\%$ khi nào $k\le2\sqrt N$.


Hầu hết các lỗi là từ xấp xỉ $\ln(1-p)\approx-p$. Một xấp xỉ tốt hơn nhiều là: $$p\approx1-e^{-\frac{k(k-1)}{2N}}$$ giả sử chỉ $k\ll N$ còn hơn là $k\ll\sqrt N$. Tuy nhiên, hãy lưu ý rằng công thức thay thế này không ổn định về mặt số lượng đối với các công thức nhỏ $p$.


Trong bình luận, nó được hỏi thêm

Làm thế nào để tôi hiểu (công thức này) từ $1/N$ cho mỗi cặp? Các cặp có hai giá trị bằng nhau có phải là các sự kiện rời nhau không? Phần nào trong dẫn xuất của nó là gần đúng?

Một cách dễ dàng để lấy được xác suất $p$ rằng có một sự va chạm giữa $k$ giá trị thống nhất giữa $N$ (vì $0\le k\le N$) là phần bù của xác suất không va chạm.

Đối với một cố định $N$, định nghĩa $q_k$ như xác suất không có va chạm sau $k$ các giá trị. Chắc chắn $q_0=q_1=1$. Va cho $k\ge2$, $q_k$ là xác suất không có va chạm giữa những người đầu tiên $k-1$ các giá trị (nghĩa là $q_{k-1}$), tính xác suất không có xung đột giữa $k-1$ các giá trị trước đó và giá trị được vẽ cuối cùng, đó là $\displaystyle\frac{N-k}N$ (biện minh có một chính xác $N-k$ giá trị giữa $N$ không bị rò rỉ do va chạm đối với giá trị cuối cùng được rút ra).

Nó theo sau $\displaystyle q_k=q_{k-1}\left(1-\frac k N\right)$, do đó $\displaystyle q_k=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, do đó $$p=1-\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}=1-\frac{N!}{(N-k)!\,N ^k}$$

Điều này là chính xác. Xem hai phần đầu tiên của câu trả lời này để biết nguồn gốc của các xấp xỉ.


Một nguồn biện minh cho xấp xỉ là:

Một cách để xem xét điều này là nếu bạn chọn $k$ các phần tử, sau đó có $k(kâ1)/2$ cặp phần tử, mỗi phần tử có một $1/N$ cơ hội trở thành một cặp có giá trị bằng nhau.

Đối số vẫy tay này không mang lại một dẫn xuất chính xác về mặt toán học của $\displaystyle p=\frac{k(k-1)}{2N}$, vì các sự kiện không rời rạc. Miễn là $p$ là nhỏ, chúng ta có thể thoát khỏi nó, nhưng điều đó trở nên sai lầm nghiêm trọng khi $k>\sqrt{2N}$.

Khi nào $k = \sqrt{N}$, cơ hội này là gần 50%.

Điều đó đúng nếu 39,3% là gần 50%.

Tim avatar
lá cờ in
Tim
Cảm ơn. Nhận xét của tôi tại https://crypto.stackexchange.com/questions/99160/are-these-both-the-probability-of-collision-in-birthday-attack/99176#comment214408_99160 đã hỏi các câu hỏi khác nhau
Tim avatar
lá cờ in
Tim
Nếu bạn xem qua câu trích dẫn đầu tiên trong bài đăng của tôi, thì cuốn sách không rút ra được xác suất như cách bạn đã thêm vào câu trả lời của mình
Tim avatar
lá cờ in
Tim
"vì các sự kiện không độc lập." Tính cộng của xác suất của một số sự kiện phụ thuộc vào việc các sự kiện rời rạc không độc lập
kelalaka avatar
lá cờ in
Tỷ lệ phần trăm cần liên kết...
fgrieu avatar
lá cờ ng
@kelalaka: bằng chứng của tôi về +28% chỉ là số (do đó _không có bằng chứng_): Tôi đã lập biểu đồ $\frac{\left(1-\frac{{k^2}!}{(k^2-k)!\ ,k^{2k}}\right)\,2k^2}{k(k-1)}-1$; tương tự cho +14% +7%.
Tim avatar
lá cờ in
Tim
Cảm ơn. (1) Câu "Đầu tiên chúng ta quay lại ... lấy pâk(kâ1)/2N" mong muốn có chứng minh (k(kâ1))/(2N) là một xấp xỉ hợp lý không? (2) Liệu "Lập luận vẫy tay này không mang lại một dẫn xuất chính xác về mặt toán học của p=k(kâ1)/2N, vì các sự kiện không rời rạc. Miễn là p nhỏ, chúng ta có thể xử lý nó , nhưng điều đó cực kỳ sai khi k>sqrt(2N). Khi k=sqrt(N), cơ hội này gần bằng 50%. Điều đó đúng nếu 39,3% gần bằng 50%" nghĩa là k(kâ1) /2N là một xấp xỉ xấu? (3) nếu bạn không có ý mâu thuẫn trong (1) (2), bạn có thể giải thích, chỉnh sửa hoặc diễn giải ý của bạn thực sự không?
fgrieu avatar
lá cờ ng
(1) Chính xác hơn, nó ngụ ý $k(kâ1)/(2N)$ là một xấp xỉ hợp lệ _cho $k$ hoặc $p$ thấp hơn ngưỡng nào đó._ (2) Có nghĩa là $k(kâ 1)/(2N)$ không được chứng minh bằng lập luận đưa ra, không có tuyên bố về thời điểm áp dụng và là một phép tính gần đúng khủng khiếp đối với $k$ trên một ngưỡng nào đó. Như đã giải thích, nó đã giảm đáng kể (+24%) khi áp dụng cho $k=\sqrt N$ và $N$ lãi suất mã hóa. (3) Không có mâu thuẫn.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.