Теория
По нескольким подряд идущим выходам LCG можно восстановить все параметры и предсказывать будущее. Ключ — разности: \(t_n = x_{n+1} - x_n \bmod m\). Из рекурренции следует \(t_{n+1} \equiv a \cdot t_n \pmod m\), поэтому \(a = t_2 \cdot t_1^{-1} \bmod m\), где обратный элемент существует, если \(t_1\) и \(m\) взаимно просты, а затем \(c = x_2 - a \cdot x_1 \bmod m\).
Если модуль неизвестен, его находит метод Стерна: каждая тройка разностей даёт величину \(t_{n+2}t_n - t_{n+1}^2\), делящуюся на \(m\), — модуль равен их наибольшему общему делителю. Именно поэтому LCG нельзя использовать для секретов: четыре–шесть выходов — и генератор вскрыт.
Важно: против CSPRNG этот приём бессилен — их выходы не связаны простым линейным соотношением. Сравните: MT вскрывается по 624 выходам, а ChaCha20 не поддаётся вовсе.
Пример с решением
- Условие. Выходы glibc-генератора: 1103527590, 377401575, 662824084, 1147902781. Найдите a, c и следующее число (модуль \(2^{31}\)).
- Формула. \(a = t_2 \cdot t_1^{-1} \bmod m\), \(c = x_2 - a \cdot x_1 \bmod m\).
- Подстановка. \(t_1 = 1421357233\), \(t_2 = 285422509\), обе разности нечётны — обратный элемент существует.
- Вычисление. \(a = 1103515245\), \(c = 12345\).
- Ответ. Параметры glibc rand восстановлены; следующее число — 2035015474 (проверьте в калькуляторе). Секреты такому генератору доверять нельзя.
Главное
- Четыре–шесть выходов вскрывают LCG полностью.
- Метод Стерна восстанавливает и неизвестный модуль.
- CSPRNG так не вскрыть — в этом их ценность.