Skip to main content
Engineering LibreTexts

14.4: Exercises

  • Page ID
    86470
  • \( \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 \(14.1\)

    Let \(p\) be an odd prime, as usual. Recall that \(\mathbb{Q R}_{p}^{*}\) is the set of quadratic residues mod \(p\) - that is, \(\mathbb{Q R}_{p}^{*}=\left\{x \in \mathbb{Z}_{p}^{*} \mid \exists y: x \equiv{ }_{p} y^{2}\right\}\). Show that if \(g\) is a primitive root of \(\mathbb{Z}_{p}^{*}\) then \(\left\langle g^{2}\right\rangle=\mathbb{Q} \mathbb{R}_{p}^{*}\)

    Note: This means that \(g^{a} \in \mathbb{Q R}_{p}^{*}\) if and only if \(a\) is even \(-\) and in particular, the choice of generator \(g\) doesn’t matter.

    Exercise \(14.2\)

    Suppose \(N=p q\) where \(p\) and \(q\) are distinct primes. Show that \(\left|\mathbb{Q} \mathbb{R}_{N}^{*}\right|=\left|\mathbb{Q} \mathbb{R}_{p}^{*}\right| \cdot\left|\mathbb{Q} \mathbb{R}_{q}^{*}\right|\).

    Hint:

    Exercise \(14.3\)

    Suppose you are given \(X \in\langle g\rangle\). You are allowed to choose any \(X^{\prime} \neq X\) and learn the discrete log of \(X^{\prime}\) (with respect to base \(g\) ). Show that you can use this ability to learn the discrete \(\log\) of \(X\)

    Exercise \(14.4\)

    Let \(\langle g\rangle\) be a cyclic group with \(n\) elements and generator \(g\). Show that for all integers \(a\), it is true that \(g^{a}=g^{a \% n}\).

    Note: As a result, \(\langle g\rangle\) is isomorphic to the additive group \(\mathbb{Z}_{n}\).

    Exercise \(14.5\)

    Let \(g\) be a primitive root of \(\mathbb{Z}_{n}^{*}\). Recall that \(\mathbb{Z}_{n}^{*}\) has \(\phi(n)\) elements. Show that \(g^{a}\) is a primitive root of \(\mathbb{Z}_{n}^{*}\) if and only if \(\operatorname{gcd}(a, \phi(n))=1\)

    Note: It follows that, for every \(n\), there are either 0 or \(\phi(\phi(n))\) primitive roots mod \(n\).

    Exercise \(14.6\)

    Let \(\langle g\rangle\) be a cyclic group with \(n\) elements. Show that for all \(x, y \in\langle g\rangle\), it is true that \(x^{n}=y^{n} .\)

    \(\dot{\varepsilon}_{u}\left(v_{v} b\right)\) SI ๆеч \(M \cdot v \mathrm{~}\)

    Hint:

    Exercise \(14.7\)

    (a) Prove the following variant of Lemma 4.10: Suppose you fix a value \(x \in \mathbb{Z}_{N}\). Then when sampling \(q=\sqrt{2 N}\) values \(r_{1}, \ldots, r_{q}\) uniformly from \(\mathbb{Z}_{N}\), with probability at least \(0.6\) there exist \(i \neq j\) with \(r_{i} \equiv_{N} r_{j}+x\).

    (b) Let \(g\) be a primitive root of \(\mathbb{Z}_{p}^{*}\) (for some prime \(p\) ). Consider the problem of computing the discrete \(\log\) of \(X \in \mathbb{Z}_{p}^{*}\) with respect to \(g-\) that is, finding \(x\) such that \(X \equiv_{p} g^{x}\). Argue that if one can find integers \(r\) and \(s\) such that \(g^{r} \equiv_{p} X \cdot g^{s}\) then one can compute the discrete \(\log\) of \(X\).

    (c) Combine the above two observations to describe a \(O(\sqrt{p})\)-time algorithm for the discrete logarithm problem in \(\mathbb{Z}_{p}^{*}\).

    Exercise \(14.8\)

    In an execution of DHKA, the eavesdropper observes the following values:

    \[\begin{array}{ll} p=461733370363 & A=114088419126 \\ g=2 & B=276312808197 \end{array}\]

    What will be Alice & Bob’s shared key?

    Exercise \(14.9\)

    Explain what is wrong in the following argument:

    In Diffie-Hellman key agreement, Alice sends \(A=g^{a}\) and Bob sends \(B=g^{b}\). Their shared key is \(g^{a b}\). To break the scheme, the eavesdropper can simply compute \(A \cdot B=\left(g^{a}\right)\left(g^{b}\right)=g^{a b}\).

    Exercise \(14.10\)

    Let \(\mathbb{G}\) be a cyclic group with \(n\) elements and generator \(g\). Consider the following algorithm:

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

    Let \(D H=\left\{\left(g^{a}, g^{b}, g^{a b}\right) \in \mathbb{G}^{3} \mid a, b, \in \mathbb{Z}_{n}\right\}\)

    (a) Suppose \((A, B, C) \in D H\). Show that the output distribution of \(\operatorname{RAND}(A, B, C)\) is the uniform distribution over \(D H\)

    (b) Suppose \((A, B, C) \notin D H\). Show that the output distribution of \(\operatorname{RAND}(A, B, C)\) is the uniform distribution over \(\mathbb{G}^{3}\).

    \(\star\) (c) Consider the problem of determining whether a given triple \((A, B, C)\) is in the set \(D H\). Suppose you have an algorithm \(\mathcal{A}\) that solves this problem on average slightly better than chance. That is: \[\begin{aligned} &\operatorname{Pr}[\mathcal{A}(A, B, C)=1]>0.51 \text { when }(A, B, C) \text { chosen uniformly in } D H \\ &\operatorname{Pr}[\mathcal{A}(A, B, C)=0]>0.51 \text { when }(A, B, C) \text { chosen uniformly in } \mathbb{G}^{3} \end{aligned}\] The algorithm \(\mathcal{A}\) does not seem very useful if you have a particular triple \((A, B, C)\) and you really want to know whether it is in \(D H\). You might have one of the triples for which \(\mathcal{A}\) gives the wrong answer, and there’s no real way to know.

    Show how to construct a randomized algorithm \(\mathcal{A}^{\prime}\) such that: for every \((A, B, C) \in \mathbb{G}^{3}\) : \[\operatorname{Pr}\left[\mathcal{A}^{\prime}(A, B, C)=[(A, B, C) \stackrel{?}{\in} D H]\right]>0.99\] Here the input \(A, B, C\) is fixed and the probability is over the internal randomness in \(\mathcal{A}^{\prime}\). So on every possible input, \(\mathcal{A}^{\prime}\) gives a very reliable answer.


    This page titled 14.4: 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?