# Derivative of Diffie Hellman

Looking to get some clarification on this. We have the same three protagonists, Bob and Alice, trying to send each other a message. And Eve trying to figure out the message sent by Bob and Alice.

Suppose they proceed as follows:

• Alice privately picks numbers a and x such that $ax \equiv 1 mod(p-1)$;
• Bob privately picks a number b such that the gcd(b,p-1) = 1;
• Alice computes $u \equiv m^a mod(p)$, and sends this to Bob;
• Bob computes $v \equiv u^b mod(p)$, and sends this to Alice;
• Alice computes $w \equiv v^x mod(p)$, and sends this to Bob.

How does bob figure out Alice's message?

Now, suppose Alice and Bob are too lazy to exponentiate, and instead:

• Alice privately picks numbers a and x such that $ax \equiv 1 mod(p)$;
• Bob privately picks a number b such that the gcd(b,p) = 1;
• Alice computes $u \equiv a\cdot m(mod(p))$, and sends this to Bob;
• Bob computes $v \equiv b \cdot u(mod(p))$, and sends this to Alice;
• Alice computes $w \equiv x \cdot v(mod(p))$, and sends this to Bob.

How does Bob figure out Alice's message?

• The first one is known as Shamir's three-pass protocol. Commented Oct 19, 2014 at 17:05

Fermat's little theorem says that if $k \equiv 1 \mod (p-1)$, then $m^k \equiv m \mod p$.

So if you have a number $a$ and you take $m^a \mod p$ and the result you do to the power $x$ ,modulo $p$ then you get $(m^a)^x \equiv m^{ax} \mod p$ and this will equal $m$ again when $ax \equiv 1 \mod (p-1)$.

Alice puts a lock on $m$ (power $a$), then Bob puts his lock on it (power $b$), and then Alice removes the first lock by using the power $x$, which cancels the effect of the power $a$...

This should put you on the right track for the first.

The second really isn't that hard...

• Thanks for the help! I'm still getting stuck though... so Bob will end up with $w = v^x = (u^b)^x = ((m^a)^b)^x = (m^{ax})^b = m^b$, is that correct? Then how does Bob use this to get just m? Commented Oct 19, 2014 at 18:13
• How can he reverse his $b$? (How did Alice do that ?) Commented Oct 19, 2014 at 18:48
• Eureka! That's what I needed :) He would just find a new number, say y, such that $y \cdot d \equiv 1 mod (p-1)$, and then raise m to the y'th power to get back m. Thank you! Commented Oct 19, 2014 at 19:01
• $d$ should be $b$ in the previous comment Commented Oct 19, 2014 at 19:03
• Ahh, yes. My bad. I should have also said raise 'w' to the y'th power, but it's all the same I suppose. Commented Oct 19, 2014 at 19:22