-<+>

I-<v>

Рис. 17-8. Сдвиговый регистр с нелинейной обратной связью (возможно небезопасный).

Рис. 17-9. 3-битовый сдвиговый регистр с нелинейной обратной связью.

На 8-й показан 3-битовый генератор со следующей обратной связью: новым битом является произведение первого и второго битов. Если его проинициализировать значением 110, то последовательность внутренних состояний будет следующей:

0 1 0 0 0 1 0 0 0 0 0 0

И так до бесконечности. Выходом является последовательность младших значащих битов :

0 1 1 0 1 0 0 0 0 0 0 0

Это не слишком полезно.

Может быть и хуже. Если начальное значение 100, то следующими состояниями являются 010, 001, а затем всегда 000. Если начальным значением является 111 , то оно будет повторяться всегда и с самого начала.

Была проделана определенная работа по вычислению линейной сложности произведения двух LFSR [1650, 726, 1364, 630, 658, 659]. Конструкция, включающая вычисление LFSR над полем нечетных характеристик [310] не является безопасной [842.].

17.7 Другие потоковые шифры

В литературе описывались и другие потоковые шифры. Вот некоторые из них. Генератор Плесса (Pless)

Этот генератор использует свойства J-K триггеров [1250]. Восемь LFSR управляют четырьмя J-K триггерами; каждый триггер нелинейно объединяет два LFSR. Чтобы избежать проблемы, что выход триггера определяет и источник, и значение следующего выходного бита, после тактирования четырех триггеров их в ы-ходы перемешиваются для получения окончательного потока ключей .

Этот алгоритм был криптоаналитически взломан с помощью вскрытия каждого триггера в отдельности

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

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

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

a*= ak-i © (a* v a*+i)

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

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

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

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

xt+i = bxt mod p

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

crypt(1)

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

Другие схемы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x,+1 = gx,- mod р