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 **QNR _{n}[+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[ lsb _{n}(M) | J(M^{e}/n) ] = H[ lsb_{n}(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)**.

- 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**. - 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. - Is the result of
**• 4.5 •**still valid using**d’**instead of**d**? - Using MAPLE™ find two random
**100**-digit primes**p**and**q**with the property that**|gcd(p-1,q-1)|>75**digits. - Find exponents
**e,d,d’**such that**|e|=|d|=|n|=200**digits whereas**|d’|<125**digits. Verify on**10**random examples that**(m**.^{e})^{d’}mod n = m

Goldwasser-Micali

Let **n=p*q**, the product of two primes, and let **y** be an element of **QNR _{n}[+1].** Remember that the

Let **GM(m _{1}),GM(m_{2})** be the

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.

- Show how Bob can prove that both
**GM(m**were encryptions of the same message_{1}),GM(m_{2})**m**without disclosing anything at all about it._{1}=m_{2} - Show how Bob can prove that
**GM(m**were encryptions of messages_{1}),GM(m_{2})**m**and_{1}**m**that differed in an_{2}**even**(including zero) or**odd**number of positions, without disclosing anything else about them. - Assume
**m**have even length,_{1},m_{2}**|m**. Show how Bob can prove that_{1}|=|m_{2}|=2k**GM(m**were encryptions of different messages_{1}),GM(m_{2})**m**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_{1}<>m_{2}**GM(m**and_{1})**GM(m**, 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_{2})**2k**. - How much uncertainty is left about
**m**when only learning that they differ ? How much uncertainty is left about_{1},m_{2}**m**when learning that they differ by the method suggested in (c.) ?_{1},m_{2}

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