OKlibrary  0.2.1.6
IteratedBlockCipher.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 23.12.2009 (Swansea) */
00002 /* Copyright 2009, 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 /* *******************************************************************
00023    * Compositional iterated block ciphers with iterated key schedule *
00024    *******************************************************************
00025 */
00026 
00027 /*
00028    Let I be the "index set" (the possible values of round indices i), KB
00029    be the set of possible keys ("key blocks"), and MB the set of possible
00030    messages ("message blocks"; to be used for plain text and cipher text).
00031 */
00032 
00033 /* 
00034    The "key schedule" produces from an initial "key" a sequence
00035    K_0, ..., K_N of keys via the equations
00036 
00037    K_0 = key
00038    K_i = f(K_{i-1},i).
00039    
00040    Here
00041 
00042    f : KB x I -> KB
00043 
00044    is the "key round-function", while I = {1, ..., N}.
00045 */
00046 
00047 /* For such a key round-function compute a function, call it F,
00048    with F(key,i) = K_i according to the above definition:
00049 */
00050 key_schedule_0(key_round_f) := buildq([key_round_f], lambda([key,N],
00051  lreduce(key_round_f,cons(k,create_list(i,i,1,N)))))$
00052 
00053 /* 
00054    The iterated block cipher C(m,k,N) is computed via the following
00055    equations:
00056 
00057    M_0 = plain text = m
00058    M_i = rc( mr(M_{i-1},i-1), K_{i-1})
00059    M_N = cipher text = C(m,k,N)
00060 
00061    where K_0, ..., K_{N-1} is computed from k via the above
00062    key schedule. So
00063 
00064    C : MB x KB x I -> MB.
00065 
00066    For the constitutive functions rc (the "round composition") and mr (the
00067    "message round-function") we have
00068 
00069    rc : MB x KB -> MB
00070    mr : MB x I -> MB.
00071 
00072    The "round-function" rf is the map MB x KB x I -> MB,
00073    given by
00074 
00075    rf(m,k,i) = m for i=0
00076    rf(m,k,i) = rc(mr(m,i-1),k) for i > 0.
00077 
00078    So
00079 
00080    M_i = rf(M_{i-1}, K_{i-1}, i)
00081 
00082    for i > 0.
00083 
00084    We have I = {0, ..., N-1}. Often the map mr(-,0) is just the identity.
00085    Then N is one more than the "official" round count (since "key whitening"
00086    for the input has been counted as first round).
00087 */
00088 
00089 /* Given a key round-function, and a round-function given by the
00090    message-round-function and the round-composition, compute a block cipher
00091    C such that C(m,k,N) = M_N according to the above definition:
00092 */
00093 ibc_0(key_round_f, message_round_f, compo_f) := 
00094  buildq([key_round_f, message_round_f, compo_f],
00095   lambda([plain_text,key,N],
00096    block([cipher_text:plain_text, round_key:key],
00097     for i : 1 thru N do (
00098       cipher_text : compo_f(message_round_f(cipher_text,i-1), round_key),
00099       round_key : key_round_f(round_key,i)
00100    ),
00101    return(cipher_text))))$
00102 
00103 /* Remarks:
00104    For AES-like block-ciphers the composition is addition modulo 2 ("xor"),
00105    while the message-round-function is defined as follows (0 < i < N):
00106 
00107    mr(m,0) = m
00108    mr(m,i) = mix_columns(shift_rows(sub_bytes(m)))
00109    mr(m,N) = shift_rows(sub_bytes(m)).
00110 
00111    Here sub_bytes: MB -> MB is the S-box (operating on elementary units like 
00112    bytes) applied in parallel, shift_rows: MB -> MB is a simple permutation of
00113    the elementary units, while mix_columns: MB -> MB is an invertible affine
00114    map over the unit vector space.
00115 */
00116