3
$\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$
3

2 Answers 2

1
$\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:  8
Bob Sends Over Public Chanel:  4

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

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


In the sense of optimization, the code from sublimerobots is not good. Actually. instead of

bobSharedSecret = (A**bobSecret) % sharedPrime

a faster version

bobSharedSecret = pow(A,bobSecret,sharedPrime)

which uses modular binary exponentiation.

$\endgroup$
3
  • 1
    $\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$ Commented Jun 29, 2019 at 18:03
  • $\begingroup$ Two remarks: A] use of FLT is optional, and only provides a time saving by a factor like $\log(a)/\log(p)$ (about 2 in the first example, about 5 in the second). B] As pointed in above comment, the values in the second example are wrong. $\endgroup$
    – fgrieu
    Commented Oct 27, 2019 at 19:15
  • $\begingroup$ @fgrieu I don't know why it was a mistake and why I did not correct it. I've used code to generate! Thanks. $\endgroup$
    – kelalaka
    Commented Oct 27, 2019 at 19:38
1
$\begingroup$

It could have three consequences.

1) If you are very unlucky, and you pick a "zero" ($a$ such that $a=0\mod p-1 $), it will break your system : (but this will happen with a negligible probability, and it could be detected) An external observer will easily guess the shared secret

2) You lose in efficiency

3) Your integer had to be chosen upper-bounded (you can not pick uniformly over all the integers, if you choose badly this point (something not divisible by $p$), it will create a bias in the distribution of your keys (probably not a problem in practice, but in theory it's less secure).

$\endgroup$
2
  • $\begingroup$ $a\equiv0\pmod p$ does not seem to matter. $a\equiv0\pmod{p-1}$ matters in that it will make the shared secret always $1$, which is insecure; but the two parties still hold the same shared secret. You get $a\equiv0\pmod{p-1}$ using $a\equiv 0\pmod{p-1}$. $\endgroup$
    – fgrieu
    Commented Oct 28, 2019 at 12:42
  • $\begingroup$ you are alright about the (p-1), I put more precision about "break" $\endgroup$
    – Ievgeni
    Commented Oct 28, 2019 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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