OKlibrary  0.2.1.6
Cipher.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 27.2.2012 (Swansea) */
00002 /* Copyright 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 
00026 
00027 /* *****************
00028    * KeeLoq cipher *
00029    *****************
00030 */
00031 
00032 /* Keeloq is a 32-bit shift-register block cipher with 32-bit plaintext and
00033    ciphertext, a 64-bit key, and 528 rounds.
00034 
00035    All additions and multiplications are in ZZ_2.
00036 
00037    The encryption algorithm for KeeLoq, as described in [Algebraic and Slide
00038    attacks on KeeLoq; Gregory Bard, Nicholas Courtois and David Wagner], is:
00039     1) The inputs are
00040           - plaintext, P_s, a 32-bit binary string, and
00041           - key, K_s, a 64-bit binary string.
00042        A k-bit binary string here is a string over {0,1} of length k.
00043     2) Declare (0-indexed) {0,1}-valued arrays
00044           - K, of size 32, and
00045           - L, of size 560,
00046        both initialised to all 0.
00047     3) Set K to reverse(K_s).
00048        K[31] is the leftmost bit of K_s, K[0] the rightmost.
00049     4) Set the first 32 values of L to reverse(P_s).
00050        L[31] is the leftmost bit of P_s, L[0] the rightmost.
00051     5) For i in 0 to 527 do
00052            L[i+32]= K[i mod 64] + L[i] + L[i+16] +
00053                       NLF(L[i+31], L[i+26],L[i+20],L[i+9],L[i+1])
00054     6) The ciphertext is the 32-bit string of 0s and 1s corresponding to
00055        L[559],...,L[528] where L[559] is the leftmost bit and
00056        L[528] is the rightmost digit.
00057 
00058    The non-linear feedback function is defined as an ANF as follows
00059 
00060     NLF(a,b,c,d,e) := d + e + ac + ae + bc + be + cd + de + ade + ace
00061                       + abd + abc.
00062 
00063    The arrays above are 0-based for simplicity, given the use of mod.
00064    The binary strings P_s, K_s and the ciphertext are reversed
00065    because they are indexed in reverse (e.g., the leftmost plaintext
00066    bit has index 31) in [Algebraic and Slide attacks on KeeLoq; Gregory Bard,
00067    Nicholas Courtois and David Wagner].
00068 
00069    The todo "Good definition" in
00070    Cryptology/Lisp/CryptoSystems/KeeLoq/plans/general.hpp discusses replacing
00071    this definition with an equivalent definition which better fits into the
00072    OKlibrary.
00073 
00074 */
00075 
00076 /* The KeeLoq non-linear feedback function: */
00077 /* ??? what are a,b,c,d,e ??? */
00078 keeloq_nlf(a,b,c,d,e) :=
00079   mod(d+e+a*c+a*e+b*c+b*e+c*d+d*e+a*d*e+a*c*e+a*b*d+a*b*c, 2)$
00080 
00081 /* The Keeloq round taking an 8-bit vector as input: */
00082 /* ??? what is V w.r.t. our system (see below) ??? what is the output ??? */
00083 keeloq_round(V) :=
00084   mod(V[1] + V[2] + V[3] + keeloq_nlf(V[4],V[5],V[6],V[7],V[8]),2)$
00085 /* (8+1)-bit boolean function for the KeeLoq round: */
00086 keeloq_round_bf(V) := [mod(keeloq_round(rest(V,-1))+V[9]+1, 2)]$
00087 
00088 
00089 /* Encrypting plaintext P, a boolean list of length 32, with key K, a boolean
00090    list of length 64 for r-round KeeLoq: */
00091 /* ??? what is a "boolean list" ??? what is the output ??? */
00092 keeloq_encryption_gen(r, P,K) := block([P_c : reverse(P), K_rev : reverse(K)],
00093   for i : 0 thru r-1 do
00094     P_c : endcons(
00095       keeloq_round([K_rev[mod(i,64)+1],P_c[i+1],P_c[i+16+1],P_c[i+31+1],
00096         P_c[i+26+1],P_c[i+20+1],P_c[i+9+1],P_c[i+1+1]]), P_c),
00097   return(reverse(rest(P_c, length(P_c) - 32))))$
00098 keeloq_encryption(P,K) := keeloq_encryption_gen(528,P,K)$
00099 
00100 /* ??? Where is the validation information ??? */
00101 
00102