# Is this self algorithm made private key for Diffie-Hellman key exchange secure

i created a function in javascript that creates my a for the DH exchange like this:

function createSecretKeyArray(){
let BigNumber = require('bignumber.js');
let numberArray = [];
const multiplier = 1;

for(let i=0; i<32; i++){

let randomNumber = BigNumber.random(multiplier);
let MulConstant = new BigNumber(10 ** multiplier);
numberArray.push(secret);
}

return numberArray;

}


TLDR: It creates 32 randomized numbers between 1 and 11 and computes my a: a = number0 * number1 * .... * number31. I want to use this in G^a mod P, G=2, P is from https://datatracker.ietf.org/doc/html/rfc3526#section-5, chapter 5.

My question is now: Is this algorithm secure ? Are there any problems that occur once someone tries to guess my secret ?

• So, you have around 107 bits for $a$, too small Commented Dec 30, 2023 at 19:30
• Ok, this is changable, i take this. But my question is, if my algorithm is insecure. For example, are there some flaws to track my a ? Commented Dec 30, 2023 at 19:38
• That is rather a computer/network security question... Commented Dec 30, 2023 at 19:39
• It's really rather simple. When ever you ask "Is this crypto thing I made secure?", then the answer is "no". If you don't ask, it's still not secure. Commented Jan 4 at 9:21

Is this algorithm secure ?

No, it is not.

As kelalaka pointed out, the $$a$$ values you get are always less than 111 bits long; we know private exponents that small can be recovered.

However, it's worse than that.

Your $$a$$ will always be in the form $$2^b3^c5^d7^e11^f$$, for $$b,c,d,e,f$$ with known (and small) distributions. Given a value $$g^a$$, the attacker can just make two lists, one of $$g^{5^d7^e11^f}$$ (for values of $$d,e,f$$ that fall in the probable range, he needn't cover every possibility [1]), and $$a^{-(2^b3^c)}$$, and scan those two lists to look for a match. I expect that shouldn't take that long on a laptop, and is likely to succeed [2].

And, once he has recovered $$a$$, he can learn any shared secret derived with that private value.

[1]: The point of covering only the probable possibilities is that this makes the lists much shorter, while still making the attack succeed with high probability. If you have the resources, the attacker can list every possibility - I suspect those lists might end up being a bit too large for a single laptop.

[2]: And, yes, this attack is a variant of Big Step/Little Step; it's a classic for a reason.

• Ok, thanks a lot! What are the best alternatives for a self-calculated a ? Commented Dec 31, 2023 at 9:25
• @kelalaka: actually, the $a$ I was referring to is the product of all 32 values between 1 and 11. Hence, the possible ranges of $b,c,d,e,f$ are a bit larger... Commented Dec 31, 2023 at 13:08
• @kelalaka: well, $a$ is the product of 32 random values selected from $1, 2^1, 3^1, 2^2, 5^1, 2^13^1, 7, 2^3, 3^2, 2^15^1, 11^1$. Because they are multiplied, we are effectively just adding the exponents from the common bases (for example, $4 \times 6 \times 9 = 2^2 \times 2^13^1 \times 3^2 = 2^{2+1}3^{1+2}$. The resulting exponents will have an easily computable distribution. Commented Dec 31, 2023 at 17:09
• @poncho yes, that is. Was not clear for everybody IMHO. Commented Dec 31, 2023 at 17:20

Actually, if you take it mathematically and choose a better range, you get faaar more complexity to strengthen the algorithm:

First of all choose a single random number r in a range v between, for example, 1000 and 10000 (you can set the borders of your range different). Then take a range, for example [r-v, r+v], with an range-size k=2*v, this is the range we pick our random numbers from.

Secondly, take n numbers from your range and calculate your a from DH with these numbers as mentioned above.

If you do this (or even a "better" version with higher values and borders), you can calculate the possible number of possibilities for your exponents with the binomial coefficient ( n+k-1 over k-1 ) (See here: https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)). These numbers grow exponentially if you choose good values for n and k.

Here is an example:

v = 250 => k = 500
r = 4213 => k's in [3963, 4463]
n = 1024


Calculate:

( n+k-1 over k-1 ) = 1024+500-1 over 500-1 = 1523 over 499 = 4.904565E+416


Even if you take smaller numbers like my example you will get an gigantic number of possibilities for your exponents e1 * e2 * ... * e1023 = a.

• And how is this better than the simple-minded "select a random integer $a$ from the range $[1, 2^{256}]$? Commented Jan 1 at 20:02
• It is easier to calculate your modular expressions if you have the single coefficents your a consists of. Commented Jan 1 at 20:05
• Are you saying that, say, binary exponentiation or montgomery ladder is actually difficult? Either would be far more efficient than going through 1024 exponentiations... Commented Jan 1 at 20:13
• I actually use binary exponentation later on in the process, that is the reason why i need my number array that computes a via multiplication of the single elements. The m.-ladder is not really helpful, since i already re-calculate my result for every single exponent modulo P later on. My point is: If i choose a randomly, lets say a=2^133-1, it is extremely hard to compute 2^(2^133-1) mod P since i do not know the prime factorizarion of a. The m.-ladder will not calculate it for me, and binary exponentation does not work since i do not have the factors my a=2^133-1 consists of. Commented Jan 1 at 21:40