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 <thesweeheng@gmail.com>

/ 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 ==============================================================
AddRoundKey:gadd
SubBytes:SBox
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]}
Cipher:{[rk;t]
  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]}
InvCipher:{[rk;t]
  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:())
tv128,:`k`pt`ct!(
  0x2b7e151628aed2a6abf7158809cf4f3c;
  0x3243f6a8885a308d313198a2e0370734; 0x3925841d02dc09fbdc118597196a0b32)
tv128,:`k`pt`ct!(
  0x000102030405060708090a0b0c0d0e0f;
  0x00112233445566778899aabbccddeeff; 0x69c4e0d86a7b0430d8cdb78070b4c55a)
tv128,:`k`pt`ct!(
  0x80000000000000000000000000000000;
  0x00000000000000000000000000000000; 0x0edd33d3c621e546455bd8ba1418bec8)
tv128,:`k`pt`ct!(
  0x00000000000000000000000000000000;
  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.

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: