MADRYGA

MADRYGA (в честь автора W. E. 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. Парність всіх бітів шифротексту і відкритого тексту незмінна й залежить тільки від ключа. Тому, володіючи відкритим текстом і відповідним шифротекстом, можна передбачити парність шифротекста для будь-якого відкритого тексту.

Вразливість MADRYGA

В 1998 була виявлена ​​вразливість до атак на основі шифротексту у блочному шифрі MADRYGA, але це не отримало широкого розповсюдження.

Література

• Шнайєр Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке 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 [Архівовано 17 липня 2012 у Wayback Machine.], unpublished manuscript, October 1995.
• Alex Biryukov, Eyal Kushilevitz: From Differential Cryptoanalysis to Ciphertext-Only Attacks. CRYPTO 1998: pp. 72-88

Посилання

• From Differential Cryptanalysis to Ciphertext-Only Attacks [Архівовано 11 квітня 2018 у Wayback Machine.]
• Криптоанализ и Madryga [Архівовано 8 квітня 2018 у Wayback Machine.]