MADRYGA

MADRYGA (в честь автора W. E. Madryga) — блочний алгоритм шифрування, створений англ. W. E. Madryga в 1984 році[1].

Властивості

[ред. | ред. код]

Цей алгоритм розроблений для простої і ефективної реалізації шифрування всередині програмного забезпечення. Всі операції алгоритм виконує над байтами.

При проектуванні алгоритму автор вирішував такі завдання:

  1. Відкритий текст можна отримати з шифротексту без допомоги ключа (алгоритм безпечний);
  2. Кількість операцій, необхідна для визначення ключа за наявними шифротексту і відкритого тексту, має статистично дорівнювати добутку кількості операцій з шифрування на число можливих ключів;
  3. Популярність алгоритму не впливає на силу шифру;
  4. Зміна одного біта ключа повинна викликати для того ж відкритого тексту радикальні зміни шифротексту, і зміна одного біта відкритого тексту повинна викликати для того ж ключа радикальні зміни шифротексту;
  5. Алгоритм повинен містити некомутативну комбінацію підстановок і перестановок;
  6. Підстановки й перестановки, які використовуються в алгоритмі, повинні визначатися і вхідними даними, й ключем;
  7. Надлишкові групи бітів відкритого тексту повинні бути повністю замасковані в шифротексті;
  8. Довжина шифротексту повинна дорівнювати довжині відкритого тексту;
  9. Не повинно бути простих взаємозв'язків між будь-якими можливими ключами й особливостями шифротексту;
  10. Всі можливі ключі повинні давати сильний шифр (не повинно бути слабких ключів);
  11. Довжина ключа й тексту можуть регулюватися для реалізації різних вимог до безпеки;
  12. Алгоритм повинен дозволяти ефективну програмну реалізацію на великих мейнфреймах, мінікомп'ютерах, мікрокомп'ютерах і за допомогою дискретної логіки[1].

Алгоритм DES задовольняв перші дев'ять вимог, але останні три стали новими. Вони дають цим алгоритмам можливість програмних реалізацій.

Опис алгоритму

[ред. | ред. код]

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

Ітерація внутрішнього циклу оперує з 3-байтовим вікном даних, так званим робочим кадром. Це вікно зміщується на один байт за ітерацію. Перші два байта робочого кадру циклічно зсуваються на змінне число позицій, а для останнього байта виконується XOR з деякими бітами ключа. У міру просування робочого кадру всі байти послідовно «обертаються» і піддаються операції XOR з частинами ключа. Послідовні обертання перемішують результати попередніх операцій XOR і обертання, а результат XOR впливає на обертання. Це робить процес оборотним.

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

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

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

При дешифрування процес інвертується. При кожній ітерації внутрішнього циклу робочий кадр встановлюється на байт, третій зліва від останнього байта шифротексту, і циклічно переміщається в зворотному напрямку до байта, який знаходиться на два байти лівіше останнього байта шифротексту. І ключ, і два байта шифротексту в процесі циклічно зміщуються направо, а XOR виконується перед циклічними зрушеннями.

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

[ред. | ред. код]

Науковці з Технічного Університету в Квінсланді (англ. Queensland University of Technology) досліджували Madryga разом з деякими іншими блоковими шифрами. Вони виявили, що в цьому алгоритмі не проявляється лавинний ефект для перетворення відкритого тексту в шифротекст. Крім того, у багатьох шифротекстах відсоток одиниць був вище ніж відсоток нулів[2].

При поверхневому знайомстві з алгоритмом Елі Біхам прийшов до наступних висновків:

  1. Алгоритм складається тільки з лінійних операцій (циклічне зміщення і XOR), незначно змінюваних залежно від даних
  2. У цьому немає нічого схожого на міць S-блоків DES.
  3. Парність всіх бітів шифротексту і відкритого тексту незмінна й залежить тільки від ключа. Тому, володіючи відкритим текстом і відповідним шифротекстом, можна передбачити парність шифротекста для будь-якого відкритого тексту[1].

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

[ред. | ред. код]

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

Примітки

[ред. | ред. код]
  1. ↑ а б в From Differential Cryptanalysis to Ciphertext-Only Attacks. Архів оригіналу за 11 квітня 2018. Процитовано 10 квітня 2018.
  2. ↑ Криптоанализ и Madryga. Архів оригіналу за 8 квітня 2018. Процитовано 10 квітня 2018.
  3. ↑ Криптоаналіз. Архів оригіналу за 11 квітня 2018. Процитовано 10 квітня 2018.

Література

[ред. | ред. код]
  • Шнайєр Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке 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

Посилання

[ред. | ред. код]