Tag Info

1

Any PRNG with a finite state size is eventually periodic. The maximum period possible is $2^n$ for an $n$-bit state, but the average with a well mixed state is $2^{n/2}$. Here the hash function used is SHA-512, but the state is 1024 bits. A first guess would be a period of $2^{512}$, rather than the $2^{256}$ mephisto gives. Let's look at the cycles. Both ...

1

Yes, this PRG is theoretically periodic. Approximately after generating $2^{512}$ outputs a state will be generated that collides with a previous state. (A previous version of this answer said $2^{256}$ as I missed that two outputs are used for the state. Otus answer pointed out this mistake.) This follows from the birthday problem. However, $2^{512}$ is ...

3

No, it cannot. The keystream from AES-CTR is a pseudorandom generator but not a pseudorandom function. But I think that this may be what you actually meant.

-1

A block cipher is meant to be a PRP, not a PRF. However, the two are indistinguishable until about half the bit length, i.e. $2^{64}$ blocks for a 128-bit cipher like AES. (That's hundreds of exabytes.) So if you consider CTR mode as mapping a nonce to a keystream, that is a pseudorandom function as long as you don't use the same key for a ridiculous amount ...

4

Yo are taking only the one-to-one functions, while there are a lot of other functions, to name a few: 00 00 01 00 10 00 11 00 00 01 01 01 10 01 11 01 00 00 01 00 10 01 11 01 as you already mentioned, each table can be represented with $n*2^n$ bits, i.e. strings from the set: $\{0,1\}^{n*2^n}$, each string from this set defines one function ...

-1

Pseudorandom functions just have to produce 'random' values, there are no special restrictions on the functions. There are tests to measure the quality of random functions. These tests will try to detect if the outputs of a function are somehow correlated or biased. A well-known test battery are the Diehard Tests from George Marsaglia. Or you have more ...

1

fkraiem's answer is basically correct, but it only says that $G$ does not match the "syntax" of a PRG. But this is not entirely satisfactory for understanding what's really wrong with $G$ as a PRG. In addition, $G$ may not be pseudorandom. For example, it could be the case that $F_{00\cdots 0}(x) = 0$ for every $x$, i.e., the all-zeros key is a "weak" key ...

1

Because the key-, input- and output-length of $F$ are equal, if the length of the seed $x$ is $n$, there are $2^n$ keys and so $G$ must compute $F$ $2^n$ times and output a string of length $n\cdot 2^n$. Hence, $G$ runs in time exponential in $n$, which means it can't be a pseudorandom generator because a pseudorandom generator is a deterministic ...

Top 50 recent answers are included