Pszeudo-véletlen sorozatok tesztelése

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. október 19-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A pszeudo-véletlen szekvenciák tesztelése egy adott pszeudo-véletlen szekvencia véletlenszerű szekvenciához való  közelségének mértékének meghatározására szolgáló módszerek összessége . Ilyen mérték általában az egyenletes eloszlás jelenléte , a nagy periódus, az azonos részstringek azonos előfordulási gyakorisága stb.

Elméleti alapok

Építési alapelvek

Az egyik leginkább szemléltető teszt az egyes karakterek előfordulási gyakoriságának egyenletes eloszlására irányuló teszt. Legyen egy n  hosszúságú és m méretű sorozat . Ekkor a ν i frekvenciáknak a szakaszhoz kell tartozniuk . A legtöbb teszt azonban más módszert használ - a sorozat véletlenszerűségi hipotézisének elfogadását vagy elutasítását statisztikai eloszlások segítségével.

Egy valóban véletlenszerű sorozat valószínűségi tulajdonságainak ismeretében ellenőrizhetjük azt a hipotézist , hogy a generált sorozat mennyire hasonlít egy véletlenszerű sorozathoz. Ehhez minden teszthez kiválasztunk egy megfelelő statisztikát, értékeit kiszámítjuk az ideális és generált sorozathoz. Ha ezen értékek közötti különbség meghalad egy előre beállított kritikus értéket, akkor a sorozat nem véletlenszerűnek minősül. "Jó" sorozatok esetén egy ilyen esemény valószínűsége rendkívül kicsi (mondjuk ~0,001 és jelöljük α-val). Lehetséges azonban, hogy egy „rossz” sorozat teljesíti a kritériumot, és következtetést vonunk le a véletlenszerűségéről (az ilyen esemény valószínűségét β-val jelöljük). A gyakorlatban az n , α és β sorozathosszak összefüggenek, α adott, és n -t úgy választjuk meg, hogy β minimális legyen.

Definiáljuk a P-értéket annak a valószínűségeként, hogy az ideális generátor a vizsgáltnál kevésbé véletlenszerű sorozatot generált. Ekkor ha a P-érték nagyobb, mint α, akkor a vizsgált sorozatot véletlenszerűnek tekintjük, és fordítva.

Röviden, a statisztikai tesztelés lépései táblázat formájában ábrázolhatók:

lépésszám Folyamat Hozzászólások
egy A hipotézis megállapítása Feltételezzük, hogy a sorozat véletlenszerű
2 A vizsgált sorozat statisztikáinak kiszámítása Bitszint tesztelés
3 P-érték számítás P érték [0; egy]
négy P-érték összehasonlítása α -val Állítsa be az α értéket [0,001; 0,01]; ha P-érték > α, akkor a teszt sikeres

Az eredmények értelmezése

Legyen adott egy s bináris sorozat . Meg kell állapítani, hogy az adott sorozat megfelel-e a statisztikai teszten vagy sem. Ehhez többféle megközelítést alkalmaznak:

Küszöb

Ez a megközelítés abból áll, hogy kiszámítjuk a c(s) bináris szekvencia valamely statisztikai értékét, és összehasonlítjuk azt valamilyen küszöbértékkel. Ha a kapott c(s) érték kisebb, mint a küszöbérték, akkor az s sorozat nem felel meg a teszten.

Rögzített értéktartomány

A megközelítés a c(s) bináris sorozat valamely statisztikai értékének kiszámításából is áll, mint az első esetben. Most azonban azt mondjuk, hogy ha c(s) kívül esik valamilyen értéktartományon, akkor az s sorozat nem teljesíti ezt a tesztet.

Valószínűségi érték

Egy harmadik megközelítés annak meghatározására, hogy egy s bináris szekvencia átmegy-e egy statisztikai teszten, nem csak a c statisztikát, hanem a megfelelő p valószínűségi értéket is megszámolja . Általában egy adott statisztikát úgy számítanak ki, hogy annak nagy értékei az s sorozat nem véletlenszerű jellegére utalnak . Ekkor p annak a valószínűsége, hogy c(s) nagyobb vagy egyenlő lesz, mint c(s') egy valóban véletlenszerű s' sorozatra számítva . Ezért a p valószínűség kis értékei (általában p < 0,05 vagy p < 0,01) értelmezhetők annak bizonyítékaként, hogy s nem véletlen. Így, ha valamilyen a rögzített értékre a valószínűségi érték p < a , akkor az s bináris sorozat nem teljesíti ezt a tesztet. Általában a [ 0,001; 0,01] intervallumból veszi az értékeket.

Grafikai tesztek

Ez a kategória olyan teszteket tartalmaz, amelyek eredményeit grafikonok formájában jelenítjük meg, amelyek jellemzik a vizsgált sorozat tulajdonságait. Közöttük:

  • a szekvenciaelemek eloszlásának hisztogramja; lehetővé teszi a karakterek sorozatbeli eloszlásának egységességének értékelését és az egyes karakterek ismétlődési gyakoriságának meghatározását;
  • elosztás a repülőgépen; a sorozat elemei közötti kapcsolat meghatározására tervezték;
  • sorozatellenőrzés; lehetővé teszi az egyes karakterek egységességének meghatározását a sorozatban, valamint a k bites sorozatok eloszlásának egységességét;
  • ellenőrizze a monotonitást; az egységesség meghatározását szolgálja a nem növekvő és nem csökkenő részsorozatok elemzése alapján;
  • autokorrelációs függvény ; úgy tervezték, hogy értékelje a szekvenciák eltolt másolatai és az egyes részsorozatok közötti összefüggést ;
  • lineáris komplexitási profil; a teszt értékeli a sorozat lineáris összetettségének a hosszától való függését;
  • grafikus spektrális teszt; lehetővé teszi a sorozat bitjei eloszlásának egységességének értékelését a Fourier-transzformációs kiugró értékek magasságának elemzése alapján .

A grafikus tesztek eredményeit ember értelmezi, így az ezek alapján levonható következtetések félreérthetőek lehetnek.

Statisztikai tesztek

A grafikus tesztektől eltérően a statisztikai tesztek a sorozat numerikus jellemzőjét adják meg, és lehetővé teszik, hogy egyértelműen megállapítható legyen, hogy sikeres volt-e a teszt. A statisztikai tesztek alábbi szoftvercsomagjai a legismertebbek:

Nem. Név Szerző Szervezet
egy NIST tesztek [1] Andrew Rukhin, et. al. NIST ITL
2 TESZT-U01 [2] P. L'Ecuyer és mások. Universit'e de Montr'eal
3 CRYPT-X [3] Helen Gustafson et al. Queenslandi Műszaki Egyetem
négy A pLab projekt [4] Hellekalek Péter Salzburgi Egyetem
5 DIEHARD [5] George Marsaglia Floridai Állami Egyetem
6 Dieharder [6] Robert G Brown Duke Egyetem
7 ENT [7] John Walker Autodesk , Inc.
nyolc A Számítógép-programozás Művészete Vol. 2 félnumerikus algoritmus [8] Donald Knuth Stanford Egyetem
9 Az alkalmazott kriptográfia kézikönyve [9] Alfred Menezes és mások. C.R.C. Press, Inc.

DIEHARD tesztek

A DIEHARD teszteket George Marsaglia dolgozta ki több éven keresztül, és először véletlenszerű számoknak szentelt CD-ROM-on tették közzé. Az egyik legszigorúbb ismert tesztcsomagnak tartják őket.

D. Knuth tesztjei

Knuth tesztjei statisztikai teszten alapulnak . A statisztikai adatok számított értékét összehasonlítják a táblázatos eredményekkel, és az ilyen statisztikák előfordulási valószínűségétől függően következtetést vonnak le a minőségére vonatkozóan. Ezeknek a teszteknek az előnyei közé tartozik a kis számuk és a gyors végrehajtási algoritmusok megléte. Hátránya az eredmények értelmezésének bizonytalansága. Íme ezeknek a teszteknek az összefoglalása:

  • Nem kapcsolt sorozatok keresése . A sorozatot m nem átfedő sorozatra osztjuk, és az egyes lehetséges sorozatok előfordulási gyakoriságára egy eloszlást készítünk.
  • Ellenőrizze az időközöket . Ez a teszt a karakterek eloszlásának egységességét a vizsgált sorozatban ellenőrzi olyan részsorozatok hosszának elemzésével, amelyeknek minden eleme egy bizonyos numerikus intervallumhoz tartozik.
  • A kombinációk ellenőrzése . A sorozatot meghatározott hosszúságú részsorozatokra bontják, és különféle számkombinációkból álló sorozatokat vizsgálnak.
  • Kupongyűjtő teszt . Legyen egy n  hosszúságú és m méretű sorozat . Az egyes m - jegyű számokat tartalmazó meghatározott hosszúságú sorozatokat vizsgáljuk.
  • Permutációk ellenőrzése . Ez a teszt a karakterek eloszlásának egységességét ellenőrzi a vizsgált sorozatban a számok részsorozatokban való kölcsönös elrendezésének elemzésével.
  • Ellenőrizze a monotonitást . Az egységesség meghatározására szolgál a nem növekvő és nem csökkenő részsorozatok elemzése alapján.
  • Korreláció ellenőrzése . Ez a teszt egy sorozat elemeinek kölcsönös függetlenségét ellenőrzi.

NIST tesztek

A különbség ezek és a többi modern teszt között az algoritmusok nyitottsága. Az előnyök közé tartozik a teszteredmények egyértelmű értelmezése is. Általános jellemzők táblázata:

Nem. Teszt neve Meghatározott hiba
egy frekvencia teszt Túl sok nulla vagy egyes
2 Az összesített összegek ellenőrzése Túl sok nulla vagy egyes a sorozat elején
3 A "lyukak" ellenőrzése a részsorozatokban Eltérés az egységek sorozatainak eloszlásában
négy A "lyukak" ellenőrzése A nullák és egyesek nagy számú (kis) részsorozata azt jelzi, hogy a bitfolyam ingadozása túl gyors (lassú)
5 A mátrixok rangsorainak ellenőrzése A mátrixok rangsorai eloszlásának eltérése a megfelelő eloszlástól egy valóban véletlenszerű sorozat esetén, a sorozatok periodicitásával társulva
6 Spektrális teszt Egy sorozat periodikus tulajdonságai
7 Nem átfedő minták ellenőrzése A nem periodikus minták túl gyakoriak
nyolc Metsző minták ellenőrzése Az egyesek túl gyakori m bites sorozatai
9 Maurer egyetemes statisztikai tesztje Egy sorozat összenyomhatósága (szabályossága).
tíz Véletlen eltérések ellenőrzése Eltérés egy bizonyos típusú részsorozatok előfordulásai számának eloszlásától
tizenegy A véletlen eltérések ellenőrzésének egy változata Eltérés egy bizonyos típusú részsorozatok előfordulásai számának eloszlásától
12 A közelítő entrópia ellenőrzése Az m bites szavak egyenetlen eloszlása . A kis értékek nagy ismételhetőséget jelentenek
13 Sorozat ellenőrzés Szabálytalanság az m bites szavak eloszlásában
tizennégy Tömörítés Lempel-Ziv algoritmussal Nagyobb tömöríthetőség, mint egy valódi véletlenszerű sorozat
tizenöt Lineáris komplexitás Eltérés a lineáris komplexitási eloszlástól véges részstring hosszúság esetén

Gyakorlati alkalmazások

A véletlen- és pszeudo-véletlenszám-generátorok jelentik az információbiztonság láncszemét . Bizonyos értelemben ezek a kriptográfiai algoritmusok és protokollok létfontosságú építőkövei. Mivel az ilyen generátorokat számos kriptográfiai problémában használják, például véletlenszerű paraméterek és titkosítási rendszerek kulcsainak kialakításában, a követelmények meglehetősen magasak. A generátor kimenetén kapott abszolút tetszőleges bináris sorozat egyik kritériuma különösen az, hogy lehetetlen előre jelezni a generátor bemenetére szolgáltatott adatokra vonatkozó információ hiányában. Ezért a gyakorlatban statisztikai teszteket végeznek egy véletlen- vagy pszeudo-véletlenszám-generátor által generált bináris sorozat véletlenszerű jellegének ellenőrzésére. Ez pedig lehetővé teszi, hogy előre azonosítsa azokat a generátorokat, amelyek megfelelnek egy adott kriptográfiai probléma követelményeinek.

AES verseny

Az új Advanced Encryption Standard jóváhagyása érdekében a Nemzeti Szabványügyi és Technológiai Intézet az Egyesült Államok kormányának támogatásával versenyt rendezett, amelynek során 15 pályázó algoritmust teszteltek. Az algoritmusok értékelésének egyik kritériuma az volt, hogy alkalmasak véletlenszám-generátorra. Az ilyen generátorok tesztelését jó statisztikai tulajdonságokkal rendelkező véletlenszerű bináris szekvenciák létrehozására a NIST statisztikai tesztkészlettel végeztük .

Az AES első köre során a tesztelést 128 bites kulcsokkal végezték. A 15 algoritmusból mindössze 9 algoritmus tudott átmenni a statisztikai teszteken [10] .

Az első kör eredményei alapján 5 titkosítási algoritmust választottak ki az AES döntőjének: MARS , RC6 , Rijndael , Serpent és Twofish . Az AES verseny második fordulójában ennek az 5 algoritmusnak a véletlenszám-generátorként való alkalmasságát értékelték 192 bites és 256 bites kulcsok alapján. A NIST statisztikai tesztek időtartama több hónapig tartott, számos Sun Ultra munkaállomáson végeztek számításokat . Minden adatot online generáltak és dolgoztak fel. A második kör eredményeként kiderült, hogy mind az öt döntős egy véletlenszerű bináris sorozatot generál, jó statisztikai tulajdonságokkal, ezért álvéletlen számgenerátorként használható, és lehetséges a következő méretű kulcsok használata: 128 , 192 és 256 bites [11] .

Lásd még

Jegyzetek

  1. ↑ NIST Cryptographic Toolkit . Letöltve: 2010. május 8. Az eredetiből archiválva : 2011. augusztus 17..
  2. ↑ TesztU01 . Hozzáférés dátuma: 2010. május 8. Az eredetiből archiválva : 2010. július 23.
  3. ↑ Crypt-X archiválva : 2008. szeptember 22. a Wayback Machine -nél . Az Információbiztonsági Kutatóközpont.
  4. ↑ A pLab Project (lefelé irányuló kapcsolat) . Letöltve: 2009. november 21. Az eredetiből archiválva : 2009. november 14.. 
  5. ↑ A DIEHARD tesztcsomag archiválva : 2016. január 25.
  6. ↑ Dieharder: A Random Number Test Suite . Letöltve: 2010. május 8. Az eredetiből archiválva : 2010. június 10.
  7. ↑ ENT . Letöltve: 2010. május 8. Archiválva az eredetiből: 2010. május 15.
  8. ↑ Donald E. Knuth. The Art of Computer Programming, Vol.2: Semi-Numerical Algorithms Archivált : 2008. szeptember 4., a Wayback Machine / 3. kiadás. Addison-Wesley, 1998
  9. ↑ Alfred Menezes et al. , Handbook of Applied Cryptography Archiválva : 2005. március 7. a Wayback Machine -nél
  10. ↑ A fejlett titkosítási szabvány jelölt algoritmusainak NIST IR 6390 véletlenszerűségi tesztelése archiválva 2010. november 6. a Wayback Machine -nél 
  11. ↑ NIST IR 6483 véletlenszerűségi teszt a fejlett titkosítási szabvány döntős jelöltjeiről archiválva 2010. május 27. a Wayback Machine -nél 

Irodalom

  • Donald E. Knuth . 3. fejezet Véletlen számok // A számítógépes programozás művészete. - 3. kiadás - M .: Williams , 2000. - V. 2. Megszerzett algoritmusok. — 832 p. — ISBN 5-8459-0081-6 .
  • M. A. Ivanov, I. V. Chugunkov. 4. fejezet A PSS generátorok minőségértékelésének módszertana // Pszeudo-véletlen sorozatok generátorainak minőségének elmélete, alkalmazása és értékelése. - M. : KUDITS-OBRAZ, 2003. - 240 p. — ISBN 5-93378-056-1 .

Linkek