Tag Info

1

To expand on my comments, you need to define how $G$ is extended for inputs of different sizes before you can determine whether the resulting $G'$ are PRG or not. With the definition in your answer that $G(s_1 || s_2) = G(s_1)||G(s_2)$ it is indeed not a PRG, but you could define e.g. $G(s_1 || s_2) = G(s_1 \oplus s_2)$, in which case $G'$ is PRG. Again, ...

1

Looks good to me! My intuition is that the PRG property means "random in, random out". In 1. the input is not random so we get no guarantees - indeed, formally one could take any PRG H with 2s-bit inputs and then define G to be H except on strings where the last s bits are 0, in which case G outputs the all-zero string. Now G is still a PRG, because the ...

0

In the first case, I would say that $G'$ is not necessarily a PRG because, following from the definition of a PRG, the input seed $w = s0^{|s|}$ to $G$ is not random, so the output can't possibly be pseudorandom: the leftmost $n = |s|$ bits of $w$ correspond to a random seed $s$, but the rightmost $n$ bits are all fixed to $0$. Furthermore, the $G(x)||G(y)$ ...

4

I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths? Or is this mathematically and logically impossible? ...

1

There are many "cryptographically strong pseudorandom generators" and we know how to construct them well. If you have a strong 128-bit (or more) key $k$, then you can just use AES-CTR to get as much randomness as you need: $AES_k(0)||AES_k(1)||AES_k(2)||\cdots$. You can also do a similar thing with SHA256. The real problem that arises is where to get the key ...

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

1

If, as can be reasonably inferred from the question, a fresh random $k$ is chosen on each invocation of $G$, then $G$ is not a pseudorandom generator because it is not deterministic. (A pseudorandom generator by definition is a deterministic algorithm.) If $k$ is fixed, then more information would be needed. For example, is $k$ always the same, or is a ...

Top 50 recent answers are included