WikiDer > Алгоритм Блюма – Микали

Blum–Micali algorithm

В Алгоритм Блюма – Микали это криптографически безопасный генератор псевдослучайных чисел. Алгоритм обеспечивает безопасность из-за сложности вычислений. дискретные логарифмы.[1]

Позволять быть нечетным простым числом, и пусть быть первобытный корень по модулю . Позволять быть семенем, и пусть

.

В -й выход алгоритма равен 1, если . В противном случае на выходе будет 0. Это эквивалентно использованию одного бита как ваше случайное число. Было показано, что кусочки может использоваться, если решение задачи дискретного журнала невозможно даже для показателей с всего лишь биты.[2]

Чтобы этот генератор был безопасным, простое число должен быть достаточно большим, чтобы вычисление дискретных логарифмов по модулю невозможно.[1] Чтобы быть более точным, любой метод, который предсказывает сгенерированные числа, приведет к алгоритму, который решает проблему дискретного логарифмирования для этого простого числа.[3]

Существует статья, в которой обсуждаются возможные примеры квантовой перманентной компромиссной атаки на конструкцию Блюма – Микали. Эти атаки показывают, как предыдущая атака на генератор Блюма – Микали может быть расширена на всю конструкцию Блюма – Микали, включая Блюм Блюм Шуб и Калиски генераторы.[4]

Рекомендации

  1. ^ а б Брюс Шнайер, Прикладная криптография: протоколы, алгоритмы и исходный код на C, страницы 416-417, Wiley; 2-е издание (18 октября 1996 г.), ISBN 0471117099
  2. ^ Дженнаро, Росарио (2004). «Улучшенный псевдослучайный генератор на основе проблемы дискретного логарифмирования». Журнал криптологии. 18 (2): 91–110. Дои:10.1007 / s00145-004-0215-у. ISSN 0933-2790. S2CID 18063426.
  3. ^ Блюм, Мануэль; Микали, Сильвио (1984). «Как сгенерировать криптографически стойкие последовательности псевдослучайных битов» (PDF). SIAM Журнал по вычислениям. 13 (4): 850–864. Дои:10.1137/0213053. S2CID 7008910. Архивировано из оригинал (PDF) на 24 февраля 2015 г.
  4. ^ Guedes, Elloá B .; Франсиско Маркос де Ассис; Бернардо Лула-младший (2010). «Примеры обобщенной квантовой перманентной компромиссной атаки на конструкцию Блюм-Микали». arXiv:1012.1776 [cs.IT].

внешняя ссылка