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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Основная идея алгоритма[править | править исходный текст]

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

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

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

  1. Количество выходных бит b_i полиномиально зависит от длины зерна (в силу конечной длины цикла алгоритма).
  2. Вычисление битов b_i просто в вычислении — сложность не более чем полиномиальная от длины зерна.
  3. Биты b_i непредсказываемы. При известном генераторе и b_1, ..., b_k, первые k бит последовательности, но не зная зерна, вычисление следующего бита b_{i + 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 предыдущих[2].

Применение[править | править исходный текст]

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

В системах с закрытым ключом[править | править исходный текст]

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

В системах с открытым ключом (асимметричное шифрование)[править | править исходный текст]

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


Примеры генераторов[править | править исходный текст]

Генератор Блюма — Блюма — Шуба(BBS)[править | править исходный текст]

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

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

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[5].

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

Примечания[править | править исходный текст]

  1. Adi Shamir On the generation of cryptographically strong pseudorandom sequences, 1983
  2. [Manuel Blum and Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864.
  3. S.Goldwasser and S.Micali, Probabilistic encryption and how to play mental poker keeping secret all partial information, Proc 14th ACM Symposium on Theory of Computing, 1982, pp. 365-377
  4. 1 2 Andrey Sidorenko and Berry Schoenmakers, State Recovery Attacks on Pseudorandom Generators, 2005.
  5. O.Goldreich. Foundations of Cryprography. Basic Tools. Cambridge University Press, Cambridge, United Kingdom, 2001.
  6. Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr — Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction. http://arxiv.org/abs/1012.1776

См. также[править | править исходный текст]


Литература[править | править исходный текст]