# Exercises

- Page ID
- 7402

13.1: Prove by induction the correctness of the EXTGCD algorithm. That is, whenever (*d,a,b*) = EXTGCD(*x,y*), we have gcd(*x,y*) = *d* = *ax* + *by*. You may use the fact that the original Euclidean algorithm correctly computes the GCD.

13.2: Prove that if *g ^{a}* ≡

_{n}1 and

*g*≡

^{b}*1, then*

_{n}*g*

^{gcd(a,b)}≡

*1.*

_{n}

13.3: Prove that gcd(2^{a} − 1,2^{b} − 1) = 2^{gcd(a,b)} − 1.

13.4: Prove that *x ^{a} % n* =

*x*

^{a%ϕ(n)}

*% n*. In other words, when working modulo

*n*, you can reduce exponents modulo

*ϕ*(

*n*).

13.5: In this problem we determine the efficiency of Euclid’s GCD algorithm. Since its input is a pair of numbers (*x,y*), let’s call *x* + *y* the size of the input. Let *F _{k}* denote the

*k*th Fibonacci number, using the indexing convention

*F*

_{0}= 1;

*F*

_{1}= 2. Prove that (

*F*

_{k},

*F*

_{k}−1) is the smallest-

*size*input on which Euclid’s algorithm makes

*k*recursive calls.

*Hint:*Use induction on

*k*.

Note that the *size* of input (*F _{k},F*

_{k−1}) is

*F*

_{k+1}, and recall that

*F*

_{k+1}≈

*ϕ*

^{k+1}, where

*ϕ*≈ 1.618 . . . is the golden ratio. Thus, for any inputs of size

*N*∈ [

*F*,

_{k}*F*

_{k + 1}), Euclid’s algorithm will make less than

*k*⩽ log

_{ϕ}

*N*recursive calls. In other words, the worst-case number of recursive calls made by Euclid’s algorithm on an input of size

*N*is

*O*(log

*N*), which is linear in the number of bits needed to write such an input.

^{6}

13.6: Consider the following **symmetric-key** encryption scheme with plaintext space ? = {0,1}^{λ}. To encrypt a message *m*, we “pad” *m* into a prime number by appending a zero and then random non-zero bytes. We then multiply by the secret key. To decrypt, we divide off the key and then strip away the “padding.”

The idea is that decrypting a ciphertext without knowledge of the secret key requires factoring the product of two large primes, which is a hard problem.

Show an attack breaking CPA-security of the scheme. That is, describe a distinguisher and compute its bias. *Hint:* ask for any two ciphertexts.

13.7: Explain why the RSA encryption exponent *e* must always be an odd number.

13.8: The Chinese Remainder Theorem states that there is always a solution for *x* in the following system of equations, when gcd(*r,s*) = 1:

Give an example *u*, ?, *r, s*, with gcd(*r,s*) ≠ 1 for which the equations have no solution. Explain why there is no solution.

13.9: Bob chooses an RSA plaintext *m* ∈ ℤ_{N} and encrypts it under Alice’s public key as *c* ≡_{N}*m ^{e}*. To decrypt, Alice first computes

*m*≡

_{p}

_{p}*c*and

^{d}*m*≡

_{q}

_{q}*c*, then uses the CRT conversion to obtain

^{d}*m*∈ ℤ

*, just as expected. But suppose Alice is using faulty hardware, so that she computes a*

_{N}**wrong value**for

*m*. The rest of the computation happens correctly, and Alice computes the (wrong) result

_{q}*mˆ*. Show that, no matter what

*m*is, and no matter what Alice’s computational error was, Bob can factor

*N*if he learns

*mˆ*.

*Hint:* Bob knows *m* and *mˆ* satisfying the following:

13.10: (a). Show that given an RSA modulus *N* and *ϕ*(*N*), it is possible to factor *N* easily.

*Hint:* you have two equations (involving *ϕ*(*N*) and *N*) and two unknowns (*p* and *q*).

(b). Write a pari function that takes as input an RSA modulus *N* and *ϕ*(*N*) and factors *N*. Use it to factor the following 2048-bit RSA modulus. *Note:*take care that there are no precision issues in how you solve the problem; double-check your factorization!

13.11: True or false: if *x*^{2} ≡* _{N}* 1 then

*x*∈ ℤ

^{∗}

*. Prove or give a counterexample.*

_{N}13.12: Discuss the computational difficulty of the following problem:

*Given an integer N, find an element of* ℤ* _{N}* \ ℤ*

*.*

_{N}

If you can, relate its difficulty to that of other problems we’ve discussed (factoring *N* or inverting RSA).

13.13: (a). Show that it is possible to efficiently compute all four square roots of unity modulo *pq*, given *p* and *q*. *Hint:* CRT!

(b). Implement a pari function that takes distinct primes *p* and *q* as input and returns the four square roots of unity modulo *pq*. Use it to compute the four square roots of unity modulo

13.14: Show that, conditioned on *w* ∈ ℤ^{∗}* _{N}*, the SqrtUnity subroutine outputs a square root of unity chosen uniformly at random from the 4 possible square roots of unity.

*Hint:*use the Chinese Remainder Theorem.

13.15: Suppose *N* is an RSA modulus, and *x*^{2} ≡_{N}*y*^{2}, but *x* ≢≡*N* ± *y*. Show that *N*. can be efficiently factored if such a pair *x* and *y* are known.

13.16: Why are ± 1 the only square roots of unity modulo *p*, when *p* is an odd prime?

13.17: When *N* is an RSA modulus, why is squaring modulo *N* a 4-to-1 function, but raising to the *e*^{th} power modulo *N* is 1-to-1?

13.18: Implement a pari function that efficiently factors an RSA modulus *N*, given only *N, e,* and *d*. Use your function to factor the following 2048-bit RSA modulus. *Note:* pari function valuation(n,p) returns the largest number *d* such that *p ^{d}* |

*n*.

13.19: In this problem we’ll see that it’s bad to choose RSA prime factors *p* and *q* too close together.

(a). Let *s* = (*p* − *q*)/2 and *t* = (*p* + *q*)/2. Then *t* is an integer greater than √*N*such that *t*^{2} − *N* is a perfect square. When *p* and *q* are close, *t* is not much larger than √*N*, so by testing successive integers, it is possible to find *t*and *s*, and hence *p* and *q*.. Describe the details of this attack and how it works.

(b). Implement a pari function that factors RSA moduli using this approach. Use it to factor the following 2048-bit number (whose two prime factors are guaranteed to be close enough for the factoring approach to work in a reasonable amount of time, but far enough apart that you can’t do the trial-and-error part by hand). What qualifies as “close prime factors” in this problem? How close was *t* to √*N*?

*Hint:* pari has an issquare function. Also, be sure to do exact square roots over the integers, not the reals.

^{6}A more involved calculation that incorporates the cost of each division (modulus) operation shows the worst-case overall efficiency of the algorithm to be *O*(log^{2} *N*) — quadratic in the number of bits needed to write the input.