share/contrib/gf/aes.mac

   1
   2 /*
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; either version 2 of the License, or
   6    (at your option) any later version.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12
  13    You should have received a copy of the GNU General Public License
  14    along with this program; if not, write to the Free Software
  15    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  16    MA 02110-1301, USA.
  17
  18
  19 **** AES en/decryption *********************************************************
  20
  21    Copyright Volker van Nek, 2012 - 2016
  22
  23
  24    This file shows the polynomial aspects of the AES algorithm and its functions
  25    repeatedly convert bytes to polynomials and vice versa. The additional file
  26    gf/aes2.mac directly works at byte level.
  27
  28    In this file states are implemented as 4x4 matrices.
  29
  30    The examples at the bottom of this file are taken from the AES specification
  31    document (URL see below). One of these is also demonstrated in the excellent
  32    Rijndael_Animation_v4_en.swf (http://www.formaestudio.com/rijndaelinspector/)
  33    which I highly recommend to set next to this code.
  34
  35
  36    June, 2015: New user interface.
  37    The functions make_state and coerce_state provide flexible support for
  38    different data types. States can be build from octet-strings, integers and
  39    lists of octets and can be coerced back to these three types.
  40    The new interface is based on new functions in share/stringproc. So you
  41    should have installed Maxima version 5.37 or higher.
  42
  43    March, 2016: mix_columns polynomial version added.
  44    The abstract polynomial description of the mix_columns step is added as
  45    mix_columns_2 and inv_mix_columns_2. If cipher or inv_cipher should use these
  46    alternative versions the code of cipher resp. inv_cipher has to be changed
  47    accordingly.
  48 */
  49
  50
  51 /* sub_bytes **************************************************************** */
  52
  53 %_byte_sub[byte] := block([poly, inv, p1, p2],
  54    gf_minimal_set(2, x^8+x^4+x^3+x+1),
  55    poly : gf_n2p(byte),
  56    inv : if poly = 0 then 0 else gf_inv(poly),
  57
  58    gf_minimal_set(2, x^8+1),
  59    p1 : x^4+x^3+x^2+x+1,
  60    p2 : x^6+x^5+x+1,
  61    poly : gf_add(gf_mult(p1, inv), p2),
  62    gf_p2n(poly) )$
  63
  64 for byte:0 thru 255. do %_byte_sub[byte]$
  65
  66 sub_bytes(state) := matrixmap(lambda([byte], %_byte_sub[byte]), state)$
  67
  68
  69 /* inv_sub_bytes ************************************************************ */
  70
  71 %_inv_byte_sub[byte] := block([poly, inv, p1, p2],
  72    gf_minimal_set(2, x^8+1),
  73    poly : gf_n2p(byte),
  74    p1 : x^4+x^3+x^2+x+1,
  75    p2 : x^6+x^5+x+1,
  76    poly : gf_div(gf_sub(poly, p2), p1),
  77
  78    gf_minimal_set(2, x^8+x^4+x^3+x+1),
  79    inv : if poly = 0 then 0 else gf_inv(poly),
  80    gf_p2n(inv) )$
  81
  82 for byte:0 thru 255. do %_inv_byte_sub[byte]$
  83
  84 inv_sub_bytes(state) := matrixmap(lambda([byte], %_inv_byte_sub[byte]), state)$
  85
  86
  87 /* shift_rows *************************************************************** */
  88
  89 rotate(row, i) := append(rest(row, i), rest(row, i-4))$
  90
  91 shift_rows(state) := apply('matrix, create_list(rotate(state[i], i-1), i,1,4))$
  92
  93
  94 /* inv_shift_rows *********************************************************** */
  95
  96 inv_rotate(row, i) := append(rest(row, 4-i), rest(row, -i))$
  97
  98 inv_shift_rows(M) := apply('matrix, create_list(inv_rotate(M[i], i-1), i,1,4))$
  99
 100
 101 /* mix_columns ************************************************************** */
 102
 103 gf_set_data(2, x^8+x^4+x^3+x+1)$ /* gf_invert_by_lu (see below) needs a field */
 104
 105 mat_n2p(num_mat) := matrixmap('gf_n2p, num_mat)$
 106 mat_p2n(poly_mat) := matrixmap('gf_p2n, poly_mat)$
 107
 108 %_MIX_COLUMNS : mat_n2p( matrix(
 109    [2, 3, 1, 1],
 110    [1, 2, 3, 1],
 111    [1, 1, 2, 3],
 112    [3, 1, 1, 2] ))$
 113
 114 mix_columns(state) := block([mixed],
 115    state : mat_n2p(state),
 116    mixed : matrix(),
 117    for i:1 thru 4 do
 118       mixed : addcol(mixed, gf_matmult(%_MIX_COLUMNS, col(state, i))),
 119    mat_p2n(mixed) )$
 120
 121
 122 /* mix_columns (polynomial version) ***************************************** */
 123
 124 ef_minimal_set(x^4+1)$ /* needs gf_set_data(2, x^8+x^4+x^3+x+1)$ */
 125
 126 aes_p2c(p) := transpose(reverse(ef_p2l(p,4)))$       /* poly to column vector */
 127 aes_c2p(c) := ef_l2p(reverse(first(transpose(c))))$  /* column vector to poly */
 128
 129 %_p3 : 3*x^3+x^2+x+2$
 130
 131 mix_columns_2(state) := block([mixed],
 132    mixed : matrix(),
 133    for i:1 thru 4 do
 134       mixed : addcol(mixed, aes_p2c(ef_mult(%_p3, aes_c2p(col(state, i))))),
 135    mixed )$
 136
 137
 138 /* inv_mix_columns ********************************************************** */
 139
 140 %_INV_MIX_COLUMNS : gf_invert_by_lu(%_MIX_COLUMNS)$
 141
 142 inv_mix_columns(state) := block([mixed],
 143    state : mat_n2p(state),
 144    mixed : matrix(),
 145    for i:1 thru 4 do
 146       mixed : addcol(mixed, gf_matmult(%_INV_MIX_COLUMNS, col(state, i))),
 147    mat_p2n(mixed) )$
 148
 149
 150 /* inv_mix_columns (polynomial version) ************************************* */
 151
 152 %_p3_inv : ef_inv(%_p3)$
 153
 154 inv_mix_columns_2(state) := block([mixed],
 155    mixed : matrix(),
 156    for i:1 thru 4 do
 157       mixed : addcol(mixed, aes_p2c(ef_mult(%_p3_inv, aes_c2p(col(state, i))))),
 158    mixed )$
 159
 160
 161 /* add_round_key ************************************************************ */
 162
 163 add_round_key(state, key) :=
 164    matrixmap('?logxor, state, key)$
 165 /* with polynomial addition:
 166    mat_p2n( gf_matadd( mat_n2p(state), mat_n2p(key) ))$
 167 */
 168
 169
 170 /* key_expansion ************************************************************ */
 171
 172 %_rcon : addrow(
 173    matrix([1, 2, 4, 8, 16., 32., 64., 128., 27., 54.]),
 174    zeromatrix(3, 10.) )$
 175
 176 rot_word(col) := addrow(submatrix(1, col), col[1])$
 177
 178 key_expansion1(col1, col4, i) := block([rcon_col],
 179    col1 : mat_n2p(col1),
 180    col4 : matrixmap(lambda([byte], %_byte_sub[byte]), rot_word(col4)),
 181    col4 : mat_n2p(col4),
 182    rcon_col : mat_n2p(col(%_rcon, i)),
 183    mat_p2n( gf_matadd(col1, col4, rcon_col) ))$
 184
 185 key_expansion2(col_i, col_j) :=
 186    mat_p2n( gf_matadd( mat_n2p(col_i), mat_n2p(col_j) ))$
 187
 188 next_round_key(old, n) := block([new],
 189    new : key_expansion1(col(old, 1), col(old, 4), n),
 190    for i:2 thru 4 do
 191       new : addcol(new, key_expansion2(col(old, i), col(new, i-1))),
 192    new )$
 193
 194 %_round_key : make_array(any, 11.)$
 195
 196 key_expansion(key) := (
 197    kill(round_key),
 198    %_round_key[0] : key,
 199    for n:1 thru 10. do
 200       %_round_key[n] : next_round_key(%_round_key[n-1], n) )$
 201
 202
 203 /* cipher ******************************************************************* */
 204
 205 /*
 206 cipher and inv_cipher both return a new state.
 207 */
 208 cipher(state) := (
 209    state : add_round_key(state, %_round_key[0]),
 210
 211    for i:1 thru 9 do (
 212       state : shift_rows( sub_bytes(state) ),
 213       state : mix_columns(state), /* or mix_columns_2 */
 214       state : add_round_key(state, %_round_key[i]) ),
 215
 216    state : shift_rows( sub_bytes(state) ),
 217    add_round_key(state, %_round_key[10.]) )$
 218
 219
 220 /* inv_cipher *************************************************************** */
 221
 222 inv_cipher(state) := (
 223    state : add_round_key(state, %_round_key[10.]),
 224
 225    for n:9 step -1 thru 1 do (
 226       state : inv_shift_rows( inv_sub_bytes(state) ),
 227       state : add_round_key(state, %_round_key[n]),
 228       state : inv_mix_columns(state) ), /* or inv_mix_columns_2 */
 229
 230    state : inv_shift_rows( inv_sub_bytes(state) ),
 231    add_round_key(state, %_round_key[0]) )$
 232
 233
 234 /* user interface *********************************************************** */
 235
 236 print_block(block) :=
 237    printf(true, "~{~{~2,'0x ~}~%~}", block)$
 238
 239 /*
 240 Setting ibase causes SBCL not to compile make_state.
 241
 242 arg can be an octet-string, an integer or a list of octets.
 243 The return value is a 4x4 matrix.
 244 */
 245 make_state(arg) := block([state, c:1, r:1, ibase:16.],
 246    if stringp(arg) then arg : parse_string(sconcat(0, arg)),
 247    if integerp(arg) then arg : number_to_octets(arg),
 248    while length(arg) < 16. do arg : cons(0, arg),
 249    state : zeromatrix(4,4),
 250    for octet in arg do (
 251       state[r, c] : octet,
 252       if (r : r+1) = 5 then (r : 1, c : c+1) ),
 253    state )$
 254
 255 /*
 256 The first argument must be the state, a 4x4 matrix.
 257 The second optional argument can be 'list (the default), 'number or 'string.
 258 Accordingly the return value is a list of octets, an integer or an octet-string.
 259 */
 260 coerce_state([args]) := block([state:args[1], type, res],
 261    res : flatten(args(transpose(state))),
 262    type : if length(args) = 2 then args[2],
 263    if type = 'number then res : octets_to_number(res),
 264    if type = 'string then res : printf(false, "~{~2,'0x~}", res),
 265    res )$
 266
 267
 268 /* compilation ************************************************************** */
 269
 270 /*
 271 If speed matters it is recommended to compile the functions rather than to
 272 compile the file. When compiling use input base 10.
 273
 274 SBCL doesn't want to compile make_state.
 275
 276 compile(make_state)$
 277
 278 compile(
 279    sub_bytes, inv_sub_bytes,
 280    rotate, shift_rows, inv_rotate, inv_shift_rows,
 281    mat_n2p, mat_p2n, mix_columns, inv_mix_columns,
 282    aes_p2c, aes_c2p, mix_columns_2, inv_mix_columns_2,
 283    add_round_key,
 284    rot_word, key_expansion1, key_expansion2, next_round_key, key_expansion,
 285    cipher, inv_cipher,
 286    print_block, coerce_state )$
 287 */
 288
 289
 290 /* examples ***************************************************************** */
 291
 292 /*
 293 http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
 294 (Nov 26, 2001, AES specification)
 295 page 35/36:
 296
 297 (%i1) load(aes)$
 298
 299 (%i2) ibase: obase: 16.$
 300
 301 (%i3) state: make_state("00112233445566778899aabbccddeeff")$
 302
 303 (%i4) key: make_state("000102030405060708090a0b0c0d0e0f")$
 304
 305 (%i5) key_expansion(key)$
 306
 307 (%i6) state: cipher(state)$
 308
 309 (%i6) coerce_state(state);
 310 (%o7)       [69,0C4,0E0,0D8,6A,7B,4,30,0D8,0CD,0B7,80,70,0B4,0C5,5A]
 311 (%i8) state: inv_cipher(state)$
 312
 313 (%i9) coerce_state(state, 'string);
 314 (%o9)                  00112233445566778899AABBCCDDEEFF
 315
 316
 317 fips-197.pdf, page 33/34:
 318
 319 (%i0A) state: make_state("3243f6a8885a308d313198a2e0370734")$
 320
 321 (%i0B) key: make_state("2b7e151628aed2a6abf7158809cf4f3c")$
 322
 323 (%i0C) key_expansion(key)$
 324
 325 (%i0D) key;
 326                              [ 2B  28   0AB   9  ]
 327                              [                   ]
 328                              [ 7E  0AE  0F7  0CF ]
 329 (%o0D)                       [                   ]
 330                              [ 15  0D2  15   4F  ]
 331                              [                   ]
 332                              [ 16  0A6  88   3C  ]
 333 (%i0E) state;
 334                              [ 32   88  31   0E0 ]
 335                              [                   ]
 336                              [ 43   5A  31   37  ]
 337 (%o0E)                       [                   ]
 338                              [ 0F6  30  98    7  ]
 339                              [                   ]
 340                              [ 0A8  8D  0A2  34  ]
 341 (%i0F) state: cipher(state)$
 342
 343 (%i10) print_block(state)$
 344 39 02 DC 19
 345 25 DC 11 6A
 346 84 09 85 0B
 347 1D FB 97 32
 348
 349 (%i11) state: inv_cipher(state)$
 350
 351 (%i12) print_block(state)$
 352 32 88 31 E0
 353 43 5A 31 37
 354 F6 30 98 07
 355 A8 8D A2 34
 356
 357 */
 358
 359
 360 'done$