Random Numbers & PRNGs
Cryptography leans on random numbers everywhere: authentication protocols (to stop replay attacks), temporary session keys, public-key generation, and stream-cipher keys. For all of these uses, the numbers must be:
Statistically random
Uniform distribution across the possible values, with no dependency between successive values.
Unpredictable
You cannot predict future values even if you know all previous values in the sequence.
"True" random sequences (e.g. from physical noise sources) satisfy both properties naturally, but they're slow and hard to reproduce. In practice, systems use Pseudorandom Number Generators (PRNGs) — deterministic algorithms that produce sequences which look random and pass statistical randomness tests, without actually being truly random. Because a PRNG is a deterministic function of a seed/key, care is needed: if the seed is guessable or reused, the "randomness" collapses.
True random vs pseudorandom
True random numbers come from unpredictable physical processes (thermal noise, radioactive decay). Pseudorandom numbers come from an algorithm + a seed — reproducible if you know the seed, which is exactly why the seed/key must stay secret.
Stream Cipher Structure & Properties
A stream cipher processes plaintext one bit (or byte) at a time: it generates a pseudorandom keystream from the key, then XORs that keystream with the plaintext, bit by bit.
Why key reuse breaks everything
If C1 = P1 ⊕ K and C2 = P2 ⊕ K, then C1 ⊕ C2 = P1 ⊕ P2 — the keystream cancels out entirely, leaking a relationship between the two plaintexts that statistical/language analysis can crack.
RC4 — Overview
RC4 is the classic example of a stream cipher covered in this chapter.
RC4 Key Schedule Algorithm (KSA)
RC4 keeps an internal state array S of 256 numbers (0…255). The KSA scrambles S using the key before any encryption happens.
Initialize S
S[i] = i for i = 0…255 (identity permutation to start).
Build T from the key
T[i] = K[i mod keylen] — the key is repeated cyclically to fill all 256 slots.
Scramble S with j
For each i, update j using S[i] and T[i], then swap S[i] and S[j]. After all 256 iterations, S is a key-dependent random permutation.
Mnemonic — RC4 KSA
"Start plain, Tag with key, Jumble with j" — S Starts as 0…255 plain, T Tags each slot with a repeated key byte, then j Jumbles S by swapping pairs 256 times. That's the whole KSA in three verbs.
RC4 Encryption — The PRGA
Once S is scrambled, encryption continues shuffling the array to generate a fresh keystream byte for every message byte.
In words: bump i, use S[i] to update j, swap those two entries, then add S[i]+S[j] together to pick t — the index of the actual keystream byte. XOR S[t] with the next plaintext byte to get ciphertext (and the same operation in reverse to decrypt, since XOR is its own inverse).
Mnemonic — RC4 PRGA
"i steps, j chases, swap, sum, XOR" — i steps forward by 1, j chases by adding S[i], you swap S[i] and S[j], sum them to get t, then XOR S[t] with the plaintext byte. Five words, five actions, one keystream byte produced.
RC4 Example — Simplified 3-bit Version
To make the algorithm tractable by hand, the slides shrink RC4 down: instead of a 256-byte state, use 8 × 3-bit values (S can hold 0–7).
Key K = [1, 2, 3, 6]. Plaintext P = [1, 2, 2, 2].
Step 1 — Generate the stream: initialize S so S[i] = i, and T so it holds the key repeated as necessary:
Then perform the initial permutation (the KSA scramble described in Section 04, run with N=8 instead of 256) to scramble S using the key.
Running the simplified RC4 stream cipher on plaintext P = [1 2 2 2] with key K = [1 2 3 6] produces ciphertext:
The point of the shrunk example
The 8×3-bit toy version exists purely so you can trace the KSA and PRGA by hand on an exam without doing 256 iterations. The logic is identical to real RC4 — only N (256 → 8) and the byte width (8 bits → 3 bits) change.
RC4 Security
Claimed secure
RC4 is claimed secure against known attacks — there has been analysis, but nothing considered practically exploitable against the core algorithm itself.
Never reuse a key
As a stream cipher, RC4 must never reuse the same key (see Section 02's golden rule).
The WEP lesson
WEP's real-world weakness was not a flaw in RC4 the algorithm — it was in how WEP generated the per-packet keys fed into RC4 (short, reused/predictable IVs). The lesson: a cipher can be sound while its surrounding key-management protocol is broken.
Modes of Operation — Why We Need Them
Block ciphers (like DES: 64-bit blocks, 56-bit key) only know how to encrypt one fixed-size block at a time. Real messages are arbitrary length — e.g. 1000 bytes — so we need a systematic way to chain many block encryptions together. NIST SP 800-38A defines 5 standard modes, covering both block-oriented and stream-oriented use cases, and any of them can be used with any block cipher.
Message padding
The last block of a message is often shorter than the cipher's block size. Options: pad with a known non-data value (e.g. nulls), or pad the last block plus a count of the pad size (e.g. [b1 b2 b3 0 0 0 0 5] means 3 real data bytes + 5 bytes of pad+count). Padding may require an entire extra block. Some modes (the stream modes below) avoid this problem entirely.
Electronic Codebook (ECB)
The message is broken into independent blocks, each encrypted with the same key: Ci = EK(Pi). Each block is essentially "looked up" like a codebook entry — hence the name — and each block is encoded completely independently of every other block.
ECB's big weakness
Repeated plaintext blocks produce identical ciphertext blocks (if aligned to block boundaries) — a serious problem for data like graphics or messages that barely change, since patterns leak straight through ("codebook analysis"). ECB is really only suitable for encrypting a few independent values, e.g. a session key.
Cipher Block Chaining (CBC)
Each ciphertext block is chained into the next plaintext block before encryption, so blocks are no longer independent:
Used for: bulk data encryption, authentication.
Strength
Because each ciphertext block depends on every block before it, any change to a block affects all following ciphertext blocks — a useful integrity side-effect.
IV handling matters
The IV must be known to both sender and receiver. If sent in the clear, an attacker can flip bits of the first plaintext block and adjust the IV to compensate. Fix: either use a fixed IV (as in EFTPOS) or send the IV encrypted in ECB mode before the rest of the message.
Stream Modes of Operation — Turning a Block Cipher into a PRNG
Sometimes we need to operate on units smaller than a full block (e.g. real-time data). The stream modes convert a block cipher into a stream cipher by using it as a pseudorandom number generator:
- Cipher Feedback (CFB)
- Output Feedback (OFB)
- Counter (CTR)
Cipher Feedback (CFB)
The message is treated as a stream of bits added to the output of the block cipher; the result is fed back for the next stage (hence "feedback").
The standard allows feeding back any number of bits (1, 8, 64, 128…), denoted CFB-1, CFB-8, CFB-64, CFB-128. It's most efficient to feed back the full block width (64 or 128 bits). Used for: stream data encryption, authentication.
Error propagation
CFB is appropriate when data arrives in bits/bytes and is the most common stream mode, but errors propagate for several blocks after the point of error.
Output Feedback (OFB)
The message is treated as a stream of bits; the output of the cipher is XORed with the message, and that output is then fed back for the next stage — but the feedback path is independent of the message, so it can be computed in advance.
Used for: stream encryption on noisy channels.
Bit errors in transmission do not propagate — a corrupted ciphertext bit only corrupts the corresponding plaintext bit.
Needs an IV unique for every use (reuse lets an attacker recover outputs). More vulnerable to message stream modification. Sender/receiver must stay in sync. Research shows only full block feedback (CFB-64/128 style) should ever be used.
Counter (CTR)
A "new" mode (though proposed early on), similar to OFB but it encrypts a counter value rather than a feedback chain:
Must use a different key & counter value for every plaintext block — never reused. Used for: high-speed network encryption.
Efficiency
- Can do parallel encryption in hardware or software
- Can pre-process keystream in advance
- Supports random-access processing of blocks
Caveats
Provably as secure as the other modes, but you must never reuse a key/counter combination, or security can break down (same failure mode as OFB key/IV reuse).
Mnemonic — The 5 NIST Modes
"Every Cook Bakes Cakes Fresh, Overnight, Constantly Tracked, Really" → shorten to ECB, CBC, CFB, OFB, CTR — "Each Cipher Block Craves Order, Constantly Ticking." Order to remember: block modes first (ECB, CBC), then stream modes (CFB, OFB, CTR) which turn a block cipher into a keystream generator.
Modes Side-by-Side
| Mode | Formula | Errors Propagate? | Typical Use |
|---|---|---|---|
| ECB | Ci = EK(Pi) | No (blocks independent) | Single values, e.g. session keys |
| CBC | Ci = EK(Pi ⊕ Ci-1) | Yes — all following blocks | Bulk data, authentication |
| CFB | Ci = Pi ⊕ EK(Ci-1) | Yes — several blocks | Stream data, authentication |
| OFB | Ci = Pi ⊕ Oi, Oi = EK(Oi-1) | No (bit errors stay local) | Noisy channels |
| CTR | Ci = Pi ⊕ EK(i) | No | High-speed network encryption |
Exam Tips & Tricks
RC4 = 2 algorithms
KSA (Key Scheduling Algorithm) scrambles S using the key. PRGA (Pseudo-Random Generation Algorithm) uses the scrambled S to produce the keystream byte-by-byte. Don't confuse them.
RC4 state size
Real RC4: S has 256 entries (bytes 0–255). The exam's toy example shrinks this to 8 entries (3-bit values) — same logic, smaller numbers.
Golden rule of stream ciphers
Never reuse a key/keystream. This single fact explains the real-world WEP weakness and is a favorite exam trap.
ECB is the "bad" mode
If an exam question shows a picture with repeating patterns leaking through ciphertext, the answer is always ECB.
CBC needs an IV — protect it
Sending the IV in the clear + unencrypted allows bit-flipping attacks on the first block. Either fix the IV or encrypt it (in ECB) before sending.
Which modes resist bit-error propagation?
OFB and CTR — because feedback/counter values don't depend on the ciphertext itself. CBC and CFB propagate errors forward.
Quick Reference — Everything at a Glance
| Topic | Key Point |
|---|---|
| PRNG | Deterministic algorithm producing numbers that pass randomness tests but aren't truly random |
| Random number requirements | Statistically random (uniform, independent) + unpredictable |
| Stream cipher | Encrypts bit/byte by bit/byte by XORing with a pseudorandom keystream |
| Golden rule | Never reuse the same key/keystream in a stream cipher |
| RC4 origin | Ron Rivest design, owned by RSA DSI; variable key, byte-oriented |
| RC4 KSA | Scrambles the 256-entry state array S using the key (via T and swaps) |
| RC4 PRGA | i steps by 1, j += S[i], swap S[i]/S[j], t = S[i]+S[j], keystream byte = S[t] |
| RC4 example | K=[1,2,3,6], P=[1,2,2,2] → C=[4,1,2,0] (toy 8×3-bit version) |
| RC4 real-world weakness | WEP's flawed key generation for RC4, not RC4 itself |
| Why modes exist | Block ciphers only encrypt one fixed block; modes handle arbitrary-length messages |
| Padding | Pad last short block with nulls, or with data+count of pad bytes |
| ECB | Ci = EK(Pi); blocks independent; leaks repeated patterns |
| CBC | Ci = EK(Pi⊕Ci-1); needs IV; errors propagate forward |
| CFB | Ci = Pi⊕EK(Ci-1); converts block cipher to stream mode; errors propagate |
| OFB | Ci = Pi⊕Oi, Oi=EK(Oi-1); feedback independent of message; bit errors don't propagate |
| CTR | Ci = Pi⊕EK(i); encrypts counter; parallelizable, no error propagation |
| NIST standard | SP 800-38A defines 5 modes (ECB, CBC, CFB, OFB, CTR) |
| Modes needing unique IV/counter every time | OFB and CTR — reuse breaks security |