1
$\begingroup$

If I get a random number from a cryptographically secure random number generator then divide it by a number, say 2, is it still cryptographically secure?

$\endgroup$
3
$\begingroup$

It does not lower the security at all - at most, it changes the output space. If your output space is, say, the integers between $-100$ and $100$, then computing PRG$(s)/2$ for a random seed $s$ gives a value indistinguishable from a random value in the set $\{-50, -49.5, \cdots, 49.5,50\}$. Depending on which output space you consider and what you exactly mean by "dividing by 2", it can even remain a cryptographically strong PRG with the same output space: if your output space is, say, the field $\mathbb{F}_p$ with $p$ prime, then computing PRG$(s)$ and multiplying the output by $2^{-1} \bmod p$ gives a value indistinguishable from random in $\mathbb{F}_p$.

This follows immediatly from the security of the original PRG: since division by 2 is a reversible operation, any distinguishing attack on the new PRG trivially translates into a distinguishing attack against the original PRG.

| improve this answer | |
$\endgroup$
  • $\begingroup$ @dkimot 's random example was 2. What if he'd picked 3 instead? I know that it doesn't divide cleanly. So what then? $\endgroup$ – Paul Uszak Jul 24 '17 at 11:57
  • $\begingroup$ Note that your answer implicitly assumes that the OP keeps the exact rational number resulting from the division, and can somehow use this rational number in their cryptographic scheme without rounding / truncating it to an integer or otherwise mangling it in any irreversible way. Off the top of my head, I can't think of many cryptographic schemes that would accept e.g. $37\frac23$ as a key. If, as I suspect, the OP is instead thinking of using truncating integer division, then the truncation does lose some entropy. $\endgroup$ – Ilmari Karonen Aug 6 '19 at 12:31
1
$\begingroup$

I would argue that if your key was cryptographically-secure and derived from a large enough space such as ${2^{128}}$, and the constant that was being used to divide was also sufficiently large, such as factorial 33!, then an attacker who knew that you were using that divisor could help speed their search and thus reduce the security of your key by a few bits (not sure how many, perhaps ${2^{125}}$ in the above example, which is the length in bits of factorial 33).

Otherwise, dividing such a large number by such a tiny integer such as 2 would have a negligible effect and likely still remain secure, compared to dividing by a non-negligible number, depending on how large the constant is.

P.S. I didn't argue indistinguishability given that the question assumes a CSPRNG is used, but instead whether the constant used is reducing the security in bits of the random number.

| improve this answer | |
$\endgroup$

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.