Next: References Up: Mathematical Models in Public-Key Previous: Digital Signatures

# Exercises and Projects

1. Develop an algorithm for computing using the square-and-multiply method indicated in Example 9.1. Implement your algorithm and test it for n=12345; ; and e=0,111, 12344, 54321.

2. Let and let e=5. Given that 863 and 877 are primes, find and compute d such that .

3. The following problems relate to the discussion of the RSA system.

a.
Given n=pq =591037 and , determine p and q by first determining a quadratic equation that p satisfies and then solving it using the quadratic formula.

b.
Let M be a given multiple of . Write where m is odd. Prove that for random , the probability that is a proper factor of n for some is at least 1/2. As a consequence, show that n can be factored efficiently when a multiple of is given.

4. You are an RSA cryptosystem user with public key n=756851 and e=5. Suppose that a number in is always written as a 6 digit number (padding zeros in front if necessary). Then the numbers in represent a triple of letters under the correspondence , , , ; e.g., . Your private key is the number d computed in Exercise 9.2. Decrypt the following ciphertext:

5. Suppose that p is a prime congruent to 3 modulo 4 and c is a quadratic residue modulo p. Prove that is a square root of c modulo p.

6. Suppose Bob is a Rabin cryptosystem user with public key n=5609 and private key (p,q)=(71,79). With each number in representing two letters as in Exercise 9.4, decrypt the following ciphertext:

7. Investigate how to choose a convenient plaintext space for Rabin's cryptosystem. That is, for n=pq, find a subset of such that (a) for all different ; (b) for any , it is easy to decide whether ; and (c) should be large, say of size O(n).

8. Decrypt the following ElGamal ciphertexts. The parameters are p=3119, , , and d=799. Each number in represents two letters as in Exercise 9.4.

9. Let p=877 and . Alice uses the ElGamal signature scheme, and her public key is .

a.
Verify that (137,217) is a valid signature of Alice for the message m=710.
b.
Suppose your secret key is a=133. Sign the message m=606.

10. Suppose that Bob uses the DSA with q=103, , , a=75, and . Determine Bob's signature on the message x=1001 using the random value k= 49, and verify the resulting signature.

Next: References Up: Mathematical Models in Public-Key Previous: Digital Signatures

Shuhong Gao
Sun Oct 17 11:04:53 EDT 1999