So I was bored yesterday which is always a dangerous thing. I studied up on the AES key expansion algorithm and it turned out to be just as simple as the rest of the algorithm. I probably should have guessed that would be the case.
Setting aside my embarassing inability to keep byte orders and word orders straight (which led to about a half-dozen complete re-writes of the below code) I worked up some code to perform the expansion for 128-bit keys inputs. I've tested this against the example key in the FIPS-197 standard as well as some random keys I punched into an online calculator. Here's the code:
Code: Select all
@echo off
::define a Carriage Return string, only useable as !CR!
for /f %%a in ('copy /Z "%~dpf0" nul') do set "CR=%%a"
::define a Line Feed (newline) string (normally only used as !LF!)
set LF=^
::Above 2 blank lines are required - do not remove
::define a Line Feed string that can be used as %xLF%
set ^"xLF=^^^%LF%%LF%^%LF%%LF%"
::define a newline with line continuation
set ^"\n=^^^%LF%%LF%^%LF%%LF%^^"
::define 'macro_call' and 'Num2Hex' macros
set macro_Call=for /f "tokens=1-26" %%a in
set macro.Num2Hex=do (%\n%
setlocal enableDelayedExpansion%\n%
set /a "dec=(%%~a)"%\n%
if defined hex set "hex="%\n%
set "map=0123456789ABCDEF"%\n%
for /l %%n in (1,1,8) do (%\n%
set /a "d=dec&15,dec>>=4"%\n%
for %%d in (!d!) do set "hex=!map:~%%d,1!!hex!"%\n%
)%\n%
set hex=!hex:00=,!%\n%
for /f "tokens=* delims=," %%v in ("!hex!") do set "hex=%%v"^&if not defined hex set "hex=00"%\n%
for %%v in (!hex!) do endlocal^&if "%%~b" neq "" (set "%%~b=%%v") else %echo%%%v%\n%
)
SETLOCAL ENABLEDELAYEDEXPANSION
:: Pre-computed Rijndael S-box
set /a Sbox[0]=0x63 & set /a Sbox[1]=0x7c & set /a Sbox[2]=0x77 & set /a Sbox[3]=0x7b & set /a Sbox[4]=0xf2
set /a Sbox[5]=0x6b & set /a Sbox[6]=0x6f & set /a Sbox[7]=0xc5 & set /a Sbox[8]=0x30 & set /a Sbox[9]=0x01
set /a Sbox[10]=0x67 & set /a Sbox[11]=0x2b & set /a Sbox[12]=0xfe & set /a Sbox[13]=0xd7 & set /a Sbox[14]=0xab
set /a Sbox[15]=0x76 & set /a Sbox[16]=0xca & set /a Sbox[17]=0x82 & set /a Sbox[18]=0xc9 & set /a Sbox[19]=0x7d
set /a Sbox[20]=0xfa & set /a Sbox[21]=0x59 & set /a Sbox[22]=0x47 & set /a Sbox[23]=0xf0 & set /a Sbox[24]=0xad
set /a Sbox[25]=0xd4 & set /a Sbox[26]=0xa2 & set /a Sbox[27]=0xaf & set /a Sbox[28]=0x9c & set /a Sbox[29]=0xa4
set /a Sbox[30]=0x72 & set /a Sbox[31]=0xc0 & set /a Sbox[32]=0xb7 & set /a Sbox[33]=0xfd & set /a Sbox[34]=0x93
set /a Sbox[35]=0x26 & set /a Sbox[36]=0x36 & set /a Sbox[37]=0x3f & set /a Sbox[38]=0xf7 & set /a Sbox[39]=0xcc
set /a Sbox[40]=0x34 & set /a Sbox[41]=0xa5 & set /a Sbox[42]=0xe5 & set /a Sbox[43]=0xf1 & set /a Sbox[44]=0x71
set /a Sbox[45]=0xd8 & set /a Sbox[46]=0x31 & set /a Sbox[47]=0x15 & set /a Sbox[48]=0x04 & set /a Sbox[49]=0xc7
set /a Sbox[50]=0x23 & set /a Sbox[51]=0xc3 & set /a Sbox[52]=0x18 & set /a Sbox[53]=0x96 & set /a Sbox[54]=0x05
set /a Sbox[55]=0x9a & set /a Sbox[56]=0x07 & set /a Sbox[57]=0x12 & set /a Sbox[58]=0x80 & set /a Sbox[59]=0xe2
set /a Sbox[60]=0xeb & set /a Sbox[61]=0x27 & set /a Sbox[62]=0xb2 & set /a Sbox[63]=0x75 & set /a Sbox[64]=0x09
set /a Sbox[65]=0x83 & set /a Sbox[66]=0x2c & set /a Sbox[67]=0x1a & set /a Sbox[68]=0x1b & set /a Sbox[69]=0x6e
set /a Sbox[70]=0x5a & set /a Sbox[71]=0xa0 & set /a Sbox[72]=0x52 & set /a Sbox[73]=0x3b & set /a Sbox[74]=0xd6
set /a Sbox[75]=0xb3 & set /a Sbox[76]=0x29 & set /a Sbox[77]=0xe3 & set /a Sbox[78]=0x2f & set /a Sbox[79]=0x84
set /a Sbox[80]=0x53 & set /a Sbox[81]=0xd1 & set /a Sbox[82]=0x00 & set /a Sbox[83]=0xed & set /a Sbox[84]=0x20
set /a Sbox[85]=0xfc & set /a Sbox[86]=0xb1 & set /a Sbox[87]=0x5b & set /a Sbox[88]=0x6a & set /a Sbox[89]=0xcb
set /a Sbox[90]=0xbe & set /a Sbox[91]=0x39 & set /a Sbox[92]=0x4a & set /a Sbox[93]=0x4c & set /a Sbox[94]=0x58
set /a Sbox[95]=0xcf & set /a Sbox[96]=0xd0 & set /a Sbox[97]=0xef & set /a Sbox[98]=0xaa & set /a Sbox[99]=0xfb
set /a Sbox[100]=0x43 & set /a Sbox[101]=0x4d & set /a Sbox[102]=0x33 & set /a Sbox[103]=0x85 & set /a Sbox[104]=0x45
set /a Sbox[105]=0xf9 & set /a Sbox[106]=0x02 & set /a Sbox[107]=0x7f & set /a Sbox[108]=0x50 & set /a Sbox[109]=0x3c
set /a Sbox[110]=0x9f & set /a Sbox[111]=0xa8 & set /a Sbox[112]=0x51 & set /a Sbox[113]=0xa3 & set /a Sbox[114]=0x40
set /a Sbox[115]=0x8f & set /a Sbox[116]=0x92 & set /a Sbox[117]=0x9d & set /a Sbox[118]=0x38 & set /a Sbox[119]=0xf5
set /a Sbox[120]=0xbc & set /a Sbox[121]=0xb6 & set /a Sbox[122]=0xda & set /a Sbox[123]=0x21 & set /a Sbox[124]=0x10
set /a Sbox[125]=0xff & set /a Sbox[126]=0xf3 & set /a Sbox[127]=0xd2 & set /a Sbox[128]=0xcd & set /a Sbox[129]=0x0c
set /a Sbox[130]=0x13 & set /a Sbox[131]=0xec & set /a Sbox[132]=0x5f & set /a Sbox[133]=0x97 & set /a Sbox[134]=0x44
set /a Sbox[135]=0x17 & set /a Sbox[136]=0xc4 & set /a Sbox[137]=0xa7 & set /a Sbox[138]=0x7e & set /a Sbox[139]=0x3d
set /a Sbox[140]=0x64 & set /a Sbox[141]=0x5d & set /a Sbox[142]=0x19 & set /a Sbox[143]=0x73 & set /a Sbox[144]=0x60
set /a Sbox[145]=0x81 & set /a Sbox[146]=0x4f & set /a Sbox[147]=0xdc & set /a Sbox[148]=0x22 & set /a Sbox[149]=0x2a
set /a Sbox[150]=0x90 & set /a Sbox[151]=0x88 & set /a Sbox[152]=0x46 & set /a Sbox[153]=0xee & set /a Sbox[154]=0xb8
set /a Sbox[155]=0x14 & set /a Sbox[156]=0xde & set /a Sbox[157]=0x5e & set /a Sbox[158]=0x0b & set /a Sbox[159]=0xdb
set /a Sbox[160]=0xe0 & set /a Sbox[161]=0x32 & set /a Sbox[162]=0x3a & set /a Sbox[163]=0x0a & set /a Sbox[164]=0x49
set /a Sbox[165]=0x06 & set /a Sbox[166]=0x24 & set /a Sbox[167]=0x5c & set /a Sbox[168]=0xc2 & set /a Sbox[169]=0xd3
set /a Sbox[170]=0xac & set /a Sbox[171]=0x62 & set /a Sbox[172]=0x91 & set /a Sbox[173]=0x95 & set /a Sbox[174]=0xe4
set /a Sbox[175]=0x79 & set /a Sbox[176]=0xe7 & set /a Sbox[177]=0xc8 & set /a Sbox[178]=0x37 & set /a Sbox[179]=0x6d
set /a Sbox[180]=0x8d & set /a Sbox[181]=0xd5 & set /a Sbox[182]=0x4e & set /a Sbox[183]=0xa9 & set /a Sbox[184]=0x6c
set /a Sbox[185]=0x56 & set /a Sbox[186]=0xf4 & set /a Sbox[187]=0xea & set /a Sbox[188]=0x65 & set /a Sbox[189]=0x7a
set /a Sbox[190]=0xae & set /a Sbox[191]=0x08 & set /a Sbox[192]=0xba & set /a Sbox[193]=0x78 & set /a Sbox[194]=0x25
set /a Sbox[195]=0x2e & set /a Sbox[196]=0x1c & set /a Sbox[197]=0xa6 & set /a Sbox[198]=0xb4 & set /a Sbox[199]=0xc6
set /a Sbox[200]=0xe8 & set /a Sbox[201]=0xdd & set /a Sbox[202]=0x74 & set /a Sbox[203]=0x1f & set /a Sbox[204]=0x4b
set /a Sbox[205]=0xbd & set /a Sbox[206]=0x8b & set /a Sbox[207]=0x8a & set /a Sbox[208]=0x70 & set /a Sbox[209]=0x3e
set /a Sbox[210]=0xb5 & set /a Sbox[211]=0x66 & set /a Sbox[212]=0x48 & set /a Sbox[213]=0x03 & set /a Sbox[214]=0xf6
set /a Sbox[215]=0x0e & set /a Sbox[216]=0x61 & set /a Sbox[217]=0x35 & set /a Sbox[218]=0x57 & set /a Sbox[219]=0xb9
set /a Sbox[220]=0x86 & set /a Sbox[221]=0xc1 & set /a Sbox[222]=0x1d & set /a Sbox[223]=0x9e & set /a Sbox[224]=0xe1
set /a Sbox[225]=0xf8 & set /a Sbox[226]=0x98 & set /a Sbox[227]=0x11 & set /a Sbox[228]=0x69 & set /a Sbox[229]=0xd9
set /a Sbox[230]=0x8e & set /a Sbox[231]=0x94 & set /a Sbox[232]=0x9b & set /a Sbox[233]=0x1e & set /a Sbox[234]=0x87
set /a Sbox[235]=0xe9 & set /a Sbox[236]=0xce & set /a Sbox[237]=0x55 & set /a Sbox[238]=0x28 & set /a Sbox[239]=0xdf
set /a Sbox[240]=0x8c & set /a Sbox[241]=0xa1 & set /a Sbox[242]=0x89 & set /a Sbox[243]=0x0d & set /a Sbox[244]=0xbf
set /a Sbox[245]=0xe6 & set /a Sbox[246]=0x42 & set /a Sbox[247]=0x68 & set /a Sbox[248]=0x41 & set /a Sbox[249]=0x99
set /a Sbox[250]=0x2d & set /a Sbox[251]=0x0f & set /a Sbox[252]=0xb0 & set /a Sbox[253]=0x54 & set /a Sbox[254]=0xbb
set /a Sbox[255]=0x16
:: Pre-computed round constants for generator algorithm
set /a RC[1]=0x01 & set /a RC[2]=0x02 & set /a RC[3]=0x04 & set /a RC[4]=0x08 & set /a RC[5]=0x10
set /a RC[6]=0x20 & set /a RC[7]=0x40 & set /a RC[8]=0x80 & set /a RC[9]=0x1b & set /a RC[10]=0x36
:: Assume a 128-bit key obtained as an input parameter. This test key is from the FIPS-197 standard.
set "key=2b7e151628aed2a6abf7158809cf4f3c"
:: Process key from left to right as bytes 0 through 15
:: Rearrange the key into 4 words of 4 bytes each and insert as columns in a state matrix
:: W0 W1 W2 W3 key[r][c] definitions
:: ------------------- ---------------------
:: B0 | B4 | B8 | B12 0,0 | 0,1 | 0,2 | 0,3
:: B1 | B5 | B9 | B13 = 1,0 | 1,1 | 1,2 | 1,3
:: B2 | B6 | B10| B14 2,0 | 2,1 | 2,2 | 2,3
:: B3 | B7 | B11| B15 3,0 | 3,1 | 3,2 | 3,3
set /a "key[0][0]=0x!key:~0,2!"
set /a "key[1][0]=0x!key:~2,2!"
set /a "key[2][0]=0x!key:~4,2!"
set /a "key[3][0]=0x!key:~6,2!"
set /a "key[0][1]=0x!key:~8,2!"
set /a "key[1][1]=0x!key:~10,2!"
set /a "key[2][1]=0x!key:~12,2!"
set /a "key[3][1]=0x!key:~14,2!"
set /a "key[0][2]=0x!key:~16,2!"
set /a "key[1][2]=0x!key:~18,2!"
set /a "key[2][2]=0x!key:~20,2!"
set /a "key[3][2]=0x!key:~22,2!"
set /a "key[0][3]=0x!key:~24,2!"
set /a "key[1][3]=0x!key:~26,2!"
set /a "key[2][3]=0x!key:~28,2!"
set /a "key[3][3]=0x!key:~30,2!"
:: Display input key (round 0 key) to verify proper translation into state matrix
set /p ans="round 0 key: " <nul
FOR /L %%a IN (0,1,3) DO FOR /L %%b IN (0,1,3) DO (
%macro_call% ("!key[%%b][%%a]! hex") %macro.Num2Hex%
set /p ans="!hex!" <nul
)
echo.
:: A 128-bit key dictates 10 rounds so we need to expand 10*4=40 additional words for round keys
FOR /L %%a IN (4,1,43) DO (
set /a mod=%%a %% 4
:: If this is the first word of a new round key, start the generator algorithm
IF !mod!==0 (
set /a lastword=%%a-1
FOR %%b IN (!lastword!) DO (
:: First step is a one byte circular left shift of the previous word's values
set tempword[0]=!key[1][%%b]!
set tempword[1]=!key[2][%%b]!
set tempword[2]=!key[3][%%b]!
set tempword[3]=!key[0][%%b]!
:: Next we substitute all bytes per the pre-computed S-box
FOR /L %%c IN (0,1,3) DO FOR %%d IN (!tempword[%%c]!) DO set /a tempword[%%c]=!Sbox[%%d]!
:: Then we XOR the first byte with this round's pre-computed round constant
set /a round=%%a/4
FOR %%c IN (!round!) DO (
set /a key[0][%%a]=!tempword[0]!^^^^!RC[%%c]!
set key[1][%%a]=!tempword[1]!
set key[2][%%a]=!tempword[2]!
set key[3][%%a]=!tempword[3]!
)
)
:: Generator algorithm complete. Now we XOR the result with the first word of the last round
set /a last=%%a-4
FOR %%b IN (!last!) DO (
set /a key[0][%%a]=!key[0][%%b]!^^^^!key[0][%%a]!
set /a key[1][%%a]=!key[1][%%b]!^^^^!key[1][%%a]!
set /a key[2][%%a]=!key[2][%%b]!^^^^!key[2][%%a]!
set /a key[3][%%a]=!key[3][%%b]!^^^^!key[3][%%a]!
)
)
:: The 2nd through 4th words in each round are simply formed by XOR operations between%\n%
the immediately previous word and the word in the same position from the previous round
IF NOT !mod!==0 (
set /a first=%%a-1
set /a second=%%a-4
FOR %%b IN (!first!) DO FOR %%c IN (!second!) DO (
set /a key[0][%%a]=!key[0][%%b]!^^^^!key[0][%%c]!
set /a key[1][%%a]=!key[1][%%b]!^^^^!key[1][%%c]!
set /a key[2][%%a]=!key[2][%%b]!^^^^!key[2][%%c]!
set /a key[3][%%a]=!key[3][%%b]!^^^^!key[3][%%c]!
)
)
)
:: Display the full set of expanded keys for rounds 1 through 10
FOR /L %%a IN (4,4,40) DO (
set /a round=%%a/4
set /p ans="round !round! key: " <nul
set /a n=%%a+1 & set /a nn=%%a+2 & set /a nnn=%%a+3
FOR /L %%b IN (0,1,3) DO (
%macro_call% ("!key[%%b][%%a]! hex") %macro.Num2Hex%
set /p ans="!hex!" <nul
)
FOR %%b IN (!n!) DO FOR /L %%c IN (0,1,3) DO (
%macro_call% ("!key[%%c][%%b]! hex") %macro.Num2Hex%
set /p ans="!hex!" <nul
)
FOR %%b IN (!nn!) DO FOR /L %%c IN (0,1,3) DO (
%macro_call% ("!key[%%c][%%b]! hex") %macro.Num2Hex%
set /p ans="!hex!" <nul
)
FOR %%b IN (!nnn!) DO FOR /L %%c IN (0,1,3) DO (
%macro_call% ("!key[%%c][%%b]! hex") %macro.Num2Hex%
set /p ans="!hex!" <nul
)
echo.
)
GOTO:EOF
And the results:
Code: Select all
C:\BTP\AES>aes
round 0 key: 2B7E151628AED2A6ABF7158809CF4F3C
round 1 key: A0FAFE1788542CB123A339392A6C7605
round 2 key: F2C295F27A96B9435935807A7359F67F
round 3 key: 3D80477D4716FE3E1E237E446D7A883B
round 4 key: EF44A541A8525B7FB671253BDB0BAD00
round 5 key: D4D1C6F87C839D87CAF2B8BC11F915BC
round 6 key: 6D88A37A110B3EFDDBF98641CA0093FD
round 7 key: 4E54F70E5F5FC9F384A64FB24EA6DC4F
round 8 key: EAD27321B58DBAD2312BF5607F8D292F
round 9 key: AC7766F319FADC2128D12941575C006E
round 10 key: D014F9A8C9EE2589E13F0CC8B6630CA6
C:\BTP\AES>
The code looks longer than it really is, given all the setup and declarations at the top, and the loop to display the output at the bottom. The core logic is surprisingly short and simple. It could stand to be optimized, but I was so excited it was finally working I wanted to post it.
As an added bonus, since the Sbox is already defined, that takes care of one of the additional four operations required to actually perform an encryption, ie: SubBytes(). ShiftRows() and AddRoundKey() are extremely simple to code, so I just have to figure out MixColumns() and we'll be in the encoding business. I'm not looking forward to typing out the inverse Sbox for decryption when the time comes, but this is actually somewhat entertaining so far. I might have to find some time to be bored again next week...
