OKlibrary  0.2.1.6
AdvancedEncryptionStandard.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 6.9.2007 (Swansea) */
00002 /* Copyright 2007, 2008, 2009, 2010, 2011 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 /* The following two files are guaranteed to be included: */
00023 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/BitField.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/Block.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/ByteField.mac")$
00026 
00027 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/Conversions.mac")$
00029 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/FiniteFields.mac")$
00030 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/data/Sbox.mac")$
00031 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/data/InvSbox.mac")$
00032 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/data/FieldMultiplications.mac")$
00033 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/IteratedBlockCipher.mac")$
00034 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00035 
00036 oklib_plain_include(eigen)$ /* (for function columnvector) */
00037 
00038 /*
00039    The following functions implement AES with 128 bit up to
00040    192 bit block sizes and with the corresponding key block
00041    sizes, but for simplicity of implementation, not unequal block/key
00042    sizes.
00043 */
00044 
00045 
00046 /* *********
00047    * S box *
00048    *********
00049 */
00050 
00051 /* Constant used in the affine transformation within sbox: */
00052 rijn_affine_constant : '(x^6 + x^5 + x + 1)$
00053 /* Constant used in the affine transformation within inv_sbox: */
00054 rijn_inv_affine_constant : '(x^2 + 1)$ 
00055 
00056 /* Matrix used in the affine transformation within rijn_sbox: */
00057 rijn_sbox_matrix : apply(matrix,
00058   create_list(rotate([1,1,1,1,1,0,0,0],i),i,0,7))$
00059 /* Matrix used in the affine transformation within inv_sbox: */
00060 rijn_inv_sbox_matrix : apply(matrix,
00061   create_list(rotate([0,1,0,1,0,0,1,0],i),i,0,7))$
00062 
00063 /* The AES sbox */
00064 
00065 /* Takes a value from the byte field as vector and returns the result
00066    of applying the Rijndael Sbox operation (as vector): */
00067 rijn_sbox_vec(v) := polybin2vecbin_rijn(rijn_sbox(vecbin2polybin(v)))$
00068 /* Now representing bytes as natural numbers: */
00069 rijn_sbox_nat(i) := polybin2nat(rijn_sbox(nat2polybin(i)))$
00070 /* Now representing bytes as polynomials (the standard representation): */
00071 rijn_sbox(p) := 
00072   rijn_stand(
00073     mvecbin2polybin( rijn_sbox_matrix . polybin2mvecbin_rijn(rijn_einv(p)) ) +
00074     rijn_affine_constant)$
00075 
00076 /* Inverse of Sbox: */
00077 rijn_inv_sbox_vec(v) := polybin2vecbin_rijn(rijn_inv_sbox(vecbin2polybin(v)))$
00078 rijn_inv_sbox_nat(i) := polybin2nat(rijn_inv_sbox(nat2polybin(i)))$
00079 rijn_inv_sbox(p) :=
00080   rijn_einv(
00081     mvecbin2polybin( rijn_inv_sbox_matrix . polybin2mvecbin_rijn(p) ) +
00082     rijn_inv_affine_constant)$
00083 
00084 /* Sbox implementation that utilises a lookup array to provide fast operation:
00085 */
00086 rijn_lookup_sbox_nat(i) := sbox_data[i+1]$
00087 rijn_lookup_sbox(p) := nat2polybin(sbox_data[polybin2nat(rijn_stand(p))+1])$
00088 
00089 /* Inverse Sbox implementation that utilises a lookup array to provide 
00090    fast operation: */
00091 rijn_lookup_inv_sbox_nat(i) := inv_sbox_data[i+1]$
00092 rijn_lookup_inv_sbox(p) :=
00093   nat2polybin(inv_sbox_data[polybin2nat(rijn_stand(p))+1])$
00094 
00095 /* As a permutation-function (i.e., as a map from {1,...,256} to
00096   {1,...,256}):
00097 */
00098 rijn_sbox_pmtf(n) := rijn_lookup_sbox_nat(n-1)+1$
00099 rijn_inv_sbox_pmtf(n) := rijn_lookup_inv_sbox_nat(n-1)+1$
00100 
00101 /* As a 8 x 8 boolean function: */
00102 rijn_sbox_bf(x) := rijn_sbox_vec(x)$
00103 rijn_inv_sbox_bf(x) := rijn_inv_sbox_vec(x)$
00104 
00105 
00106 /* *************
00107    * Sub-bytes *
00108    *************
00109 */
00110 
00111 /* 
00112    Takes the input block as a matrix of arbitrary polynomials and applies the
00113    sbox operation to each polynomial, returning the matrix of the resultant
00114    polynomials:
00115 */
00116 rijn_subbytes(inputmatrix, sbox_f) := matrixmap(sbox_f, inputmatrix)$
00117 
00118 /* 
00119    Takes the input block as a matrix of arbitrary polynomials in the range
00120    and applies the inverse sbox operation to each polynomial, returning the
00121    list of resultant polynomials:
00122 */
00123 rijn_inv_subbytes(inputmatrix,inv_sbox_f) := matrixmap(inv_sbox_f, inputmatrix)$
00124 
00125 
00126 /* **************
00127    * Shift rows *
00128    **************
00129 */
00130 
00131 /*
00132    Takes a matrix and performs the shiftrows operation,
00133    returning a matrix where each row has been shifted
00134    cyclically by the specified amount (see aes_shiftrows_shifts[i]
00135    for the shift for the i'th row).
00136 */
00137 aes_shiftrows(inputmatrix) := 
00138   apply(matrix,
00139     create_list(rotate(inputmatrix[abs(r)+1],-r), r, 0,3))$
00140 
00141 /*
00142    Takes a matrix and performs the inverse shiftrows operation,
00143    returning a matrix where each row has been shifted
00144    cyclically by the specified amount (see -aes_shiftrows_shifts[i]
00145    for the shift for the i'th row).
00146 */
00147 aes_inv_shiftrows(inputmatrix) :=
00148   apply(matrix,
00149     create_list(rotate(inputmatrix[abs(r)+1],r), r, 0,3))$
00150 
00151 
00152 /* ***************
00153    * Mix columns *
00154    ***************
00155 */
00156 
00157 /*
00158    Matrix of polynomials used in the Mixcolumns step to model the 
00159    multiplication of each 4-byte column by a constant
00160    in a polynomial ring of at most order 4 with coefficients in
00161    GF(2^8):
00162 */
00163 rijn_mixcolumns_matrix : block([x], apply(matrix, 
00164   create_list(rotate([x, x + 1, 1, 1], i),i,0,3)))$
00165 /* Inverse of the rijn_mix_columns_matrix: */
00166 rijn_inv_mixcolumns_matrix : block([x], apply(matrix,
00167   create_list(rotate([x^3+x^2+x,x^3+x+1,x^3+x^2+1,x^3+1], i),i,0,3)))$
00168 
00169 /* Given a 4 x 1 matrix of arbitrary polynomials, returns the result
00170    of multiplying the Mixcolumns matrix (of polynomials) by the given matrix.
00171 */
00172 rijn_mixcolumn(inputmatrixi) :=
00173   matrixmap(rijn_stand,
00174       rijn_mixcolumns_matrix . inputmatrixi);
00175 
00176 /* Given a 4 x n matrix (for 0<=n) of arbitrary polynomials, returns the result
00177    of applying mixcolumn_f to each column (as a matrix) in the matrix.
00178 
00179    In most case mixcolumn_f should be rijn_mixcolumn.
00180 */
00181 rijn_mixcolumns(inputmatrix,mixcolumn_f) := block([M : matrix()],
00182   for i : 1 thru 4 do M : addcol(M,mixcolumn_f(col(inputmatrix,i))),
00183   return(M))$
00184 
00185 /* The inverse of the rijn_mixcolumn operation. */
00186 rijn_inv_mixcolumn(inputmatrix) :=
00187   block([rijn_mixcolumns_matrix : rijn_inv_mixcolumns_matrix],
00188     rijn_mixcolumn(inputmatrix))$
00189 
00190 /* Given a 4 x n matrix (for 0<=n) of arbitrary polynomials, returns the result
00191    of applying inv_mixcolumn_f to each column (as a matrix) in the matrix.
00192 
00193    In most case mixcolumn_f should be rijn_inv_mixcolumn.
00194 */
00195 rijn_inv_mixcolumns(inputmatrix,inv_mixcolumn_f) := 
00196   rijn_mixcolumns(inputmatrix,inv_mixcolumn_f)$
00197 
00198 
00199 /* *****************
00200    * Key expansion *
00201    *****************
00202 */
00203 
00204 /*
00205    Takes an AES round key for round r as a list of
00206    polynomials and returns the round key for round r+1 as a list
00207    of polynomials of the same size.
00208  */
00209 aes_keyschedule(keymatrix, r, sbox_f) := block(
00210   [newcols : matrix(), n_k : length(matrixcolumns(keymatrix)), round_constant : x^(r-1)],
00211   newcols : addcol(newcols,columnvector(
00212       create_list(
00213         keymatrix[i,1] + sbox_f(keymatrix[mod(i,4)+1,n_k]) + 
00214         if i = 1 then round_constant else 0,i,1,4))),
00215   for j : 2 thru n_k do
00216     newcols : addcol(newcols,columnvector(
00217       create_list(keymatrix[i,j] + newcols[i,j-1],i,1,4))),
00218   return(matrixmap(rijn_stand,newcols)))$
00219 
00220 /* Given the AES key as a list of polynomials representing the
00221    byte field elements in the AES key block, column by column,
00222    returns a list of polynomials representing the byte field elements
00223    of the concatenation of the round key blocks for all AES rounds,
00224    column by column.
00225  */
00226  aes_key_expansion(keymatrix, num_rounds, sbox_f) := block(
00227   [ks : lambda([keymatrix,r],
00228     endcons(aes_keyschedule(last(keymatrix),r,sbox_f),keymatrix))],
00229   lreduce(ks, create_list(i,i,1,num_rounds), [keymatrix]))$
00230 
00231 
00232 /* *********************************
00233    * AES encryption and decryption *
00234    *********************************
00235 */
00236 
00237 /* 
00238    Takes the plaintext matrix of polynomials and the 
00239    round key for this round as a list of polynomials, and
00240    returns a matrix of the same size of polynomials as the plaintext
00241    as the result of the round operation:
00242  */
00243 aes_round_wa(pl,sbox_f,mixcolumn_f) := /* Without round key addition */
00244     rijn_mixcolumns(aes_shiftrows(
00245         rijn_subbytes(pl,sbox_f)),mixcolumn_f)$
00246 aes_round(pl, rkl, sbox_f, mixcolumn_f) := 
00247   matrixmap(rijn_stand,
00248     aes_round_wa(pl,sbox_f,mixcolumn_f)+rkl)$
00249 aes_inv_round_wa(pl,inv_sbox_f,inv_mixcolumn_f) := 
00250     rijn_inv_subbytes(aes_inv_shiftrows(
00251         rijn_inv_mixcolumns(pl,inv_mixcolumn_f)), inv_sbox_f)$
00252 aes_inv_round(pl,rkl,inv_sbox_f,inv_mixcolumn_f) := 
00253     aes_inv_round_wa(pl+rkl, inv_sbox_f, inv_mixcolumn_f)$
00254 
00255 
00256 /* 
00257    Takes the plaintext matrix of polynomials and the 
00258    round key for this round as a list of polynomials, and
00259    returns a matrix of the same size of polynomials as the plaintext
00260    as the result of the round operation (without mixcolumn):
00261  */
00262 aes_final_round_wa(pl,sbox_f) := /* Without round key addition */
00263     aes_shiftrows(
00264         rijn_subbytes(pl,sbox_f))$
00265 aes_final_round(pl, rkl, sbox_f) := 
00266   matrixmap(rijn_stand,aes_final_round_wa(pl,sbox_f)+rkl)$
00267 aes_inv_final_round_wa(pl,inv_sbox_f) := 
00268     rijn_inv_subbytes(aes_inv_shiftrows(pl), inv_sbox_f)$
00269 aes_inv_final_round(pl,rkl,inv_sbox_f) := 
00270     aes_inv_final_round_wa(pl+rkl, inv_sbox_f)$
00271 
00272 /* 
00273    Takes the plaintext matrix of 16 polynomials, the key matrix of 16
00274    polynomials and returns the result of applying the AES 
00275    encryption algorithm:
00276 */
00277 aes_encrypt_gen(pl, kl, num_rounds, sbox_f, mixcolumn_f) := (
00278   /* Initial Rounds */
00279   ekl : aes_key_expansion(kl,num_rounds,sbox_f),
00280   initial_rk : first(ekl), final_rk : last(ekl),
00281   initial_result : 
00282     lreduce(lambda([a,b],
00283         aes_round(a,b,sbox_f,mixcolumn_f)),
00284     rest(rest(ekl), -1), pl + initial_rk),
00285   /* Final Round */
00286   matrixmap(rijn_stand,
00287     if num_rounds = 10 then
00288       aes_final_round(initial_result, final_rk, sbox_f)
00289     else
00290       aes_round(
00291           initial_result,final_rk, sbox_f, mixcolumn_f))
00292 )$
00293 
00294 /* 
00295    Takes the plaintext matrix of 16 polynomials, the key matrix of 16
00296    polynomials and returns the result of applying the AES 
00297    decryption algorithm:
00298 */
00299 aes_decrypt_gen(pl, kl, num_rounds, sbox_f, inv_sbox_f,inv_mixcolumn_f) := (
00300   /* Initial Rounds */
00301   ekl : aes_key_expansion(kl,num_rounds,sbox_f),
00302   initial_rk : first(ekl), final_rk : last(ekl),
00303   /* Final Round */
00304   if num_rounds = 10 then
00305     initial_result : aes_inv_final_round(pl,final_rk,inv_sbox_f)
00306   else
00307     initial_result :
00308       aes_inv_round(pl,final_rk, inv_sbox_f,inv_mixcolumn_f),
00309   matrixmap(rijn_stand,
00310     rreduce(
00311       lambda([a,b],aes_inv_round(a,b,inv_sbox_f,inv_mixcolumn_f)), 
00312       rest(rest(ekl), -1), initial_result) + initial_rk)
00313 )$
00314 
00315 
00316 /* ***********************************
00317    * AES as an iterated block cipher *
00318    ***********************************
00319 */
00320 
00321 
00322 /* Combined AES round: */
00323 /* OK: what does this mean? */
00324 aes_round_ibc(plain_text, round, sbox_f,mixcolumn_f) :=
00325   if round = 0 then plain_text
00326   else if round = 10 then
00327     aes_final_round_wa(plain_text,sbox_f)
00328   else
00329     aes_round_wa(plain_text, sbox_f, mixcolumn_f)$
00330 
00331 /* AES encryption as ibc (see
00332    Cryptology/Lisp/CryptoSystems/IteratedBlockCipher.mac): */
00333 /* OK: this should just be a helper-function */
00334 aes_encrypt_ibc_gen(plaintext, key, num_rounds, sbox_f, mixcolumn_f) :=
00335     ibc_0(
00336       buildq([sbox_f],lambda([key,r], aes_keyschedule(key,r,sbox_f))),
00337       buildq([sbox_f,mixcolumn_f],
00338         lambda([p,r], aes_round_ibc(p,r,sbox_f,mixcolumn_f))),
00339       lambda([a,b],
00340         matrixmap(rijn_stand,a+b)))(plaintext,key,num_rounds+1)$
00341 
00342 
00343 /* *************************************
00344    * Convenience instantiations of AES *
00345    *************************************
00346 */
00347 
00348 
00349 /* Different forms of computation */
00350 
00351 /* AES Encryption using field operations: */
00352 /* The default AES encryption function. */
00353 aes_encrypt(p,k,num_rounds) := 
00354   aes_encrypt_gen(p,k,num_rounds,rijn_sbox,rijn_mixcolumn)$
00355 aes_encrypt_std(p,k) := aes_encrypt_f(p,k,10)$
00356 aes_encrypt_nat(p,k,num_rounds) := 
00357   rijn_m2natl(
00358     aes_encrypt_gen(rijn_natl2m(p),rijn_natl2m(k),num_rounds,
00359       rijn_sbox,rijn_mixcolumn))$
00360 aes_encrypt_nat_std(p,k) := aes_encrypt_nat(p,k,10)$
00361 
00362 /* AES Encryption using lookup tables: */
00363 aes_encrypt_l(p,k,num_rounds) := 
00364   aes_encrypt_gen(p,k,num_rounds,rijn_lookup_sbox,rijn_mixcolumn)$
00365 aes_encrypt_l_std(p,k) := aes_encrypt_l(p,k,10)$
00366 aes_encrypt_nat_l(p,k,num_rounds) := 
00367   rijn_m2natl(
00368     aes_encrypt_gen(rijn_natl2m(p),rijn_natl2m(k),num_rounds,
00369       rijn_lookup_sbox,rijn_mixcolumn))$
00370 aes_encrypt_nat_l_std(p,k) := aes_encrypt_nat_l(p,k,10)$
00371 
00372 /* AES Encryption as an iterated block cipher */
00373 /* NOTE: This is equivalent to aes_encrypt */
00374 aes_encrypt_ibc(p,k,num_rounds) :=
00375   aes_encrypt_ibc_gen(p,k,num_rounds,rijn_sbox,rijn_mixcolumn)$
00376 aes_encrypt_ibc_std(p,k) := aes_encrypt_ibc(p,k,10)$
00377 aes_encrypt_nat_ibc(p,k,num_rounds) :=
00378   rijn_m2natl(
00379     aes_encrypt_ibc_gen(rijn_natl2m(p),rijn_natl2m(k),num_rounds,
00380       rijn_sbox,rijn_mixcolumn))$
00381 aes_encrypt_nat_ibc_std(p,k) := aes_encrypt_nat_ibc_std(p,k,10)$
00382 
00383 /* AES Decryption using field operations: */
00384 /* The default AES decryption function. */
00385 aes_decrypt(c,k,num_rounds) := 
00386   aes_decrypt_gen(c,k,num_rounds,rijn_sbox,rijn_inv_sbox,rijn_inv_mixcolumn)$
00387 aes_decrypt_std(c,k) := aes_decrypt_f(c,k,10)$
00388 aes_decrypt_nat(c,k,num_rounds) := 
00389   rijn_m2natl(
00390     aes_decrypt_gen(rijn_natl2m(c),rijn_natl2m(k),num_rounds,
00391       rijn_sbox,rijn_inv_sbox,rijn_inv_mixcolumn))$
00392 aes_decrypt_nat_std(c,k) := aes_decrypt_nat(c,k,10)$
00393   
00394 /* AES Decryption using lookup tables: */
00395 aes_decrypt_l(c,k,num_rounds) := 
00396   aes_decrypt_gen(c,k,num_rounds,rijn_lookup_sbox,rijn_lookup_inv_sbox,rijn_inv_mixcolumn)$
00397 aes_decrypt_l_std(c,k) := aes_decrypt_l_std(c,k,10)$
00398 aes_decrypt_nat_l(c,k,num_rounds) := 
00399   rijn_m2natl(
00400     aes_decrypt_gen(rijn_natl2m(c),rijn_natl2m(k),num_rounds,
00401       rijn_lookup_sbox,rijn_lookup_inv_sbox,rijn_inv_mixcolumn))$
00402 aes_decrypt_nat_l_std(c,k) := aes_decrypt_nat_l_std(c,k,10)$
00403   
00404 
00405 
00406 /* Various representations of input/output */
00407 
00408 
00409 /* Input and output as lists of binary numbers of size 128: */
00410 aes_encrypt_bin(p,k,num_rounds) :=
00411   lappend(
00412     map(lambda([m],int2polyadic_padd(m,2,8)),
00413       aes_encrypt_nat_l(
00414         map(binv2int, partition_elements(p,8)),
00415         map(binv2int, partition_elements(k,8)),
00416         num_rounds)))$
00417 aes_encrypt_bin_std(p,k) := aes_encrypt_bin(p,k,10)$
00418 aes_decrypt_bin(p,k,num_rounds) :=
00419   lappend(
00420     map(lambda([m],int2polyadic_padd(m,2,8)),
00421       aes_decrypt_nat_l(
00422         map(binv2int, partition_elements(p,8)),
00423         map(binv2int, partition_elements(k,8)),
00424         num_rounds)))$
00425 aes_decrypt_bin_std(p,k) := aes_decrypt_bin(p,k,10)$
00426 
00427 
00428 /* Input and output as hexadecimal values (the input does not need
00429    leading zeros, but the output is always padded to 32 hexadecimal
00430    digits): */
00431 aes_encrypt_hex(p,k,num_rounds) := 
00432   binv2hexstr(
00433     aes_encrypt_bin(
00434       hexstr2binv(lpad(p,"0",32)), hexstr2binv(lpad(k,"0",32)), num_rounds))$
00435 aes_encrypt_hex_std(p,k) := aes_encrypt_hex(p,k,10)$
00436 aes_decrypt_hex(p,k,num_rounds) :=
00437   binv2hexstr(
00438     aes_decrypt_bin(
00439       hexstr2binv(lpad(p,"0",32)), hexstr2binv(lpad(k,"0",32)), num_rounds))$
00440 aes_decrypt_hex_std(p,k) := aes_decrypt_hex(p,k,10)$
00441 
00442 /* The AES-chiffre as number-theoretical function: */
00443 aes_int(p,k,num_rounds) :=
00444   polyadic2int(
00445     aes_encrypt_nat_l(
00446       pad_block_16(int2polyadic(p,256)), 
00447       pad_block_16(int2polyadic(k,256)),
00448       num_rounds
00449     ),
00450     256)$
00451 aes_int_std(p,k) := aes_int(p,k,10)$
00452 aes_int_decrypt(c,k,num_rounds) :=
00453   polyadic2int(
00454     aes_decrypt_nat_l(
00455       pad_block_16(int2polyadic(c,256)), 
00456       pad_block_16(int2polyadic(k,256)),
00457       num_rounds
00458     ),
00459     256)$
00460 aes_int_decrypt_std(c,k) := aes_int_decrypt(c,k,10)$
00461 
00462