9346692691

sprawdzi się. Dodatkowo w kryptografii metoda generacji binarnych sekwencji pseudolosowych powinna być bezpieczna tzn. bez poznania ziarna nie ma praktycznie możliwości odgadnięcia wyglądu ciągu.

1.4 Bezpieczne generatory pseudolosowe

Przykładem algorytmu,który spełnia testy statystyczne ale nie jest bezpieczny może być liniowy generator kongruentny o przepisie na kolejną liczbę pseu-dolosową x_n, takim że:

x_n = ax_n-1 + b mod m, n > 1

a, b, m są stałymi definiującymi działania procedury. Choć idealnie sprawdza się on w większości zastosowań numerycznych okazuję się jednak, że można poznać dalszą sekwencję liczb analizując tylko wynik jego działania czyli nie znając ziarna xq, a nawet stałych generatora. W tym momencie należy zdefiniować co się kryje pod pojęciem bezpieczyny kryptograficznie generator liczb pseudolosowch. Lecz na wstępie parę definicji pomocniczych:

Definition 2. Mówimy, że generator bitów pseudolosowych przechodzi wszystkie statystyczne testy o wielomianowym czasie wykonania jeśli nie istnieje algorytm o takowym czasie, który potrafiłby prawidłowo rozróżnić wynik działania generatora od prawdziwie losowej sekwencji o tej samej długości z prawdopodobieństwie znacząco większym od 1/2.

Definition 3. Generator pseudolosowy przechodzi test następnego bitu jeśli nie istnieje algorytm o wielomianowym czasie wykonania, który potrafiłby przewidzieć (l + 1) bit wyjściowego ciągu długości s, stworzonego za pomocą danych wejściowych długości l.

Powiązanie między powyższymi definicjami na pierwszy rzut oka wydają się małe lecz w istocie okazuje się iż generator bitów pseudlosowych przechodzi test następnego bitu wtedy i tylko wtedy gdy przejdzie testy statystyczne o wielomianowym czasie.

Nadszedł wreszcie czas aby powiedzieć o czym mówi tytuł tego podrozdziału: Definition 4. Generatorem kryptograficznie bezpiecznym nazywamy taki, który przechodzi test następnego bitu

Innymi słowy znając sekwencję dowolnej długości uzyskaną za pomocą tych generatorów nie jesteśmy w stanie przewidzieć ich dalszego zachowania. Wszystko to pod warunkiem, że za nierozwiązywalne uznamy pewne zagadnienia teorii liczb. Choć rzeczą oczywistą jest, że chcemy używać algorytmu spełniającego defnicję (4) to w praktyce oznacza to zbyt małą jego wydajność. Dlatego mimo wielu zastrzeżeń pod względem bezpieczństwa omawianego powyżej wykorzystuje się takie procedury jak np. LFSR, które są wystarczająco szybkie np. dla DESa. Te bezpieczne z kolei znajdują zastosowanie w jednorazowych operacjach, takich jak generacji kluczy w RSA, gdzie zależy nam na nie powtarzalności wyniku.

Po tym dość krótkim omówieniu najważniejszych zagadnień przechodzimy do szczegółowego opisu bardzo ważnego procesu jakim jest testowanie generatorów.