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?

1 Answer 1

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!

4
  • time ​ -> ​ "modular multiplications" ​ ​ ​ ​
    – user49075
    Aug 4, 2015 at 17:18
  • I'll go with "steps" for now; it all means the same thing, really. Aug 4, 2015 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... Aug 4, 2015 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, 2015 at 17:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .