Test na další bit

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. října 2014; kontroly vyžadují 9 úprav .

Test na další bit ( angl. next-bit test ) je test, který slouží k testování generátorů pseudonáhodných čísel na šifrovací sílu . Test říká, že by neměl existovat polynomiální algoritmus, který by vzhledem k prvním k bitům náhodné sekvence mohl předpovídat k + 1 bitů s pravděpodobností ne rovnou ½.

Problém definice náhodnosti

V teorii kryptografie je samostatný problém určit, jak náhodná je sekvence čísel nebo bitů generovaných generátorem. K tomuto účelu se zpravidla používají různé statistické testy, jako jsou testy DIEHARD nebo testy NIST . Andrew Yao v roce 1982 dokázal [1] , že generátor, který projde „testem dalšího bitu“, projde jakýmkoli jiným statistickým testem náhodnosti, který lze provést v polynomiálním čase.

Formulace

Binární generátor projde testem pro další bit, pokud: pro jakýkoli a jakýkoli pravděpodobnostní polynomiální-časový algoritmus A: -> {0,1} (Algoritmus, který má jako počáteční data sekvenci bitů délky a vytváří bit na svém výstup), toto je skutečná nerovnost: $i$ ${\displaystyle \{0,1\}^{i))$ $i$

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

kde je označení funkce klesající rychleji než inverzní polynom stupně n . $O(v(n))$

Stojí za zmínku, že definice testu pro další bit neposkytuje žádný algoritmus pro provádění tohoto testu.

Rozšířený test pro další bit

Binární posloupnost přijatá ze zdroje S se považuje za prošla rozšířeným testem pro další bit, pokud: pro jakékoli i a l: 1 < i, l < n a jakýkoli pravděpodobnostní polynomický algoritmus A: -> ${\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) ))

Je dokázáno, že rozšířený test pro další bit a test pro další bit jsou ekvivalentní. [2]

Testování na nevyvážené sekvence

I když je test dalšího bitu univerzální metodou pro kontrolu nezávislosti výstupních bitů sekvence, je vhodný pouze pro nezaujaté sekvence, tedy takové, ve kterých je pravděpodobnost výskytu jedničky ekvivalentní pravděpodobnosti výskytu nuly. .

Pokud výstupní sekvence musí mít zjevně nějaké zkreslení , to znamená , pak tento test není vhodný. $b$ $P(s_{i})=b$

Pro testování nezávislosti výstupních bitů takových sekvencí je proto nutné použít jiné testy. Zejména bylo navrženo rozšíření testu na další bit - srovnávací test na další bit [3] . Myšlenkou testu je, že zpočátku věříme, že rozložení výstupní sekvence je popsáno nějakým matematickým modelem a test slouží ke kontrole souladu generátoru s tímto modelem.

Benchmarking pro další bit

Binární generátor projde testem porovnání dalšího bitu S proti modelu M, pokud: pro libovolné i a jakýkoli pravděpodobnostní algoritmus polynomiálního času (tj. algoritmus, který má posloupnost bitů délky i jako vstup a výstup bit), následující platí nerovnost: : $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)),

kde je pravděpodobnost, že algoritmus předpovídá další bit pro generátor modelu. $P_{M}(A(s_{1}^{i-1})=s_{i})$

Je zřejmé, že daný model M představující skutečně náhodnou sekvenci dostaneme , tedy klasický test pro další bit. Vzhledem k modelu s a získáme požadovaný testovací případ pro nevyváženou sekvenci s daným vychýlením . $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$

Praktické implementace

Sadeghiyan-Mohajeri testovací algoritmus

Tento test využívá stromové struktury , která je schopna uložit všechny informace o podsekvencích v celkové sekvenci.

Algoritmus pro výpočet m-bitových sekvencí může být reprezentován jako binární strom s váženými hranami. V tomto stromě každý list v hloubce l ukládá informaci o tom, kolikrát byla daná l-bitová sekvence nalezena. Protože je strom vážený, je každé jeho hraně přiřazen poměr částky zapsané v podřízeném listu k částce zapsané v nadřazeném. Pro dostatečně velkou náhodnou posloupnost se předpokládá, že čísla odpovídající hranám budou přibližně rovna 1/2.

Kroky Sadeghian-Mahaeryho algoritmu

Nastavili jsme chybovost odpovídající χ²-rozdělení s jedním stupněm volnosti a předpokladem chyby 5 %. $\alpha =\left(1+{\sqrt {(\chi ^{2})/n}}\right)/2$
Vypočítáme l = round( (n) - 1), n je délka studované sekvence. $log_{2}$
První bity přiřadíme konci sekvence a rozdělíme sekvenci na překrývající se bloky délky . $(l-1)$ $l$
Četnost schůzek počítáme pro všechny listy délky . $l$
Tvoříme také úrovně stromu. Pro všechny hrany vypočítáme odpovídající pravděpodobnosti. $l$ $(l-1)$
Pokud se pro každý list na úrovni (l-1) objeví další bit (0 nebo 1) s pravděpodobností menší než α, další bit se předpovídá podle frekvence tohoto výskytu. Jinak je předpověď nemožná.
Zahodíme bit nejvíce vlevo z l-bitové sekvence. Pomocí zbývajících (l-1) bitů přejděte znovu ke kroku 6 a určete další bit. Tuto operaci opakujeme co nejdéle. Poté, co zjistíme nemožnost predikce dalšího bitu, spočítáme počet predikovaných bitů. Tak dostaneme pro každou sekvenci délky (l-1) počet dalších bitů předpovězených předchozím krokem.
Vypočtěte P-hodnotu rovnou poměru predikovaných bitů ke všem pokusům o predikci.

Hodnotu r jsme nastavili jako pravděpodobnost, že ideální generátor vygeneroval posloupnost méně náhodnou než studovaná. Obvykle se r volí v rozmezí [0,001; 0,01]. Pokud je pak P-hodnota větší než r, pak je studovaná posloupnost považována za náhodnou a naopak jinak.

Sadeghyan-Mohaeriho test neposkytuje jasné a přesné kritérium pro určení náhodnosti sekvence. Místo toho tvůrci algoritmu předpokládají schopnost vyvodit nějaké závěry o celkovém chování sekvence. Když algoritmus úspěšně předpovídá (l+1) bitů, má se za to, že došlo k lokálnímu determinismu.

Practice Test for the Next Beat (PNB)

Účelem tohoto testu je určit odchylky ve statistice výskytu dalšího bitu pro podsekvenci. Pokud existuje taková odchylka, test se ji pokusí použít k predikci dalšího bitu. Sekvence je považována za nenáhodnou, pokud obsahuje příliš mnoho podsekvencí, jejichž poslední bit je předvídatelný.

Praktický test ukazuje rozumnější výsledky ve srovnání s původním Sadeghyan-Mokhaeriho testem.

Kroky algoritmu PNB

Nastavili jsme chybovost odpovídající -distribuci s jedním stupněm volnosti a předpokladem chyby 5%, podobně jako u Sadeghyan-Mokhaeriho algoritmu. $a={\frac {1+{\sqrt {X^{2}/n}}}{2}}$ $X^{2}$
Vypočítáme l = round( (n) - 2), n je délka studované sekvence. $log_{2}$
Přesuňte prvních l bitů na konec sekvence.
Sestavíme strom podobný stromu v algoritmu Sadeghyan-Mohaeri, v koncových uzlech nastavíme čítače odpovídající počtu nul a jedniček v dalším bitu.
Sekvenci „naskenujeme“ oknem o velikosti l bitů. Počáteční pozice okna je prvních l bitů. S každým cyklem posuneme okno o 1 bit dopředu a v závislosti na hodnotě v bitu za oknem zvýšíme čítač uzlu odpovídající hodnotám bitů v okně.
Pro každý z uzlů vypočítáme poměry a , kde a jsou hodnoty čítačů pro daný uzel. Pokud jeden z těchto poměrů překročí α, pak zvýšíme čítač . $n_{0}/(n_{0}+n_{1})$ $n_{1}/(n_{0}+n_{1})$ $n_{0}$ $n_{1}$ $Y_{o}bs$
Vypočítat P-hodnotu = (1/2)* erfc (( - μ)/sqrt(2σ²) $Y_{o}bs$

Je třeba poznamenat, že není známa žádná teorie [4] , která by umožňovala vypočítat přesné hodnoty μ a σ použité v posledním kroku algoritmu. Proto se tyto hodnoty počítají přibližně.

Viz také

Poznámky

↑ Andrew Chi-Chih Yao. Teorie a aplikace funkcí padacích dveří.
↑ A. Lavasani a T. Eghlidos. Praktický Next Bit Test pro vyhodnocení pseudonáhodné sekvence. Příloha A
↑ AWSchrift, A. Shamir. O univerzálnosti dalšího bitového testu. 1998
↑ A. Lavasani a T. Eghlidos. Praktický Next Bit Test pro vyhodnocení pseudonáhodné sekvence. Dodatek B

Literatura

Andrew Chi-Chih Yao. Teorie a aplikace funkcí padacích dveří.
A. Lavasani a T. Eghlidos. Praktický Next Bit Test pro vyhodnocení pseudonáhodné sekvence
Průsmyk Raphael. kryptografie. Přednášky.