# 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? – Thomas May 9 '15 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. – Ilmari Karonen May 9 '15 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) – poncho Jul 9 '15 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. – Hamed Temsah Dec 1 '17 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. – Meir Maor Dec 1 '17 at 10:22