Мадрыга - Madryga

В криптография, Мадрыга это блочный шифр опубликовано в 1984 г. В. Э. Мадрыгой. Он был разработан, чтобы быть простым и эффективным для реализации в программном обеспечении.[1] С тех пор в алгоритме были обнаружены серьезные недостатки, но это был один из первых алгоритмов шифрования, в котором использовались ротации, зависящие от данных,[нужна цитата ] позже используется в других шифрах, таких как RC5 и RC6.

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

  1. Любой возможный ключ должен давать надежный шифр. (Имеется в виду нет слабые ключи, который есть в DES.)
  2. Длина ключа и текста должна регулироваться в соответствии с различными требованиями безопасности.
  3. Алгоритм должен быть эффективно реализован в программном обеспечении на больших мэйнфреймы, миникомпьютеры, и микрокомпьютеры, а в дискретных логика. (DES имеет большое количество побитовых перестановок, которые неэффективны в программных реализациях.)

Алгоритм

Madryga достигла цели повышения эффективности программного обеспечения: единственные операции, которые он использует, - это XOR и вращения, оба работают только с целыми байтами. У Мадрыги есть ключ переменной длины без верхнего предела его длины.

Мадрыга указана с восемью патронами,[1] но при необходимости его можно увеличить, чтобы обеспечить большую безопасность. В каждом раунде алгоритм перебирает весь открытый текст п раз, где п - длина открытого текста в байтах. Алгоритм одновременно просматривает три байта, поэтому Madryga представляет собой 24-битный блочный шифр. Это XOR ключевой байт с крайним правым байтом и вращает два других как один блок. Вращение зависит от результата XOR. Затем алгоритм переходит на один байт вправо. Итак, если бы он работал с байтами 2, 3 и 4, после того, как он завершил их вращение и XOR, он бы повторил процесс с байтами 3, 4 и 5.

Ключевой график очень простой. Для начала весь ключ подвергается операции XOR со случайной константой той же длины, что и ключ, а затем поворачивается влево на 3 бита. Он снова вращается после каждой итерации вращения и XOR. Самый правый его байт используется в каждой итерации XOR с крайним правым байтом блока данных.

Алгоритм дешифрования - это просто обратный алгоритм шифрования. Из-за характера операции XOR она обратима.

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

На первый взгляд Madryga кажется менее защищенным, чем, например, DES. Все операции Мадрыги линейны. DES S-боксы являются его единственным нелинейным компонентом, и недостатки в них - это то, что дифференциальный криптоанализ и линейный криптоанализ стремитесь эксплуатировать. Хотя вращения Мадрыги в небольшой степени зависят от данных, они все же линейны.

Возможно, фатальный недостаток Мадрыги состоит в том, что она не демонстрирует лавинный эффект. Виноват в этом его небольшой блок данных. Один байт может влиять только на два байта слева и один байт справа.

Эли Бихам рассмотрел алгоритм без формального анализа. Он заметил, что «четность всех бит открытого текста и зашифрованного текста является константой, зависящей только от ключа. Таким образом, если у вас есть один открытый текст и соответствующий ему зашифрованный текст, вы можете предсказать четность зашифрованного текста для любого открытого текста. " Здесь, паритет относится к сумме XOR всех битов.

В 1995 году Кен Ширрифф обнаружил дифференциальную атаку на Мадригу, требующую 5000 выбранные открытые тексты.[2] Бирюков и Kushilevitz (1998) опубликовали улучшенную дифференциальную атаку, требующую только 16 пар выбранный открытый текст, а затем продемонстрировали, что ее можно преобразовать в атака только зашифрованным текстом используя 212 зашифрованные тексты, при разумных предположениях об избыточности открытого текста (например, ASCII -кодированный английский язык ). Атака с использованием только зашифрованного текста разрушительна для современного блочного шифра; как таковой, вероятно, более разумно использовать другой алгоритм для шифрования конфиденциальных данных.[1]

Рекомендации

  1. ^ а б c Алексей Бирюков, Эяль Кушилевиц (1998). От дифференциального криптоанализа к атакам с использованием только зашифрованного текста. КРИПТО. С. 72–88. CiteSeerX  10.1.1.128.3697.CS1 maint: использует параметр авторов (связь)
  2. ^ Кен Ширрифф (октябрь 1995 г.). «Дифференциальный криптоанализ Мадрыги». Цитировать журнал требует | журнал = (помощь) Неопубликованная рукопись.

дальнейшее чтение

  • W. E. Madryga, "Высокопроизводительный алгоритм шифрования", Компьютерная безопасность: глобальный вызов, Издательство Elsevier Science, 1984, стр. 557–570.