Как АНБ внедрило закладку в генератор псевдослучайных чисел

По материалам этой статьи.

Генератор «от АНБ» основан на эллиптических кривых. Не надо их бояться, тем более что суть алгоритма и закладки можно описать более простыми словами. Будет не сложнее, чем понять как работает протокол Диффи — Хеллмана

Алгоритм

(перевод этого материала)

1. Предлагает нам взять простое число p и два числа g,h которые оба меньше, чем p.
2. Говорит нам, что его состояние в любой момент времени можно описать положительным числом s меньшим, чем p
3. Чтобы выполнить один шаг алгоритма, нужно установить r=g^s(mod p), s′=g^r(mod p)
4. Текущее состояние установить в s′
5. Выход алгоритма t=h^r(mod p )

Закладка

Закладка — секретное число e такое, что g=h^e (mod p).
АНБ, которое разработало алгоритм, выбрало числа g h путём генерации случайных h и e и установив g=h^e (mod p). а потом опубликовав g, h, p но оставив у себя e.

Как пользоваться закладкой

Допустим, АНБ стало известно одно из состояний t генератора. Это может быть, например IV симметричного алгоритма, который передается по открытому каналу. Или соль.
А теперь фокус покус

t^e=(h^r)^e=h^re=(h^e)^r=g^r=s′(mod p).

а s′ — это следующее состояние алгоритма. Что и требовалось доказать.

Такие пироги.

В оригинале P — кривая, G, H — две точки. Операция возведения в степень по модулю заменена на умножение