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

Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) — это криптографически стойкий алогоритм генерации псевдослучайных последовательностей, с использованием сида. Идеи алгоритма были изложены Блюмом и Микали в 1984 году. Алгоритм был разработан на основе алгоритма генератора Шамира, предложенного Ади Шамиром годом ранее. Алгоритм отличается от предшественника более сильными требованиями к сложности вычисления выходной последовательности. В отличие от генератора Шамира выходом данного алгоритма являются биты, а не числа.

Основная идея алгоритма

Рассмотрим простейшую идею построения генератора псевдослучайных чисел: мы задаёмся некоторой начальной случайной последовательностью (Seed) и выбираем некоторый алгоритм шифрования. Далее на каждой итерации шифруя текущее состояния и выбирая из полученного результата набор битов, мы можем получать последовательность чисел, которая выглядит довольно случайным образом.

Алгоритм Блюма — Микали использует именно этот процесс, используя «хардкор-биты» (hard-core bit, hard-core predicate).

Понятие хардкор-бита

«Хардкор-битом»(предикатом) B для функции f называют некоторую функцию, такую, что:

1. Выходное значение B — 1 бит.
2. Для неё нет такого полиномиально-временного(Класс BPP — Bounded-error probabilistic polynomial) алгоритма, который может вычислить B(x) из f(x) с вероятностью отличной от 1/2.

Теорема Блюма - Микали

$S$ — Seed $n$ — длина аргумента функции $f$. Она же — длина $S$. $f$ - преобразование из $\{0,1\}^{n}$ в $\{0,1\}^{n}$ , а $B$ — из $\{0,1\}^{n}$ в {0,1} - сложный бит для $f$. $h_{i}=B(S_{i})$; $h_{i}$ — биты конечной генерируемуой последовательности. $S_{i}=f(S_{i-1})$; $S_{0}=S$. $(t,\varepsilon )$-псевдослучайность - свойство последовательности для которой выполнено $|P(A(B_{1}..B_{i})==B_{i}+1)-1/2|<\varepsilon$ $(t,\varepsilon )$-сложный бит - свойство функции $A$, для которой $|P(A(B_{1}..B_{i})==0)-1/2|<\varepsilon$, где $A()$ — время нахождения алгоритма криптоаналитиком за время $t$.

Определим $G_{BM}$ как следующий процесс: Возьмем некоторую случайную последовательность (seed). Если $B$ является $(t,\varepsilon )$-сложным битом, то $G_{BM}$ — $(t-m*TIME(f),\varepsilon *m)$-генератор псевдослучайных чисел. $TIME(f)$ - время вычисления функции $f$.

Теорема доказывается от противного; Предполагается, что существует алгоритм позволяющий найти $i+1$ элемент, зная $i$ предыдущих.

Атаки на алгоритм

Реализации данного алгоритма как правило опираются на сложность вычисления обратных функций в поле Галуа, например на сложности вычисления дискретного логарифма. Следовательно, для взлома этого алгоритма необходимо лишь уметь брать дискретный алгоритм за обозримое время. На настоящих реализациях компьютеров для правильно подобранных чисел - это очень ресурсоёмкая операция. Однако, аналогичный алгоритм на квантовом компьютере даёт выигрыш в скорости в квадрате, что делает взлом такого генератора весомо более реальным. Атака основана на одном из вариантов квантовых алгоритмов - подскоке амплитуды, более обобщенном варианте Алгоритма Гровера.

Примеры генераторов

Генератор Блюма — Блюма — Шуба

Основная статья: Алгоритм Блюма — Блюма — Шуба

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

Dlog generator

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

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

Генератор Калински

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

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

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

См. также

• Тест на следующий бит

Литература

• http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml
• http://www.csee.wvu.edu/~xinl/library/papers/comp/Blum_FOCS1982.pdf