im trying to work on key agreement schemas on embeded systems. for diffie hellman, ive written a 256 bit multiplication, on AVR core it takes about 2 seconds on 1Mhz frequency, lets say my algorithm is weak and it'll work in 1/10 of this time. if we multiply the clock and say were working on 3Ghz PC, we have to exponentiate a 256 bit digit to a 256 bit digit, which means doing the multiplication 1.15e77 ( 2^256) time. with a simple relation, it'll take e-4*1.15e77 seconds then?? right??? it is really to long to be practical? what am i missing out here? ty for your answers!!

thanks for your usefull answers so far, but i think my question is a little diffirent!! im not asking a general question, im asking the exact implementation problem, pierre said i would need at most 256 time multiplication, but isn't the public key 256 bits? then diffie hellman would need 2^256 time multiplication at most? what am i missong here? thanks for your previous and upcomiong answers!!

  • $\begingroup$ possible duplicate of How do institutions like banks do RSA with big primes? $\endgroup$
    – Thomas
    May 9 '15 at 8:02
  • $\begingroup$ Yeah, it's a dupe, but the original could really use a better answer. Of the three answers so far, one is buggy, one is (mostly) irrelevant and one takes way too long to get to the point. $\endgroup$ May 9 '15 at 11:27
  • $\begingroup$ BTW: this isn't actually related to your question, but Diffie-Hellman modulo a 256 bit prime is quite insecure. To be secure, you really need at least 1024 bit Diffie-Hellman as an absolute minimum (with 2048 bit groups strongly encouraged). Alternatively, you might want to consider Elliptic Curve groups; there, a 256 bit EC group is actually secure (but the equivalent of the multiplication (called addition there) is rather more compled) $\endgroup$
    – poncho
    Jul 9 '15 at 16:48
  • $\begingroup$ As the question was not received clearly , it is about processing cost of a single exponentiation operation in the scale needed for diffie-hellman. as it is impractical to run it every time user requests a public key needing service like even opening a https web page, operating systems and browsers use PKI to manage the needed operations which are basically set of number generated from a trusted third party. $\endgroup$ Dec 1 '17 at 9:22
  • $\begingroup$ This should probably be a comment and definetly not an accepted answer. There is an abundance of evidence diffie hellman is practical and happen easily every time we open a secure connection. Obviously it can be done so the original question remains. What are you missing? The other answer by Pierre gives the most likely answer. $\endgroup$
    – Meir Maor
    Dec 1 '17 at 10:22

There is a well known technique for exponentation, you might read this http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method . The same techniques and its variants are used for matrix exponentiation ... You only need 256 squaring and at most 256 multiplications.

  • 1
    $\begingroup$ You will find the crypto algorithms algorithms for quite efficient implementations in the "Handbook of Applied Cryptography Book by A. J. Menezes, Alfred Menezes, Paul van Oorschot, and Scott Vanstone" $\endgroup$
    – Pierre
    May 9 '15 at 9:44

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.