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

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

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

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

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

Придумывая алгоритм, Блюм и Микали выдвинули три требования к выходной последовательности:

1. Количество выходных битов $b_{i}$ должно полиномиально зависеть от длины зерна (в силу конечной длины цикла алгоритма).
2. Получение битов $b_{i}$ должно быть простым в вычислительном плане — количество действий должно быть ограничено сверху некоторой полиномиальной функцией от длины зерна.
3. Биты $b_{i}$ должны быть непредсказываемы. При известном генераторе и известных первых $k$ битах последовательности $b_{1},...,b_{k}$, но не зная зерна, определение следующего бита $b_{k+1}$ c вероятностью, отличной от 50%, должно являться вычислительно сложной задачей. То есть, такое вычисление не должно выполняться за полиномиальное от длины зерна количество операций.

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

«Хардкор-битом» (предикатом) 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$ предыдущих.

Применение

Генераторы, основанные на данном алгоритме находят применение в системах как с закрытым, так и с открытым ключом.

В системах с закрытым ключом

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

В системах с открытым ключом (асимметричное шифрование)

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

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

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

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

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

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

Dlog generator

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

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

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

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

Пусть $p$ - простое число, такое что $p=2\ mod\ 3$. Рассмотрим кривую в $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 такого генератора - некоторая точка на кривой.

Уязвимости алгоритма

Доказано, что проблема, состоящая в том, чтобы различить истинную случайную последовательность и последовательность сгенерированную согласно схеме Блюма-Микали может быть сведена к задаче обращения функции $f$.

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

См. также

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

Литература

• B. S. Kaliski. Elliptic Curves and Cryptography: A Pseudorandom Bit Generator and Other Tools. PhD thesis, MIT, Cambridge, MA, USA, 1988.
• https://web.archive.org/web/20080216164459/http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml
• https://web.archive.org/web/20150224041435/http://www.csee.wvu.edu/~xinl/library/papers/comp/Blum_FOCS1982.pdf