Pull to refresh

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

Reading time1 min
Views76K

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

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



Алгоритм

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


Закладка



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

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



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

te=(hr)e=hre=(he)r=gr=s′(mod p).

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

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

В оригинале P — кривая, G, H — две точки. Операция возведения в степень по модулю заменена на умножение
Tags:
Hubs:
Total votes 155: ↑116 and ↓39+77
Comments50

Articles