I'm reading Understanding Cryptography by Christof Paar and Jan Pelzl. In chapter 2 (Stream Ciphers). There is a section talking about "Bulding Key Streams from PRNGs".
They assume a PRNG based on the linear congruential generator:
$$S_0 = seed $$
$$S_{i+1} \equiv AS_i + B\mod m, i=0,1,...$$
where we choose m to be 100 bits long and $ S_i,A,B \in \{0,1,...,m-1\}. $ Note that this
PRNG can have excellent statistical properties if we choose the parameters carefully.
The modulus m is part of the encryption scheme and is publicly known. The secret
key comprises the values (A,B) and possibly the seed S0, each with a length of 100.
That gives us a key length of 200 bit, which is more than sufficient to protect against
a brute-force attack. Since this is a stream cipher, Alice can encrypt:
$$y_i \equiv x_i + s_i \mod 2 $$
where $s_i$ are the bits of the binary representation of the PRNG output symbols $S_j$
But Oscar can easily launch an attack. Assume he knows the first 300 bits of
plaintext (this is only 300/8=37.5 byte), e.g., file header information, or he guesses
part of the plaintext. Since he certainly knows the ciphertext, he can now compute
the first 300 bits of key stream as:
$$s_i \equiv y_i + x_i \mod m , i = 1,2,...,300$$
These 300 bits immediately give the first three output symbols of the PRNG:$S_1 = (s_1,...,s_{100}), S_2 = (s_{101},...,s_{200})$ and $S_3 = (s_{201},...,s_{300}).$
(emphasis mine)
My questions are:
- What is an output symbol ?
- how we determine the output symbols (# of bits, etc)
