Diffie Hellman Exponentiation Implementation Problem

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!!

• possible duplicate of How do institutions like banks do RSA with big primes? May 9, 2015 at 8:02
• 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. May 9, 2015 at 11:27
• 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) Jul 9, 2015 at 16:48
• 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. Dec 1, 2017 at 9:22
• 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. Dec 1, 2017 at 10:22