1
$\begingroup$

As we know that in DH key exchange, both Alice and Bob would agree on the parameter $p$ and $g$. Next, Alice would choose a secret key $A$ while Bob would choose a secret key $B$. Alice would compute $g^A\mod p$ and Bob would compute $g^B\mod p$. They would exchange these computed values and each side would raise their secret key against the received computed value, i.e. $(g^A)^B\mod p = (g^B)^A\mod p$.

From Charlie's (external party) point of view, he would know values of $p$, $g$, $g^A\mod p$ and $g^B\mod p$. Assuming that $g^A\mod p$ and $g^B\mod p$ are 100 digits long, would he be able to determine a bound (in terms of digits or bits) for the respective secret key $A$ and $B$?

Please do point me at any links that is relevant to this question! Thanks & Cheers!

Improve this question
$\endgroup$
1
  • $\begingroup$ Would appreciate your comments on this question when you downvote, so that I could improve on it. Thanks! $\endgroup$
    – edmund2008
    Apr 29, 2014 at 9:30

1 Answer 1

Reset to default
2
$\begingroup$

Assuming that $g^A \bmod p$ and $g^B \bmod p$ are 100 digits long, would Charlie be able to determine a bound (in terms of digits or bits) for the respective secret key $A$ and $B$ ?

100 digits is approximately 332 bits; if $p$ is 332 bits long, then it is known to be feasible to apply the Number Field Sieve algorithm to recover the values $A$ and/or $B$; that certainly would give him the bound.

For reference, Antoine Joux and Reynald Lercier computed the discrete log of a 431 bit (130 digit) base in three weeks.

Improve this answer
$\endgroup$

Your Answer

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

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