[1356]. К тому же, объединение J-K триггеров слабо криптографически; генераторы такого типа не устоят перед корреляционным вскрытием [1451].

Генератор на базе клеточного автомата

В [1608, 1609], Стив Вольфрам (Steve Wolfram) предложил использовать в качестве генератора псевдослучайных чисел одномерный клеточный автомат. Рассмотрение клеточного автомата не является предметом этой книги, но генератор Вольврама состоит из одномерного массива битов a1, a2, a3, ... , ak, ... , an и функции обновления:

ak= ak-1 е (ak v ak+1)

Бит извлекается из одного из значений ak, реально все равно какого.

Генератор ведет себя как вполне случайный . Однако для этих генераторов существует успешное вскрытие с известным открытым текстом [1052]. Это вскрытие выполнимо на PC со значениями n вплоть до 500 битов. Кроме того, Пол Барделл (Paul Bardell) доказал, что выход клеточного автомата может быть также сгенерир о-ван с помощью сдвигового регистра с линейной обратной связью той же длины и, следовательно, не дает бол ь-шей безопасности [83].

Генератор 1/p

Этот генератор был предложен и подвергнут криптоанализу в [193]. Если внутреннее состояние генератора в момент времени t равно xt, то

xt+1 = bxt mod p

Выходом генератора является младший значащий бит xt div где div - это целочисленное деление с усечением. Для максимального периода константы b и p должны быть выбраны так, что p - простое число, а b - примитивный корень mod p. К сожалению, этот генератор не безопасен. (Заметим, что для b = 2 FCSR целыми числами связи выдает последовательность, обратную данной .)

crypt(1)

Оригинальный алгоритм шифрования UNIX, crypt(1), представляет собой потоковый шифр, использующий те же идеи, что и Энигма. Это 256-элементный, однороторный подстановочный шифр с отражателем . И ротор, и отражатель получаются из ключа. Этот алгоритм намного проще, чем немецкая Энигма времен второй мировой войны, и квалифицированному криптоаналитику несложно его взломать [1576, 1299]. Для вскрытия файлов, зашифрованных crypt(1), можно использовать свободно доступную программу UNIX, называемую Crypt Breakers Workbench (CBW, инструмент взломщика шифров).

Другие схемы

Еще один генератор основан на проблеме рюкзака (см. раздел 19.2) [1363]. CRYPTO-LEGGO небезопасен [301]. Джоан Дэймен (Joan Daemen) разработала SubStream, Jam и StepRightUp [402], но они слишком новы, чтобы их комментировать. Множество других алгоритмов описано в литературе, но еще больше хранится в се к-рете и встроено в аппаратуру.

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

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

Согласно Райнеру Рюппелу существует четыре различных подхода к проектированию потоковых шифров [1360, 1362]:

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

- Информационно-теоретический подход. Пытается сохранить открытый текст в тайне от криптоаналитика. Независимо от того, как много действий выполнит криптоаналитик, он никогда не получит однозначного решения.

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

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

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

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

Со временем этот подход привел к появлению набора критериев проектирования потоковых шифров [1432, 99, 1357, 1249]. Они рассматривались Рюппелом в [1362], где он подробно приводит теоретические основы этих критериев.

- Длинный период без повторений.

- Критерий линейной сложности - большая линейная сложность , линейный профиль сложности, локальная линейная сложность и т.д.

- Статистические критерии, например, идеальные к-мерные распределения.

- Путаница - каждый бит потока ключей должен быть сложным преобразованием всех или большинства битов ключа.

- Диффузия - избыточность в подструктурах должна рассеиваться, приводя к более "размазанной" стат и-стике.

- Критерии нелинейности для логических функций, такие как отсутствие корреляции m-го порядка, расстояние до линейных функций, лавинный критерий, и т.д.

Этот перечень критериев проектирования не уникален для потоковых шифров, разработанных с помощью системно-теоретического подхода, он справедлив для всех потоковых шифров . Это справедливо и для всех блочных шифров. Особенностью системно-теоретического подхода является то, что потоковые шифры неп о-средственно разрабатываются, чтобы удовлетворить этим критериям .

Главной проблемой таких криптосистем является невозможность доказать их безопасность, никогда не было доказано, что эти критерии проектирования необходимы или достаточны для безопасности . Генератор потока ключей может удовлетворять всем правилам разработки, но тем не менее оказаться небезопасным . Другой может оказаться безопасным. Этом процессе все еще остается что-то магическое .

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

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

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

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

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

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

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

х,+1 = g,- mod ,p

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

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

896, 799].

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

xi+1 = xei mod N

Выход генератора представляет собой младший значащий бит xi. Безопасность этого генератора опирается на сложность вскрытия 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. Вычислим

x0 = x2 mod n

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

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

xi = xi-12 mod n

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

bi - это младший значащий бит xi, где xi = x0(2i )mod(( -1)(q

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

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

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

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

17.10 Другие подходы к проектированию потоковых шифров

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