Bezpieczny generator pseudolosowy

[dropcap]W[/dropcap]brew tytułowi nie będziemy się dziś skupiać na BHP generatora pseudolosowego ani też nie będziemy go pilnować, czy aby nie planuje gdzieś zamachu terrorystycznego.

Zamiast tego skupimy się na bezpieczeństwie rozumianym w sensie kryptograficznym.

Czym więc jest generator pseudolosowy bezpieczny kryptograficznie?

Jest to taki generator, który uniemożliwia odgadnięcie kolejnego wygenerowanego bitu na podstawie znajomości wielu poprzednich bitów, z prawdopodobieństwem dużo większym niż 50%.

Powyższa definicja jest pełna podstępnych sformułowań:

  • “wiele bitów” może oznaczać zarówno 10 jak i 1000000, prawda?
  • Prawdopodobieństwo “dużo większe niż 50%” może oznaczać zarówno 55% jak też 99.9%.

Tak to niestety wygląda w świecie algorytmów szyfrujących. Dużo tam “płynnych” pojęć, a same algorytmy są na tyle mocne, na ile mocna jest wiara naukowców w to, że pewne problemy obliczeniowe nie dadzą się rozwiązać w pewnym sensownym czasie. Oraz nasza wiara w ich wiarę.

No dobra. Przejdźmy nad tymi językowymi nieścisłościami do porządku dziennego, ponieważ i tak nic z tym teraz nie zrobimy. Spróbujmy zamiast tego przyjrzeć się jednemu z wielu znanych współcześnie algorytmów generujących pseudolosowy ciąg bitów, który jest bezpieczny kryptograficznie. Mowa o algorytmie Blum Blum Shub.

Startujemy od dwóch dużych (naprawdę dużych! czym większe, tym lepiej!) różnych liczb pierwszych. Istotne jest, aby obie te liczby były nie tylko duże, różne i pierwsze, ale również kongruentne do 3 modulo 4 (po naszemu: aby po podzieleniu przez 4 zwracały resztę 3).

Mnożymy te liczby przez siebie, wynik tego mnożenia zapisujemy pod literką M (“mnożenie” zaczyna się na “m”, więc łatwo zapamiętać).

Osobno wybieramy sobie – całkiem z czapy – dowolną liczbę całkowitą X większą od zera oraz mniejszą od M.

No i teraz zaczynamy generować pseudolosowe bity:

1. Podnosimy X do kwadratu, wynik dzielimy przez M, resztę z dzielenia zapamiętujemy jako X.
2. Wypluwamy na wyjściu ostatni (najmniej znaczący) bit X.
3. Przechodzimy do punktu 1, chyba że wygenerowaliśmy już wystarczająco dużo bitów.

Jak można łatwo zauważyć, algorytm jest bardzo mało wydajny. W każdym kroku wymaga mnożenia naprawdę wielkich liczb tylko po to, żeby wygenerować jeden bit na wyjściu.

To prawda. Algorytm Blum Blum Shub jest wolny. Ale za to jest to jeden z najprostszych algorytmów pseudolosowych bezpiecznych kryptograficznie. Przy odrobinie skupienia jest go w stanie zrozumieć nawet osoba nieposiadająca żadnego matematycznego wykształcenia (na przykład ja!).

Uważny Czytelnik być może zaniepokoił się w momencie, kiedy trzeba było wybrać początkowe X. Skoro należy to zrobić “z czapy”, to najlepiej skorzystać z jakiegoś generatora liczb pseudolosowych, prawda? A jeszcze lepiej, żeby był on kryptograficznie bezpieczny…

Jak człowiek nie spojrzy, tak dupa z tyłu.

Temat zerżnięty bezczelnie z blogu Johna D. Cooka, jednego z moich ulubionych blogerów – naukowców: https://www.johndcook.com/blog/2017/09/21/a-cryptographically-secure-random-number-generator/


Zapisz się
Powiadom o
guest
13 komentarzy
Inline Feedbacks
Zobacz wszystkie komentarze
13
0
Zapraszam do skomentowania wpisu.x
()
x