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

Exercises

  • Page ID
    7407
  • 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 : x ≡p 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 i ≠ j with ri ≡N rj + x.

    HintThis 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 X ≡p gx. Argue that if one can find integers r and ssuch that gr ≡p 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:

    Figure14-8.jpg

     

    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:

    Figure14-9.jpg

     

    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:

    Figure14-10.jpg

     

    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:

    Figure14-11.jpg

     

    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.