17.9 Сложностно-теоретический подход к проектированию потоковых шифров

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

Генератор псевдослучайных чисел Шамира

Эди Шамир использовал в качестве генератора псевдослучайных чисел алгоритм RSA [1417]. Хотя Шамир показал, что предсказание выхода генератора псевдослучайных чисел равносильно взлому RSA, потенциальное смещение выхода была продемонстрирована в [1401, 200].

Генератор Blum-Micali

Безопасность этого генератора определяется трудностью вычисления дискретных логарифмов [200]. Пусть g - простое число, а p - еще одно простое число. Ключ x₀ начинает процесс:

x_i+1 = g^x_i mod p

Выходом генератора является 1, если x_i < (p - 1)/2, и 0 в противном случае.

Если p достаточно велико, чтобы вычисление дискретных логарифмов mod p стало физически невозможным, то этот генератор безопасен. Дополнительные теоретические результаты можно найти в [1627, 986, 985, 1237, 896, 799].

RSA

Этот генератор RSA [35, 36] является модификацией [200]. Начальные параметры - модуль N, произведение двух больших простых чисел p и q, и целое число e, относительно простое с (p-1)(q-1), а также стартовое случайное число x₀, меньшее N.

x_i+1 = x^e_i mod N

Выход генератора представляет собой младший значащий бит x_i. Безопасность этого генератора опирается на сложность вскрытия RSA. Если N достаточно велико, то генератор безопасен. Дополнительная теория приведена в [1569, 1570, 1571, 30, 354].

Blum, Blum, and Shub

Простейший и наиболее эффективный генератор, использующий сложностно-теоретический подход, в честь своих авторов называется Blum, Blum, and Shub. Мы сократим его название до BBS, хотя иногда его называют генератором с квадратичным остатком [193].

Теория генератора BBS использует квадратичные остатки по модулю n (см. раздел 11.3). Вот как он работает.

Сначала найдем два простых числа, p и q, которые конгруэнтны 3 modulo 4. Произведение этих чисел, n, является целым числом Блюма (Blum). Выберем другое случайное целое число x, взаимно простое с n. Вычислим

x₀ = x² mod n

Это стартовое число генератора.

Теперь можно начать вычислять биты. i-ым псевдослучайным битом является младший значащий бит x_i, где

x_i = x_i-1² mod n

Самым интригующим свойством этого генератора является то, что для получения i-го бита не нужно вычислять предыдущие i-1 биты. Если вам известны p и q, вы можете вычислить i-ый бит непосредственно.

b_i - это младший значащий бит x_i, где x_i =

Это свойство означает, что вы можете использовать этот криптографически сильный генератор псевдослучайных чисел в качестве потоковой криптосистемы для файла с произвольным доступом.

Безопасность этой схемы основана на сложности разложения n на множители. Можно опубликовать n, так что кто угодно может генерировать биты с помощью генератора. Однако пока криптоаналитик не сможет разложить n на множители, он никогда не сможет предсказать выход генератора - ни даже утверждать что-нибудь вроде: "Следующий бит с вероятностью 51 процент будет единицей".

Более того, генератор BBS непредсказуем в левом направлении и непредсказуем в правом направлении. Это означает, что получив последовательность, выданную генератором, криптоаналитик не сможет предсказать ни следующий, ни предыдущий бит последовательности. Это вызвано не безопасностью, основанной на каком-то никому не понятном сложном генераторе битов, а математикой разложения n на множители.

Этот алгоритм медленен, но есть способы его ускорить. Оказывается, что в качестве псевдослучайных битов можно использовать несколько каждого x_i. В соответствии с [1569, 1570, 1571, 35, 36] если n - длина x_i, можно использовать log₂n младших значащих битов x_i. Генератор BBS сравнительно медленный и не подходит для потоковых шифров. Однако для высоконадежных приложений, таких как генерация ключей, этот генератор лучше многих других.