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

Question

[daniilkening]

Здраствуйте в учебных целях хочу узнать возможно ли взломать такой генератор? В языке программирования Pawno есть функция рандом , которая основана на lcg. Коэффициент m по умолчанию в этом языке программирования равен 2 в 31 степени. Сколько нужно входных значений чтобы вскрыть этот генератор?

Нашел код который вроде как должен решить эту проблему. Но не совсем понятно как он работает...
https://github.com/ctf-x/ctfx-problems-2016/tree/m...

Answer 1

[Михаил]

Что вы подразумеваете под "вскрыть"? Научиться предсказывать следующее значение? ГПСЧ - в принципе детерминированная функция, предыдущее значение однозначно определяет следующее (рекуррентная функция).

Если же речь идет об определении коэффициентов a и c, то это делается элементарно: делаете seed=0, следующее значение генератора равно c. Делаете seed = 1 - следующее значение генератора равно (a+c) % m, откуда, при известном m и c вычисляется a.

Comments

[daniilkening]

Да , предсказать следующее значение.

[Михаил]

daniilkening, отредактировал ответ.

[daniilkening]

Михаил, спасибо за информацию. Если я узнал все коэффициенты то как посчитать следующие значения? Если пользоваться формулой то такой? Ss+1 = ((a*S+c) mod m ) mod 37 . Но если так считать то это значит что после каждого к примеру значения 34 всегда будет идти значение 7 (к примеру) . Или я неправильно же понимаю?

[daniilkening]

Михаил, вот сайт где похожий вопрос на мой https://www.reddit.com/r/math/comments/5njsys/crac... , но там говорят что я не знаю фактических чисел , знаю только по модулю. Еще слышал что языки программирования могут отбрасывать последние 16 бит . Я не уверен что данный вопрос легкий , так как я не компетентен в программировании и коде.