SM4

SM4 — алгоритм блочного шифрования используемый в Китае как национальный стандарт для беспроводных локальных сетей (WLAN Authentication and Privacy Infrastructure (WAPI)).

SM4 (SMS4)
Опубликован	2006 г. (рассекречен)
Размер ключа	128 бит
Размер блока	128 бит
Число раундов	32
Тип	Сеть Фейстеля

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

Термины и определения

Слово и байт

Множество ${\displaystyle Z_{2}^{e}}$ определено как вектор из e бит.

${\displaystyle Z_{2}^{32}}$ это слово.

${\displaystyle Z_{2}^{8}}$ это байт.

Определения

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-бит, и представлена как ${\displaystyle MK=(MK_{0},\ MK_{1},\ MK_{2},\ MK_{3})}$, в каждой ${\displaystyle MK_{i}\ (i=0,\ 1,\ 2,\ 3)}$ содержится слово.

Раундовый ключ представлен как ${\displaystyle (rk_{0},\ rk_{1},\ \ldots ,\ rk_{31})}$. Он создаётся ключом шифрования.

${\displaystyle FK=(FK_{0},\ FK_{1},\ FK_{2},\ FK_{3})}$ это система параметров.

${\displaystyle CK=(CK_{0},\ CK_{1},\ \ldots ,\ CK_{31})}$ фиксированный параметр.

${\displaystyle FK_{i}}$ и ${\displaystyle CK_{i}}$ это слова, используемые для расширения алгоритма.

Раундовая функция F

SM4 использует нелинейную структуру подстановки, за раз шифруется 32 бита. Это так называемая однораундовая замена. Для наглядного примера рассмотрим однораундовую подстановку: Представим 128-битный входной блок как четыре 32-битных элемента
${\displaystyle (X_{0},X_{1},X_{2},X_{3})\in (Z_{2}^{32})^{4}}$, с ${\displaystyle rk\in Z_{2}^{32}}$, тогда ${\displaystyle F}$ имеет вид:
${\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)}$

Смешанная подстановка Т

${\displaystyle T}$ это подстановка которая создаёт 32 бита из 32 бит ${\displaystyle T:Z_{2}^{32}\to Z_{2}^{32}.}$ Эта подстановка обратима, и содержит в себе нелинейную подстановку, τ, и линейную подстановку L, то есть ${\displaystyle T(.)=L(\tau (.))}$

Нелинейная подстановка τ

${\displaystyle \tau }$ обрабатывает параллельно четыре S-box.

Пусть 32-битным входным словом будет ${\displaystyle A=(a_{0},a_{1},a_{2},a_{3})\in (Z_{2}^{32})^{4}}$, где каждая ${\displaystyle a_{i}}$ это 8-битный символ. Пусть 32-битным выходным словом будет ${\displaystyle B=(b_{0},b_{1},b_{2},b_{3})\in (Z_{2}^{32})^{4}}$), имеет вид
${\displaystyle (b_{0},b_{1},b_{2},b_{3})=\tau (A)}$ = (Sbox(${\displaystyle a_{0}}$), Sbox(${\displaystyle a_{1}}$), Sbox(${\displaystyle a_{2}}$), Sbox(${\displaystyle a_{3}}$))

Линейная подстановка L

${\displaystyle B\in Z_{2}^{32}}$, 32-битное слово нелинейной подстановки ${\displaystyle \tau }$ будет выводить слово линейной подстановки L. Пусть ${\displaystyle C\in Z_{2}^{32}}$ будет 32-битным выходным словом создаваемым L. Тогда
${\displaystyle C=L(B)=B\oplus (B<<<2)\oplus (B<<<10)\oplus (B<<<18)\oplus (B<<<24)}$

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».

Шифрование и расшифрование

Пусть обратной подстановкой ${\displaystyle R}$ будет:
${\displaystyle R(A_{0},A_{1},A_{2},A_{3})=(A_{3},A_{2},A_{1},A_{0}),A_{i}\in Z_{2}^{32},i=0,1,2,3.}$
Пусть текст, который подается на входе будет
${\displaystyle (X_{0},X_{1},X_{2},X_{3})\in (Z_{2}^{32})^{4}}$,
на выходе зашифрованный текст будет
${\displaystyle (Y_{0},Y_{1},Y_{2},Y_{3})\in (Z_{2}^{32})^{4}}$,
и ключ шифрования будет
${\displaystyle rk_{i},i=0,1,2,\ldots ,31.}$
Тогда шифрование будет происходить следующим образом:
${\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}$
${\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})}$
Алгоритм шифрования и расшифрования имеют одну и ту же структуру, за исключением того что порядок, в котором используются раундовые ключи обратный.
Порядок ключа при шифровании:${\displaystyle (rk_{0},rk_{1},\ldots ,rk_{31}).}$
Порядок ключа при расшифровании: ${\displaystyle (rk_{31},rk_{3}0,\ldots ,rk_{0}).}$

Key expansion

Раундовый ключ ${\displaystyle rk_{i}}$ используемый для шифрования, получается из ключа шифрования MK.
Пусть ${\displaystyle MK=(MK_{0},MK_{1},MK_{2},MK_{3}),MK_{i}\in Z_{2}^{32},i-0,1,2,3;K_{i}\in Z_{2}^{32},i=0,1,\ldots ,31;rk_{i}\in Z_{2}^{32},i=0,1,\ldots ,31}$: вывод следующий:
Во-первых,

${\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})}$

Тогда для ${\displaystyle i=0,1,2,\ldots ,31}$: ${\displaystyle rk_{i}=K_{i+4}=K_{i}\oplus T'(K_{i+1}\oplus K_{i+2}\oplus K_{i+3}\oplus CK_{i})}$
Записи:
(1) ${\displaystyle T'}$ подстановка использует ту же ${\displaystyle T}$ что и при шифровании, за исключением линейной подстановки L, она заменена на ${\displaystyle L'}$:
${\displaystyle L'(B)=B\oplus (B<<<13)\oplus (B<<<23);}$
(2) Система параметров ${\displaystyle FK}$, приведена в шестнадцатеричной записи
${\displaystyle FK_{0}=(a3b1bac6),FK_{1}=(56aa3350),FK_{2}=(677d9197),FK_{3}=(b27022dc)}$
(3) Параметр константа ${\displaystyle CK}$ получается:
Пусть ${\displaystyle ck_{i,0},ck_{i,1},ck_{i,2},ck_{i,3})\in (Z_{2}^{32})^{4},}$ тогда ${\displaystyle ck_{i,j}=(4i+j)*7(mod256).}$ 32 константы ${\displaystyle CK_{i}}$ в шестнадцатеричной записи представлены ниже:

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

${\displaystyle rk}$ и выходная информация в каждом раунде:

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