Bezpieczny generator pseudolosowy

https://xpil.eu/60p

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/

https://xpil.eu/60p

13 komentarzy

  1. 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.

    1. To, o czym piszesz, to oczywiście działanie jak najbardziej poprawne z puntu widzenia programisty. Mówiąc bardziej ogólnie, ziarno (seed) do generatora pseudolosowego należy wziąć ze „zbiornika z entropią”. Czym więcej entropii, tym mniejsza szansa na to, że ktoś będzie w stanie odtworzyć naszą sekwencję pseudolosową (i tym samym narobić nam syfu). I jest to prawda niezależna od tego, w jakim języku piszesz program.

      Niemniej jednak to wszystko jest „z boku” względem tematu głównego mojego wpisu, który traktuje zagadnienie od strony stricte matematycznej. Generator pseudolosowy, zanim się go zaimplementuje w komputerze, trzeba najpierw dobrze zaprojektować i przemyśleć od strony formalnej. Większość z nich to „urządzenia” oparte na dość skomplikowanych obliczeniach. Wybrałem akurat Blum Blum Shub ze względu na jego prostotę.

      A także dlatego, że pisał o nim John, z którego blogu bezczelnie zerżnąłem temat 🙂

      1. Ale w sumie sam generator też może bazować na zegarze wewnętrznym i po kilku prostych obliczeniach wypluwać liczbę. W sumie to nie wiem, dlaczego tak nie jest, przecież to się samo nasuwa. Gdy programowałem w Assemblerze na Atari to z tego właśnie korzystałem. Był tam jakiś bardzo szybki jednobajtowy (chyba?) zegar (o ile dobrze pamiętam, służył do synchronizacji obrazu), który przyrastał co 1/50 sekundy i w sumie jedyne co potrzebowałem, do odczytać go i dopasować do potrzebnego mi zakresu. A jako, że w Assebmlerze i tak bazowałem głównie na bajtach i słowach (nie używałem liczb zmiennoprzecinkowych), to całość była banalnie prosta.

        Ty siedzisz w temacie głębiej, to może wiesz dlaczego ludzie piszą skomplikowane generatory zamiast po prostu przekształcać jakiś wewnętrzny zegar albo automatycznie używać go jako ziarna – wtedy nie ma bolca, żeby dało się przewidzieć kolejną liczbę.

        1. Dlatego na przykład, że wewnętrzne zegary potrafią mieć bardzo niedużą rozdzielczość czasową. Poczytaj sobie o tym, jak swego czasu wykorzystano tę słabość do złamania algorytmu tasującego w pokerze on-line: http://xpil.eu/hqs – wydawałoby się, że milisekunda to bardzo krótko, ale jeżeli czas przechowywany jest w rejestrze 32-bitowym, to już dupa blada, bo ilość możliwych potasowań nagle spada o kilkadziesiąt rzędów wielkości i łatwo jest stwierdzić, jak talia jest potasowana. Dlatego oprócz czasu do „zbiornika” z entropią wrzuca się też inne śmieci: temperaturę procesora / karty grafiki, prędkość obrotową wentylatora, ilość ruchów myszą, uderzeń w klawisze i tak dalej. Jakiekolwiek urządzenia zamieniające sygnały analogowe na cyfrowe pomagają „nazbierać” entropii do generowania lepszej losowości.

          1. Oczywiście, że tak. Zegar był tylko przykładem, ale faktycznie warto dorzucać inne elementy. Pytanie brzmi, dlaczego generatory tego nie robią?
            Bo jestem pewien, że nie robią, inaczej nie byłoby niniejszego wpisu.

            1. Ależ robią! Linuksy mają nawet biblioteki systemowe do generowania / przechowywania entropii. Ale, jak już wcześniej nadmieniłem, to wszystko rozważania praktyczne, a mój wpis dotyczy wyłącznie strony teoretycznej.

              1. Ale jednak nie wszystkie i tu jest problem.

                Pisałem kiedyś jakąś prostą układankę w Dev-Cpp, w której generator musiałem inicjować i robiłem to jakaś stałą liczbą. I ZAWSZE klocki układały mi się na kolejnych planszach w ten sam sposób. Ergo – generator nie korzystał z żadnego zegara czy innej entropii.

                Dopiero musiałem użyć wspomnianego wyżej srand(timeGetTime()); żeby gra faktycznie za każdym razem losowo układała klocki.

                Wiem, że Ty teoretyzujesz, ale moje pytanie jest jak najbardziej praktyczne: Dlaczego są generatory, które robią właśnie całą masę obliczeń i są przewidywalne zamiast skorzystać z pomocy sprzętowych?

                Tutaj nawiążę do któregoś Twojego wcześniejszego wpisu i losowaniu szczęśliwców w pracy do premii (czy jakoś tak). Pisałeś, że były głosy sprzeciwu, że jeden wygrał dwa razy a inny ani razu i do dupy z takim generatorem. Dlatego robiłeś w nim poprawki. TO i przypomina jakiś bardzo stary artykuł z Bajtka (chyba), gdzie porównywano różne generatory i był taki test, że na wykresie na osi X był jakiś zakres liczb a na Y – ile razy została wylosowana. Potem odpalano taki generator i okazało się, że większość dba o to, żeby liczby były losowane w miarę równomiernie. Chyba tylko jeden miał coś takiego jak odwrócony dzwon Gaussa, gdzie faworyzowane były liczby graniczne.

                I dlatego się zastanawiam, dlaczego ludzie się męczą i programują jakieś skomplikowane algorytmy, które koniec końców są bardziej pseudo niż losowe, mając co dyspozycji sprzętową pomoc w postaci różnych zegarów, portów i innych czujników. Przecież nawet bardzo proste procesory mają nie tylko zegar czasu rzeczywistego, ale szybkie zegary służące do synchronizacji różnych podzespołów.

                1. Wydaje mi się, że końcem końców wybór metody generowania (pseudo-)losowości zależy od tego, ile na tym da się zarobić (lub stracić). Czym większe pieniądze wchodzą w grę, tym bardziej ostrożnie (i solidnie) programiści będą podchodzić do zagadnienia.

                  Każdy generator pseudolosowy, nieważne, skomplikowany czy nie, będzie generował tę samą sekwencję dla tej samej wartości ziarna. Dlatego trzeba „dorzucać” nowe ziarno do algorytmu od czasu do czasu, żeby „połamać” przewidywalność sekwencji. Porządne generatory robią to porządnie, a byle jakie – wiadomo. Ilość dostęnego ziarna jest tożsama z wielkością puli entropii.

                  Jeżeli timeGetTime() jest „wąskie” (a często jest), to nawet jeżeli będziesz się do niego odwyływał co milisekundę, żeby „zresetować” generator, nadal będziesz generował kiepskiej jakości losowość.

                  Co gorsza, nawet jeżeli Tobie, jako programiście, będzie się wydawało, że dostajesz ładne, losowe ciągi, da się zapuścić kilka prostych testów (na przykład testy z serii Die Hard: https://en.wikipedia.org/wiki/Diehard_tests) które pokażą, że losowość kuleje, chociaż nie widać tego gołym okiem.

                2. A jeszcze, odpowiadając na Twoje pytanie: programiści „męczą się” ze skomplikowanymi algorytmami pseudolosowymi zamiast korzystać wyłącznie ze źródeł faktycznie losowych, ponieważ ilość dostępnej entropii jest znikoma w porównaniu z zapotrzebowaniem na losowość.

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

    1. Wbrew pozorom to wcale nie takie trudne, jak by się mogło na pierwszy rzut oka wydawać. Jeżeli nie masz nic lepszego do roboty, daj znać czego nie rozumiesz, postaram się wytłumaczyć.

      1. Dziekuje serdecznie za wspanialomyslna propozycje, pozostane jednak w blogiej ignorancji. Posiadam umiejetnosc porozumiewania sie w kilku innych jezykach, wobec tego jezyk programowania pozwole sobie odpuscic.

        1. Dowcip polega na tym, że idee tu opisywane nie mają nic wspólnego z jakimkolwiek językiem programowania. Zarówno losowość jak i entropia są pojęciami związanymi ze światem jako takim, żadne programowanie komputerów tu nie jest konieczne (acz oczywiście na jakimś tam etapie okazuje się być bardzo pomocne).

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.