open Big_int;;

let print_big_int bi =
  Format.printf "@[bi \"%s\"@]" (string_of_big_int bi);;
#install_printer print_big_int;;


(**** Conversion chaine <=> liste de big_int ****)


let int_list_of_string strn =
  let rec loop acc = function
    | 0 -> acc
    | n  -> let n1=n-1
      in loop (int_of_char (String.get strn n1)::acc) n1
  in loop [] (String.length strn);;

let taille_block = 6;;
let big256 = big_int_of_int 256;;

let get_block lst =
  let rec loop res i = function
    | [] -> (res, [])
    | a::l as lst->
	if i < taille_block then
	  loop (add_big_int
		  (mult_big_int res big256)
		  (big_int_of_int a))
	    (i+1) l
	else (res, lst)
  in loop zero_big_int 1 lst;;

let coupe_block lst =
  let rec loop acc = function
    | []  -> acc
    | lst -> let blk, rem = get_block lst
      in loop (blk::acc) rem
  in List.rev (loop [] lst);;

let nums_of_string str = coupe_block (int_list_of_string str);;



let recover_block bi =
  let rec loop res i nbr =
    if i < taille_block then
      let qu,md = quomod_big_int nbr big256
      in let intmod = int_of_big_int md
      in if intmod <> 0 then
	  loop (intmod::res) (i+1) qu
	else
	  loop res (i+1) qu
    else res
  in loop [] 1 bi;;

let string_of_nums nums =
  let lint =
      List.flatten (List.map recover_block nums)
  in let lc =
      List.map
	(function i -> String.make 1 (char_of_int i))
	lint 
  in List.fold_right (^) lc "";;




(**** Calculs modulaire (inverse / power) ****)


let euclide a b =
  let rec loop
    ((d1, u1, v1) as t1)
    ((d2, u2, v2) as t2)
    = if eq_big_int d2 zero_big_int then t1
    else let qu,rem = quomod_big_int d1 d2 in
      loop t2 (rem,
	       sub_big_int u1 (mult_big_int qu u2),
	       sub_big_int v1 (mult_big_int qu v2))
  in loop (a, unit_big_int, zero_big_int)
          (b, zero_big_int, unit_big_int);;

let inverse_mod a p =
  let d, u, _ = euclide a p in
    if eq_big_int d unit_big_int then
      if le_big_int u zero_big_int then
	add_big_int u p 
      else u
    else failwith "Non invertible !!!";;

let rec power_mod a n pow =
  if eq_big_int pow zero_big_int then
    unit_big_int
  else let qu, rem = quomod_big_int
		      pow (big_int_of_int 2)
  in let sqa = mod_big_int (mult_big_int a a) n
  in let an2 = power_mod sqa n qu
  in if eq_big_int rem zero_big_int then an2
  else mod_big_int (mult_big_int a an2) n;;



(************* DEMONSTRATION ***********************)

let bi = big_int_of_string;;

let p1 = bi "131232133";;
let p2 = bi "234789337";;
let e  = bi "892033";;
let r  = (mult_big_int
	    (sub_big_int p1 unit_big_int)
            (sub_big_int p2 unit_big_int));;
let d  = inverse_mod e r;;

let n    = mult_big_int p1 p2;;
let pub  = (n, e);;
let priv = (n, d);;

let encode (n, c) m =
  power_mod m n c;;



let message = "Je vais coder le message suivant : Tout est Ok ! Ça marche !!!";;
let code =
  List.map (encode pub) (nums_of_string message);;

let decode = 
  string_of_nums (List.map (encode priv) code);;

decode = message;;