## 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:
- 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.
- Pick a and compute b for encryption.
- Print out the private and the public key and the total from part
1.
- 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
The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.