OKlibrary  0.2.1.6
SmallScaleAdvancedEncryptionStandard.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 27.1.2010 (Swansea) */
00002 /* Copyright 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 file is guaranteed to be included: */
00023 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/SmallScaleWordFields.mac")$
00024 
00025 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00027 oklib_plain_include(eigen)$ /* (for function columnvector) */
00028 
00029 
00030 /*
00031    The following implements the small scale AES as described in [Small Scale
00032    Variants of the AES] and
00033    [Algebraic Aspects of the Advanced Encryption Standard, section 3.3].
00034 
00035    The basic structure of the encryption and decryption is the same as AES
00036    (see AdvancedEncryptionStandard.mac). In particular matrices are used
00037    as input and output, and polynomials are used as the block elements.
00038 
00039    However, rather than simply being able to vary the number of rounds, this
00040    system allows one to additionally vary the following parameters (all
00041    non-negative integers):
00042 
00043    e - specifies that the size of the finite field used for individual
00044        block elements should be 2^e (i.e., the field is a GF(2^e) field)
00045        where the modulo polynomials for each of these fields is
00046        predefined.
00047    n_C - The number of columns in the block matrix.
00048    n_R - The number of rows in the block matrix.
00049 
00050    In addition to these parameters, we additionally (to [Small Scale Variants
00051    of the AES]) allow arbitrary finite fields rather than just fields of size
00052    2^e for the block elements and therefore we also introduce an integer
00053    parameter b for the base, and a parameter mod_poly for the
00054    modulo-polynomial to define (and standardise) the result of any operations
00055    in this field.
00056 
00057    Given this variety of parameters, functions are needed to define
00058    different Sbox and MixColumn operations based on the new dimensions of the
00059    fields and the block, which in turn use different vectors and matrices
00060    in their definition (as defined by [Small Scale Variants of the AES] or by
00061    the user in cases where this has not been defined there), therefore
00062    functions such as ss_mixcolumn_matrix, ss_sbox_matrix,
00063    ss_sbox_affine_constant etc. are defined which take their defining
00064    parameters (from b,e,n_C,n_R) and return the "standard" object to be used
00065    in each case.
00066 
00067    In [Small Scale Variants of the AES], there are two major variations, apart
00068    from the minor variations described above, namely those denoted by AES (the
00069    default variation in [Small Scale Variants of the AES]) and AES*, where AES
00070    is defined without a specialised final round (contrary to the standard AES
00071    definition), while AES* is defined in the same way as the standard AES with
00072    a specialised final round which does not contain MixColumns.
00073 
00074    For some functions two variants are provided, the standard version (without
00075    any special ending) and a generalised version (postfixed with "_gen"):
00076     - The standard versions take (in addition to any other arguments) only the
00077       base b and exponent e for the field, and then all other parameters
00078       (mod_poly, the sbox function, mixcolumn function etc) are derived using
00079       functions such as ss_polynomial, ss_sbox etc which provide the default
00080       constants and implementations.
00081     - The generalised version then take all parameters necessary for their
00082       function (from the list of parameters described above) without
00083       assuming any defaults.
00084    
00085 */
00086 
00087 /*
00088    The following naming conventions have been used in this module:
00089 
00090    Functions ending in "_gen" provide a generalisation of their namesake
00091    function, where additional parameters are taken, rather than using the
00092    standard constants provided by functions such as ss_mixcolumn_matrix etc.
00093 
00094    The AES and AES* variations as described in [Small scale variants of the
00095    AES] are called given by the functions ss_encrypt and ss_encrypt_wf
00096    respectively where "_wf" signifies "*w*ith *f*inal round".
00097 
00098 */
00099 
00100 /* TODO: REWRITE documentation below */
00101 /* TODO: TIDY code below to ensure readability. */
00102 
00103 /* OK: I thought this file would have been completed? */
00104 
00105 /* **************************************
00106    * Special bit-linear byte operations *
00107    **************************************
00108 */
00109 
00110 /* Here we provide special operations at the byte level involving linear
00111    transformations at the bit level. */
00112 
00113 /* Returns the result of applying the sboxes linear map to the given
00114    word (as a polynomial). */
00115 ss_sbox_linmap_gen(field_element,b,e,mod_poly, sbox_matrix) :=
00116   ss_stand(mvec2poly(sbox_matrix . poly2mvec_ss(field_element,e)),b,mod_poly)$
00117 ss_sbox_linmap(field_element,b,e) :=
00118   ss_sbox_linmap_gen(field_element,b,e,ss_polynomial(b,e),ss_sbox_matrix(b,e))$
00119 
00120 /* Returns the result of applying the sboxes linear map and then multiplication
00121    by a to the given word (as a polynomial). */
00122 ss_mul_w_sbox_linmap_gen(field_element,a,b,e,mod_poly, sbox_matrix) :=
00123   ss_mul(
00124     ss_sbox_linmap_gen(field_element,b,e,mod_poly,sbox_matrix),a,b,mod_poly)$
00125 ss_mul_w_sbox_linmap(field_element,a,b,e) :=
00126   ss_mult_w_sbox_linmap_gen(
00127     field_element,a,b,e,ss_polynomial(b,e),ss_sbox_matrix(b,e))$
00128 
00129 /* *********
00130    * S box *
00131    *********
00132 */
00133 
00134 /* Constant used in the affine transformation within ss_sbox: */
00135 ss_affine_constant_2_4 : '(x^2+x)$
00136 ss_affine_constant_2_8 : '(x^6 + x^5 + x + 1)$
00137 /* Returns the default affine constant for the default GF(b^e) field: */
00138 ss_affine_constant(b,e) :=
00139   if b = 2 then
00140     if e = 4 then ss_affine_constant_2_4
00141     else if e = 8 then ss_affine_constant_2_8
00142     else und
00143   else und$
00144 /* Constant used in the affine transformation within ss_inv_sbox: */
00145 /* Generated by multiplying the corresponding Sbox matrix by the
00146    vector for the affine constant and converting back to polynomials. */
00147 ss_inv_affine_constant_2_4 : '(x+1)$ 
00148 ss_inv_affine_constant_2_8 : '(x^2 + 1)$
00149 /* Returns the default inverse affine constant for the default GF(b^e) field. */
00150 ss_inv_affine_constant(b,e) :=
00151   if b = 2 then
00152     if e = 4 then ss_inv_affine_constant_2_4
00153     else if e = 8 then ss_inv_affine_constant_2_8
00154     else und
00155   else und$
00156 
00157 /* Matrix used in the affine transformation within ss_sbox: */
00158 ss_sbox_matrix_2_1 : matrix([1])$
00159 ss_sbox_matrix_2_4 : apply(matrix,
00160   create_list(rotate([1,0,1,1],i),i,0,3))$
00161 ss_sbox_matrix_2_8 : apply(matrix,
00162   create_list(rotate([1,1,1,1,1,0,0,0],i),i,0,7))$
00163 /* Returns the default sbox matrix for the default GF(b^e) field. */
00164 ss_sbox_matrix(b,e) :=
00165   if b = 2 then
00166     if e = 1 then ss_sbox_matrix_2_1
00167     else if e = 4 then ss_sbox_matrix_2_4
00168     else if e = 8 then ss_sbox_matrix_2_8
00169     else und
00170   else und$
00171 /* Matrix used in the affine transformation within ss_sbox: */
00172 ss_inv_sbox_matrix_2_1 : matrix([1])$
00173 ss_inv_sbox_matrix_2_4 : apply(matrix,
00174   create_list(rotate([1,1,1,0],i),i,0,3))$
00175 ss_inv_sbox_matrix_2_8 : apply(matrix,
00176   create_list(rotate([0,1,0,1,0,0,1,0],i),i,0,7))$
00177 /* Returns the default inverse sbox matrix for the default GF(b^e) field. */
00178 ss_inv_sbox_matrix(b,e) :=
00179   if b = 2 then
00180     if e = 1 then ss_inv_sbox_matrix_2_1
00181     else if e = 4 then ss_inv_sbox_matrix_2_4
00182     else if e = 8 then ss_inv_sbox_matrix_2_8
00183     else und
00184   else und$
00185 
00186 /* The small scale AES sbox takes an individual small scale
00187    field element (an element of the block) and returns
00188    the result of applying the small scale sbox operation
00189    defined for the given field parameters, sbox_matrix
00190    and affine_constant. Note here that sbox_matrix is a
00191    diagonal matrix of size e of elements in {1,...,b} and
00192    affine constant is a column vector size e with elements
00193    in {1,...,b}.
00194 
00195    Formally given a polynomial p as the field_element, the
00196    result of ss_sbox_gen is the polynomial of the form:
00197 
00198    sum(b[i] * x^(e-i), i, 1,e)
00199 
00200    where
00201 
00202    b[i] = sum(sbox_matrix[i,j] * a[j], i, 1, e) + affine_constant[i]
00203 
00204    and the coefficients a[i] (for i in {1,...,e}) are the coefficients
00205    of the polynomial defined as the inverse of p in the field:
00206 
00207    sum(a[i] * x^(e-i),i,1,e) = p^(-1) (in GF(b^e) mod mod_poly)
00208 
00209    where a[i],b[i] range over {0,...,b}.
00210 
00211    ss_inv_sbox(,_gen) are defined precisely the same as ss_sbox(,_gen)
00212    but for convention/convenience another function is provided with
00213    the expectation that the inv_sbox_matrix provided is the inverse
00214    of the matrix provided to ss_sbox(,_gen) within the GF(b^e) field.   
00215 */
00216 ss_sbox_gen(field_element,b,e,mod_poly, sbox_matrix,affine_constant) := block(
00217   [inv_elem : ss_einv(field_element,b,mod_poly)],
00218   ss_stand(mvec2poly(
00219     sbox_matrix . poly2mvec_ss(inv_elem,e)) + affine_constant,b,mod_poly))$
00220 ss_sbox(field_element, b,e) :=
00221   ss_sbox_gen(field_element,b,e,ss_polynomial(b,e),
00222     ss_sbox_matrix(b,e),ss_affine_constant(b,e))$
00223 ss_inv_sbox_gen(field_element,b,e,mod_poly,
00224     inv_sbox_matrix,inv_affine_constant) := block(
00225   [affine_result : mvec2poly(
00226       inv_sbox_matrix . poly2mvec_ss(field_element,e) +
00227           poly2mvec_ss(inv_affine_constant,e))],
00228   ss_einv(affine_result,b,mod_poly))$
00229 ss_inv_sbox(field_element, b,e) :=
00230   ss_inv_sbox_gen(field_element,b,e,ss_polynomial(b,e),
00231     ss_inv_sbox_matrix(b,e),ss_inv_affine_constant(b,e))$
00232 
00233 
00234 /* Small scale Sbox as boolean function */
00235 ss_sbox_bf(V,b,e) := poly2vec_ss(ss_sbox(vec2poly(V),b,e),e)$
00236 /* TODO: implement general versions of these functions. */
00237 
00238 /* Sbox with addition as a boolean function where the first half of
00239    the input boolean vector is input to the Sbox and then the result of
00240    the Sbox, is added to the other half of the input. */
00241 ss_sbox_w_add_bf(V,b,e) := block(
00242   [V1 : take_elements(floor(length(V)/2),V), V2 : rest(V,floor(length(V)/2))],
00243   ss_vecadd(ss_sbox_bf(V1,b,e),V2,b))$
00244 
00245 /* Sbox followed by multiplication by word field element elem as a boolean 
00246    function where the first half of the input boolean vector is input to the 
00247    Sbox and then the result of the Sbox, is added to the other half of the 
00248    input. */
00249 ss_sbox_w_mul_bf(V,elem,b,e) :=
00250   ss_vecmul(ss_sbox_bf(V,b,e),poly2vec_ss(elem,e),b,e,ss_polynomial(b,e))$
00251 
00252 
00253 /* *************
00254    * Sub-bytes *
00255    *************
00256 */
00257 
00258 /* 
00259    Takes the input block as a matrix of arbitrary polynomials
00260    and applies the given sbox operation to each polynomial, returning
00261    the matrix of result polynomials:
00262 */
00263 ss_subbytes(inputmatrix, sbox_f) := matrixmap(sbox_f, inputmatrix)$
00264 
00265 /* 
00266    Takes the input block as a matrix of polynomials and applies the given
00267    inverse sbox operation to each polynomial, returning the list of result
00268    polynomials:
00269 */
00270 ss_inv_subbytes(inputmatrix,inv_sbox_f) := matrixmap(inv_sbox_f, inputmatrix)$
00271 
00272 
00273 /* **************
00274    * Shift rows *
00275    **************
00276 */
00277 
00278 
00279 /*
00280    Takes a matrix and performs the shiftrows operation,
00281    returning a matrix where row i (for i in {1,..,length(inputmatrix)) has
00282    been shifted cyclically left by i-1.
00283 */
00284 ss_shiftrows(inputmatrix) :=
00285   apply(matrix,
00286     create_list(rotate(inputmatrix[abs(r)+1],-r), r, 0,length(inputmatrix)-1))$
00287 
00288 
00289 /*
00290    Takes a matrix and performs the inverse shiftrows operation,
00291    returning a matrix where row i (for i in {1,..,length(inputmatrix)) has
00292    been shifted cyclically right by i -1.
00293 */
00294 ss_inv_shiftrows(inputmatrix) :=
00295   apply(matrix,
00296     create_list(rotate(inputmatrix[abs(r)+1],r), r, 0,length(inputmatrix)-1))$
00297 
00298 
00299 /* ***************
00300    * Mix columns *
00301    ***************
00302 */
00303 
00304 /*
00305    Matrices used in the mixcolumns step to model the 
00306    multiplication of each n_C-byte column by a constant
00307    in a polynomial ring of at most order n_C with coefficients in
00308    GF(b^e):
00309 */
00310 ss_mixcolumns_matrix_2_4_1 : matrix([1])$
00311 ss_mixcolumns_matrix_2_8_1 : matrix([1])$
00312 ss_mixcolumns_matrix_2_4_2 : block([x], apply(matrix,
00313   create_list(rotate([x+1,x],i),i,0,1)))$
00314 ss_mixcolumns_matrix_2_8_2 : block([x], apply(matrix,
00315   create_list(rotate([x+1,x],i),i,0,1)))$
00316 ss_mixcolumns_matrix_2_4_4 : block([x], apply(matrix, 
00317   create_list(rotate([x, x + 1, 1, 1], i),i,0,3)))$
00318 ss_mixcolumns_matrix_2_8_4 : block([x], apply(matrix, 
00319   create_list(rotate([x, x + 1, 1, 1], i),i,0,3)))$
00320 ss_mixcolumns_matrix(b,e,n_R) :=
00321   if b = 2 then
00322     if n_R = 4 then
00323       if e = 4 then ss_mixcolumns_matrix_2_4_4
00324       else if e = 8 then ss_mixcolumns_matrix_2_8_4
00325       else und
00326     else if n_R = 2 then
00327       if e = 4 then ss_mixcolumns_matrix_2_4_2
00328       else if e = 8 then ss_mixcolumns_matrix_2_8_2
00329       else und
00330     else if n_R = 1 then
00331       if e = 4 then ss_mixcolumns_matrix_2_4_1
00332       else if e = 8 then ss_mixcolumns_matrix_2_8_1
00333       else und
00334     else und
00335   else und$
00336 /* Inverse of the rijn_mix_columns_matrix: */
00337 ss_inv_mixcolumns_matrix_2_4_1 : matrix([1])$
00338 ss_inv_mixcolumns_matrix_2_8_1 : matrix([1])$
00339 ss_inv_mixcolumns_matrix_2_4_2 : block([x], apply(matrix,
00340   create_list(rotate([x+1,x], i),i,0,1)))$
00341 ss_inv_mixcolumns_matrix_2_8_2 : block([x], apply(matrix,
00342   create_list(rotate([x+1,x], i),i,0,1)))$
00343 ss_inv_mixcolumns_matrix_2_4_4 : block([x], apply(matrix,
00344   create_list(rotate([x^3+x^2+x,x^3+x+1,x^3+x^2+1,x^3+1], i),i,0,3)))$
00345 ss_inv_mixcolumns_matrix_2_8_4 : block([x], apply(matrix,
00346   create_list(rotate([x^3+x^2+x,x^3+x+1,x^3+x^2+1,x^3+1], i),i,0,3)))$
00347 ss_inv_mixcolumns_matrix(b,e,n_R) :=
00348   if b = 2 then
00349     if n_R = 4 then
00350       if e = 4 then ss_inv_mixcolumns_matrix_2_4_4
00351       else if e = 8 then ss_inv_mixcolumns_matrix_2_8_4
00352       else und
00353     else if n_R = 2 then
00354       if e = 4 then ss_inv_mixcolumns_matrix_2_4_2
00355       else if e = 8 then ss_inv_mixcolumns_matrix_2_8_2
00356       else und
00357     else if n_R = 1 then
00358       if e = 4 then ss_inv_mixcolumns_matrix_2_4_1
00359       else if e = 8 then ss_inv_mixcolumns_matrix_2_8_1
00360       else und
00361     else und
00362   else und$
00363 
00364 ss_mixcolumns_matrix2inv_mixcolumns_matrix(b,e, mixcolumns_matrix) :=
00365   if b = 2 then
00366     if e = 8 then
00367       if mixcolumns_matrix = ss_mixcolumns_matrix_2_8_4 then
00368         ss_inv_mixcolumns_matrix_2_8_4
00369       else if mixcolumns_matrix = ss_mixcolumns_matrix_2_8_2 then
00370         ss_inv_mixcolumns_matrix_2_8_2
00371       else if mixcolumns_matrix = ss_mixcolumns_matrix_2_8_1 then
00372         ss_inv_mixcolumns_matrix_2_8_1
00373       else und
00374     else if e = 4 then
00375       if mixcolumns_matrix = ss_mixcolumns_matrix_2_4_4 then
00376         ss_inv_mixcolumns_matrix_2_4_4
00377       else if mixcolumns_matrix = ss_mixcolumns_matrix_2_4_2 then
00378         ss_inv_mixcolumns_matrix_2_4_2
00379       else if mixcolumns_matrix = ss_mixcolumns_matrix_2_4_1 then
00380         ss_inv_mixcolumns_matrix_2_4_1
00381       else und
00382     else und
00383   else und$
00384       
00385 
00386 /* Takes a (maxima) vector of polynomials and returns the result of
00387    multiplying the input matrix by the given mixcolumns_matrix
00388    in field specified by b, e and mod_poly.
00389 
00390    So for an input vector V of size n_R, the result is a vector W such that
00391    for i in {1,...,n_R}
00392 
00393    W[i] = sum(ss_stand(mixcolumns_matrix[i,j] * V[i]),b,e,mod_poly),j,1,n_R)
00394 
00395    where ss_stand is the standardisation of the result of the multiplication
00396    into a polynomial of the form sum(a[i] * x^(e-i), i, 1,e) where each a[i]
00397    is in {1,...,b}, i.e., a standardised representation of GF(b^e) field
00398    elements.
00399 */
00400 ss_mixcolumn_gen(V,b,e,mod_poly,mixcolumns_matrix) :=
00401   matrixmap(lambda([p],ss_stand(p,b,mod_poly)),
00402       mixcolumns_matrix . V);
00403 ss_mixcolumn(V,b,e) :=
00404   ss_mixcolumn_gen(V,b,e,
00405     ss_polynomial(b,e),
00406     ss_mixcolumns_matrix(b,e,length(V)))$
00407 
00408 /* The small scale MixColumns operation as a boolean function: */
00409 ss_mixcolumn_gen_bf(V,b,e,mod_poly,mixcolumns_matrix) := block(
00410   [Vec : map(vec2poly,partition_elements(V,e))],
00411   lappend(
00412     m2l_r(matrixmap(lambda([E],poly2vec_ss(E,e)),
00413         ss_mixcolumn_gen(Vec,b,e,mod_poly,mixcolumns_matrix)))))$
00414 ss_mixcolumn_bf(V,b,e) := 
00415   ss_mixcolumn_gen_bf(V,b,e,ss_polynomial(b,e),
00416     ss_mixcolumns_matrix(b,e,floor(length(V)/e)))$
00417 
00418 /* The boolean matrix representing the MixColumns operation  */
00419 ss_mixcolumn_gen_boolm(b,e,mod_poly,mixcolumns_matrix) := block([rows],
00420   rows : length(mixcolumns_matrix),
00421   transpose(apply(matrix,
00422       create_list(
00423         ss_mixcolumn_gen_bf(
00424           create_list(if i = j then 1 else 0, j, 1, e * rows),
00425           b,e,mod_poly, mixcolumns_matrix),
00426         i,1,e*rows))))$
00427 ss_mixcolumn_boolm(b,e,rows) :=
00428   ss_mixcolumn_gen_boolm(b,e,ss_polynomial(b,e),
00429     ss_mixcolumns_matrix(b,e,rows))$
00430 
00431 /* The small scale SubBytes followed by MixColumns operation on a single
00432    column of the AES block as a boolean function: */
00433 ss_round_column_gen_bf(V,b,e,mod_poly,mixcolumns_matrix,sbox_f_) := block(
00434   [Vec : map(vec2poly,partition_elements(V,e))],
00435   lappend(
00436     m2l_r(matrixmap(lambda([E],poly2vec_ss(E,e)),
00437           ss_mixcolumn_gen(
00438             ss_subbytes(Vec,sbox_f_),b,e,mod_poly,mixcolumns_matrix)))))$
00439 ss_round_column_bf(V,b,e) := 
00440   ss_round_column_gen_bf(V,b,e,ss_polynomial(b,e),
00441     ss_mixcolumns_matrix(b,e,floor(length(V)/e)),
00442     lambda([p],ss_sbox(p,b,e)))$
00443 
00444 /* Takes a (maxima) matrix of polynomials and returns the result of
00445    multiplying the input matrix by the given mixcolumns_matrix
00446    in field specified by b, e and mod_poly.
00447 
00448    So for an input matrix M of size n_R, the result is a vector W such that
00449    for i in {1,...,n_R}, j in {1,...,n_C}
00450 
00451    N[i,j] = sum(ss_stand(mixcolumns_matrix[i,k] * M[i,j]),b,e,mod_poly),
00452                   k,1,n_R)
00453 
00454    where ss_stand is the standardisation of the result of the multiplication
00455    into a polynomial of the form sum(a[i] * x^(e-i), i, 1,e) where each a[i]
00456    is in {1,...,b}, i.e., a standardised representation of GF(b^e) field
00457    elements.
00458 */
00459 ss_mixcolumns_gen(M,b,e,mod_poly,mixcolumns_matrix) :=
00460   matrixmap(lambda([p],ss_stand(p,b,mod_poly)),
00461       mixcolumns_matrix . M);
00462 ss_mixcolumns(M,b,e) :=
00463   ss_mixcolumns_gen(M,b,e,
00464     ss_polynomial(b,e),
00465     ss_mixcolumns_matrix(b,e,length(M)))$
00466 
00467 /* Takes a (maxima) vector of polynomials and returns the result of
00468    multiplying the input matrix by the given mixcolumns_matrix
00469    in field specified by b, e and mod_poly.
00470 
00471    So for an input vector V of size n_R, the result is a vector W such that
00472    for i in {1,...,n_R}
00473 
00474    W[i] = sum(ss_stand(mixcolumns_matrix[i,j] * V[i]),b,e,mod_poly),j,1,n_R)
00475 
00476    where ss_stand is the standardisation of the result of the multiplication
00477    into a polynomial of the form sum(a[i] * x^(e-i), i, 1,e) where each a[i]
00478    is in {1,...,b}, i.e., a standardised representation of GF(b^e) field
00479    elements.
00480 */
00481 ss_inv_mixcolumn_gen(V,b,e,mod_poly,inv_mixcolumns_matrix) :=
00482   matrixmap(lambda([p],ss_stand(p,b,mod_poly)),
00483       inv_mixcolumns_matrix . V);
00484 ss_inv_mixcolumn(V,b,e) :=
00485   ss_inv_mixcolumn_gen(V,b,e,
00486     ss_polynomial(b,e),
00487     ss_inv_mixcolumns_matrix(b,e,length(V)))$
00488 
00489 /* Takes a (maxima) matrix of polynomials and returns the result of
00490    multiplying the input matrix by the given mixcolumns_matrix
00491    in field specified by b, e and mod_poly.
00492 
00493    So for an input matrix M of size n_R, the result is a vector W such that
00494    for i in {1,...,n_R}, j in {1,...,n_C}
00495 
00496    N[i,j] = sum(ss_stand(inv_mixcolumns_matrix[i,k] * M[i,j]),b,e,mod_poly),
00497                   k,1,n_R)
00498 
00499    where ss_stand is the standardisation of the result of the multiplication
00500    into a polynomial of the form sum(a[i] * x^(e-i), i, 1,e) where each a[i]
00501    is in {1,...,b}, i.e., a standardised representation of GF(b^e) field
00502    elements.
00503 */
00504 ss_inv_mixcolumns_gen(M,b,e,mod_poly,inv_mixcolumns_matrix) :=
00505   matrixmap(lambda([p],ss_stand(p,b,mod_poly)),
00506       inv_mixcolumns_matrix . M);
00507 ss_inv_mixcolumns(M,b,e) :=
00508   ss_mixcolumns_gen(M,b,e,
00509     ss_polynomial(b,e),
00510     ss_inv_mixcolumns_matrix(b,e,length(M)))$
00511 
00512 
00513 /* *****************
00514    * Key expansion *
00515    *****************
00516 */
00517 
00518 /*
00519    Takes a matrix of polynomials as the round key for
00520    round r-1, and returns the small scale AES round
00521    key for round r, given the small scale sbox function
00522    sbox_f.
00523 */
00524 /* OK: what is the *mathematical* definition? */
00525 ss_keyschedule(M, r, b, mod_poly, sbox_f) := block(
00526   [newcols : matrix(), n_C : length(matrixcolumns(M)),
00527    round_constant : x^(r-1), n_R : length(M)],
00528   newcols : addcol(newcols,columnvector(
00529       create_list(
00530         (if n_C > 1 then M[i,1] else 0) + sbox_f(M[mod(i,n_R)+1,n_C]) + 
00531         if i = 1 then round_constant else 0,i,1,n_R))),
00532   for j : 2 thru n_C do
00533     newcols : addcol(newcols,columnvector(
00534       create_list(M[i,j] + newcols[i,j-1],i,1,n_R))),
00535   return(matrixmap(lambda([p],ss_stand(p,b,mod_poly)),newcols)))$
00536 
00537 /*
00538    Takes a matrix of polynomials as the input key and
00539    returns a matrix of size n_R * n_C * (num_rounds+1)
00540    where columns i * (n_R * n_C) to (i+1) * (n_R * N_C)
00541    are the round key matrix for round i, and where n_R and
00542    n_C are the number of rows and number of columns in
00543    the input key matrix (resp).
00544 */
00545 ss_key_expansion_gen(M, num_rounds, b, mod_poly, sbox_f) := block(
00546   [ks : lambda([M,r],
00547     endcons(ss_keyschedule(last(M),r,b,mod_poly,sbox_f),M))],
00548   lreduce(ks, create_list(i,i,1,num_rounds), [M]))$
00549 ss_key_expansion(M,num_rounds,b,e) := 
00550   ss_key_expansion_gen(M,num_rounds,b,ss_polynomial(b,e), lambda([a],ss_sbox(a,b,e)))$
00551 
00552 
00553 /* *********************************************
00554    * Small scale AES encryption and decryption *
00555    *********************************************
00556 */
00557 
00558 /* Takes a matrix of polynomials and another matrix
00559    of polynomials representing the round key and computes the result of
00560    applying the small scale AES round function on this matrix
00561    given the sbox and mixcolumn functions.
00562 
00563    Note ss_round_wa does not take the round key, and performs
00564    all operations in the small scale AES round, apart from the
00565    addition of the round key (i.e., subbytes, shiftrows, mixcolumns).
00566 */
00567 ss_round_wa_gen(pl,b,e,mod_poly,sbox_f,mixcolumns_matrix) := 
00568     ss_mixcolumns_gen(ss_shiftrows(
00569         ss_subbytes(pl,sbox_f)),b,e,mod_poly,mixcolumns_matrix)$
00570 ss_round_wa(pl,b,e) := 
00571     ss_mixcolumns(ss_shiftrows(
00572         ss_subbytes(pl,lambda([a],ss_sbox(a,b,e)))),b,e)$
00573 ss_round_gen(pl, rkl,b,e,mod_poly,sbox_f,mixcolumns_matrix) := 
00574   matrixmap(lambda([p], ss_stand(p,b,mod_poly)),
00575     ss_round_wa_gen(pl,b,e,mod_poly,sbox_f,mixcolumns_matrix)+rkl)$
00576 ss_round(pl,rkl,b,e) := 
00577   matrixmap(lambda([p], ss_stand(p,b,ss_polynomial(b,e))),
00578     ss_round_wa(pl,b,e)+rkl)$
00579   
00580 /* Takes a matrix of polynomials and another matrix
00581    of polynomials representing the round key and computes the result of
00582    applying the inverse of the small scale AES round function on this matrix
00583    given the sbox and mixcolumn functions.
00584 
00585 
00586    Note ss_inv_round_wa does not take the round key, and performs
00587    all operations in the small scale AES round, apart from the
00588    addition of the round key (i.e., inv_subbytes, inv_shiftrows,
00589    inv_mixcolumns).
00590 */
00591 ss_inv_round_wa_gen(pl,b,e,mod_poly,inv_sbox_f,inv_mixcolumn_matrix) := 
00592     ss_inv_subbytes(
00593       ss_inv_shiftrows(
00594         ss_inv_mixcolumns_gen(pl,b,e,mod_poly,inv_mixcolumns_matrix)),
00595       inv_sbox_f)$
00596 ss_inv_round_wa(pl,b,e,mod_poly,inv_sbox_f,inv_mixcolumn_matrix) := 
00597     ss_inv_subbytes(ss_inv_shiftrows(ss_inv_mixcolumns(pl,b,e)),inv_sbox_f)$
00598 ss_inv_round_gen(pl,rkl,b,e,mod_poly,inv_sbox_f,inv_mixcolumns_matrix) := 
00599     ss_inv_round_wa(pl+rkl,b,e,mod_poly,inv_sbox_f, inv_mixcolumns_matrix)$
00600 ss_inv_round(pl,rkl,b,e,mod_poly,inv_sbox_f,inv_mixcolumns_matrix) := 
00601     ss_inv_round_wa(pl+rkl,b,e,mod_poly,inv_sbox_f, inv_mixcolumns_matrix)$
00602 
00603 
00604 /* Takes a matrix of polynomials and another matrix
00605    of polynomials representing the round key and computes the result of
00606    applying the specialised final small scale AES round function on this
00607    matrix given the sbox and mixcolumn functions.
00608 
00609    Note ss_final_round_wa does not take the round key, and performs
00610    all operations in the small scale AES round, apart from the
00611    addition of the round key (i.e., subbytes, shiftrows).
00612 */
00613 ss_final_round_wa(pl,sbox_f) := /* Without round key addition */
00614     ss_shiftrows(
00615         ss_subbytes(pl,sbox_f))$
00616 ss_final_round(pl,rkl,b,mod_poly, sbox_f) :=  /* With round key addition */
00617   matrixmap(lambda([p],ss_stand(p,b,mod_poly)),
00618     ss_final_round_wa(pl,sbox_f)+rkl)$
00619 /* Takes a matrix of polynomials and another matrix
00620    of polynomials representing the round key and computes the result of
00621    applying the inverse of the specialised final small scale AES round
00622    function on this  matrix given the sbox and mixcolumn functions.
00623 
00624    Note ss_inv_final_round_wa does not take the round key, and performs
00625    all operations in the small scale AES round, apart from the
00626    addition of the round key (i.e., inv_subbytes, inv_shiftrows).
00627 */
00628 ss_inv_final_round_wa(pl,inv_sbox_f) := 
00629     ss_inv_subbytes(ss_inv_shiftrows(pl), inv_sbox_f)$
00630 ss_inv_final_round(pl,rkl,inv_sbox_f) := 
00631     ss_inv_final_round_wa(pl+rkl, inv_sbox_f)$
00632 
00633 
00634 /* Takes a matrix of polynomials, another matrix
00635    of polynomials representing the round key, and the number of rounds and
00636    computes the result (as a matrix of polynomials) of applying the small
00637    scale AES on this  matrix given the sbox and mixcolumn functions.
00638 
00639    Note ss_encrypt_wf(,_gen) use the standard round function for the final
00640    round, not the specialised version.
00641 */
00642 /* WITH final round (_wf) */
00643 ss_encrypt_wf_gen(pl, kl, num_rounds,b,e,mod_poly,sbox_f,mixcolumns_matrix) :=
00644 block([n_C : length(pl)],
00645   /* Initial Rounds */
00646   ekl : ss_key_expansion_gen(kl,num_rounds,b,mod_poly,sbox_f),
00647   initial_rk : first(ekl), final_rk : last(ekl),
00648   initial_result : 
00649     lreduce(lambda([m,n],
00650         ss_round_gen(m,n,b,e,mod_poly,sbox_f,mixcolumns_matrix)),
00651     rest(rest(ekl), -1), pl + initial_rk),
00652   /* Final Round */
00653   matrixmap(lambda([p],ss_stand(p,b,mod_poly)),
00654       ss_final_round(initial_result,final_rk, b,mod_poly, sbox_f))
00655 )$
00656 ss_encrypt_gen(pl, kl, num_rounds,b,e,mod_poly, sbox_f, mixcolumns_matrix) :=
00657 block(
00658   [n_C : length(pl)],
00659   /* Initial Rounds */
00660   ekl : ss_key_expansion_gen(kl,num_rounds,b,mod_poly,sbox_f),
00661   initial_rk : first(ekl),
00662   matrixmap(lambda([p],ss_stand(p,b,mod_poly)),
00663     lreduce(lambda([m,n],
00664         ss_round_gen(m,n,b,e,mod_poly,sbox_f,mixcolumns_matrix)),
00665     rest(ekl), pl + initial_rk))
00666 )$
00667 
00668 
00669 /* Takes a matrix of polynomials, another matrix
00670    of polynomials representing the round key, and the number of rounds and
00671    computes the result (as a matrix of polynomials) of applying the small
00672    scale AES decryption on this  matrix given the sbox, inverse sbox and
00673    inverse  mixcolumn functions.
00674 
00675    Note ss_decrypt_wf(,_gen) use the standard inverse round function for the
00676    final round, not the specialised version.
00677 */
00678 /* WITH final round (_wf) */
00679 ss_decrypt_wf_gen(pl, kl, num_rounds, b,e,mod_poly, sbox_f, inv_sbox_f,inv_mixcolumns_matrix) := block(
00680   [n_C : length(pl)],
00681   /* Initial Rounds */
00682   ekl : ss_key_expansion_gen(kl,num_rounds,b,mod_poly,sbox_f),
00683   initial_rk : first(ekl), final_rk : last(ekl),
00684   /* Final Round */
00685   if num_rounds = 10 then
00686     initial_result : ss_inv_final_round(pl,final_rk,inv_sbox_f)
00687   else
00688     initial_result :
00689       ss_inv_round_gen(pl,final_rk,b,e,mod_poly,
00690         inv_sbox_f,inv_mixcolumn_matrix),
00691   matrixmap(lambda([a],ss_stand(a,b,mod_poly)),
00692     rreduce(
00693       lambda([m,n],
00694         ss_inv_round_gen(m,n,b,e,mod_poly,inv_sbox_f,inv_mixcolumn_matrix)), 
00695       rest(rest(ekl), -1), initial_result) + initial_rk)
00696 )$
00697 /* WITHOUT final round */
00698 ss_decrypt_gen(pl, kl, num_rounds, b,e,mod_poly, sbox_f, inv_sbox_f,inv_mixcolumns_matrix) := block(
00699   [n_C : length(pl)],
00700   /* Initial Rounds */
00701   ekl : ss_key_expansion_gen(kl,num_rounds,b,mod_poly,sbox_f),
00702   initial_rk : first(ekl), 
00703   matrixmap(lambda([a],ss_stand(a,b,mod_poly)),
00704     rreduce(
00705       lambda([m,n],
00706         ss_inv_round_gen(m,n,b,e,mod_poly,inv_sbox_f,inv_mixcolumns_matrix)), 
00707       rest(ekl), pl) + initial_rk)
00708 )$
00709 
00710 
00711 /* **********************************************************
00712    * Small scale AES encryption as an iterated block cipher *
00713    **********************************************************
00714 */
00715 
00716 /* Combined small scale round function to be used within the
00717    iterated block cipher implementation of the small scale AES
00718    (ss_encrypt_ibc_gen).
00719 
00720    For the given plaintext and round, ss_round_ibc_gen acts
00721    identically on plain_text if round is 0, and otherwise
00722    acts as the small scale AES round function (without key
00723    addition).
00724 
00725    The reason for the difference when round is 0, is so that
00726    the iterated block cipher scheme applies the initial round
00727    key addition required by the AES, before iterating the round
00728    function.
00729 */
00730 ss_round_ibc_gen(plain_text, round,b,e,mod_poly, sbox_f,mixcolumns_matrix) :=
00731   if round = 0 then plain_text
00732   else
00733     ss_round_wa_gen(plain_text,b,e,mod_poly, sbox_f, mixcolumns_matrix)$
00734 
00735 /* Small scale AES encryption as ibc (see
00736    Cryptology/Lisp/CryptoSystems/IteratedBlockCipher.mac): */
00737 ss_encrypt_ibc_gen(plaintext, key, num_rounds, b,e,mod_poly,
00738   sbox_f, mixcolumns_matrix) :=
00739     ibc_0(
00740       buildq([b,mod_poly,sbox_f],
00741         lambda([key,r], ss_keyschedule(key,r,b,mod_poly,sbox_f))),
00742       buildq([sbox_f,mixcolumns_matrix,b,e,mod_poly],
00743         lambda([p,r],
00744           ss_round_ibc_gen(p,r,b,e,mod_poly,sbox_f,mixcolumns_matrix))),
00745       buildq([b,mod_poly],
00746         lambda([m,n],
00747           matrixmap(lambda([p],ss_stand(p,b,mod_poly)),m+n)))
00748       )(plaintext,key,num_rounds+1)$
00749 
00750 
00751 /* **********************************************************
00752    * Small scale AES instantiations                         *
00753    **********************************************************
00754 */
00755 
00756 /* Default small scale AES encryption WITHOUT a final round: */
00757 ss_encrypt(pl, kl, num_rounds,b,e) :=
00758   ss_encrypt_gen(pl,kl,num_rounds,b,e,
00759     ss_polynomial(b,e),
00760     buildq([b,e],lambda([a], ss_sbox(a,b,e))),
00761     ss_mixcolumns_matrix(b,e,length(pl)))$
00762 /* Default small scale AES encryption WITH final round (_wf): */
00763 ss_encrypt_wf(pl, kl, num_rounds,b,e) :=
00764    ss_encrypt_wf_gen(pl,kl,num_rounds,b,e,
00765      ss_polynomial(b,e), lambda([a], ss_sbox(a,b,e)),
00766      ss_mixcolumns_matrix(b,e,length(pl)))$
00767 /* Default small scale AES decryption WITHOUT final round: */
00768 ss_decrypt(pl, kl, num_rounds, b,e) :=
00769   ss_decrypt_gen(pl,kl,num_rounds,b,e,ss_polynomial(b,e),
00770     buildq([b,e],lambda([a], ss_sbox(a,b,e))),
00771     buildq([b,e],lambda([a], ss_inv_sbox(a,b,e))),
00772     ss_inv_mixcolumns_matrix(b,e,length(pl)))$
00773 /* Default small scale AES decryption WITH final round (_wf): */
00774 ss_decrypt_wf(pl, kl, num_rounds, b,e) :=
00775   ss_decrypt_wf_gen(pl,kl,num_rounds,b,e,ss_polynomial(b,e),
00776     lambda([a], ss_sbox(a,b,e)), lambda([a], ss_inv_sbox(a,b,e)),
00777     ss_inv_mixcolumns_matrix(b,e,length(pl)))$
00778 
00779 /* Instantiation of AES as an iterated block cipher: */
00780 ss_encrypt_ibc(plaintext,key,num_rounds,b,e) :=
00781   ss_encrypt_ibc_gen(plaintext,key,num_rounds,b,e,ss_polynomial(b,e),
00782     buildq([b,e],lambda([p],ss_sbox(p,b,e))),
00783     ss_mixcolumns_matrix(b,e,length(plaintext)))$
00784 
00785 
00786 /* Input and output as lists of natural numbers from 0 to b^e-1: */
00787 ss_encrypt_natl(pl, kl, num_rounds, b, e, n_R) :=
00788   ss_m2natl(
00789     ss_encrypt(ss_natl2m(pl,b,n_R),ss_natl2m(kl,b,n_R),num_rounds,b,e),b)$
00790 ss_decrypt_natl(pl, kl, num_rounds, b, e, n_R) :=
00791   ss_m2natl(
00792     ss_decrypt(ss_natl2m(pl,b,n_R),ss_natl2m(kl,b,n_R),num_rounds,b,e),b)$
00793 
00794 /* Input and output as lists of binary numbers of size e*n_C*n_R: */
00795 ss_encrypt_bin(pl, kl, num_rounds,b,e,n_R) :=
00796   lappend(
00797     map(lambda([m],int2polyadic_padd(m,b,e)),
00798       ss_encrypt_natl(
00799         map(binv2int, partition_elements(pl,e)),
00800         map(binv2int, partition_elements(kl,e)),
00801         num_rounds, b, e, n_R)))$
00802 ss_decrypt_bin(pl, kl, num_rounds,b,e,n_R) :=
00803   lappend(
00804     map(lambda([m],int2polyadic_padd(m,b,e)),
00805       ss_decrypt_natl(
00806         map(binv2int, partition_elements(pl,e)),
00807         map(binv2int, partition_elements(kl,e)),
00808         num_rounds, b, e, n_R)))$
00809 
00810 /* Input and output as hexadecimal values (the input does not need
00811    leading zeros, but the output is always padded to 32 hexadecimal
00812    digits): */
00813 ss_encrypt_hex(p,k,num_rounds,b,e,n_R,n_C) := block([num_hex_digits,num_bits],
00814   num_bits : e*n_R*n_C,
00815   num_hex_digits : ceiling(num_bits/4),
00816   binv2hexstr(
00817     ss_encrypt_bin(
00818       rest(
00819         hexstr2binv(lpad(p,"0",num_hex_digits)),
00820         (num_hex_digits * 4) - num_bits),
00821       rest(
00822         hexstr2binv(lpad(k,"0",num_hex_digits)),
00823         (num_hex_digits * 4) - num_bits),
00824       num_rounds, b, e, n_R)))$
00825 ss_decrypt_hex(p,k,num_rounds,b,e,n_R,n_C) := block([num_hex_digits,num_bits],
00826   num_bits : e*n_R*n_C,
00827   num_hex_digits : ceiling(num_bits/4),
00828   binv2hexstr(
00829     ss_decrypt_bin(
00830       rest(
00831         hexstr2binv(lpad(p,"0",num_hex_digits)),
00832         (num_hex_digits * 4) - num_bits),
00833       rest(
00834         hexstr2binv(lpad(k,"0",num_hex_digits)),
00835         (num_hex_digits * 4) - num_bits),
00836       num_rounds, b, e, n_R)))$
00837 
00838