⬆️ ⬇️

Implementing AES on Wolfram Mathematica

In the Wolfram Mathematica article : an acquaintance of the 8bitjoey habroman introduced the community to the excellent Wolfram Mathematica mathematical 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 somehow familiar with Mathematica. This package contains very detailed documentation. To call the help of the function, simply select it and press F1. A good explanation of the AES algorithm (with examples in JavaScript) was made in the article How the AES works .

')

AES implementation



First, let's declare global variables: substitution (S-box), number of rounds (Nr), block size (Nb) and key (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; 
    

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;





The first line includes the package for working with finite fields , and the second line announces 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. To make a variable local, the Module function is used. Below is the code of the Main function with closely related functions



 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[]; 
    

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[];



Out of habit, I record any function through the Module, even with empty parameters. The plain text (Plaintext) and key (Key) specified in the Main function are taken from fips 197 for testing the code. Translation from the 16th system to the 10th system can be done in two ways: via the “16 ^^” macro or the FromDigits function.

When writing cryptographic algorithms in Mathematica, the functions IntegerDigits and FromDigits are often used. The first translates the number to any basis, and the second performs the opposite action.

State always represents an integer. This is done for the purpose of simple understanding of the algorithm.



Below is the key code function:

 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]; (*   *) ) ]; 
    

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]; (* *) ) ];



The code is commented, if you have any questions, then ask.



 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]; ) ]; 
    

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]; ) ];



The functions of the cyclic (round) function and the final transformation presented in this code, I think, do not require an explanation - they are designated exactly the same as in fips 197.



 AddRoundKey[State_, RoundKey_] := Module[{tState}, ( tState = BitXor[State, RoundKey]; Return[tState]; ) ]; 
    

AddRoundKey[State_, RoundKey_] := Module[{tState}, ( tState = BitXor[State, RoundKey]; Return[tState]; ) ];



The addition function with the key is very primitive: it is necessary to add the input value and key to module 2. To do this, use the BitXor function, which is fed to the input 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]; ) ]; 
    

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]; ) ];



The SubByte function consists of 3 parts:





 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[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]; ) ];



The ShiftRow function code is pretty simple. From 1 to 3 lines - the conversion of an Integer into a matrix, the next 3 lines shift 1, 2 and 3 bytes respectively, then translate back from the matrix into an Integer.



And from the point of view of mathematics, the most interesting is the MixColumn function, which I will comment on 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]; ) ]; 
    

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]; ) ];





findings



Thus, with the help of Mathematica, you can easily implement encryption algorithms, provided that you know mathematics (for the most part, number theory ).



Afterword



Last month I am programming using the sage product. The reason for the transition was the insufficient Mathematica performance for cryptological needs and the high cost of the product. Changing Mathematica to sage was difficult, due to insufficiently developed integrated help. But after a few days you get used to it and everything becomes simple. Easy to master sage will be people who know python.



If you have questions on Mathematica ask! If possible, I will try to answer.



The source code of the entire algorithm can be taken from here .

Source: https://habr.com/ru/post/123760/



All Articles