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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

Возьмём такие простые ${\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}}$ .
Также было показано , что генератор остаётся асимптотически стойким, если для выходной последовательности выбирать не один, а несколько младших битов. Но стоит отметить, что генератор в такой модификации уже не будет соответствовать алгоритму Блюма-Микали.

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

Dlog generator

Пусть ${\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.}$

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

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

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

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

Примечания

См. также

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

Литература

• B. S. Kaliski. Elliptic Curves and Cryptography: A Pseudorandom Bit Generator and Other Tools. PhD thesis, MIT, Cambridge, MA, USA, 1988.