Другие блочные шифры

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 выбранных открытых текстов за 2³⁹ шагов, тот же способ позволит вскрыть Lucifer с 128-битовыми блоками и 8 этапами с помощью 60 выбранных открытых текстов за 2⁵³ шагов. 18-этапный, 128-битовый Lucifer вскрывается дифференциальным криптоанализом с помощью 24 выбранных открытых текстов за 2²¹ шагов. Все эти вскрытия использовали сильные S‑блоки DES. Применив дифференциальный криптоанализ против второй реализации Lucifer, Бихам и Шамир обнаружили, что S-блоки намного слабее, чем в DES. Дальнейший анализ показал, что более половины возможных ключей не являются безопасными [112]. Криптоанализ со связанными ключами может взломать 128-битовый Lucifer с любым числом этапов с помощью 2³³ выбранных открытых текстов для выбранных ключей или 2⁶⁵ известных открытых текстов для выбранных ключей [158]. Вторая реализация Lucifer еще слабее [170, 172, 112].

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

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

MADRYGA

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

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

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

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

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

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

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

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

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

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

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

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

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

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