CRYPTON — алгоритм симетричного блокового шифрування (розмір блоку 128 біт, ключ довжиною до 256 біт), розроблений південнокорейським криптологом Чьо Лім Хун () з південнокорейської компанії Future Systems, яка з кінця 1980-х років працює на ринку забезпечення мереж і захисту інформації.
Алгоритм був розроблений в 1998 році для участі у конкурсі AES. Як зізнавався автор, конструкція алгоритму спирається на алгоритм SQUARE{Chae Hoon Lim, CRYPTON: A New 128-bit Block Cipher — Specification and Analysis (Version 0.5) , 1998}.
В алгоритмі Crypton немає традиційних для блочних шифрів мережі Фейстеля. Основу даного шифру становить так звана SP-мережа (повторювана циклова функція, що складається із замін-перестановок, орієнтована на розпаралелену нелінійну обробку всього блоку даних). Крім високої швидкості, перевагами таких алгоритмів є полегшення дослідження стійкості шифру до методів диференціального та лінійного криптоаналізу, що є на сьогодні основними інструментами розтину блочних шифрів.
На конкурс AES була представлена версія алгоритму Crypton v0.5. Однак, як казав Чьо Лім Хун, йому не вистачало часу для розробки повної версії. І вже на першому етапі конкурсу AES в ході аналізу алгоритмів, версія Crypton v0.5 була замінена на версію Crypton v1.0. Відмінність нової версії від первинної полягала в зміні таблиці замін та в модифікації процесу розширення ключа.
Структура алгоритму. Основні характеристики Як і інші учасники конкурсу AES, Crypton призначений для шифрування 128-бітових блоків данихJoan Daemen, Lars Knudsen, Vincent Rijmen. The Block Cipher Square . Fast Software Encryption (FSE) 1997, Volume 1267 of Lecture Notes in Computer Science. Haifa, Israel: Springer-Verlag, pp. 149–165, 1997. При шифруванні використовуються ключі шифрування для декількох фіксованих розмірів — від 0 до 256 біт з кратністю 8 бітів. Структура алгоритму Crypton — структура «Квадрата» — багато в чому схожа на структуру алгоритму Square, створеного в 1997 році. Криптографічні перетворення для алгоритмів з даною структурою можуть бути виконані як для цілих рядків і стовпців масиву, так і над окремими його байтами. (Варто зазначити, що алгоритм Square був розроблений авторами майбутнього переможця конкурсу AES — авторами алгоритму Rijndael — Вінсентом Ріджменом і Джоан Дейменом.)
Шифрування Алгоритм Crypton являє 128-бітовий блок шифруємих даних у вигляді байтового масиву 4×4, над якими в процесі шифрування проводиться кілька раундів перетворень. У кожному раунді передбачається послідовне виконання наступних операцій: Таблична заміна ; Лінійне перетворення ; Байтова перестановка ; Операція .
Таблична заміна Алгоритм Crypton використовує 4 таблиці замін. Кожна з яких заміщає 8-бітне вхідне значення на вихідне такого ж розміру.
Всі таблиці є похідними від основної таблиці (див. рисунок — обчислення похідних таблиць замін).
Нижче представлений приклад таблиць: Таблиця : 63 ec 59 aa db 8e 66 c0 37 3c 14 ff 13 44 a9 91 3b 78 8d ef c2 2a f0 d7 61 9e a5 bc 48 15 12 47 ed 42 1a 33 38 c8 17 90 a6 d5 5d 65 6a fe 8f a1 93 c2 2f 0c 68 58 df f4 45 11 a0 a7 22 96 fb 7d 1d b4 84 e0 bf 57 e9 0a 4e 83 cc 7a 71 39 c7 32 74 3d de 50 85 06 6f 53 e8 ad 82 19 e1 ba 36 cb 0e 28 f3 9b 4a 62 94 1f bd f6 67 41 d8 d1 2d a4 86 b7 01 c5 b0 75 02 f9 2c 29 6e d2 f5 8b fc 5a e4 7f dd 07 55 b1 2b 89 72 18 3a 4c b6 e3 80 ce 49 cf 6b b9 f2 0d dc 64 95 46 f7 10 9a 20 a2 3f d6 87 70 3e 21 fd 4d 7b 3c ae 09 8a 04 b3 54 f8 30 00 56 d4 e7 25 bb ac 98 73 ea c9 9d 4f 7e 03 ab 92 a8 43 0f fa 24 5c 1e 60 31 97 cd c6 79 f5 5e e5 34 76 1c 81 b2 af 0b 5d d9 e2 27 6d d0 88 c1 51 e6 9c 77 be 99 23 da eb 52 2e b5 08 05 6c b8 1b a3 69 8c d3 40 26 f1 c4 9f 35 ee 7c 4b 16 Таблиця 8d b3 65 aa 6f 3a 99 03 dc f0 50 ff 4c 11 a6 46 ec e1 36 bf 0b a8 c3 5f 85 7a 96 f2 21 54 48 1d b7 09 68 cc e0 23 5c 42 9a 57 75 95 a9 fb 3e 86 4e 2b bc 30 a1 61 7f d3 15 44 82 9e 88 5a Ef f5 74 d2 12 83 fe 5d a7 28 39 0e 33 e9 c5 e4 1f c8 d1 f4 7b 41 16 18 bd 4d a3 b6 0a 64 87 ea d8 2f 38 a0 cf 6e 29 89 52 7c f6 db 9d 05 63 47 b4 92 1a de 04 17 c2 d5 08 e7 b0 a4 b9 4b 7d 2e f3 69 93 fd 77 1c 55 c6 ac 26 c9 60 e8 31 da 8f 02 3b 25 3f ad e6 cb 34 73 91 56 19 df 40 6a 80 8a fc 5b 1e c1 f8 84 f7 35 ed 0f ba 24 2a 10 ce 51 e3 c0 00 59 53 9f 94 ee b2 62 cd ab 27 76 3d f9 0c ae 4a a2 0d 3c eb 90 71 78 81 c4 5e 37 1b e5 d7 79 97 d0 d9 70 06 ca be 2c 6d 67 8b 9c b5 43 22 07 45 9b 72 dd fa 66 8c 6b af 49 b8 d6 20 14 b1 e2 6c 8e a5 32 4f 01 98 c7 13 7e d4 bb f1 2d 58 Таблиця b1 72 76 bf ac ee 55 83 ed aa 47 d8 33 95 60 c4 9b 39 1e 0c 0a 1d ff 26 89 5b 22 f1 d4 40 c8 67 9d a4 3c e7 c6 b5 f7 dc 61 79 15 86 78 6e eb 32 b0 ca 4f 23 d2 fb 5e 08 24 4d 8a 10 09 51 a3 9f f6 6b 21 c3 0d 38 99 1f 1c 90 64 fe 8b a6 48 bd 53 e1 ea 57 ae 84 b2 45 35 02 7f d9 c7 2a d0 7c c9 18 65 00 97 2b 06 6a 34 f3 2c 92 ef dd 7a 56 a2 c4 88 b9 50 75 d3 e4 11 ce 4b a7 fd 3f be 81 8e d5 5a 49 42 54 70 a1 df 87 ab 7d f4 12 05 2e 27 0f c1 30 66 98 3d cb b8 e6 9c 63 e3 bc 19 fa 3a 2f 9e f2 6f 1a 28 3b c2 0e 03 c0 b7 59 a9 d7 74 85 d6 ad 41 ec 8c 71 f0 93 5d b6 1b 68 e5 44 07 e0 14 8a f9 73 cd 4e 25 bb 31 5f 4a cc 8f 91 de 6d 7b f5 b3 29 a0 17 6c da e8 04 96 82 52 36 43 5c db 8d 80 d1 e2 b4 58 46 ba e9 01 20 fc 13 16 f8 94 62 37 cf 69 9a af 77 c5 3e 7e a5 2d 0b Таблиця : b1 f6 8e 07 72 6b d5 e0 76 21 5a 14 bf c3 49 a8 ac 0d 42 f9 ee 38 54 73 55 99 70 cd 83 1f a1 4e ed 1c df 25 aa 90 87 bb 47 64 ab 31 d8 fe 7d 5f 33 8b f4 4a 95 a6 12 cc 60 48 05 8f c4 bd 2e 91 9b 53 27 de 39 e1 0f 6d 1e ea c1 7b 0c 57 30 f5 0a ae 66 b3 1d 84 98 29 ff b2 3d a0 26 45 cb 17 89 35 b8 6c 5b 02 e6 da 22 7f 9c e8 f1 d9 63 04 d4 c7 e3 96 40 2a bc 82 c8 d0 19 52 67 7c fa 36 9d c9 3a 43 a4 18 2f 5c 3c 65 9e db e7 00 f2 8d c6 97 6f 80 b5 2b 1a d1 f7 06 28 e2 dc 6a 3b b4 61 34 c2 58 79 f3 0e 46 15 2c 03 ba 86 92 c0 e9 78 ef b7 01 6e dd 59 20 eb 7a a9 fc 32 56 d7 13 b0 a2 74 16 ca 4c 85 f8 4f 88 d6 94 23 b9 ad 62 d2 50 41 37 fb 75 ec cf 5e d3 8c 69 08 e4 71 9a 24 11 f0 af 4d ce 93 77 8a 4b 5d c5 10 a7 b6 3e 09 fd 1b 7e 51 3f 68 a5 a3 be e5 2d 9f 81 44 0b У парних раундах використовується операція в непарних — . Ці операції і таблиці замін вволодіють рядом якостей, які є важливі, особливо для уніфікації операцій шифрування і розшифрування. Властивості таблиць і операцій:
де — поточне значення блоку шифруємих даних. Операції і можна визначити наступним чином:
де:
— поточне значення конкретного байта даних;
— значення байта даних після виконання операції;
Лінійне перетворення
Тут використовується 4 спеціальні константи, шістнадцяткові значення яких наведені нижче:
Ці константи об'єднані в маскуючі послідовності, наведені нижче:
де — операція конкатенації.
Сама ж операція — являє собою бітову перестановку. У непарних раундах використовується операція :
де:
— логічна побітова операція «і»;
і — значення i-го рядка оброблюваних даних до і після виконання операції відповідно.
У парних раундах використовується операція :
Фактично ця операція забезпечує наявність в кожному результуючому байті кожного стовпця двох біт кожного початкового байта того ж стовпця.
Байтова перестановка
Дана перестановка перетворює найпростішим чином рядок даних у стовпець:
Операція
Дана операція є побітовим складанням всього масиву даних з ключем раунду:
де: — нове значення блоку шифруємих даних; — ключ поточного раунду .
Зауважимо, саме 12 раундів шифрування рекомендується автором алгоритму Чьо Хун Лімом, проте сувора кількість раундів не встановлена. Крім 12 раундів шифрування, перед першим раундом алгоритму виконується попередня операція , а по завершенні 12 раундів виконується вихідне перетворення , що складається з послідовно виконуваних операцій , і .
Розшифрування Розшифрування виконується застосуванням зворотних операцій в зворотній послідовності. Всі операції, крім і є зворотними самим собі, а самі і зв'язані наступними співвідношеннями:
тому при дешифруванні — використовується в парних раундах, а — в непарних.
Варто відзначити ще одну особливість: кожен етап може бути виконуватися паралельно, що важливо при реалізації на сучасних багатоядерних і мультипоточних системах. Алгоритм має структуру SP-мережі, як і Rijndael (який є переможцем конкурсу AES) Також особливістю шифру є те, що для зашифрування та розшифрування може використовуватися одна і та ж процедура, але з різними підключами. Алгоритм ефективний як при програмній, так і апаратній реалізації. Шифр досить швидкий — на конкурсі AES при використанні компілятора Borland C показав найкращі результати серед всіх учасників.
Процедура розширення ключа Алгоритм Crypton вимагає наявність 128 — бітового ключа для кожного раунду, а також 128 бітового ключа для попередньої операції σ. Розширення ключа відбувається в два етапи: на першому етапі відбувається формування восьми розширених ключів; на другому етапі відбувається обчислення ключів раундів з розширених ключів.
Формування розширених ключів Формування розширених ключів відбувається так: Якщо ключ шифрування має розмір, менший 256 біт, він доповнюється бітовими нулями, поки не досягне 32-байтового вихідного ключа :
Ключ K розкладається на послідовності і , перша з яких містить тільки парні байти ключа, друга — тільки непарні:
Над послідовностями і виконується один раунд шифрування алгоритму Crypton з використанням ключа раунду, що складається з нульових бітів. Відповідно для виконуються перетворення непарного раунду, для відбувається перетворення парного раунду. Результуючі послідовності позначаються як і . Відбувається обчислення 8 розширених ключів:
для де і — послідовності, які визначаються наступними формулами:
Обчислення ключів раундів Для обчислення з розширених ключів — ключів раундів, використовуються наступні константи:
Зауважимо, що псевдовипадкові константи A54FF53A і 3C6EF372 утворюються з дробових частин від чисел і відповідно.
Спочатку обчислюються ключі для попередньої операції σ і першого раунду:
де — i-ий рядок ключа раунду . Як і для шифруємих даних, ключ надається у вигляді таблиці.
Константи обчислюються шляхом побітового циклічного зрушення кожного байта константи на 1 біт вліво.
Для другого та кожного наступного парного раунду ключ обчислюється наступним чином: Виконується модифікація перших чотирьох розширених ключів:
де знаком <<< позначена операція побітового циклічного зрушення кожного байта (роздільно) розширеного ключа на вказане число біт вліво, а << — побітового циклічного зрушення всього ключа на вказане число біт вліво. Обчислення ключа раунду за допомогою модифікованих розширених ключів:
Аналогічно відбувається обчислення ключів для непарних раундів:
Процедура розширення ключа дозволяє генерувати ключі раундів «на льоту», тобто в процесі шифрування по мірі необхідності. Це явна перевага алгоритму, принаймні тому, що не потрібно пам'яті для зберігання ключів раундів. Для розшифрування можливо і виконання прямої процедури розширення ключа і використання отриманих ключів раундів у зворотному порядку.
Безпека
Недоліки алгоритму Crypton При аналізі вихідної версії алгоритму, Crypton v0.5, відразу двоє експертів незалежно виявили клас слабких ключів: таких виявилося 2 в ступені 32 256-бітових ключів. Також, була виявлена атака на шестираундову версію алгоритму Crypton, схожа на атаку на алгоритм Square. Це було однією з причин появи нової версії алгоритму — Crypton v1.0.
Переваги алгоритму Crypton Однак на думку експертів інституту NIST, перераховані вище недоліки не є грубими. Крім того, плюсів у алгоритму було цілком достатньо: алгоритм ефективний на програмному та апаратному рівні завдяки високому ступені паралельності і використанні дуже простих логічних операцій ANDS/XORS; алгоритм не піддається атакам по часу виконання і споживаної потужності; хороша стійкість до існуючих атак; можливість розпаралелювання операцій в процесі шифрування;