MADRYGA

MADRYGA (в честь автора W. E. Madryga) — блочный алгоритм шифрования, созданный В. Е. Мадрига в 1984 году.

Свойства

Этот алгоритм разработан для простой и эффективной реализации шифрования внутри программного обеспечения. Все операции алгоритм выполняет над байтами.

При проектировании алгоритма автор решал следующие задачи:

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

Алгоритм DES удовлетворял первым девяти требованиям, но последние три стали новыми. Они дают этому алгоритму возможность программных реализаций.

Описание алгоритма

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

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

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

При шифровании каждая операция внутреннего цикла устанавливает рабочий кадр на предпоследний байт текста и циклически перемещает его к байту открытого текста, третьему слева от последнего. Сначала весь ключ подвергается операции XOR со случайной константой, а затем циклически смещается влево на 3 бита. Младшие три бита младшего байта рабочего кадра сохраняются, они определяют вращение остальных двух байтов. Затем для младшего байта рабочего кадра выполняется операция XOR с младшим байтом ключа. Далее объединение двух старших байтов циклически смещается влево на переменное число битов (от 0 до 7). Наконец рабочий кадр смещается вправо на один байт и весь процесс повторяется.

Смысл случайной константы в том, чтобы превратить ключ в псевдослучайную последовательность. Длина константы должна быть равна длине ключа. При обмене данными абоненты должны пользоваться константами одинаковой длины. Для 64-битового ключа Мадрига рекомендует константу 0x0f1e2d3c4b5a6978.

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

Криптоанализ MADRYGA

Исследователи из Технического Университета в Квинсланде (Queensland University of Technology) исследовали Madryga вместе с некоторыми другими блочными шифрами. Они обнаружили, что в этом алгоритме не проявляется лавинный эффект для преобразования открытого текста в шифротекст. Кроме того, во многих шифротекстах процент единиц был выше чем процент нулей.

При поверхностном знакомстве с алгоритмом Эли Бихам пришёл к следующим выводам:

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

Примечания

Литература

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке C = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз.
W. E. Madryga, «A High Performance Encryption Algorithm», Computer Security: A Global Challenge, Elsevier Science Publishers, 1984, pp. 557—570.
Ken Shirriff, Differential Cryptanalysis of Madryga, unpublished manuscript, October 1995.
Alex Biryukov, Eyal Kushilevitz: From Differential Cryptoanalysis to Ciphertext-Only Attacks. CRYPTO 1998: pp. 72-88