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$
5
  • 2
    $\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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 0:19

1 Answer 1

3
$\begingroup$

DHKE

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

Alice and Bob, during the key exchange, generate random numbers $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 an 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 then 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 safe primes. The safe prime is optimal.

Usually, the generator $g$ is chosen to generate order $q$ so that the Legendre Symbol of $g^a$ doesn't leak low order bit of $a$.

Prime Generating

The naive approach generates a prime $q$ then checks 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 speeds 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 at the same random number if there are $k$ people using the same DHKE modulus. We are assuming that the $k$ people use 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 as 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 a 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 is 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, 2020 at 7:25
  • $\begingroup$ @Kadragon you can post your implementation issues on StackOverflow with the language and Cryptography tag. $\endgroup$
    – kelalaka
    Aug 25, 2020 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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