[Request] Diffie-Hellman Key Object

Scenario: You want to send some encrypted message from one MMF2 application to another over a network. You could for instance use the AESFusion object to encrypt a string (using a key), and then send the encrypted string over the network with Lacewing.

Problem: How do you set up the key in the receiving program so that you can decrypt the message? You can't just send the key over the network, that would kind of ruin the point of using encryption in the first place. You could hard code a key in both programs, but that's not really a good idea either.

A solution: Before encrypting and sending the message, create a key using the Diffie-Hellman key exchange algorithm. The algorithm takes some random numbers as inputs, two are "public" and can be safely sent across the network while another is "private" and is generated independently by both sending and receiving programs. With these inputs you can magically (mathematically) generate the same key in two different places without sending any values that can be intercepted and used by a third party.

See http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange for more information and an example.

I have been able to replicate the example from Wikipedia with just events in MMF2, but I haven't been able to make it work with large enough input numbers for the resulting key to be secure.

The request: A simple object that compute the values from inputs with the Diffie-Hellman algorithm, returning strings. It should need only two actions:

1) Generate "stage 1" string from inputs
2) Generate key (as string) from "stage 1" string

You can do this without needing an extension. What prevents you from generating the codes directly? All you need is correct exponentiation.

I would guess that for decent security it requires numbers larger than MMF can naturally represent, eg. 128 bits.

Even without that, MMF's pow function is floating point, which would cause too many errors for the key exchange to be 100% reliable.

I did make it work using small values like in the example on Wikipedia. When using larger prime numbers or larger values for the random integers the two keys rarely came out the same. I figured it had to be because of lack of precision, but I'm not exactly an expert. If anyone else has succeeded, I would love an example file!

Fast exponentiation isn't possible in MMF, you'd need to use an extension. If I wasn't so busy I'd put into an extension the code I used for my cryptography unit at Uni. And someone less lazy would wrap a proper, well-tested encryption library into an extension :)

So if it has been established that MMF2 cannot pull this off internally, I guess the request still stands. We have some working encryption objects, but we need a key exchange mechanism.

Have you tried with the Int64 object? It's not 128 bit like said above, but it could do for some simple stuff.

Can it do exponentiation?

Yep apparently :)

I have now made an attempt using the Int64 object, but I seem to be running into the same problems as before. It works with really small integers (<20), but with anything larger the keys come out differently. I'm not sure how large the numbers need to be for the exchange to be reasonably secure, but I'm sure 1-20 isn't enough. :)

Have anyone else tried with the Int64 object?

Hmm, if you really need this you could make your own 128 bit (16 byte) or 256 bit (32 byte) math program with the binary objects. I have thought about it but I do not have enough experiance with binary just yet to attempt it. I don't even know how the Int64 object does it! If I knew that then I'd help ;)

The INT64 object probably just uses C++'s built-in 64-bit int type (long long int?). As there is no int version of pow() in the C standard library, it's probably using the floating point version, hence why it doesn't seem to be any better.

Maybe try multiplying in a loop?

64 bits is too small to be useful, you are almost certainly overflowing it. You really do need multiprecision integer arithmetic. (Wasn't there an extension for this long ago?)

I thought we had a "big int" extension somewhere (at least there was something like that when I was embarking to write one). However, you can work around this by using multiple smaller numbers and cascading the key generation process in layers so that each layer results in a 64-big number.

Wouldn't that cause problems with "stage 2" of the process, when the key is computed from the result of the calculation performed by the remote party?

I'm thinking about this part:

a^b mod c

Where 'a' is the value received from the other party, 'b' is the (preferably large) random integer and 'c' is the prime number.

Quote:

---

Originally Posted by Mokhtar

I thought we had a "big int" extension somewhere (at least there was something like that when I was embarking to write one). However, you can work around this by using multiple smaller numbers and cascading the key generation process in layers so that each layer results in a 64-big number.

---

Well now you're describing how you implement multiprecision arithmetic :) It seriously would be easier to wrap one of the pre-existing libraries than to start doing this in MMF.

Of course Chris, but building an extension requires a C++ developer with some free time.

By the way, if anyone knows of any other method besides the Diffie-Hellman key exchange one could use to exchange a key, I would appreciate to hear some ideas. I am in need of some way to establish a secure connection in my project.