SM4
SM4 (SMS4) | |
---|---|
Опубликован | 2006 г. (рассекречен) |
Размер ключа | 128 бит |
Размер блока | 128 бит |
Число раундов | 32 |
Тип | Сеть Фейстеля |
SM4 — алгоритм блочного шифрования используемый в Китае как национальный стандарт для беспроводных локальных сетей (WLAN Authentication and Privacy Infrastructure (WAPI)).
Первоначально алгоритм назывался SMS4, однако в тексте стандарта GM/T 0002-2012 SM4 Block Cipher Algorithm от 21 марта 2012 года был официально переименован в SM4.[1]
SM4 был предложен как шифр используемый в стандарте IEEE 802.11i, но был быстро заменён ISO. Одной из причин этого была оппозиция WAPI fast-track продвигаемая IEEE.
Алгоритм SM4 был разработан профессором Лю Шу-ваном (LU Shu-wang(???)). Алгоритм был рассекречен в январе 2006. Несколько характеристик SM4:
- Размер блока составляет 128 бит.
- Используется 8 — битный S-box
- Размер ключа 128 бит.
- Используются только операции типа XOR, кругового сдвига и приложения S-Box
- Выполняется 32 раунда для обработки одного блока
- Каждый раунд обновляет четверть (32 бита) внутреннего состояния.
- Используется не линейное составление ключа (key schedule) для создания раундовых ключей.
- При расшифровке используются те же ключи что и при шифровании, но в обратном порядке.
Термины и определения
Слово и байт
Множество [math]\displaystyle{ Z^e_2 }[/math] определено как вектор из e бит.
[math]\displaystyle{ Z^{32}_2 }[/math] это слово.
[math]\displaystyle{ Z^8_2 }[/math] это байт.
Round Key | Round Keys получаются из Cipher Key используя процедуру Key Expansion. Они применяются к State при шифровании и расшифровании |
---|---|
Cipher Key | секретный, криптографический ключ, который используется Key Expansion процедурой, чтобы произвести набор ключей для раундов(Round Keys); может быть представлен как прямоугольный массив байтов, имеющий четыре строки и Nk колонок. |
Key Expansion | процедура используемая для генерации Round Keys из Cipher Key |
S-box | нелинейная таблица замен, использующаяся в нескольких трансформациях замены байт и в процедуре Key Expansion для взаимнооднозначной замены значения байта. Предварительно рассчитанный S-box можно увидеть ниже. |
S-box
S-box фиксируется 8 — битами на входе и 8 — битами на выходе, записывается как Sbox().
Ключи и ключевые параметры
Длина шифрованного ключа составляет 128-бит, и представлена как [math]\displaystyle{ MK=(MK_0,\ MK_1,\ MK_2,\ MK_3) }[/math], в каждой [math]\displaystyle{ MK_i\ (i=0,\ 1,\ 2,\ 3) }[/math] содержится слово.
Раундовый ключ представлен как [math]\displaystyle{ (rk_0,\ rk_1,\ \ldots,\ rk_{31}) }[/math]. Он создаётся ключом шифрования.
[math]\displaystyle{ FK=(FK_0,\ FK_1,\ FK_2,\ FK_3) }[/math] это система параметров.
[math]\displaystyle{ CK=(CK_0,\ CK_1,\ \ldots,\ CK_{31}) }[/math] фиксированный параметр.
[math]\displaystyle{ FK_i }[/math] и [math]\displaystyle{ CK_i }[/math] это слова, используемые для расширения алгоритма.
Раундовая функция F
SM4 использует нелинейную структуру подстановки, за раз шифруется 32 бита. Это так называемая однораундовая замена. Для наглядного примера рассмотрим однораундовую подстановку:
Представим 128-битный входной блок как четыре 32-битных элемента
[math]\displaystyle{ (X_0,X_1,X_2,X_3) \in (Z^{32}_2)^4 }[/math], с [math]\displaystyle{ rk \in Z^{32}_2 }[/math], тогда [math]\displaystyle{ F }[/math] имеет вид:
[math]\displaystyle{ F(X_0,X_1,X_2,X_3,rk) = X_0 \oplus T(X_1 \oplus X_2 \oplus X_3 \oplus rk) }[/math]
Смешанная подстановка Т
[math]\displaystyle{ T }[/math] это подстановка которая создаёт 32 бита из 32 бит [math]\displaystyle{ T : Z^{32}_2 \to Z^{32}_2. }[/math] Эта подстановка обратима, и содержит в себе нелинейную подстановку, τ, и линейную подстановку L, то есть [math]\displaystyle{ T(.) = L (\tau(.)) }[/math]
Нелинейная подстановка τ
[math]\displaystyle{ \tau }[/math] обрабатывает параллельно четыре S-box.
Пусть 32-битным входным словом будет [math]\displaystyle{ A = (a_0,a_1,a_2,a_3) \in (Z^{32}_2)^4 }[/math], где каждая [math]\displaystyle{ a_i }[/math] это 8-битный символ.
Пусть 32-битным выходным словом будет [math]\displaystyle{ B = (b_0,b_1,b_2,b_3) \in (Z^{32}_2)^4 }[/math]), имеет вид
[math]\displaystyle{ (b_0,b_1,b_2,b_3) = \tau (A) }[/math] = (Sbox([math]\displaystyle{ a_0 }[/math]), Sbox([math]\displaystyle{ a_1 }[/math]), Sbox([math]\displaystyle{ a_2 }[/math]), Sbox([math]\displaystyle{ a_3 }[/math]))
Линейная подстановка L
[math]\displaystyle{ B \in Z^{32}_2 }[/math], 32-битное слово нелинейной подстановки [math]\displaystyle{ \tau }[/math] будет выводить слово линейной подстановки L. Пусть [math]\displaystyle{ C \in Z^{32}_2 }[/math] будет 32-битным выходным словом создаваемым L. Тогда
[math]\displaystyle{ C = L(B) = B \oplus (B \lt \lt \lt 2) \oplus (B \lt \lt \lt 10) \oplus (B \lt \lt \lt 18) \oplus (B \lt \lt \lt 24) }[/math]
S box
Все Sbox числа в шестнадцатеричной записи.
_ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | d6 | 90 | e9 | fe | cc | e1 | 3d | b7 | 16 | b6 | 14 | c2 | 28 | fb | 2c | 05 |
1 | 2b | 67 | 9a | 76 | 2a | be | 04 | c3 | aa | 44 | 13 | 26 | 49 | 86 | 06 | 99 |
2 | 9c | 42 | 50 | f4 | 91 | ef | 98 | 7a | 33 | 54 | 0b | 43 | ed | cf | ac | 62 |
3 | e4 | b3 | 1c | a9 | c9 | 08 | e8 | 95 | 80 | df | 94 | fa | 75 | 8f | 3f | a6 |
4 | 47 | 07 | a7 | fc | f3 | 73 | 17 | ba | 83 | 59 | 3c | 19 | e6 | 85 | 4f | a8 |
5 | 68 | 6b | 81 | b2 | 71 | 64 | da | 8b | f8 | eb | 0f | 4b | 70 | 56 | 9d | 35 |
6 | 1e | 24 | 0e | 5e | 63 | 58 | d1 | a2 | 25 | 22 | 7c | 3b | 01 | 21 | 78 | 87 |
7 | d4 | 00 | 46 | 57 | 9f | d3 | 27 | 52 | 4c | 36 | 02 | e7 | a0 | c4 | c8 | 9e |
8 | ea | bf | 8a | d2 | 40 | c7 | 38 | b5 | a3 | f7 | f2 | ce | f9 | 61 | 15 | a1 |
9 | e0 | ae | 5d | a4 | 9b | 34 | 1a | 55 | ad | 93 | 32 | 30 | f5 | 8c | b1 | e3 |
a | 1d | f6 | e2 | 2e | 82 | 66 | ca | 60 | c0 | 29 | 23 | ab | 0d | 53 | 4e | 6f |
b | d5 | db | 37 | 45 | de | fd | 8e | 2f | 03 | ff | 6a | 72 | 6d | 6c | 5b | 51 |
c | 8d | 1b | af | 92 | bb | dd | bc | 7f | 11 | d9 | 5c | 41 | 1f | 10 | 5a | d8 |
d | 0a | c1 | 31 | 88 | a5 | cd | 7b | bd | 2d | 74 | d0 | 12 | b8 | e5 | b4 | b0 |
e | 89 | 69 | 97 | 4a | 0c | 96 | 77 | 7e | 65 | b9 | f1 | 09 | c5 | 6e | c6 | 84 |
f | 18 | f0 | 7d | ec | 3a | dc | 4d | 20 | 79 | ee | 5f | 3e | d7 | cb | 39 | 48 |
Например, если на входе Sbox принимает значение «ef», тогда найдя строку «e» и столбец «f», получаем Sbox(«ef») = «84».
Шифрование и расшифрование
Пусть обратной подстановкой [math]\displaystyle{ R }[/math] будет:
[math]\displaystyle{ R (A_0 ,A_1, A_2, A_3) = (A_3, A_2, A_1, A_0), A_i \in Z^{32}_2, i = 0, 1, 2, 3. }[/math]
Пусть текст, который подается на входе будет
[math]\displaystyle{ (X_0, X_1, X_2, X_3) \in (Z^{32}_2)^4 }[/math],
на выходе зашифрованный текст будет
[math]\displaystyle{ (Y_0, Y_1, Y_2, Y_3) \in (Z^{32}_2)^4 }[/math],
и ключ шифрования будет
[math]\displaystyle{ rk_i, i = 0, 1, 2,\ldots , 31. }[/math]
Тогда шифрование будет происходить следующим образом:
[math]\displaystyle{ X_{i+4} = F (X_i, X_{i+1}, X_{i+2}, X_{i+3}, rk_i) = X_i \oplus T (X_{i+1} \oplus X_{i+2} \oplus X_{i+3} \oplus rk_i), i = 0, 1, 2,\ldots , 31 }[/math]
[math]\displaystyle{ (Y_0 , Y_1 , Y_2 , Y_3) = R (X_{32} , X_{33} , X_{34} , X_{35}) = (X_{35} , X_{34} , X_{33} , X_{32}) }[/math]
Алгоритм шифрования и расшифрования имеют одну и ту же структуру, за исключением того что порядок, в котором используются раундовые ключи обратный.
Порядок ключа при шифровании:[math]\displaystyle{ (rk_0, rk_1,\ldots ,rk_{31} ). }[/math]
Порядок ключа при расшифровании: [math]\displaystyle{ (rk_{31}, rk_30,\ldots ,rk_0 ). }[/math]
Key expansion
Раундовый ключ [math]\displaystyle{ rk_i }[/math] используемый для шифрования, получается из ключа шифрования MK.
Пусть [math]\displaystyle{ MK = (MK_0, MK_1, MK_2, MK_3), MK_i \in Z^{32}_2, i - 0,1,2,3; K_i \in Z^{32}_2, i = 0,1,\ldots ,31; rk_i \in Z^{32}_2, i = 0,1,\ldots ,31 }[/math]: вывод следующий:
Во-первых,
[math]\displaystyle{ (K_0, K_1, K_2, K_3) = (MK_0 \oplus FK_0, MK_1 \oplus FK_1, MK_2 \oplus FK_2, MK_3 \oplus FK_3) }[/math]
Тогда для [math]\displaystyle{ i = 0,1,2,\ldots ,31 }[/math]:
[math]\displaystyle{ rk_i = K_{i+4} = K_i \oplus T' (K_{i+1} \oplus K_{i+2} \oplus K_{i+3} \oplus CK_i) }[/math]
Записи:
(1) [math]\displaystyle{ T' }[/math] подстановка использует ту же [math]\displaystyle{ T }[/math] что и при шифровании, за исключением линейной подстановки L, она заменена на [math]\displaystyle{ L' }[/math]:
[math]\displaystyle{ L' (B) = B \oplus (B \lt \lt \lt 13) \oplus (B \lt \lt \lt 23); }[/math]
(2) Система параметров [math]\displaystyle{ FK }[/math], приведена в шестнадцатеричной записи
[math]\displaystyle{ FK_0 = (a3b1bac6), FK_1 = (56aa3350), FK_2 = (677d9197), FK_3 = (b27022dc) }[/math]
(3) Параметр константа [math]\displaystyle{ CK }[/math] получается:
Пусть [math]\displaystyle{ ck_{i,0},ck_{i,1},ck_{i,2},ck_{i,3}) \in (Z^{32}_2)^4, }[/math] тогда [math]\displaystyle{ ck_{i,j} = (4i + j) * 7 (mod 256). }[/math] 32 константы [math]\displaystyle{ CK_i }[/math] в шестнадцатеричной записи представлены ниже:
00070e15 | 1c232a31 | 383f464d | 545b6269 |
70777e85 | 8c939aa1 | a8afb6bd | c4cbd2d9 |
e0e7eef5 | fc030a11 | 181f262d | 343b4249 |
50575e65 | 6c737a81 | 888f969d | a4abb2b9 |
c0c7ced5 | dce3eaf1 | f8ff060d | 141b2229 |
30373e45 | 4c535a61 | 686f767d | 848b9299 |
a0a7aeb5 | bcc3cad1 | d8dfe6ed | f4fb0209 |
10171e25 | 2c333a41 | 484f565d | 646b7279 |
Пример шифрования
Ниже представлен пример шифрования. Мы используем его для проверки правильности шифрования. Числа проверяются в шестнадцатеричной записи.
Пример № 1. Шифрование один раз
plaintext: | 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 |
encrypting key: | 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 |
[math]\displaystyle{ rk }[/math] и выходная информация в каждом раунде:
rk[ 0] | = | f12186f9 | X[ 4] | = | 27fad345 |
rk[ 1] | = | 41662b61 | X[ 5] | = | a18b4cb2 |
rk[ 2] | = | 5a6ab19a | X[ 6] | = | 11c1e22a |
rk[ 3] | = | 7ba92077 | X[ 7] | = | cc13e2ee |
rk[ 4] | = | 367360f4 | X[ 8] | = | f87c5bd5 |
rk[ 5] | = | 776a0c61 | X[ 9] | = | 33220757 |
rk[ 6] | = | b6bb89b3 | X[ 10] | = | 77f4c297 |
rk[ 7] | = | 24763151 | X[ 11] | = | 7a96f2eb |
rk[ 8] | = | a520307c | X[ 12] | = | 27dac07f |
rk[ 9] | = | b7584dbd | X[ 13] | = | 42dd0f19 |
rk[10] | = | c30753ed | X[14] | = | b8a5da02 |
rk[11] | = | 7ee55b57 | X[15] | = | 907127fa |
rk[12] | = | 6988608c | X[16] | = | 8b952b83 |
rk[13] | = | 30d895b7 | X[17] | = | d42b7c59 |
rk[14] | = | 44ba14af | X[18] | = | 2ffc5831 |
rk[15] | = | 104495a1 | X[19] | = | f69e6888 |
rk[16] | = | d120b428 | X[20] | = | af2432c4 |
rk[17] | = | 73b55fa3 | X[21] | = | ed1ec85e |
rk[18] | = | cc874966 | X[22] | = | 55a3ba22 |
rk[19] | = | 92244439 | X[23] | = | 124b18aa |
rk[20] | = | e89e641f | X[24] | = | 6ae7725f |
rk[21] | = | 98ca015a | X[25] | = | f4cba1f9 |
rk[22] | = | c7159060 | X[26] | = | 1dcdfa10 |
rk[23] | = | 99e1fd2e | X[27] | = | 2ff60603 |
rk[24] | = | b79bd80c | X[28] | = | eff24fdc |
rk[25] | = | 1d2115b0 | X[29] | = | 6fe46b75 |
rk[26] | = | 0e228aeb | X[30] | = | 893450ad |
rk[27] | = | f1780c81 | X[31] | = | 7b938f4c |
rk[28] | = | 428d3654 | X[32] | = | 536e4246 |
rk[29] | = | 62293496 | X[33] | = | 86b3e94f |
rk[30] | = | 01cf72e5 | X[34] | = | d206965e |
rk[31] | = | 9124a012 | X[35] | = | 681edf34 |
Шифр текст: 68 1e df 34 d2 06 96 5e 86 b3 e9 4f 53 6e 42 46
Пример № 2: Использование ключа шифрования такого же как и текст для шифрования 1.000.000 раз
Текст: | 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 |
Ключ шифрования: | 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 |
Шифрованный текст: | 59 52 98 c7 c6 fd 27 1f 04 02 f8 04 c3 3d 3f 66 |
Примечания
- ↑ http://www.codeofchina.com/standard/GMT0002-2012.html Архивная копия от 4 марта 2016 на Wayback Machine GM/T 0002-2012 SM4 Block Cipher Algorithm (English)
Ссылки
- Chinese document describing the SMS4 cipher Архивная копия от 10 июля 2007 на Wayback Machine
- English translation of the Chinese document Архивная копия от 9 апреля 2016 на Wayback Machine
- Linear and Differential Cryptanalysis of Reduced SMS4 Block Cipher Архивная копия от 18 февраля 2012 на Wayback Machine
- Example of SMS4 implemented as a Spreadsheet
- Page of Prof. LU Shu-wang(???) in Chinese
- Example of SMS4 implemented in ANSI C Архивная копия от 22 февраля 2012 на Wayback Machine
В статье не хватает ссылок на источники (см. также рекомендации по поиску). |