Pseudosatunnaisten sekvenssien testaus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. lokakuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Pseudosatunnaisten sekvenssien testaus  on joukko menetelmiä tietyn näennäissatunnaisen sekvenssin ja satunnaisen sekvenssin läheisyyden mittaamiseksi . Tällainen mitta on yleensä tasaisen jakauman läsnäolo , suuri jakso, identtisten osamerkkijonojen yhtä suuri esiintymistiheys jne.

Teoreettinen perusta

Rakentamisen periaatteet

Yksi havainnollistavimmista testeistä on testi kunkin merkin esiintymistiheyden tasaiselle jakautumiselle. Olkoon  sarja, jonka pituus on n ja mitta m . Tällöin taajuuksien ν i tulee kuulua väliin . Useimmissa testeissä käytetään kuitenkin eri menetelmää - hyväksytään tai hylätään sekvenssin satunnaisuushypoteesi käyttämällä tilastollisia jakaumia.

Tietäen todella satunnaisen sekvenssin todennäköisyysominaisuudet, voidaan niiden avulla testata hypoteesia siitä, kuinka samanlainen luotu sekvenssi on satunnaisen sekvenssin kanssa. Tätä varten jokaiselle testille valitaan sopiva tilasto, jonka arvot lasketaan ihanteelliselle ja generoidulle sekvenssille. Jos näiden arvojen välinen ero ylittää jonkin etukäteen asetetun kriittisen arvon, sekvenssiä pidetään ei-satunnaisena. "Hyvällä" sekvenssillä tällaisen tapahtuman todennäköisyys on erittäin pieni (oletetaan ~0,001 ja merkitään se α:lla). On kuitenkin mahdollista, että "huono" sekvenssi täyttää kriteerin ja sen satunnaisuudesta tehdään johtopäätös (merkitään tällaisen tapahtuman todennäköisyyttä β:lla). Käytännössä sekvenssin pituudet n , α ja β liittyvät toisiinsa, α on annettu ja n valitaan β:n minimoimiseksi.

Määritellään P-arvo todennäköisyydeksi, että ihanteellinen generaattori generoi vähemmän satunnaisen sekvenssin kuin tutkittava. Sitten jos P-arvo on suurempi kuin α, niin tutkittua sekvenssiä pidetään satunnaisena ja päinvastoin.

Lyhyesti, tilastollisen testauksen vaiheet voidaan kuvata taulukon muodossa:

vaiheen numero Prosessi Kommentit
yksi Hypoteesin lausunto Oletetaan, että sarja on satunnainen
2 Tutkitun sekvenssin tilastojen laskenta Bittitason testaus
3 P-arvon laskeminen P-arvo [0; yksi]
neljä P-arvon vertaaminen α:han Aseta α [0,001; 0,01]; jos P-arvo > α, testi on hyväksytty

Tulosten tulkinta

Olkoon binäärisekvenssi s annettu . On selvitettävä, läpäiseekö annettu sekvenssi tilastollisen testin vai ei. Tätä varten käytetään useita erilaisia ​​lähestymistapoja:

Kynnys

Tämä lähestymistapa koostuu binäärisekvenssin c(s) tilastollisen arvon laskemisesta ja sen vertaamisesta johonkin kynnysarvoon. Jos tuloksena saatu arvo c(s) on pienempi kuin kynnysarvo, sekvenssi s läpäisee tämän testin.

Kiinteä arvoalue

Lähestymistapa koostuu myös binäärisekvenssin c(s) tilastollisen arvon laskemisesta, kuten ensimmäisessä tapauksessa. Nyt sanomme kuitenkin, että jos c(s) on jonkin arvoalueen ulkopuolella, sekvenssi s epäonnistuu tässä testissä.

Todennäköisyysarvo

Kolmas lähestymistapa sen määrittämiseksi, läpäiseekö binäärisekvenssi s tilastollisen testin, ei lasketa vain tilastollista c: tä vaan myös sitä vastaavaa todennäköisyysarvoa p . Yleensä tietty tilasto lasketaan siten, että sen suuret arvot viittaavat sekvenssin s ei-satunnaiseen luonteeseen . Silloin p on todennäköisyys, että c(s) on suurempi tai yhtä suuri kuin c(s') laskettuna todella satunnaiselle sekvenssille s' . Siksi pienet todennäköisyyden p arvot (yleensä p < 0,05 tai p < 0,01) voidaan tulkita todisteeksi siitä, että s ei ole satunnainen. Siten, jos jollekin kiinteälle arvolle a todennäköisyysarvo p < a , niin binäärisekvenssi s läpäisee tämän testin. Yleensä a ottaa arvot väliltä [0,001; 0,01].

Grafiikkatestit

Tähän kategoriaan kuuluvat testit, joiden tulokset näytetään kaavioina, jotka kuvaavat tutkitun sekvenssin ominaisuuksia. Heidän keskuudessaan:

  • sekvenssielementtien jakauman histogrammi; voit arvioida merkkien jakautumisen yhtenäisyyttä sarjassa ja määrittää kunkin merkin toistotiheyden;
  • jakelu koneessa; suunniteltu määrittämään sekvenssin elementtien välinen suhde;
  • sarja tarkistaa; voit määrittää sekvenssin yksittäisten merkkien tasaisuuden sekä k bitin sarjan jakautumisen tasaisuuden;
  • tarkista monotonisuus; toimii yhdenmukaisuuden määrittämisessä ei-nousevien ja ei-laskevien osasekvenssien analyysin perusteella;
  • autokorrelaatiofunktio ; suunniteltu arvioimaan sekvenssien siirrettyjen kopioiden ja yksittäisten osasekvenssien välistä korrelaatiota ;
  • lineaarinen monimutkaisuusprofiili; testi arvioi sekvenssin lineaarisen kompleksisuuden riippuvuuden sen pituudesta;
  • graafinen spektritesti; antaa sinun arvioida sekvenssin bittien jakautumisen tasaisuutta Fourier-muunnospoikkeamien korkeuden analyysin perusteella .

Graafisten testien tulokset ovat ihmisen tulkimia, joten niihin perustuvat johtopäätökset voivat olla epäselviä.

Tilastolliset testit

Toisin kuin graafiset testit, tilastolliset testit antavat sekvenssin numeerisen ominaisuuden ja mahdollistavat yksiselitteisen selvityksen, onko testi läpäissyt. Seuraavat tilastotestien ohjelmistopaketit tunnetaan parhaiten:

Ei. Nimi Tekijä Organisaatio
yksi NIST-testit [1] Andrew Rukhin, et. al. NIST ITL
2 TEST-U01 [2] P. L'Ecuyer ja muut. Montr'ealin yliopisto
3 CRYPT-X [3] Helen Gustafson et ai. Queenslandin teknillinen yliopisto
neljä pLab-projekti [4] Peter Hellekalek Salzburgin yliopisto
5 DIEHARD [5] George Marsaglia Floridan osavaltion yliopisto
6 Dieharder [6] Robert G Brown Duken yliopisto
7 ENT [7] John Walker Autodesk , Inc.
kahdeksan The Art Of Computer Programming Voi. 2 puolinumeerista algoritmia [8] Donald Knuth Stanfordin yliopisto
9 Sovellettavan kryptografian käsikirja [9] Alfred Menezes ja muut. C.R.C. Press, Inc.

DIEHARD-testit

DIEHARD-testit kehitti George Marsaglia useiden vuosien aikana, ja ne julkaistiin ensimmäisen kerran satunnaisluvuille omistetulla CD-ROM-levyllä. Niitä pidetään yhtenä tiukimmista tunnetuista testisarjoista.

D. Knuthin testit

Knuthin testit perustuvat tilastolliseen testiin . Tilastojen laskettua arvoa verrataan taulukkotuloksiin ja tällaisten tilastojen esiintymistodennäköisyydestä riippuen tehdään johtopäätös sen laadusta. Näiden testien etuja ovat niiden pieni määrä ja nopeiden suoritusalgoritmien olemassaolo. Haittapuolena on tulosten tulkinnan epävarmuus. Tässä on yhteenveto näistä testeistä:

  • Etsitään linkittämättömiä sarjoja . Sekvenssi jaetaan m ei-päällekkäiseen sarjaan ja kunkin mahdollisen sarjan esiintymistiheydille muodostetaan jakauma .
  • Tarkista välit . Tämä testi tarkistaa tutkitun sekvenssin merkkijakauman tasaisuuden analysoimalla osasekvenssien pituuksia, joiden kaikki elementit kuuluvat tiettyyn numeeriseen väliin.
  • Yhdistelmien tarkistus . Sekvenssi jaetaan tietynpituisiin osasarjoihin ja tarkastellaan eri numeroyhdistelmistä koostuvia sarjoja.
  • Kupongin kerääjätesti . Olkoon  sarja, jonka pituus on n ja mitta m . Tutkitaan tietynpituisia sekvenssejä , jotka sisältävät jokaisen m -numeroisen luvun.
  • Tarkistetaan permutaatioita . Tämä testi tarkistaa tutkitun sekvenssin merkkijakauman tasaisuuden analysoimalla lukujen keskinäistä järjestystä osajonoissa.
  • Tarkista monotonisuus . Käytetään tasaisuuden määrittämiseen ei-nousevien ja ei-laskevien osasekvenssien analyysin perusteella.
  • Korrelaation tarkistus . Tämä testi tarkistaa sekvenssin elementtien keskinäisen riippumattomuuden.

NIST-testit

Ero näiden testien ja muiden nykyaikaisten testien välillä on algoritmien avoimuus. Etujen joukossa on myös testitulosten yksiselitteinen tulkinta. Taulukko yleisistä ominaisuuksista:

Ei. Testin nimi Määritelty vika
yksi taajuustesti Liikaa nollia tai ykkösiä
2 Tarkistetaan kumulatiivisia määriä Liikaa nollia tai ykkösiä sarjan alussa
3 Tarkistetaan "reiät" osajaksoissa Poikkeama yksiköiden sekvenssien jakautumisessa
neljä "reikien" tarkistaminen Suuri (pieni) määrä nollien ja ykkösten osasarjoja osoittaa, että bittivirran vaihtelu on liian nopea (hidas)
5 Matriisien rivien tarkistaminen Matriisien rivien jakauman poikkeama vastaavasta jakaumasta todella satunnaiselle sekvenssille, joka liittyy sekvenssien jaksoisuuteen
6 Spektritesti Jakson jaksolliset ominaisuudet
7 Ei-päällekkäisten kuvioiden tarkistaminen Ei-jaksolliset kuviot ovat liian yleisiä
kahdeksan Etsitään risteäviä kuvioita Liian yleisiä ykkösten m -bittisiä sekvenssejä
9 Maurerin yleinen tilastollinen testi Jakson puristuvuus (säännöllisyys).
kymmenen Satunnaisten poikkeamien tarkistus Poikkeama tietyntyyppisten osasekvenssien esiintymisten lukumäärän jakaumasta
yksitoista Muunnelma satunnaisten poikkeamien tarkistamisesta Poikkeama tietyntyyppisten osasekvenssien esiintymisten lukumäärän jakaumasta
12 Likimääräisen entropian tarkistaminen M - bittisten sanojen epätasainen jakautuminen . Pienet arvot tarkoittavat suurta toistettavuutta
13 Sarjan tarkistus Epäsäännöllisyys m - bittisten sanojen jakautumisessa
neljätoista Pakkaus käyttämällä Lempel-Ziv-algoritmia Parempi pakatettavuus kuin todellinen satunnainen sarja
viisitoista Lineaarinen monimutkaisuus Poikkeama äärellisen alijonon pituuden lineaarisesta kompleksisuusjakaumasta

Käytännön sovellukset

Satunnais- ja pseudosatunnaislukugeneraattorit ovat linkki tietoturvassa . Tietyssä mielessä nämä ovat tärkeitä salausalgoritmien ja protokollien rakennuspalikoita. Koska tällaisia ​​generaattoreita käytetään monissa salausongelmissa, esimerkiksi salausjärjestelmien satunnaisten parametrien ja avaimien muodostamisessa, niille asetetut vaatimukset ovat melko korkeat. Erityisesti yksi kriteereistä täysin mielivaltaiselle binäärisekvenssille, joka saadaan generaattorin lähdöstä, on mahdottomuus ennustaa sitä, jos generaattorin sisäänmenoon syötetystä tiedosta ei ole tietoa. Tästä syystä käytännössä tehdään tilastollisia testejä satunnais- tai näennäissatunnaislukugeneraattorin generoiman binäärisekvenssin satunnaisuuden tarkistamiseksi. Tämä puolestaan ​​antaa sinun tunnistaa etukäteen tietyn salausongelman vaatimukset täyttävät generaattorit.

AES-kilpailu

Uuden Advanced Encryption Standardin hyväksymiseksi National Institute of Standards and Technology järjesti Yhdysvaltain hallituksen tuella kilpailun, jonka aikana testattiin 15 hakijan algoritmia. Eräs algoritmien arvioinnissa käytetty kriteeri oli niiden soveltuvuus satunnaislukugeneraattoreihin. Tällaisten generaattoreiden testaus satunnaisten binäärisekvenssien muodostamiseksi, joilla on hyvät tilastolliset ominaisuudet, suoritettiin käyttämällä NIST-tilastotestisarjaa .

Ensimmäisen AES-kierroksen aikana testattiin 128-bittisiä avaimia. Vain 9 algoritmia 15 algoritmista läpäisi tilastolliset testit [10] .

Ensimmäisen kierroksen tulosten perusteella AES-finalisteiksi valittiin 5 salausalgoritmia: MARS , RC6 , Rijndael , Serpent ja Twofish . AES-kilpailun toisella kierroksella arvioitiin näiden viiden algoritmin soveltuvuutta satunnaislukugeneraattoreiksi 192- ja 256-bittisten avainten perusteella. NIST-tilastotestien kesto oli useita kuukausia, ja laskelmia tehtiin useilla Sun Ultra -työasemilla . Kaikki tiedot luotiin ja käsiteltiin verkossa. Toisen kierroksen tuloksena kävi ilmi, että jokainen viidestä finalistista generoi satunnaisen binäärisekvenssin, jolla on hyvät tilastolliset ominaisuudet, ja siksi sitä voidaan käyttää näennäissatunnaislukugeneraattorina, ja on mahdollista käyttää avaimia, joiden koko on: 128 , 192 ja 256 bittiä [11] .

Katso myös

Muistiinpanot

  1. ↑ NIST Cryptographic Toolkit . Haettu 8. toukokuuta 2010. Arkistoitu alkuperäisestä 17. elokuuta 2011.
  2. ↑ TestU01 . Käyttöpäivä: 8. toukokuuta 2010. Arkistoitu alkuperäisestä 23. heinäkuuta 2010.
  3. ↑ Crypt-X arkistoitu 22. syyskuuta 2008 Wayback Machinessa . Tietoturvan tutkimuskeskus.
  4. ↑ pLab-projekti (downlink) . Haettu 21. marraskuuta 2009. Arkistoitu alkuperäisestä 14. marraskuuta 2009. 
  5. ↑ DIEHARD Test Suite arkistoitu 25. tammikuuta 2016.
  6. ↑ Dieharder: A Random Number Test Suite . Haettu 8. toukokuuta 2010. Arkistoitu alkuperäisestä 10. kesäkuuta 2010.
  7. ↑ ENT . Haettu 8. toukokuuta 2010. Arkistoitu alkuperäisestä 15. toukokuuta 2010.
  8. ↑ Donald E. Knuth. The Art of Computer Programming, Vol.2: Semi-Numerical Algorithms Arkistoitu 4. syyskuuta 2008 Wayback Machinessa / 3rd ed. Addison-Wesley, 1998
  9. ↑ Alfred Menezes et al. Handbook of Applied Cryptography arkistoitu 7. maaliskuuta 2005 Wayback Machinessa
  10. ↑ NIST IR 6390:n kehittyneiden salausstandardien ehdokasalgoritmien satunnaistestaus, arkistoitu 6. marraskuuta 2010 Wayback Machinessa 
  11. ↑ NIST IR 6483 -satunnaistestaus edistyneen salausstandardin finalistiehdokkaille , arkistoitu 27. toukokuuta 2010 Wayback Machinessa 

Kirjallisuus

  • Donald E. Knuth . Luku 3. Satunnaisluvut // Tietokoneohjelmoinnin taito. - 3. painos - M .: Williams , 2000. - V. 2. Saadut algoritmit. — 832 s. — ISBN 5-8459-0081-6 .
  • M. A. Ivanov, I. V. Chugunkov. Luku 4. PSS-generaattoreiden laadun arviointimenetelmä // Teoria, sovellus ja näennäissatunnaisten sekvenssien generaattoreiden laadun arviointi. - M. : KUDITS-OBRAZ, 2003. - 240 s. — ISBN 5-93378-056-1 .

Linkit