Score:1

ทั้งสองอย่างนี้น่าจะเป็นการปะทะกันในการโจมตีวันเกิดหรือไม่?

ธง in
Tim

เกี่ยวกับการโจมตีวันเกิด หนังสือ วิศวกรรมการเข้ารหัส พูดว่า:

โดยทั่วไป หากองค์ประกอบสามารถรับค่าที่แตกต่างกันได้ N ค่า คุณก็สามารถทำได้ คาดว่าจะเกิดการชนกันครั้งแรกหลังจากเลือกประมาณ $\sqrt{N}$ สุ่ม องค์ประกอบ เรากำลังทิ้งรายละเอียดที่แน่นอนไว้ที่นี่ แต่ $\sqrt{N}$ เป็น ค่อนข้างใกล้ชิด สำหรับความขัดแย้งวันเกิด เรามี N = 365 และ $\sqrt{N} \ประมาณ 19$. จำนวนคนที่ต้องการก่อนมีโอกาส วันเกิดซ้ำเกิน 50% คือ 23 จริง แต่ $\sqrt{N}$ ใกล้เข้ามาแล้ว เพียงพอสำหรับจุดประสงค์ของเราและเป็นค่าประมาณที่นักเข้ารหัส มักจะใช้

วิธีหนึ่งในการมองสิ่งนี้คือถ้าคุณเลือก $k$ องค์ประกอบแล้ว มี $k(k - 1)/2$ องค์ประกอบที่เป็นคู่ซึ่งแต่ละองค์ประกอบมี $1/N$ โอกาสที่จะเป็นคู่ที่มีค่าเท่ากัน ดังนั้นโอกาสที่จะพบ ใกล้จะชนกันแล้ว $k(k - 1)/2N$. เมื่อไร $k = \sqrt{N}$โอกาสนี้ อยู่ใกล้ถึง 50 % .

และ วิกิพีเดีย พูดว่า:

ตัวอย่างเช่น พิจารณาสถานการณ์ที่ครูที่มีนักเรียน 30 คนในชั้นเรียน (n = 30 คน) ถามวันเกิดของทุกคน (เพื่อความง่าย ไม่ต้องสนใจปีอธิกสุรทิน) เพื่อระบุว่านักเรียนสองคนมีวันเกิดเดียวกันหรือไม่ (ซึ่งสอดคล้องกับการชนกันของแฮช ดังจะอธิบายต่อไป) โอกาสนี้อาจดูน้อยนิด ตอบโต้โดยสัญชาตญาณ ความน่าจะเป็นที่นักเรียนอย่างน้อยหนึ่งคนจะมีวันเกิดเดียวกันกับนักเรียนคนอื่นๆ ในแต่ละวันคือประมาณ 70% (สำหรับ n = 30) จากสูตร ${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$.

ซึ่งสามารถใช้ถ้อยคำใหม่ในแง่ของภาษาใน วิศวกรรมการเข้ารหัส:

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

มันควรจะเท่ากับต่อไปนี้จาก วิศวกรรมการเข้ารหัส:

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

ทำไม

kelalaka avatar
in flag
นั่นคือการประมาณที่คุณไม่ได้สังเกตบนหน้าวิกิพีเดีย และการซ้ำที่เป็นไปได้คือ [โอกาสของการชนกันของฟังก์ชันแฮชที่มีเอาต์พุต 256 บิตคือเท่าใด](https://crypto.stackexchange.com/q/39641/18298) และ [ความน่าจะเป็นในการโจมตีวันเกิดของการชนกันในบทนำสู่สมัยใหม่ การเข้ารหัส](https://crypto.stackexchange.com/a/72791/18298) และ [ในขอบเขตล่างสำหรับปัญหาวันเกิด](https://crypto.stackexchange.com/q/64584/18298) และ [อะไร เป็นข้อผิดพลาดในการประมาณความน่าจะเป็นของการชนกันนี้หรือไม่](https://crypto.stackexchange.com/q/66328/18298) และอื่นๆ ที่ไม่ได้อยู่ในรายการ...
kelalaka avatar
in flag
หน้า Wiki: [ปัญหาวันเกิด - การประมาณ](https://en.wikipedia.org/wiki/Birthday_problem#การประมาณ)
Tim avatar
in flag
Tim
ขอบคุณ. @เคลาลากะ. ฉันไม่พบ (k(kâ1))/(2N) ในลิงก์ ฉันคิดถึงมันไหม
kelalaka avatar
in flag
ดู `นี่ใช้ได้สำหรับต่ำ ` ในลิงค์แรก 101 คำตอบ...
Tim avatar
in flag
Tim
@kelalaka ขอบคุณค่ะ หนังสือในโพสต์ของฉันดูเหมือนจะอธิบาย (k(kâ1))/(2N) ในวิธีที่ต่างออกไป แต่ละคู่มีค่าเท่ากันสองเหตุการณ์ที่ไม่ปะติดปะต่อหรือไม่
kelalaka avatar
in flag
อันดับแรกจะเลือกค่า $k$ แบบสุ่มแบบเดียวกัน จากนั้นสร้างคู่โดยที่แต่ละค่ามีโอกาส $1/N$ ของการชนกัน....
fgrieu avatar
ng flag
ที่มาของการประมาณอยู่ใน [_Birthday problem for cryptographic hashing, 101_](https://crypto.stackexchange.com/a/39644/555) ระวังการใช้ $(k,n)$ โดยที่คำถามปัจจุบันใช้ $(N,k)$
Tim avatar
in flag
Tim
@fgrieu ขอบคุณ ฉันยังคงมีคำถามเดิม หนังสือในโพสต์ของฉันดูเหมือนจะอธิบาย (k(kâ1))/(2N) แตกต่างจากคำตอบของคุณ ฉันจะเข้าใจได้อย่างไรจาก 1/N สำหรับแต่ละคู่? แต่ละคู่มีค่าเท่ากันสองเหตุการณ์ที่ไม่ปะติดปะต่อหรือไม่ ส่วนใดของการได้มาคือการประมาณ?
Score:2
ธง ng

คำถามถามว่าเราจะจากไปอย่างไร $\displaystyle p=1 - \frac{N!}{(N-k)!\,N^k}$ สำหรับความน่าจะเป็นของการชนกันของ $k$ ค่าสุ่มที่สม่ำเสมอระหว่าง $N$เพื่อการประมาณ $\displaystyle p\ประมาณ\frac{k(k-1)}{2N}$ (ซึ่งถือว่า $k$ มีขนาดเล็กเมื่อเทียบกับ $\sqrt N$ ).

ก่อนอื่นเราจะกลับไปที่ $\displaystyle1-p=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$ซึ่งเป็นวิธีการ $p$ ถูกกำหนดมาแต่แรกแล้ว จากนั้นเราก็หาลอการิทึมทั้งสองข้างแล้วใช้มัน $u>0,v>0\implies\ln(u\,v)=\ln(u)+\ln(v)$ ที่จะได้รับ $$\displaystyle\ln(1-p)=\sum_{j=0}^{k-1}{\ln\left(1-\frac j N\right)}$$

สำหรับขนาดเล็ก $|x|$มันถือ $\ln(1+x)\ประมาณ x$. ใช้สิ่งนี้กับ $x=p$ ทางด้านซ้ายและ $\displaystyle x=\frac j N$ ทางด้านขวาเราได้รับ $\displaystyle p\ประมาณ\sum_{j=0}^{k-1}\frac j N$. เราเขียนสิ่งนี้ใหม่เป็น $\displaystyle p\ประมาณ\frac 1 N\sum_{j=0}^{k-1}j$.

ตอนนี้เราใช้ผลรวมของจำนวนเต็มที่ไม่เป็นลบน้อยกว่า $k$ เป็น $\displaystyle\frac{k\,(k-1)}2$ และได้รับสิ่งที่ต้องการ $\displaystyle p\ประมาณ\frac{k(k-1)}{2N}$.

โดยไม่ต้องพิสูจน์: การประมาณนี้ของ $p$ เป็นส่วนเกินเสมอ มันปิดน้อยกว่า $+28\%$ เมื่อไร $k\le\sqrt N$, น้อยกว่า $+14\%$ เมื่อไร $k\le\sqrt{2N}$, น้อยกว่า $+7\%$ เมื่อไร $k\le2\sqrt N$.


ข้อผิดพลาดส่วนใหญ่มาจากการประมาณค่า $\ln(1-p)\ประมาณ-p$. การประมาณที่ดีกว่ามากคือ: $$p\ประมาณ1-e^{-\frac{k(k-1)}{2N}}$$ ซึ่งสมมติขึ้นเท่านั้น $k\ll N$ ค่อนข้างมากกว่า $k\ll\sqrt N$. อย่างไรก็ตาม ระวังว่าสูตรทางเลือกนี้มีความไม่แน่นอนทางตัวเลขสำหรับรายย่อย $p$.


ในความคิดเห็นจะมีการถามเพิ่มเติม

จะเข้าใจได้อย่างไร (สูตรนี้) จาก $1/N$ อย่างละคู่? แต่ละคู่มีค่าเท่ากันสองเหตุการณ์ที่ไม่ปะติดปะต่อหรือไม่ ส่วนใดของการได้มาคือการประมาณ?

วิธีง่าย ๆ ในการหาค่าความน่าจะเป็น $p$ ว่ามีการปะทะกัน $k$ ค่าสม่ำเสมอระหว่าง $N$ (สำหรับ $0\le k\le N$) เป็นส่วนเติมเต็มของความน่าจะเป็นที่จะไม่มีการชนกัน

สำหรับการแก้ไข $N$, กำหนด $q_k$ ตามความน่าจะเป็นที่จะไม่มีการชนกันภายหลัง $k$ ค่า อย่างชัดเจน $q_0=q_1=1$. และสำหรับ $k\ge2$, $q_k$ คือความน่าจะเป็นที่จะไม่มีการชนกันระหว่างอันแรก $k-1$ ค่า (นั่นคือ $q_{k-1}$) เวลาความน่าจะเป็นที่จะไม่มีการชนกันระหว่าง $k-1$ ค่าก่อนหน้าและค่าสุดท้ายที่จับมา ซึ่งก็คือ $\displaystyle\frac{N-k}N$ (เหตุผลมีว่า $N-k$ ค่าระหว่าง $N$ ที่ไม่รั่วไหลไปชนกับค่าสุดท้ายที่ดึงมา)

มันเป็นไปตาม $\displaystyle q_k=q_{k-1}\left(1-\frac k N\right)$, ดังนั้น $\displaystyle q_k=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, ดังนั้น $$p=1-\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}=1-\frac{N!}{(N-k)!\,N ^k}$$

นี้แน่นอน ดูสองส่วนแรกของคำตอบนี้เพื่อหาค่าประมาณ


แหล่งหนึ่งให้เหตุผลประมาณว่า:

วิธีหนึ่งในการมองสิ่งนี้คือถ้าคุณเลือก $k$ องค์ประกอบแล้วมี $k(kâ1)/2$ องค์ประกอบที่เป็นคู่ซึ่งแต่ละองค์ประกอบมี $1/N$ โอกาสที่จะเป็นคู่ที่มีค่าเท่ากัน

อาร์กิวเมนต์แบบโบกมือนี้ไม่ได้ให้ผลลัพธ์ที่แน่นอนทางคณิตศาสตร์ของ $\displaystyle p=\frac{k(k-1)}{2N}$เนื่องจากเหตุการณ์ไม่ปะติดปะต่อ ตราบเท่าที $p$ มีขนาดเล็ก เราสามารถหลีกเลี่ยงได้ แต่นั่นจะผิดพลาดอย่างร้ายแรงเมื่อ $k>\sqrt{2N}$.

เมื่อไร $k = \sqrt{N}$โอกาสนี้ใกล้ถึง 50% แล้ว

เป็นจริงถ้า 39.3% ใกล้เคียงกับ 50%

Tim avatar
in flag
Tim
ขอบคุณ. ความคิดเห็นของฉันที่ https://crypto.stackexchange.com/questions/99160/are-these-both-the-probability-of-collision-in-birthday-attack/99176#comment214408_99160 ถามคำถามที่แตกต่างกัน
Tim avatar
in flag
Tim
หากคุณดูที่คำพูดแรกในโพสต์ของฉัน หนังสือเล่มนี้ไม่ได้มาจากความน่าจะเป็นตามที่คุณเพิ่มลงในคำตอบของคุณ
Tim avatar
in flag
Tim
"เนื่องจากเหตุการณ์ไม่เป็นอิสระ" การบวกความน่าจะเป็นของหลายเหตุการณ์ขึ้นอยู่กับเหตุการณ์ที่แยกจากกันไม่เป็นอิสระต่อกัน
kelalaka avatar
in flag
เปอร์เซ็นต์ที่ต้องการลิงก์...
fgrieu avatar
ng flag
@kelalaka: หลักฐานของฉันสำหรับ +28% เป็นเพียงตัวเลขเท่านั้น (ดังนั้น _โดยไม่ต้องพิสูจน์_): ฉันพล็อต $\frac{\left(1-\frac{{k^2}!}{(k^2-k)!\ ,k^{2k}}\right)\,2k^2}{k(k-1)}-1$; เท่ากับ +14% +7%
Tim avatar
in flag
Tim
ขอบคุณ. (1) ของคุณ "ก่อนอื่นเรากลับไปที่ ... รับ pâk(kâ1)/2N" ที่ต้องการ (k(kâ1))/(2N) เป็นการประมาณที่สมเหตุสมผลหรือไม่ (2) ไม่ "การโต้เถียงแบบโบกมือนี้ไม่ได้ให้ผลลัพธ์ที่แน่นอนทางคณิตศาสตร์ของ p=k(kâ1)/2N เนื่องจากเหตุการณ์ไม่ปะติดปะต่อ ตราบใดที่ p มีขนาดเล็ก เราก็สามารถหลีกเลี่ยงได้ แต่นั่นจะผิดอย่างมหันต์เมื่อ k>sqrt(2N) เมื่อ k=sqrt(N) โอกาสนี้จะใกล้เคียงกับ 50% นั่นเป็นความจริงหาก 39.3% ใกล้เคียงกับ 50%" หมายความว่า k(kâ1) /2N เป็นการประมาณที่ไม่ดี? (3) ถ้าคุณไม่ได้หมายถึงความขัดแย้งใน (1) (2) คุณช่วยอธิบาย แก้ไข หรือถอดความความหมายที่แท้จริงได้ไหม
fgrieu avatar
ng flag
(1) ให้แม่นยำยิ่งขึ้น มันหมายความว่า $k(kâ1)/(2N)$ เป็นการประมาณที่ถูกต้อง _สำหรับ $k$ หรือ $p$ ต่ำกว่าเกณฑ์บางส่วน_ (2) หมายความว่า $k(kâ 1)/(2N)$ ไม่ถูกต้องตามข้อโต้แย้งที่ให้ไว้ โดยไม่ได้ระบุว่าจะใช้เมื่อใด และเป็นค่าประมาณที่แย่มากสำหรับ $k$ ที่สูงกว่าค่าเกณฑ์บางตัว ตามที่อธิบายไว้ มันถูกปิดไปแล้วอย่างมาก (โดย +24%) เมื่อนำไปใช้กับ $k=\sqrt N$ และ $N$ ของความสนใจด้านการเข้ารหัส (3) ไม่มีความขัดแย้ง

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา