Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) — это криптографически стойкий алогоритм генерации псевдослучайных последовательностей, с использованием зерна (Random seed). Идеи алгоритма были изложены Блюмом и Микали в 1984 году. Алгоритм был разработан на основе алгоритма генератора Шамира, предложенного Ади Шамиром годом ранее[1]. Алгоритм отличается от предшественника более сильными требованиями к сложности вычисления выходной последовательности. В отличие от генератора Шамира выходом данного алгоритма являются биты, а не числа.
Рассмотрим простейшую идею построения генератора псевдослучайных чисел: мы задаёмся некоторой начальной случайной последовательностью (зерно) и выбираем некоторый алгоритм шифрования. Далее на каждой итерации шифруя текущее состояния и выбирая из полученного результата набор битов, мы можем получать последовательность чисел, которая выглядит довольно случайным образом.
Алгоритм Блюма — Микали использует именно этот процесс, используя «хардкор-биты» (hard-core bit, hard-core predicate).
Придумывая алгоритм, Блюм и Микали выдвинули три требования к выходной последовательности:
«Хардкор-битом» (предикатом) B для функции f называют некоторую функцию, такую, что:
— Seed
— длина аргумента функции
. Она же — длина
.
- преобразование из
в
, а
— из
в {0,1} - сложный бит для
.
;
— биты конечной генерируемуой последовательности.
;
.
-псевдослучайность - свойство последовательности для которой выполнено
-сложный бит - свойство функции
, для которой
,
где
— алгоритм, найденный криптоаналитиком за время
.
Определим
как следующий процесс:
Возьмем некоторую случайную последовательность (seed).
Если
является
-сложным битом, то
—
-генератор псевдослучайных чисел.
- время вычисления функции
.
Теорема доказывается от противного; Предполагается, что существует алгоритм позволяющий найти
элемент, зная
предыдущих[2].
Генераторы, основанные на данном алгоритме находят применение в системах как с закрытым, так и с открытым ключом.
Два партнера безопасно обменявшись секретной начальной последовательности, получают общую случайную последовательность длиной в во много раз большей, чем начальная последовательность.
Гольдвассер и Микали показали[3], что в предположении что определение квадратичных вычетов по модулю от составных чисел - вычислительно сложная задача, существует шифровальная схема, обладающая следующим свойством:
"Злоумышленник, зная алгоритм шифрования и имея зашифрованный текст не может получить никакой информации об оригинальном тексте."
Это свойство так же известно под названием принципа Керкгоффса.
Возмём такие простые
и
, что
— 1024-битное и
. Функция
. В качестве сложного бита берется функция, возвращающая наименьший значимый бит.
является таковым в допущении, что не существует алгоритма вычисления дискретного логарифма сложности лучше либо равной
.
Также было показано[4], что генератор остаётся асимптотически стойким, если для выходной последовательности выбирать не один, а несколько младших битов. Но стоит отметить, что генератор в такой модификации уже не будет соответствовать алгоритму Блюма-Микали.
Приведём некоторые численные оценки для BBS для двух вариантов атаки:
Допустим, требуется сгенерировать последовательность длиной
, такую что ни один алгоритм не сможет отличить эту последовательность от истинно случайной за время
операций с вероятностью больше чем 1/100. Расчет показывает, что для генерации такой последовательности требуется зерно длиной
бит. В случае, если требуется скомпрометировать генератор, т.е. найти зерно по выходной последовательности за те же времена с той же точностью, то защита от подобной атаки будет обеспечиваться всего при
бит[4].
Пусть
— 1024 битное простое число, а
принадлежит
. Определим
→
, как
.
Сложный бит
B(x) является таковым в допущении, что не существует алгоритма вычисления дискретного логарифма c функцией сложности
или лучше.
Криптостойкость вышеприведённых генераторов базировалась на сложности нахождения дискретного логарифма. Генератор Калински использует идею эллиптических кривых.
Пусть
- простое число, такое что
. Рассмотрим кривую в
x
(поле Галуа) вида:
.
Точки кривой
вместе с точкой на бесконечности
образуют циклическую группу порядка
. Пусть
— генератор этой группы.
Введём следующую функцию:
Соответственно, функция, используемая в генераторе имеет вид:
Сложный бит генератора:
Seed такого генератора - некоторая точка на кривой.
Доказано, что проблема, состоящая в том, чтобы различить истинную случайную последовательность и последовательность сгенерированную согласно схеме Блюма-Микали может быть сведена к задаче обращения функции
[5].
Реализации данного алгоритма, как правило, опираются на сложность вычисления обратных функций, например на сложности вычисления дискретного логарифма. Следовательно, для взлома этого алгоритма необходимо лишь уметь брать дискретный логарифм за обозримое время. На настоящих реализациях компьютеров для правильно подобранных чисел - это очень ресурсоёмкая операция. Однако, аналогичный алгоритм на квантовом компьютере даёт выигрыш в скорости в квадрате, что делает взлом такого генератора весомо более реальным. Атака основана на одном из вариантов квантовых алгоритмов - подскоке амплитуды, более обобщенном варианте Алгоритма Гровера[6].
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .