Режимы блочных шифров

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

Режим шифрования

метод применения блочного шифра, позволяющий преобразовать последовательность блоков открытого текста в последовательность блоков шифротекста. При этом для шифрования одного блока могут использоваться данные другого блока.

Обычно режимы шифрования используются для изменения процесса шифрования так, чтобы результат шифрования каждого блока был уникальным вне зависимости от открытого текста и не позволял сделать какие-либо выводы об их структуре.

Режим электронной кодовой книги (Electronic Codebook, ECB)

Так же называется режимом простой замены. Собственно, это режим “наивного” применения блочного шифра, когда блоки шифротекста независимы друг от друга.

\[C_i = E(P_i, k),\]

где \(C_i\) – блоки шифротекста, \(P_i\) – блоки открытого текста, \(k\) – ключ.

Режим сцепления блоков шифротекста (Cipher Block Chaining, CBC)

Для рандомизации каждого последующего блока открытого текста используется предыдущий блок шифротекста.

\[C_i = E(P_i \oplus C_{i-1}, k).\]

Здесь \(\oplus\) – побитовое суммирование по модулю 2 (xor).

Для шифрования первого блока используется так называемый вектор инициализации (initialization vector, IV) – случайный битовый вектор размера блока. Тогда,

\[C_0 = IV,\] \[C_1 = E(P_1 \oplus C_0, k).\]

Вектор инициализации передаётся вместе с шифротекстом.

Дешифрование тогда

\[C_0 = IV,\] \[P_i = D(C_i,k) \oplus C_{i-1}.\]

Недостатком этого режима является невозможность распараллеливания шифрования (но дешифрование возможно распараллелить).

Режим обратной связи по шифротексту (Cipher Feedback, CFB)

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

\[C_i = E(C_{i-1}, k)\oplus P_i\] \[P_i = E(C_{i-1}, k)\oplus C_i\] \[C_0 = IV\]

Возможности распараллеливания такие же, как у CBC.

Особенностью режима является то, что при потере или порче одного из блоков, “испорчен” так же будет только следующий блок открытого текста, но не остальные.

Существуют модификации этого режима, допускающие потерю лишь части блока – в частности это становится интересно при потоковой передаче данных. В таком варианте, фактически используемые блоки меньше длины блока самого шифра, а для генерации блочных ключей используется сдвиговый регистр:

\[C_i = head(E(S_{i-1}, k), x) \oplus P_i,\] \[P_i = head(E(S_{i-1}, k), x) \oplus C_i,\] \[S_i = ((S_{i-1} \ll x) + C_i) \mod 2^n,\] \[S_0 = IV,\] где \(n\) – длина блока шифра (в битах), \(x\) – длина фактически используемого блока (в битах), \(head(d, x)\) возвращает \(x\) старших бит \(d\). В таком варианте, при потере числа бит, кратного \(x\) из шифротекста, “испорченными” окажутся не все последующие блоки, а \(n/x\) блоков после последнего утерянного.

Режим обратной связи по выходу (Output Feedback, OFB)

Аналогичен CFB, но блочные ключи не зависят от открытого текста

\[O_0 = IV,\] \[O_i = E(O_{i-1}, k),\] \[C_i = P_i \oplus O_i,\] \[P_i = C_i \oplus O_i.\]

Использование OFB с частичным блоком, как в CFB очень сильно уменьшает длину цикла \(O_i\), поэтому не рекомендовано их соображений криптостойкости.

Одним из достоинств режима OFB является прямая применимость кодов, исправляющих ошибки, к шифротексту, поскольку, в силу свойств побитового xor, “порча” бита в шифротексте соответствует “порче” того же бита в открытом тексте.

Режим счётчика (Counter, CTR)

Аналогично OFB, режим счётчика превращает блоковый шифр в поточный. Следующий блочный ключ генерируется шифрованием некоего “счётчика”, который может быть любой неповторяющейся последовательностью – обычный счётчик, увеличивающийся на 1, самый простой и достаточно популярный вариант.

\[C_i = P_i\oplus E(\chi_i, k),\] где \(\chi_i\) – значение последовательности счётчика.

Понятно, что при одинаковом ключе, \(\chi_i\) должны быть уникальны для каждого блока каждого сообщения. Это может быть достигнуто за счёт, например, назначения старших битов счётчика уникальным номером приращения, а младших – номером блока.

Асимметричный шифр RSA

Разработанный Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом алгоритм асимметричного шифрования, основанный на проблеме факторизации больших чисел.

Алгоритм генерации ключей

1. Выбираются два различных случайных простых числа \(p\) и \(q\) заданного размера (в битах)
2. Вычисляется модуль \(n=p\cdot q\)
3. Вычисляется значение функции Эйлера от модуля \(\varphi(n) = (p-1)(q-1)\)
4. Выбирается число \(e\), \(1 < e < \varphi(n)\), взаимно простое со значением \(\varphi(n)\). Это число называется открытой экспонентой. Обычно в качестве числа \(e\) выбирается простое число, содержащее небольшое количество единичных бит в двоичном представлении, поскольку это упрощает вычисления при шифровании. Например, простые числа Ферма. Слишком малые значения \(e\), возможно, ухудшают криптостойкость, поэтому популярные варианты – 17, 257, 65537 (все известные простые числа Ферма кроме 3, 5).
5. Вычисляется число \(d\), мультипликативно обратное к \(e\) по модулю \(\varphi(n)\) \[d\cdot e = 1 \mod \varphi(n).\] Оно называется секретной экспонентой. Для вычисления можно использовать, например, расширенный алгоритм Евклида.
6. Пара (e, n) называется открытым ключом и используется для шифрования. Она может быть опубликована.
7. Пара (d, n) называется закрытым ключом и используется для дешифрования. Она должна оставаться секретной.

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

Алгоритм шифрования является блочным, соответственно открытый текст разбивается на блоки, равные размеру ключа, затем каждый блок шифруется.

Функция шифрования \[E(p, (e, n)) = p^e \mod n\]

Функция дешифрования \[D(c, (d, n)) = c^d \mod n\]

Поскольку \(d\) является мультипликативно обратным к \(e\) по модулю \(\varphi(n)\), и в мультипликативной группе по модулю \(n\) порядок любого элемента является делителем \(\varphi(n)\) (теорема Лагранжа), функции шифрования и дешифрования являются взаимно-обратными, т.е.

\[E(D(c, (d, n)), (e, n)) = c^{de} \mod n = c\] \[D(E(p, (d, n)), (e, n)) = p^{ed} \mod n = p\]

Симметричный шифр AES

Конкретные шифры из семейства шифров Рейндала (Rijndael), имеющие блок длины 128 бит и ключ длины 128, 192 или 256 бит. Является американским национальным стандартом с 2002 года. Широко применяется.

AES является блочным шифром, соответственно открытый текст делится на блоки и каждый блок шифруется отдельно.

В основе алгоритма лежат операции над матрицей байт \(4\times 4\), инициализируемой открытым текстом и называемой состоянием.

Если блок открытого текста имеет вид \(b_0 b_1 \ldots b_{15}\), то матрица состояния инициализируется значением

\[\begin{bmatrix} b_0 & b_4 & b_8 & b_{12} \\ b_1 & b_5 & b_9 & b_{13} \\ b_2 & b_6 & b_{10} & b_{14} \\ b_3 & b_7 & b_{11} & b_{15} \\ \end{bmatrix}\]

Размер ключа определяет число циклов преобразования, называемых раундами, применяемых к этой матрице.

• Для 128-битного ключа, 10 раундов
• Для 192-битного ключа, 12 раундов
• Для 256-битного ключа, 14 раундов

Общее описание алгоритма

1. На основе расписания ключей Рейндала (см. ниже) вырабатываются \(r+1\) ключей раундов на основе ключа шифра, где \(r\) – число раундов.
2. Для каждого раунда:
   1. Состояние объединяется с ключом раунда побитовым сложением по модулю 2.
   2. Каждый байт состояния заменяется на новый в соответствии с фиксированной таблицей (см. ниже)
   3. Каждая строка матрицы циклически смещается на свой номер влево (нумерация начиная с 0): \[\begin{bmatrix} b_0 & b_4 & b_8 & b_{12} \\ b_1 & b_5 & b_9 & b_{13} \\ b_2 & b_6 & b_{10} & b_{14} \\ b_3 & b_7 & b_{11} & b_{15} \\ \end{bmatrix} \to \begin{bmatrix} b_0 & b_4 & b_8 & b_{12} \\ b_5 & b_9 & b_{13} & b_1 \\ b_{10} & b_{14} & b_2 & b_6 \\ b_{15} & b_3 & b_7 & b_{11}\\ \end{bmatrix}\]
   4. Если не последний раунд, столбцы представляются в виде полиномов 3-й степени над \(GF(2^8)\) и умножаются на \(a(x)=3x^3+x^2+x+2 \mod x^4+1\)
3. Состояние объединяется с дополнительным ключом раунда побитовым сложением по модулю 2.

Конечное поле Рейндала

Конечное поле Рейндала является частным случаем конечного поля \(GF(256)\).

Конкретно, это циклическое поле многочленов над \(GF(2)\) по модулю \(x^8+x^4+x^3+x+1\). Биты каждого элемента \(GF(256)\) трактуются как коэффициенты многочлена 7-й степени.

Таблица подстановок Рейндала

Таблица подстановок строится следующим образом: значение рассматривается как значение в поле Рейндала. От значения вычисляется мультипликативно-обратное в поле Рейндала. результат вычисления затем умножается на многочлен \(x^4+x^3+x^2+x+1\) и складывается с многочленом \(x^6+x^5+x+1\).

Таблица подстановок тогда имеет вид:

	00	01	02	03	04	05	06	07	08	09	0a	0b	0c	0d	0e	0f
00	63	7c	77	7b	f2	6b	6f	c5	30	01	67	2b	fe	d7	ab	76
10	ca	82	c9	7d	fa	59	47	f0	ad	d4	a2	af	9c	a4	72	c0
20	b7	fd	93	26	36	3f	f7	cc	34	a5	e5	f1	71	d8	31	15
30	04	c7	23	c3	18	96	05	9a	07	12	80	e2	eb	27	b2	75
40	09	83	2c	1a	1b	6e	5a	a0	52	3b	d6	b3	29	e3	2f	84
50	53	d1	00	ed	20	fc	b1	5b	6a	cb	be	39	4a	4c	58	cf
60	d0	ef	aa	fb	43	4d	33	85	45	f9	02	7f	50	3c	9f	a8
70	51	a3	40	8f	92	9d	38	f5	bc	b6	da	21	10	ff	f3	d2
80	cd	0c	13	ec	5f	97	44	17	c4	a7	7e	3d	64	5d	19	73
90	60	81	4f	dc	22	2a	90	88	46	ee	b8	14	de	5e	0b	db
a0	e0	32	3a	0a	49	06	24	5c	c2	d3	ac	62	91	95	e4	79
b0	e7	c8	37	6d	8d	d5	4e	a9	6c	56	f4	ea	65	7a	ae	08
c0	ba	78	25	2e	1c	a6	b4	c6	e8	dd	74	1f	4b	bd	8b	8a
d0	70	3e	b5	66	48	03	f6	0e	61	35	57	b9	86	c1	1d	9e
e0	e1	f8	98	11	69	d9	8e	94	9b	1e	87	e9	ce	55	28	df
f0	8c	a1	89	0d	bf	e6	42	68	41	99	2d	0f	b0	54	bb	16

Расписание ключей Рейндала

Константы раундов \(rcon\) представляют из себя 32-битные числа \([rc_i ~ 00 ~ 00 ~ 00],\) со старшим байтом определяемым как \[rc_i = x^{i-1}\] в поле Рейндала, и нулевыми младшими байтами.

\(i\)	\(rc_i\)	\((rc_i)_{16}\)
1	1	0x01
2	2	0x02
3	4	0x04
4	8	0x08
5	16	0x10
6	32	0x20
7	64	0x40
8	128	0x80
9	27	0x1B
10	54	0x36

Пусть \(N\) – длина ключа в 32-битных словах, т.е. 4 для AES128, 6 для AES192 и 8 для AES256.

Пусть \(K_0,\ldots,K_{N-1}\) – 32-битные части ключа шифра.

Пусть \(R = r+1\) – количество необходимых ключей раундов, и \(W_0,\ldots,W_{4R-1}\) – 32-битные части ключей раундов.

\[F_1(x) = S(x \lll 8)\] \[F_2(x) = S(x)\]

\(S\) – побайтная подстановка по таблице Рейндала, \(\lll\) – циклический битовый сдвиг влево.

Тогда \[W_i = \begin{cases} K_i, & i < N \\ W_{i-N} \oplus F_1(W_{i-1}) \oplus rcon_{i/N}, & i \ge N, i \equiv 0 \pmod{N} \\ W_{i-N}\oplus F_2(W_{i-1}), & i \ge N, N > 6, i \equiv 4 \pmod{N} \\ W_{i-N} \oplus W_{i-1} & \text{иначе} \\ \end{cases} \]