Skip to main content
Engineering LibreTexts

13.6: Exercises

  • Page ID
    86465
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Exercise \(13.1\)

    Prove by induction the correctness of the EXTGCD algorithm. That is, whenever \(\operatorname{EXTGCD}(x, y)\) outputs \((d, a, b)\), we have \(\operatorname{gcd}(x, y)=d=a x+b y\). You may use the fact that the original Euclidean algorithm correctly computes the GCD.

    Exercise \(13.2\)

    Prove that if \(g^{a} \equiv_{n} 1\) and \(g^{b} \equiv_{n} 1\), then \(g^{\operatorname{gcd}(a, b)} \equiv_{n} 1\).

    Exercise \(13.3\)

    Prove that \(\operatorname{gcd}\left(2^{a}-1,2^{b}-1\right)=2^{\operatorname{gcd}(a, b)}-1\)

    Exercise \(13.4\)

    Prove that \(x^{a} \% n=x^{a \% \phi(n)} \% n\) for any \(x \in \mathbb{Z}_{n}^{*}\). In other words, when working modulo \(n\), you can reduce exponents modulo \(\phi(n)\)

    Exercise \(13.5\)

    How many fractions \(a / b\) in lowest terms are there, where \(0<a / b<1\) and \(b \leqslant n\) ? For \(n=5\) the answer is 9 since the relevant fractions are:

    \[\frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}\]

    Write a formula in terms of \(n\). What is the answer for \(n=100 ?\)

    Hint:

     

    Exercise \(13.6\)

    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 \(\left(F_{k}, F_{k-1}\right)\) is the smallest-size input on which Euclid’s algorithm makes \(k\) recursive calls.

    Hint:

     

    Note that the size of input \(\left(F_{k}, F_{k-1}\right)\) is \(F_{k+1}\), and recall that \(F_{k+1} \approx \phi^{k+1}\), where \(\phi \approx\) \(1.618 \ldots\) is the golden ratio. Thus, for any inputs of size \(N \in\left[F_{k}, F_{k+1}\right)\), Euclid’s algorithm will make less than \(k \leqslant \log _{\phi} 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. \({ }^{8}\)

    Exercise \(13.7\)

    Consider the following symmetric-key encryption scheme with plaintext space \(\mathcal{M}=\) \(\{0,1\}^{\lambda}\). To encrypt a message \(m\), we "pad" \(m\) into a prime number by appending a zero and then random non-zero bytes. We then mulitply 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.

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Show an attack breaking CPA-security of the scheme. That is, describe a distinguisher and compute its bias.

    Hint:

    Exercise \(13.8\)

    Explain why the RSA exponents \(e\) and \(d\) must always be odd numbers.

    Exercise \(13.9\)

    Why must \(p\) and \(q\) be distinct primes? Why is it a bad idea to choose \(p=q\) ?

    Exercise \(13.10\)

    A simple power analysis (SPA) attack is a physical attack on a computer, where the attacker monitors precisely how much electrical current the processor consumes while performing a cryptographic algorithm. In this exercise, we will consider an SPA attack against the MonExP algorithm shown in Section 13.2.

    The MODEXP algorithm consists mainly of squarings and multiplications. Suppose that by monitoring a computer it is easy to tell when the processor is running a squaring vs. a multiplication step (this is a very realistic assumption). This assumption is analogous to having access to the printed output of this modified algorithm:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Describe how the printed output of this algorithm lets the attacker completely learn the value \(e\). Remember that in RSA it is indeed the exponent that is secret, so this attack leads to key recovery for RSA.

    Hint:

    Exercise \(13.11\)

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

    \[x \equiv r u\]

    \[x \equiv{ }_{s} v\]

    Give an example \(u, v, r, s\), with \(\operatorname{gcd}(r, s) \neq 1\) for which the equations have no solution. Explain why there is no solution.

    Exercise \(13.12\)

    Prove Claims \(13.10\) and \(13.11 .\)

    Exercise \(13.13\)

    Consider a rectangular grid of points, with width \(w\) and height \(h\). Starting in the lowerleft of the grid, start walking diagonally northeast. When you fall off end the grid, wrap around to the opposite side (i.e., Pac-Man topology). Below is an example of the first few steps you take on a grid with \(w=3\) and \(h=5\):

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Show that if \(\operatorname{gcd}(w, h)=1\) then you will eventually visit every point in the grid.

    Hint:

    Exercise \(13.14\)

    Suppose \((u, v) \in \mathbb{Z}_{r} \times \mathbb{Z}_{s}\) is a CRT encoding of \(x \in \mathbb{Z}_{r s}\). Prove that \(x \in \mathbb{Z}_{r s}^{*}\) if and only if \(u \in \mathbb{Z}_{r}^{*}\) and \(v \in \mathbb{Z}_{s}^{*}\)

    Note: this problem implies that \(\phi(r s)=\phi(r) \phi(s)\) when \(\operatorname{gcd}(r, s)=1\). A special case of this identity is the familiar expression \(\phi(p q)=(p-1)(q-1)\) when \(p\) and \(q\) are distinct primes.

    Exercise \(13.15\)

    There is a bug (or at least an oversight) in the proof that \(x \mapsto x^{e} \% N\) and \(y \mapsto y^{d} \% N\) are inverses. We used the fact that \(x^{\phi(N)} \equiv_{N} 1\), but this is only necessarily true for \(x \in \mathbb{Z}_{N}^{*}\). Using the Chinese Remainder Theorem, show that the RSA function and its inverse are truly inverses, even when applied to \(x \notin \mathbb{Z}_{N}^{*}\)

    Exercise \(13.16\)

    We are supposed to choose RSA exponents \(e\) and \(d\) such that \(e d \equiv_{\phi(N)} 1\). Let \(N=p q\) and define the value \(L=\operatorname{lcm}(p-1, q-1)\). Suppose we choose \(e\) and \(d\) such that \(e d \equiv_{L} 1\). Show that RSA still works for this choice of \(e\) and \(d-\) in other words, \(x \mapsto x^{e} \% N\) and \(y \mapsto y^{d} \% N\) are inverses.

    Hint:

    Exercise \(\star 13.17\)

    If \(y^{e} \equiv_{N} x\) then we call \(y\) an " \(e\)-th root" of \(x\). One way to think about RSA is that raising something to the \(d\) power is equivalent to computing an \(e\)-th root. Our assumption about RSA is that it’s hard to compute \(e\)-th roots given only public \(e\) and \(N\).

    In this problem, show that if you are given an \(a\)-th root of \(x\) and \(b\)-th root of the same \(x\), and \(\operatorname{gcd}(a, b)=1\), then you can easily compute an \(a b\)-th root of \(x\).

    More formally, given \(x, y, z\) and \(N\) where \(y^{a} \equiv_{N} x\) and \(z^{b} \equiv_{N} x\), show how to efficiently compute a value \(w\) such that \(w^{a b} \equiv_{N} x\)

    Compute \(w\) for the following values (after verifying that \(y\) is an \(a\)-th root and \(z\) is a \(b\)-th \(\operatorname{root}\) of \(x \bmod N)\)

    \[\begin{aligned} &N=318753895014839414391833197387495582828703628009180678460009 \\ &x=183418622076108277295248802695684859123490073011079896375192 \\ &a=56685394747281296805145649774065693442016512301628946051059 \\ &b=178205100585526989632998577959780764157496762062661723119813 \\ &y=185575838649944725271855413520846311652963277243867273346885 \\ &z=20697550065842164169278024507041536884260713996371572807344 \end{aligned}\]

    Hint:

    Exercise \(13.18\)

    Suppose Alice uses the CRT method to sign some message \(m\) in textbook RSA. In other words, she computes \(m^{d} \% p\), then \(m^{d} \% q\), and finally converts this CRT encoding back to \(\mathbb{Z}_{N}\). But suppose Alice is using faulty hardware (or Eve is bombarding her hardware with electromagnetic pulses), so that she computes the wrong value mod \(q\). The rest of the computation happens correctly, and Alice publishes \(m\) and the (incorrect) signature \(\sigma\).

    Show that, no matter what \(m\) is, and no matter what Alice’s computational error was, Eve can factor \(N\) (upon seeing \(m, \sigma\), and the public RSA information \(N\) and \(e\) ).

    Hint:

    Exercise \(13.19\)

    (a) Show that given an RSA modulus \(N\) and \(\phi(N)\), it is possible to factor \(N\) easily.

    Hint: 

    (b) Write a Sage function that takes as input an RSA modulus \(N\) and \(\phi(N)\) and outputs the prime factors of \(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!

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    Exercise \(13.20\)

    True or false: if \(x^{2} \equiv_{N} 1\) then \(x \in \mathbb{Z}_{N}^{*}\). Prove or give a counterexample.

    Exercise \(13.21\)

    Discuss the computational difficulty of the following problem:

    Given an integer \(N\), find a nonzero element of \(\mathbb{Z}_{N} \backslash \mathbb{Z}_{N}^{*}\)

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

    Exercise \(13.22\)

    (a) Show that it is possible to efficiently compute all four square roots of unity modulo \(p q\), given \(p\) and \(q\)

    Hint:

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

    \[1052954986442271985875778192663 \times 611174539744122090068393470777\]

    Exercise \(\star 13.23\)

    Show that, conditioned on \(w \in \mathbb{Z}_{N}^{*}\), the SqrtUnity subroutine outputs a square root of unity chosen uniformly at random from the 4 possible square roots of unity.

    Hint:

    Exercise \(13.24\)

    Suppose \(N\) is an RSA modulus, and \(x^{2} \equiv_{N} y^{2}\), but \(x \equiv_{N} \pm y\). Show that \(N\) can be efficiently factored if such a pair \(x\) and \(y\) are known.

    Exercise \(13.25\)

    Why are \(\pm 1\) the only square roots of unity modulo \(p\), when \(p\) is an odd prime?

    Exercise \(13.26\)

    When \(N\) is an RSA modulus, why is squaring modulo \(N\) a 4-to- 1 function, but raising to the \(e^{\text {th }}\) power modulo \(N\) is \(1-\) to- 1 ?

    Exercise \(13.27\)

    Implement a Sage 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.

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    Exercise \(13.28\)

    In this problem we’ll see that it’s bad to choose RSA prime factors \(p\) and \(q\) too close together.

    (a) Let \(N=p q\) be an RSA modulus. Show that if you know \(N\) and \(\delta=|p-q|\) then you can efficiently factor \(N\).

    (b) Alice generated the following RSA modulus \(N=p q\) and lets you know that \(|p-q|<\) 10000 . Factor \(N\):

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    Exercise \(13.29\)

    Here is a slightly better method to factor RSA moduli whose factors are too close together. As before, let \(N=p q\).

    (a) Define \(t=(p+q) / 2\). Note that when \(p\) and \(q\) are close, \(t\) is not much larger than \(\sqrt{N}\). Show that:

    • \(t^{2}-N\) is a perfect square.
    • Given \(t\), it is possible to efficiently factor \(N\).

    Hint:

    (b) Write a Sage function that factors RSA moduli whose prime factors are close. Use it to factor the following 2048-bit number. How close were the factors (how large was \(|p-q|)?\)

    Hint:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    \({ }^{8} \mathrm{~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\left(\log ^{2} N\right)-\) quadratic in the number of bits needed to write the input.


    This page titled 13.6: Exercises is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .

    • Was this article helpful?