0

Alice, Bob and Eve are all present in the classroom. Alice and Bob want to agree on a password that Eve will not be able to know. Eve has access to all communication between Alice and Bob, and Alice and Bob share no common information unknown to Eve. They apply the so-called Diffie-Hellman key exchange protocol (you are not supposed to be familiar with this terminology). This protocol works as follows: First Alice and Bob choose a (large) prime number N and a suitable number g with 2 ≤ g < N.

Then Alice chooses a number 1 < A < N randomly. She doesn’t reveal this number, but keeps this number a secret. Similarly, Bob chooses a number 1 < B < N randomly that he keeps secret. Alice then announces the number g ^A modulo N to Bob (and Eve who is Eavesdropping). Similarly, Bob announces the number g ^B modulo N to Alice (and Eve). The idea in the protocol is that Alice and Bob can both calculate (in a feasible manner) the secret key as the number $$g^{AB} mod(N)$$

a) Explain how Alice and Bob can compute the number g^(AB)modulo N. (Hint: You may assume that Alice and Bob can feasibly compute g C modulo N for any given number C).

My Attempt -

If Alice and Bob can compute g^c mod N then we know that Alice can work out B because Alice knows 3 of the 4 variables to the equation Bob gave. Bob announced the answer to g^b mod N. Alice know's the answer to this equation, g and N. So she can solve for 'b'. Similarly Bob can do the same. Once both they have worked out either A or B, they know their own values so can compute $$g^{AB} mod(N)$$

Would that be correct?

TheRapture87
  • 209

1 Answers1

0

Firstly your question looks like you copied and pasted, since exponents are missing all over the place. Secondly, your attempt is of course wrong, because the same reasoning would let Eve obtain all the information. The point is that you can feasibly compute exponentiation modulo $N$, but you cannot feasibly undo it (at least we don't know how to do it as of today). So you have to figure out how Alice and Bob can compute the desired key without so-called solving equations.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • 1
    Here "feasible" usually means within a few months; Something that takes 100 years is not feasible. – user21820 May 05 '16 at 13:43
  • Ok, so we start of knowing that g and N are public. Alice then selects a private random number 'A' which she uses to compute $$g^A mod N$$ sharing the answer publically. Bob then does the same procedure but with a B, sharing the answer publically again. Alice takes bob's public answer and raises it to the power of her private key to obtain the shared secret value. Bob takes his public answer and raises it o the power of Alices private key to obtain the shared secret value.

    Now they both have the same secret value but Eve does not. They can then calculate g^AB mod N

     – TheRapture87 May 05 '16 at 15:20
  • @Aceboy1993: Exactly. You're done! =) By the way, the inverse problem is called the Discrete Logarithm problem, which is as of now not known to be feasible to solve by a conventional computer, but has been shown to be theoretically feasible to solve by a quantum computer. If quantum computers are successfully built, they would render RSA broken. – user21820 May 05 '16 at 15:46
  • Thank you for the help. That is quite interesting about quantum computing, worrying as well! – TheRapture87 May 05 '16 at 15:51
  • @Aceboy1993: Well so people are now coming up with cryptographic schemes that seem resistant to quantum algorithms, in anticipation of the day Shor's algorithm for solving the discrete logarithm can be performed on large inputs. – user21820 May 05 '16 at 16:13