Блочные шифры

3. Блочные шифры

3.1. Алгоритм Lucifer

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

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

Применив дифференциальный криптоанализ к первой реализации алгоритма Lucifer, Бихам и Шамир показали, что Lucifer с 32-битовыми блоками и 8 раундами можно взломать с помощью 40 подобранных открытых текстов за 2²⁹ операций. Этот же метод позволяет вскрыть Lucifer с 128-битовыми блоками и 8 раундами с помощью 60 подобранных открытых текстов за 2⁵³ шагов. Другая дифференциальная атака вскрывает 18-раундовый, 128-битовый Lucifer с помощью 24 подобранных открытых текстов за 2²¹ операций. Во всех этих вскрытиях использовались стойкие S-блоки алгоритма DES. Применив дифференциальный криптоанализ ко второй реализации Lucifer, Бихам и Шамир обнаружили, что его S-блоки намного слабее, чем в алгоритме DES. Дальнейший анализ показал нестойкость более половины возможных ключей. Криптоанализ на основе связанных ключей позволяет взломать 128-битовый Lucifer с любым числом раундов с помощью 2³³ подобранных открытых текстов для подобранных ключей или 2⁶⁵ известных открытых текстов для подобранных ключей. Вторая реализация Lucifer еще слабее.

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

3.2. Алгоритм Madryga

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

Стоит перечислить задачи, которые решал автор при проектировании алгоритма:

ü Без помощи ключа открытый текст невозможно получить из шифртекста. (Это означает только то, что алгоритм стоек).

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

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

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

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

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

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

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

ü Между любыми возможными ключами и особенностями шифртекста недопустимы простые взаимосвязи.

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

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

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

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

Похожие работы

Обґрунтовання застосування лікарських композицій на основі нанорозмірного кремнезему в комплексному лікуванні генералізованого пародонтиту

Скачать

59220

0

0

... на генералізований пародонтит / О. І. Кутельмах // Вісник стоматології. – 2007. - № 4. – С. 137-139. АНОТАЦІЯ Кутельмах О.І. Обґрунтування застосування лікарських композицій на основі нанорозмірного кремнезему в комплексному лікуванні генералізованого пародонтиту. – Рукопис. Дисертація на здобуття наукового ступеня кандидата медичних наук за спеціальністю 14.01.22-стоматологія. – Державна ...

Мат.моделирование (Программа СДКМС)

Скачать

45010

19

22

... X1, X2 – необходимое количество рекламных заказов 2X1+2X2 ≤ 7 X1 = 1 X2 = 2 F(X1, X2) = 7 1.4. Выбор и обоснование технических средств, программ и информационных средств для реализации математического моделирования. Для реализации математического моделирования в целях данной курсовой работы выбрана система проектирования и оценки качества и устойчивости экономических объектов – СДКМС. ...

Дисертація: вимоги до написання та захист

Скачать

245524

1

0

... ічного університету, доктором технічних наук, професором М-П.Зборщиком. Висновок установи, в якій виконано дисертацію, с першою і дуже важливою її експертизою з точки зору відповідності дисертації вимогам “Порядку”. Висновок затверджується ректором (директором) або проректором (заступником директора) з наукової роботи, які несуть персональну відповідальність за якість, об'єктивність і строки пі ...

Патентоведение и основы научных исследований

Скачать

146019

0

0

... . – СПб., Изд-во “Профессия”, 2000. – С. 54-90. Раздел II Методические указания по выполнению практических работ Введение Практические занятия по дисциплине “Патентоведение и основы научных исследований” для студентов специальности 271200 “Технология продуктов общественного питания”, направления 655700 “Технология продуктов специального назначения и общественного питания” предназначены ...