|| ------------------------------------------------------------------
|| Projet Miranda -- simple RSA (?) encryption/decryption
|| Michael Vorburger, cours de progr. IV, Prof. C. Rapin, EPFL
|| May 23, 1997
|| ------------------------------------------------------------------

%include "diophante.m"


%include "keys.m"

e_ = r mod (p-1)  ||  ATTENTION: e is predefined, euler's number (see log)
f  = r mod (q-1)

i = (x0 (diophante e_ (1-p) 1)) mod (abs (delta_x (diophante e_ (1-p) 1)))
j = (x0 (diophante f  (1-q) 1)) mod (abs (delta_x (diophante f (1-q) 1)))



|| ------------------------------------------------------------------
||    general & math specific helper functions
|| ------------------------------------------------------------------

|| tuple_x & tuple_y  --  helper functions for decomposing tuples/pairs

tuple_x (x,y) = x
tuple_y (x,y) = y


|| pow_mod a k p = a^k mod p
|| The struff below is for power (^) and mod with big numbers.
|| Source: Function puiss_mod from Corrige Ex. 15, file premiers.m

pow_mod :: num->num->num->num
pow_mod a 0 p = 1
pow_mod a k p
  = pow_mod ((a*a) mod p) (k div 2) p, if k mod 2=0
  = (a*(pow_mod a (k-1) p)) mod p, otherwise



|| ------------------------------------------------------------------
||    encoding functions (pure math, no I/O)
|| ------------------------------------------------------------------

|| one_group string n p256 sofar
|| Builds ONE "packet" by forming the polynomial string!0 + 256*string!1 
||  + 256^2*string!2 etc. until the packet value exceeds n. Initially,
|| set p256=1 & sofar=0. This function returns a tuple containing 
|| (remaining_string, value_of_converted_string)

one_group :: [char]->num->num->num -> ([char],num)
one_group [] n p256 sofar
  = ([], sofar)
one_group string n p256 sofar
  = one_group (tl string) n (256*p256) ( code (hd string)*p256 + sofar),   
       if ( code (hd string)*p256 + sofar ) < n
  = (string, sofar),
       otherwise


|| grouping string n
|| converts string into a list of numbers, all of which are < n.
|| (Numbers are polynomials; characters from string are coefficients to 256^k)

grouping :: [char]->num -> [num]
grouping [] n
  = []
grouping string n 
  = tuple_y( a_group ) : grouping ( tuple_x(a_group) ) n 
    where a_group=one_group string n 1 0
  
    
|| codifie n r s
|| Encodes num. _value_ s (not complete string) using n & r as public key
|| Basically, m=codifie r n s  ==>  m=s^r mod n

codifie :: num->num->num -> num
codifie n r s
  = pow_mod s r n



|| ------------------------------------------------------------------
||    decoding functions (pure math, no I/O)
|| ------------------------------------------------------------------


|| decodifie m
|| Decodes num. value m (not complete string) using the private key.
|| Constant numbers which are independant from m are calculated above.

decodifie :: num -> num
decodifie m
  = v + x * p
        where x = (x0 (dio)) mod abs (delta_x (dio))
              dio = diophante p (-q) (w-v)
              v = pow_mod t i p
              w = pow_mod u j q
              t = m mod p
              u = m mod q


|| degrouping_one n
|| Converts one polynomial packet back to string. (Inverse of one_group above)

degrouping_one :: num -> [char]
degrouping_one n
  = (decode (n mod 256) : degrouping_one (n div 256)), if n>256
  = [decode n], otherwise


|| degrouping 
|| converts a list of polynomial packets back to one string

degrouping :: [num] -> [char]
degrouping []
  = []
degrouping list
  = (degrouping_one (hd list)) ++ (degrouping (tl list))


|| ------------------------------------------------------------------
||    de- & encode string & I/O operations
|| ------------------------------------------------------------------

|| encode_text text n r   --   encodes the string (text)

encode_text :: [char]->num->num->[char]
encode_text text n r
  = lay (
          map
                show
                ( map
                      ( codifie n r )
                      ( grouping text n )
                )
        ) 


|| encode_file filename n r   --  encodes the file given by filename

encode_file :: [char]->num->num->[sys_message]
encode_file filename n r
  = [Tofile (filename++".encoded")
     (encode_text (read filename) n r)         
     , Closefile (filename++".encoded") ]



|| decode_text text  --  decodes the given string (text)

decode_text :: [char]->[char]
decode_text text
  = degrouping ( 
                 map
                      decodifie
                      (map numval (lines text))
               )
  
  
  
|| decode_file filename   --   decodes the file given by filename
  
decode_file filename
  = [Tofile (filename++".decoded")
     (decode_text (read filename))
     , Closefile (filename++".decoded") ]