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

Я рекомендую использовать схему Бихама для зависящих от ключа S-блоков. Она может быть легко реал и-зована программно или аппаратно (с помощью микросхем с загружаемыми S-блоками), и не приводит к потере эффективности по сравнению с DES. Эта схема повышает устойчивость алгоритма к вскрытию грубой силой, усложняет дифференциальный и линейный криптоанализ и заставляет NSA столкнуться с алгоритмом, по кра й-ней мере таким же сильным как DES, но другим.

Глава 13 Другие блочные шифры

13.1 LUCIFER

В конце 60-х IBM начала выполнение исследовательской программы по компьютерной криптографии, наз ы-анной Люцифером (Lucifer) и руководимой сначала Хорстом Фейстелем (Horst Feistel), а затем Уолтом Тачм е-ном (Walt Tuchman). Это же название - Lucifer - получил блочный алгоритм, появившийся в результате этой программыв начале 70-х [1482, 1484]. В действительности существует по меньшей мере два различных алг о-ритма с таким именем [552, 1492]. [552] содержит ряд пробелов в спецификации алгоритма. Все это привело к заметной путанице.

Lucifer - это набор перестановок и подстановок, его блоки похожи на блоки DES. В DES результат функции f объединяется с помощью XOR со входом предыдущего этапа, образуя вход следующего этапа. У S-блоков алг о-ритма Lucifer 4-битовые входы и 4-битовые выходы, вход S-блоков представляет собой перетасованный выход S блоков предыдущего этапа, входом S-блоков первого этапа является открытый текст. Для выбора использу е-мого S-блока из двух возможных применяется бит ключа. (Lucifer реализует это, как один T-блок с 9 битами на входе и 8 битами на выходе.) В отличие от DES половины блока между этапами не переставляются и вообще понятие половины блока не используется в алгоритме Lucifer. У этого алгоритма 16 этапов, 128-битовые блоки и более простое, чем в DES, распределение ключей.

Применив дифференциальный криптоанализ к первой реализации Luciferа, Бихам и Шамир [170, 172] пок а-зали, что Lucifer с 32-битовыми блоками и 8 этапами может быть взломан с помощью 40 выбранных открытых текстов за 239 шагов, тот же способ позволит вскрыть Lucifer с 128-битовыми блоками и 8 этапами с помощью 60 выбранных открытых текстов за 2 53 шагов. 18-этапный, 128-битовый Lucifer вскрывается дифференциал ь-ным криптоанализом с помощью 24 выбранных открытых текстов за 2 21 шагов. Все эти вскрытия использовали сильные S-блоки DES. Применив дифференциальный криптоанализ против второй реализации Lucifer, Бихам и Шамир обнаружили, что S-блоки намного слабее, чем в DES. Дальнейший анализ показал, что более половины возможных ключей не являются безопасными [112]. Криптоанализ со связанными ключами может взломать 128-битовый Lucifer с любым числом этапов с помощью 2 33 выбранных открытых текстов для выбранных ключей или 265 известных открытых текстов для выбранных ключей [158]. Вторая реализация Lucifer еще слабее [170, 172, 112].

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

Lucifer является объектом нескольких патентов США: [553, 554, 555, 1483]. Сроки действия всех этих п а-тентов истекли.

13.2 MADRYGA

В.Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984 году [999]. 0н может быть эффе к-тивно реализован как программа: в нем нет надоедливых перестановок, и все операции выполняются над ба й-тами. Стоит перечислить задачи, которые решал автор при проектировании алгоритма:

1. 0ткрытый текст нельзя получить из шифротекста без помощи ключа. (Это означает только то, что а л-горитм безопасен.)

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

3. Известность алгоритма не влияет на силу шифра. (Безопасность полностью опр еделяется ключом.)

4. Изменение одного бита ключа должно вызывать для того же открытого текста радикальное изменение шифротекста, и Изменение одного бита открытого текста должно вызывать для того же ключа рад и-кальное изменение шифротекста. (Это лавинный э ффект.)

5. Алгоритм должен содержать некоммутативную комбинацию подстановок и перестан овок.

6. Подстановки и перестановки, используемые в алгоритме, должны определяться и входными данными, и ключом.

7. Избыточные группы битов открытого текста должны быть полностью замаскированы в шифротексте.

8. Длина шифротекста должна равняться длине открытого текста.

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

10. Все возможные ключи должны давать сильный шифр. (Не должно быть слабых кл ючей.)

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

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

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

Описание Madryga

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

Итерация внутреннего цикла оперирует с 3-байтовым окном данных, называемым рабочим кадром (см. 12-й). Это окно смещается на 1 байт за итерацию. (При работе с последними 2 байтами данные считаются цикл и-чески замкнутыми.) Первые два байта рабочего кадра циклически сдвигаются на переменное число позиций, а для последнего байта выполняется XOR с некоторыми битами ключа. По мере продвижения рабочего кадра все байты последовательно "вращаются" и подвергаются операции XOR с частями ключа. Последовательные вр а-щения перемешивают результаты предыдущих операций XOR и вращения, а результат XOR влияет на вращ е-ние. Это делает весь процесс обратимым.

Текст

Движущийся

рабочий

кадр

Циклический сдвиг

Преобразование

12345 ...

TL- TL-1

WF(1H WF(2)

WF(3)

8 битов 8 битов

8 битов

Объект сдвига

3 бита

Объект преобразования

8 битов XOR

ключа

Рис. 13-1. Одна итерация Madryga.

Так как каждый байт данных влияет на два байта слева от себя и на один байт справа, после восьми прох о-дов каждый байт шифротекста зависит от 16 байтов слева и от восьми байтов справа.

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