1

Assuming shared parameters: prime p base g

Alice's private key is a and her public key is A, which is g ^ a mod p

Calcuating A requires g * g * g... a times. Modulus is applied whenever necessary.

If an attacker knows A, p, and g, why is it hard to calculate a? Would he not just keep multiplying on g and seeing if he's achieved A?

I am not seeing what is fundamentally different between Alice's computation to create A from a, and Eve's computation to brute force a knowing A. Can anyone provide some insight here?

3

Computing the public key is a problem of modular exponentiation, which can be done in O(log(e)) steps via exponentiation by squaring.

On the other hand, finding the private key is the discrete logarithm problem, for which no equally efficient algorithm exists. You just have to run through all the possible values and try them all. There are some better algorithms, such as Pollig-Hellman and Big Step-Little Step, but they are generally not applicable for the general case (the former is only efficient for numbers that decompose into small primes, for example)

This means that computing a modular exponent is vastly faster than a discrete logarithm. For a very large exponent, this effectively makes the exponentiation a one-way function.

...unless, of course, you have a quantum computer!

  • time ​ -> ​ "modular multiplications" ​ ​ ​ ​ – user49075 Aug 4 '15 at 17:18
  • I'll go with "steps" for now; it all means the same thing, really. – etherealflux Aug 4 '15 at 17:19
  • Also, I'll expand upon this answer when I get home - I tried to look up my notes from crypto, but the mobile OneNote app just shows the word "[Equation]" 25 times in every page... – etherealflux Aug 4 '15 at 17:30
  • This is perfect. Thanks! I did not know that the exponentiation could be done in less steps than e. Makes perfect sense. – ztpsec Aug 4 '15 at 17:48

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.