Làm thế nào để vẽ các từ ngẫu nhiên từ một từ điển vật lý?

Giả sử tôi có một từ điển vật lý thực sự và tôi muốn rút các từ từ đó một cách ngẫu nhiên bằng cách sử dụng xúc xắc. Làm thế nào tôi nên làm điều đó?

Có thể làm việc với một đồng xu sẽ dễ dàng hơn vì việc chuyển đổi hệ nhị phân thành số thập phân dễ dàng hơn, nhưng dù sao đi nữa, nếu tôi sử dụng xúc xắc, thì tôi có thể tạo ra một số trong cơ số 6 bằng một số lần ném xúc xắc.

Vấn đề là từ điển không có đánh số thứ tự cho từng từ, nên tôi nghĩ việc chọn ngẫu nhiên một số trang thì một từ ngẫu nhiên trên trang đó không được phân bổ đồng đều. Nếu một số trang có nhiều từ hơn những trang khác, thì tôi đoán nó không đồng nhất.

Nhân tiện, trong một từ điển có 20.000 từ, liệu tôi có thể chỉ lấy 4 từ thực sự ngẫu nhiên để sử dụng làm cụm mật khẩu bổ sung cho hạt giống bitcoin của mình không? Tôi chỉ muốn nó thực sự khó bị bẻ khóa trong 5 năm tới trên máy AWS sao cho nó sẽ không tốn hơn 100.000 đô la cho toàn bộ cuộc tấn công.

Tôi không muốn sử dụng các từ đã chọn bip vì chúng không có trong ngôn ngữ chính của tôi

Làm thế nào để vẽ các từ ngẫu nhiên từ một từ điển vật lý, sử dụng xúc xắc?

Giả sử chúng ta biết tổng số trang $p$ trong từ điển, và có thể ước tính một số $w$ để không có trang nào có nhiều hơn $w$ từ trên đó, chúng ta có thể sử dụng lấy mẫu từ chối để phân phối chính xác:

• tìm cái nhỏ nhất $k$ với $6^k\ge p$, và lớn nhất $d\in\{1,2,3\}$ với $6^k\ge d\,p$
• tìm cái nhỏ nhất $\ell$ với $6^\ell\ge w$, và lớn nhất $e\in\{1,2,3\}$ với $6^\ell\ge e\,w$
• cho mỗi từ trong số 4 từ để chọn
  • nói lại
    • $i:=0$
    • nói lại $k$ lần
      • vẽ một giá trị xúc xắc $v$ Trong $[1,6]$
      • $i:=6i+v-1$
    • $i:=\lfloor i/d\rfloor+1$, đó là ngẫu nhiên thống nhất trong $[1,6^k/d]$
    • nếu trang $i$ tồn tại trong từ điển và chứa ít nhất một từ
      • $j:=0$
      • nói lại $\ell$ lần
        • vẽ một giá trị xúc xắc $v$ Trong $[1,6]$
        • $j:=6j+v-1$
      • $j:=\lsàn j/e\rsàn+1$, đó là ngẫu nhiên thống nhất trong $[1,6^\ell/e]$
      • nếu có ít nhất $j$ từ trên trang $i$
        • chọn $j^\text{th}$ từ của trang $i$ và thoát khỏi vòng lặp

Chúng ta có thể thoát khỏi $w$ có lẽ hơi quá nhỏ, ví dụ: $w$ ít nhất $2W/người $, ở đâu $W$ là số từ gần đúng trong từ điển, miễn là các từ trong quá khứ chỉ số $w$ trong trang của họ (không thể chọn) chỉ là một phần nhỏ của các từ.

trên một từ điển có 20.000 từ, liệu tôi có thể chỉ lấy 4 từ thực sự ngẫu nhiên để sử dụng làm cụm mật khẩu bổ sung cho hạt giống bitcoin của mình không?

điều này mang lại $4\log_2(20000)\approx57$ một chút entropy. Điều đó có đủ hay không để ngăn chặn việc tìm kiếm vũ phu, tùy thuộc vào kéo dài phím được sử dụng để thay đổi 4 từ thành một từ khóa.

Nó đã được trích dẫn BIP39, sử dụng PBKDF2 với $2^{11}$ lặp lại và HMAC-SHA-512. Chi phí tìm kiếm tất cả các khóa sẽ bị chi phối bởi $2^{57+11+1}=2^{69}$ Băm SHA-512, rất ít (tôi không muốn đi xa đến mức ước tính cách điều đó sẽ được thực hiện tốt nhất với AWS hoặc tệ hơn là ngoại suy điều đó trong 5 năm). Tôi khuyên bạn nên sử dụng Argon2 thay vì PBKDF2 HMAC-SHA-512 và giảm các tham số chi phí thành 10 giây tính toán, và như vậy là đủ an toàn.