OKlibrary  0.2.1.6
AdvancedEncryptionStandard.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 15.2.2008 (Swansea) */
00002 /* Copyright 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 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/ByteField.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/AdvancedEncryptionStandard.mac")$
00025 
00026 
00027 kill(f)$
00028 
00029 /* *********
00030    * S box *
00031    *********
00032 */
00033 
00034 okltest_rijn_sbox_vec(f) := block(
00035   assert(f([0,0,0,0,0,0,0,0]) = [0,1,1,0,0,0,1,1]),
00036   assert(f([0,0,0,0,0,0,0,1]) = [0,1,1,1,1,1,0,0]),
00037   assert(f([0,1,0,1,0,0,1,0]) = [0,0,0,0,0,0,0,0]),
00038   assert(f([1,1,1,1,1,1,1,1]) = [0,0,0,1,0,1,1,0]),
00039   if oklib_test_level=0 then return(true),
00040   for b : 0 thru 255 do
00041     assert(f(nat2vecbin_rijn(b)) = nat2vecbin_rijn(rijn_lookup_sbox_nat(b))),
00042   true)$
00043 
00044 okltest_rijn_sbox_nat(f) := block(
00045   assert(f(0) = 99),
00046   assert(f(82) = 0),
00047   assert(f(255) = 22),
00048   if oklib_test_level=0 then return(true),
00049   for b : 0 thru 255 do
00050     assert(f(b) = rijn_lookup_sbox_nat(b)),
00051   true)$
00052 
00053 okltest_rijn_sbox(f) := block(
00054   assert(f(0) = x^6+x^5+x+1),
00055   assert(f(x^6+x^4+x) = 0),
00056   assert(f(x^7+x^6+x^5+x^4+x^3+x^2+x+1) = x^4+x^2+x),
00057   if oklib_test_level=0 then return(true),
00058   for b : 0 thru 255 do
00059     assert(f(b) = rijn_lookup_sbox(b)),
00060   true)$
00061 
00062 okltest_rijn_inv_sbox_vec(f) := block(
00063   assert(f([0,1,1,0,0,0,1,1]) = [0,0,0,0,0,0,0,0]),
00064   assert(f([0,1,1,1,1,1,0,0]) = [0,0,0,0,0,0,0,1]),
00065   assert(f([0,0,0,0,0,0,0,0]) = [0,1,0,1,0,0,1,0]),
00066   assert(f([0,0,0,1,0,1,1,0]) = [1,1,1,1,1,1,1,1]),
00067   if oklib_test_level=0 then return(true),
00068   for b : 0 thru 255 do
00069     assert(f(nat2vecbin_rijn(b)) =
00070       nat2vecbin_rijn(rijn_lookup_inv_sbox_nat(b)))
00071   )$
00072 
00073 okltest_rijn_inv_sbox_nat(f) := block(
00074   assert(f(0) = 82),
00075   assert(f(99) = 0),
00076   assert(f(22) = 255),
00077   if oklib_test_level=0 then return(true),
00078   for b : 0 thru 255 do
00079     assert(f(b) = rijn_lookup_inv_sbox_nat(b)),
00080   true)$
00081 
00082 okltest_rijn_inv_sbox(f) := block(
00083   assert(f(0) = x^6+x^4+x),
00084   assert(f(x^6+x^5+x+1) = 0),
00085   assert(f(x^4+x^2+x) = x^7+x^6+x^5+x^4+x^3+x^2+x+1),
00086   if oklib_test_level=0 then return(true),
00087   for b : 0 thru 255 do
00088     assert(f(b) = rijn_lookup_inv_sbox(b)),
00089   true)$
00090 
00091 okltest_rijn_sbox_pmtf(f) := (
00092   assert(create_list(f(i)-1,i,1,256) =
00093     [99,124,119,123,242,107,111,197,48,1,103,43,254,215,171,118,202,130,201,
00094      125,250,89,71,240,173,212,162,175,156,164,114,192,183,253,147,38,54,63,
00095      247,204,52,165,229,241,113,216,49,21,4,199,35,195,24,150,5,154,7,18,128,
00096      226,235,39,178,117,9,131,44,26,27,110,90,160,82,59,214,179,41,227,47,132,
00097      83,209,0,237,32,252,177,91,106,203,190,57,74,76,88,207,208,239,170,251,
00098      67,77,51,133,69,249,2,127,80,60,159,168,81,163,64,143,146,157,56,245,188,
00099      182,218,33,16,255,243,210,205,12,19,236,95,151,68,23,196,167,126,61,100,
00100      93,25,115,96,129,79,220,34,42,144,136,70,238,184,20,222,94,11,219,224,50,
00101      58,10,73,6,36,92,194,211,172,98,145,149,228,121,231,200,55,109,141,213,
00102      78,169,108,86,244,234,101,122,174,8,186,120,37,46,28,166,180,198,232,
00103      221,116,31,75,189,139,138,112,62,181,102,72,3,246,14,97,53,87,185,134,
00104      193,29,158,225,248,152,17,105,217,142,148,155,30,135,233,206,85,40,223,
00105      140,161,137,13,191,230,66,104,65,153,45,15,176,84,187,22]),
00106   true)$
00107 
00108 okltest_rijn_inv_sbox_pmtf(f) := (
00109   assert(create_list(f(i)-1,i,1,256) = 
00110   [82,9,106,213,48,54,165,56,191,64,163,158,129,243,215,251,124,227,57,130,
00111    155,47,255,135,52,142,67,68,196,222,233,203,84,123,148,50,166,194,35,61,
00112    238,76,149,11,66,250,195,78,8,46,161,102,40,217,36,178,118,91,162,73,109,
00113    139,209,37,114,248,246,100,134,104,152,22,212,164,92,204,93,101,182,146,
00114    108,112,72,80,253,237,185,218,94,21,70,87,167,141,157,132,144,216,171,0,
00115    140,188,211,10,247,228,88,5,184,179,69,6,208,44,30,143,202,63,15,2,193,175,
00116    189,3,1,19,138,107,58,145,17,65,79,103,220,234,151,242,207,206,240,180,230,
00117    115,150,172,116,34,231,173,53,133,226,249,55,232,28,117,223,110,71,241,26,
00118    113,29,41,197,137,111,183,98,14,170,24,190,27,252,86,62,75,198,210,121,32,
00119    154,219,192,254,120,205,90,244,31,221,168,51,136,7,199,49,177,18,16,89,39,
00120    128,236,95,96,81,127,169,25,181,74,13,45,229,122,159,147,201,156,239,160,
00121    224,59,77,174,42,245,176,200,235,187,60,131,83,153,97,23,43,4,126,186,119,
00122    214,38,225,105,20,99,85,33,12,125]),
00123   true)$
00124 
00125 /* *************
00126    * Sub-bytes *
00127    *************
00128 */
00129 
00130 okltest_rijn_subbytes(f) := (
00131   assert(f(diagmatrix(4,0),rijn_sbox) =
00132     genmatrix(lambda([a,b],x^6+x^5+x+1),4,4)),
00133   assert(f(diagmatrix(4,1),rijn_sbox) =
00134     genmatrix(lambda([a,b],
00135       if a = b then x^6+x^5+x^4+x^3+x^2 else x^6+x^5+x+1),4,4)),
00136   assert(f(rijn_l2m(
00137         map(nat2polybin,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16])),rijn_sbox) =
00138     rijn_l2m(map(nat2polybin,
00139         [124,119,123,242,107,111,197,48,1,103,43,254,215,171,118,202]))),
00140   true)$
00141 
00142 okltest_rijn_inv_subbytes(f) := (
00143   assert(f(genmatrix(lambda([a,b],x^6+x^5+x+1),4,4),rijn_inv_sbox) =
00144     diagmatrix(4,0)),
00145   assert(f(
00146       genmatrix(lambda([a,b],
00147           if a = b then x^6+x^5+x^4+x^3+x^2
00148           else x^6+x^5+x+1),4,4),rijn_inv_sbox) = diagmatrix(4,1)),
00149   assert(totaldisrep(f(rijn_l2m(map(nat2polybin,[124,119,123,242,107,111,197,
00150             48,1,103,43,254,215,171,118,202])),rijn_inv_sbox)) =
00151     rijn_l2m(map(nat2polybin, [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]))),
00152   true)$
00153     
00154 
00155 
00156 /* **************
00157    * Shift rows *
00158    **************
00159 */
00160 
00161 okltest_aes_shiftrows(f) := block(
00162   assert(f(diagmatrix(4,0))=diagmatrix(4,0)),
00163   assert(f(genmatrix(lambda([a,b],[a,b]),4,4)) =
00164     genmatrix(lambda([a,b],[a,mod((b-1)+(a-1),4)+1]),4,4)),
00165   true)$
00166 
00167 okltest_aes_inv_shiftrows(f) := block(
00168   assert(f(diagmatrix(4,0))=diagmatrix(4,0)),
00169   assert(f(genmatrix(lambda([a,b],[a,mod((b-1)+(a-1),4)+1]),4,4)) =
00170     genmatrix(lambda([a,b],[a,b]),4,4)),
00171   true)$
00172 
00173 
00174 /* ***************
00175    * Mix columns *
00176    ***************
00177 */
00178 
00179 okltest_rijn_mixcolumn(f) := block(
00180   assert(f(rijn_natl2m([0,0,0,0])) = rijn_natl2m([0,0,0,0])),
00181   assert(f(rijn_natl2m([50,67,7,52]))=
00182     rijn_natl2m([146, 137, 35, 122])),
00183   true)$
00184 
00185 okltest_rijn_inv_mixcolumn(f) := block(
00186   assert(f(rijn_natl2m([0,0,0,0])) = rijn_natl2m([0,0,0,0])),
00187   assert(f(rijn_natl2m([146, 137, 35, 122]))=
00188     rijn_natl2m([50,67,7,52])),
00189   true)$
00190 
00191 okltest_rijn_mixcolumns(f) := block(
00192   assert(f(rijn_natl2m([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]),
00193         rijn_mixcolumn) = rijn_natl2m([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])),
00194   assert(f(rijn_natl2m(
00195           [50,136,49,224,67,90,49,55,246,48,152,7,168,141,162,52]),
00196         rijn_mixcolumn)= rijn_natl2m(
00197       [54,138,227,52,110,147,34,192,56,34,228,167,81,96,38,164])),
00198   true)$
00199 
00200 okltest_rijn_inv_mixcolumns(f) := block(
00201   assert(f(rijn_natl2m([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]),
00202         rijn_inv_mixcolumn) = rijn_natl2m([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])),
00203   assert(f(rijn_natl2m(
00204           [54,138,227,52,110,147,34,192,56,34,228,167,81,96,38,164])
00205       ,rijn_inv_mixcolumn)= rijn_natl2m(
00206     [50,136,49,224,67,90,49,55,246,48,152,7,168,141,162,52])),
00207   true)$ 
00208 
00209 
00210 /* *****************
00211    * Key expansion *
00212    *****************
00213 */
00214 
00215 okltest_aes_key_expansion(f) := block(
00216   /* Extreme Cases for sbox */
00217   assert(f(rijn_natl2m([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]),10,rijn_lookup_sbox) =  map(rijn_natl2m,
00218       [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
00219        [98,99,99,99,98,99,99,99,98,99,99,99,98,99,99,99],
00220        [155,152,152,201,249,251,251,170,155,152,152,201,249,251,251,170],
00221        [144,151,52,80,105,108,207,250,242,244,87,51,11,15,172,153],
00222        [238,6,218,123,135,106,21,129,117,158,66,178,126,145,238,43],
00223        [127,46,43,136,248,68,62,9,141,218,124,187,243,75,146,144],
00224        [236,97,75,133,20,37,117,140,153,255,9,55,106,180,155,167],
00225        [33,117,23,135,53,80,98,11,172,175,107,60,198,27,240,155],
00226        [14,249,3,51,59,169,97,56,151,6,10,4,81,29,250,159],
00227        [177,212,216,226,138,125,185,218,29,123,179,222,76,102,73,65],
00228        [180,239,91,203,62,146,226,17,35,233,81,207,111,143,24,142]])),
00229   true)$
00230 
00231 
00232 /* *********************************
00233    * AES encryption and decryption *
00234    *********************************
00235 */
00236 
00237 okltest_aes_round(f) := block(
00238   assert(f(rijn_natl2m([25,160,154,233,61,244,198,248,227,226,141,72,190,43,
00239     42,8]),rijn_natl2m([160,136,35,42,250,84,163,108,254,44,57,118,23,177,57,5]),
00240     rijn_lookup_sbox,rijn_mixcolumn)=
00241     rijn_natl2m([164,238,162,207,252,114,239,68,45,86,113,142,141,81,242,28])),
00242   assert(f(rijn_natl2m([72,103,77,214,108,29,227,95,78,157,177,88,238,13,56,
00243     231]),rijn_natl2m([239,168,182,219,68,82,113,11,165,91,37,173,65,127,59,0]),
00244     rijn_lookup_sbox,rijn_mixcolumn) =
00245     rijn_natl2m([224,126,108,114,247,65,112,85,181,48,74,109,254,31,10,56])),
00246   true)$
00247 
00248 okltest_aes_inv_round(f) := block(
00249   assert(f(rijn_natl2m([164,238,162,207,252,114,239,68,45,86,113,142,141,81,
00250     242,28]),rijn_natl2m([160,136,35,42,250,84,163,108,254,44,57,118,23,177,57,5]),
00251     rijn_lookup_inv_sbox,rijn_inv_mixcolumn)=
00252     rijn_natl2m([25,160,154,233,61,244,198,248,227,226,141,72,190,43,42,8])),
00253   assert(f(rijn_natl2m([224,126,108,114,247,65,112,85,181,48,74,109,254,31,10,
00254     56]),rijn_natl2m([239,168,182,219,68,82,113,11,165,91,37,173,65,127,59,0]),
00255     rijn_lookup_inv_sbox,rijn_inv_mixcolumn) =
00256     rijn_natl2m([72,103,77,214,108,29,227,95,78,157,177,88,238,13,56,231])),
00257   true)$
00258 
00259 okltest_aes_encrypt_gen(f) := block(
00260   assert(f(rijn_natl2m([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]),rijn_natl2m([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]),10,
00261     rijn_lookup_sbox,rijn_mixcolumn) = 
00262     rijn_natl2m([102,233,75,212,239,138,44,59,136,76,250,89,202,52,43,46])),
00263   assert(f(rijn_natl2m(
00264         [50,136,49,224,67,90,49,55,246,48,152,7,168,141,162,52]),
00265       rijn_natl2m([43,40,171,9,126,174,247,207,21,210,21,79,22,166,136,60]),10,
00266       rijn_lookup_sbox,rijn_mixcolumn) = 
00267     rijn_natl2m([87,22,170,250,44,198,139,155,139,155,229,13,48,227,242,6])),
00268   true)$
00269 
00270 okltest_aes_decrypt_gen(f) := block(
00271   assert(f(rijn_natl2m(
00272         [87,22,170,250,44,198,139,155,139,155,229,13,48,227,242,6]),
00273       rijn_natl2m([43,40,171,9,126,174,247,207,21,210,21,79,22,166,136,60]),10,
00274       rijn_lookup_sbox,rijn_lookup_inv_sbox,rijn_inv_mixcolumn) = 
00275     rijn_natl2m([50,136,49,224,67,90,49,55,246,48,152,7,168,141,162,52])),
00276   assert(f(rijn_natl2m([102,233,75,212,239,138,44,59,136,76,250,89,202,52,43,46]),rijn_natl2m([0,0,0,0,
00277     0,0,0,0,0,0,0,0,0,0,0,0]),10,rijn_sbox,rijn_lookup_inv_sbox,
00278     rijn_inv_mixcolumn) = 
00279     rijn_natl2m([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])),
00280   true)$
00281 
00282 /* Performs integration testing on the AES encryption and decryption functions */
00283 /* MG : Should this be higher test levels of the aes_encrypt and aes_decrypt
00284  * tests? */
00285 /* OK: What is this function doing??? */
00286 okltest_aes(f_e,f_d) := block([inputList, outputList],
00287   inputList : [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
00288   keyList : [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
00289   for i : 0 thru 20 do
00290     inputList : f_e(inputList,keyList,rijn_lookup_sbox,
00291       rijn_mixcolumn,rijn_nataddl),
00292   for i : 0 thru 20 do 
00293     inputList : f_d(inputList,keyList,rijn_lookup_sbox,
00294       rijn_lookup_inv_sbox,rijn_inv_mixcolumn, rijn_aes_log_gf2t8_add),
00295   assert(inputList = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]),
00296   true)$
00297 
00298 
00299 /* *************************************
00300    * Convenience instantiations of AES *
00301    *************************************
00302 */
00303 
00304 /* The generic aes-encryption test function, where the inputs as well as the
00305    output is given as a list of polynomials:
00306 */
00307 okltest_aes_encrypt_generic(f) := block([V1],
00308 /* Test values according to [The Design of Rijndael; Daemen, Rijmen, 
00309    Appendix D.3]
00310 */
00311   V1 : rijn_natl2m(map(hex2int, ["66","E9","4B","D4","EF","8A","2C","3B","88","4C","FA","59","CA","34","2B","2E"])),
00312   assert(f(diagmatrix(4,0),diagmatrix(4,0),10) = V1),
00313   assert(f(V1, diagmatrix(4,0),10) = rijn_natl2m(map(hex2int, ["F7","95","BD","4A","52","E2","9E","D7","13","D3","13","FA","20","E9","8D","BC"]))),
00314   true)$
00315 
00316 /* The generic aes-encryption test function, where the inputs as well as the
00317    output is given as a list of bytes:
00318 */
00319 okltest_aes_encrypt_nat_generic(f) := block([V1],
00320 /* Test values according to [The Design of Rijndael; Daemen, Rijmen, 
00321    Appendix D.3]
00322 */
00323   V1 : map(hex2int, ["66","E9","4B","D4","EF","8A","2C","3B","88","4C","FA","59","CA","34","2B","2E"]),
00324   assert(f(pad_block_16([]),pad_block_16([]),10) = V1),
00325   assert(f(V1, pad_block_16([]),10) = map(hex2int, ["F7","95","BD","4A","52","E2","9E","D7","13","D3","13","FA","20","E9","8D","BC"])),
00326   true)$
00327 
00328 /* The generic aes-decryption test function, where the inputs as well as the
00329    output is given as a list of polynomials:
00330 */
00331 okltest_aes_decrypt_generic(f) := block([V1],
00332 /* Test values according to [The Design of Rijndael; Daemen, Rijmen, 
00333    Appendix D.3]
00334 */
00335   V1 : rijn_natl2m(map(hex2int, ["66","E9","4B","D4","EF","8A","2C","3B","88","4C","FA","59","CA","34","2B","2E"])),
00336   assert(totaldisrep(f(rijn_natl2m(map(hex2int, ["F7","95","BD","4A","52","E2","9E","D7","13","D3","13","FA","20","E9","8D","BC"])), diagmatrix(4,0),10)) = V1),
00337   assert(f(V1, diagmatrix(4,0),10) = diagmatrix(4,0)),
00338   true)$
00339 
00340 /* The generic aes-decryption test function, where the inputs as well as the
00341    output is given as a list of bytes:
00342 */
00343 okltest_aes_decrypt_nat_generic(f) := block([V1],
00344 /* Test values according to [The Design of Rijndael; Daemen, Rijmen, 
00345    Appendix D.3]
00346 */
00347   V1 : map(hex2int, ["66","E9","4B","D4","EF","8A","2C","3B","88","4C","FA","59","CA","34","2B","2E"]),
00348   assert(totaldisrep(f(map(hex2int, ["F7","95","BD","4A","52","E2","9E","D7","13","D3","13","FA","20","E9","8D","BC"]), pad_block_16([]),10)) = V1),
00349 
00350   assert(f(V1, pad_block_16([]),10) = pad_block_16([])),
00351   true)$
00352 
00353 okltest_aes_encrypt_bin(f) := (
00354   assert(f(create_list(0,i,1,128),create_list(0,i,1,128),10) =
00355     hexstr2binv("66E94BD4EF8A2C3B884CFA59CA342B2E")),
00356   assert(
00357     f(hexstr2binv("3243F6A8885A308D313198A2E0370734"),
00358       hexstr2binv("2B7E151628AED2A6ABF7158809CF4F3C"),2) =
00359       hexstr2binv("AA8F5F0361DDE3EF82D24AD26832469A")),
00360   true)$
00361 
00362 okltest_aes_decrypt_bin(f) := (
00363   assert(
00364     f(hexstr2binv("66E94BD4EF8A2C3B884CFA59CA342B2E"),
00365       create_list(0,i,1,128),10) = create_list(0,i,1,128)),
00366   assert(
00367     f(hexstr2binv("AA8F5F0361DDE3EF82D24AD26832469A"),
00368       hexstr2binv("2B7E151628AED2A6ABF7158809CF4F3C"),2) =
00369     hexstr2binv("3243F6A8885A308D313198A2E0370734")),
00370   true)$
00371 
00372 okltest_aes_encrypt_hex(f) := (
00373   assert(f("0","0",10) = "66E94BD4EF8A2C3B884CFA59CA342B2E"),
00374   assert(f("00","000",10) = "66E94BD4EF8A2C3B884CFA59CA342B2E"),
00375     assert(f("3243F6A8885A308D313198A2E0370734",
00376         "2B7E151628AED2A6ABF7158809CF4F3C",2) =
00377       "AA8F5F0361DDE3EF82D24AD26832469A"),
00378   true)$
00379 
00380 okltest_aes_decrypt_hex(f) := (
00381   assert(f("66E94BD4EF8A2C3B884CFA59CA342B2E","0",10) = lpad("","0",32)),
00382   assert(f("66E94BD4EF8A2C3B884CFA59CA342B2E","000",10) = lpad("","0",32)),
00383   assert(f("AA8F5F0361DDE3EF82D24AD26832469A",
00384       "2B7E151628AED2A6ABF7158809CF4F3C",2) =
00385     "3243F6A8885A308D313198A2E0370734"),
00386   true)$
00387 
00388 
00389 okltest_aes_int(f) := (
00390   assert(f(0,0,10) = 136792598789324718765670228683992083246), 
00391   true)$
00392