- Generator de bit aleator
- Dispozitiv sau algoritm care produce o secventa de cifre binare care sunt independente statistic si fara nici o preferinta pentru vreuna dintre cifre
- Obs
- Dispozitivele folosesc ca sursa de entropie fenomenele fizice. Generarea print-un algoritm presupune exploatarea unui proces specific platformei de calcul. Este indicata utilizarea mai multor surse naturale de etropie, esantionarea acestora, concatenarea si apoi mixarea (ex: printr-o functie dispersie)
Utilizarea in scopuri criptografice a unui generator aleator implica interzicerea accesului adversarului la generator - Teste statistice
- Este imposibil sa se demonstreze matematic ca un generator este cu adevarat aleator. Se folosesc teste statistice pentru detectarea eventualelor slabiciuni dar rezultatul trebuie privit ca o dovada probabilistica ca generatorul produce secvente cu anumite proprietati
- testul de frecventa (un bit)
- se testeaza daca aparitiile cifrelor "0" si "1" sunt aproximativ egale. Variabila aleatoare X=(n0-n1)2/n trebuie sa prezinte o distributie de probabilitate χ2 cu un grad de libertate daca n>10 (in practica n>>10000)
- testul serial (doi biti)
- se testeaza daca aparitiile secventelor "00", "01", "11" si "10" sunt aproximativ egale. Variabila aleatoare X=4/(n-1)(n002+n012+n112+n102)-2/n(n02+n12)+1 trebuie sa prezinte o distributie de probabilitate χ2 cu doua de libertate daca n>21
- testul poker (generalizare test frecventa)
- fie m∈N* ai [n/m] ≥ 5x2m. Se imparte secventa in k=[n/m] intervale disjuncte, de lungime m. Se noteaza ni numarul de aparitii ale secventei a ia, i∈[1, 2m]. Variabila aleatoare X=2m/k (∑i=12mni2) -k trebuie sa prezinte o distributie de probabilitate χ2 cu 2m-1 grade de libertate
- testul de serie
- se determina aparitiile seriilor de "0" si "1" de diverse lungimi si se compara cu, aparitiile unei secvente de lungime i pentru o secventa aleatoare de lungime n, ei=(n-i+3)/2i+2. Fie k cea mai mare valoare a lui i pentru care ei≥ 5. Zi si Ui reprezinta numerele de secvente de "0" si "1" de lungime i unde i∈[1, k]. Variabila aleatoare X = ∑i=1k((Zi-ei)2/ei) + ∑i=1k((Ui-ei)2/ei)trebuie sa prezinte o distributie de probabilitate χ2 cu 2k-2 grade de libertate
- testul de autocorelatie
- se testeaza corelatia intre secventa si versiuni alunecate ale sale. Fie d ∈[1, [n/2]]. Numarul de biti din secventa, care nu sunt egali cu biti alunecati-d este A(d) = ∑i=0n-d-1 si ⊕ si+d. Variabila aleatoare X = 2 (A(d)-(n-d)/2)/ (n-d)1/2 trebuie sa prezinte o distributie de probabilitate N(0,1) daca (n-d) ≧ 10
- testul Maurer (test universal)
# posted by Sorin Badescu @ 5:05 PM