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

Exercises and Projects

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

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

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

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

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

4. You are an RSA cryptosystem user with public key n=756851 and e=5. Suppose that a number in tex2html_wrap_inline948 is always written as a 6 digit number (padding zeros in front if necessary). Then the numbers in tex2html_wrap_inline948 represent a triple of letters under the correspondence tex2html_wrap_inline1884, tex2html_wrap_inline1886, tex2html_wrap_inline856, tex2html_wrap_inline1890; e.g., tex2html_wrap_inline1892. 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 tex2html_wrap_inline1906 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 tex2html_wrap_inline948 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 tex2html_wrap_inline1920 of tex2html_wrap_inline948 such that (a) tex2html_wrap_inline1924 for all different tex2html_wrap_inline1926; (b) for any tex2html_wrap_inline970, it is easy to decide whether tex2html_wrap_inline1930; and (c) tex2html_wrap_inline1920 should be large, say of size O(n).

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

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

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

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

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

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