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

| improve this answer | |
$\endgroup$
  • 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$ – Meysam Ghahramani Jun 29 '19 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 Oct 27 '19 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 Oct 27 '19 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).

| improve this answer | |
$\endgroup$
  • $\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 Oct 28 '19 at 12:42
  • $\begingroup$ you are alright about the (p-1), I put more precision about "break" $\endgroup$ – Ievgeni Oct 28 '19 at 12:46

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.