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

Question

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);
      let secret = new BigNumber(randomNumber.mul(MulConstant).add(1).floor().toPrecision(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 ?

Answer 1

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.

Answer 2

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

Link to calculator: https://www.hackmath.net/en/calculator/n-choose-k?n=1523&k=499&order=0&repeat=0

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