# Tag Info

2

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 ...

7

It is not accurate to say that the keystream from AES-CTR is a pseudorandom function. However, it is a pseudorandom generator. Furthermore, the construction that you gave is close to working but it's unclear where the key fits in. I will therefore elaborate on what we can exactly say. Let $F$ be a pseudorandom function, and for simplicity assume that the ...

-1

If $f$ is a block cipher, it 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.) Since you consider the CTR mode as mapping a nonce to a keystream generated with that nonce, that is a pseudorandom function. The concatenate ...

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 ...

Top 50 recent answers are included