This is my conception, implementation and tests of advanced(2-layer) DiifieHellman('2lDH' abbreviated) key exchange protocol that works with very long inegers(like 19.729+ chars long without any problems). You can find an example file(main.cpp) at this repository with it's description.
Original DiffieHellman is here.
It is also a part of RedLibrary.
I was understanding how DiffieHellman works and I thought, DH is really good for making secure client-server messaging channels, but I did have an idea how to make the algorithm longer(and safer) and get an opportunity to hide the base number you use.
Basically, it is the DH, but 2lDH firstly calculates the base number, and the shared key after that. So, that is why it was named "2-layer DiffieHellman".
So, here you can see the standard DiffieHellman algorithm:
Diffie-Hellman (colors)
======================
___ ___
/ m \ / m \ - // 1 Step. We have the same values at the beginning.
\___/ \___/
_|_ _|_
/m*a\ /m*b\ - // 2 Step. We're getting mixed keys.
\___/\___ /\___/
___ __|____/ ___
/m*b\/ |______/m*a\ - // 3 Step. We're exchanging them.
\___/ \___/
_|_ _|_
/mab\ /mab\ - // 4 Step. Mixing again with secret keys and that will be -THE SHARED KEY-.
\___/ \___/I'm sure you know it, so, I wrote it here to make it easier to compare with 2-layer DH.
Let's have a look of 2-layer DiffieHellman:
2-layer DiffieHellman (colors)
=============================
Part 1 (getting the base)
------------------------
___ ___
/ m \ / m \ - // 1 Step. We have the same values at the beginning.
\___/ \___/
_|_ _|_
/m*x\ /m*y\ - // 2 Step. We're getting mixed keys.
\___/\___ /\___/
___ __|____/ ___
/m*y\/ |______/m*x\ - // 3 Step. We're exchanging them.
\___/ \___/
_|_ _|_
/mxy\ /mxy\ - // 4 Step. Mixing again with secret keys and that will be -THE BASE NUM-.
\___/ \___/
Part 2 (getting the shared secret)
---------------------------------
h = mxy // 'h' is our base num (wrote this just to make it easier).
___ ___
/ h \ / h \ - // 1 Step. We have the same base, which is hidden for the Man-In-The-Middle(MITM).
\___/ \___/
_|_ _|_
/h*a\ /h*b\ - // 2 Step. We're mixing the base with secret keys.
\___/\___ /\___/
___ __|____/ ___
/h*b\/ |______/h*a\ - // 3 Step. We're exchanging them.
\___/ \___/
_|_ _|_
/hab\ /hab\ - // 4 Step. Mixing again with secret keys and that will be -THE SHARED SECRET-.
\___/ \___/
Shared key = hab
----------So, as you can see, that looks like a doubled DiffieHellman, and yeah, it is, but, first of all, our Base Num is hidden now, secondly, this DH edition is now safed from log function and, thirdly, we spend reasonable time to get well secured. In fact, there are some difficulcy modes in this library, which gives it an ability to it to be rather wide-usable(from IoT to infrastructure-level apps).
It looks like this:
2-layer DiffieHellman (math scheme)
==================================
P = -1 // The max value of data type.
Part 1 (getting a base)
----------------------
1) Public keys.
~~~~~~~~~~~~~~~
/// Getting a public keys.
AlicePublic1 = (2 ** AliceKey1) mod P
BobPublic1 = (2 ** BobKey1) mod P
2) Symmetric base.
~~~~~~~~~~~~~~~~~~
/// Getting the same reminder.
AliceShared = (BobPublic1 ** AliceKey1 mod 998 + 2) mod P1 // Shared (E [2;1000].
BobShared = (AlicePublic1 ** BobKey1 mod 998 + 2) mod P1 // Shared (E [2;1000].
Part 2 (getting the shared secret)
---------------------------------
SharedBase is our base num.
1) Public keys.
~~~~~~~~~~~~~~~
/// Getting a public keys.
AlicePublic2 = (SharedBase ** (rand() % (standard / log2(SharedBase))) + 1) mod P2
""""""""""""""""""""""""""""""""""""""""""" // Same 1.
BobPublic2 = (SharedBase ** (rand() % (standard / log2(SharedBase))) + 1) mod P2
""""""""""""""""""""""""""""""""""""""""""" // Same 2.
2) Symmetric Secret.
~~~~~~~~~~~~~~~~~~~~
/// Getting the symmetric pair.
AliceSymmetric = (BobPublic2 ** (rand() % (standard / log2(SharedBase))) + 1) mod P2
""""""""""""""""""""""""""""""""""""""""""" // Same 1.
BobSymmetric = (AlicePublic2 ** (rand() % (standard / log2(SharedBase))) + 1) mod P2
""""""""""""""""""""""""""""""""""""""""""" // Same 2.
/// Finally.
AliceSymmetric = BobSymmetric
-------------- ------------In the example file I used Prime number equal to -1, because I wanted the algorithm to be un-cutted in range in all operations(I wanted to get a pair of fingerprints that can be used in encryption functions as a key).
The crucial thing in classic DiffieHellman is that you're exchanging something, that it's impossible to calculate sqrt from(as difficult that useless):
6k (unsafest one).
-------
Average time spent to calculate(for example) = 0.01s.
Max value is about (2 ** (6.000 * 6.000)).
Key is one of [2; 2**36m]. (With some exclusions).
Just imagine how much time that takes.
Or calculate in a big num calculator.So, as that is so, we can conclude:
Est. chance of getting the one we need = lim[x->0]As we use _2lDH_ that is like 2x _DiffieHellman_, that can be wrote as funny math like:
Est. chance of getting the one we need = lim[x->0] / 2In fact, to break this, first of all we need to capture all packets related to the protocol and to perform all calculations needed after that.
I made some standards for each part to use 2lDH in way you need. Let's check them out.
⚠️ Also need to say that these parts were calculated on different machines, but I think that is good, let's get a look of such a typical calculators:Part 1: 💻 [MacBook Air 2017 with Intel core I5 processor] Simple and reliable, historical machine imo.
Part 2: 💻 [MacBook Air 2020 with M1 processor] Typical anybody's calculator, all of these operations will take +- the same time ;).
✏️: sqrt(max) was placed there to show the nums each side need to use as max value to get a private key in time <= than I shown.
| Standard(num of possible variations, millions) | sqrt(max) | base | Time spent(in seconds) |
|---|---|---|---|
| 70m | 8.366 | 2 | 4,127 |
| 105m | 10.246 | 2 | 8,525 |
| 126m | 11.224 | 2 | 11,799 |
| 238m | 15.427 | 2 | 38,475 |
| 336m | 18.330 | 2 | 71,926 |
5 Standards for Part 1. I think that's enough to start, but maybe will add more later. Let's continue with Part 2.
As it can use different bases, I've separated these tables.
We have a problem in fact, I don't know how to calculate the nums here. They differs a lot(exponent can equal to 1, or to the max one), so, let me write just the range I got by executing the examples some times...
| difficulcy mode | num of possible variations | sqrt(max) | Time spent(in seconds) |
|---|---|---|---|
| 6k | 36.000.000 | 6.000 | 0.8-4 |
| 8k | 64.000.000 | 8.000 | 0-4 |
| 11k | 121.000.000 | 11.000 | 1-??? |
| 16k | 256.000.000 | 16.000 | 1-26(?) |
So, it's possible to spend a lot of time calculating this.
I had to spend 26 seconds to calculate a pair(16k mode):
(I couldn't fit even one shared number in one terminal, haha).
As you could understand, it can be used everywhere you need a secure channel(server-client applications for example), literally everywhere.
Good question, not difficult in fact:
- 1.) We're getting the same keys.(Full 2lDH cycle)
- 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, quality of Red).
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).
In fact this is the thing everyone should do in own vision to get to result needed. Hope you will do that.
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.
- 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.
With Copyright© ∞ Vladimir Rogozin.