OKlibrary  0.2.1.6
Sboxes.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 19.3.2011 (Swansea) */
00002 /* Copyright 2011, 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/NumberTheory/Lisp/Auxiliary.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/FiniteFunctions/Basics.mac")$
00024 
00025 des_sbox_matrices : [
00026 matrix(
00027 [14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7],
00028 [0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8],
00029 [4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0],
00030 [15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13]
00031 ),
00032 matrix(
00033 [15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10],
00034 [3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5],
00035 [0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15],
00036 [13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9]
00037 ),
00038 matrix(
00039 [10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8],
00040 [13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1],
00041 [13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7],
00042 [1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12]
00043 ),
00044 matrix(
00045 [7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15],
00046 [13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9],
00047 [10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4],
00048 [3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14]
00049 ),
00050 matrix(
00051 [2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9],
00052 [14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6],
00053 [4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14],
00054 [11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3]
00055 ),
00056 matrix(
00057 [12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11],
00058 [10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8],
00059 [9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6],
00060 [4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13]
00061 ),
00062 matrix(
00063 [4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1],
00064 [13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6],
00065 [1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2],
00066 [6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12]
00067 ),
00068 matrix(
00069 [13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7],
00070 [1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2],
00071 [7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8],
00072 [2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11]
00073 )
00074 ]$
00075 
00076 /* Converting a des-matrix to a 6 x 4 boolean function: */
00077 desmatrix2bf(M) := buildq([M], lambda([x],
00078  block([
00079   row :  polyadic2int([x[1],x[6]],2)+1,
00080   column : polyadic2int([x[2],x[3],x[4],x[5]],2)+1],
00081    int2polyadic_padd(M[row,column], 2, 4)
00082  )))$
00083 
00084 /* The i-th DES S-box as 6 x 4 boolean function: */
00085 des_sbox_bf(i) := desmatrix2bf(des_sbox_matrices[i])$
00086 /* The j-th output bit of the i-th DES S-box as a 6x1 boolean function: */
00087 des_6t1_sbox_bf(i,j) := buildq([i,j], lambda([v], [des_sbox_bf(i)(v)[j]]))$
00088 
00089 /* The combined DES "box" made by taking the conjunction of the i-th
00090    6x1-bit DES S-boxes for i in L, as an mxn boolean function.
00091    L is non-repeating, and in ascending numeric order, and has elements
00092    in {1,...,32} (indices for the 32 6x1-bit S-boxes).
00093 
00094    We have that:
00095      - m is the number of unique input variables across
00096        all i-th 6x1 DES S-boxes for i in L;
00097      - n is the number of elements in L;
00098      - The input to des_sbox_bf(L) should be the inputs to the DES S-boxes
00099        specified in L, in the order given by L, where "variables" shared by
00100        multiple S-boxes are not repeated in the input (they occur at their
00101        earliest index).
00102      - The output of des_sbox_bf(L) has the same size as L, one output-bit
00103        for each 6x1-bit S-box in indexed in L.
00104 
00105 */
00106 des_comb_sbox_bf(L) := buildq([L], lambda([x], block(
00107     [V_res : [], curr_index : 1, last_output_bit : 0],
00108   sbox6t1_to_6t4sbox_ind_ : lambda([i], floor((i-1)/4)+1),
00109   sbox6t1_to_6t4sbox_out_ind_ : lambda([i], mod(i-1,4)+1),
00110   in_same_6t4_sbox : lambda([i,j],
00111     is(sbox6t1_to_6t4sbox_ind_(i) = sbox6t1_to_6t4sbox_ind_(j))),
00112   for i : 1 thru length(L) do block([sbox6t1_inputs],
00113     sbox6t1_inputs : create_list(x[j],j, curr_index, curr_index + 5),
00114     if i < length(L) and not(in_same_6t4_sbox(L[i],L[i+1])) then
00115       curr_index : curr_index + 6,
00116     V_res : cons(
00117       des_6t1_sbox_bf(sbox6t1_to_6t4sbox_ind_(L[i]),
00118                       sbox6t1_to_6t4sbox_out_ind_(L[i]))(x)[1], V_res)),
00119   return(reverse(V_res)))))$
00120 /* For example, we have that:
00121      - des_comb_sbox_bf([1,2,3,4]) = des_sbox_bf(1)
00122      - des_comb_sbox_bf([5,6,7,8]) = des_sbox_bf(2)
00123      - des_comb_sbox_bf([9,10,11,12]) = des_sbox_bf(3)
00124      - des_comb_sbox_bf([1,2,3,4,5,6,7,8]) is the combination of
00125        des_sbox_bf(1) and des_sbox_bf(2).
00126      - des_comb_sbox_bf([1,2,3,4,5,6]) is the combination of
00127        des_sbox_bf(1) and half of des_sbox_bf(2).
00128 */
00129 
00130 
00131