Алгоритм Блюма — Микали

Два партнёра безопасно обменявшись секретной начальной последовательностью, получают общую случайную последовательность длиной во много раз большей, чем начальная последовательность.

Гольдвассер и Микали показали[3], что в предположении что определение квадратичных вычетов по модулю от составных чисел - вычислительно сложная задача, существует шифровальная схема, обладающая следующим свойством:
"Злоумышленник, зная алгоритм шифрования и имея зашифрованный текст не может получить никакой информации об оригинальном тексте."
Это свойство так же известно под названием принципа Керкгоффса.

Возьмём такие простые ${\displaystyle p}$ и ${\displaystyle q}$, что ${\displaystyle N=pq}$ — 1024-битное и ${\displaystyle p=q=3\ mod\ 4}$. Функция ${\displaystyle f(x)=x^{2}\ mod\ N}$. В качестве сложного бита берется функция, возвращающая наименьший значимый бит. ${\displaystyle B(x)}$ является таковым в допущении, что не существует алгоритма вычисления дискретного логарифма сложности лучше либо равной ${\displaystyle n^{2}}$.
Также было показано[4], что генератор остаётся асимптотически стойким, если для выходной последовательности выбирать не один, а несколько младших битов. Но стоит отметить, что генератор в такой модификации уже не будет соответствовать алгоритму Блюма-Микали.

Приведём некоторые численные оценки для BBS для двух вариантов атаки:
Допустим, требуется сгенерировать последовательность длиной ${\displaystyle 10^{7}}$, такую что ни один алгоритм не сможет отличить эту последовательность от истинно случайной за время ${\displaystyle 2^{80}}$ операций с вероятностью больше чем 1/100. Расчет показывает, что для генерации такой последовательности требуется зерно длиной ${\displaystyle n\geqslant 6800}$ бит. В случае, если требуется скомпрометировать генератор, т.е. найти зерно по выходной последовательности за те же времена с той же точностью, то защита от подобной атаки будет обеспечиваться всего при ${\displaystyle n\geqslant 1100}$ бит[4].

Пусть ${\displaystyle p}$ — 1024 битное простое число, а ${\displaystyle g}$ принадлежит ${\displaystyle \mathbb {Z} _{p}}$. Определим ${\displaystyle f:\{1,...,p-1\}}$ → ${\displaystyle \{1,...,p-1\}}$, как ${\displaystyle f(x)=g^{x}\ mod\ p}$.
Сложный бит
${\displaystyle B(x)=\left\{{\begin{matrix}0,&x<p/2\\1,&x\geqslant p/2\end{matrix}}\right.}$

B(x) является таковым в допущении, что не существует алгоритма вычисления дискретного логарифма c функцией сложности ${\displaystyle n^{3}}$ или лучше.

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

Пусть ${\displaystyle p}$ - простое число, такое что ${\displaystyle p=2\ mod\ 3}$. Рассмотрим кривую в ${\displaystyle F_{p}}$ x ${\displaystyle F_{p}}$ (поле Галуа) вида: ${\displaystyle y^{2}=x^{3}+c}$. Точки кривой ${\displaystyle (x,y)}$ вместе с точкой на бесконечности ${\displaystyle {\mathcal {O}}}$ образуют циклическую группу порядка ${\displaystyle p+1}$. Пусть ${\displaystyle Q}$ — генератор этой группы. ${\displaystyle P}$ Введём следующую функцию: ${\displaystyle \phi (P)=\left\{{\begin{matrix}y,&P=(x,y)\\p,&P={\mathcal {O}}\end{matrix}}\right.}$
Соответственно, функция, используемая в генераторе имеет вид: ${\displaystyle f(P)=\phi (P)*Q}$
Сложный бит генератора: ${\displaystyle B(P)=\left\{{\begin{matrix}1,&P=\phi (P)\geqslant (p+1)/2\\0,&P=\phi (P)<(p+1)/2\end{matrix}}\right.}$

Seed такого генератора - некоторая точка на кривой.