Генератор BBS. 
Криптографические методы защиты информации

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

Сперва выбирается число Блюма п = pq, где р и q простые числа, сравнимые с 3 по модулю 4. Далее выбирается случайное число х, которое взаимно просто с п. Начальным состоянием генератора является жо = х² (mod п). Тогда случайным битом 7* с номером г будет младший бит числа х, где.

Замечательным свойством данного генератора является то, что для вычисления г-го выходного бита 7, не нужно вычислять предыдущие i -1 бит. При известных р и q знак числа Xi можно вычислить по формуле:

Данное свойство позволяет использовать BBS-генератор в качестве потоковой криптосистемы для шифрования файлов с произвольным доступом.

Устойчивость данной системы к взлому (непредсказуемость знаков выхода влево и вправо) основана на сложности разложения п на множители и свойствах чисел Блюма.

Упражнение 6.4.5. Пусть п = pq, p, q — простые числа, сравнимые с 3 по модулю 4. Докажите следующие утверждения.

^|0См. L.Blum, M. BIum, M. Shub A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, v. 15, n. 2, 1986, pp. 364−383.

• 1. У каждого квадратичного вычета по модулю п имеется ровно 4 квадратных корпя, один из которых также является квадратом.
• 2. Существует ровно 4 вычета а е таких, что а² = a (mod п). Найдите эти вычеты.

Следует отметить, что криптографические свойства BBSгенератора основаны па тех же идеях, что лежат в основе схемы асимметричного шифрования Рабина-Вильямса, подробно описываемой нами позднее в разделе 10.2.