MADRYGA

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Свойства[править | править вики-текст]

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

  1. Открытый текст нельзя получить из шифротекста без помощи ключа (алгоритм безопасен);
  2. Количество операций, нужное для определения ключа по имеющимся шифротексту и открытому тексту, должно быть статистически равно произведению количества операций по шифровании на число возможных ключей;
  3. Известность алгоритма не влияет на силу шифра;
  4. Изменение одного бита ключа должно вызывать для того же открытого текста радикальное изменение шифротекста, и изменение одного бита открытого текста должно вызывать для того же ключа радикальное изменения шифротекста;
  5. Алгоритм должен содержать некоммутативную комбинацию подстановок и перестановок;
  6. Подстановки и перестановки, используемые в алгоритме, должны определяться и входными данными и ключом;
  7. Избыточные группы битов открытого текста должны быть полностью замаскированы в шифротексте;
  8. Длина шифротекста должна равняться длине открытого текста;
  9. Не должно быть простых взаимосвязей между любыми возможными ключами и особенностями шифротекста;
  10. Все возможные ключи должны давать сильный шифр (не должно быть слабых ключей);
  11. Длина ключа и текста могут регулироваться для реализации различных требований к безопасности;
  12. Алгоритм должен позволять эффективную программную реализацию на больших мейнфреймах, миникомпьютерах, микрокомпьютерах и с помощью дискретной логики.

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

Описание алгоритма[править | править вики-текст]

Madryga состоит из двух вложенных циклов. Внешний цикл повторяется восемь раз (но это количество может быть увеличено для повышения безопасности) и содержит применение внутреннего цикла к открытому тексту. Внутренний цикл превращает открытый текст в шифротекст, повторяясь для каждого 8-битового блока (байта) открытого текста. Следовательно, весь открытый текст восемь раз последовательно обрабатывается алгоритмом. Итерация внутреннего цикла оперирует с 3-байтовым окном данных, называемым рабочим кадром. Это окно смещается на один байт за итерацию. Первые две байта рабочего кадра циклически сдвигаются на переменное число позиций, а для последнего байта выполняется XOR с некоторыми битами ключа. По мере продвижения рабочего кадра все байты последовательно «вращаются» и подвергаются операции XOR с частями ключа. Последовательные вращения перемешивают результаты предыдущих операций XOR и вращения, а результат XOR влияет на вращение. Это делает процесс обратимым. Так как каждый байт данных влияет на да байта слева от себя и на один байт справа, после восьми проходов каждый байт шифротекста зависит от 16 байтов слева и от восьми байтов справа. При шифровании каждая операция внутреннего цикла устанавливает рабочий кадр на предпоследний байт текста и циклически перемещает его к байту открытого текста, третьему слева от последнего. Сначала весь ключ подвергается операции XOR со случайной константой, а затем циклически смещается влево на 3 бита. Младшие три бита младшего байта рабочего кадра сохраняются, они определяют вращение остальных двух байтов. Затем для младшего байта рабочего кадра выполняется операция XOR с младшим байтом ключа. Далее объединение двух старших байтов циклически смещается влево на переменное число битов (от 0 до 7). Наконец рабочий кадр смещается вправо на один байт и весь процесс повторяется. Смысл случайной константы в том, чтобы превратить ключ в псевдослучайную последовательность. Длина константы должна быть равна длине ключа. При обмене данными абоненты должны пользоваться константами одинаковой длины. Для 64-битового ключа Мадрига рекомендует константу 0x0f1e2d3c4b5a6978. При дешифровании процесс инвертируется. При каждой итерации внутреннего цикла рабочий кадр устанавливается на байт, третий слева от последнего байта шифротекста, и циклически перемещается в обратном направлении до байта, который находится на два байта левее последнего байта шифротекста. И ключ и два байта шифротекста в процессе циклически смещаются направо, а XOR выполняется перед циклическими сдвигами.

Криптоанализ MADRYGA[править | править вики-текст]

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

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

Ссылки[править | править вики-текст]

  • 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

Литература[править | править вики-текст]

  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке C = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз.