1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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...) $\endgroup$ – Tango Feb 14 '15 at 9:01
  • $\begingroup$ @Tango: Because when you plug in $B = g^b \pmod p$, it is understood that it applies to both. Regards $\endgroup$ – Amzoti Feb 14 '15 at 12:58
  • $\begingroup$ Okay. Now I have it. Thank you. $\endgroup$ – Tango Feb 14 '15 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.