Programming Language :

C on Unix OR

JAVA under Windows NT (write an applet so that it works on web pages)

Libraries :

The GNU Multiple Precision Arithmetic Library Edition 2.0.2

JDK1.1.6 : http://java.sun.com/products/jdk/1.1/docs/api/java.math.BigInteger.html

Input/Output :
This program takes key length as an input and outputs two prime numbers.

 
Description of the function performed by the program(s), including any specific references to standard :
Creating a pair of corresponding public and private keys for the RSA cryptosystem requires generation of two very large prime numbers. The minimum length of these primes used in today's RSA implementations is 256 bits, which corresponds to numbers in the range 10^75. Due to the fast progress in factorization algorithms used to break RSA, it is currently recommended to use 384, 512, or even 1024-bit primes. This program utilizes Rabin-Miller algorithm to produce two prime numbers of length k bits where k is specified by the user. In addition, we compare it with Lucas- Lehmer Test.

Rabin-Milller Test

Choose a random number, p, to test. Calculate b, where b is the number of times 2 divides p-1. Then calculate m, such that p = 1 + 2^bm

1. Choose a random number, a, such that a is less than p.

2. Set j = 0, and set z = a^m mod p.

3. If  z = 1, or if z = p – 1, then p passes the test and may be prime.

4. If j > 0 and z = 1, then p is not prime.

5. Set j = j +1. If j < b and z = z² mod p-1  != p-1 go back to step 4. If z = p – 1, then p passes the test and may be prime.

6. If j = b and z = p –1, then p is not prime.
 

Testing functionality and Performance :
Functionality and performance is defined by "speed" of the algorithm and probability of error. We calculate probability of error for algorithm implemented in function and measure the time to produce large prime numbers of length k bits.

Plan of experiements to be performed using the program(s) :
find large prime numbers of length k bits, and measure the performance(time). Try to optimize the program

Following will be also discussed on paper.

• Proofs that these algorithms work
• Number of iterations required
• Generating a Strong Primes/Why they are necessary
• Proving that a number was generated at random
• Comparison of speed at various algorithms for various key sizes

March 25 : Initial algorithm implementations. Initial proofs why these algorithms work

April 8 : Refinement.(for any bugs) Measure performance. Generating Strong Primes/Background

April 22 : Further refinement(try to make the code more efficient), Proving that a number was generated at random.

A list of possible areas, where the specification can change depending on the progress of the project.

• Grantham-Frobenius Method can be done in addition to two algorithms if time allows.
• C with GNU Multiple Precision Arithmetic Library 2.0.2 will be used as first approach; however, if time allows, attempt to write it in JAVA will be explored.