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

Действительность намного светлее. Упомянутые предостережения верны, только если различные ключи з а-висят друг от друга. Если все используемые ключи независимы, то сложность взлома последовательности алг о-ритмов по крайней мере не меньше, чем сложность взлома первого из применяемых алгоритмов [1033]. Если второй алгоритм чувствителен к вскрытию с выбранным открытым текстом, то первый алгоритм может обле г-чить это вскрытие и при последовательном использовании сделать второй алгоритм чувствительным к вскр ы-тию с известным открытым текстом . Такое возможное облегчение вскрытия не ограничивается только алгори т-мами шифрования: если вы позволите кому-то другому определить любой из алгоритмов, делающих что-то с вашим сообщением до шифрования, стоит удостовериться, что ваше шифрование устойчиво по отношению к вскрытию с выбранным открытым текстом . (Обратите внимание, что наиболее часто используемым алгоритмом для сжатия и оцифровки речи до модемных скоростей, применяемым перед любым алгоритмом шифрования, является CELP, разработанный NSA.)

Это можно сформулировать и иначе: При использовании вскрытия с выбранным открытым текстом посл е-довательность шифров взломать не легче, чем любой из шифров последовательности [858]. Ряд результатов показал, что последовательное шифрование взломать по крайней мере не легче, чем самый сильный из шифров последовательности, но в основе этих результатов лежат некоторые несформулированные предположения [528]. Только если алгоритмы коммутативны , как в случае каскадных потоковых шифров (или блочных шифров в р е-жиме OFB), надежность их последовательности не меньше, чем у сильнейшего из используемых алгоритмов .

Если Алиса и Боб не доверяют алгоритмам друг друга , они могут использовать их последовательно . Для потоковых алгоритмов их порядок не имеет значения . При использовании блочных алгоритмов Алиса может сн а-чала использовать алгоритм A, а затем алгоритм B. Боб, который больше доверяет алгоритму B, может использовать алгоритм B перед алгоритмом A. Между алгоритмами они могут вставить хороший потоковый шифр. Это не причинит вреда и может значительно повысить безопасность .

Не забудьте, что ключи для каждого алгоритма последовательности должны быть независимыми . Если алгоритм A использует 64-битовый ключ, а алгоритм B - 128-битовый ключ, то получившаяся последовательность должна использовать 192-битовый ключ. При использовании зависимых ключей у пессимистов гораздо больше шансов оказаться правыми.

15.8 Объединение нескольких блочных алгоритмов

Вот другой способ объединить несколько блочных алгоритмов, безопасность которого гарантировано будет по крайней мере не меньше, чем безопасность обоих алгоритмов . Для двух алгоритмов (и двух независимых ключей):

(1)Генерируется строка случайных битов R того же размера, что и сообщение М.

(2)R шифруется первым алгоритмом.

(3)М © R шифруется вторым алгоритмом.

(4)Шифротекст сообщения является объединением результатов этапов (2) и (3).

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

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

Глава 16

Генераторы псевдослучайных последовательностей и потоковые шифры

16.1 Линейные конгруэнтные генераторы

Линейными конгруэнтными генераторами являются генераторы следующей формы Хя = (аХя-1 + b) mod m

в которых Хя - это я-ый член последовательности, а Хя-1 - предыдущий член последовательности. Переменные a, b и m - постоянные: а - множитель, b - инкремент, и m - модуль. Ключом, или затравкой, служит значение X0.

Период такого генератора не больше, чем m. Если a, b и m выбраны правильно, то генератор будет генератором с максимальным периодом (иногда называемым максимальной длиной), и его период будет равен m. (Например, b должно быть взаимно простым с m.) Подробное описание выбора констант для получения макс и-мального периода можно найти в [863, 942]. Еще одной хорошей статьей по линейным конгруэнтным генераторам и их теории является [1446].

В 15-й, взятой из [1272,], перечисляются хорошие константы линейных конгруэнтных генераторов . Все они обеспечивают генераторы с максимальным периодом и, что даже более важно, удовлетворяют спектральному тесту на случайность для размерностей 2, 3, 4, 5 и 6 [385, 863]. Таблица организована по максимальному произведению, которое не вызывает переполнения в слове указанной длины .

Преимуществом линейных конгруэнтных генераторов является их быстрота за счет малого количества оп е-раций на бит.

К несчастью линейные конгруэнтные генераторы нельзя использовать в криптографии, так как они предск а-зуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом (Jim Reeds) [1294, 1295, 1296], а затем Джоан Бояр (Joan Boyar) [1251]. Ей удалось также вскрыть квадратичные генераторы :

Хя = (аХя-12 + bXn-1 + c) mod m

и кубические генераторы:

Хя = (аХя-13 + bXn-12 + c Хя-1+ d) mod m

Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального ген е-ратора [923, 899, 900]. Были взломаны и усеченные линейные конгруэнтные генераторы [581, 705, 580], и усеченные линейные конгруэнтные генераторы с неизвестными параметрами [1500, 212]. Таким образом была доказана бесполезность конгруэнтных генераторов для криптографии.

Табл. 16-1.

Константы для линейных конгруэнтных генераторов

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

Объединение линейных конгруэнтных генераторов

Был предпринят ряд попыток объединения линейных конгруэнтных генераторов [1595, 941]. Криптографическая безопасность полученных результатов не повышается, но они обладают более длинными периодами и лучшими характеристиками в некоторых статистических тестах . Для 32-битовых компьютеров можно использовать следующий генератор [941]:

static long sl = 1 ; /* "long" должно быть 32-битовым целым. */ static long s2 = 1 ; #define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if (s<0) s+=m ;

/* MODMIJLT(a,b,c,nl,s) рассчитывает s*b mod m при условии, что m=a*b+c и 0 <= c < m. */

/* combinedLCG возвращает действительное псевдослучайное значение в диапазоне

*(0,1). Она объединяет линейные конгруэнтные генераторы с периодами

*231-85 и 231-249, и ее период равен произведению этих двух простых чисел. */

double combinedLCG ( void ) {

long q ; long z ;

MODMULT ( 53668, 40014, 12211, 2147483563L, sl ) MODMULT ( 52774, 40692, 3791, 2147483399L, s2 ) z = s1 - s2 ;

if ( z < 1 )

z += 2147483562 ; return z * 4.656613e-10 ;

/* В общем случае перед использованием combinedLCG вызывается initLCG. */ void initLCG( long InitS1, long InitS2 )

sl = InitS1; s2 = InitS2;

Этот генератор работает при условии, что компьютер может представить все целые числа между -231+85 и 231-249. Переменные s1 и s2 глобальны и содержат текущее состояние генератора. Перед первым вызовом их необходимо проинициализировать. Для переменной s1 начальное значение должно лежать в диапазоне между 1