Skip to main content
[ "article:topic", "showtoc:no", "license:ccbync", "authorname:mrosulek" ]
Engineering LibreTexts

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 ga ≡n 1 and gb ≡n 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.

    Figure13-19.jpg

    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:

    Figure13-20.jpg

    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 me. To decrypt, Alice first computes mp ≡p cd and mq ≡qcd, 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:

    Figure13-21.jpg

    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!

    Figure13-22.jpg

    13.11: True or false: if x2 ≡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 qHint: 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

    Figure13-23.jpg

    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 x2 ≡N 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.

    Figure13-24.jpg

    Figure13-25.jpg

    Figure13-26.jpg

    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 t2 − 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.

    Figure13-27.jpg


    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.