CRYPTON

CRYPTON
Розробники Чьо Хун Лім (Future Systems, Inc.)
Уперше оприлюднений 1998-1999
Раундів 12
Тип SP-мережа

CRYPTON — алгоритм симетричного блокового шифрування (розмір блоку 128 біт, ключ довжиною до 256 біт), розроблений південнокорейським криптологом Чьо Лім Хун (англ. Chae Hoon Lim) з південнокорейської компанії Future Systems, яка з кінця 1980-х років працює на ринку забезпечення мереж і захисту інформації.

Алгоритм був розроблений в 1998 році для участі у конкурсі AES. Як зізнавався автор, конструкція алгоритму спирається на алгоритм SQUARE[1].

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

На конкурс AES була представлена версія алгоритму Crypton v0.5. Однак, як казав Чьо Лім Хун, йому не вистачало часу для розробки повної версії. І вже на першому етапі конкурсу AES в ході аналізу алгоритмів, версія Crypton v0.5 була замінена на версію Crypton v1.0. Відмінність нової версії від первинної полягала в зміні таблиці замін та в модифікації процесу розширення ключа.

Структура алгоритму. Основні характеристики

Як і інші учасники конкурсу AES, Crypton призначений для шифрування 128-бітових блоків даних[2]. При шифруванні використовуються ключі шифрування для декількох фіксованих розмірів — від 0 до 256 біт з кратністю 8 бітів. Структура алгоритму Crypton — структура «Квадрата» — багато в чому схожа на структуру алгоритму Square, створеного в 1997 році. Криптографічні перетворення для алгоритмів з даною структурою можуть бути виконані як для цілих рядків і стовпців масиву, так і над окремими його байтами. (Варто зазначити, що алгоритм Square був розроблений авторами майбутнього переможця конкурсу AES — авторами алгоритму Rijndael — Вінсентом Ріджменом і Джоан Дейменом.)

Шифрування

Алгоритм Crypton являє 128-бітовий блок шифруємих даних у вигляді байтового масиву 4×4, над якими в процесі шифрування проводиться кілька раундів перетворень. У кожному раунді передбачається послідовне виконання наступних операцій:

  • Таблична заміна γ {\displaystyle \gamma } ;
  • Лінійне перетворення π {\displaystyle \pi } ;
  • Байтова перестановка τ {\displaystyle \tau } ;
  • Операція σ {\displaystyle \sigma } .
Таблична заміна γ {\displaystyle \gamma }

Таблична заміна γ {\displaystyle \gamma }

Алгоритм Crypton використовує 4 таблиці замін. Кожна з яких заміщає 8-бітне вхідне значення на вихідне такого ж розміру.

Обчислення похідних таблиць замін (<<n - є циклічне зрушення вліво значення оброблюваного байта на n бітів)

Всі таблиці S 0 . . . S 3 {\displaystyle S_{0}...S_{3}} є похідними від основної таблиці S {\displaystyle S} (див. рисунок — обчислення похідних таблиць замін).

Нижче представлений приклад таблиць: Таблиця S 0 {\displaystyle S_{0}} :

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

Таблиця S 1 {\displaystyle S_{1}}

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

Таблиця S 2 {\displaystyle S_{2}}

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

Таблиця S 3 {\displaystyle {\displaystyle S_{3}}} :

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

У парних раундах використовується операція γ e {\displaystyle \gamma _{e}} в непарних — γ o {\displaystyle \gamma _{o}} . Ці операції і таблиці замін вволодіють рядом якостей, які є важливі, особливо для уніфікації операцій шифрування і розшифрування. Властивості таблиць і операцій:

γ e ( γ o ( A ) ) = γ o ( γ e ( A ) ) = A ; {\displaystyle \gamma _{e}(\gamma _{o}(A))=\gamma _{o}(\gamma _{e}(A))=A;}
S − 1 = S ; {\displaystyle S^{-1}=S;}
S 2 = S 0 − 1 4 ; {\displaystyle S_{2}=S_{0}^{-1}4;}
S 3 = S 1 − 1 ; {\displaystyle S_{3}=S_{1}^{-1};}

де A {\displaystyle A}  — поточне значення блоку шифруємих даних. Операції γ e {\displaystyle \gamma _{e}} і γ o {\displaystyle \gamma _{o}} можна визначити наступним чином:

γ e : b i j = S ( j + 2 + i m o d 4 ) ( a i j ) ; {\displaystyle \gamma _{e}:b_{ij}=S_{(j+2+imod4)}(a_{ij});}
γ o : b i j = S ( j + i m o d 4 ) ( a i j ) . {\displaystyle \gamma _{o}:b_{ij}=S_{(j+imod4)}(a_{ij}).}

де:

a i j {\displaystyle a_{ij}} — поточне значення конкретного байта даних; b i j {\displaystyle b_{ij}} b i j {\displaystyle b_{ij}}

b i j {\displaystyle b_{ij}} — значення байта даних після виконання операції;

Лінійне перетворення π {\displaystyle {\displaystyle \pi }}

Лінійне перетворення

Тут використовується 4 спеціальні константи, шістнадцяткові значення яких наведені нижче:

m 0 = F C ; {\displaystyle {\displaystyle m_{0}=FC;}}
m 1 = F 3 ; {\displaystyle {\displaystyle m_{1}=F3;}}
m 2 = C F ; {\displaystyle {\displaystyle m_{2}=CF;}}
m 3 = 3 F ; {\displaystyle m_{3}=3F;}

Ці константи об'єднані в маскуючі послідовності, наведені нижче:

M 0 = m 3 ∙ m 2 ∙ m 1 ∙ m 0 ; {\displaystyle {\displaystyle M_{0}=m_{3}\bullet m_{2}\bullet m_{1}\bullet m_{0};}}
M 1 = m 0 ∙ m 3 ∙ m 2 ∙ m 1 ; {\displaystyle {\displaystyle M_{1}=m_{0}\bullet m_{3}\bullet m_{2}\bullet m_{1};}}
M 2 = m 1 ∙ m 0 ∙ m 3 ∙ m 2 ; {\displaystyle {\displaystyle M_{2}=m_{1}\bullet m_{0}\bullet m_{3}\bullet m_{2};}}
M 3 = m 2 ∙ m 1 ∙ m 0 ∙ m 3 ; {\displaystyle M_{3}=m_{2}\bullet m_{1}\bullet m_{0}\bullet m_{3};}

де ∙ {\displaystyle \bullet }  — операція конкатенації.

Сама ж операція π {\displaystyle \pi }  — являє собою бітову перестановку. У непарних раундах використовується операція π o {\displaystyle \pi _{o}} :

B [ 0 ] = ( A [ 3 ] & M 3 ) ⊕ ( A [ 2 ] & M 2 ) ⊕ ( A [ 1 ] & M 1 ) ⊕ ( A [ 0 ] & M 0 ) ; {\displaystyle B[0]=(A[3]\&M_{3})\oplus (A[2]\&M_{2})\oplus (A[1]\&M_{1})\oplus (A[0]\&M_{0});}
B [ 1 ] = ( A [ 3 ] & M 0 ) ⊕ ( A [ 2 ] & M 3 ) ⊕ ( A [ 1 ] & M 2 ) ⊕ ( A [ 0 ] & M 1 ) ; {\displaystyle B[1]=(A[3]\&M_{0})\oplus (A[2]\&M_{3})\oplus (A[1]\&M_{2})\oplus (A[0]\&M_{1});}
B [ 2 ] = ( A [ 3 ] & M 1 ) ⊕ ( A [ 2 ] & M 0 ) ⊕ ( A [ 1 ] & M 3 ) ⊕ ( A [ 0 ] & M 2 ) ; {\displaystyle B[2]=(A[3]\&M_{1})\oplus (A[2]\&M_{0})\oplus (A[1]\&M_{3})\oplus (A[0]\&M_{2});}
B [ 3 ] = ( A [ 3 ] & M 2 ) ⊕ ( A [ 2 ] & M 1 ) ⊕ ( A [ 1 ] & M 0 ) ⊕ ( A [ 0 ] & M 3 ) ; {\displaystyle B[3]=(A[3]\&M_{2})\oplus (A[2]\&M_{1})\oplus (A[1]\&M_{0})\oplus (A[0]\&M_{3});}

де:

& {\displaystyle \&} — логічна побітова операція «і»;

A [ i ] {\displaystyle {\displaystyle A[i]}} і B [ i ] {\displaystyle {\displaystyle B[i]}}  — значення i-го рядка оброблюваних даних до і після виконання операції відповідно.

У парних раундах використовується операція π e {\displaystyle \pi _{e}} :

B [ 0 ] = ( A [ 3 ] & M 1 ) ⊕ ( A [ 2 ] & M 0 ) ⊕ ( A [ 1 ] & M 3 ) ⊕ ( A [ 0 ] & M 2 ) ; {\displaystyle B[0]=(A[3]\&M_{1})\oplus (A[2]\&M_{0})\oplus (A[1]\&M_{3})\oplus (A[0]\&M_{2});}
B [ 1 ] = ( A [ 3 ] & M 2 ) ⊕ ( A [ 2 ] & M 1 ) ⊕ ( A [ 1 ] & M 0 ) ⊕ ( A [ 0 ] & M 3 ) ; {\displaystyle B[1]=(A[3]\&M_{2})\oplus (A[2]\&M_{1})\oplus (A[1]\&M_{0})\oplus (A[0]\&M_{3});}
B [ 2 ] = ( A [ 3 ] & M 3 ) ⊕ ( A [ 2 ] & M 2 ) ⊕ ( A [ 1 ] & M 1 ) ⊕ ( A [ 0 ] & M 0 ) ; {\displaystyle B[2]=(A[3]\&M_{3})\oplus (A[2]\&M_{2})\oplus (A[1]\&M_{1})\oplus (A[0]\&M_{0});}
B [ 3 ] = ( A [ 3 ] & M 0 ) ⊕ ( A [ 2 ] & M 3 ) ⊕ ( A [ 1 ] & M 2 ) ⊕ ( A [ 0 ] & M 1 ) ; {\displaystyle B[3]=(A[3]\&M_{0})\oplus (A[2]\&M_{3})\oplus (A[1]\&M_{2})\oplus (A[0]\&M_{1});}

Фактично ця операція забезпечує наявність в кожному результуючому байті кожного стовпця двох біт кожного початкового байта того ж стовпця.

Байтова перестановка τ {\displaystyle {\displaystyle \tau }}

Байтова перестановка

Дана перестановка перетворює найпростішим чином рядок даних у стовпець:

τ : b i j = a i j {\displaystyle \tau :b_{ij}=a_{ij}}

Операція σ {\displaystyle {\displaystyle \sigma }}

Побітове додавання всього масиву даних з ключем раунду

Дана операція є побітовим складанням всього масиву даних з ключем раунду:

σ : B = A ⊕ K r {\displaystyle \sigma :B=A\oplus K_{r}}

де: B {\displaystyle B}  — нове значення блоку шифруємих даних; K r {\displaystyle K_{r}}  — ключ поточного раунду r {\displaystyle r} .

Зауважимо, саме 12 раундів шифрування рекомендується автором алгоритму Чьо Хун Лімом, проте сувора кількість раундів не встановлена. Крім 12 раундів шифрування, перед першим раундом алгоритму виконується попередня операція σ {\displaystyle \sigma } , а по завершенні 12 раундів виконується вихідне перетворення ϕ e {\displaystyle \phi _{e}} , що складається з послідовно виконуваних операцій τ {\displaystyle \tau } , π e {\displaystyle \pi _{e}} і τ {\displaystyle \tau } .

Розшифрування

Розшифрування виконується застосуванням зворотних операцій в зворотній послідовності. Всі операції, крім γ e {\displaystyle \gamma _{e}} і γ o {\displaystyle \gamma _{o}} є зворотними самим собі, а самі γ e {\displaystyle \gamma _{e}} і γ o {\displaystyle \gamma _{o}} зв'язані наступними співвідношеннями:

γ e − 1 = γ o ; {\displaystyle \gamma _{e}^{-1}=\gamma _{o};}
γ o − 1 = γ e , {\displaystyle \gamma _{o}^{-1}=\gamma _{e},}

тому при дешифруванні  γ o {\displaystyle \gamma _{o}}  — використовується в парних раундах, а γ e {\displaystyle \gamma _{e}}  — в непарних.

Варто відзначити ще одну особливість: кожен етап може бути виконуватися паралельно, що важливо при реалізації на сучасних багатоядерних і мультипоточних системах. Алгоритм має структуру SP-мережі, як і Rijndael (який є переможцем конкурсу AES) Також особливістю шифру є те, що для зашифрування та розшифрування може використовуватися одна і та ж процедура, але з різними підключами. Алгоритм ефективний як при програмній, так і апаратній реалізації. Шифр досить швидкий — на конкурсі AES при використанні компілятора Borland C показав найкращі результати серед всіх учасників.

Процедура розширення ключа

Алгоритм Crypton вимагає наявність 128 — бітового ключа для кожного раунду, а також 128 бітового ключа для попередньої операції σ. Розширення ключа відбувається в два етапи:

  1. на першому етапі відбувається формування восьми розширених ключів;
  2. на другому етапі відбувається обчислення ключів раундів з розширених ключів.

Формування розширених ключів

Формування розширених ключів відбувається так:

  • Якщо ключ шифрування має розмір, менший 256 біт, він доповнюється бітовими нулями, поки не досягне 32-байтового вихідного ключа K {\displaystyle K} :
K = k 31 ∙ . . . ∙ k 1 ∙ k 0 {\displaystyle K=k_{31}\bullet ...\bullet k_{1}\bullet k_{0}}
  • Ключ K розкладається на послідовності U {\displaystyle U} і V {\displaystyle V} , перша з яких містить тільки парні байти ключа, друга — тільки непарні:
U = U 3 ∙ U 2 ∙ U 1 ∙ U 0 ; {\displaystyle U=U_{3}\bullet U_{2}\bullet U_{1}\bullet U_{0};}
U = k 8 i + 6 ∙ k 8 i + 4 ∙ k 8 i + 2 ∙ k 8 i ; {\displaystyle U=k_{8i+6}\bullet k_{8i+4}\bullet k_{8i+2}\bullet k_{8i};}
U = k 8 i + 6 ∙ k 8 i + 4 ∙ k 8 i + 2 ∙ k 8 i ; {\displaystyle U=k_{8i+6}\bullet k_{8i+4}\bullet k_{8i+2}\bullet k_{8i};}
V = k 8 i + 7 ∙ k 8 i + 5 ∙ k 8 i + 3 ∙ k 8 i + 1 ; {\displaystyle V=k_{8i+7}\bullet k_{8i+5}\bullet k_{8i+3}\bullet k_{8i+1};}
  • Над послідовностями U {\displaystyle U} і V {\displaystyle V} виконується один раунд шифрування алгоритму Crypton з використанням ключа раунду, що складається з нульових бітів. Відповідно для U {\displaystyle U} виконуються перетворення непарного раунду, для V {\displaystyle V} відбувається перетворення парного раунду. Результуючі послідовності позначаються як U ′ {\displaystyle U'} і V ′ {\displaystyle V'} .
  • Відбувається обчислення 8 розширених ключів:
K e i = U i ′ ⊕ T 1 ; {\displaystyle Ke_{i}=U'_{i}\oplus T_{1};}
K e i + 4 = U i ′ ⊕ T 0 ; {\displaystyle Ke_{i+4}=U'_{i}\oplus T_{0};}

для i = 0 , 1 , 2 , 3 , {\displaystyle i=0,1,2,3,} де T 1 {\displaystyle T_{1}} і T 0 {\displaystyle T_{0}}  — послідовності, які визначаються наступними формулами:

T 0 = U 0 ′ ⊕ U 1 ′ ⊕ U 2 ′ ⊕ U 3 ′ ; {\displaystyle T_{0}=U'_{0}\oplus U'_{1}\oplus U'_{2}\oplus U'_{3};}
T 1 = V 0 ′ ⊕ V 1 ′ ⊕ V 2 ′ ⊕ V 3 ′ . {\displaystyle T_{1}=V'_{0}\oplus V'_{1}\oplus V'_{2}\oplus V'_{3}.}

Обчислення ключів раундів

Для обчислення з розширених ключів — ключів раундів, використовуються наступні константи:

C 0 = A 54 F F 53 A ; {\displaystyle C_{0}=A54FF53A;}
C i = C i − 1 + 3 C 6 E F 372 m o d 2 32 ; {\displaystyle C_{i}=C{i-1}+3C6EF372mod2^{32};}
M c 0 = A C A C A C A C ; {\displaystyle Mc_{0}=ACACACAC;}

Зауважимо, що псевдовипадкові константи A54FF53A і 3C6EF372 утворюються з дробових частин від чисел 7 {\displaystyle {\sqrt {7}}} і 5 {\displaystyle {\sqrt {5}}} відповідно.

Спочатку обчислюються ключі для попередньої операції σ і першого раунду:

K 0 [ i ] = K e i ⊕ C 0 ⊕ M c i ; {\displaystyle K_{0}[i]=Ke_{i}\oplus C_{0}\oplus Mc_{i};}
K 1 [ i ] = K e i + 4 ⊕ C 1 ⊕ M c i ; {\displaystyle K_{1}[i]=Ke_{i+4}\oplus C_{1}\oplus Mc_{i};}

де K r [ i ] {\displaystyle K_{r}[i]}  — i-ий рядок ключа раунду r {\displaystyle r} . Як і для шифруємих даних, ключ надається у вигляді таблиці.

Подання ключа у вигляді таблиці аналогічно шифруємим даним

Константи M c i [ i ] {\displaystyle Mc_{i}[i]} обчислюються шляхом побітового циклічного зрушення кожного байта константи M c i − 1 {\displaystyle Mc_{i-1}} на 1 біт вліво.

Для другого та кожного наступного парного раунду ключ обчислюється наступним чином:

  • Виконується модифікація перших чотирьох розширених ключів:
{ K e 3 , K e 2 , K e 1 , K e 0 } ← { K e 0 <<< 6 , K e 3 <<< 6 , K e 2 << 16 , K e 1 << 24 } ; {\displaystyle \{Ke_{3},Ke_{2},Ke_{1},Ke_{0}\}\leftarrow \{Ke_{0}<<<6,Ke_{3}<<<6,Ke_{2}<<16,Ke_{1}<<24\};}

де знаком <<< позначена операція побітового циклічного зрушення кожного байта (роздільно) розширеного ключа на вказане число біт вліво, а << — побітового циклічного зрушення всього ключа на вказане число біт вліво.

  • Обчислення ключа раунду за допомогою модифікованих розширених ключів:
K r [ i ] = K e i ⊕ C r ⊕ M c i ; {\displaystyle K_{r}[i]=Ke_{i}\oplus C_{r}\oplus Mc_{i};}

Аналогічно відбувається обчислення ключів для непарних раундів:

{ K e 7 , K e 6 , K e 5 , K e 4 } ← { K e 6 << 16 , K e 5 << 8 , K e 4 <<< 2 , K e 7 <<< 2 } ; {\displaystyle \{Ke_{7},Ke_{6},Ke_{5},Ke_{4}\}\leftarrow \{Ke_{6}<<16,Ke_{5}<<8,Ke_{4}<<<2,Ke_{7}<<<2\};}
K r [ i ] = K e i + 4 ⊕ C r ⊕ M c i ; {\displaystyle K_{r}[i]=Ke_{i+4}\oplus C_{r}\oplus Mc_{i};}

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

Безпека

Недоліки алгоритму Crypton

При аналізі вихідної версії алгоритму, Crypton v0.5, відразу двоє експертів незалежно виявили клас слабких ключів: таких виявилося 2 в ступені 32 256-бітових ключів. Також, була виявлена атака на шестираундову версію алгоритму Crypton, схожа на атаку на алгоритм Square. Це було однією з причин появи нової версії алгоритму — Crypton v1.0.

Переваги алгоритму Crypton

Однак на думку експертів інституту NIST, перераховані вище недоліки не є грубими. Крім того, плюсів у алгоритму було цілком достатньо:

  1. алгоритм ефективний на програмному та апаратному рівні завдяки високому ступені паралельності і використанні дуже простих логічних операцій ANDS/XORS;
  2. алгоритм не піддається атакам по часу виконання і споживаної потужності;
  3. хороша стійкість до існуючих атак;
  4. можливість розпаралелювання операцій в процесі шифрування;
  5. швидке розширення ключа, швидке формування ключів: шифрування з списоком ключів йде набагато швидше ніж шифрування з одним блоком, так що це дуже ефективно в додатках, що вимагають часті заміни ключів (наприклад, в хеш-режимі).
  6. досить висока швидкість на всіх цільових платформах;
  7. невеликі вимоги до оперативної пам'яті і можливість розширення ключа «на льоту» дозволяють використовувати алгоритм Crypton в смарткартах з мінімальними ресурсами;
  8. алгоритм підтримує додаткові розміри ключів, крім тих, що були встановлені конкурсом (128, 192, 256 біт).

Розробником була заявлена гарантована стійкість до лінійного та диференційного криптоаналізу і, в цілому, всім існуючим на момент розробки атак. Перероблений ключовий розклад і нові таблиці S-Box виключили всі виявлені недоліки та вразливості.

Інтегральна атака на шифр Crypton (4-х раундовий)

Аналіз безпеки блочно-симетричного шифру (БСШ) Crypton показує, що 12-раундовий самозамінюючий шифр (з однаковими процесами для шифрування та розшифрування) з довжиною блоку 128 біт і довжиною ключа до 128 бітів володіє гарною стійкістю до існуючих атак. Інтегральна атака на 4-х раундовий БСШ Crypton набагато ефективніша, ніж повний перебір по всьому ключовому простору.

Короткий опис шифру

Crypton являє собою блочний шифр. Довжина ключа і довжина блоку 128 біт. Чотири перетворення працюють з проміжним результатом, так званим Станом (State). Стан можна представити у вигляді прямокутного масиву з 16 байт:

( A i , j ) {\displaystyle {\displaystyle (A_{i,j})}} де A ∈ { 0 , . . . , 3 } {\displaystyle {\displaystyle A\in \{0,...,3\}}}

Позначимо стовпець з 4 байт як  A j = ( A 0 j , A 1 j , A 2 j , A 3 j ) {\displaystyle {\displaystyle A_{j}=(A_{0j},A_{1j},A_{2j},A_{3j})}}

Так само уявімо ключ шифрування:

( K i , j ) {\displaystyle {\displaystyle (K_{i,j})}} де K ∈ { 0 , . . . , 3 } {\displaystyle K\in \{0,...,3\}} і K j = ( K 0 j , K 1 j , K 2 j , K 3 j ) {\displaystyle K_{j}=(K_{0j},K_{1j},K_{2j},K_{3j})} .

У шифрі визначено поле Галуа G F ( 2 8 ) {\displaystyle GF(2^{8})} , елементами якого є байти. Байти розглядаються як многочлени над Z 2 {\displaystyle {\displaystyle Z_{2}}}

b ↔ b 7 x 7 + b 6 x 6 + b 5 x 5 + b 4 x 4 + b 3 x 3 + b 2 x 2 + b 1 x 1 + b 0 {\displaystyle b\leftrightarrow b_{7}x^{7}+b_{6}x^{6}+b_{5}x^{5}+b_{4}x^{4}+b_{3}x^{3}+b_{2}x^{2}+b_{1}x^{1}+b_{0}}

Операція додавання ⊕ {\displaystyle \oplus }  — при складанні байт відповідні їм многочлени складаються над   Z 2 {\displaystyle Z_{2}} .

Операція множення — при множенні відповідні їм многочлени перемножуються над  Z 2 {\displaystyle Z_{2}} і результуючий многочлен береться за модулем від простого многочлена

m ( x ) = x 8 + x 4 + x 3 + x 1 + 1 {\displaystyle m(x)=x^{8}+x^{4}+x^{3}+x^{1}+1}

В процесі роботи алгоритму, ключ ( K i , j ) {\displaystyle {\displaystyle (K_{i,j})}} розширюється (Key Schedule, Key Expansion). Перші 4 стовпців (по 4 байти) є вихідним ключем K 0 {\displaystyle K^{0}} . Кожний наступний r {\displaystyle r} -й набір з 4 стовпчиків обчислюється з попереднього набору і використовується для r {\displaystyle r} -ого раунду, позначимо його K r = ( K i , j r ) {\displaystyle K^{r}=(K_{i,j}^{r})} . Раунд складається з чотирьох різних елементарних перетворень, які перетворять стан A = ( A i , j ) {\displaystyle A=(A_{i,j})} у стан B = ( B i , j ) {\displaystyle B=(B_{i,j})}  :

  • Заміна байт — BS (Byte Substitution): застосування перестановки S {\displaystyle S} або B i , j = S ( A i , j ) {\displaystyle {\displaystyle B_{i,j}=S(A_{i,j})}}
  • Зрушення рядків — SR (Shift Rows): циклічне зрушення байт за правилом: B i , j = A i , ( j + 1 ) m o d 4 {\displaystyle {\displaystyle B_{i,j}=A_{i,(j+1)mod4}}}
  • Замішування стовпців — MC (Mix Columns: кожен стовпець стану змінюється лінійним перетворенням μ : ( 0 , 1 ) 32 → ( 0 , 1 ) 32 {\displaystyle {\displaystyle \mu :(0,1)^{32}\rightarrow (0,1)^{32}}}

Інакше кажучи, це є ніщо інше, як множення стовпців на матрицю зліва: B = μ ( A ) = E = ( 2 3 1 1 1 2 3 1 1 1 2 3 3 1 1 2 ) {\displaystyle {\displaystyle B=\mu (A)=E={\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}}}}

Операція μ {\displaystyle \mu } оборотна : A j = μ − 1 ( B j ) {\displaystyle {\displaystyle A_{j}=\mu ^{-1}(B_{j})}}

  • Додавання раундового ключа — KA (Key Addition): до поточного стану додається раундовий ключ.

Фінальний раунд не містить операції MC. Формули, що зв'язують стан  A r {\displaystyle A^{r}} і A r − 1 {\displaystyle A^{r-1}} :

A r = M C ( S R ( S ( A r − 1 ) ) ) ⊕ K r − 1 {\displaystyle {\displaystyle A^{r}=MC(SR(S(A^{r-1})))\oplus K^{r-1}}} ;
A r − 1 = S − 1 ( S R − 1 ( M C − 1 ( A r ⊕ K r − 1 ) ) ) {\displaystyle {\displaystyle A^{r-1}=S^{-1}(SR^{-1}(MC^{-1}(A^{r}\oplus K^{r-1})))}} ;

Алгоритм реалізації інтегральної атаки

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

Введемо визначення.

Λ {\displaystyle {\displaystyle \Lambda }}  — набір з 256 вхідних блоків (масивів State), кожен з яких має байти (назвемо їх активними), значення яких різні для всіх 256 блоків. Інші байти (пасивні) залишаються однаковими для всіх 256 блоків з Λ {\displaystyle {\displaystyle \Lambda }} -набору. Тобто для будь-яких A , B ∈ Λ {\displaystyle A,B\in \Lambda } то A i j ≠ B i j {\displaystyle A_{ij}\neq B_{ij}} якщо байт з індексом (i, j) активний і інакше A i j = B i j {\displaystyle A_{ij}=B_{ij}} .

Λ r {\displaystyle {\displaystyle \Lambda ^{r}}}  — Λ {\displaystyle {\displaystyle \Lambda }}  k активними байтами.
P r {\displaystyle {\displaystyle P_{r}}}  — множина станів в кінці раунду r.

Λ {\displaystyle {\displaystyle \Lambda }} -набір. Після елементарних перетворень BS і KA блоки Λ {\displaystyle {\displaystyle \Lambda }} -набору дадуть в результаті інший  Λ {\displaystyle {\displaystyle \Lambda }} -набір з активними байтами в тих же позиціях, що й вихідний. Перетворення SR змістить ці байти відповідно заданим в ній зміщенням. Після перетворення MC Λ {\displaystyle {\displaystyle \Lambda }} -набору в загальному випадку необов'язково залишиться Λ {\displaystyle {\displaystyle \Lambda }} -набором (результат операції може перестати відповідати визначенню Λ {\displaystyle {\displaystyle \Lambda }} -набору). Так як кожен байт B i j {\displaystyle B_{ij}} результату MC є лінійною комбінацією (з оборотними коефіцієнтами) чотирьох вхідних байт того ж стовпця B i j = 2 A i j ⊕ 3 A i + 1 m o d 4 j ⊕ A i + 2 m o d 4 j ⊕ A i + 3 m o d 4 j {\displaystyle B_{ij}=2A_{ij}\oplus 3A_{i+1mod4j}\oplus A_{i+2mod4j}\oplus A_{i+3mod4j}} , то стовпець з єдиним активним байтом на вході дасть у результаті на виході стовпець з усіма чотирма активними байтами.

Розглянемо шифрування Λ 1 {\displaystyle {\displaystyle \Lambda ^{1}}} -набору. У всіх блоках буде активний тільки один байт. Значення цього байта по-різному у всіх 256 блоках, а інші байти однакові. У першому раунді перетворення MC перетворює один активний байт в стовпець з 4-ма активними байтами, тобто P 1 {\displaystyle P_{1}} є Λ 4 {\displaystyle \Lambda ^{4}} . У другому раунді ці 4 байта розійдуться на 4 різні стовпці в результаті перетворення SR, P 2 {\displaystyle P_{2}} є Λ 16 {\displaystyle \Lambda ^{16}} -набором. Перетворення MC наступного, третього раунду перетворює ці байти в 4 стовпці, що містять активні байти. Цей набір все ще залишається Λ {\displaystyle {\displaystyle \Lambda }} -набором до того моменту, коли він надходить на вхід MC третього раунду.

Основна властивість Λ {\displaystyle {\displaystyle \Lambda }} -набору — порозрядна сума за модулем 2 ( ⊕ {\displaystyle \oplus } ) всіх байтів, які перебувають на одних і тих же місцях, по всьому набору дорівнює нулю (порозрядна сума неактивних (з однаковими значеннями) байтів дорівнює нулю за визначенням операції « ⊕ {\displaystyle \oplus } », а активні байти, пробігаючи всі 256 значень, також при порозрядному додаванні дадуть нуль)

Результат перетворення MC в третьому раунді байтів вхідного масиву даних A {\displaystyle A} в байти вихідного масиву даних B {\displaystyle B}  — порозрядна сума всіх блоків вихідного набору буде дорівнювати нулю:

⊕ B = M C ( A ) , A ∈ Λ 1 6 B i j = ⊕ A ∈ Λ 1 6 ( 2 A i j ⊕ 3 A i + 1 m o d 4 j ⊕ A i + 2 m o d 4 j ⊕ A i + 3 m o d 4 j ) = 0 {\displaystyle \oplus _{B=MC(A),A\in \Lambda ^{1}6}B_{ij}=\oplus _{A\in \Lambda ^{1}6}(2A_{ij}\oplus 3A_{i+1mod4j}\oplus A_{i+2mod4j}\oplus A_{i+3mod4j})=0}

Таким чином P 3 {\displaystyle P_{3}} є Λ 16 {\displaystyle \Lambda ^{16}} . Повна сума даних на вході дорівнює нулю. Ця рівність порушується подальшим перетворенням BS.

Ключ K r {\displaystyle K^{r}} однозначно задається в R поданні:

L r = S R − 1 ( M C − 1 ( K r ) ) {\displaystyle L^{r}=SR^{-1}(MC^{-1}(K^{r}))}
K r = M C ( S R ( L r ) ) {\displaystyle K^{r}=MC(SR(L^{r}))}

Для проведення атаки потрібна множина  Q 4 {\displaystyle Q_{4}} , що складаються з 256 станів. Q r = S R − 1 ( M C − 1 ( A ) ) , A ∈ P r {\displaystyle Q_{r}=SR^{-1}(MC^{-1}(A)),A\in P_{r}} Множину  Q 4 {\displaystyle Q_{4}} можна отримати застосуванням 2 зворотніх перетворень SR і MC з вхідних даних шифру P 4 {\displaystyle P_{4}} .

Схема базової інтегральної атаки на 4-раундовий Crypton: Для всіх i , j ∈ 0 , 1 , 2 , 3 {\displaystyle {\displaystyle i,j\in {0,1,2,3}}}

для k   i n G F ( 2 8 ) {\displaystyle {\displaystyle k\ inGF(2^{8})}}

якщо ⊕ Z ∈ Q S − 1 ( Z i j ⊕ k ) ≠ 0 {\displaystyle \oplus _{Z\in Q}S^{-1}(Z_{ij}\oplus k)\neq 0} ,

то L i j 4 ≠ k {\displaystyle {\displaystyle L_{ij}^{4}\neq k}}

У цій схемі інвертується 4-й раунд крок за кроком, щоб отримати байти P 3 {\displaystyle {\displaystyle P_{3}}} повна сума яких дорівнює 0. При L i j 4 = k {\displaystyle L_{ij}^{4}=k} сума ⊕ Z ∈ Q S − 1 ( Z i j ⊕ k ) = 0 {\displaystyle {\displaystyle \oplus _{Z\in Q}S^{-1}(Z_{ij}\oplus k)=0}}

Якщо передбачуване значення байта ключа було вірне, то воно буде включене в можливі варіанти на місце L 4 {\displaystyle {\displaystyle L^{4}}} . Велика частина невірних значень байта буде відсіяною. За рахунок того, що пошук може проводитися окремо (паралельно) для кожного байта ключа, швидкість підбору всього значення раундового ключа досить велика. Далі за значенням L 4 {\displaystyle L^{4}} можна знайти K 4 {\displaystyle K^{4}} , а потім і K 0 {\displaystyle K^{0}}  — вихідний ключ.

Конкурс AES

Першими кроками назустріч зміні стандартів шифрування було створення конкурсу AES. Це був відкритий конкурс, що проводиться інститутом стандартів і технологій США — NIST (National Institute of Standart and Technology). Переможець конкурсу повинен був стати новим стандартом шифрування США. У конкурсі могли брати участь приватні особи, компанії як усередині США, так і за межами країни. Основні вимоги:

  1. 128 біт — розмір блоку шифруємих даних.
  2. Три або більшої кількості розмірів ключів має підтримуватися алгоритмом (128, 256, 192 — біт — обов'язкові розміри ключів для конкурсу).

Однак, незважаючи на малу кількість вимог для алгоритмів, було багато побажань:

  1. алгоритм повинен бути стійкий від криптоаналітичних атак, відомих на момент проведення конкурсу;
  2. структура алгоритму повинна бути ясною, простою і обґрунтованою;
  3. повинні бути відсутні слабкі і еквівалентні ключі;
  4. швидкість шифрування даних повинна бути високою на всіх потенційних апаратних платформах від 8 до 64 бітових.
  5. структура алгоритму повинна дозволяти розпаралелювати операції в багатопроцесорних системах і апаратних реалізаціях.
  6. алгоритм повинен пред'являти мінімальні вимоги до оперативної та енергонезалежної пам'яті.
  7. не повинно бути обмежень на використання алгоритмів.

Зауважимо, що учасникам конкурсу AES дозволялося вносити зміни в алгоритми в ході конкурсу, якщо це незначні модифікації. Для алгоритму Crypton при наданні нової версії, журі визнали зміни значними, так як вони стосувалися таблиці замін, процедури розширення ключа. В результаті, на конкурсі брала участь версія Crypton v0.5.

Відсутність явних мінусів і наявність переваг у алгоритмі Crypton все одно не дозволила йому вийти у фінал конкурсу AES. Причиною тому була участь в конкурсі двох алгоритмів: Rijndael і Twofish. Ці алгоритми не мали проблем слабких ключів як у алгоритмі Crypton. Більше того, вони були швидшими ніж Crypton на цільових платформах. Було вирішено, що надалі Crypton програє в будь-якому разі цим алгоритмам, тому експерти конкурсу не пропустили Crypton у фінал. (Rijndael — майбутній переможець конкурсу).

Версії алгоритму Crypton

У конкурсі брала участь первинна редакція алгоритму, яка отримала індекс 0.5 через деякий час. Через деякий час було запропоновано ще кілька редакцій, останньою з якої стала версія 1.0 з переробленим ключовим розкладом і новими таблицями підстановки.

Примітки

  1. ↑ {Chae Hoon Lim, CRYPTON: A New 128-bit Block Cipher — Specification and Analysis (Version 0.5) [Архівовано 3 червня 2016 у Wayback Machine.], 1998}
  2. ↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. The Block Cipher Square [Архівовано 17 січня 2016 у Wayback Machine.]. Fast Software Encryption (FSE) 1997, Volume 1267 of Lecture Notes in Computer Science. Haifa, Israel: Springer-Verlag, pp. 149–165, 1997

Посилання та Література

  • A New 128-bit Block Cipher. [Архівовано 4 квітня 2018 у Wayback Machine.] Specification and Analysis. [Архівовано 4 квітня 2018 у Wayback Machine.] (англ)
  • A New 128-bit Block Cipher Specification and Analysis Other[недоступне посилання з лютого 2019] (англ)
  • Спецификация алгоритма
  • Chae Hoon Lim. . — DOI:10.1.1.52.5771.
  • Алгоритмы Шифрования. Специальный Справочник/ Автор: Сергей Петрович Панасенко/ Изд: «БХВ-Санкт-Петербург», 2009
  • п
  • о
  • р
SP-мережа, блок 64 біт : SAFER | SHARK
Мережа Файстеля, блок 64 біт  : ГОСТ 28147-89 (Magma) | 3-DES | Blowfish | DES | FEAL | IDEA | KASUMI | RC5 | TEA
SP-мережа, блок від 128 біт : Калина | AES | Anubis | CRYPTON | Hierocrypt-3 | Kuznechik | PRESENT | SQUARE | Serpent | Threefish
Мережа Файстеля, блок від 128 біт : Camellia | CAST-256 | MARS | RC6 | Sinople | Twofish