2
$\begingroup$

I'm currently writing my own implementation of Diffie-Hellma n(This isn't for actual use. This is strictly for me to get a better understanding of DH by doing it myself.)

For the prime and generator, I am using RFC 3526, more specifically the 4096-bit prime.

My question is, is there a specific standard secret integer generation for Diffie-Hellman? Since the security of the secret integers(Commonly two, but DH does support more than 1-1 communication) is pretty crucial to the security of the key exchange.

$\endgroup$
6
  • 1
    $\begingroup$ Are you looking for standards? There are already rfc listed in Wikipedia. Also, there are lots of Q/A here talk about using Sophie Germain prime $q$ used to calculate $p = 2q + 1$, $p$ is called a safe prime. $\endgroup$ – kelalaka Aug 21 '20 at 18:26
  • $\begingroup$ @kelalaka I've already got p and q figured out, like I said in my post, using RFC 3526. I'm talking the two+ private keys associated with the exchange. $\endgroup$ – Kadragon Aug 21 '20 at 21:35
  • $\begingroup$ Could you edit your question with a tittle to clarify your actual case? in DHKE both parties agree on a group and a generator. Then the secret integers are random... $\endgroup$ – kelalaka Aug 21 '20 at 21:48
  • $\begingroup$ @kelalaka The secret integers are random, but depending on the implementation you could get a secret integer of 1, which wouldn't be terribly secure. $\endgroup$ – Kadragon Aug 21 '20 at 23:05
  • 1
    $\begingroup$ There's nothing special about 1. It's just a random integer, you can make the same argument for six, or fourteen thousand six hundred and twenty five. It can be that you've thought specifically about using 1 as an exponent and it seems as though "obviously" you just get the base back and so an observer "knows" your random number was 1. But actually an observer can choose any number they expect you to pick and calculate for themselves the value that would be sent if you did. Your vulnerability here is that this adversary somehow knows your random numbers, it's not about any particular value $\endgroup$ – tialaramex Aug 22 '20 at 0:19
3
$\begingroup$

DHKE

In an exponential Diffie-Hellman, denoted by DHKE, one takes a group $G$ with a generator $g$ with its order $n$.

The Alice and Bob, during the key exchange, generates random number $a$ and $b$ in the range $a,b\in (1,n)$ and transmits $g^a$ and $g^b$ and finally, they establish the key as $g^{ab}$ then use a KDF to derive a symmetric key and IV/nonce.

There is also Elliptic Curve version of DHKE and it is denoted by ECDH and it is more used than the classical exponential version.

Prime

In DHKE, we choose prime to be a safe prime, that is $p = 2 \cdot q + 1$ with $q$ is also a prime. The $q$ is called a Sophie Germain prime.

This is a countermeasure against Pohlig-Hellman algorithm that benefits from the small factor of the $p-1$. If a safe prime is used than the factors are $2$ and $q$. Having a large factor is a countermeasure against the Pohlig-Hellman.

There is also Schnorr group with $p = r\,q + 1$. This can be considered as a generalization of the sage primes. The sage prime is optimal.

Prime Generating

The naive approach generates a prime $q$ then check for the primality of $2 \, q +1$ (Menezes: Algorithm 4.86). In pseudocode;

do
   p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)

There are faster methods

  • Double-Speed Safe Prime Generation by David Naccache, 2003

    as the title suggests, this speed this up by about a factor of two by testing both $2q + 1$ and $(q − 1)/2$ for primality.

    The idea is using the random prime $p$ as safe prime or Sophie Germain prime;

    do 
      p = randomPrime(k-bit integer)
    while ((p − 1)/2 and 2p + 1 are composite)
    
  • Safe Prime Generation with a Combined Sieve by Michael J. Wiener, 2003.

    They proposed sieving small primes up to $2^{16}$. This provides $15x$ speed up than the naive algorithm.

    The idea starts with this observation; both $q$ and $q=2p+1$ must be congruent to $2$ modulo $3$. Therefore one can eliminate the candidates with which are $0$ modulo $3$ and $1$ modulo $3$.

    This can be generalized to any odd prime $r$. Eliminate $q$'s that are conguruent to $(r-1)/2$ modulo $r$ since in this case $p$ is divisible $r$.

    Take a set $S$ all odd prime $<B$. Then $\prod_{r\in S}(r-2)/r$ of the candidates will survive the sieve.

    If $B=2^{16}$ it is estimated that it can produce $\approx \times 15$ speed up.

Collision

Now we will look at the probability of arriving the same random number if there are $k$ people using the same DHKE modulus. We are assuming that the $k$ people using the same secure (unpredictable) random number generator to generate their random keys. To simplify this, we can assume that there is one person who generates random numbers. In this case, this is completely the birthday-paradox and in Cryptography we look at this is the birthday attack to find a collision with 50%. This is a common way to look at the collision of the hash functions.

Let $H$ be the range of the random number generator, and the $p$ represents the probability we want, then $n(p; H)$ be the smallest number of values we have to choose;

$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$

In the classic hash collision case, we set $p=1/2$ and this approaches

$$n(0.5;H) \approx 1.1774 \sqrt H$$ and we usually represent as $\mathcal{O}(\sqrt{H})$

Now, let's look at some actual numbers.

  • 2048-bit prime

    Assume that $n$ is 2048-bit number, remember $n$ was the order of the generator $g$. Then

    $$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$

    With 50% probability $$n(0.5;2^{2048})\approx 2^{1204}$$

    As a result, you need to generate $2^{1204}$ random numbers to hit one again with 50%. Not feasible.

  • 4096- bit prime

    $$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$

    With 50% probability $$n(0.5;2^{4096})\approx 2^{2048}$$

    As a result, you need to generate $2^{2048}$ random numbers to hit one again with 50%. Not feasible. Pre-Compute the dlog table.


Since the modulus are pre-determined by the standards, one can argue that some organizations with superpowers built some DLog table for the modulus.

This is not a danger, too. Let assume that they can build a table up to $2^{64}$ then the probability of your random hit is $$\frac{\ell \, 2^{64}}{2^{2048}}$$ with $\ell$ try. Put the possible key generation number of your group into $\ell$. So, 2048-bit is a really big number to deal with.

$\endgroup$
2
  • $\begingroup$ pastebin.com/hPSfSY3B Is my implementation correct? Whenever I run it it takes absolutely forever just to do ga. $\endgroup$ – Kadragon Aug 25 '20 at 7:25
  • $\begingroup$ @Kadragon you can post your implementation issues on StackOverflow with the language and Cryptography tag. $\endgroup$ – kelalaka Aug 25 '20 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.