OKlibrary  0.2.1.6
ByteField.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 24.12.2009 (Swansea) */
00002 /* Copyright 2009, 2010, 2012 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/Algebra/Lisp/FiniteFields.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/MaximaInternals/Auxiliary.mac")$
00026 
00027 kill(f)$
00028 
00029 /* ******************
00030    * Representation *
00031    ******************
00032 */
00033 
00034 okltest_rijn_polynomial(f) := block([x],
00035   assert(hipow(f,x) = 8),
00036   assert(gf_set(2,8,f)[1] # false),
00037   for i : 0 thru 7 do
00038     assert(elementp(coeff(f,x,i),{0,1}) = true),
00039   true)$
00040 
00041 okltest_rijn_stand(f) := block([x],
00042   assert(f(0) = 0),
00043   assert(f(1) = 1),
00044   assert(f(x^8) = x^4+x^3+x+1),
00045   assert(f(x^8 + x^4 + x^3 + x + 1) = 0),
00046   true)$
00047 
00048 okltest_nat2polybin(f) := block([x],
00049   assert(f(0) = 0),
00050   assert(f(1) = 1),
00051   assert(f(2) = x),
00052   assert(f(3) = x+1),
00053   assert(f(4) = x^2),
00054   for e : 0 thru 5 do
00055     assert(f(2^e) = x^e),
00056   true)$
00057 
00058 okltest_polybin2nat(f) := block([x],
00059   assert(f(0) = 0),
00060   assert(f(1) = 1),
00061   assert(f(x) = 2),
00062   assert(f(x+1) = 3),
00063   assert(f(x^2) = 4),
00064   for e : 0 thru 5 do
00065     assert(f(x^e) = 2^e),
00066   true)$
00067 
00068 okltest_rijn_stand_vec(f) := (
00069   assert(f([]) = []),
00070   assert(f([0]) = [0]),
00071   assert(f([1]) = [1]),
00072   assert(f([1,0,0,0,0,1,1]) = [1,0,0,0,0,1,1]),
00073   assert(f([2]) = [0]),
00074   assert(f([3]) = [1]),
00075   assert(f([3,1,1,1,2]) = [1,1,1,1,0]),
00076   true)$
00077 
00078 okltest_nat2vecbin(f) := (
00079   assert(f(0) = [0]),
00080   assert(f(1) = [1]),
00081   assert(f(2) = [1,0]),
00082   assert(f(3) = [1,1]),
00083   assert(f(4) = [1,0,0]),
00084   for e : 0 thru 10 do
00085     assert(f(2^e) = cons(1,create_list(0,i,1,e))),
00086   true)$
00087 
00088 okltest_nat2vecbin_rijn(f) := (
00089   assert(f(0) = [0,0,0,0,0,0,0,0]),
00090   assert(f(1) = [0,0,0,0,0,0,0,1]),
00091   assert(f(2) = [0,0,0,0,0,0,1,0]),
00092   assert(f(3) = [0,0,0,0,0,0,1,1]),
00093   assert(f(4) = [0,0,0,0,0,1,0,0]),
00094   for e : 0 thru 7 do
00095     assert(f(2^e) = create_list(if i = 8 - e then 1 else 0, i, 1, 8)),
00096   true)$
00097 
00098 okltest_vecbin2nat(f) := (
00099   assert(f([0]) = 0),
00100   assert(f([1]) = 1),
00101   assert(f([1,0]) = 2),
00102   assert(f([1,1]) = 3),
00103   assert(f([1,0,0]) = 4),
00104   for e : 0 thru 10 do
00105     assert(f(cons(1,create_list(0,i,1,e))) = 2^e),
00106   true)$
00107 
00108 okltest_polybin2vecbin(f) := (
00109   assert(f(0) = [0]),
00110   assert(f(1) = [1]),
00111   assert(f(x) = [1,0]),
00112   assert(f(x+1) = [1,1]),
00113   assert(f(x^2) = [1,0,0]),
00114   for e : 0 thru 10 do
00115     assert(f(x^e) = cons(1,create_list(0,i,1,e))),
00116   true)$
00117 
00118 okltest_polybin2vecbin_rijn(f) := (
00119   assert(f(0) = [0,0,0,0,0,0,0,0]),
00120   assert(f(1) = [0,0,0,0,0,0,0,1]),
00121   assert(f(x) = [0,0,0,0,0,0,1,0]),
00122   assert(f(x+1) = [0,0,0,0,0,0,1,1]),
00123   assert(f(x^2) = [0,0,0,0,0,1,0,0]),
00124   for e : 0 thru 7 do
00125     assert(f(x^e) = create_list(if i = 8 - e then 1 else 0, i, 1, 8)),
00126   true)$
00127 
00128 okltest_vecbin2polybin(f) := (
00129   assert(f([0]) = 0),
00130   assert(f([1]) = 1),
00131   assert(f([1,0]) = x),
00132   assert(f([1,1]) = x+1),
00133   assert(f([1,0,0]) = x^2),
00134   for e : 0 thru 10 do
00135     assert(f(cons(1,create_list(0,i,1,e))) = x^e),
00136   true)$
00137 
00138 okltest_polybin2mvecbin(f) := (
00139   assert(f(0) = matrix([0])),
00140   assert(f(1) = matrix([1])),
00141   assert(f(x) = matrix([1],[0])),
00142   assert(f(x+1) = matrix([1],[1])),
00143   assert(f(x^2) = matrix([1],[0],[0])),
00144   for e : 0 thru 10 do
00145     assert(f(x^e) = apply(matrix,cons([1],create_list([0],i,1,e)))),
00146   true)$
00147 
00148 okltest_polybin2mvecbin_rijn(f) := (
00149   assert(f(0) = matrix([0],[0],[0],[0],[0],[0],[0],[0])),
00150   assert(f(1) = matrix([0],[0],[0],[0],[0],[0],[0],[1])),
00151   assert(f(x) = matrix([0],[0],[0],[0],[0],[0],[1],[0])),
00152   assert(f(x+1) = matrix([0],[0],[0],[0],[0],[0],[1],[1])),
00153   assert(f(x^2) = matrix([0],[0],[0],[0],[0],[1],[0],[0])),
00154   for e : 0 thru 7 do
00155     assert(f(x^e) = apply(matrix,
00156         create_list(if i = 8 - e then [1] else [0], i, 1, 8))),
00157   true)$
00158 
00159 okltest_mvecbin2polybin(f) := (
00160   assert(f(matrix([0])) = 0),
00161   assert(f(matrix([1])) = 1),
00162   assert(f(matrix([1],[0])) = x),
00163   assert(f(matrix([1],[1])) = x+1),
00164   assert(f(matrix([1],[0],[0])) = x^2),
00165   for e : 0 thru 10 do
00166     assert(f(apply(matrix,cons([1],create_list([0],i,1,e)))) = x^e),
00167   true)$
00168 
00169 
00170 
00171 /* **************
00172    * Operations *
00173    **************
00174 */
00175 
00176 okltest_rijn_add(f) := block([x],
00177   assert(f(0,0) = 0),
00178   assert(f(x,x) = 0),
00179   assert(f(x,x^4+x^2+x+3) = x^4+x^2+1),
00180   true)$
00181 
00182 okltest_rijn_mul(f) := block([x],
00183   assert(f(0,0) = 0),
00184   assert(f(0,x^2) = 0),
00185   assert(f(1,x^3+x^2+3) = x^3+x^2+1),
00186   assert(f(x^4,x^4) = x^4+x^3+x+1),
00187   assert(f(rijn_polynomial-1,rijn_polynomial-1) = 1),
00188   true)$
00189 
00190 okltest_rijn_matmul(f) := block([x],
00191   assert(f(matrix(),matrix()) = matrix()),
00192   assert(f(matrix([0]),matrix([0])) = matrix([0])),
00193   assert(f(matrix([x,0],[0,x]),matrix([x,0],[0,x])) = matrix([x^2,0],[0,x^2])),
00194   assert(f(matrix([x,1],[x,x^2]),matrix([1,x^3],[x,0])) = matrix([0,x^4],[x^3+x,x^4])),
00195   assert(f(matrix([x^4,0],[0,x^4]),matrix([x^4,0],[0,x^4])) = matrix([x^4+x^3+x+1,0],[0,x^4+x^3+x+1])),
00196   true)$
00197 
00198 okltest_rijn_inv(f) := block([x],
00199   assert(f(1) = 1),
00200   assert(f(x) = x^7+x^3+x^2+1),
00201   assert(tcre_p(f(x+x^2)) = false),
00202   true)$
00203 
00204 okltest_rijn_einv(f) := (
00205   assert(f(0) = 0),
00206   assert(okltest_rijn_inv(f) = true),
00207   true)$
00208 
00209 okltest_rijn_natadd(f) := (
00210   assert(f(0,0) = 0),
00211   assert(okltest_rijn_add(buildq([f], lambda([a,b], nat2polybin(f(polybin2nat(rijn_stand(a)),polybin2nat(rijn_stand(b))))))) = true),
00212   true)$
00213 
00214 okltest_rijn_natmul(f) := (
00215   assert(f(0,0) = 0),
00216   assert(f(0,1) = 0),
00217   assert(f(1,1) = 1),
00218   assert(f(2,141) = 1),
00219   true)$
00220 
00221 okltest_rijn_natinv(f) := (
00222   assert(f(0) = 0),
00223   assert(f(1) = 1),
00224   assert(f(2) = 141),
00225   assert(f(polybin2nat(rijn_stand(-1))) = polybin2nat(rijn_stand(-1))),
00226   true)$
00227 
00228 okltest_rijn_inv_pmtf(f) := (
00229   assert(create_list(f(i)-1,i,1,256) =
00230     [0,1,141,246,203,82,123,209,232,79,41,192,176,225,229,199,116,180,170,75,
00231     153,43,96,95,88,63,253,204,255,64,238,178,58,110,90,241,85,77,168,201,193,
00232     10,152,21,48,68,162,194,44,69,146,108,243,57,102,66,242,53,32,111,119,187,
00233     89,25,29,254,55,103,45,49,245,105,167,100,171,19,84,37,233,9,237,92,5,202,
00234     76,36,135,191,24,62,34,240,81,236,97,23,22,94,175,211,73,166,54,67,244,71,
00235     145,223,51,147,33,59,121,183,151,133,16,181,186,60,182,112,208,6,161,250,
00236     129,130,131,126,127,128,150,115,190,86,155,158,149,217,247,2,185,164,222,
00237     106,50,109,216,138,132,114,42,20,159,136,249,220,137,154,251,124,46,195,
00238     143,184,101,72,38,200,18,74,206,231,210,98,12,224,31,239,17,117,120,113,
00239     165,142,118,61,189,188,134,87,11,40,47,163,218,212,228,15,169,39,83,4,27,
00240     252,172,230,122,7,174,99,197,219,226,234,148,139,196,213,157,248,144,107,
00241     177,13,214,235,198,14,207,173,8,78,215,227,93,80,30,179,91,35,56,52,104,
00242     70,3,140,221,156,125,160,205,26,65,28]),
00243   true)$
00244 
00245 okltest_rijn_vecadd(f) := (
00246   assert(f([0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]) = [0,0,0,0,0,0,0,0]),
00247   for i : 0 thru 7 do
00248     assert(f(nat2vecbin_rijn(2^i),nat2vecbin_rijn(0)) = nat2vecbin_rijn(2^i)),
00249   for i : 0 thru 7 do
00250     assert(f(nat2vecbin_rijn(2^i),nat2vecbin_rijn(2^i)) = nat2vecbin_rijn(0)),
00251   assert(f([1,0,1,1,0,1,0,0], [1,1,1,1,1,1,1,1]) = [0,1,0,0,1,0,1,1]),
00252   true)$
00253 
00254 okltest_rijn_vecmul(f) := (
00255   assert(f([0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]) = [0,0,0,0,0,0,0,0]),
00256   assert(f([0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1]) = [0,0,0,0,0,0,0,1]),
00257   for i : 0 thru 7 do
00258     assert(f(nat2vecbin_rijn(2^i),nat2vecbin_rijn(0)) = nat2vecbin_rijn(0)),
00259   for i : 0 thru 6 do
00260     assert(f(nat2vecbin_rijn(2^i),nat2vecbin_rijn(2)) = nat2vecbin_rijn(2^(i+1))),
00261   for i : 0 thru 3 do
00262     assert(f(nat2vecbin_rijn(2^i),nat2vecbin_rijn(2^i)) = nat2vecbin_rijn(2^(2*i))),
00263   assert(f(nat2vecbin_rijn(2^7),nat2vecbin_rijn(2)) = [0,0,0,1,1,0,1,1]),
00264   assert(f(nat2vecbin_rijn(2^4),nat2vecbin_rijn(2^4)) = [0,0,0,1,1,0,1,1]),
00265   assert(f(nat2vecbin_rijn(2^7), nat2vecbin_rijn(2^7)) = [1,0,0,1,1,0,1,0]),
00266   assert(f(nat2vecbin_rijn(56), nat2vecbin_rijn(32)) = [0,1,0,0,0,0,0,1]),
00267   true)$
00268 
00269 okltest_rijn_vecinv(f) := (
00270   assert(f([0]) = [0,0,0,0,0,0,0,0]),
00271   assert(f([1]) = [0,0,0,0,0,0,0,1]),
00272   assert(f([0,0,0,0,0,1,0,1]) = [0,1,0,1,0,0,1,0]),
00273   assert(okltest_rijn_inv(
00274       buildq([f], lambda([a], vecbin2polybin(f(polybin2vecbin_rijn(a))))))),
00275   /* XXX */
00276   true)$
00277 
00278