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

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

• задача: чтобы по структуре шифротекста нельзя было сделать выводов о структуре открытого текста

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).
• Для первого блока \(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.
• при потере или порче одного из блоков, “испорчен” так же будет только следующий блок открытого текста, но не остальные.

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

• \(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.\)
• Использование с частичным блоком, как в CFB, уменьшает длину цикла \(O_i\), плохо
• достоинство: прямая применимость помехоустойчивых кодов к шифротексту

Counter, CTR

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

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

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

Генерация ключей

1. Выбираются два случайных простых числа \(p\neq q\) заданного размера (в битах)
2. Вычисляется модуль \(m=p\cdot q\)
3. Вычисляется \(\varphi(m) = (p-1)(q-1)\)
4. Выбирается открытая экспонента \(e\), \(1 < e < \varphi(m)\), взаимно простое со значением \(\varphi(m).\) Популярные варианты – 17, 257, 65537
5. Вычисляется секретная экспонента \(d\): \(d\cdot e = 1 \mod \varphi(m).\)
6. (e, m) – открытый ключ
7. (d, m) – закрытый ключ

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

• Блочный алгоритм
• \(E(p, (e, m)) = p^e \mod m\)
• \(D(c, (d, m)) = c^d \mod m\)

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

• пусть \(P_i = [b_0 b_1 \ldots b_{15}]\)
• тогда \[s_i^{(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}\]

• Размер ключа определяет число раундов операций, применяемых \(s_i\):
• Для 128-битного ключа, 10 раундов
• Для 192-битного ключа, 12 раундов
• Для 256-битного ключа, 14 раундов

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

• частный случай \(GF(256)\).
• циклическое поле многочленов над \(GF(2)\) по модулю \(p(x) = x^8+x^4+x^3+x+1\)
• биты элемента \(GF(256)\) – коэффициенты многочлена 7-й степени

Подстановки Рейндала

• \(S(g(x)) = g(x)^{-1} f(x) + t(x) \mod p(x)\)
• \(p(x) = x^8+x^4+x^3+x+1\)
• \(f(x) = x^4+x^3+x^2+x+1\)
• \(t(x) = x^6+x^5+x+1\)

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

• Константы раундов \(rcon_i = [rc_i ~ 00 ~ 00 ~ 00],\) \(rc_i = x^{i-1}\) в поле Рейндала
• Пусть \(K_0,\ldots,K_{N-1}\) – 32-битные части ключа (N=4 для AES128, 6 для AES192 и 8 для AES256)
• Пусть \(r\) – число раундов, \(R = r+1\) – количество ключей раундов, и \(W_0,\ldots,W_{4R-1}\) – 32-битные части ключей раундов.
• \(F_1(x) = S(x \lll 8)\), \(\lll\) – циклический битовый сдвиг, \(F_2(x) = S(x)\), \(S\) - побайтовая подстановка Рейндала

• AES128 ⇒ N=4, R=11; AES192 ⇒ N=6, R=13; AES256 ⇒ N=8, R=15

Алгоритм

1. Из расписания ключей вырабатываются ключи раундов \(J_1,\ldots, J_{R},\) \(R=r+1\).

2. Для каждого раунда \(j=1,\ldots,r\):
   1. \(s_i^{(j)} = s_i^{(j-1)}\oplus J_j\)
   2. \(s_i^{(j)} = S(s_i^{(j)})\)
   3. \(\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. \(\mathrm if~j\neq r\), столбцы представляются в виде \(b(x)=b_3x^3+b_2x^2+b_1x+b_0\) над \(GF(2^8)\) и умножаются на \(a(x)=3x^3+x^2+x+2 \mod x^4+1\)
3. \(C_i = s_i^{(r)}\oplus J_{R}\)