2
$\begingroup$

As the first step for generating a secret DH key a uniformly distributed random number $k$ must be generated, which is used to calculate the $k$-th exponent of the basepoint $A$. Depending on the group order $n$, $k$ can be between $1 \ldots n-1$ .

The binary representation length of the group order is 32 Bytes in my case, but not all bits of those $32 \cdot 8=256$ bits are used, since the group order is slightly smaller than the prime $p$, and also $p$ is smaller than $2^{256}-1$ . Therefore if I generate a 32 Byte random number $k$ , sometimes it is larger than $n$. When this happens, is it allowed to take the modulo $n$ of this number to get a new randon number

$k' = k \,\, mod \,\, n$

and use that instead? I was told to do it in that way.

First I was tempted to confirm that, but then I see that the upper end of the intervall $1 \ldots 2^{256}-1$, namely $n \ldots 2^{256}-1$ is mapped back into $1 \ldots 2^{256}-1-n$ . And therefore the distribution of random numbers for the target interval is not uniform anymore, since each representative within the interval $1 \ldots 2^{2561}-1-n$ is double-weighted - one time from the original interval and another time from the mapped back interval, so the odds for this interval are doubled as compared to numbers outside the interval. And what to do with $k'=0$, when $k=n$ ?

The other option would be to generate a random number exaktly between 1 and n-1.

Since I'm not 100% sure but this was a tip from a really experienced crypto-programmer I'm wavered between the two options...

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
3
$\begingroup$

Your analysis is correct, generating a random 32 Bytes number and reducing it modulo $n$ gives an incorrect distribution (in general). I see three natural solutions to this issue: (I'm not a programmer and do not know which one would be the most suited for efficiency)

1) Generate the random number directly between $1$ and $n-1$ as you suggested

2) Generate a random $32+\kappa$ Byes number, where $\kappa$ is a security parameter (e.g. $\kappa = 10$ for 80 bits of security), and reduce it modulo $n$. This gives a distribution statistically close to uniform over $[1, n]$

Explanation: so, you have this $256$ bit modulus $n$, and you pick (say) a random $336$ bits integer. You do not obtain a uniform distribution by reducing it modulo $n$, but "almost": let us write $2^{336} = n \times N + R$, with $R < n$ ($N,R$ are the quotient and remainder of the Euclidean division by $n$). Intuitively, if we had generated our number between $1$ and $n \times N$, we would indeed have obtained a uniform distribution when reducing it modulo $n$ (as it is a multiple of $n$). The bad case happens when the random number we generate is between $n\times N + 1$ and $2^{336}$. But this happens with probability at most $R/2^{336} < 2^{256}/2^{336} = 2^{-80}$, which is extremely unlikely. Thus, by adding some security parameter to the size of the sampled bit strings, you ensure that you'll get a distribution statistically close to uniform.

As poncho pointed out in a comment, when $n$ is already chosen very close to $2^{256}$, then there is no need to add such "security bits", taking a random 256 bits number will already give something close to uniform (my answer focused on the most general case).

3) Generate 32 Bytes integers and use rejection sampling: if a number is higher than $n$, ignore it and restart until you get a number smaller than $n$. This gives a uniform distribution over $[1,n]$ and is efficient if $n$ is very close to $2^{256}-1$

Any of those solution should be a proper fix to the problem; the direct modulo reduction seem theoretically unacceptable to me (but might be accepted on the basis that it still provides some good security level in practice, enough at least to circumvent any known attack, even though it's a bit dirty).

EDIT: the case $k'=0$ when $k=n$ that you mention is not a problem as it has a negligible probability to happen.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Actually, one could argue that (for a 256 bit curve with $p \approx 2^{256}$, say, P256), $k > n$ also has a negligible probability of occurring, at most $2^{-127}$, and hence any complexity you add to eliminate that possibility is more likely to reduce security than to increase it... $\endgroup$
    – poncho
    Oct 3, 2016 at 21:27
  • $\begingroup$ I understand 1) and 3) but not 2). In that case I generate random numbers much bigger than required. But after reduction the same mapping problem occures. I cannot see why it approximately gives uniform distribution. $\endgroup$
    – MichaelW
    Oct 3, 2016 at 21:41
  • $\begingroup$ @poncho: do I miss something? if e.g. $n = 2^{255} + 1$, you still have a $256$ bits number, but your random numbers are higher than $n$ with probability $\approx 1/2$. But yes, my answer addressed the general case of "some 256 bits modulus". If the modulus is taken extremely close to $2^{256}$, then yes, the problem happens only with negligible probability. But in this case, as I said, the third solution is the default good solution (it would always work from the first try and thus coincide with your solution). michael: I'll detail that in the post $\endgroup$
    – Geoffroy Couteau
    Oct 4, 2016 at 8:05
0
$\begingroup$

Instead of reduction modulo n you can use a multiplication by n:

  1. Select a random number k as in step 2)
  2. Multiply with n
  3. Take the upper 32 bytes as k'.

The distribution of k' has a small bias too, similar to that in the reduction case.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So, you simply suggesting the modulo that can cause the bias! $\endgroup$
    – kelalaka
    Oct 7 at 19:11

Your Answer

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

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