# 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 gan 1 and gbn 1, then ggcd(a,b)n 1.

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

13.4: Prove that xa % n = xa%ϕ(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 Fk denote the kth Fibonacci number, using the indexing convention F0 = 1; F1 = 2. Prove that (Fk,Fk−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 (Fk,Fk−1) is Fk+1, and recall that Fk+1ϕk+1, where ϕ ≈ 1.618 . . . is the golden ratio. Thus, for any inputs of size N ∈ [Fk,Fk + 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 cN me. To decrypt, Alice first computes mpp cd and mqqcd, 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 mq. The rest of the computation happens correctly, and Alice computes the (wrong) result . Show that, no matter what m is, and no matter what Alice’s computational error was, Bob can factor N if he learns .

Hint: Bob knows m and 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 x2N 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 ofN \ ℤ*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 x2N y2, 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 eth 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 pd | 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 = (pq)/2 and t = (p + q)/2. Then t is an integer greater than √Nsuch that t2N 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. 6A more involved calculation that incorporates the cost of each division (modulus) operation shows the worst-case overall efficiency of the algorithm to be O(log2 N) — quadratic in the number of bits needed to write the input.