Bezpieczny generator pseudolosowy

O bardzo wolnej, ale za to bardzo bezpiecznej metodzie generowania bitów pseudolosowych

Wbrew 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/

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

13 komentarzy do "Bezpieczny generator pseudolosowy"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
Andrzej
Gość

Ja mam następujący sposób (nie wiem, czy efektywny i bezpieczny – nie jestem specjalistą), zresztą nie ja to wymyśliłem, tylko gdzieś o tym czytałem.

Mianowicie w wielu językach programowania generator trzeba zainicjować – trzeba ustawić posiew czy jakoś tak. W innych nie jest to wymagane, ale jest mimo wszystko jest taka możliwość. Więc przed generowaniem każdej liczby ustawiam go liczbą pobraną z zegara np. w C++: srand(timeGetTime());

Co o tym sądzisz? Tutaj podobno NIE DA się przewidzieć ŻADNEJ liczby, bo za każdym razem losowane są od nowa. Nie wiem tylko, jak tu jest z szybkością. Podobno inicjalizacja generatora jest bardzo czasochłonna.

Kasia
Gość

Kiedy widze dyskusje taka jak ta strasznie zaluje, ze nie znam tego jezyka, ale zakladam ze rozmawiacie o mega ciekawych rzeczach 😉

wpDiscuz