CPSC 120 Programming Project 4
Public Key Cryptography

Due Friday, December 5, 2003 by 4:00 p.m.

In a public key cryptography system each person who wants to communicate with others has two sets of "keys" - one set is private, only known to the owner, and the other set is public, available to anyone who wants to send encrypted messages to the owner of the key. The public keys are used by the sender to encode the message and the private keys are used by the recipient to decode the message. Since the private keys are known only to the owner, that person is the only one who can read the message.

In this project you will implement a version of the RSA public key encryption scheme. This scheme is named after its developers - Ron Rivest, Adi Shamir, and Len Adleman. The system works as follows:

Each participant (which we will call a coder) constructs a "key" for encoding and decoding as follows:

1. Pick two primes p and q and compute n = pq. (In a good coding system p and q should be very large.)
2. Compute m, the least common multiple of p - 1 and q - 1.
3. Pick r so that is has no divisors in common with m other than 1 (that is, r is relatively prime to m - any such r works).
4. Find s so that rs = 1 (mod m) (there is only one such s between 1 and m).
5. The n and r are the "public key" - they are available to anyone and are used to send encrypted messages to the holder of this key. p, q, and s are secret and are used to decrypt messages sent to the holder of this key.

The sender of a message gets the two parts of the public key of the recipient and then does the following:

1. Converts the message to a string of digits.
2. Breaks the message up into uniformly sized blocks of digits.
3. If M is the integer form of the block of digits, then M must be relatively prime to n (otherwise the code can easily be broken). In practice, this should never be a problem - p and q should both be larger than any possible M hence n will automatically be relatively prime to n.
4. For each block M, computes and sends R = M^rmod n.

The receiver of the message receives the sequence of R's and for each, calculates R^smod n and then converts the resulting string of digits back to characters.

Given this description of the algorithm, we see that the attributes for the Coder class are the integers p, q, r, m, and s. The class needs the following public methods:

• A constructor with three parameters - two primes p and q and an integer r. The constructor then must compute m, make sure r is relatively prime to m, and compute s. The constructor should also make sure p and q are prime.
• A method that computes and returns n (one part of the public key)
• An accessor for r (another part of the public key)
• An encode method that takes a String as a parameter (the message to be encoded) and the public keys r and n of the recipient of the message. Encode then encodes the message and returns a string representing the encoding (this is called the ciphertext). This method should be static. (Why?)
• A decode method that takes a String as a parameter (the ciphertext) and returns the decoded message. This method is an instance method. (Why?)

• A method to find the least common multiple of two integers. The method needs two integer parameters. It should return the least common multiple of the two. The least common multiple of two integers a and b is the product ab divided by the greatest common divisor of the two. There is a method for greatest common divisor in the Rational class in the text.
• A method to compute the s. (This will be given to you - the algorithm is an extended version of Euclid's algorithm for finding the greatest common divisor. Click here for the method.)
• A method to test for primality. This method should take a single integer parameter and return a boolean indicating whether or not the integer is prime. Remember that prime means divisible by only one and itself. This can be implemented as a simple loop - to see if an integer a is prime you can divide by each integer from 2 up until the square root of a. If you ever get a zero remainder the number is not prime; otherwise it is.
• The encode method should use several helper methods. So the numbers don't get too big we will break the message up into blocks of just 2 characters each. Basically the encode method needs to do the following steps (and it should use methods to do some of the individual steps): For each two character block,
  • Convert the two character block to a number (say M). To do this use the getNumericValue method of the Character class. For example the character block hi would get the value 1718 (the numeric value of h is 17 and i is 18). Note that getNumericValue does not distinguish between upper and lower case - both h and H have numeric value 17. Use 36 for the value of the space character rather than the value returned by getNumericValue (it returns a negative number).
  • Compute R = M^rmod (n).
  • Concatenate R to a string representing the encoded message - put a space between the number for each block.
• The decode method should also use several helper methods. It needs to use a StringTokenizer to break the encrypted message (usually called the ciphertext up into the encodings (the R's) for each block. Each token returned by the StringTokenizer will be the code for one block. Each token however is returned as a String. The PigLatinTranslator starting on page 240 of the book uses a StringTokenizer. The outline of what you do is below (most of the steps should be handled by a support method rather than done directly in this method):

      public String decode (String ciphertext)
      {
         String message = "";
         StringTokenizer tokenizer = new StringTokenizer (ciphertext);
         String token;
  
         while (tokenizer.hasMoreTokens())
         {
            token = tokenizer.nextToken();
            
            // convert the token to an integer R
  
            // compute M = Rs mod n.
  
            // convert M back to a string of characters (this will be 1 or
            // two characters
  
            // concatenate the characters with the message
  
         }
  
         // return the message
  
      }
  

• Observe that both encoding and decoding requires calculating a power of a number modulo another number. You should have a single method that does this and call it from both encode and decode. That method would have the following signature:

         // compute bimod k
         private int power (int b, int i, int k)
  
  

  To avoid overflow and to avoid possible loss of precision power should use a loop that finds the power iteratively, and at each step divides by k and takes the remainder. Because Math.pow converts to double (and returns a double) it should not be used -- loss of precision can result from large integers.

The main program should use two Coder objects - one for Alice and one for Bob (or you can use your own names for the two "people" sending encrypted messages back and forth -- it is standard practice in cryptography books to use Alice and Bob). Read in the p, q, and r for each then instantiate the object. Have a loop that lets the two send encrypted messages back and forth. So if Alice wants to send a message to Bob, your program needs to get the message, then get Bob's public keys, then encrypt the message, display the encrypted message, then Bob's coder will decode the message. The decoded message should be displayed. Use dialog boxes for input and output.

As usual, use good programming techniques. You should use good variable names, constants where appropriate, whitespace, and correct indentation and alignment of statements (emacs will do this for you if you let it!). Documentation must include a header with the file name, your name, the date, and a clear, complete description of what the program does. Each method must have a brief description of what it does. Both the Coder class and the class containing the main program must be documented.

Hand In

Academic Integrity Reminder!!! Programming assignments are to be your own work. You may get help on the specifics of the assignment from no one except the instructor. You may not show your program to anyone or look at anyone else's program code or share ideas with anyone about how to write the program.