# RSA Cryptography, finding the secret key

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?

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.
• 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 May 5, 2016 at 15:20