1
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\begingroup$ possible duplicate of How do institutions like banks do RSA with big primes? $\endgroup$
    – Thomas
    May 9, 2015 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$
    – Ilmari Karonen
    May 9, 2015 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, 2015 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$
    – Danii-Sh
    Dec 1, 2017 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, 2017 at 10:22

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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, 2015 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.