13.6: Exercises

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 ≡_n 1, then g^gcd(a,b) ≡_n 1.

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 kth Fibonacci number, using the indexing convention F₀ = 1; F₁ = 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.⁶

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^d and m_q ≡_qc^d, then uses the CRT conversion to obtain m ∈ ℤ_N, just as expected. But suppose Alice is using faulty hardware, so that she computes a wrong value for m_q. The rest of the computation happens correctly, and Alice computes the (wrong) result 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² ≡_N 1 then x ∈ ℤ^∗_N. Prove or give a counterexample.

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² ≡_N y², 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 √Nsuch that t² − 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 tand 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.

---

⁶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² N) — quadratic in the number of bits needed to write the input.