Tesztelje a következő darabot

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2014. október 9-én felülvizsgált verziótól ; az ellenőrzések 9 szerkesztést igényelnek .

A következő bit tesztje ( eng. next-bit test ) egy olyan teszt, amely a pszeudo-véletlenszám-generátorok kriptográfiai erősségének tesztelésére szolgál . A teszt azt mondja, hogy nem szabad olyan polinomiális algoritmusnak lennie, amely egy véletlen sorozat első k bitjével k + 1 bitet tud előre jelezni ½ valószínűséggel.

A véletlenszerűség meghatározásának problémája

A kriptográfia elméletében külön probléma annak meghatározása, hogy egy generátor által generált szám- vagy bitsorozat mennyire véletlenszerű. Általában különféle statisztikai teszteket használnak erre a célra, például a DIEHARD teszteket vagy a NIST teszteket . Andrew Yao 1982-ben bebizonyította [1] , hogy az a generátor, amely átmegy a "következő bitteszten", minden más statisztikai véletlenszerűségi teszten is megfelel, amely polinomiális időben elvégezhető.

Megfogalmazás

Egy bináris generátor megfelel a tesztnek a következő bitre, ha: bármely és bármely valószínűségi polinomiális idő algoritmusra A: -> {0,1} (Algoritmus, amely kezdeti adatként egy bit hosszúságú sorozatot tartalmaz , és egy bitet állít elő kimenet), a következő valódi egyenlőtlenség: $én$ ${\displaystyle \{0,1\}^{i))$ $én$

|P(A(s_{1}^{i-1})=s_{i})-1/2|<O(v(n)),

ahol az n fokú inverz polinomnál gyorsabban csökkenő függvény megnevezése . $O(v(n))$

Érdemes megjegyezni, hogy a következő bit tesztjének meghatározása nem ad semmilyen algoritmust ennek a tesztnek a végrehajtására.

Kibővített teszt a következő bithez

Az S forrástól kapott bináris sorozatot úgy tekintjük, hogy átment a kiterjesztett teszten a ->következő bitre, ha: bármely i és l esetén: 1 < i, l < n és bármely A valószínűségi polinomiális idő algoritmus: ${\displaystyle s_{1}^{n))$ ${\displaystyle \{0,1\}^{i-1))$ ${\displaystyle \{0,1\}^{l))$

|P(A(s_{1}^{i-1})=s_{i}^{1-i+l})-(1/2)^{l}|<O(v(n) ))

Bebizonyosodott, hogy a következő bitre vonatkozó kiterjesztett teszt és a következő bit tesztje egyenértékű. [2]

Kiegyensúlyozatlan sorozatok tesztelése

Bár a következő bitteszt egy univerzális módszer egy sorozat kimeneti bitjei függetlenségének ellenőrzésére, csak torzítatlan sorozatokra alkalmas, vagyis olyanokra, amelyekben az egy előfordulási valószínűsége megegyezik a nulla előfordulási valószínűségével. .

Ha a kimeneti sorozatnak nyilvánvalóan bizonyos torzítása kell , hogy legyen, azaz , akkor ez a teszt nem alkalmas. $b$ $P(s_{i})=b$

Ezért az ilyen sorozatok kimeneti bitjei függetlenségének teszteléséhez más teszteket kell használni. Különösen javasolták a teszt kiterjesztését a következő bitre - egy összehasonlító tesztet a következő bitre [3] . A teszt lényege, hogy kezdetben azt hisszük, hogy a kimeneti sorozat eloszlását valamilyen matematikai modell írja le, és a teszt arra szolgál, hogy ellenőrizze, hogy a generátor megfelel-e ennek a modellnek.

Benchmarking a következő bithez

Egy bináris generátor megfelel az S következő bites összehasonlító tesztnek az M modellhez képest, ha: bármely i és bármely valószínűségi polinomiális idő algoritmus (vagyis olyan algoritmus esetén, amelynek i hosszúságú bitsorozata van bemenetként és egy bitet ad ki) esetén a következő egyenlőtlenség érvényes: : $A\colon \{0,1\}^{i}\rightarrow \{0,1\}$

|P_{S}(A(s_{1}^{i-1})=s_{i})-P_{M}(A(s_{1}^{i-1})=s_{ i})|<O(v(n)),

ahol annak a valószínűsége, hogy az algoritmus megjósolja a következő bitet a modellgenerátor számára. $P_{M}(A(s_{1}^{i-1})=s_{i})$

Nyilvánvaló, hogy egy valóban véletlenszerű sorozatot reprezentáló M modellt kapunk , vagyis a következő bit klasszikus tesztjét. Adott a modell és a -val , megkapjuk a kívánt tesztesetet egy adott torzítású kiegyensúlyozatlan sorozathoz . $P_{M}(A(s_{1}^{i-1})=s_{i})=1/2)$ $P_{M}(A(s_{1}^{i-1})=1)=b$ $P_{M}(A(s_{1}^{i-1})=0)=1-b$ $b$

Gyakorlati megvalósítások

Sadeghiyan-Mohajeri tesztalgoritmus

Ez a teszt kihasználja a fastruktúra előnyeit , amely képes tárolni az összes információt a teljes sorozat részsorozatairól.

Az m-bites sorozatok kiszámítására szolgáló algoritmus egy súlyozott élekkel rendelkező bináris faként ábrázolható. Ebben a fában minden l mélységben lévő levél információt tárol arról, hogy az adott l-bites sorozattal hányszor találkoztak. Mivel a fa súlyozott, minden éléhez hozzá van rendelve a gyermeklapra írt összeg és a szülőben írt összeg aránya. Megfelelően nagy véletlenszerű sorozat esetén feltételezzük, hogy az éleknek megfelelő számok megközelítőleg egyenlőek lesznek 1/2-vel.

A Sadeghian-Mahaery algoritmus lépései

A χ²-eloszlásnak megfelelő hibaszintet egy szabadságfokkal és 5%-os hibafeltevéssel állítottuk be. $\alpha =\left(1+{\sqrt {(\chi ^{2})/n}}\jobbra)/2$
Kiszámítjuk, hogy l = kerek( (n) - 1), n a vizsgált sorozat hossza. $napló_{2}$
Az első biteket a sorozat végéhez rendeljük, és a sorozatot átfedő hosszúságú blokkokra osztjuk . $(l-1)$ $l$
Kiszámoljuk a találkozások gyakoriságát minden hosszúságú levélre . $l$
A fa szintjeit is kialakítjuk . Minden élre kiszámítjuk a megfelelő valószínűségeket. $l$ $(l-1)$
Minden egyes (l-1) szintű levél esetében, ha a következő bit (0 vagy 1) α-nál kisebb valószínűséggel fordul elő, akkor a következő bitet az előfordulás gyakorisága szerint jósolják meg. Ellenkező esetben az előrejelzés lehetetlen.
Eldobjuk az l-bites sorozat bal szélső bitjét. A fennmaradó (l-1) bitek felhasználásával lépjen újra a 6. lépésre, és határozza meg a következő bitet. Ezt a műveletet addig ismételjük, ameddig csak lehetséges. Miután megkaptuk a következő bit előrejelzésének lehetetlenségét, megszámoljuk az előrejelzett bitek számát. Így minden (l-1) hosszúságú sorozatra megkapjuk az előző lépés által megjósolt következő bitek számát.
Számítson ki egy P-értéket, amely megegyezik az előrejelzett bitek és az összes becslési kísérlet arányával.

Az r értéket annak valószínűségeként állítjuk be, hogy az ideális generátor a vizsgáltnál kevésbé véletlenszerű sorozatot generált. Általában r értéket [0,001; 0,01]. Ekkor ha a P-érték nagyobb, mint r, akkor a vizsgált sorozatot véletlenszerűnek tekintjük, és fordítva.

A Sadeghyan-Mohaeri teszt nem ad egyértelmű és pontos kritériumot egy sorozat véletlenszerűségének meghatározására. Ehelyett az algoritmus megalkotói azt feltételezik, hogy képesek következtetéseket levonni a sorozat általános viselkedéséről. Amikor az algoritmus sikeresen előrejelzi az (l+1) bitet, úgy tekintjük, hogy helyi determinizmus történt.

Gyakorló teszt a következő ütemhez (PNB)

Ennek a tesztnek az a célja, hogy meghatározza az eltéréseket egy részsorozat következő bit előfordulási statisztikájában. Ha van ilyen eltérés, a teszt megpróbálja ezt felhasználni a következő bit előrejelzésére. Egy sorozatot nem véletlenszerűnek tekintünk, ha túl sok olyan részsorozatot tartalmaz, amelyek utolsó bitje megjósolható.

A gyakorlati teszt ésszerűbb eredményeket mutat az eredeti Sadeghyan-Mokhaeri teszthez képest.

A PNB algoritmus lépései

A -eloszlásnak megfelelő hibaszintet egy szabadságfokkal és 5%-os hibafeltevéssel állítjuk be, hasonlóan a Sadeghyan-Mokhaeri algoritmushoz. $a={\frac {1+{\sqrt {X^{2}/n}}}{2}}$ $X^{2}$
Kiszámítjuk, hogy l = round( (n) - 2), n a vizsgált sorozat hossza. $napló_{2}$
Mozgassa az első l bitet a sorozat végére.
A Sadeghyan-Mohaeri algoritmus fához hasonló fát állítunk össze, a végpontokban a következő bitben a nullák és egyesek számának megfelelő számlálókat állítunk be.
A sorozatot egy l bites ablakkal „szkenneljük”. Az ablak kezdeti pozíciója az első l bit. Minden ciklusban 1 bittel előre mozgatjuk az ablakot, és az ablakot követő bit értékétől függően növeljük a csomópont számlálóját, amely megfelel az ablakban lévő bitek értékének.
Mindegyik csomóponthoz kiszámítjuk az arányokat és , ahol és az adott csomópont számlálóinak értékei. Ha ezen arányok valamelyike meghaladja az α-t, akkor növeljük a számlálót . $n_{0}/(n_{0}+n_{1})$ $n_{1}/(n_{0}+n_{1})$ $n_{0}$ $n_{1}$ $Y_{o}bs$
P-érték = (1/2)* erfc (( - μ)/sqrt(2σ²) kiszámítása $Y_{o}bs$

Meg kell jegyezni, hogy nincs ismert elmélet [4] , amely lehetővé tenné az algoritmus utolsó lépésében használt μ és σ pontos értékeinek kiszámítását. Ezért ezeket az értékeket hozzávetőlegesen számítják ki.

Lásd még

Jegyzetek

↑ Andrew Chi-Chih Yao. Csapóajtó-függvények elmélete és alkalmazásai.
↑ A. Lavasani és T. Eghlidos. Gyakorlati Következő Bitteszt az álvéletlenszerű szekvencia kiértékeléséhez. A Függelék
↑ AWSchrift, A. Shamir. A Next Bit Test egyetemességéről. 1998
↑ A. Lavasani és T. Eghlidos. Gyakorlati Következő Bitteszt az álvéletlenszerű szekvencia kiértékeléséhez. B. függelék

Irodalom

Andrew Chi-Chih Yao. Csapóajtó-függvények elmélete és alkalmazásai.
A. Lavasani és T. Eghlidos. Gyakorlati Következő Bitteszt az álvéletlenszerű szekvencia kiértékeléséhez
Raphael Pass. kriptográfia. Előadások.