2
$\begingroup$

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)
$\endgroup$

1 Answer 1

2
$\begingroup$

What is an output symbol ?

An output symbol is the base "unit" of output of a PRNG. The keystream itself is composed of an integer number of symbols. If the PRNG outputs bits (like an LFSR), then the symbol is a single bit. If the PRNG outputs octets (like RC4), then the symbol is an integer in the range $[0,255]$.

how we determine the output symbols (# of bits, etc)

If you have $n$ possible symbols, then a single symbol is described by $\log_2(n)$ bits. Generally, the number of output symbols for a PRNG are a power of two. This might not always be the case. If a PRNG outputted alphanumeric symbols with 26 different possibilities, then each symbol would hold $\log_2(26) \approx 4.7$ bits of information. It would probably be better to represent such a symbol as an integer in the range $[0,26]$ rather than representing it as a fractional number of bits.

The example PRNG in the question specified the symbol $S_i \in \{0,1,\dots m-1\}$ and additionally specified $m=100$. This means that the symbol for that PRNG is a 100-bit value, although it could also be represented as a single integer in the range $[0,2^{100})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.