Cryptography Chapter 2

Stream Cipher

A symmetric cipher that encrypts data one bit at a time using a keystream.

Why it matters:
This is the main topic of Chapter 2.

Example:

yi=xi⊕siy_i=x_i\oplus s_i

Common confusion:
The keystream is not necessarily the secret key itself.

Keystream

Simple definition:
A sequence of bits combined with plaintext using XOR.

Why it matters:
The security of a stream cipher depends heavily on the keystream.

Example:

Plaintext:

101101101101

Keystream:

011010011010

Ciphertext:

110111110111

Your professor explicitly emphasized that stream-cipher security relies on the keystream.

XOR

Simple definition:
A bitwise operation that outputs 1 when the two input bits are different.

0⊕0=00\oplus0=00⊕1=10\oplus1=11⊕0=11\oplus0=11⊕1=01\oplus1=0

Why it matters:
XOR is the encryption/decryption operation used throughout the chapter.

Common confusion:
XOR is equivalent to addition modulo 2.

TRNG — True Random Number Generator

Simple definition:
Produces random values from a physical process.

Why it matters:
Used when actual unpredictability from physical randomness is needed.

Examples from lecture:

• coin toss

• radioactive decay

• Brownian motion

The slides emphasize that TRNG output cannot be predicted or reproduced.

PRNG — Pseudorandom Number Generator

Simple definition:
A deterministic algorithm that generates a sequence from an initial seed.

Why it matters:
It can look random without actually being unpredictable.

Example:

si+1=f(si)s_{i+1}=f(s_i)

or more generally:

si+1=f(si,si−1,…)s_{i+1}=f(s_i,s_{i-1},\ldots)

Common confusion:
“Looks random” does not mean “secure for cryptography.”

CSPRNG — Cryptographically Secure Pseudorandom Number Generator

Simple definition:
A PRNG whose future output is computationally infeasible to predict.

Why it matters:
This is what cryptography really needs.

The professor’s slide gives the key condition: knowing previous output should not allow an efficient algorithm to predict the next bit with probability better than 50%50\%.

One-Time Pad

Simple definition:
A stream cipher using a truly random keystream that is as long as the message and never reused.

Why it matters:
It gives unconditional security.

Common confusion:
It is secure only if the random key material is genuinely random and used only once.

Computational Security

Simple definition:
A system is considered secure when breaking it requires too much computation.

Why it matters:
Practical stream ciphers generally aim for computational security, not unconditional security.

The lecture slide defines it in terms of the best known attack requiring at least tt operations.

LFSR — Linear Feedback Shift Register

Simple definition:
A sequence generator made from flip-flops and XOR feedback.

Why it matters:
It is fast and hardware-efficient, but a plain LFSR is predictable.

Common confusion:
Good statistical properties do not make an LFSR cryptographically secure.

Degree of an LFSR

Simple definition:
The number of flip-flops in the LFSR.

If there are 3 flip-flops:

degree=3

Period / Sequence Length

Simple definition:
The number of generated states or output bits before the pattern repeats.

For a degree-mm LFSR:

maximum period=2^m−1

Characteristic Polynomial

Simple definition:
A polynomial representation of the LFSR feedback rule.

For the lecture example:

si=si−2⊕si−3s_i=s_{i-2}\oplus s_{i-3}

corresponds to:

p(x)=x3+x+1p(x)=x^3+x+1

Why it matters:
It gives a mathematical way to analyze LFSR behavior.

Known-Plaintext Attack

Simple definition:
An attack where the attacker knows some plaintext and its corresponding ciphertext.

For a stream cipher:

yi=xi⊕siy_i=x_i\oplus s_i

so:

si=xi⊕yi\boxed{s_i=x_i\oplus y_i}

That reveals keystream bits.

Berlekamp–Massey Algorithm

Simple definition:
An algorithm that can reconstruct the shortest LFSR capable of producing an observed bit sequence.

Why it matters:
It shows why plain LFSRs are cryptographically weak.

Your professor emphasized the rule of thumb that roughly 2m2m output bits can recover a degree-mm LFSR.

Linear

Simple definition:
Built using operations that behave like linear equations.

In this chapter, XOR corresponds to addition modulo 2, so XOR-only LFSRs are linear.

Nonlinear

Simple definition:
Contains operations such as multiplication of bits.

In hardware, an AND gate behaves like bit multiplication:

xyxy

This breaks the simple linear structure.

Trivium

Simple definition:
A modern stream cipher built using multiple shift-register structures and nonlinear operations.

Why it matters:
It shows how designers keep the speed of shift registers while making analysis much harder.

The professor’s slide highlights 288 registers, 3 AND gates, and 7 XOR gates.