Programming  Assignment 2

Writing an RSA cryptographic system.  RSA system works as follows : We use two large primes  p and q,  n = pq, and compute the "encrypt key" e by gcd(e,(p-1)(q-1)) = 1.  At the same time, the "decrypt key" d can be found;  d is an inverse of e mod (p-1)(q-1).

Let John be a person who want to send a secret message to Mary.  Mary generates e,d,n as explained above and publishs two keys to the public: e, n.  The d is kept as the secret decrypt key by Mary herself.  John uses e, n  to encrypt his message, let it be M,  (the message is considered to be a block of number not larger than n),

        C = M^e mod n

John sends the encrypted message C to May.  Upon receiving C, Mary decrypts the message using her secret key d,  by

        M = C^d mod n

You write two separate programs : encrypt, decrypt which take standard input and standard output. The input will be a text of this form :  p q message  .  where p, q is two primes not larger than 8 bits and represented by hex number, two digits of 0..9,A..F and message is a string of printable
characters (including space and newline) maximum length is 2000 character.  The encrypt program
takes the input and produce an encrypted output.  Your output should also be a text of the form :
        e d n c1 c2 c3 ...
where e, d, n  are your keys in 4 digits hex number and c1, c2, c3 ... are the encrypt message which caused by encrypting the message character by character.  They are printed as sequence of 4 digits hex number.  The decrypt program takes this output and produce the original message.

Bonus will be given to the solution that can handle p, q larger than 8 bits

Sample of input text : short   long
Sample of encrypted output : short   long

Submission of the solution required the following :

• On screen test with my unknown plain input text (the same format as Sample).  Your encrypt program must produce the encrypted output which will be check by my decrypt program
• On screen test with my unknown encrypted input text (the same format as Sample).  Your decrypt program must produce the plain output which will be check against my know plain text
• The written report that include the listing of the important part of your program and your analysis of the running time of  your algorithm.
• Answer the question how your algorithm work.
• In case, your program has trouble with input/output format, you are allowed to correct your program in-time.  I will not accept any submission after  the time is up (13:00).