MA 479 / CSSE 479: Cryptography
Homework 7 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.] Write a program that implements the Las Vegas algorithm which factors an RSA modulus given the encryption and decryption exponents. (See me for details.) Explain in your own words why the algorithm succeeds in one iteration with probability at least 1/2.

2. [8 points.] Implement Shanks' algorithm for solving the discrete log problem. (See me for the details.) Explain in your own words why the algorithm is correct and why it runs in O(sqrt(p)) time (neglecting logarithmic factors).

3. [8 points.] Implement fast multiplication (successive doubling) on elliptic curves in Maple; you may start with the code in the lecture notes. Your code should deal gracefully and correctly with the point at infinity.

   For the next two problems, you need to interpret ASCII messages. To send an ASCII message 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);
   

4. [4 points.] Someone you think is Alice has sent you the message:

   This is Alice. Really!

   with RSA signature: 403957491364180659273889163856195726231808344604528999278864506614180626036771409681777301593883658685395194553022662652995737604338970. According to Alice's secure web site (a trusted source), her public key is e = 67, n=2907354897182427562197295231552018137414565442749272241126385970800225422898836069121817735655252040276523300434202169894987283419895539. Verify that the message was correctly signed by Alice.

5. Fixed 9 May [6 points.] Read Problem 10.4 from the textbook.  Your ElGamal global elements are: q=1766847064778384329583297500742918515827483896875618958121606201292619891, α=3.  Your private key is:
   X_A=262135447844327898368064488079704732389915835738393802798002956710974153 and your public key is:
   Y_A=1161294372566163280738724307716167784483932985449154183350107102014096707.
   You receive the following encrypted message:
   C₁=1356580608075200111353561247755551523687496022456972329549648252659517452, C₂=46191453237502773983138214360262384066255711708183892658988691012817835.
   Decrypt the (ASCII) message.  Can you figure out what the k used to send the message is?
   
   
   
6. [6 points.] Using (ElGamal) Elliptic Curve Cryptography with the curve y² = x³+750x+188, the prime p=751, and the "generator" G=(0, 376), send Bob the point (361, 8) using the public key (256, 409).  (You will have to select a nonce.)
   
   
7. [6 points.] You are using (ElGamal) Elliptic Curve Cryptography with the curve y² = x³+750x+188, the prime p=751, and the "generator" G=(0, 376).  Your private key is x_A=34 and your public key is Y_A=(522, 469).  You receive the following encrypted message: (180, 343), (233, 495); (139, 413), (97, 284); (510, 429), (687, 244); (734, 552), (7, 240); (93, 631), (417, 158); (237, 23), (254, 247); (207, 215), (301, 493). (The first point in each pair is C₁ and the second is C₂.)  Decrypt the message and interpret it by taking the x coordinates of the points, dividing them by 20 (throwing away the remainder), and using 0 through 9 as decimal digits and 10 through 35 as the letters A through Z.