CSci 4509 Cryptographic Protocols -- Problem set 4.

Due Thursday, April 21

Problem 1

Problem 5.3 p. 219 in Stinson.

Problem 2

Problem 5.7 p. 219 in Stinson.

Problem 3: RSA encryption

Part 1. Write a program to generate an RSA key pair with two 4-digit primes (in decimal representation) and to perform encryption/decryption. Specifically your program should:
  1. Keep choosing 4-digit random numbers and test if the chosen numbers are prime until two prime ones are found. You can use the straightforward algorithm (checking all possible divisors up to the square root) to check if the number is prime. Keep total of the number of random numbers that you tried.
  2. Pick a and compute b for encryption.
  3. Print out the private and the public key and the total from part 1.
  4. Pick three numbers at random, encrypt them using your system, and decrypt them to make sure that you get the same number back.
Write down the results. Submit your program electronically so that I can test it.

Note that the extended euclidean algorithm for computing multiplicative inverses is implemented in the code for Affine Cipher

Problem 4: RSA digital signatures

Prove that in the RSA cryptosystem eK(dK(y)) = y, where eK is the encryption function, and dK is the decryption function. Note that this fact is the basis of RSA digital signatures.

Problem 5: estimating difficulty of breaking RSA by pre-generating key pairs

Consider the following approach for breaking RSA encryption: suppose we generate a large number of public/private key pairs and create a database of all possible pairs and their corresponding products.

Prime Number Theorem (see p. 172 of Stinson) says that there are approximately N/ln N prime numbers between 1 and N. Give an estimate of the number of entries in the database to guarantee that a given n is there with the probability of 1/2. Assuming that there are 1,000,000,000 RSA users, how many entries do we need to store in the database to guarantee that at least one of the key pairs is in the database with the probability of 1/2?

Is this a feasible attack on RSA with 512-bit key? On RSA with 1024-bit key? Please explain, show all your computations. You may approximate your answer, a couple of orders of magnitude don't matter.

That's all
CSci 4509 homepage