share/contrib/gf/aes2.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 2 (byte version) ****************************************
  20
  21    Copyright Volker van Nek, 2012 - 2015
  22
  23
  24    This is an alternative to share/contrib/gf/aes.mac. It works at byte level
  25    and shows how to use precomputed lookup tables. It also presents a concise
  26    description of the mix_columns operation by using matrix-dot-multiplication
  27    controlled by Maxima's global variables matrix_element_add and .._mult.
  28
  29    In this file states are implemented as 4x4 arrays with destructively working
  30    operations.
  31
  32    See below for examples.
  33
  34
  35    June, 2015: New user interface.
  36    The functions make_state and coerce_state provide flexible support for
  37    different data types. States can be build from octet-strings, integers and
  38    lists of octets and can be coerced back to these three types.
  39    The new interface is based on new functions in share/stringproc. So you
  40    should have installed Maxima version 5.37 or higher.
  41 */
  42
  43
  44 /* GF arithmetic by lookup tables ******************************************* */
  45
  46 gf_set_data(2, x^8+x^4+x^3+x+1)$
  47
  48 gf_make_logs()$
  49
  50 mult_by_table(a, b) :=
  51    if a = 0 or b = 0 then 0
  52    else gf_powers[ ?mod(gf_logs[a] + gf_logs[b], 255.) ]$
  53
  54 inv_by_table(a) :=
  55    if a = 0 then 0
  56    else gf_powers[255. - gf_logs[a]]$
  57
  58
  59 /* sub_bytes **************************************************************** */
  60
  61 %_byte_sub : make_array(fixnum, 256.)$
  62
  63 byte_lrot(b, n) :=
  64    ?logior(?logand(?ash(b, n), 255.), ?ash(b, n-8))$
  65
  66 for byte : 0 thru 255. do
  67    %_byte_sub[byte] :
  68       block([s, x],
  69          x : inv_by_table(byte),
  70          s : [x, 99.],
  71          for n thru 4 do
  72             s : cons(byte_lrot(x, n), s),
  73          apply('?logxor, s) )$
  74
  75 print_byte_sub() :=
  76    printf(true, "~{~16@{~2,'0x ~}~%~}", listarray(%_byte_sub))$
  77
  78 sub_bytes(state) :=
  79    for i:0 thru 3 do
  80       for j:0 thru 3 do
  81          state[i, j] : %_byte_sub[state[i, j]] $
  82
  83
  84 /* inv_sub_bytes ************************************************************ */
  85
  86 %_inv_byte_sub : make_array(fixnum, 256.)$
  87
  88 for byte : 0 thru 255. do
  89    %_inv_byte_sub[byte] :
  90       block([s, x],
  91          x : ?logxor(byte, 99.),
  92          s : [byte_lrot(x, 1), byte_lrot(x, 3), byte_lrot(x, 6)],
  93          inv_by_table( apply('?logxor, s) ) )$
  94
  95 print_inv_byte_sub() :=
  96    printf(true, "~{~16@{~2,'0x ~}~%~}", listarray(%_inv_byte_sub))$
  97
  98 inv_sub_bytes(state) :=
  99    for r:0 thru 3 do
 100       for c:0 thru 3 do
 101          state[r, c] : %_inv_byte_sub[state[r, c]] $
 102
 103
 104 /* shift_rows *************************************************************** */
 105
 106 rotate1(state, r) := block([sr0 : state[r, 0]],
 107    for c:0 thru 2 do
 108       state[r, c] : state[r, c+1],
 109    state[r, 3] : sr0 )$
 110
 111 rotate2(state) := block([s],
 112    s : state[2, 0], state[2, 0] : state[2, 2], state[2, 2] : s,
 113    s : state[2, 1], state[2, 1] : state[2, 3], state[2, 3] : s )$
 114
 115 inv_rotate1(state, r) := block([sr3 : state[r, 3]],
 116    for c:3 step -1 thru 1 do
 117       state[r, c] : state[r, c-1],
 118    state[r, 0] : sr3 )$
 119
 120 shift_rows(state) := (
 121    rotate1(state, 1), rotate2(state), inv_rotate1(state, 3) )$
 122
 123
 124 /* inv_shift_rows *********************************************************** */
 125
 126 inv_shift_rows(state) := (
 127    rotate1(state, 3), rotate2(state), inv_rotate1(state, 1) )$
 128
 129
 130 /* mix_columns ************************************************************** */
 131
 132 matrix_element_add : ?logxor $
 133
 134 matrix_element_mult : mult_by_table $
 135
 136 %_MIX_COLUMNS : matrix(
 137    [2, 3, 1, 1],
 138    [1, 2, 3, 1],
 139    [1, 1, 2, 3],
 140    [3, 1, 1, 2] )$
 141
 142 mix_columns(state) := block([mat],
 143    mat : %_MIX_COLUMNS . genmatrix(state, 3,3,0,0),
 144    fillarray(state, flatten(args(mat))) )$
 145
 146
 147 /* inv_mix_columns ********************************************************** */
 148
 149 %_INV_MIX_COLUMNS :
 150    matrixmap('gf_p2n, gf_invert_by_lu( matrixmap('gf_n2p, %_MIX_COLUMNS) ) )$
 151
 152 inv_mix_columns(state) := block([mat],
 153    mat : %_INV_MIX_COLUMNS . genmatrix(state, 3,3,0,0),
 154    fillarray(state, flatten(args(mat))) )$
 155
 156
 157 /* add_round_key ************************************************************ */
 158
 159 add_round_key(state, key) :=
 160    for r:0 thru 3 do
 161       for c:0 thru 3 do
 162          state[r, c] : ?logxor(state[r, c], key[r, c])$
 163
 164
 165 /* key_expansion ************************************************************ */
 166
 167 %_rcon : make_array(fixnum, 4, 10.)$
 168
 169 for i:0 thru 9 do
 170    %_rcon[0, i] : gf_p2n(gf_exp(x, i))$
 171
 172 rot_word(old, new) := (
 173    new[3, 0] : old[0, 3],
 174    for r:0 thru 2 do
 175       new[r, 0] : old[r+1, 3] )$
 176
 177 key_expansion1(old, new, n) := (
 178    rot_word(old, new),
 179    for r:0 thru 3 do
 180       new[r, 0] : %_byte_sub[new[r, 0]],
 181    for r:0 thru 3 do
 182       new[r, 0] : ?logxor(old[r, 0], new[r, 0], %_rcon[r, n-1]) )$
 183
 184 key_expansion2(old, new) :=
 185    for c:1 thru 3 do
 186       for r:0 thru 3 do
 187          new[r, c] : ?logxor(new[r, c-1], old[r, c])$
 188
 189 %_round_key : make_array(any, 11.)$
 190
 191 make_round_key(n) := (
 192    %_round_key[n] : make_array(fixnum, 4, 4),
 193    key_expansion1(%_round_key[n-1], %_round_key[n], n),
 194    key_expansion2(%_round_key[n-1], %_round_key[n]) )$
 195
 196 key_expansion(key) := (
 197    %_round_key[0] : key,
 198    for n:1 thru 10. do make_round_key(n) )$
 199
 200
 201 /* cipher ******************************************************************* */
 202
 203 /*
 204 cipher and inv_cipher both change the state destructively.
 205 */
 206 cipher(state) := (
 207    add_round_key(state, %_round_key[0]),
 208
 209    for n:1 thru 9 do (
 210       sub_bytes(state),
 211       shift_rows(state),
 212       mix_columns(state),
 213       add_round_key(state, %_round_key[n]) ),
 214
 215    sub_bytes(state),
 216    shift_rows(state),
 217    add_round_key(state, %_round_key[10.]) )$
 218
 219
 220 /* inv_cipher *************************************************************** */
 221
 222 inv_cipher(state) := (
 223    add_round_key(state, %_round_key[10.]),
 224
 225    for n:9 step -1 thru 1 do (
 226       inv_shift_rows(state),
 227       inv_sub_bytes(state),
 228       add_round_key(state, %_round_key[n]),
 229       inv_mix_columns(state) ),
 230
 231    inv_sub_bytes(state),
 232    inv_shift_rows(state),
 233    add_round_key(state, %_round_key[0]) )$
 234
 235
 236 /* user interface *********************************************************** */
 237
 238 matrix_to_state(matrix) := block([state],
 239    state : make_array(fixnum, 4, 4),
 240    fillarray(state, flatten(args(matrix))) )$
 241
 242 state_to_matrix(state) := genmatrix(state, 3, 3, 0, 0)$
 243
 244 print_block(block) :=
 245    printf(true, "~{~4@{~2,'0x ~}~%~}", listarray(block))$
 246
 247 /*
 248 Setting ibase causes SBCL not to compile make_state.
 249
 250 arg can be an octet-string, an integer or a list of octets.
 251 The return value is a Lisp array.
 252 */
 253 make_state(arg) := block([state, c:0, r:0, ibase:16.],
 254    if stringp(arg) then arg : parse_string(sconcat(0, arg)),
 255    if integerp(arg) then arg : number_to_octets(arg),
 256    while length(arg) < 16. do arg : cons(0, arg),
 257    state : make_array(fixnum, 4, 4),
 258    for octet in arg do (
 259       state[r, c] : octet,
 260       if (r : r+1) = 4 then (r : 0, c : c+1) ),
 261    state )$
 262
 263 /*
 264 The first argument must be the state, a 4x4 Lisp array.
 265 The second optional argument can be 'list (the default), 'number or 'string.
 266 Accordingly the return value is a list of octets, an integer or an octet-string.
 267 */
 268 coerce_state([args]) := block([state:args[1], type, res:[]],
 269    for c:3 thru 0 step -1 do
 270       for r:3 thru 0 step -1 do
 271          res : cons(state[r, c], res),
 272    type : if length(args) = 2 then args[2],
 273    if type = 'number then res : octets_to_number(res),
 274    if type = 'string then res : printf(false, "~{~2,'0x~}", res),
 275    res )$
 276
 277
 278 /* compilation ************************************************************** */
 279
 280 /*
 281 If speed matters it is recommended to compile the functions rather than to
 282 compile the file. When compiling use input base 10.
 283
 284 SBCL doesn't want to compile make_state.
 285
 286 compile(make_state)$
 287
 288 compile(
 289    mult_by_table, inv_by_table,
 290    byte_lrot, sub_bytes, inv_sub_bytes, print_byte_sub, print_inv_byte_sub,
 291    rotate1, rotate2, inv_rotate1, shift_rows, inv_shift_rows,
 292    mix_columns, inv_mix_columns,
 293    add_round_key,
 294    rot_word, key_expansion1, key_expansion2, make_round_key, key_expansion,
 295    cipher, inv_cipher,
 296    matrix_to_state, state_to_matrix, print_block, coerce_state )$
 297 */
 298
 299
 300 /* examples ***************************************************************** */
 301
 302 /*
 303 http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
 304 (Nov 26, 2001, AES specification)
 305 page 35/36:
 306
 307 (%i1) load(aes2)$
 308
 309 (%i2) ibase : obase : 16.$
 310
 311 (%i3) state : make_state("00112233445566778899aabbccddeeff")$
 312
 313 (%i4) key : make_state("000102030405060708090a0b0c0d0e0f")$
 314
 315 (%i5) key_expansion(key)$
 316
 317 (%i6) cipher(state);
 318 (%o6)                               done
 319 (%i7) coerce_state(state);
 320 (%o7)       [69,0C4,0E0,0D8,6A,7B,4,30,0D8,0CD,0B7,80,70,0B4,0C5,5A]
 321 (%i8) inv_cipher(state);
 322 (%o8)                               done
 323 (%i9) coerce_state(state, 'string);
 324 (%o9)                  00112233445566778899AABBCCDDEEFF
 325
 326 fips-197.pdf, page 33/34:
 327
 328 (%i0A) state : make_state("3243f6a8885a308d313198a2e0370734");
 329 (%o0A)                         Lisp array [4,4]
 330 (%i0B) key : make_state("2b7e151628aed2a6abf7158809cf4f3c")$
 331
 332 (%i0C) key_expansion(key)$
 333
 334 (%i0D) print_block(key)$
 335 2B 28 AB 09
 336 7E AE F7 CF
 337 15 D2 15 4F
 338 16 A6 88 3C
 339
 340 (%i0E) print_block(state)$
 341 32 88 31 E0
 342 43 5A 31 37
 343 F6 30 98 07
 344 A8 8D A2 34
 345 (%i0F) cipher(state);
 346 (%o0F)                              done
 347 (%i10) print_block(state)$
 348 39 02 DC 19
 349 25 DC 11 6A
 350 84 09 85 0B
 351 1D FB 97 32
 352 (%i11) inv_cipher(state);
 353 (%o11)                              done
 354 (%i12) print_block(state)$
 355 32 88 31 E0
 356 43 5A 31 37
 357 F6 30 98 07
 358 A8 8D A2 34
 359
 360 */
 361
 362
 363 'done$