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.

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>Z^e_2</math> определено как вектор из e бит.

<math>Z^{32}_2</math> это слово.

<math>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>MK=(MK_0,\ MK_1,\ MK_2,\ MK_3)</math>, в каждой <math>MK_i\ (i=0,\ 1,\ 2,\ 3)</math> содержится слово.

Раундовый ключ представлен как <math>(rk_0,\ rk_1,\ \ldots,\ rk_{31})</math>. Он создаётся ключом шифрования.

<math>FK=(FK_0,\ FK_1,\ FK_2,\ FK_3)</math> это система параметров.

<math>CK=(CK_0,\ CK_1,\ \ldots,\ CK_{31})</math> фиксированный параметр.

<math>FK_i</math> и <math>CK_i</math> это слова, используемые для расширения алгоритма.

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

SM4 использует нелинейную структуру подстановки, за раз шифруется 32 бита. Это так называемая однораундовая замена. Для наглядного примера рассмотрим однораундовую подстановку: Представим 128-битный входной блок как четыре 32-битных элемента
<math>(X_0,X_1,X_2,X_3) \in (Z^{32}_2)^4</math>, с <math>rk \in Z^{32}_2</math>, тогда <math>F </math> имеет вид:
<math> 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> T </math> это подстановка которая создаёт 32 бита из 32 бит <math> T : Z^{32}_2 \to Z^{32}_2.</math> Эта подстановка обратима, и содержит в себе нелинейную подстановку, τ, и линейную подстановку L, то есть <math> T(.) = L (\tau(.)) </math>

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

<math>\tau </math> обрабатывает параллельно четыре S-box.

Пусть 32-битным входным словом будет <math> A = (a_0,a_1,a_2,a_3) \in (Z^{32}_2)^4 </math>, где каждая <math> a_i</math> это 8-битный символ. Пусть 32-битным выходным словом будет <math> B = (b_0,b_1,b_2,b_3) \in (Z^{32}_2)^4 </math>), имеет вид
<math> (b_0,b_1,b_2,b_3) = \tau (A) </math> = (Sbox(<math> a_0 </math>), Sbox(<math> a_1 </math>), Sbox(<math> a_2 </math>), Sbox(<math> a_3 </math>))

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

<math> B \in Z^{32}_2 </math>, 32-битное слово нелинейной подстановки <math> \tau </math> будет выводить слово линейной подстановки L. Пусть <math> C \in Z^{32}_2 </math> будет 32-битным выходным словом создаваемым L. Тогда
<math> C = L(B) = B \oplus (B <<< 2) \oplus (B <<< 10) \oplus (B <<< 18) \oplus (B <<< 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>R</math> будет:
<math> 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> (X_0, X_1, X_2, X_3) \in (Z^{32}_2)^4 </math>,
на выходе зашифрованный текст будет
<math> (Y_0, Y_1, Y_2, Y_3) \in (Z^{32}_2)^4 </math>,
и ключ шифрования будет
<math> rk_i, i = 0, 1, 2,\ldots , 31. </math>
Тогда шифрование будет происходить следующим образом:
<math> 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> (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> (rk_0, rk_1,\ldots ,rk_{31} ).</math>
Порядок ключа при расшифровании: <math> (rk_{31}, rk_30,\ldots ,rk_0 ).</math>

Key expansion

Раундовый ключ <math>rk_i</math> используемый для шифрования, получается из ключа шифрования MK.
Пусть <math> 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> (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> i = 0,1,2,\ldots ,31</math>: <math> 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> T'</math> подстановка использует ту же <math> T</math> что и при шифровании, за исключением линейной подстановки L, она заменена на <math> L'</math>:
<math> L' (B) = B \oplus (B <<< 13) \oplus (B <<< 23); </math>
(2) Система параметров <math>FK</math>, приведена в шестнадцатеричной записи
<math>FK_0 = (a3b1bac6), FK_1 = (56aa3350), FK_2 = (677d9197), FK_3 = (b27022dc)</math>
(3) Параметр константа <math> CK </math> получается:
Пусть <math> ck_{i,0},ck_{i,1},ck_{i,2},ck_{i,3}) \in (Z^{32}_2)^4, </math> тогда <math> ck_{i,j} = (4i + j) * 7 (mod 256). </math> 32 константы <math>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> 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

Ссылки

• [www.oscca.gov.cn/UpFile/200621016423197990.pdf Chinese document describing the SMS4 cipher]
• [eprint.iacr.org/2008/329.pdf English translation of the Chinese document]
• [eprint.iacr.org/2008/281 Linear and Differential Cryptanalysis of Reduced SMS4 Block Cipher]
• [www.cryptoclarity.com/CryptoClarityLLC/Welcome/Entries/2009/2/24_SMS4_Cipher_as_a_Spreadsheet.html Example of SMS4 implemented as a Spreadsheet]
• [www.lois.labs.gov.cn/personnel/lvshuwang.htm Page of Prof. LU Shu-wang(???) in Chinese]
• [hi.baidu.com/numax/blog/item/80addfefddfb93e4cf1b3e61.html Example of SMS4 implemented in ANSI C]

Отрывок, характеризующий SM4

– Ваше сиятельство, лёгко как! – сказал он, почтительно улыбаясь.
– Что!
– Лёгко, ваше сиятельство.
«Что он говорит?» подумал князь Андрей. «Да, об весне верно, подумал он, оглядываясь по сторонам. И то зелено всё уже… как скоро! И береза, и черемуха, и ольха уж начинает… А дуб и не заметно. Да, вот он, дуб».
На краю дороги стоял дуб. Вероятно в десять раз старше берез, составлявших лес, он был в десять раз толще и в два раза выше каждой березы. Это был огромный в два обхвата дуб с обломанными, давно видно, суками и с обломанной корой, заросшей старыми болячками. С огромными своими неуклюжими, несимметрично растопыренными, корявыми руками и пальцами, он старым, сердитым и презрительным уродом стоял между улыбающимися березами. Только он один не хотел подчиняться обаянию весны и не хотел видеть ни весны, ни солнца.
«Весна, и любовь, и счастие!» – как будто говорил этот дуб, – «и как не надоест вам всё один и тот же глупый и бессмысленный обман. Всё одно и то же, и всё обман! Нет ни весны, ни солнца, ни счастия. Вон смотрите, сидят задавленные мертвые ели, всегда одинакие, и вон и я растопырил свои обломанные, ободранные пальцы, где ни выросли они – из спины, из боков; как выросли – так и стою, и не верю вашим надеждам и обманам».
Князь Андрей несколько раз оглянулся на этот дуб, проезжая по лесу, как будто он чего то ждал от него. Цветы и трава были и под дубом, но он всё так же, хмурясь, неподвижно, уродливо и упорно, стоял посреди их.
«Да, он прав, тысячу раз прав этот дуб, думал князь Андрей, пускай другие, молодые, вновь поддаются на этот обман, а мы знаем жизнь, – наша жизнь кончена!» Целый новый ряд мыслей безнадежных, но грустно приятных в связи с этим дубом, возник в душе князя Андрея. Во время этого путешествия он как будто вновь обдумал всю свою жизнь, и пришел к тому же прежнему успокоительному и безнадежному заключению, что ему начинать ничего было не надо, что он должен доживать свою жизнь, не делая зла, не тревожась и ничего не желая.


По опекунским делам рязанского именья, князю Андрею надо было видеться с уездным предводителем. Предводителем был граф Илья Андреич Ростов, и князь Андрей в середине мая поехал к нему.
Был уже жаркий период весны. Лес уже весь оделся, была пыль и было так жарко, что проезжая мимо воды, хотелось купаться.
Князь Андрей, невеселый и озабоченный соображениями о том, что и что ему нужно о делах спросить у предводителя, подъезжал по аллее сада к отрадненскому дому Ростовых. Вправо из за деревьев он услыхал женский, веселый крик, и увидал бегущую на перерез его коляски толпу девушек. Впереди других ближе, подбегала к коляске черноволосая, очень тоненькая, странно тоненькая, черноглазая девушка в желтом ситцевом платье, повязанная белым носовым платком, из под которого выбивались пряди расчесавшихся волос. Девушка что то кричала, но узнав чужого, не взглянув на него, со смехом побежала назад.
Князю Андрею вдруг стало от чего то больно. День был так хорош, солнце так ярко, кругом всё так весело; а эта тоненькая и хорошенькая девушка не знала и не хотела знать про его существование и была довольна, и счастлива какой то своей отдельной, – верно глупой – но веселой и счастливой жизнию. «Чему она так рада? о чем она думает! Не об уставе военном, не об устройстве рязанских оброчных. О чем она думает? И чем она счастлива?» невольно с любопытством спрашивал себя князь Андрей.
Граф Илья Андреич в 1809 м году жил в Отрадном всё так же как и прежде, то есть принимая почти всю губернию, с охотами, театрами, обедами и музыкантами. Он, как всякому новому гостю, был рад князю Андрею, и почти насильно оставил его ночевать.
В продолжение скучного дня, во время которого князя Андрея занимали старшие хозяева и почетнейшие из гостей, которыми по случаю приближающихся именин был полон дом старого графа, Болконский несколько раз взглядывая на Наташу чему то смеявшуюся и веселившуюся между другой молодой половиной общества, всё спрашивал себя: «о чем она думает? Чему она так рада!».
Вечером оставшись один на новом месте, он долго не мог заснуть. Он читал, потом потушил свечу и опять зажег ее. В комнате с закрытыми изнутри ставнями было жарко. Он досадовал на этого глупого старика (так он называл Ростова), который задержал его, уверяя, что нужные бумаги в городе, не доставлены еще, досадовал на себя за то, что остался.
Князь Андрей встал и подошел к окну, чтобы отворить его. Как только он открыл ставни, лунный свет, как будто он настороже у окна давно ждал этого, ворвался в комнату. Он отворил окно. Ночь была свежая и неподвижно светлая. Перед самым окном был ряд подстриженных дерев, черных с одной и серебристо освещенных с другой стороны. Под деревами была какая то сочная, мокрая, кудрявая растительность с серебристыми кое где листьями и стеблями. Далее за черными деревами была какая то блестящая росой крыша, правее большое кудрявое дерево, с ярко белым стволом и сучьями, и выше его почти полная луна на светлом, почти беззвездном, весеннем небе. Князь Андрей облокотился на окно и глаза его остановились на этом небе.
Комната князя Андрея была в среднем этаже; в комнатах над ним тоже жили и не спали. Он услыхал сверху женский говор.
– Только еще один раз, – сказал сверху женский голос, который сейчас узнал князь Андрей.
– Да когда же ты спать будешь? – отвечал другой голос.
– Я не буду, я не могу спать, что ж мне делать! Ну, последний раз…
Два женские голоса запели какую то музыкальную фразу, составлявшую конец чего то.
– Ах какая прелесть! Ну теперь спать, и конец.
– Ты спи, а я не могу, – отвечал первый голос, приблизившийся к окну. Она видимо совсем высунулась в окно, потому что слышно было шуршанье ее платья и даже дыханье. Всё затихло и окаменело, как и луна и ее свет и тени. Князь Андрей тоже боялся пошевелиться, чтобы не выдать своего невольного присутствия.
– Соня! Соня! – послышался опять первый голос. – Ну как можно спать! Да ты посмотри, что за прелесть! Ах, какая прелесть! Да проснись же, Соня, – сказала она почти со слезами в голосе. – Ведь этакой прелестной ночи никогда, никогда не бывало.
Соня неохотно что то отвечала.
– Нет, ты посмотри, что за луна!… Ах, какая прелесть! Ты поди сюда. Душенька, голубушка, поди сюда. Ну, видишь? Так бы вот села на корточки, вот так, подхватила бы себя под коленки, – туже, как можно туже – натужиться надо. Вот так!
– Полно, ты упадешь.
Послышалась борьба и недовольный голос Сони: «Ведь второй час».
– Ах, ты только всё портишь мне. Ну, иди, иди.
Опять всё замолкло, но князь Андрей знал, что она всё еще сидит тут, он слышал иногда тихое шевеленье, иногда вздохи.
– Ах… Боже мой! Боже мой! что ж это такое! – вдруг вскрикнула она. – Спать так спать! – и захлопнула окно.
«И дела нет до моего существования!» подумал князь Андрей в то время, как он прислушивался к ее говору, почему то ожидая и боясь, что она скажет что нибудь про него. – «И опять она! И как нарочно!» думал он. В душе его вдруг поднялась такая неожиданная путаница молодых мыслей и надежд, противоречащих всей его жизни, что он, чувствуя себя не в силах уяснить себе свое состояние, тотчас же заснул.


На другой день простившись только с одним графом, не дождавшись выхода дам, князь Андрей поехал домой.
Уже было начало июня, когда князь Андрей, возвращаясь домой, въехал опять в ту березовую рощу, в которой этот старый, корявый дуб так странно и памятно поразил его. Бубенчики еще глуше звенели в лесу, чем полтора месяца тому назад; всё было полно, тенисто и густо; и молодые ели, рассыпанные по лесу, не нарушали общей красоты и, подделываясь под общий характер, нежно зеленели пушистыми молодыми побегами.
Целый день был жаркий, где то собиралась гроза, но только небольшая тучка брызнула на пыль дороги и на сочные листья. Левая сторона леса была темна, в тени; правая мокрая, глянцовитая блестела на солнце, чуть колыхаясь от ветра. Всё было в цвету; соловьи трещали и перекатывались то близко, то далеко.