В статье Wolfram Mathematica: знакомство хаброчеловек 8bitjoey познакомил сообщество с отличным математическим пакетом Wolfram Mathematica.Сегодня я продолжу экскурс в данный продукт. Чтобы совместить приятное с полезным, реализуем алгоритм AES при помощи данного продукта.
Вместо введения
Данная статья ориентирована на пользователей, которые уже хоть как-то знакомы с Mathematica. В рассматриваемом пакете очень детальная документация. Для вызова справки о функции, достаточно выделит её и нажать F1. Хорошее пояснение алгоритма AES (с примерами на JavaScript) было сделано в статье Как устроен AES.
Реализация AES
Для начала объявим глобальные переменные: подстановку (S-box), количество раундов (Nr), размер блока (Nb) и ключа (Nk).
Needs["FiniteFields`"];
fld = FiniteFields`GF[2, {1, 1, 0, 1, 1, 0, 0, 0, 1}];
Sbox = {99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254,
215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162,
175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52,
165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154,
7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90,
160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252,
177, 91, 106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251,
67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64,
143, 146, 157, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205,
12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115,
96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11,
219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149,
228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234,
101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198, 232, 221,
116, 31, 75, 189, 139, 138, 112, 62, 181, 102, 72, 3, 246, 14, 97,
53, 87, 185, 134, 193, 29, 158, 225, 248, 152, 17, 105, 217, 142,
148, 155, 30, 135, 233, 206, 85, 40, 223, 140, 161, 137, 13, 191,
230, 66, 104, 65, 153, 45, 15, 176, 84, 187, 22};
Nr = 10;
Nb = 4;
Nk = 4;
Первая строка подключает пакет для работы с конечнечными полями, а вторая объявляет его. {1, 1, 0, 1, 1, 0, 0, 0, 1}=1+x+x^3+x^4+x^8 — неприводимый полином в поле GF(256).
Стоит напомнить, что все переменные в Mathematica глобальные. Для того, чтобы сделать переменную локальной используется функция Module. Ниже представлен код функции Main с тесно с ней связанные.
Rijndael[State_, CipherKey_] := Module[{ExpandedKey, i, tState},
(
tState = State; (*переписываем входное значение state для работы с ним*)
ExpandedKey = KeyExpansion[CipherKey]; (*вызываем функцию разворачивания ключа и получаем массив ключей для всех раундов*)
tState = AddRoundKey[tState, ExpandedKey[[1]]]; (*первое сложение с ключом*)
For[i = 1, i < Nr, i++,
(
tState = RRound[tState, ExpandedKey[[i + 1]]]; (*раундовое преобразование*)
)
];
tState = FinalRRound[tState, ExpandedKey[[Nr + 1]]]; (*финальное преобразование*)
Return[tState];
)
];
Main[] := Module[{},
(
Plaintext = FromDigits["00112233445566778899aabbccddeeff", 16];
Key = FromDigits["000102030405060708090a0b0c0d0e0f", 16];
CipherText = Rijndael[Plaintext, Key];
Print[BaseForm[CipherText, 16]];
Print[CipherText == 16^^69c4e0d86a7b0430d8cdb78070b4c55a];
)
];
Main[];
Уже по привычке любую функцию записываю через Module, даже с пустыми параметрами. Открытый текст (Plaintext ) и ключ (Key), указанные в функции Main, взяты из fips 197 для тестирования кода. Перевод из 16-ой системы в 10-ую можно осуществить двумя способами: через макрос «16^^» или функцию FromDigits.
При написании криптографических алгоритмов в Mathematica часто используются функции IntegerDigits и FromDigits. Первая переводит число в любой базис, а вторая выполняет обратное действие.
State всегда представляет Integer. Это сделано с целью простого понимания алгоритма.
Ниже представлен код функции разворачивания ключа:
KeyExpansion[CipherKey_] := Module[{i, j, k, ExpandedKey},
(
ExpandedKey = Array[#*0 &, Nr + 1]; (*объявляем массив размером Nr + 1 с нулевыми значениями*)
ExpandedKey[[1]] = CipherKey;
For[i = 1, i <= Nr + 1, i++,
(
ExpandedKey[[i]] = IntegerDigits[ExpandedKey[[i]], 2^8, 16]; (*разбиваем ключи на байты*)
ExpandedKey[[i]] = Partition[ExpandedKey[[i]], 4]; (*записываем в виде матрицы*)
)
];
(*Вычисляем rcon*)
Rcon = Array[{#*0, #*0, #*0, #*0} &, Nr];
Rcon[[1, 1]] = 1;
For[i = 2, i <= Nr, i++,
(
Rcon[[i, 1]] = Rcon[[i - 1, 1]]*2;
If[Rcon[[i, 1]] >= 256,
Rcon[[i, 1]] = BitXor[Rcon[[i, 1]], 283]];
)
];
For[i = 2, i <= Nr + 1, i++,
(
ExpandedKey[[i, 1]] = RotateLeft[ExpandedKey[[i - 1, 4]], 1]; (*циклический сдвиг влево на 1 байт*)
(*Блок подстановок*)
For[j = 1, j <= 4, j++,
(
ExpandedKey[[i, 1, j]] = Sbox[[ExpandedKey[[i, 1, j]] + 1]];
)
];
(*Xor с константой*)
ExpandedKey[[i, 1]] =
BitXor[ExpandedKey[[i, 1]], Rcon[[i - 1]],
ExpandedKey[[i - 1, 1]]];
(*Получение оставшихся байтов ключа*)
For[k = 2, k <= 4, k++,
(
ExpandedKey[[i, k]] =
BitXor[ExpandedKey[[i, k - 1]], ExpandedKey[[i - 1, k]]];
)
];
)
];
(*обратное приведение к Integer*)
For[i = 1, i <= Nr + 1, i++,
(
ExpandedKey[[i]] = Flatten[ExpandedKey[[i]]];
ExpandedKey[[i]] = FromDigits[ExpandedKey[[i]], 2^8];
)
];
Return[ExpandedKey]; (*возвращаем массив цикловых ключей*)
)
];
Код прокомментирован, если возникнут вопросы, то задавайте.
RRound[State_, Key_] := Module[{i, tState},
(
tState = State;
tState = ByteSub[tState];
tState = ShiftRow[tState];
tState = MixColumn[tState];
tState = AddRoundKey[tState, Key];
Return[tState];
)
];
FinalRRound[State_, Key_] := Module[{i, tState},
(
tState = State;
tState = ByteSub[tState];
tState = ShiftRow[tState];
tState = AddRoundKey[tState, Key];
Return[tState];
)
];
Функции цикловой (раундовой) функции и конечного преобразования, представленные в данном коде, думаю, не требуют объяснения — они обозначены точно так же, как и в fips 197.
AddRoundKey[State_, RoundKey_] := Module[{tState},
(
tState = BitXor[State, RoundKey];
Return[tState];
)
];
Функция сложения с ключём очень примитивная: необходимо сложитьпо модулю 2 входное значение и ключ. Для этого используем функцию BitXor, которой на вход подаются Integer.
ByteSub[State_] := Module[{i, tState},
(
tState = State;
tState = IntegerDigits[tState, 2^8, 16];
For[i = 1, i <= 16, i++,
(
tState[[i]] = Sbox[[tState[[i]] + 1]];
)
];
tState = FromDigits[tState, 2^8];
Return[tState];
)
];
Функция SubByte состоит из 3 частей:
- разбиение Integer на 16 байтов;
- непосредственно замена входных значений на числа из переменной Sbox;
- объединение байтов обратно в Integer.
ShiftRow[State_] := Module[{tState},
(
tState = State;
tState = IntegerDigits[tState, 2^8, 16];
tState = Partition[tState, 4];
tState = Transpose[tState];
tState[[2]] = RotateLeft[tState[[2]], 1];
tState[[3]] = RotateLeft[tState[[3]], 2];
tState[[4]] = RotateLeft[tState[[4]], 3];
tState = Transpose[tState];
tState = Flatten[tState];
tState = FromDigits[tState, 2^8];
Return[tState];
)
];
Код функции ShiftRow довольно простой. С 1 по 3 строчки — преобразование Integer в матрицу, следующие 3 строки осуществляют сдвиг 1, 2 и 3 байтов соответственно, потом переводим обратно из матрицы в Integer.
И самая интересная, с точки зрения математики, функция MixColumn, которую я прокомментирую непосредственно в коде. Если возникнут вопросы — задавайте.
MixColumn[State_] := Module[{i, j, tState},
(
tState = State;
(*Преобразование Integer в матрицу*)
tState = IntegerDigits[tState, 2^8, 16];
tState = Partition[tState, 4];
tState = Transpose[tState];
(*Матрица из стандатра fips 197*)
M = ({
{2, 3, 1, 1},
{1, 2, 3, 1},
{1, 1, 2, 3},
{3, 1, 1, 2}
});
(*Перевод чисел в элементы поля*)
For[i = 1, i <= 4, i++,
(
For[j = 1, j <= 4, j++,
(
M[[i, j]] = fld[Reverse[IntegerDigits[M[[i, j]], 2, 8]]]; (*разбиваем Integer на биты и переворачиваем*)
tState[[i, j]] =
fld[Reverse[IntegerDigits[tState[[i, j]], 2, 8]]];
)
];
)
];
(*Умножение матрицы на столбец*)
tState = M.tState;
(*Преобразование State к байтам*)
For[i = 1, i <= 4, i++,
(
For[j = 1, j <= 4, j++,
(
If[tState[[i, j]] == 0, Continue[]];
tState[[i, j]] = FromDigits[Reverse[tState[[i, j]][[1]]], 2];
)
];
)
];
(*Обратное преобразование матрицы к Integer*)
tState = Transpose[tState];
tState = Flatten[tState];
tState = FromDigits[tState, 2^8];
Return[tState];
)
];
Выводы
Таким образом, при помощи Mathematica можно с лёгкостью реализовать алгоритмы шифрования, при условии, что знаешь математику (по большей части теорию чисел).
Послесловие
Последний месяц я программирую, используя продукт sage. Причиной перехода послужила недостаточная производительность Mathematica для криптологических потребностей и дороговизна продукта. Менять Mathematica на sage было сложновато, из-за недостаточно развитой встроенной помощи. Но после нескольких дней привыкаешь и всё становится просто. Легко освоить sage будет людям, знающим python.
Если есть вопросы по Mathematica задавайте! По возможноти постараюсь ответить.
Исходный код всего алгоритма можно взять отсюда.
