Cryptology Assignment 3

Due 10:15 Wednesday, April 29, 1998

Write a program which chooses a public-private key pair for the quadratic residuosity implementation of probabilistic encryption, encrypts a message using the public key, and decrypts it using the private key. These should be three separate functions in your program, so that it would be easy to separate them into three separate programs. Let the message be in ASCII, and store it in a file.

To choose a random prime, you can choose random numbers of the correct length and check them for primality. How long does it take to find two primes, each containing 512 bits? How long do your encryption and decryption functions take?

To deal with the long numbers necessary, I recommend that you use the language C with the Large Integer Package due to Paul Leyland and Arjen Lenstra. You can get it via anonymous ftp from

       ftp.ox.ac.uk:/pub/math/freelip/freelip 1.1.tar.gz.
After you gunzip freelip 1.1.tar.gz and tar -xvf freelip 1.1.tar,

there will be several files, including lipdoc.ps, which contains the documentation. You may use any of the modular arithmetic routines (note that squaring is faster than multiplication, so you should do that when appropriate) and the randomization routines (we won’t worry about their shortfalls in terms of cryptographic security), but do not use the primality testing or prime number generating routines other than to test the ones you write yourself. What confidence level did you choose for primality checking?

Please turn in your program and some output, including the public and private keys, plus the input and output for the encryption and decryption. You should write a brief report, explaining how your program should be used, discussing how long your program took to run, and discussing why using a pseudorandom number generator which is not cryptographically secure could be a problem. Your report should also mention any major functions you used, such as one to check primality or one to check quadratic residuosity. You should also send me your program and any extra files via e-mail (they can just be attachments in pine).