COSC COSC5910.03 Software Foundations

Instructor: J. Liu

Assignment 1. Due Tuesday February 4 in class.

This problem deals with the secure transfer of data over the internet. It involves the encryption of input data (to convert it into some unrecognizable form) and its decryption (to convert the unrecognizable message back to its original form). The method we consider here is called the RSA cryptosystem, named after the initials of its authors from MIT in 1978 (Rivest, Shamir, Adleman).

RSA is a public-key system: one key is needed for encryption and a different but related key is used for decryption. The scheme is based on the observation that it is very difficult (if not impossible) to determine the decryption key even if you know the algorithm and the encryption key.

There are three integers associated with the scheme:

    u: the public exponent
    v: the private exponent
    m: the modulo integer
The public key is the pair (u,m); and the private key is (v,m). For an integer x (less than m), the encrypted number y is given by:
    y = (x^u) % m,
where x^u is x raised to the power of u. On the other hand, the decryption scheme is given by:
    (y^v) % m,
We will get back the original value x provided the three values u, v, m satisfy some conditions.

For example, u = 37, v = 97, and m = 3713 can be used to encrypt and decrypt values of less than 3713. Click here for some examples of using these set of keys.

In practice, the values of u, v, m are very large integers so that overflow will occur even if we use "long" integers. Java 2 has a class called "BigInteger, designed for arbitrary-precision integers.

  1. The algorithm to generate the set of RSA key values uses prime numbers and modulo arithmetic. You can find many web sites that discuss the algorithm. Click here for a description. Design and write a Java class called RsaKey with a method
              public static int privateExponent(int prime1, int prime2, int exponent)
    
    that first ensures that the two integers prime1, prime2 are prime numbers and that exponent and (prime1-1)*(prime2-1) are relatively prime. If these conditions are met, it will compute and return the private exponent for the RSA system using the product prime1*prime2 as the divisor and exponent as the public exponent value. If the conditions are not met, a zero value will be returned.

    Here, you need to compute the multiplicative modulo inverse of an integer; that is, for a pair of relatively prime numbers a and m, find b such that

             (a * b) % m = 1.
    
    You can use a simple brute force method by finding the first integer starting from 1 that satisfies this condition. (A more efficient method uses the extended Euclidean algorithm.)

    Write another method in the RsaKey class, called

              public static int crackRSA(int divisor, int exponent)
    
    that returns the private exponent value for the public RSA key values of divisor and exponent. Here you can assume that (divisor,exponent) is a valid set of RSA keys.

    Note that we can implement crackRSA here because the divisor is assumed to be of type int and in practice, it should be a BigInteger. Also, for this part of the assignment, you are not allowed to use the BigInteger class. For the remaining two parts, BigIntegers should be used.

  2. Design and implement a Java code for the RSA method. Use the "BigInteger" class (consult the Java API for a detailed description of the class and its methods), to implement the encryption and decryption schemes. You may use any of the methods in the BigInteger class except the modPow(..) method.

    You should use RSA key values determined in the first part to test your code. Choose your values so that the divisor has 5 digits (with leading nonzero digit).

    Your output should include the value of the input data, say x, the value of x^u, and the encrypted value y. Then, you should decrypt the y value and output the value of y^v and the decrypted value (which should be x).

  3. A file contains a number of integers, intercepted from a transmission. It is known that the first integer is the divisor and the second integer is the public exponent value. The remaining numbers are encrypted messages.

    Write a Java program to break the encoding by determining the private exponent key and then decrypt all the integers in the file (except the first two). You only need to produce the original messages (no intermediate results as in the previous part).


Last Updated: 01/10/2003