1
$\begingroup$

Diffie-Hellman works as follows:

Given public parameters $p$ (a large prime) and $g$ (always referred to as a generator of $(\mathbb{Z}^∗_p)$. Then:

  • Alice randomly chooses $a<p$ and sends $A\leftarrow g^a \mod p$ to Bob;

  • Bob randomly chooses $b<p$ and sends $B\leftarrow g^b \mod p $ to Alice;

  • Alice computes $S\leftarrow B^a \mod p$;

  • Bob computes $S\leftarrow A^b \mod p$.

What happens if we choose $a$ and $b$ grater than $p$?

$\endgroup$
0
$\begingroup$

The modulus operation $\pmod p$ is performed at each step and reduces the result into $\bmod p$. And a clever implementation can use the Fermat's Little Theorem instead of taking the power than reducing to modulo $p$. After that it's possible to use the modular version of repeated squares algorithm or similar.

Example 1) code used from sublimerobots

sharedPrime = 23    # p
sharedBase = 5      # g

aliceSecret = 600     # a
bobSecret = 1500      # b

Alice Sends Over Public Chanel:  8
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:
Alice Shared Secret:  2
Bob Shared Secret:  2

Example 2)

sharedPrime = 23    # p
sharedBase = 5      # g

aliceSecret = 6000000  # a
bobSecret = 15000000   # b

Alice Sends Over Public Chanel:  17
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:

Alice Shared Secret:  8
Bob Shared Secret:  8

I think you are confusing the mathematical representation and the actual value.

$\endgroup$
  • $\begingroup$ Dear @kelalaka, I think that something is wrong with your answer. In example 2, you said $5^{6000000} \bmod 23 =17$ but this is wrong. $\endgroup$ – Meysam Ghahramani Jun 29 at 18:03

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.