Ciągi losowe, są niezbędnym elementem wielu algorytmów kryptograficznych. Są one wykorzystywane na przykład w szyfrowaniu strumieniowym i metodzie one-time-pad, przy podpisach cyfrowych oraz protokołach kryptograficznych.

Losowym ciągiem może być na przykład, ciąg bitów generowanych poprzez rzucanie monetą: wyrzucenie reszki daje 1, orła zaś 0. Trzeba też założyć, że moneta jest dobrze wyważona, co oznacza, że otrzymanie orła w jednym rzucie jest tak samo prawdopodobne jak wyrzucenie reszki.

Generator liczb losowych może utrzymywać specjalny licznik, który liczy, ile jest jeszcze losowych bitów w generatorze. Implementacja takiego licznika jest jednak bardzo trudna. Dodatkową cechą generatora powinno być to, że nawet znając kod generatora i odczytując z niego kolejne, tworzone liczby losowe, nie powinno się dać przewidzieć jaka będzie następna liczba.

Dotychczas nie ma dostępnych na rynku i tanich efektywnych urządzeń generujących losowe ciągi. Decydującym powodem jest to, że tanio i szybko można uzyskać tzw. ciągi pseudolosowe za pomocą specjalnych algorytmów. Ciągi pseudolosowe mają wszystkie własności ciągów losowych, ale jednocześnie mogą być wygenerowane w deterministyczny sposób. Jedynym losowym elementem takiego ciągu jest zarodek. Ciąg pseudolosowy jest tworzony tak, że i-ty element (b_i) jest wyznaczony przez pewien deterministyczny algorytm z zarodka x, indeksu i oraz wartości b₁, b₂, ..., b_i-1. Zarodek jest zwykle stosunkowo krótkim ciągiem, więc można go wygenerować takimi metodami, jak poprzez mierzenie odstępów czasu pomiędzy uderzeniami palców w klawiaturę. Z drugiej strony musi on być na tyle długi, by wykluczyć możliwość odtworzenia zarodka poprzez przeglądanie wszystkich zarodków i ciągów przez nie generowanych.

Ciągi pseudolosowe stosowane w kryptografii, nie powinny być rozróżnialne od prawdziwych losowych ciągów przy użyciu żadnych praktycznie dostępnych metod. Ciągi te powinny być również nieprzewidywalne, co oznacza, że bez znajomości zarodka x nie da się w praktyce obliczyć elementu ciągu b_i, znając elementy b₁, ..., b_i-1[3, 21].

Generatory ciągów pseudolosowych

Linear Feedback Shift Register (LFSR) jest zbudowany z dwóch części: rejestru przesuwającego oraz ciągu odczepów (pomiędzy niektórymi bitami rejestru i bramką XOR nie ma połączenia). Rejestr przesuwający może być przedstawiony jako ciąg bitów. Pojawienie się bitów na wyjściu rejestru przesuwającego wyznaczane jest przez impulsy, które powodują, że wszystkie bity w rejestrze są przesuwane o jedną pozycję w prawo i na wyjściu LFSR pojawia się najmniej znaczący bit. Nowy, najbardziej znaczący bit jest obliczany przez sumowanie modulo 2 innych bitów w rejestrze, zgodnie z ciągiem odczepów.

Rysunek 5.17. Rejestr przesuwający z liniowym sprzężeniem zwrotnym (LFSR) [32]

Zarodek ciągu stanowi konfiguracja połączeń pomiędzy bitami rejestru a węzłem realizującym XOR oraz początkowy ciąg bitów zapisany w rejestrze przesuwającym. LFSR generuje bity bardzo szybko, jeśli jest zaimplementowany poprzez hardware. Niestety, kryptograficzne własności ciągów generowanych przez LFSR są bardzo słabe [21, 32].

Generator Blum-Blum-Shub (BBS) nosi nazwę od nazwisk trzech jego wynalazców. Niekiedy bywa on też nazywany generatorem reszt kwadratowych. Podstawą teoretyczną jego działania jest obliczanie reszt kwadratowych modulo n. Generator ten działa w taki sposób, że należy wziąć dwie liczby pierwsze p i q, które są kongruentne względem 3 modulo 4. Iloczyn tych liczb n=p^.q jest liczbą całkowitą Bluma. Następnie należy wybrać inną losową liczbę całkowitą x, względnie pierwszą z n, i obliczyć:

Bezpieczeństwo tego algorytmu opiera się na trudności faktoryzacji liczby n. Dla danego ciągu wytworzonego przez BBS kryptoanalitycy nie mogą przewidzieć wartości kolejnego bitu w ciągu lub wartości bitu poprzedniego.

Generator BBS jest względnie powolny i w związku z tym niezbyt użyteczny dla szyfrów strumieniowych, jednak przy zastosowaniach wymagających silnego zabezpieczenia, takich jak wytwarzanie kluczy, jest on najlepszy [32].