# Is this simple PRNG secure?

$G$ is a PRNG used in a stream cipher and defined in the following way:

1. G receives $s_0$ as an input, which is a random string drawn from a uniform distribution.

2. The output of step $i$ is $s_i = (s_{i-1}\cdot (N+1) + 1) \bmod{N}$, for $i=1,2,3\dots$

Is this PRNG secure? If not, what is the distinguisher?

• Hint: Try choosing some $s_0$ and compute a few elements of the generated sequence. – yyyyyyy Apr 30 '16 at 12:00
• Part of the problem is I didn't manage to understand what is the output of $s_0(N+1)$... Thought it was a function, not simple multiplication. Thank's to Vitor I see through my stupidity ;9 – Jjang Apr 30 '16 at 16:59

$s_i = s_{i-1}\cdot(N + 1) + 1 = s_{i-1} \cdot N + s_{i-1} + 1$

but $s_{i-1} \cdot N = 0 \pmod N$, so

$s_i = s_{i-1} + 1 \pmod N$

which means you can discover the next number to be generated just looking to the current one...

• Thanks. For some reason I thought $s_i(N+1)$ was passing N+1 as a parameter for $s_i$, but it's a string, so I was confused. Now that I see that it's simple multiplication... oh well. Thanks :) – Jjang Apr 30 '16 at 17:00

However, for any PRNG of the form $s_{i+1} = F(s_{i})$, where the attacker sees the $s_i$ values, and knows $F$, then he can distinguish it. Given a sequence of values $r_1, r_2, ...$, he can determine whether it was generated by that PRNG by checking if $r_2 = F(r_1)$; this is always true for the real PRNG, and rarely true for a random stream.
• Have $F$ include some secret information (so that the attacker cannot compute it), or
• Some function $G$ that disguises the state; so that while the internal state updates are of the form $s_{i+1} = F(s_i)$, the outputs that the attacker sees are actually $G(s_{i+1})$