C#. Криптографические алгоритмы. AES-256
В VR редко встретишь публикации на тему криптографии, однако на форуме частенько возникают вопросы как запрограммировать тот или иной шифр, хэш-функцию и т.д. В своей первой статье для VR я хочу рассказать как самому написать пару функций, реализующих блочный шифр AES-256 (Advanced Encryption Standard с длиной ключа 256 бит, длиной блока 128 бит), который в настоящий момент является стандартом в США. Сразу оговорюсь, что программировать будем 2 режима работы – режим счетчика (Counter Mode, CTR) и режим счетчика с аутентификацией CCM (CTR + CBC-MAC).
Описание шифра смотри в стандарте FIPS-197 "Announcing the Advanced Encryption Standard", описание режима CCM можно найти в RFC 3610 "Counter with CBC-MAC (CCM)", описание режима CTR можно легко найти в Интернете.
Итак, приступим к разбору самого алгоритма. Согласно FIPS-197 наша версия алгоритма будет иметь 14 раундов. Весь алгоритм описывается следующим псевдокодом:
Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4, Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr-1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1) out = state end
Для нашего случая Nb=4, Nk=8, Nr=14.
Как видим из листинга, для AES-256 блок открытого текста представляется в виде двумерного массива state размера 4 на 4, к которому в определенном порядке применяются 4 функции AddRoundKey, SubBytes, ShiftRows, MixColumns. Рассмотрим эти функции подробнее.
1. Функция SubBytes заменяет каждый байт массива state в соответствии с определенной в стандарте таблицей замены

2. Функция ShiftRows циклически сдвигает последние три строки массива state на 1, 2 и 3 позиции соответственно:

Функция MixColumns представляет каждый столбец массива state как многочлен над полем GF(2^8) и умножается на определенный в стандарте многочлен по модулю x^4+1 (Кому от таких слов страшно, лучше посмотреть код =). В стандарте сказано как свести эту операцию к операции умножения матриц. Это мы и будем использовать.
4. Функция AddRoundKey производит XOR каждого столбца массива state с раундовым ключом (о том как получаются раундовые ключи расскажу чуть позже).

Получение массива раундовых ключей происходит следующим образом:
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk) begin word temp i = 0 while (i < Nk) w[i]=word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]) i = i+1 end while i = Nk while (i < Nb * (Nr+1)) temp = w[i-1] if (i mod Nk = 0) temp = SubWord(RotWord(temp)) xor Rcon[i/Nk] else if (Nk > 6 and i mod Nk = 4) temp = SubWord(temp) end if w[i] = w[i-Nk] xor temp i = i+1 end while end
Напомню, что нас интересует только случай AES-256 ( Nb=4, Nk=8, Nr=14).
С описанием алгоритма вроде бы разобрались. Остается только разобраться с режимами работы. Оба рассматриваемых режима работы не требуют программирования обратного преобразования (расшифрования) каждого блока сообщения. Вообще говоря, рассматриваемые режимы очень похожи, разница между ними лишь в том, что в режиме CCM дополнительно обеспечивается аутентификация (проверка подлинности) сообщения.
В режиме CCM информация для аутентификации (имитовставка) получается следующим образом:



где блок B_0 в соответствии с RFC 3610 имеет следующий формат:
byte[] B_0 = new byte[16]; B_0[0] = 0x09; B_0[1] = (byte)(nonce & 0xff); B_0[2] = (byte)((nonce >> 8) & 0xff); B_0[3] = (byte)((nonce >> 16) & 0xff); B_0[4] = (byte)((nonce >> 24) & 0xff); B_0[5] = (byte)((nonce >> 32) & 0xff); B_0[6] = (byte)((nonce >> 40) & 0xff); B_0[7] = (byte)((nonce >> 48) & 0xff); B_0[8] = (byte)((nonce >> 56) & 0xff); B_0[9] = (byte)((messageNumber & 0xff)); B_0[10] = (byte)((messageNumber >> 8) & 0xff); B_0[11] = (byte)((messageNumber >> 16) & 0xff); B_0[12] = (byte)((messageNumber >> 24) & 0xff); B_0[13] = 0x00; B_0[14] = (byte)(input.Length & 0xff); B_0[15] = (byte)((input.Length >> 8) & 0xff);
nonce - 64 бита "случайности"
messageNumber - номер передаваемого сообщения
input.Length - длина передаваемного сообщения
Процесс шифрования описывается следующим образом:

где S_i – i-й блок шифрованного текста, A_i – i-й блок открытого текста, K – ключ шифрования данных (длиной 256 бит).
Первый блок A_0 в соответствии с RFC 3610 имеет следующий формат:
A_temp[0] = 0x01; A_temp[1] = (byte)(nonce & 0xff); A_temp[2] = (byte)((nonce >> 8) & 0xff); A_temp[3] = (byte)((nonce >> 16) & 0xff); A_temp[4] = (byte)((nonce >> 24) & 0xff); A_temp[5] = (byte)((nonce >> 32) & 0xff); A_temp[6] = (byte)((nonce >> 40) & 0xff); A_temp[7] = (byte)((nonce >> 48) & 0xff); A_temp[8] = (byte)((nonce >> 56) & 0xff); A_temp[9] = (byte)((messageNumber & 0xff)); A_temp[10] = (byte)((messageNumber >> 8) & 0xff); A_temp[11] = (byte)((messageNumber >> 16) & 0xff); A_temp[12] = (byte)((messageNumber >> 24) & 0xff); A_temp[13] = 0x00; A_temp[14] = 0x00; A_temp[15] = 0x00;
Процесс шифрования в режиме CTR такой же, как и в режиме CCM. Аутентификация в режиме CTR при шифровании отсутствует.
Итак, когда все разобрано можно приступить непосредственно к программированию. Сразу оговорюсь, что данный код далек от идеального, то есть в нем есть большой простор для оптимизации и т.д. Для начала нам понадобится написать умножение двух многочленов с приведением по модулю
(таким образом задается поле GF(2^8).
Реализуется оно следующим образом:
//получение бита из слова private static ushort ExtractBit(ushort source, ushort number) { if (number < 16) { return (ushort)((source >> number) & 1); } return 0; } //установка бита в слово private static ushort SetBit(ushort source, ushort number, ushort val) { if (number>15) return 0; if (val>1) return 0; if (ExtractBit(source, number) == val) return source; return (ushort)(source ^ (1<<number)); } //умножение двух многочленов с приведением по модулю x^4+x^3+x^2+1 private static byte PolynomsMuliply(byte a, byte b) { ushort result = 0; ushort temp; for (ushort i = 0; i < 15; i++) { temp = 0; for (ushort k = 0; k <= i; k++) { ushort ak = ExtractBit(a, k); ushort bik = ExtractBit(b, (ushort)(i - k)); temp = (ushort) (temp ^ (ak & bik)); } result = SetBit(result, i, temp); } ushort mod = 283; //приведение по модулю втупую =) прибавлением многочлена if (ExtractBit(result, 14) == 1) result = (ushort)(result ^ (mod << 6)); if (ExtractBit(result, 13) == 1) result = (ushort)(result ^ (mod << 5)); if (ExtractBit(result, 12) == 1) result = (ushort)(result ^ (mod << 4)); if (ExtractBit(result, 11) == 1) result = (ushort)(result ^ (mod << 3)); if (ExtractBit(result, 10) == 1) result = (ushort)(result ^ (mod << 2)); if (ExtractBit(result, 9) == 1) result = (ushort)(result ^ (mod << 1)); if (ExtractBit(result, 8) == 1) result = (ushort)(result ^ mod); return (byte)result; }
Основные четыре функции шифра реализуются следующим образом:
private static void MixColumns(ref byte[,] state) { byte[,] new_state = new byte[4, 4]; for (int c = 0; c < 4; c++) { new_state[0, c] = (byte)(PolynomsMuliply(2,state[0,c]) ^ PolynomsMuliply(3,state[1,c]) ^ state[2,c] ^ state[3,c]); new_state[1, c] = (byte)(state[0, c] ^ PolynomsMuliply(2, state[1, c]) ^ PolynomsMuliply(3, state[2, c]) ^ state[3, c]); new_state[2, c] = (byte)(state[0, c] ^ state[1, c] ^ PolynomsMuliply(2, state[2, c]) ^ PolynomsMuliply(3, state[3, c])); new_state[3, c] = (byte)(PolynomsMuliply(3, state[0, c]) ^ state[1, c] ^ state[2, c] ^ PolynomsMuliply(2, state[3, c])); } state = new_state; return; } private static void ShiftRows(ref byte[,] state) { byte temp1 = state[1, 0]; state[1, 0] = state[1, 1]; state[1, 1] = state[1, 2]; state[1, 2] = state[1, 3]; state[1, 3] = temp1; temp1 = state[2, 0]; byte temp2 = state[2, 1]; state[2, 0] = state[2, 2]; state[2, 1] = state[2, 3]; state[2, 2] = temp1; state[2, 3] = temp2; temp1 = state[3, 0]; temp2 = state[3, 1]; byte temp3 = state[3, 2]; state[3, 0] = state[3, 3]; state[3, 1] = temp1; state[3, 2] = temp2; state[3, 3] = temp3; } private static void SubBytes(ref byte[,] state) { byte x; byte y; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { x = (byte)(state[i, j] >> 4); y = (byte)(state[i, j] & 0xf); state[i, j] = S(x, y); } } } private static void AddRoundKey(ref byte[,] state, uint w0, uint w1, uint w2, uint w3 ) { state[0, 0] = (byte)(state[0, 0] ^ (w0 >> 24)); state[1, 0] = (byte)(state[1, 0] ^ ((w0 >> 16) & 0xff)); state[2, 0] = (byte)(state[2, 0] ^ ((w0 >> 8) & 0xff)); state[3, 0] = (byte)(state[3, 0] ^ (w0 & 0xff)); state[0, 1] = (byte)(state[0, 1] ^ (w1 >> 24)); state[1, 1] = (byte)(state[1, 1] ^ ((w1 >> 16) & 0xff)); state[2, 1] = (byte)(state[2, 1] ^ ((w1 >> 8) & 0xff)); state[3, 1] = (byte)(state[3, 1] ^ (w1 & 0xff)); state[0, 2] = (byte)(state[0, 2] ^ (w2 >> 24)); state[1, 2] = (byte)(state[1, 2] ^ ((w2 >> 16) & 0xff)); state[2, 2] = (byte)(state[2, 2] ^ ((w2 >> 8) & 0xff)); state[3, 2] = (byte)(state[3, 2] ^ (w2 & 0xff)); state[0, 3] = (byte)(state[0, 3] ^ (w3 >> 24)); state[1, 3] = (byte)(state[1, 3] ^ ((w3 >> 16) & 0xff)); state[2, 3] = (byte)(state[2, 3] ^ ((w3 >> 8) & 0xff)); state[3, 3] = (byte)(state[3, 3] ^ (w3 & 0xff)) }
В приведенном листинге функция S возвращает значение из таблицы замены.
Теперь опишем операцию получения массива раундовых ключей из ключа шифрования в соответствии с алгоритмом KeyExpansion:
private static uint[] KeyExpansion(byte[] key) { uint[] Rcon = new uint[] { 0,0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000 }; uint[] w = new uint[60]; for (int i = 0; i < 60; i++) w[i] = 0; for (int i = 0; i < 8; i++) { w[i] = (((uint)key[4 * i]) << 24) ^ ((((uint)key[4 * i + 1]) << 16)) ^ (((uint)key[4 * i + 2]) << 8) ^ key[4 * i + 3]; } for (int i = 8; i < 60; i++) { uint temp = w[i - 1]; if ((i % 8) == 0) { temp = SubWord(RotWord(temp)) ^ Rcon[i / 8]; } else if (i % 8 == 4) { temp = SubWord(temp); } w[i] = w[i - 8] ^ temp; } return w; } private static uint SubWord(uint p) { byte p0 = (byte)(p >> 24); byte p1 = (byte)(p >> 16); byte p2 = (byte)(p >> 8); byte p3 = (byte)p; byte x = (byte)(p0 >> 4); byte y = (byte)(p0 & 0x0f); p0 = S(x, y); x = (byte)(p1 >> 4); y = (byte)(p1 & 0x0f); p1 = S(x, y); x = (byte)(p2 >> 4); y = (byte)(p2 & 0x0f); p2 = S(x, y); x = (byte)(p3 >> 4); y = (byte)(p3 & 0x0f); p3 = S(x, y); return ((((uint)p0) << 24) ^ (((uint)p1) << 16) ^ (((uint)p2) << 8) ^ p3); } private static uint RotWord(uint w) { uint temp = w >> 24; temp = (w << 8) ^ temp; return temp; }
Приступим к написанию кода функции шифрования блока открытого текста (алгоритм Cipher из вышеприведенного листинга):
private static void Cipher(byte[,] in_array, out byte[,] out_array, uint[] w) { byte[,] state = in_array; AddRoundKey(ref state, w[0], w[1], w[2], w[3]); for (int round = 1; round <= 13; round++) { SubBytes(ref state); ShiftRows(ref state); MixColumns(ref state); AddRoundKey(ref state, w[round*4], w[round*4+1], w[round*4+2], w[round*4+3]); } SubBytes(ref state); ShiftRows(ref state); AddRoundKey(ref state, w[56], w[57], w[58], w[59]); out_array = state; } private static byte[] AES_Block_Encrypt(byte[] input, uint[] key) { byte[,] output; byte[,] plainBlock = ArrayToSquare(input); Cipher(plainBlock, out output, key); return SquareToArray(output); }
Код функции шифрования в режиме CCM (код функции расшифрования смотри в исходниках):
public static bool AES_CCM_Encrypt(byte[] input, byte[] key, out byte[] output, ulong nonce, uint messageNumber) { if(input.Length < 16) throw new ArgumentOutOfRangeException(); if (input.Length > ((1 << 16) - 1)) throw new ArgumentOutOfRangeException(); //заполняем блок B_0 byte[] B_0 = new byte[16]; B_0[0] = 0x09; B_0[1] = (byte)(nonce & 0xff); B_0[2] = (byte)((nonce >> 8) & 0xff); B_0[3] = (byte)((nonce >> 16) & 0xff); B_0[4] = (byte)((nonce >> 24) & 0xff); B_0[5] = (byte)((nonce >> 32) & 0xff); B_0[6] = (byte)((nonce >> 40) & 0xff); B_0[7] = (byte)((nonce >> 48) & 0xff); B_0[8] = (byte)((nonce >> 56) & 0xff); B_0[9] = (byte)((messageNumber & 0xff)); B_0[10] = (byte)((messageNumber >> 8) & 0xff); B_0[11] = (byte)((messageNumber >> 16) & 0xff); B_0[12] = (byte)((messageNumber >> 24) & 0xff); B_0[13] = 0x00; B_0[14] = (byte)(input.Length & 0xff); B_0[15] = (byte)((input.Length >> 8) & 0xff); //----------------------- byte[] temp; uint[] w = KeyExpansion(key); uint len = (uint)(input.Length / 16); uint rest = (uint)(input.Length % 16); temp = AES_Block_Encrypt(B_0, w); for (int i = 0; i < len; i++) { for (int k = 0; k < 16; k++) { temp[k] = (byte)(temp[k] ^ input[16 * i + k]); } temp = AES_Block_Encrypt(temp, w); } if (rest != 0) { for (int i = 0; i < rest; i++) { temp[i] = (byte)(temp[i] ^ input[16 * len + i]); } temp = AES_Block_Encrypt(temp, w); } byte[] A_temp = new byte[16]; A_temp[0] = 0x01; A_temp[1] = (byte)(nonce & 0xff); A_temp[2] = (byte)((nonce >> 8) & 0xff); A_temp[3] = (byte)((nonce >> 16) & 0xff); A_temp[4] = (byte)((nonce >> 24) & 0xff); A_temp[5] = (byte)((nonce >> 32) & 0xff); A_temp[6] = (byte)((nonce >> 40) & 0xff); A_temp[7] = (byte)((nonce >> 48) & 0xff); A_temp[8] = (byte)((nonce >> 56) & 0xff); A_temp[9] = (byte)((messageNumber & 0xff)); A_temp[10] = (byte)((messageNumber >> 8) & 0xff); A_temp[11] = (byte)((messageNumber >> 16) & 0xff); A_temp[12] = (byte)((messageNumber >> 24) & 0xff); A_temp[13] = 0x00; A_temp[14] = 0x00; A_temp[15] = 0x00; byte[] S_0 = AES_Block_Encrypt(A_temp, w); output = new byte[8 + input.Length]; output[0] = (byte)(messageNumber & 0xff); output[1] = (byte)((messageNumber >> 8) & 0xff); output[2] = (byte)((messageNumber >> 16) & 0xff); output[3] = (byte)((messageNumber >> 24) & 0xff); output[4] = (byte)(S_0[0] ^ temp[0]); output[5] = (byte)(S_0[1] ^ temp[1]); output[6] = (byte)(S_0[2] ^ temp[2]); output[7] = (byte)(S_0[3] ^ temp[3]); for (uint i = 1; i <= len; i++) { A_temp[14] = (byte)(i & 0xff); A_temp[15] = (byte)((i >> 8) & 0xff); S_0 = AES_Block_Encrypt(A_temp, w); for (int k = 0; k < 16; k++) { output[8 + (i-1)*16 + k] = (byte)(input[(i - 1) * 16 + k] ^ S_0[k]); } } if (rest != 0) { A_temp[14] = (byte)((len + 1) & 0xff); A_temp[15] = (byte)(((len + 1) >> 8) & 0xff); S_0 = AES_Block_Encrypt(A_temp, w); for (int k = 0; k < rest; k++) { output[8 + len * 16 + k] = (byte)(input[len * 16 + k] ^ S_0[k]); } } Array.Clear(w, 0, w.Length); return true; }
В режиме CTR функции зашифрования и расшифрования одинаковы. Код функции зашифрования (расшифрования) имеет вид:
// i - номер сообщения и номер блока public static ulong AES_CRT(byte[] input, byte[] key, out byte[] output, ulong nonce, ulong i) { byte[] K_i; byte[,] out_array; uint numblock = (uint)(input.Length / 16); uint rest = (uint)(input.Length % 16); uint[] w = KeyExpansion(key); ulong temp_i = i; byte[] temp; output = new byte[input.Length]; for (int s = 0; s < numblock; s++) { temp = ulongToByteArray(nonce, temp_i); Cipher(ArrayToSquare(temp),out out_array, w); K_i = SquareToArray(out_array); for (int k = 0; k < 16; k++) { output[s * 16 + k] = (byte)(input[s * 16 + k] ^ K_i[k]); } temp_i++; } if (rest != 0) { temp = ulongToByteArray(nonce, temp_i); Cipher(ArrayToSquare(temp), out out_array, w); K_i = SquareToArray(out_array); for (int k = 0; k < rest; k++) { output[numblock * 16 + k] = (byte)(input[numblock * 16 + k] ^ K_i[k]); } temp_i++; } Array.Clear(w, 0, w.Length); return temp_i; }
Вот и все =) Корректность программной реализации можно проверить используя Test Vectors из стандарта FIPS-197. Надеюсь читатель понял, что американский стандарт шифрования не такой уж и сложный для программной реализации. В дальнейшем можно написать класс, реализующий алгоритм шифрования как того требует System.Security.Cryptography, то есть класс, наследующий SymmetricAlgorithm, но это уже тема для отдельной статьи =)
Если что-то непонятно, пиши evgenij.minsk@gmail.com.
Evgenij
WWW: http://plaintext.su
Исходник прилагается:
| Вложение | Размер |
|---|---|
| aes.zip | 4.99 КБ |
- Войдите или зарегистрируйтесь, чтобы получить возможность отправлять комментарии
- 4981 просмотр



Комментарии
9 комментария(ев)Дата: ЧТ, 17/02/2011 - 00:47
Для меня криптография - святое... Жалко только что всё это на C#, а я его не знаю...
Дата: ЧТ, 17/02/2011 - 02:44
Хи-хи )) нет никаких проблем перекодить на С/С++. Дело 15ти минут
Дата: Втр, 15/03/2011 - 21:58
могу только позавидовать тем,для кого это так просто
Дата: СР, 14/12/2011 - 23:52
Дешифрует неверно. Может я где-то не прав?
Дата: ЧТ, 15/12/2011 - 00:00
У тебя в коде:
Два раза применяется AES_Block_Encrypt, то есть открытый текст у тебя просто 2 раза шифруется алгоритмом AES.
Правильно говорить не "дешифрует", а "расшифровывает"!
Дата: ЧТ, 15/12/2011 - 01:34
Вспылил, был не прав
Почему-то думал что тут как и в режиме CCM шифрование равно расшифрованию.
Дата: ЧТ, 15/12/2011 - 05:32
Да, таковы хитрости применения режимов работы алгоритмов
Дата: Втр, 20/12/2011 - 15:41
Мои труды не были напрасны!
]]>AESEncryptor.exe]]>
P.S. Спасибо автору за статью.
Дата: Втр, 20/12/2011 - 16:45