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 = Innocent
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 >> Cool & 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 >> Cool & 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 >> Cool & 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 >> Cool & 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 >> Cool & 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< }

//умножение двух многочленов с приведением по модулю 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, Cool == 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 >> Cool & 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 >> Cool & 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 >> Cool & 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 >> Cool & 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]) << Cool ^ key[4 * i + 3];
}
for (int i = 8; i < 60; i++)
{
uint temp = w[i - 1];
if ((i % Cool == Innocent
{
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) << Cool ^ p3);
}

private static uint RotWord(uint w)
{
uint temp = w >> 24;
temp = (w << Cool ^ 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 >> Cool & 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 >> Cool & 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 >> Cool & 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 != Innocent
{
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 >> Cool & 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 >> Cool & 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 >> Cool & 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 >> Cool & 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 != Innocent
{
A_temp[14] = (byte)((len + 1) & 0xff);
A_temp[15] = (byte)(((len + 1) >> Cool & 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 != Innocent
{
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.zip4.99 КБ

Комментарии

9 комментария(ев)
аватар: Кирилл Щербатов
Кирилл Щербатов
Дата: ЧТ, 17/02/2011 - 00:47
Звание: Энтузиаст
Сообщений: 296

Для меня криптография - святое... Жалко только что всё это на C#, а я его не знаю...

аватар: Evgenij
Evgenij
Дата: ЧТ, 17/02/2011 - 02:44
Звание: Посвященный
Сообщений: 310

Хи-хи )) нет никаких проблем перекодить на С/С++. Дело 15ти минут Smile

аватар: Enchantress
Enchantress
Дата: Втр, 15/03/2011 - 21:58
Звание: Наблюдатель
Сообщений: 1

могу только позавидовать тем,для кого это так просто Smile

аватар: Игорь Стародынов
Игорь Стародынов
Дата: СР, 14/12/2011 - 23:52
Звание: Наблюдатель
Сообщений: 4

private void button_GO_Click(object sender, RoutedEventArgs e) { string KeyString = textBox_Key.Text; byte[] Key = new byte[32]; for (byte i = 0; i < 32; i++) { Key[i] = byte.Parse(KeyString.Substring(i*2, 2), System.Globalization.NumberStyles.AllowHexSpecifier); }

string InputString = textBox_Input.Text;
byte[] Input = new byte[16];
for (byte i = 0; i < 16; i++)
{
Input[i] = byte.Parse(InputString.Substring(i*2, 2), System.Globalization.NumberStyles.AllowHexSpecifier);
}

byte[] Crypted = _AES.AES_Block_Encrypt(Input, _AES.KeyExpansion(Key));

byte[] Uncrypted = _AES.AES_Block_Encrypt(Crypted, _AES.KeyExpansion(Key));
string resuult = string.Empty;
for (byte i = 0; i < 16; i++)
{
resuult += string.Format("{0:X}",Uncrypted[i]);
}
textBox_Output.Text = resuult;
}

Дешифрует неверно. Может я где-то не прав?

аватар: Evgenij
Evgenij
Дата: ЧТ, 15/12/2011 - 00:00
Звание: Посвященный
Сообщений: 310

У тебя в коде:

byte[] Crypted = _AES.AES_Block_Encrypt(Input, _AES.KeyExpansion(Key)); byte[] Uncrypted = _AES.AES_Block_Encrypt(Crypted, _AES.KeyExpansion(Key));

Два раза применяется AES_Block_Encrypt, то есть открытый текст у тебя просто 2 раза шифруется алгоритмом AES.

Правильно говорить не "дешифрует", а "расшифровывает"! Wink

аватар: Игорь Стародынов
Игорь Стародынов
Дата: ЧТ, 15/12/2011 - 01:34
Звание: Наблюдатель
Сообщений: 4

Вспылил, был не прав Smile
Почему-то думал что тут как и в режиме CCM шифрование равно расшифрованию.

аватар: Evgenij
Evgenij
Дата: ЧТ, 15/12/2011 - 05:32
Звание: Посвященный
Сообщений: 310

Да, таковы хитрости применения режимов работы алгоритмов Smile

аватар: Игорь Стародынов
Игорь Стародынов
Дата: Втр, 20/12/2011 - 15:41
Звание: Наблюдатель
Сообщений: 4

Мои труды не были напрасны!
]]>AESEncryptor.exe]]>

P.S. Спасибо автору за статью.

аватар: Evgenij
Evgenij
Дата: Втр, 20/12/2011 - 16:45
Звание: Посвященный
Сообщений: 310

Smile Пожалуйста