Testa för nästa bit

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

Testet för nästa bit ( eng.  next-bit test ) är ett test som tjänar till att testa pseudoslumptalsgeneratorer för kryptografisk styrka . Testet säger att det inte bör finnas en polynomalgoritm som, givet de första k bitarna i en slumpmässig sekvens, kan förutsäga k + 1 bitar med en sannolikhet som inte är lika med ½.

Problemet med att definiera slumpmässighet

I teorin om kryptografi är ett separat problem att bestämma hur slumpmässig en sekvens av tal eller bitar som genereras av en generator är. I regel används olika statistiska tester för detta ändamål, såsom DIEHARD-testen eller NIST-testerna . Andrew Yao bevisade [1] 1982 att en generator som klarar "nästa bit-testet" kommer att klara alla andra statistiska slumpmässighetstest som kan göras i polynomtid.

Formulering

En binär generator klarar testet för nästa bit om: för vilken som helst probabilistisk polynom-tidsalgoritm A: -> {0,1} (Algorithm som har som initial data en sekvens av bitar av längd , och producerar en bit vid dess output), är följande sann ojämlikhet:

där  är beteckningen på en funktion som minskar snabbare än det inversa polynomet av grad n .

Det är värt att notera att definitionen av ett test för nästa bit inte tillhandahåller någon algoritm för att utföra detta test.

Förlängt test för nästa bit

Den binära sekvensen , mottagen från källan S, anses ha klarat det utökade testet för nästa bit om: för någon i och l: 1 < i, l < n och eventuell probabilistisk polynom-tidsalgoritm A: ->

Det är bevisat att det utökade testet för nästa bit och testet för nästa bit är ekvivalenta. [2]

Testa för obalanserade sekvenser

Även om nästa bittest är en universell metod för att kontrollera oberoendet av utgångsbitarna i en sekvens, är det endast lämpligt för opartiska sekvenser, det vill säga de där sannolikheten för förekomst av en är ekvivalent med sannolikheten för förekomst av noll .

Om utgångssekvensen uppenbarligen måste ha en viss förspänning , det vill säga, är detta test inte lämpligt.

För att testa oberoendet av utbitarna i sådana sekvenser måste därför andra tester användas. I synnerhet föreslogs en utvidgning av testet till nästa bit - ett jämförande test till nästa bit [3] . Tanken med testet är att vi initialt tror att fördelningen av utdatasekvensen beskrivs av någon matematisk modell, och testet tjänar till att kontrollera generatorns överensstämmelse med denna modell.

Benchmarking för nästa bit

En binär generator klarar S nästa-bits-jämförelsetestet mot modell M om: för valfritt i och någon probabilistisk polynom-tidsalgoritm (dvs en algoritm som har en sekvens av bitar med längden i som ingång och utmatning av en bit), följande ojämlikhet gäller: :

var  är sannolikheten för att algoritmen förutsäger nästa bit för modellgeneratorn.

Givet en modell M som representerar en verkligt slumpmässig sekvens får vi givetvis , det vill säga ett klassiskt test för nästa bit. Givet modellen med och får vi det önskade testfallet för en obalanserad sekvens med en given bias .

Praktiska implementeringar

Sadeghiyan-Mohajeri testalgoritm

Detta test drar fördel av trädstrukturen , som kan lagra all information om delsekvenser i den övergripande sekvensen.

Algoritmen för att beräkna m-bitars sekvenser kan representeras som ett binärt träd med viktade kanter. I detta träd lagrar varje löv på djupet l information om hur många gånger den givna l-bitarssekvensen har påträffats. Eftersom trädet är viktat tilldelas var och en av dess kanter förhållandet mellan det belopp som skrivs i det underordnade arket och det belopp som skrivs i det överordnade. För en tillräckligt stor slumpmässig sekvens antas det att talen som motsvarar kanterna kommer att vara ungefär lika med 1/2.

Steg i Sadeghian-Mahaery-algoritmen
  1. Vi sätter felnivån som motsvarar χ²-fördelningen med en frihetsgrad och ett felantagande på 5%.
  2. Vi beräknar l = rund ( (n) - 1), n ​​är längden på sekvensen som studeras.
  3. Vi tillskriver de första bitarna till slutet av sekvensen och delar upp sekvensen i överlappande längdblock .
  4. Vi beräknar mötesfrekvensen för alla lövlängder .
  5. Vi bildar också trädets nivåer. Vi beräknar motsvarande sannolikheter för alla kanter.
  6. För varje blad på nivå (l-1), om nästa bit (0 eller 1) inträffar med en sannolikhet mindre än α, förutsägs nästa bit enligt frekvensen av den förekomsten. Annars är förutsägelse omöjlig.
  7. Vi kasserar biten längst till vänster i l-bitars sekvensen. Använd de återstående (l-1) bitarna, gå till steg 6 igen och bestäm nästa bit. Vi upprepar denna operation så länge som möjligt. Efter att vi har fått omöjligheten att förutsäga nästa bit, räknar vi antalet förutsagda bitar. Sålunda får vi för varje längdsekvens (l-1) antalet nästa bitar som förutspåtts av föregående steg.
  8. Beräkna ett P-värde lika med förhållandet mellan predikterade bitar och alla prediktionsförsök.

Vi satte värdet r som sannolikheten att den ideala generatorn genererade en sekvens som är mindre slumpmässig än den som studeras. Vanligtvis väljs r inom [0,001; 0,01]. Om sedan P-värdet är större än r, så anses den studerade sekvensen vara slumpmässig och vice versa annars.

Sadeghyan-Mohaeri-testet ger inte ett tydligt och exakt kriterium för att bestämma slumpmässigheten i en sekvens. Istället antar skaparna av algoritmen förmågan att dra några slutsatser om sekvensens övergripande beteende. När algoritmen framgångsrikt förutsäger (l+1) bitar, anses det att lokal determinism har inträffat.

Öva test för nästa takt (PNB)

Syftet med detta test är att bestämma avvikelser i nästa bitförekomststatistik för en undersekvens. Om det finns en sådan avvikelse försöker testet använda den för att förutsäga nästa bit. En sekvens anses icke-slumpmässig om den innehåller för många delsekvenser vars sista bit är förutsägbar.

Det praktiska testet visar mer rimliga resultat i jämförelse med det ursprungliga Sadeghyan-Mokhaeri-testet.

Steg för PNB-algoritmen
  1. Vi ställer in felnivån motsvarande -fördelning med en frihetsgrad och ett felantagande på 5%, på samma sätt som Sadeghyan-Mokhaeri-algoritmen.
  2. Vi beräknar l = rund( (n) - 2), n är längden på sekvensen som studeras.
  3. Flytta de första l bitarna till slutet av sekvensen.
  4. Vi komponerar ett träd som liknar trädet i Sadeghyan-Mohaeri-algoritmen, i slutnoderna ställer vi in ​​räknare som motsvarar antalet nollor och ettor i nästa bit.
  5. Vi "scannar" sekvensen med ett fönster av storlek l-bitar. Fönstrets initiala position är de första l bitarna. Med varje cykel flyttar vi fönstret 1 bit framåt och, beroende på värdet i biten som följer efter fönstret, ökar vi nodens räknare som motsvarar värdena på bitarna i fönstret.
  6. För var och en av noderna beräknar vi förhållandena och , var och  är värdena för räknarna för den givna noden. Om ett av dessa förhållande överstiger α, ökar vi räknaren .
  7. Beräkna P-värde = (1/2)* erfc ((  - μ)/sqrt(2σ²)

Det bör noteras att det inte finns någon känd teori [4] som gör att man kan beräkna de exakta värdena på μ och σ som används i det sista steget i algoritmen. Därför beräknas dessa värden ungefär.

Se även

Anteckningar

  1. ↑ Andrew Chi-Chih Yao. Teori och tillämpningar av falldörrsfunktioner.
  2. ↑ A. Lavasani och T. Eghlidos. Praktiskt test för nästa bit för att utvärdera pseudoslumpmässig sekvens. Bilaga A
  3. ↑ AWSchrift, A. Shamir. Om universaliteten av nästa bit-test. 1998
  4. ↑ A. Lavasani och T. Eghlidos. Praktiskt test för nästa bit för att utvärdera pseudoslumpmässig sekvens. Bilaga B

Litteratur

  • Andrew Chi-Chih Yao. Teori och tillämpningar av falldörrsfunktioner.
  • A. Lavasani och T. Eghlidos. Praktiskt test för nästa bit för att utvärdera pseudoslumpmässig sekvens
  • Raphael Pass. kryptografi. Föredrag.