Is a large random number cryptographically equivalent to the product of multiple smaller ones?

Question

Say I create a 256-bit key by taking a random number between $0$ and $2^{256}-1$.

Would it be cryptographically equivalent to generate $8$ numbers $r_1\dots r_8$ between $0$ and $31$, and combining them in the following way?

$$\mathit{rand} = 2^{r_1} \cdot 2^{r_2} \cdot 2^{r_3} \cdot 2^{r_4} \cdot 2^{r_5} \cdot 2^{r_6} \cdot 2^{r_7} \cdot 2^{r_8}$$

It would still add up to 256th power, but would it be secure of generating it this way? If not, then how to do it, how to generate big random number by combining smaller ones?

Answer 1

If you choose a number uniformly at random in the range $[0, 31]$, that's $32$ distinct values and thus $log_2(32) = 5$ bits of entropy. If you choose $8$ such numbers, then you have $5 \times 8 = 40$ bits of entropy total, meaning that there are $2^{40}$ distinct combinations you could get. It doesn't matter how you combine them, that's already far short of $2^{256}$.

And it gets worse, because you're multiplying numbers that you compute from your eight choices:

$$\mathit{rand} = 2^{r_1}\cdot 2^{r_2}\cdot 2^{r_3}\cdot 2^{r_4}\cdot 2^{r_5}\cdot 2^{r_6}\cdot 2^{r_7}\cdot 2^{r_8} $$

Since multiplication is commutative ($a \times b = b \times a$) and associative ($a \times (b \times c) = (a \times b) \times c$), it means that many combinations among those $2^{40}$ distinct choices actually yield the same product after the multiplication. E.g., if two sequences of random choices are permutations of each other their product is the same. In this case, it is even worse, since $\mathit{rand}=2^{r_1+\dots+r_8}$ is always a power of two: This means we are effectively sampling a $256$-bit number that has exactly one bit set, so there's only $256=2^8$ possible outcomes!

If not, then how to do it, how to generate big random number by combining it from smaller ones?

Basically, by choosing digits at random in some base. If you have $n$ randomly drawn digits $d_0, ..., d_{n-1}$ in base $b$, then $d_0b^0 + ... + d_{n-1}b^{n-1}$ is a uniform random number in the range $[0, b^n)$. For example, to generate a 256-bit number at random, you could:

• Choose 256 individual bits at random ($n = 256$, $b = 2$);
• Choose 32 bytes at random ($n = 32$, $b = 8$);
• Choose eight 32-bit machines words at random ($n = 8$, $b = 32$);
• Choose four 64-bit machines words at random ($n = 4$, $b = 64$).

In practice, this is done by just concatenating randomly chosen bytes or machine words.

Answer 2

No, that is not equivalent. By multiplying many small random numbers you can only get smooth numbers. You can never get large primes, for example.

Instead, you can add them together like $x_0 + x_1 n + x_2 n^2 + \dots$

That is, you multiply each by the size $n$, for numbers between $0$ and $n-1$, raised to a larger and larger power. (Equivalently, if $n$ is a power of two you can just concatenate the binary representations.)

Answer 3

This depends on the unknown internal state of the generator. If you seed RC4 with one byte (the key) and generate eight bytes, it only has one byte of security.

If you use SHA-1 with a 512-bit key, hashing a counter, it will only have 160-bits of security, because the unknown internal state of the function is only 160-bits (the chaining value).

For AES-256, it has a secret internal state of 256-bits (the key).

There has been a large body of literature on random number generation, but your question isn't directly related to any of them.

To directly answer your question, a number between 1 and 32 is a 6-bit value. Usually people concatenate bit values to form a key. There is also a bias, none of those numbers include zero or the values between 33 and 63.