🔑🔑 DiffieHellman

What is it?

This is an implementation of DiifieHellman key exchange protocol that works with very long inegers(19.729 chars long, can work with bigger ones, look at the screenshot that is placed above this text or below). You also can find an example file(main.cpp) at this repository with it's description.

Advanced DiffieHellman is here.
It is also a part of RedLibrary.

How it works?

The simpliest way to describe how it works is to draw that, so, I did that, here it is:

  _____     _____
 /     \   /     \
|   m   | |   m   | - 1 Step. We have the same values at the beginning.
 \_____/   \_____/
    |         |
  __|__     __|__
 /     \   /     \
|  m+a  | |  m+b  | - 2 Step. We're mixing them with our secret keys.
 \_____/   \_____/
    |         |
  __|__     __|__
 /     \   /     \
|   ma  | |   mb  | - 3 Step. We got mixed keys.
 \_____/| |\_____/
        \ / 
  _____  X  _____
 /     \/ \/     \
|   mb  | |   mb  | - 4 Step. We're exchanging them.
 \_____/   \_____/
    |         |
  __|__     __|__
 /     \   /     \
| mb+a  | | ma+b  | - 5 Step. Mixing again with secret keys.
 \_____/   \_____/
    |         |
  __|__     __|__
 /     \   /     \
|  mab  | |  mab  | - 6 Step. We got the same keys.
 \_____/   \_____/

So, you have successfully traced the 'fingered-edition' DiffieHellman, but we're here for something much more difficult and interesting, you're here for education, not for code, doesn't it? ;)

I'm joking, it's 'safed' by MIT Licence, it's fully your's.

Let's get back to the funny math. Let's describe it by steps I drew before:

• 1.) It's like 0 position, needn't to describe it. Just getting a 'Prime number', base number(it's named 'g') and getting some random keys.

P = -1; // Just getting the max value.
g = 3;  // Base number, in fact, it's better to use 2.

Yeah, we're working with exponent, because it's 'easy' to calculate it but it's difficult to get sqrt from that.

• 2.-3.) We're calculating our public keys with the following formulas:

A = g**a mod P // For Alice.
B = g**b mod P // For Bob.

• 4.) Next, we're exchanging them, and the crucial thing in DiffieHellman is that you're exchanging something, that it's impossible to calculate sqrt from(or at least toooooooooo difficult, as difficult that useless):

Est. chance of getting the one we need = lim[x->0]

• 5.-6.) We're using our secret key again to get synced keypair, and yeah, exponent again:

S1 = B**a mod P // For Alice.
S2 = A**b mod P // For Bob.

S1 = S2

Congratulations! We did that! Now, you understand how it works, don't you want to see some examples? Look at the screenshots below.

Where to use?

As you could understand, it can be used everywhere you need a secure channel(server-client applications for example), literally everywhere.

Any tests? Okay:

Tested on Macbook Air with i5.

So, for spending about 200 seconds to calculate(haha, ya, 200), you have these settings:

Alice's secret	Bob's secret	G	P	Time(seconds)
7.000.000	103	2	have't used	197,268
7.000.000	52	4	have't used	199,839
7.000.000	34	8	have't used	196,951
7.000.000	25	16	have't used	221,794
7.000.000	20	32	have't used	193,420

Or another test - about 60 seconds:

Alice's secret	Bob's secret	G	P	Time(seconds)
3.000.000	145	2	have't used	59,770
3.200.000	3	3	have't used	57,992
3.000.000	72	4	have't used	59,241
2.200.000	3	5	have't used	57,804

Or the one you want to see:

Task	Time
2 ** 3.005.400.000 (not using P)	about 20 minutes

So, if you want to use any of these nums, you have to calculate ~time you would like to spend(paper math, yo), and, of course, use the sqrt(Akey * Bkey) as a range of rand() or Red::Randomizer() in your application(+2!!!! Of course, bcs, that's the way to make DH possible).

How to make a channel in client-server application?

Good question, not difficult in fact:

• 1.) We're getting the same keys.(Full DiffieHellman)
• 2.) Now, we have the same keys. We need to get an encrypted channel, how to do that? My answers are here:
  ** 1.) AES standard.
  ** 2.) RES standard (mine one).
  You can use DH shared key as a key or to make it x2 longer with my simple encryption algorithm(Va1) and after that use the result to get a hashed sum, or to get a hash, and cut/expand it to the length you need(Sha256).

Notes:

• P number (prime one) works stable with ~197.290 characters long (From 'RedTypes.h': 'Red::uint524288_t').
• Needs to understand that the time of calculation rises as the secret key value rises.
• If you use any of integer types that sizes as 2048 and more, it will take a HUGE AMOUNT OF TIME to calculate, use those only for specific tasks.
• Secret key is restricted by uint max size in power function(function from boost is used there).

All material in this repository is in the public domain.