|| ------------------------------------------------------------------ || 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") ]