July 14, 2011 at 22:59AES implementation on Wolfram Mathematica
In an article by Wolfram Mathematica: Introducing the Haberman, 8bitjoey introduced the community to the excellent Wolfram Mathematica math package. Today I will continue the excursion into this product. To combine business with pleasure, we implement the AES algorithm using this product.
Instead of introducing
This article is aimed at users who are already at least somewhat familiar with Mathematica. The package in question has very detailed documentation. To call help about a function, just select it and press F1. A good explanation of the AES algorithm (with JavaScript examples) was made in the article How AES Works .
AES implementation
First, let's declare global variables: substitution (S-box), number of rounds (Nr), block size (Nb) and key size (Nk). The first line connects the package to work with finite fields , and the second declares it. {1, 1, 0, 1, 1, 0, 0, 0, 1} = 1 + x + x ^ 3 + x ^ 4 + x ^ 8 is an irreducible polynomial in the field GF (256). It is worth recalling that all variables in Mathematica are global. In order to make the variable local, the Module function is used. Below is the code of the Main function with closely related functions. Out of habit, I write any function through Module, even with empty parameters. The plain text (Plaintext) and key (Key) specified in the Main function are taken from fips 197
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;
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[];
to test the code. The transfer from the 16th system to the 10th can be done in two ways: through the macro “16 ^^” or the FromDigits function.
When writing cryptographic algorithms in Mathematica, the IntegerDigits and FromDigits functions are often used. The first translates the number into any basis, and the second performs the opposite action.
State always represents Integer. This is for the purpose of understanding the algorithm.
Below is the code for the key deployment function: The code is commented, if you have questions, then ask. The functions of the cyclic (round) function and the final transformation presented in this code, I think, do not require explanation - they are denoted exactly in the same way as in fips 197.
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];
)
];
AddRoundKey[State_, RoundKey_] := Module[{tState},
(
tState = BitXor[State, RoundKey];
Return[tState];
)
];
The key addition function is very primitive: it is necessary to add the input value and the key by module 2. To do this, we use the BitXor function, which Integer is fed to the input. The SubByte function consists of 3 parts:
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];
)
];
- splitting Integer into 16 bytes;
- directly replacing input values with numbers from the Sbox variable;
- concatenate bytes back to 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 function code is pretty simple. From lines 1 to 3 - the conversion of Integer to a matrix, the next 3 lines shift 1, 2 and 3 bytes, respectively, then translate it back from the matrix to Integer.
And the most interesting, from the point of view of mathematics, MixColumn function, which I will comment directly in the code. If you have any questions, ask.
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];
)
];
conclusions
Thus, using Mathematica, you can easily implement encryption algorithms, provided that you know the mathematics (for the most part number theory ).
Afterword
I have been programming the last month using the sage product . The reason for the transition was the insufficient performance of Mathematica for cryptological needs and the high cost of the product. Changing Mathematica to sage was a bit complicated due to the underdeveloped built-in help. But after several days you get used to it and everything becomes simple. Easy to learn sage will be for people who know python.
If you have questions about Mathematica, ask! If possible, I will try to answer.
The source code of the entire algorithm can be taken from here .
