Testa pseudo-slumpmässiga sekvenser

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 oktober 2020; kontroller kräver 5 redigeringar .

Att testa pseudo-slumpmässiga sekvenser  är en uppsättning metoder för att bestämma måttet på närhet av en given pseudo-slumpmässig sekvens till en slumpmässig. En sådan åtgärd är vanligtvis närvaron av en enhetlig fördelning , en stor period, en lika frekvens av förekomst av identiska delsträngar, etc.

Teoretisk grund

Konstruktionsprinciper

Ett av de mest illustrativa testerna är ett test för en enhetlig fördelning av förekomstfrekvenserna för varje tecken. Låta vara  en följd av längden n och dimensionen m . Då måste frekvenserna ν i tillhöra segmentet . Men de flesta tester använder en annan metod - acceptera eller förkasta slumpmässighetshypotesen för sekvensen med hjälp av statistiska fördelningar.

Genom att känna till de probabilistiska egenskaperna hos en verkligt slumpmässig sekvens kan man använda dem för att testa hypotesen om hur lik den genererade sekvensen är en slumpmässig. För att göra detta väljs en lämplig statistik för varje test, dess värden beräknas för den ideala och genererade sekvensen. Om skillnaden mellan dessa värden överstiger ett kritiskt värde som ställts in i förväg, anses sekvensen vara icke-slumpmässig. För "bra" sekvenser är sannolikheten för en sådan händelse extremt liten (låt oss säga ~0,001 och beteckna det med α). Det finns dock en möjlighet att en "dålig" sekvens kommer att uppfylla kriteriet och en slutsats kommer att göras om dess slumpmässighet (vi betecknar sannolikheten för en sådan händelse som β). I praktiken är sekvenslängderna n , α och β relaterade, α ges och n väljs för att minimera β.

Låt oss definiera P-värdet som sannolikheten att den ideala generatorn genererade en sekvens som är mindre slumpmässig än den som studeras. Om sedan P-värdet är större än α, så anses den studerade sekvensen vara slumpmässig och vice versa annars.

Kortfattat kan stegen i statistisk testning avbildas i form av en tabell:

stegnummer Bearbeta Kommentarer
ett Uttalande av hypotesen Vi antar att sekvensen är slumpmässig
2 Beräkning av statistik för den studerade sekvensen Bitnivåtestning
3 P-värde beräkning P-värde [0; ett]
fyra Jämför P-värde med α Ställ α inom [0,001; 0,01]; om P-värde > α är testet godkänt

Tolkning av resultat

Låt en binär sekvens s ges . Det krävs att fastställa om den givna sekvensen klarar det statistiska testet eller inte. För att göra detta används flera olika tillvägagångssätt:

Tröskel

Detta tillvägagångssätt består i att beräkna något statistiskt värde för den binära sekvensen c(s) och jämföra den med något tröskelvärde. Om det resulterande värdet c(s) är mindre än tröskelvärdet, så klarar sekvensen s detta test.

Fast värdeintervall

Tillvägagångssättet består också i att beräkna något statistiskt värde för den binära sekvensen c(s) som i det första fallet. Men nu säger vi att om c(s) ligger utanför något värdeintervall, så klarar sekvensen s detta test.

Sannolikhetsvärde

Ett tredje tillvägagångssätt för att bestämma huruvida en binär sekvens s klarar ett statistiskt test innefattar att räkna inte bara statistiken c(s) utan också dess motsvarande sannolikhetsvärde p . Vanligtvis beräknas en viss statistik på ett sådant sätt att dess stora värden antyder en icke-slumpmässig karaktär av sekvensen s . Då är p sannolikheten att c(s) kommer att vara större än eller lika med c(s') beräknat för en verkligt slumpmässig sekvens s' . Därför kan små värden på sannolikheten p (vanligtvis p < 0,05 eller p < 0,01) tolkas som bevis på att s inte är slumpmässigt. Således, om för något fast värde a sannolikhetsvärdet p < a , så klarar den binära sekvensen s detta test. Som regel tar a värden från intervallet [0,001;0,01].

Grafiktester

Denna kategori inkluderar tester, vars resultat visas i form av grafer som karakteriserar egenskaperna hos den studerade sekvensen. Bland dem:

  • histogram över fördelningen av sekvenselement; låter dig utvärdera enhetligheten i fördelningen av tecken i sekvensen och bestämma frekvensen för upprepning av varje tecken;
  • distribution på planet; utformad för att bestämma förhållandet mellan elementen i sekvensen;
  • seriekontroll; låter dig bestämma enhetligheten för enskilda tecken i sekvensen, såväl som enhetligheten i fördelningen av serier av k bitar;
  • kontrollera för monotoni; tjänar till att fastställa enhetlighet baserat på analysen av icke-ökande och icke-minskande undersekvenser;
  • autokorrelationsfunktion ; utformad för att utvärdera korrelationen mellan förskjutna kopior av sekvenser och individuella delsekvenser;
  • linjär komplexitetsprofil; testet utvärderar beroendet av sekvensens linjära komplexitet på dess längd;
  • grafiskt spektraltest; låter dig utvärdera enhetligheten i fördelningen av bitar i sekvensen baserat på analysen av höjden på Fourier-transformens extremvärden .

Resultaten av grafiktester tolkas av en människa, så slutsatserna baserade på dem kan vara tvetydiga.

Statistiska tester

Till skillnad från grafiska tester ger statistiska tester en numerisk egenskap av sekvensen och låter dig entydigt säga om testet är godkänt. Följande programvarupaket för statistiska tester är mest kända:

Nej. namn Författare Organisation
ett NIST-tester [1] Andrew Rukhin, et. al. NIST ITL
2 TEST-U01 [2] P. L'Ecuyer och andra. Universit'e de Montr'eal
3 CRYPT-X [3] Helen Gustafson et al. Queensland University of Technology
fyra The pLab Project [4] Peter Hellekalek Universitetet i Salzburg
5 DIEHARD [5] George Marsaglia Florida State University
6 Dieharder [6] Robert G Brown Duke University
7 ÖNHHH [7] John Walker Autodesk , Inc.
åtta Konsten att programmera vol. 2 seminumeriska algoritmer [8] Donald Knuth Stanford University
9 Handbook of Applied Cryptography [9] Alfred Menezes och andra. C.R.C. Press, Inc.

DIEHARD tester

DIEHARD-tester utvecklades av George Marsaglia under flera år och publicerades först på CD-ROM tillägnad slumpmässiga nummer. De anses vara en av de mest rigorösa testsviterna som är kända.

D. Knuths tester

Knuths tester bygger på ett statistiskt test . Statistikens beräknade värde jämförs med resultat i tabellform, och beroende på sannolikheten att sådan statistik förekommer dras en slutsats om dess kvalitet. Bland fördelarna med dessa tester är deras lilla antal och förekomsten av snabba exekveringsalgoritmer. Nackdelen är osäkerheten i tolkningen av resultaten. Här är en sammanfattning av dessa tester:

  • Söker efter olänkade serier . Sekvensen är uppdelad i m icke-överlappande serier och en fördelning konstrueras för förekomstfrekvenserna för varje möjlig serie.
  • Kontrollera intervaller . Detta test kontrollerar enhetligheten i fördelningen av tecken i den studerade sekvensen genom att analysera längden på delsekvenser, vars alla element tillhör ett visst numeriskt intervall.
  • Kontrollera kombinationer . Sekvensen är uppdelad i undersekvenser av en viss längd och serier som består av olika kombinationer av tal undersöks.
  • Kupongsamlartest . Låta vara  en följd av längden n och dimensionen m . Följder av en viss längd som innehåller varje m -siffrigt nummer undersöks.
  • Kontrollera permutationer . Detta test kontrollerar enhetligheten i fördelningen av tecken i den studerade sekvensen genom att analysera det inbördes arrangemanget av siffror i undersekvenser.
  • Kontrollera för monotoni . Används för att bestämma enhetlighet baserat på analys av icke-ökande och icke-minskande delsekvenser.
  • Korrelationskontroll . Detta test kontrollerar det ömsesidiga oberoendet av elementen i en sekvens.

NIST-tester

Skillnaden mellan dessa tester och andra moderna är algoritmernas öppenhet. Bland fördelarna är också en entydig tolkning av testresultat. Tabell över allmänna egenskaper:

Nej. Testnamn Definierad defekt
ett frekvenstest För många nollor eller ettor
2 Kontrollera ackumulerade belopp För många nollor eller ettor i början av sekvensen
3 Kollar "hål" i undersekvenser Avvikelse i fördelningen av sekvenser av enheter
fyra Kollar "hål" Ett stort (litet) antal undersekvenser av nollor och ettor indikerar att fluktuationen i bitströmmen är för snabb (långsam)
5 Kontrollera rangen av matriser Avvikelse i fördelningen av matriser från motsvarande fördelning för en verkligt slumpmässig sekvens, associerad med sekvensernas periodicitet
6 Spektraltest Periodiska egenskaper hos en sekvens
7 Kontrollerar efter icke-överlappande mönster Icke-periodiska mönster är för vanliga
åtta Söker efter korsande mönster För vanliga m -bitars sekvenser av ettor
9 Maurers universella statistiska test Kompressibilitet (regelbundenhet) för en sekvens
tio Kontrollerar slumpmässiga avvikelser Avvikelse från fördelningen av antalet förekomster av delsekvenser av visst slag
elva En variant av att kontrollera för slumpmässiga avvikelser Avvikelse från fördelningen av antalet förekomster av delsekvenser av visst slag
12 Kontrollera den ungefärliga entropin Ojämn fördelning av m -bitars ord. Små värden betyder hög repeterbarhet
13 Seriekontroll Oregelbundenhet i fördelningen av m -bitars ord
fjorton Komprimering med Lempel-Ziv-algoritmen Större komprimerbarhet än en sann slumpmässig sekvens
femton Linjär komplexitet Avvikelse från linjär komplexitetsfördelning för ändlig delstränglängd

Praktiska applikationer

Generatorer av slumpmässiga och pseudo-slumptal är länken inom informationssäkerhet . På sätt och vis är dessa viktiga byggstenar för kryptografiska algoritmer och protokoll. Eftersom sådana generatorer används i många kryptografiska problem, till exempel bildandet av slumpmässiga parametrar och nycklar för krypteringssystem, är kraven på dem ganska höga. I synnerhet är ett av kriterierna för en absolut godtycklig binär sekvens som erhålls vid generatorns utgång omöjligheten att förutsäga den i frånvaro av någon information om data som tillförs generatorns ingång. Därför utförs i praktiken statistiska tester för att kontrollera slumpmässigheten hos en binär sekvens som genereras av en slump- eller pseudoslumptalsgenerator. Vilket i sin tur gör att du i förväg kan identifiera generatorer som uppfyller kraven för ett specifikt kryptografiskt problem.

AES-tävling

För att godkänna den nya avancerade krypteringsstandarden höll National Institute of Standards and Technology , med stöd av den amerikanska regeringen, en tävling under vilken 15 ansökande algoritmer testades. Ett av kriterierna som användes för att utvärdera algoritmer var deras lämplighet som slumptalsgeneratorer. Testning av sådana generatorer för bildning av slumpmässiga binära sekvenser med goda statistiska egenskaper utfördes med hjälp av NIST statistiska testsvit .

Under den första omgången av AES gjordes testning med 128-bitars nycklar. Endast 9 algoritmer av 15 algoritmer klarade de statistiska testerna [10] .

Baserat på resultaten från den första omgången valdes 5 krypteringsalgoritmer ut som AES-finalister: MARS , RC6 , Rijndael , Serpent och Twofish . I den andra omgången av AES-tävlingen utvärderades lämpligheten av dessa 5 algoritmer som slumptalsgeneratorer baserat på 192-bitars och 256-bitars nycklar. Varaktigheten av NIST statistiska tester var flera månader, med beräkningar utförda på många Sun Ultra-arbetsstationer . All data genererades och bearbetades online. Som ett resultat av den andra omgången visades det att var och en av de fem finalisterna genererar en slumpmässig binär sekvens med goda statistiska egenskaper och därför kan användas som en pseudoslumptalsgenerator, och det är möjligt att använda nycklar med storlekarna: 128 , 192 och 256 bitar [11] .

Se även

Anteckningar

  1. ↑ NIST Cryptographic Toolkit . Hämtad 8 maj 2010. Arkiverad från originalet 17 augusti 2011.
  2. ↑ TestU01 . Tillträdesdatum: 8 maj 2010. Arkiverad från originalet 23 juli 2010.
  3. ↑ Crypt-X Arkiverad 22 september 2008 på Wayback Machine . Forskningscentrum för informationssäkerhet.
  4. ↑ The pLab Project (nedlänk) . Hämtad 21 november 2009. Arkiverad från originalet 14 november 2009. 
  5. ↑ DIEHARD Test Suite Arkiverad 25 januari 2016.
  6. ↑ Dieharder: A Random Number Test Suite . Hämtad 8 maj 2010. Arkiverad från originalet 10 juni 2010.
  7. ↑ ENT . Hämtad 8 maj 2010. Arkiverad från originalet 15 maj 2010.
  8. ↑ Donald E. Knuth. The Art of Computer Programming, Vol.2: Semi-Numerical Algorithms Arkiverad 4 september 2008 på Wayback Machine / 3rd ed. Addison-Wesley, 1998
  9. ↑ Alfred Menezes et al. Handbook of Applied Cryptography Arkiverad 7 mars 2005 på Wayback Machine
  10. ↑ NIST IR 6390 Slumpmässighetstestning av Advanced Encryption Standard Candidate Algoritms Arkiverad 6 november 2010 på Wayback Machine 
  11. ↑ NIST IR 6483 Slumpmässighetstestning av finalistkandidaterna för Advanced Encryption Standard Arkiverad 27 maj 2010 på Wayback Machine 

Litteratur

  • Donald E. Knuth . Kapitel 3. Slumptal // Konsten att programmera datorer. - 3:e uppl. - M .: Williams , 2000. - V. 2. Erhållna algoritmer. — 832 sid. — ISBN 5-8459-0081-6 .
  • M. A. Ivanov, I. V. Chugunkov. Kapitel 4. Metodik för att bedöma kvaliteten på PSS-generatorer // Teori, tillämpning och bedömning av kvaliteten på generatorer av pseudo-slumpmässiga sekvenser. - M. : KUDITS-OBRAZ, 2003. - 240 sid. — ISBN 5-93378-056-1 .

Länkar