Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
    
Would appreciate your comments on this question when you downvote, so that I could improve on it. Thanks! –  edmund2008 Apr 29 at 9:30
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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