MA 479 / CSSE 479: Cryptography
Homework 5 problems inspired by Computer Science

Rose-Hulman Institute of Technology
A joint effort of the
Department of Mathematics
and the Department of Computer Science & Software Engineering
Spring term, 2003-2004

• Use any language and environment you wish. Please check with me if you have any questions about what features of the language or environment you may use. In particular, please do not use pre-packaged matrix calculation routines.
• The user interface is up to you.
• Turn in the source and object code of the program, and any supporting materials, to these drop boxes.
• Make sure you include clear instructions on how the code is to be run! Most of the points will be determined based on whether the program performs correctly on test cases.

The non-programming problems you may turn in to the drop boxes or on paper.

Drop box submissions are due at midnight on the due date. Paper submissions are due in class or in the box outside my office by 5:00 p.m.

1. [8 points.] Create software that can encrypt and decrypt using the Pohlig-Hellman exponential cipher as explained in class. (That is, block size m=2, p=3001, "a"=0.)
    
2. [12 points.] Create software that can encrypt and decrypt using the Pohlig-Hellman exponential cipher with arbitrary (within reason) block size m.  Have your program report its value of p so that the results can be checked.  (Continue to use "a"=0.)
    
3. [4 points.] Demonstrate your understanding of the key-generation step of the RSA cryptosystem by:
   • Finding two large primes.
   • From those primes, find a public key e and corresponding private key d.

   This problem is VERY easy in Maple because:

   • Maple has isprime and ithprime functions.
   • Maple has a gcd function.
   • Maple can compute the inverse of x mod y by:

        x &^ (-1) mod y
   

4. [2 points.] Demonstrate your understanding of the encryption step of the RSA cryptosystem by:
   • Given the public key (n, e) = (66416653, 1000001),
   • encrypt the message 10101010.
   This problem is VERY easy in Maple.
    

5. [2 points.] Demonstrate your understanding of the decryption step of the RSA cryptosystem by:
   • Given the private key (n, d) = (66416653, 1000001),
   • decrypt the encrypted message 53404979.
   This problem is VERY easy in Maple.
   
   

   For the next two problems, you need to send ASCII messages using RSA. To send an ASCII message using RSA we first need to translate the message into a number; e.g. "HI"=104105. In Maple, this may be done by

   mess:= convert( "hi", bytes);
   len:=nops(mess);
   numbr:= sum( mess[k]*1000^(len-k) , k=1..len);
   

   This may be reconverted back to characters in Maple by using the commands

   rongway:=convert( numbr, base,1000); 
   len:=nops(rongway); 
   thisisit:= [seq( rongway[len-k], k=0..(len-1))]; 
   convert(thisisit,bytes);
   

6. [4 points.] Your public key is: e=5
   n =1000000000000000000000000000000000000000000000000000000000000000000160300000013270000000000000000000000000000000000000000000000000000000000000002127181
   

   You know that n's prime factors are 10⁷⁰+1603 and 10⁸⁰+1327. You receive the following encrypted message:
   223897127930723938249906123728900845551197361369896121141599622622367463987177076976678763976252906951878641368964747814858009593601674182847816720986
   Decrypt the (ASCII) message.
   
   
   

7. [32 points.] Supppose you intercept a message which was sent using the public key: e=797
   n = 253075277577172543965736655367038444769478357341928704773134781671301027140846923219830993503499361347997474759329498343943360959479808000001494433
   The encrypted message is:
   68350473913328196310472472283006831689697773472427700170952459216819208065724984712084640638257482301343417836142040578828058507305387062978715492
   What is the original (ASCII) message?