Testování pseudonáhodných sekvencí

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é 19. října 2020; kontroly vyžadují 5 úprav .

Testování pseudonáhodných sekvencí  je soubor metod pro stanovení míry blízkosti dané pseudonáhodné sekvence k náhodné. Takovou mírou je obvykle přítomnost rovnoměrného rozdělení , velká perioda, stejná frekvence výskytu identických podřetězců atd.

Teoretický základ

Konstrukční principy

Jedním z nejnázornějších testů je test rovnoměrného rozložení četností výskytu každého znaku. Nechť  je posloupnost délky n a dimenze m . Potom frekvence ν i musí patřit do intervalu . Většina testů však používá jinou metodu – přijetí nebo zamítnutí hypotézy náhodnosti sekvence pomocí statistických rozdělení.

Známe-li pravděpodobnostní vlastnosti skutečně náhodné posloupnosti, můžeme je použít k testování hypotézy o tom, jak podobná je vygenerovaná posloupnost náhodné posloupnosti. K tomu je pro každý test vybrána vhodná statistika, její hodnoty jsou vypočteny pro ideální a vygenerovanou sekvenci. Pokud rozdíl mezi těmito hodnotami překročí nějakou předem nastavenou kritickou hodnotu, je sekvence považována za nenáhodnou. Pro „dobré“ sekvence je pravděpodobnost takové události extrémně malá (řekněme ~0,001 a označme ji α). Existuje však možnost, že kritérium splní „špatná“ posloupnost a bude učiněn závěr o její náhodnosti (pravděpodobnost takové události označujeme β). V praxi jsou délky sekvencí n , α a β ve vztahu, je dáno α a n je zvoleno tak, aby se minimalizovalo β.

Definujme P-hodnotu jako pravděpodobnost, že ideální generátor vygeneroval posloupnost méně náhodnou než studovaná. Pokud je pak P-hodnota větší než α, pak je studovaná posloupnost považována za náhodnou a naopak jinak.

Stručně lze kroky statistického testování znázornit ve formě tabulky:

číslo kroku Proces Komentáře
jeden Vyjádření hypotézy Předpokládáme, že posloupnost je náhodná
2 Výpočet statistiky studované sekvence Testování úrovně bitů
3 Výpočet P-hodnoty P hodnota [0; jeden]
čtyři Porovnání P-hodnoty s α Nastavte α v rozmezí [0,001; 0,01]; pokud P-hodnota > α, pak je test úspěšný

Interpretace výsledků

Nechť je dána binární posloupnost s . Je třeba zjistit, zda daná sekvence projde statistickým testem či nikoliv. K tomu se používá několik různých přístupů:

Práh

Tento přístup spočívá ve výpočtu nějaké statistické hodnoty binární posloupnosti c(s) a jejím porovnání s nějakou prahovou hodnotou. Pokud je výsledná hodnota c(s) menší než prahová hodnota, pak sekvence s v tomto testu nevyhoví.

Pevný rozsah hodnot

Přístup také spočívá ve výpočtu nějaké statistické hodnoty binární posloupnosti c(s) jako v prvním případě. Nyní však říkáme, že pokud je c(s) mimo nějaký rozsah hodnot, pak posloupnost s v tomto testu selže.

Hodnota pravděpodobnosti

Třetí přístup k určení, zda binární sekvence s projde statistickým testem, zahrnuje počítání nejen statistiky c(s), ale také její odpovídající pravděpodobnostní hodnotu p . Obvykle se konkrétní statistika počítá tak, že její velké hodnoty znamenají nenáhodnou povahu sekvence s . Potom p je pravděpodobnost, že c(s) bude větší nebo rovno c(s') vypočítané pro skutečně náhodnou posloupnost s' . Proto malé hodnoty pravděpodobnosti p (obvykle p < 0,05 nebo p < 0,01) lze interpretovat jako důkaz, že s není náhodné. Je-li tedy pro nějakou pevnou hodnotu a pravděpodobnostní hodnota p < a , pak binární posloupnost s v tomto testu selže. Zpravidla a nabývá hodnot z intervalu [0,001;0,01].

Grafické testy

Do této kategorie patří testy, jejichž výsledky jsou zobrazeny ve formě grafů, které charakterizují vlastnosti studované sekvence. Mezi nimi:

  • histogram distribuce sekvenčních prvků; umožňuje vyhodnotit rovnoměrnost rozložení znaků v sekvenci a určit frekvenci opakování každého znaku;
  • distribuce na rovině; určené k určení vztahu mezi prvky sekvence;
  • sériová kontrola; umožňuje určit jednotnost jednotlivých znaků v sekvenci a také jednotnost rozložení řad k bitů;
  • zkontrolujte monotónnost; slouží ke stanovení uniformity na základě analýzy nerostoucích a neklesajících dílčích sekvencí;
  • autokorelační funkce ; navržený k vyhodnocení korelace mezi posunutými kopiemi sekvencí a jednotlivými subsekvencemi;
  • lineární profil složitosti; test hodnotí závislost lineární složitosti sekvence na její délce;
  • grafický spektrální test; umožňuje vyhodnotit rovnoměrnost rozložení bitů sekvence na základě analýzy výšky odlehlých hodnot Fourierovy transformace .

Výsledky grafických testů interpretuje člověk, takže závěry na nich založené mohou být nejednoznačné.

Statistické testy

Na rozdíl od grafických testů poskytují statistické testy číselnou charakteristiku sekvence a umožňují jednoznačně říci, zda test prošel. Nejznámější jsou následující softwarové balíčky statistických testů:

Ne. název Autor Organizace
jeden NIST testy [1] Andrew Rukhin, et. al. NIST ITL
2 TEST-U01 [2] P. L'Ecuyer a další. Universit'e de Montr'eal
3 CRYPT-X [3] Helen Gustafson a kol. Queensland University of Technology
čtyři Projekt pLab [4] Petr Hellekálek Univerzita v Salcburku
5 DIEHARD [5] George Marsaglia Floridská státní univerzita
6 Dieharder [6] Robert G Brown Duke University
7 ORL [7] John Walker Autodesk , Inc.
osm The Art Of Computer Programming Vol. 2 seminumerické algoritmy [8] Donald Knuth Stanfordská Univerzita
9 Příručka aplikované kryptografie [9] Alfred Menezes a další. Společnost C.R.C. Press, Inc.

DIEHARD testy

Testy DIEHARD vyvinul George Marsaglia v průběhu několika let a byly poprvé publikovány na CD-ROM věnovaném náhodným číslům. Jsou považovány za jednu z nejpřísnějších známých testovacích sad.

Testy D. Knutha

Knuthovy testy jsou založeny na statistickém testu . Vypočtená hodnota statistiky je porovnána s tabulkovými výsledky a v závislosti na pravděpodobnosti výskytu takové statistiky je učiněn závěr o její kvalitě. Mezi výhody těchto testů patří jejich malý počet a existence rychlých prováděcích algoritmů. Nevýhodou je nejistota v interpretaci výsledků. Zde je souhrn těchto testů:

  • Kontrola nepropojených sérií . Sekvence je rozdělena na m nepřekrývajících se řad a je zkonstruováno rozdělení pro četnosti výskytu každé možné řady.
  • Kontrolujte intervaly . Tento test kontroluje rovnoměrnost rozložení znaků ve studované posloupnosti analýzou délek dílčích posloupností, jejichž všechny prvky patří do určitého číselného intervalu.
  • Kontrola kombinací . Posloupnost je rozdělena na dílčí posloupnosti určité délky a zkoumají se řady složené z různých kombinací čísel.
  • Test sběratele kupónů . Nechť  je posloupnost délky n a dimenze m . Zkoumají se posloupnosti určité délky obsahující každé m -ciferné číslo.
  • Kontrola permutací . Tento test ověřuje rovnoměrnost rozložení znaků ve studované posloupnosti analýzou vzájemného uspořádání čísel v dílčích posloupnostech.
  • Zkontrolujte monotónnost . Používá se k určení uniformity na základě analýzy nerostoucích a neklesajících dílčích sekvencí.
  • Kontrola korelace . Tento test kontroluje vzájemnou nezávislost prvků sekvence.

Testy NIST

Rozdíl mezi těmito testy a ostatními moderními je otevřenost algoritmů. Mezi výhody patří také jednoznačná interpretace výsledků testu. Tabulka obecných vlastností:

Ne. Název testu Definovaná vada
jeden frekvenční test Příliš mnoho nul nebo jedniček
2 Kontrola kumulativních částek Příliš mnoho nul nebo jedniček na začátku sekvence
3 Kontrola "děr" v dílčích sekvencích Odchylka v rozložení posloupností jednotek
čtyři Kontrola "děr" Velký (malý) počet dílčích sekvencí nul a jedniček naznačuje, že kolísání bitového toku je příliš rychlé (pomalé)
5 Kontrola hodností matrik Odchylka rozložení řad matic od odpovídajícího rozložení pro skutečně náhodnou sekvenci, spojená s periodicitou sekvencí
6 Spektrální test Periodické vlastnosti posloupnosti
7 Kontrola nepřekrývajících se vzorů Neperiodické vzory jsou příliš časté
osm Kontrola protínajících se vzorů Příliš běžné m -bitové sekvence jedniček
9 Maurerův univerzální statistický test Stlačitelnost (pravidelnost) sekvence
deset Kontrola náhodných odchylek Odchylka od rozložení počtu výskytů podsekvencí určitého druhu
jedenáct Varianta kontroly náhodných odchylek Odchylka od rozložení počtu výskytů podsekvencí určitého druhu
12 Kontrola přibližné entropie Nerovnoměrné rozložení m -bitových slov. Malé hodnoty znamenají vysokou opakovatelnost
13 Kontrola série Nepravidelnost v distribuci m -bitových slov
čtrnáct Komprese pomocí Lempel-Ziv algoritmu Větší stlačitelnost než skutečná náhodná sekvence
patnáct Lineární složitost Odchylka od lineární distribuce složitosti pro konečnou délku podřetězce

Praktické aplikace

Spojením v informační bezpečnosti jsou generátory náhodných a pseudonáhodných čísel . V jistém smyslu se jedná o zásadní stavební kameny kryptografických algoritmů a protokolů. Protože se takové generátory používají v mnoha kryptografických problémech, například při vytváření náhodných parametrů a klíčů šifrovacích systémů, jsou požadavky na ně poměrně vysoké. Zejména jedním z kritérií pro absolutně libovolnou binární sekvenci získanou na výstupu generátoru je nemožnost ji předpovědět při absenci jakýchkoliv informací o datech dodávaných na vstup generátoru. Proto se v praxi provádějí statistické testy pro kontrolu náhodné povahy binární sekvence generované generátorem náhodných nebo pseudonáhodných čísel. Což zase umožňuje předem identifikovat generátory, které splňují požadavky konkrétního kryptografického problému.

Soutěž AES

Za účelem schválení nového standardu pokročilého šifrování uspořádal Národní institut pro standardy a technologie s podporou vlády USA soutěž, během níž bylo testováno 15 algoritmů žadatelů. Jedním z kritérií používaných při hodnocení algoritmů byla jejich vhodnost jako generátory náhodných čísel. Testování těchto generátorů pro tvorbu náhodných binárních sekvencí s dobrými statistickými vlastnostmi bylo provedeno pomocí sady statistických testů NIST .

Během prvního kola AES bylo testování provedeno se 128bitovými klíči. Pouze 9 algoritmů z 15 bylo schopno projít statistickými testy [10] .

Na základě výsledků prvního kola bylo vybráno 5 šifrovacích algoritmů jako finalisté AES: MARS , RC6 , Rijndael , Serpent a Twofish . Ve druhém kole soutěže AES byla hodnocena vhodnost těchto 5 algoritmů jako generátorů náhodných čísel na základě 192bitových a 256bitových klíčů. Statistické testy NIST trvaly několik měsíců, přičemž výpočty byly prováděny na mnoha pracovních stanicích Sun Ultra . Všechna data byla generována a zpracována online. Jako výsledek druhého kola se ukázalo, že každý z pěti finalistů generuje náhodnou binární sekvenci s dobrými statistickými vlastnostmi, a proto může být použit jako generátor pseudonáhodných čísel a je možné použít klíče o velikosti: 128 , 192 a 256 bitů [11] .

Viz také

Poznámky

  1. ↑ NIST Cryptographic Toolkit . Získáno 8. května 2010. Archivováno z originálu 17. srpna 2011.
  2. ↑ TestU01 . Datum přístupu: 8. května 2010. Archivováno z originálu 23. července 2010.
  3. ↑ Crypt-X Archivováno 22. září 2008 na Wayback Machine . Výzkumné centrum informační bezpečnosti.
  4. ↑ Projekt pLab (downlink) . Získáno 21. listopadu 2009. Archivováno z originálu 14. listopadu 2009. 
  5. ↑ Testovací sada DIEHARD Archivována 25. ledna 2016.
  6. ↑ Dieharder: A Random Number Test Suite . Získáno 8. května 2010. Archivováno z originálu 10. června 2010.
  7. ↑ ENT . Získáno 8. května 2010. Archivováno z originálu 15. května 2010.
  8. ↑ Donald E. Knuth. The Art of Computer Programming, Vol.2: Semi-Numerical Algorithms Archived 4. září 2008 na Wayback Machine / 3rd ed. Addison-Wesley, 1998
  9. ↑ Alfred Menezes et al. Handbook of Applied Cryptography Archived 7. března 2005 na Wayback Machine
  10. ↑ NIST IR 6390 Randomness Testing of Advanced Encryption Standard Candidate Algorithms Archived 6. listopadu 2010 na Wayback Machine 
  11. ↑ Testování náhodnosti NIST IR 6483 kandidátů finalistů standardu Advanced Encryption Archivováno 27. května 2010 na Wayback Machine 

Literatura

  • Donald E. Knuth . Kapitola 3. Náhodná čísla // Umění počítačového programování. - 3. vyd. - M .: Williams , 2000. - V. 2. Získané algoritmy. — 832 s. — ISBN 5-8459-0081-6 .
  • M. A. Ivanov, I. V. Čugunkov. Kapitola 4. Metodika hodnocení kvality generátorů PSS // Teorie, aplikace a hodnocení kvality generátorů pseudonáhodných sekvencí. - M. : KUDITS-OBRAZ, 2003. - 240 s. — ISBN 5-93378-056-1 .

Odkazy