# 14.4: Exercises

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

14.1: Let p be an odd prime, as usual. Recall that ℚℝp is the set of quadratic residues mod p— that is, ℚℝp = {x ∈ ℤp| ∃y : xp y2}. Show that if g is a primitive root of ℤp then ⟨g2⟩ = ℚℝp.

Note: This means that ga ∈ ℚℝp if and only if a is even — and in particular, the choice of generator g doesn’t matter.

14.2: Suppose N = pq where p and q are distinct primes. Show that |ℚℝN| = |ℚℝp| · |ℚℝq|.

Hint: Chinese remainder theorem.

14.3: Suppose you are given X ∈ ⟨g⟩. You are allowed to choose any X’X and learn the discrete log of X’. (with respect to base g). Show that you can use this ability to learn the discrete log of X.

14.4: Let ⟨g⟩ be a cyclic group with n elements and generator g. Show that for all integers a, it is true that ga = ga%n.

Note: As a result, ⟨g⟩ is isomorphic to the additive group ℤn.

14.5: Let g be a primitive root of ℤn. Recall that ℤn has ϕ(n) elements. Show that ga is a primitive root of ℤn if and only if gcd(a,ϕ(n)) = 1.

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

14.6: Let ⟨g⟩ be a cyclic group with n elements. Show that for all x,y ∈ ⟨g⟩, it is true that xn = yn.

Hint: every x ∈ ⟨g⟩ can be written as x = ga for some appropriate a. What is (ga)n?

14.7: (a). Prove the following variant of Lemma 4.8: Suppose you fix a value x ∈ ℤN. Then when sampling q = √2N values r1,. . . ,rq uniformly from ℤN, with probability at least 0.6 there exist ij with riN rj + x.

Hint: This is extremely similar to Exercise 4.7

(b). Let g be a primitive root of ℤp (for some prime p). Consider the problem of computing the discrete log of X ∈ ℤp with respect to g — that is, finding x such that Xp gx. Argue that if one can find integers r and ssuch that grp X · gs then one can compute the discrete log of X.

(c). Combine the above two observations to describe a O(√p)-time algorithm for the discrete logarithm problem in ℤp.

14.8: In an execution of DHKA, the eavesdropper observes the following values: What will be Alice & Bob’s shared key?

14.9: Explain what is wrong in the following argument:

In Diffie-Hellman key agreement, Alice sends A = ga and Bob sends B = gb. Their shared key is gab. To break the scheme, the eavesdropper can simply compute A · B = (ga)(gb) = gab.

14.10: Let ? be a cyclic group with n elements and generator g. Consider the following algorithm: Let DH = {(ga,gb,gab ) ∈ ?3 | a,b,∈ ℤn}.

(a). Suppose (A,B,C) ∈ DH. Show that the output distribution of RAND(A,B,C) is the uniform distribution over DH

(b). Suppose (A,B,C) ∉ DH. Show that the output distribution of RAND(A,B,C) is the uniform distribution over ?3.

(c). Consider the problem of determining whether a given triple (A,B,C) is in the set DH. Suppose you have an algorithm ? that solves this problem on average slightly better than chance. That is: The algorithm ? does not seem very useful if you have a particular triple (A,B,C) and you really want to know whether it is in DH. You might have one of the triples for which ? gives the wrong answer, and there’s no real way to know.

Show how to construct a randomized algorithm ?’ such that: for every (A,B,C) ∈ ?3: Here the input A,B,C is fixed and the probability is over the internal randomness in ?’. So on every possible input, ?’ gives a very reliable answer.

14.4: Exercises is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.