AES in q

I’m learning q. For starters I decided to implement something familiar. So here is AES-128 in q:

/ AES reference implementation in Q
/ by <>

/ GF(256) ops ============================================================
.q.gadd:{0b sv (0b vs x)<>0b vs y}''                / addition (XOR)
mu3:{x gadd mod[2*x;256] gadd 0x1b*x>0x7f}          / multiply by 0x03
xp3:`byte$mu3 scan 1                                / exp base 0x03
lg3:`byte$0,iasc xp3                                / log base 0x03
ix:{`byte$xp3[(255-lg3 x) mod 255]*x>0}             / 1/x
.q.gmul:{`byte$xp3[((lg3 x) + lg3 y)mod 255]*0<x&y} / multiplication
.q.gmmul:{x ((gadd/)@gmul)\: y}                     / matrix mul

/ SBox ===================================================================
aff:(-1 rotate) scan 1 1 1 1 1 0 0 0                / affine matrix
SBox:0x63 gadd {`byte$2 sv aff gmmul 0b vs x} each ix til 256

/ Tables =================================================================
RCon:0x01020408102040801b366cd8ab4d                 / round constants
SRow:0 1 2 3                                        / ShiftRows offsets
MixE:(-1 rotate) scan 0x02030101                    / MixColumns matrix
MixD:(-1 rotate) scan 0x0e0b0d09                    / InvMixColumns matrix

/ Round ops ==============================================================
InvSubBytes:`byte$iasc SBox
ShiftRows:SRow rotate'
InvShiftRows:(neg SRow) rotate'
MixColumns:MixE gmmul
InvMixColumns:MixD gmmul

/ Key expansion ops ======================================================
fold:@[;4 4#til 16]
mkrk:{[k;rc] t:(rc,0x000000) gadd SubBytes 1 rotate k[3]; t gadd\ k}
KeyExpansion:{[k] rk:enlist k:fold k; flip each rk, k mkrk\ RCon[til 10]}

/ Cipher =================================================================
Round:{AddRoundKey[MixColumns ShiftRows SubBytes x; y]}
  t:AddRoundKey[flip fold t; rk[0]] Round/ rk[1+til 9];
  raze flip AddRoundKey[ShiftRows SubBytes t; rk[10]]}

InvRound:{InvMixColumns AddRoundKey[InvSubBytes InvShiftRows x; y]}
  t:AddRoundKey[flip fold t; rk[10]] InvRound/ rk[9-til 9];
  raze flip AddRoundKey[InvSubBytes InvShiftRows t; rk[0]]}

/ Testvectors ============================================================
tv128:([] k:(); pt:(); ct:())
  0x3243f6a8885a308d313198a2e0370734; 0x3925841d02dc09fbdc118597196a0b32)
  0x00112233445566778899aabbccddeeff; 0x69c4e0d86a7b0430d8cdb78070b4c55a)
  0x00000000000000000000000000000000; 0x0edd33d3c621e546455bd8ba1418bec8)
  0x80000000000000000000000000000000; 0x3ad78e726c1ec02b7ebfe92b23d9ec34)

/ Tests ==================================================================
E:{[k;pt;ct] `Fail`Pass ct~Cipher[KeyExpansion k; pt]}
D:{[k;pt;ct] `Fail`Pass pt~InvCipher[KeyExpansion k; ct]}
test:select Test:i, Encrypt:E'[k;pt;ct], Decrypt:D'[k;pt;ct] from tv128

WordPress mangles 0x and ‘ despite encapsulating the code in <pre>. You can download the program here instead: aes1_q. Remember to rename the file extension to .q.

The implementation follows closely the FIP 197 specifications. It implements both encryption and decryption with test vectors to validate its correctness. It is a concise description of AES-128 although a q/k expert would probably find it verbose.

Credits: The expression to compute XOR was suggested by Attila Vrabecz in response to my query on the KDB+ Personal Developers mailing list.

Posted in k&q. Tags: . Leave a Comment »

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: