Amerykański instytut standardyzacyjny NIST określił szczegółowe wymagania odnośnie liczb losowych stosowanych do celów kryptograficznych. Dokument NIST SP 800-22 określa 16 testów statystycznych, których spełnienie pozwala na zaakceptowanie danego ciągu liczb losowych do celów kryptograficznych. Najczęściej zestaw testów służy do badania siły generatorów liczb pseudolosowych, programowych oraz sprzętowych.
Dla programistów pragnących przetestować własną implementację przydatny będzie zestaw programów sts-1.5.tar, napisanych i udostępnionych publicznie przez NIST. Zestaw ten nie jest zbyt przyjazny w użytkowaniu, więc poniżej przedstawiamy krótki przewodnik korzystania z niego.
Po ściągnięciu i skompilowaniu (pod uniksami make) uzyskujemy program assess, który jest interfejsem do wszystkich dostępnych testów. Załóżmy, że mamy plik test zawierający 102400 bajtów z generatora, który chcemy przetestować. Opisana poniżej procedura wykorzystuje tylko dwa testy: częstości zer i jedynek (frequency) oraz częstości zer i jedynek w podblokach (block-frequency).
Niektóre testy, jak block-frequency wymagają podania dodatkowych parametrów, w tym wypadku wielkości bloku. Aby poznać ich znaczenie należy zapoznać się z opisami poszczególnych testów w dokumencie 800-22, gdzie znajdują się także informacje kiedy i jakich parametrów używać. W przypadku block-frequency ustalamy arbitralnie wielkość bloku na 8 bitów. Warto dodać, że program assess operuje przede wszystkim na bitach, więc długości podawane w programie należy przeliczać na bity.
Dane wejściowe:
- plik test
- długość 102400 bajty, czyli 819200 bity
- testy do wykonania
- frequency
- block-frequency
Procedura:
- Uruchamiamy ./assess 819200 (argument określa liczbę bitów do testowania). Program jest oparty o kolejne menu i ma bardzo surowy interfejs użytkownika.
- Wybieramy 00 (opcja Input File). Program posiada kilkanaście wbudowanych generatorów ciągów, które można analizować, natomiast opcja 00 pozwala wczytać do analizy dane użytkownika.
- Podajemy nazwę pliku test.
- Kolejne menu pozwala wybrać testy, które chcemy zastosować do naszych danych. Wybieramy 0, ponieważ chcemy wybrać je samodzielnie.
- Wpisujemy 1100000000000000 aby wybrać testy frequency i block-frequency.
- Następne pytanie dotyczy parametru testu block-frequency, czyli długości bloku. Wybieramy 8 bitów.
- Pytanie o ilość generowanych ciągów bitowych w przypadku danych z pliku nie ma znaczenia, wpisujemy 1.
- Następne pytanie określa format danych wejściowych, tzn. czy będą to zera i jedynki w postaci tekstowej, czy plik binarny. Wybieramy 1, rozpoczynając tym samym testy.
- Program kończy pracę.
Rezultaty znajdziemy w podkatalogach experiments/AlgorithmTesting/frequency i block-frequency, w pliku stats. Plik ten zawiera wartości pośrednie charakterystyczne dla danego testu oraz informację o jego ostatecznym wyniku (tzw. p-value) wraz z informacją, czy test został zakończony pomyślnie czy nie. Wynik SUCCESS oznacza, że dane posiadają własności losowe, wynik FAILED - że nie są one losowe.
Bibliografia
- NIST SP 800-22, ,,A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications'', http://csrc.nist.gov/rng/rng2.html