Как вскрыть линейный конгруэнтный генератор псевдослучайных чисел?

Question

[NickMN]

В учебных целях, я хочу взломать самый простой ГПСЧ.

Здесь могут помочь даже те, кто не знает про линейный конгруэнтный генератор или про гпсч в принципе, т.к. вопрос в недопонимании английского текста и немного математики.

Для вас вкратце: Есть такая штука как генератор псевдослучайных чисел. т.е. рандом, если проще. "Псевдослучайные" они потому что они не случайны, но похожи на таковые. Одна из реализаций такого генератора:

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 generator
Design of Cryptographically Strong Generator By Tr...

Comments

[Василий]

ещё описание таких генераторов, есть во втором томе кнута

[NickMN]

Василий: я читал, там нет взлома

[Василий]

NickMN: ну да там про взлом нет, по этому и не в ответах, зато ещё одно описание, которое может пригодится кому-то ещё.

[NickMN]

Василий: Собственно, во многих книгах по криптографии описываются генераторы, впрочем, не парьтесь. Я без претензий.

Answer 1

[Deerenaros]

В брутфорсе всё очень просто, мы генирируем последовательность за последовательностью и смотрим на ту, которую хотим взломать. Если всё совпадает - значит взломали. Каждый второй член сделано для усложнения.

Плумстед не пони точно, но похоже они выводят через мат. ожидание похожую последовательность. То есть по идеи он очень быстрый, но в пределе неточный, то беж неправильный. Посему не вникал.

А Марсальи, точнее парни, что на него ссылаются просто решают систему сравнений, насколько я понял. А сам Марсальи что-то доказал там об этих генераторах, что позволило составить саму систему.

Всё это беглый взгляд, но в целом линейные генераторы с точки зрения криптографии - очень плохая идея. Дело не столько во взломе, сколько в том, что они не очень хорошо имитируют случайную последовательность, да и линейность сама по себе оставляет много свободы для творчества криптоаналитиков. А по поводу простоты реализации - тут можно поспорить, ибо целочисленный остаток от деления не самая простая операция, есть куда интереснее генераторы на нелинейной бинарной логике.

Comments

[NickMN]

Спасибо, что хоть отозвались. Я думаю сделаю всё полным перебором, однако, всё-таки интересно что происходит в предложенном полном переборе именно во втором коде, где происходит какая-то модульная инверсия. Интересно понять, что за мат. алгоритмы во второй и третей ссылке. Но это уже не важно, я выбрал брутфорс. Вы считаете LFSR-генераторы (программные) проще взломать? Честно говоря, их взломом не интересовался ещё.

[Deerenaros]

NickMN: Всегда пожалуйста. Ясное дело, проще. Другое дело, что такая ересь очень просто реализуется и очень быстро работает, но криптографический стойкой её назвать сложно.

Впрочем, криптоанализ забавная штука. Вот поломали ГОСТ наш, ну было 240 сложных бит, стало 170... То, что это где-то пара жизней вселенных и несколько тонн открытого текста криптоаналитики предпочитают умалчивать.

Хотя здесь, конечно, немного другая история. Вся эта муть в принципе расписывается в энное число линейных уравнений, а системы за кубическое время мы пока не разучились. Впрочем, используется это дело весьма активно, но не столько в криптографии, сколько в околорандомных вычислениях.

А алгоритмы надо читать и разбирать. Было время, когда надо было разбираться, но сейчас вроде как время пошло, а вспоминать тяжко. В целом, роадмап я вам наметил, даже если он неверный - освоитесь и разберётесь. Марсальи кажется самым адекватным, если его утверждения действительно верные, то разобравшись в его утверждениях (там ссылка приводится) решить полученную систему - не вопрос.

[NickMN]

Deerenaros: Спасибо)