This question already has an answer here:

I very well understand the Diffie-Hellman key exchange method, at least I think I do. And I was trying to implement it to try it out.

I went and calculated a very large prime number $p$ about 400 digits long. And i set $g$ to 5.

I generated a random secret number $a$, for example: 42523434.

The problem I'm facing is when I calculate $g^a \bmod p$, $g^a$ in particular, it seems to take my computer forever to calculate it, so it seems to be impractical to give $a$ such a number so I went for a smaller number (a five digit number) which takes about a second or two to calculate.

So now we have $A \equiv g^a \pmod p$, with the eavesdropper knowing $g$, $p$, and $A$.

But wouldn't it be possible to brute force $a$ by trying all 100000 combinations until what he calculates matches $A$ which would take him that long if he is good at computing powers? A solution to this would be increasing $a$ but increasing $a$ would make the exchange take so long that it wouldn't be a good method to exchange the keys.


marked as duplicate by yyyyyyy, Biv, otus, tylo, e-sushi Aug 15 '17 at 13:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


You want modular exponentiation, not exponentiation followed by modular reduction.

The range of $a$—usually chosen uniformly at random from at least $2^{256}$ possibilities—is so large the attacker has no hope of guessing it blindly. The attacker's best strategy is to use the number field sieve to compute the discrete logarithm, rather than blindly guessing candidates and checking them, which is why we typically choose prime moduli with over 600 digits, or 2048 bits.


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