Cum să desenezi cuvinte la întâmplare dintr-un dicționar fizic?

Să presupunem că am un dicționar fizic real și vreau să trag cuvinte din el la întâmplare, folosind zaruri. Cum ar trebui să o fac?

Poate că este mai ușor să lucrezi cu o monedă, deoarece este mai ușor să convertești binar într-o zecimală, dar orice, dacă folosesc zaruri, pot genera un număr în baza 6 cu câteva aruncări de zaruri.

Problema este că dicționarul nu are un număr de index pentru fiecare cuvânt, așa că cred că alegerea unui număr aleatoriu de pagină apoi a unui cuvânt aleatoriu pe pagina respectivă nu este distribuită uniform. Dacă o pagină are mai multe cuvinte decât celelalte, atunci cred că nu este uniformă.

Apropo, pe un dicționar cu 20.000 de cuvinte este în regulă pentru mine să obțin doar 4 cuvinte cu adevărat aleatorii pe care să le folosesc ca expresie de acces suplimentară pentru semințele mele de bitcoin? Vreau doar să fie foarte greu de spart în următorii 5 ani pe o mașină AWS, astfel încât să nu coste mai mult de 100.000 USD pentru întregul atac.

Nu vreau să folosesc cuvintele selectate bip deoarece nu sunt în limba mea principală

Cum să desenezi cuvinte aleatoriu dintr-un dicționar fizic, folosind zaruri?

Presupunând că știm numărul total de pagini $p$ în dicționar și poate estima unele $w$ astfel încât nicio pagină să nu aibă mai mult de $w$ cuvinte pe el, putem folosi eșantionarea de respingere pentru echidistribuția exactă:

• găsiți cel mai mic $k$ cu $6^k\ge p$, și cel mai mare $d\în\{1,2,3\}$ cu $6^k\ge d\,p$
• găsiți cel mai mic $\ell$ cu $6^\ell\ge w$, și cel mai mare $e\în\{1,2,3\}$ cu $6^\ell\ge e\,w$
• pentru fiecare dintre cele 4 cuvinte de ales
  • repeta
    • $i:=0$
    • repeta $k$ ori
      • trage o valoare a zarului $v$ în $[1,6]$
      • $i:=6i+v-1$
    • $i:=\lfloor i/d\rfloor+1$, care este uniform aleatoriu în [1,6^k/zi] $
    • dacă pagina $i$ există în dicționar și conține cel puțin un cuvânt
      • $j:=0$
      • repeta $\ell$ ori
        • trage o valoare a zarului $v$ în $[1,6]$
        • $j:=6j+v-1$
      • $j:=\lfloor j/e\rfloor+1$, care este uniform aleatoriu în $[1,6^\ell/e]$
      • dacă există măcar $j$ cuvinte de pe pagină $i$
        • alege $j^\text{th}$ cuvânt de pagină $i$ și ieși din bucla de repetare

Putem scăpa $w$ poate puțin prea mic, de ex. $w$ macar $2W/p$, Unde $W$ este numărul aproximativ de cuvinte din dicționar, atâta timp cât cuvintele trecute de index $w$ în pagina lor (care nu poate fi aleasă) sunt doar o mică parte din cuvinte.

pe un dicționar cu 20.000 de cuvinte este în regulă pentru mine să obțin doar 4 cuvinte cu adevărat aleatorii pe care să le folosesc ca expresie de acces suplimentară pentru semințele mele de bitcoin?

Asta da 4$\log_2(20000)\aproximativ57$ un pic de entropie. Este suficient, sau nu, pentru a descuraja căutarea cu forța brută, în funcție de întinderea cheii folosit pentru a schimba cele 4 cuvinte într-o cheie.

A fost citat BIP39, care folosește PBKDF2 cu $2^{11}$ iterații și HMAC-SHA-512. Costul căutării tuturor cheilor ar fi dominat de $2^{57+11+1}=2^{69}$ Hash-uri SHA-512, care este incomod de puține (nu vreau să merg până la a estima cum ar fi cel mai bine făcut cu AWS sau, mai rău, să extrapolez asta în 5 ani). Vă sugerez să folosiți Argon2 în loc de PBKDF2 HMAC-SHA-512 și să măriți parametrii de cost la 10 secunde de calcul, iar apoi este suficient de sigur.