В учебных целях, я хочу взломать самый простой ГПСЧ.
Здесь могут помочь даже те, кто не знает про линейный конгруэнтный генератор или про гпсч в принципе, т.к. вопрос в недопонимании английского текста и немного математики.
Для вас вкратце: Есть такая штука как генератор псевдослучайных чисел. т.е. рандом, если проще. "Псевдослучайные" они потому что они не случайны, но похожи на таковые. Одна из реализаций такого генератора:
Xn+1=(aXn+c) mod m
Где Xn – это n-ый член последовательности. Переменные a, c и m – постоянные: a – множитель, c – инкремент, m – модуль. X0 – начальное значение.
Мои условия взлома:
1. Мы знаем, что генератор основан на линейном конгруэнтном методе.
2. Мы не знаем a, c и m.
3. Мы можем получить любые члены последовательности.
Задача: определить a,c,m (с большей вероятностью).
Несколько способов нашел в английском варианте. Мне нужен любой из них или другой, который я не знаю.
На
этом сайте решают это брутфорсом. Единственное, там дана не вся последовательность, а каждый второй член. Поэтому, насколько я понял, проделывать PowerMod не нужно. Вопросы по этому способу следующие:
1. Я правильно понял, что второй код реализован потому, что первый выдавал два результата, а нам нужен один?
2. Вопрос по модульной арифметике: Как получили, что c = X2 - ((X1 * a) % m) (в первом коде)?
3. Почему m < 10*M_START?
4. Что происходит во втором коде?
Вот
тут - Plumstead’s algorithm. А
здесь - алгоритм Дж. Марсальи Поясните пожалуйста, кто понял, с математической точки зрения.
Другие ссылки :
Modular arithmetic + division by multiplication + ...Why 1103515245 is used in rand?Cracking a linear congruential generatorDesign of Cryptographically Strong Generator By Tr... 
Средний
