Matt's Blog


Sun Dec 3 12:23:24 EST 2006

A stream cipher can be thought of as a machine that has internal state and generates a stream of random values as an input stream is fed into the machine, with a stream of random values coming out of the output when the input stream and generated stream are combined. The advantage of this viewpoint is that a general control function can be constructed that can take a number of different encryption machines as arguments eg a Caeser shift cipher, Vignere cipher or modern stream cipher such as RC4.

This machine can be represented by a structure containing

  • combination function for input and generated values
  • internal state of the machine
  • next input value to process

The evolution function then takes this structure and returns a new structure with

  • new combination function (or the old one if it doesn't change)
  • new state
  • output value

The encryption machine function is then used as an argument of a higher order function that maps the machine over the list of input values to produce the list of output values.

  • Sidenote: the openssl command can be used to encrypt files using a range of ciphers eg openssl rc4 -in infile -out outfile.enc Also does base64 encoding - useful tool!

Shown below is the ocaml code for a general stream cipher setup. The main functions are crypt and encrypt, which define the framework for the actual algorithm:

(* Utility functions *)
(* range function to return list of integers from [a;...;b] *)
let rec range a b = 
  if a > b then [] else (a :: (range (a+1) b))

(* Swap two elements of an array *)
let swap s i j=
  let tmp = s.(i) in
    s.(i) <- s.(j);
    s.(j) <- tmp;

(* Convert string to array of character codes *)
let str_to_intarray str = 
  let slen = String.length str in
  let a = Array.make slen 0 in
    for i = 0 to (slen-1) do
      a.(i) <- (Char.code str.[i])

(* Convert list of character codes to a string *)
let intlst_to_str l = 
    (fun acc x -> acc ^ (String.make 1 (Char.chr x)))
    "" l

(* The encryption functions *)

(* General stream cipher is defined by an internal state, a function
to create an output character given the current state and the input
character, and an evolution function to make the cipher machine go to
a new internal state *)
let crypt evolvefun (f,init_state) cintlst = 
  List.rev (snd
      (fun ((f,state),acc) x -> 
        let (new_f,new_state, out_char) = evolvefun (f,state,x) in
          ((new_f,new_state), out_char::acc)
      ) ((f,init_state),[]) cintlst));;

let encrypt evolvefun (f,init_state) str = 
  (Array.to_list (str_to_intarray str)))

(* Caeser shift cipher:  replace each character with the one "shift"
charcters ahead in the alphabet eg if shift = 3 a->d, b->e etc.
Precondition:  character is lowercase or space (space gets transmitted
as is) *)
let crypt_c f shift str =
    (fun (f,state,in_char) -> (f,state,f state in_char))
    (f, shift) str

let shift_right k = 
  (fun x -> 
    let start_code = Char.code 'a' in
    let space_code = Char.code ' ' in
    if x = space_code then space_code else
    (start_code + (((x-start_code) + k) mod 26)))

let encrypt_c = crypt_c shift_right
let decrypt_c = crypt_c (fun k-> shift_right (26 -k))

(* Vignere cipher: similar to the Caeser shift cipher, step through
the elements of a key word and add each character in turn to the
incoming list of characters.  Again, input only lowercase or space. 
let crypt_v f kwd str =
    (fun (f,(wd, strlen, index),in_char) -> 
        (wd, strlen, (index + 1) mod strlen),
        f wd.(index) in_char))
      (str_to_intarray kwd, String.length kwd,0)) str

let encrypt_v = 
  crypt_v (fun k-> shift_right (k + 1 - Char.code 'a'))
let decrypt_v = 
  crypt_v (fun k-> shift_right (26 -(k + 1 - Char.code 'a')))

(* Implementation of the RC4 stream cipher *)
(* Basic algorithm:  Define an S-box that takes an 8-bit input and
returns an 8-bit output, modifying the S-box in the process.
If the byte stored in the S-box at position k is s(k) then the
algorithm to generate "random" byte K is:
i = (i + 1) mod 256
j = (j + s(i)) mod 256
swap s(i) and s(j)
t = (s(i) + s(j)) mod 256
K = s(t) 

To initialise:
1. fill S-box with s(0)=0, s(1)=1, ... s(255)=255
2. Fill another 256 byte array with [|k1;k2;k3;...;kn;k1;k2;...|]
3. j=0; for i=0 to 255 do
          j = (j+s(i)+k(i)) mod 256
          swap s(i) and s(j)


(* RC4 initialisation function for k an array of ints *)
let rc4_init k = 
  let k_len = Array.length k in
  let s=Array.of_list (range 0 255) in
  let rec aux i j = 
    if i>255 then s
        let j_new = (j+s.(i)+(k.(i mod k_len))) mod 256 in
        swap s i j_new;
        aux (i+1) j_new
  in aux 0 0

(* Evolution function to evolve rc4 internal state and return output
character *)
let rc4_evolve (f,(i,j,s), in_char) =
  let i_next = (i+1) mod 256 in
  let j_next = (j+s.(i_next)) mod 256 in
  let k = s.((s.(i_next) + s.(j_next)) mod 256) in
    swap s i_next j_next;
    (f,(i_next,j_next, s), (f k in_char))

let crypt_rc4 f kwd str = 
    (0,0, (rc4_init (str_to_intarray kwd)))) str

let to_bitlist nbits num = 
  let rec aux k n acc = 
    if k=0 then acc else aux (k-1) (n/2) ((n mod 2)::acc)
  in aux nbits num []

let xor num1 num2 = 
  let bl1 = to_bitlist 8 num1 and
      bl2 = to_bitlist 8 num2 in
  List.fold_left (fun acc x -> 2*acc + x) 0 
      (fun x y -> match x, y with
       | 0, 0 -> 0 | 0, 1 -> 1
       | 1, 0 -> 1 | _, _ -> 0) bl1 bl2)

let encrypt_rc4 = crypt_rc4 (fun k x -> xor k x)
let decrypt_rc4 = encrypt_rc4

[code] [ocaml]


code (31)

erlang (6)
ideas (24)
lisp (1)
me (14)
notes (6)
ocaml (4)
physics (46)
qo (7)
unix (6)
vim (3)