Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I have a cryptographically secured RNG that uses a recommended block cipher to generate the random number. As its output, I receive the random number which is very large, but the application requires the usage of two random numbers, and both of them with smaller bit-size of the RNG output.
Can I split the random number into two smaller vectors and consider them as two random numbers? Is this a recommended practice?
Yes you can.
Suppose that you have a pseudorandom generator that, on some seed $s$, outputs $n$ pseudorandom bits, where $n$ is even. Then on a uniformly random input seed $s$, prg$(s) = r$ can be written $r_1 + 2^{n/2}r_2$, with $(r_1,r_2) \in (\{0,1\}^{n/2})^2$. I claim that both $r_1$ and $r_2$ are computationally indistinguishable from uniformly random elements from $\{0,1\}^{n/2}$.
The intuition behind this is as follows: suppose toward contradiction that some polynomial size algorithm can distinguish $r_1$ from random, when $r_1$ is computed as the $n/2$ least significant bits of prg$(s) = r$, for a uniformly random $s$. Now, you are given an $n$-bit string $r$ and must tell whether it is random or it is the output of the PRG. Just decompose $r = r_1 + 2^{n/2}r_2$, and run your distinguisher on input $r_1$: if it tells you that $r_1$ is non-random, then $r$ is non-random (as the distribution of uniformly random $n$-bit numbers is perfectly equal to the distribution obtained by picking two uniformly random $n/2$-bit numbers $r_1,r_2$ and computing $r$ as $r_1 + 2^{n/2}r_2$), hence you can distinguish outputs of the PRG on random seeds from random $n$-bit values, contradicting the fact that the PRG is cryptographically secure. The same argument shows that $r_2$ cannot be distinguished from random.
More generally, fix any size-$k$ subset $S$ of $\{1, \cdots, n\}$, for some $k \leq n$; a similar argument shows that the $k$-bit string obtained by running a secure prg on a random seed, and taking the $k$ bits of the output indexed by $S$, is computationally indistinguishable from random (and the distinguishing advantage of any polytime adversary is at most equal to its distinguishing advantage against the PRG). You can have a bunch of random-looking bit strings just by considering any partition of the bits of your PRG output.
