CS547A Homework set #5

Due Monday December 3, 2001 in class at 13:00

Exercises (from Stinson’s book)

• 4.5 •

• 7.4 •

• 9.7 •

Other Exercises

Jacobi symbol and least significant bit

Let n=p*q, the product of two primes, and let n-1 be an element of QNRn[+1] i.e.

the Jacobi symbol J(n-1/n) = +1. Let e be an RSA public exponent mod n.

• Give specific conditions on p and q to have the Jacobi symbol J(n-1/n) = +1.

Let M be a random variable describing the random choice of a plaintext 0<M<n.

• Show that H[ lsbn(M) | J(Me/n) ] = H[ lsbn(M) ].

• Use MAPLE™ to show that this may be false if the Jacobi symbol J(n-1/n) = -1.

Smaller RSA decryption exponent

Define, for n=p*q, the function £(n)=Ø(n)/gcd(p-1,q-1). An extension of Euler's theorem is that for all x, 0<x<n, such that gcd(x,n)=1, we have x £(n) = 1 (mod n).

  1. Let (n,e) be an RSA public key and d be the corresponding RSA private decryption key. Show that for at least half the e's, there exists a d', 0<d'<£(n)<d, such that d' may be used to decrypt instead of d.

  2. Discuss the pros and cons of having gcd(p-1,q-1) be fairly large with respect to n, in terms of efficiency and security.

  3. Is the result of • 4.5 • still valid using d’ instead of d ?

  4. Using MAPLE™ find two random 100-digit primes p and q with the property that |gcd(p-1,q-1)|>75 digits.

  5. Find exponents e,d,d’ such that |e|=|d|=|n|=200 digits whereas |d’|<125 digits. Verify on 10 random examples that (me)d’ mod n = m.

Goldwasser-Micali

Let n=p*q, the product of two primes, and let y be an element of QNRn[+1]. Remember that the Goldwasser-Micali cryptosystem with public parameters (n,y) encrypts a zero bit by [a random square] x2 mod n and a one bit by [a random pseudo-square] x2y mod n.

Let GM(m1),GM(m2) be the Goldwasser-Micali encryption of messages m1 and m2 as computed and sent by Bob to Alice. Suppose Bob applied his personal signature to the encryption of each bit.

Imagine the government witnessed Bob's transmission of both messages to Alice and they wish to have some minor information about the messages as follows.

  1. Show how Bob can prove that both GM(m1),GM(m2) were encryptions of the same message m1=m2 without disclosing anything at all about it.

  2. Show how Bob can prove that GM(m1),GM(m2) were encryptions of messages m1 and m2 that differed in an even (including zero) or odd number of positions, without disclosing anything else about them.

  3. Assume m1,m2 have even length, |m1|=|m2|=2k. Show how Bob can prove that GM(m1),GM(m2) were encryptions of different messages m1<>m2 by disclosing nothing except for the fact that they differed somewhere among all but one of the positions. (Bob can put aside one encrypted bit at a fixed position of GM(m1) and GM(m2), and then prove that the remaining truncated messages are different without disclosing anything about them except for the fact that they differ). Explain why we need messages of even length 2k.

  4. How much uncertainty is left about m1,m2 when only learning that they differ ? How much uncertainty is left about m1,m2 when learning that they differ by the method suggested in (c.) ?

(in both cases assume that the a priori uncertainty was maximum.)