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 integerThe 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.
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.
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).
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