จะวาดคำแบบสุ่มจากพจนานุกรมจริงได้อย่างไร?

สมมติว่าฉันมีพจนานุกรมจริงๆ เล่มหนึ่ง และฉันต้องการสุ่มคำจากพจนานุกรมโดยใช้ลูกเต๋า ฉันควรทำอย่างไร?

บางทีมันอาจจะง่ายกว่าที่จะทำงานกับเหรียญเพราะมันง่ายกว่าที่จะแปลงเลขฐานสองเป็นทศนิยม แต่ไม่ว่าอย่างไรก็ตาม ถ้าฉันใช้ลูกเต๋า ฉันสามารถสร้างตัวเลขในฐาน 6 ด้วยการโยนลูกเต๋า

ปัญหาคือพจนานุกรมไม่มีหมายเลขดัชนีสำหรับแต่ละคำ ดังนั้นฉันคิดว่าการเลือกหมายเลขหน้าแบบสุ่มแล้วคำที่สุ่มในหน้านั้นจะไม่กระจายอย่างสม่ำเสมอ ถ้าบางหน้ามีคำมากกว่าหน้าอื่น ฉันเดาว่ามันไม่เหมือนกัน

อย่างไรก็ตาม ในพจนานุกรมที่มี 20,000 คำ เป็นไปได้ไหมที่ฉันจะได้รับคำแบบสุ่มอย่างแท้จริงเพียง 4 คำเพื่อใช้เป็นข้อความรหัสผ่านเพิ่มเติมสำหรับเมล็ด bitcoin ของฉัน ฉันแค่ต้องการให้การแคร็กเครื่อง AWS เป็นเรื่องยากมากในอีก 5 ปีข้างหน้า โดยที่จะไม่เสียค่าใช้จ่ายมากกว่า 100,000 ดอลลาร์สหรัฐฯ สำหรับการโจมตีทั้งหมด

ฉันไม่ต้องการใช้คำที่เลือกเพราะไม่ได้อยู่ในภาษาหลักของฉัน

วิธีการวาดคำแบบสุ่มจากพจนานุกรมจริงโดยใช้ลูกเต๋า?

สมมติว่าเราทราบจำนวนหน้าทั้งหมด $p$ ในพจนานุกรมและประมาณการได้บ้าง $w$ เพื่อให้ไม่มีหน้าใดเกิน $w$ จากคำพูดนี้ เราสามารถใช้การสุ่มตัวอย่างการปฏิเสธเพื่อการกระจายที่แน่นอน:

• หาที่เล็กที่สุด $k$ กับ $6^k\ge พี$และใหญ่ที่สุด $d\in\{1,2,3\}$ กับ $6^k\ge d\,p$
• หาที่เล็กที่สุด $\ell$ กับ $6^\ell\ge w$และใหญ่ที่สุด $e\in\{1,2,3\}$ กับ $6^\ell\ge อี\,w$
• สำหรับแต่ละ 4 คำที่จะเลือก
  • ทำซ้ำ
    • $i:=0$
    • ทำซ้ำ $k$ ครั้ง
      • วาดลูกเต๋ามูลค่า $v$ ใน $[1,6]$
      • $i:=6i+v-1$
    • $i:=\lชั้น i/d\rชั้น+1$ซึ่งเป็นการสุ่มแบบสม่ำเสมอ $[1,6^k/d]$
    • ถ้าหน้า $i$ มีอยู่ในพจนานุกรมและมีคำอย่างน้อยหนึ่งคำ
      • $j:=0$
      • ทำซ้ำ $\ell$ ครั้ง
        • วาดลูกเต๋ามูลค่า $v$ ใน $[1,6]$
        • $j:=6j+v-1$
      • $j:=\ชั้น j/e\rชั้น +1$ซึ่งเป็นการสุ่มแบบสม่ำเสมอ $[1,6^\ell/e]$
      • ถ้ามีอย่างน้อย $เจ$ คำบนหน้า $i$
        • เลือก $j^\text{th}$ คำของหน้า $i$ และออกจากการวนซ้ำ

เราสามารถหนีไปกับ $w$ อาจเล็กเกินไปเล็กน้อยเช่น $w$ อย่างน้อย $2W/p$, ที่ไหน $W$ คือจำนวนคำโดยประมาณในพจนานุกรม ตราบใดที่คำผ่านดัชนี $w$ ในหน้า (ที่เลือกไม่ได้) เป็นเพียงส่วนน้อยของคำ

ในพจนานุกรมที่มี 20,000 คำ เป็นไปได้ไหมที่ฉันจะได้รับคำสุ่มจริงๆ เพียง 4 คำเพื่อใช้เป็นข้อความรหัสผ่านเพิ่มเติมสำหรับเมล็ด bitcoin ของฉัน

สิ่งนี้ให้ $4\log_2(20000)\ประมาณ57$ เอนโทรปีเล็กน้อย เพียงพอหรือไม่ที่จะยับยั้งการค้นหากำลังดุร้าย ทั้งนี้ขึ้นอยู่กับ การยืดที่สำคัญ ใช้เปลี่ยน 4 คำเป็นคีย์

มีการอ้างถึง BIP39 ซึ่งใช้ PBKDF2 กับ $2^{11}$ การทำซ้ำและ HMAC-SHA-512 ค่าใช้จ่ายในการค้นหาคีย์ทั้งหมดจะถูกควบคุมโดย $2^{57+11+1}=2^{69}$ แฮช SHA-512 ซึ่งมีน้อยอย่างน่าอึดอัด (ฉันไม่ต้องการไปไกลถึงการประเมินว่าจะทำได้ดีเพียงใดกับ AWS หรือแย่กว่านั้นคือคาดการณ์ใน 5 ปี) ฉันแนะนำให้ใช้ Argon2 แทน PBKDF2 HMAC-SHA-512 และเพิ่มพารามิเตอร์ต้นทุนเป็น 10 วินาทีในการคำนวณ เท่านี้ก็ปลอดภัยมากพอแล้ว