Русский
Русский
English
Статистика
Реклама

Blum-Blum-Shub generator и его применение

Введение

В настоящее время случайные числа используются в различных областях науки. Например, для моделирования различных реальных процессов зачастую нужно учитывать не только поведение исследуемой величины, но и влияние различных непредсказуемых явлений. Кроме того, в некоторых методах анализа данных, полученных в результате эксперимента, также используются случайные числа. В теории игр случайность также играет большую роль. Ну и конечно в криптографии. Многие алгоритмы шифрования или электронной подписи используют случайные числа.

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

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

Один из таких генераторов - генератор BBS (Blum-Blum-Shub generator) - и будет рассмотрен в этой статье.

Основные определения

Для описания генератора BBS понадобятся следующие понятия:

  • Случайное число - число, представляющее собой реализацию случайной величины

  • Детерминированный алгоритм алгоритм, который возвращает те же выходные значения при тех же входных значениях

  • Псевдослучайное число число, полученное детерминированным алгоритмом, используемое в качестве случайного числа

  • Генератор псевдослучайных бит (ГПСБ) - детерминированный алгоритм, который получает на вход бинарную последовательность длины n и выдает на выходе бинарную последовательность длины l(n), которая кажется случайной. Входное значение ГПСБ называется начальным вектором, а выход называется псевдослучайной последовательностью бит

    Поясним, что же такое кажется случайной. В данном случае это означает, что последовательность, сгенерированная ГПСБ, не является случайной, однако она неотличима от истинно случайной последовательности такой же длины. Ниже приведем два определения криптографической безопасности генератора, а затем покажем, что они эквивалентны.

  • Целое число x из мультипликативной группы по модулю n называется квадратичным вычетом по модулю n, если существует такое y, что y^2 \equiv x \ mod \ n. В противном случае x - квадратичный невычет по модулю n.

  • Простое число p такое, что p \equiv 3 \ mod \ 4, называется простым числом Блюма.

Следующие 2 определения являются эквивалентными:

  • Говорят, что ГПСБ проходит все полиномиальные по времени статистические тесты, и поэтому может рассматриваться как криптографически безопасный ГПСБ, если никакой полиномиальный по времени алгоритм не может различить выходную последовательность генератора и истинно случайную последовательность с вероятностью превышающей 1/2.

  • Говорят, ГПСБ проходит битовый тест, если нет полиномиального по времени алгоритма, который на основе первых rl(n)1 бит выходной последовательности sможет предсказать (r+1)-ый бит s с вероятностью большей1/2.

Алгоритм работы генератора BBS (Blum-Blum-Shub generator)

  1. Генерируем два различных простых больших числа Блюма p и q

  2. n := p \cdot q

  3. Генерируем случайное число s \in Z_n^* (мультипликативная группа по модулю n)

  4. x_0 := s^2 \ mod \ n

  5. Последовательность определяется как x_i := x_{i-1}^2 \ mod \ nи b_i := x_i \ mod \ 2

  6. Последовательность на выходе: b_0, b_1, b_2, ...

Приведу пример работы данного алгоритма:

Пусть n = p \cdot q = 7 \cdot 19 = 133 и s = 100. Тогда мы имеем x_0 = 100^2 \equiv 25 \ mod \ 133 . Получаем последовательность: x_1 = 25^2 \equiv 93 \ mod \ 133и b_1 = 93 \equiv 1 \ mod \ 2, x_2 = 93^2 \equiv 4 \ mod \ 133и b_2 = 4 \equiv 0 \ mod \ 2, x_3 = 4^2 = 16 \ mod \ 133 и b_3 = 16 \equiv 0 \ mod \ 2, x_4 = 16^2 \equiv 123 \ mod \ 133 и b_4 = 123 \equiv 1 \ mod \ 2

На выходе получили последовательность 1,0,0,1.

Последовательность, полученная на выходе генератора BBS, является периодичной, причем период равен \lambda (\lambda (x)), где \lambda(n) = \{\min{m}: a^m \equiv 1 \mod n \} - функция Кармайкла.

Интересной особенностью генератора BBS является то, что при знании разложения числа n на множители он допускает эффективное прямое определение любого бита последовательности. Равенство

позволяет рационально вычислить i-ый элемент последовательности, если даны x_0, n, \lambda(n).

Безопасность генератора BBS

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

Криптографическая стойкость генератора BBS основана на проблеме определения квадратичного вычета, которая формулируется следующим образом:

  • Задача определения квадратичного вычета состоит в том, чтобы решить является лиx \in Z_n^* квадратичным вычетом или нет.

  • A(n,x)- алгоритм, который решает эту задачу, выдает 1 тогда и только тогда, когда x является квадратичным вычетом и 0 в противном случае.

Решение данной задачи является вычислительно сложной задачей.

В своей статье изобретатели генератора доказали, что ГПСБ BBS является непредсказуемым (криптографически стойким) генератором.

Применение

В статье Выборновой Ю.Д приведено исследование средней скорости работы различных реализаций генератора BBS. Было получено, что скорость работы данного генератора во много раз ниже скорости работы современных симметричных алгоритмов блочного шифрования. Генератор BBS сравнивался с алгоритмами блочного шифрования, потому что алгоритмы блочного шифрования используются для построения криптографически стойких генераторов псевдослучайных последовательностей

Из этого следует, что данный алгоритм может использоваться только для генерации данных, если необходима непредсказуемость и криптографическая стойкость, а скорость генерации не имеет не имеет значения. А именно: для генерации ключей в асимметричных системах, таких как RSA, в качестве генератора имитовставки (средство обеспечения имитозащиты в протоколах аутентификации с доверяющими друг другу участниками), генератора ключей для имитовставки, а также в некоторых реализациях криптографических протоколов аутентификации и шифрования. Однако, стоит заметить, что низкая скорость не всегда является недостатком. В криптографии существуют задачи, в которых специально используются медленные алгоритмы. Одной из таких задач является генерация ключа на основе пароля.

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

Функция генерации ключа на основе пароля (Password-Based Key Derivation Function, PBKDF) это детерминированный алгоритм, который применяется для получения криптографической ключевой информации из какого-либо секретного значения. Таким образом, такая функция позволяет из легко запоминающегося пароля пользователя получить криптографически стойкий ключ заданной длины, называемый мастер-ключом.

В основе алгоритма PBKDF лежит псевдослучайная функция. Обозначим ее PRF. На вход подается число С, которое определяет, сколько раз нужно запустить псевдослучайную функцию. Также на вход подается пароль Р , соль S - не секретная строка символов, уникальная для каждого пароля, и желаемая длина мастер-ключа MK_Length.

Обозначим мастер-ключ MK , тогда MK = PBKDF_{(PRF, C)}(P, S, MK \_ Length)

Благодаря применению уникальной соли для каждого пользователя, даже если несколько пользователей при регистрации ввели одинаковый пароль, значение ключа в базе будет разным, и злоумышленник не сможет догадаться, у каких пользователей пароли совпадают. То есть основное назначение соли - сделать возможной генерацию большого количества ключей для каждого пароля при фиксированном C. Для каждого пароля число возможных ключей составит 2^{Salt \_ Length}, где Salt_Length - длина соли в битах.

Разработанный алгоритм генерации ключа на основе пароля имеет следующий вид:

Холостыми назовем первые Dummy _ Bits _ Number бит, порожденных генератором BBS, которые не будут учитываться при создании мастер-ключа. Полезными назовем те биты, порожденные генератором BBS, которые будут принимать участие в генерации ключа. Мастер-ключ будем генерировать блоками. Общее количество блоков обозначимa.

Создадим два временных массива T и U и для каждого блока i выполним следующее: обнулим ячейку T_i, в U_0запишем результат конкатенации соли S и номера блока i, переведенного в бинарный вид функцией Binary(). Затем будем запускать BBS генератор и складывать результат со значением T_iпока не обнулится счетчик итераций C. Мастер-ключ является результатом конкатенации всех блоков. Последний блок заменяется на первые r бит этого блока.

Заключение

В заключение хочется подчеркнуть, что данный генератор является надежным, и в настоящее время используется в задачах, где стойкость алгоритма важнее высокой скорости выполнения. Однако, генератор BBS будет стойким только до тех пор, пока не будет изобретен алгоритм, позволяющий быстро проводить факторизацию чисел.

Источники

  • Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 800-57. NIST. Retrieved 19 August 2013.

  • Pascal Junod, Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator, August 1999

  • Слеповичев И.И.; ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНХ ЧИСЕЛ, 2017

  • A. C. Yao. Theory and application of trapdoor functions. In Proc. 23rd IEEE Symp. on Foundations of Comp. Science, pages 8091, Chicago, 1982. IEEE.

  • M. Blum and S. Micali. How to generate cryptographically strong se- quences of pseudo-random bits. SIAM J. Computing, 13(4):850863, November 1984.

  • Lenore Blum, Manuel Blum, and Michael Shub. Comparison of two pseudo-random number generators. In R. L. Rivest, A. Sherman, and D. Chaum, editors, Proc. CRYPTO 82, pages 6178, New York, 1983. Plenum Press.

  • A. J. (Alfred J.) Menezes, Paul C. Van Oorschot, and Scott A. Van- stone. Handbook of applied cryptography. The CRC Press series on discrete mathematics and its applications. CRC Press, 2000 N.W. Cor- porate Blvd., Boca Raton, FL 33431-9868, USA, 1997.

  • E. Kranakis. Primality and Cryptography. Wiley-Teubner Series in Computer Science, 1986.

  • S. Goldwasser and S. Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In Proc. 14th ACM Symp. on Theory of Computing, pages 365377, San Francisco, 1982. ACM.

  • Выборнова, Ю.Д. Реализация генератора Blum-Blum-Shub и исследование его основных характеристик / Ю.Д. Выборнова // IN SITU.

  • Брассар, Дж. Современная криптология / Дж. Брассар. Москва: Полимед, 1999. 107 с.

  • Ю.Д. Выборнова, Разработка функции генерации ключа на основе пароля в качестве приложения генератора Blum-Blum-Shub, Новая техника, 2017

  • Turan, M. Recommendation for password-based key derivation / M. Turan, E. Barker, W. Burr, L. Chen NIST, 2010. 18 p.

Источник: habr.com
К списку статей
Опубликовано: 23.12.2020 20:04:15
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Информационная безопасность

Криптография

Генератор

Безопасность

Псевдослучайность

Генерация ключей

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru