Cryptography
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
begin
s.(i) <- s.(j);
s.(j) <- tmp;
end
(* 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
begin
for i = 0 to (slen-1) do
a.(i) <- (Char.code str.[i])
done;
a
end
(* Convert list of character codes to a string *)
let intlst_to_str l =
List.fold_left
(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
(List.fold_left
(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 =
intlst_to_str
(crypt
evolvefun
(f,init_state)
(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 =
encrypt
(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 =
encrypt
(fun (f,(wd, strlen, index),in_char) ->
(f,
(wd, strlen, (index + 1) mod strlen),
f wd.(index) in_char))
(f,
(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
else
begin
let j_new = (j+s.(i)+(k.(i mod k_len))) mod 256 in
swap s i j_new;
aux (i+1) j_new
end
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
begin
swap s i_next j_next;
(f,(i_next,j_next, s), (f k in_char))
end
let crypt_rc4 f kwd str =
encrypt
rc4_evolve
(f,
(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
(List.map2
(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