Мадрига
В криптографии опубликованный Мадрига — это блочный шифр, в 1984 году В. Е. Мадригой. Он был разработан для простой и эффективной реализации в программном обеспечении. [1] С тех пор в алгоритме были обнаружены серьезные недостатки, но это был один из первых алгоритмов шифрования, в котором использовалась ротация, зависящая от данных. [ нужна ссылка ] позже использовался в других шифрах, таких как RC5 и RC6 .
В своем предложении Мадрига сформулировал двенадцать целей проектирования, которые обычно считаются хорошими целями при разработке блочного шифра. DES уже выполнил девять из них. Три, которые DES не выполнил, были:
- Любой возможный ключ должен давать надежный шифр. (Это означает отсутствие слабых ключей , которые есть в DES.)
- Длина ключа и текста должны регулироваться в соответствии с различными требованиями безопасности.
- Алгоритм должен быть эффективно реализован в программном обеспечении на больших мейнфреймах , мини- и микрокомпьютерах , а также в дискретной логике . (В DES имеется большое количество побитовых перестановок, которые неэффективны в программных реализациях.)
Алгоритм [ править ]
Madryga достигла цели повышения эффективности программного обеспечения: единственные операции, которые она использует, — это XOR и ротация , обе работают только с целыми байтами. У Madryga есть ключ переменной длины, без верхнего предела его длины.
Мадрига рассчитана на восемь раундов, [1] но при необходимости это значение можно увеличить, чтобы обеспечить большую безопасность. В каждом раунде алгоритм обрабатывает весь открытый текст n раз, где n — длина открытого текста в байтах. Алгоритм обрабатывает три байта за раз, поэтому Мадрига представляет собой 24-битный блочный шифр. Он выполняет XOR ключевого байта с самым правым байтом и вращает два других как один блок. Вращение зависит от результата операции XOR. Затем алгоритм перемещается вправо на один байт. Таким образом, если бы он работал с байтами 2, 3 и 4, после завершения вращения и выполнения операции XOR он повторил бы процесс с байтами 3, 4 и 5.
Схема ключей очень проста. Для начала весь ключ подвергается операции XOR со случайной константой той же длины, что и ключ, а затем поворачивается влево на 3 бита. Он вращается снова после каждой итерации вращения и XOR. Самый правый его байт используется в каждой итерации операции XOR с самым правым байтом блока данных.
Алгоритм дешифрования является просто обратным алгоритму шифрования. Из-за характера операции XOR она обратима.
Криптоанализ [ править ]
На первый взгляд Мадрига кажется менее безопасной, чем, например, DES. Все операции Мадриги линейны. DES S-блоки — его единственный нелинейный компонент, и их недостатки — это то, что как дифференциальный криптоанализ , так и линейный криптоанализ стремятся использовать . Хотя вращения Мадриги в небольшой степени зависят от данных, они по-прежнему линейны.
Возможно, фатальный недостаток Мадриги в том, что она не проявляет лавинного эффекта . В этом виноват его небольшой блок данных. Один байт может влиять только на два байта слева и один байт справа.
Эли Бихам рассмотрел алгоритм, не проводя формального анализа. Он заметил, что «четность всех битов открытого текста и зашифрованного текста является константой и зависит только от ключа. Итак, если у вас есть один открытый текст и соответствующий ему зашифрованный текст, вы можете предсказать четность зашифрованного текста для любого открытого текста. " Здесь четность относится к сумме XOR всех битов.
В 1995 году Кен Ширрифф обнаружил дифференциальную атаку на Мадригу, которая требует 5000 выбранных открытых текстов . [2] Бирюков и Кушилевиц (1998) опубликовали улучшенную дифференциальную атаку, требующую всего 16 пар выбранного открытого текста, а затем продемонстрировали, что ее можно преобразовать в атаку только зашифрованного текста, используя 2 12 зашифрованные тексты при разумных предположениях об избыточности открытого текста (например, ASCII в кодировке английский язык ). Атака только с использованием зашифрованного текста разрушительна для современного блочного шифра; поэтому, вероятно, более разумно использовать другой алгоритм для шифрования конфиденциальных данных. [1]
Ссылки [ править ]
- ^ Jump up to: а б с Алексей Бирюков ; Эяль Кушилевиц (1998). От дифференциального криптоанализа к атакам только с использованием зашифрованного текста . КРИПТО . стр. 72–88. CiteSeerX 10.1.1.128.3697 .
- ^ Кен Ширрифф (октябрь 1995 г.). «Дифференциальный криптоанализ Мадриги» .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) Неопубликованная рукопись.
Дальнейшее чтение [ править ]
- В. Е. Мадрига, «Высокопроизводительный алгоритм шифрования», Компьютерная безопасность: глобальный вызов , Elsevier Science Publishers, 1984, стр. 557–570.
