Diffie–Hellman key exchange

Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula:

G(generator), P(prime), A(side A), B(side B)

• A = G^A MOD P
• B = G^B MOD P

AS is a secret key that side A will generate:

• AS = B^A MOD P

BS is a secret key that side B will generate:

• BS = A^B MOD P

So I realise I have to refresh my memory about prime numbers and learn about primitive roots, So I did learned them but I couldn't understand how the math is even possible, let me show an example so I can focus my question:

1. G = 5, P = 7, A = 8, B = 25
2. A = 5^8 MOD 7
3. A = 4
4. B = 5^25 MOD 7
5. B = 5
6. AS = 4^5 MOD 7
7. AS = 2
8. BS = 5^4 MOD 7
9. BS = 2

How can AS be equal to BS?, I will be glad if someone can help me understand how is it possible.

Alice ($a$ is private) calculates her public value:

$$A = g^a \pmod p$$

Bob ($b$ is private) calculates his public value:

$$B = g^b \pmod p$$

They exchange $A$ and $B$ (both public).

Alice calculates:

$$s_A = g^a \times B = g^a \times g^b \pmod p = g^{a b} \pmod p$$

Bob calculates:

$$s_B = g^b \times A = g^b \times g^a \pmod p = g^{b a} \pmod p = g^{a b} \pmod p$$

Notice that:

$$s_A = s_B$$

The security is wrapped up in the Discrete Log Problem (DLP).

• I've been trying to learn and understand this as well. I plugged in small numbers to experiment with this and it seems to me that Alice should have "s_A = (g^a \times B) (mod p) = ..." instead. So why doesn't the g^a \times B also have a mod operator when it's used elsewhere? (Apparently the markdown for subscripts and so on does not work in comments...) – Tango Feb 14 '15 at 9:01
• @Tango: Because when you plug in $B = g^b \pmod p$, it is understood that it applies to both. Regards – Amzoti Feb 14 '15 at 12:58
• Okay. Now I have it. Thank you. – Tango Feb 14 '15 at 16:48