Cryptopals zestaw 3 ćwiczenie 21

Kolejny krótki wpis bo i samo zadanie bardzo proste i nie wymagające od nas szczególnej wiedzy czy dłuższej chwili namysłu. Odstawiamy na razie na bok te wszystkie 'AESy’ i zajmiemy się generowaniem liczb pseudolosowych. Kiedy piszemy aplikacje zdarza się, że potrzebujemy wygenerować jakąś losową wartość.

Chyba większość osób uczących się programowania po raz pierwszy spotkała się z tym problemem, kiedy musieli napisać grę w której musimy zgadnąć o jakiej liczbie od 0 do n „pomyślał” sobie nasz program. Oczywiście nie możemy na stałe wpisać konkretnej wartości ponieważ taki program za każdym razem „wymyślałby” tą samą wartość i granie w taką grę więcej niż raz nie miała by sensu.

Oczywiście języki programowania dają nam możliwość generowania liczb pseudolosowych np. w C++ możemy użyć funkcji rand() (http://www.cplusplus.com/reference/cstdlib/rand/) a w Pythonie możemy użyć modułu random (https://docs.python.org/3/library/random.html).

Nazywam liczby generowane przez tego typu funkcja liczbami pseudolosowymi ponieważ pomimo tego, że na pierwszy rzut oka wyglądają jak by faktycznie były losowe to jednak po wygenerowaniu dostatecznie dużej ilości liczby zaczniemy dostrzegać powtarzający się wzór. W przypadku kiedy nasza aplikacja jest np. grą i chcemy wygenerować mapę poziomu albo ilość obrażeń zadanych przeciwnikowi nie ma potrzeby szukać innych rozwiązań. Kiedy jednak potrzebny jest nam element losowy w celu zabezpieczenia jakichś danych będziemy potrzebowali czegoś lepszego, ale o tym dlaczego przekonamy się w kolejnych zadaniach.

Jednym z popularnych algorytmów do generacji liczb losowych jest algorytm Mersenne Twister oznaczony jako MT19937 (https://pl.wikipedia.org/wiki/Mersenne_Twister). Wartość 19937 oznacza, że liczy generowane przez ten algorytm zaczną się powtarzać po wygenerowaniu 2^19937-1 wartości. Poniżej moja implementacja:

class MTRng(object):
    
    def __init__(self, seed = 0):
        self._gMTidx = 0
        self._gMT = [ 0 ] * 624
        self._gMT[0] = seed
        for idx in range(1, len(self._gMT)):
            self._gMT[idx] = ((self._gMT[idx-1]>>30)^self._gMT[idx-1]*
                              0x6c078965 + 1) & 0xffffffff
    
    def updateState(self, state):
        self._gMT = state
    
    def extractNumber(self):
        if self._gMTidx == 0:
            self._generateNumbers()
        
        tmp = self._gMT[self._gMTidx]
        tmp = (tmp ^ (tmp>>11))&0xffffffff
        tmp = (tmp ^ ((tmp<<7) & 0x9d2c5680))&0xffffffff
        tmp = (tmp ^ ((tmp<<15) & 0xefc60000))&0xffffffff
        tmp = (tmp ^ (tmp>>18))&0xffffffff
        self._gMTidx = (self._gMTidx+1)%len(self._gMT)
        return tmp
    
    def _generateNumbers(self):
        for idx in range(len(self._gMT)):
            tmp = self._gMT[idx]&0x80000000
            tmp |= self._gMT[(idx+1)%len(self._gMT)]&0x7fffffff
            self._gMT[idx] = self._gMT[(idx+397)%len(self._gMT)] ^ (tmp>>1)
            if tmp&0x1 != 0:
                self._gMT[idx] = self._gMT[idx] ^ 0x9908b0df

Całość dostępna na gitlabie: https://gitlab.com/akoltys/cryptopals .