Tuesday, November 15, 2005

 

Secvente aleatoare

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)

Comments: Post a Comment



<< Home

This page is powered by Blogger. Isn't yours?