Study sheet: Affine and Stream Ciphers

📋 Course Outline

1. Cryptology and Symmetric Cryptography
2. Cryptanalysis and Key Security
3. Modular Arithmetic and Historical Ciphers
4. Affine Cipher
5. Security and Cryptography Foundations
6. Stream Cipher Principles
7. Randomness and One-Time Pads
8. LFSR Structure and Attacks
9. Practical Stream Cipher Constructions
10. Trivium Design and Operation
11. Trivium Security and Stream Cipher Context
12. DES Architecture and Core Principles
13. DES Key Schedule and Decryption
14. Security and Attacks on DES
15. DES Alternatives and PRESENT
16. AES Design and Overview
17. Finite and Galois Fields
18. AES Internal Structure

📖 1. Cryptology and Symmetric Cryptography

🔑 Key Concepts & Definitions

• Cryptology : the general field that includes cryptography and cryptanalysis
• Cryptographic Protocols : use cryptographic algorithms as building blocks to realize more complex security functions, such as TLS for secure web communication
• Plaintext : also called cleartext, is the original readable message before encryption

📝 Essential Points

📌 Cryptography secures communication against an adversary, whereas cryptanalysis studies how to break cryptosystems.

📌 Symmetric algorithms use one shared secret key for encryption and decryption, whereas asymmetric algorithms use a private key and a public key.

• In a symmetric cryptosystem, Alice encrypts plaintext x with key k to produce ciphertext y, and Bob decrypts y with the same key to recover x.

💡 Memory Hook

Cryptography secures communication, whereas cryptanalysis breaks cryptosystems.

📖 2. Cryptanalysis and Key Security

★ Must-know

📌 A brute-force attack treats a cipher as a black box and tests all possible keys, whereas an analytical attack exploits the internal structure of the cipher.

• A brute-force attack checks every key in the key space by decrypting ciphertext y and testing whether the result matches known plaintext x.

• Letter-frequency analysis can exploit:

  • Single-letter frequencies
  • Pairs, triples, or larger groups of symbols
  • Frequent short words when word separators are available

📌 Kerckhoffs’ Principle states that a cryptosystem should remain secure even when the attacker knows all system details except the secret key. — Auguste Kerckhoffs, 1883

• The stated symmetric-key security estimates are:
  • 56–64 bits for short-term security lasting a few hours or days
  • 112–128 bits for long-term security lasting several decades without quantum computers
  • 256 bits for long-term security lasting several decades even with currently known quantum algorithms

Further detail

• The substitution cipher has a key space of 26! and therefore approximately 2^88 possible keys.

💡 Memory Hook

Ciphertext-only → known-plaintext → chosen-plaintext → chosen-ciphertext

📖 3. Modular Arithmetic and Historical Ciphers

🔑 Key Concepts & Definitions

• Modulo Operation : for integers a, r, and positive m, the relation a ≡ r mod m holds when m divides a − r, with m called the modulus and r called a remainder
• Integer Ring : the set {0, 1, …, m − 1} with addition and multiplication performed modulo m

★ Must-know

📐 Formula — Every integer a can be written as $a=q\cdot m+r$ with $0\le r<m$, which gives $a\equiv r\pmod m$.

📌 An element a in Z_m has a multiplicative inverse if and only if gcd(a,m)=1, meaning that a and m are coprime.

📐 Formula — The shift cipher encrypts and decrypts letters represented in Z_26 using $e_k(x)\equiv x+k\pmod{26}$ and $d_k(y)\equiv y-k\pmod{26}$.

📐 Formula — The affine cipher encrypts with $y\equiv a\cdot x+b\pmod{26}$ and decrypts with $x\equiv a^{-1}\cdot(y-b)\pmod{26}$, subject to $gcd(a,26)=1$.

Further detail

• The affine cipher has 312 possible keys because its key space contains 12 valid values for a and 26 values for b.

💡 Memory Hook

A clock whose numbers wrap around illustrates modular arithmetic.

📖 4. Affine Cipher

🔑 Key Concepts & Definitions

• Affine Cipher : Encrypts a value x as $y \equiv a \cdot x + b \pmod{26}$ and decrypts it as $x \equiv a^{-1} \cdot (y-b) \pmod{26}$ using the key k=(a,b), where $\gcd(a,26)=1$.

★ Must-know

• The affine cipher has 12 possible values for a and 26 possible values for b, giving a key space of 312 keys.

📌 The affine cipher is vulnerable to exhaustive search and letter-frequency analysis because its key space is small and its plaintext-to-ciphertext letter mapping is fixed.

Further detail

• The valid multiplier values for the affine cipher modulo 26 are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25.

• To find the multiplicative inverse of a, test possible values until $a \cdot a^{-1} \equiv 1 \pmod{26}$; for example, the inverse of 3 is 9 because $3\cdot9=27\equiv1\pmod{26}$.

• With key k=(9,13), the plaintext ATTACK, represented as 0,19,19,0,2,10, encrypts to the ciphertext nccnfz, represented as 13,2,2,13,5,25, and the inverse of 9 is 3.

💡 Memory Hook

Multiplication plus addition produces the affine substitution.

📖 5. Security and Cryptography Foundations

🔑 Key Concepts & Definitions

• Provable Security : Means providing an algorithmic description, a precise security model defining the adversary’s capacities and goal, and a mathematical proof that the scheme meets its security goal under a stated cryptographic hardness assumption.
• Multiparty Computation : Multiparty computation allows several parties to provide inputs and jointly compute a function while learning only their own input and the result, not the other participants’ inputs.

★ Must-know

📌 Cryptography, IT security, and cybersecurity protect information systems against malicious human actors, whereas technical safety and reliability primarily address random technical failures during normal operation.

• The traditional CIA triad consists of:

  • confidentiality
  • integrity
  • availability

• 🔄 A systematic IT-security approach proceeds by: defining assets and security needs, evaluating attack potential and possible attack paths, specifying adequate countermeasures

• Kerckhoffs’ Principle states that the design of a cryptographic system should not require secrecy and that compromising the system should not inconvenience the correspondents. — Auguste Kerckhoffs, 1883

Further detail

• Gentry proposed the first fully homomorphic encryption scheme in 2009, based on lattices.

• General secret sharing requires at least t of n participants to collaborate to reconstruct or compute a secret, and it was proposed independently by Shamir and Blakley in 1979.

💡 Memory Hook

Security protects against attackers, whereas safety addresses random technical failures.

📖 6. Stream Cipher Principles

🔑 Key Concepts & Definitions

• True Random Number Generators : True random number generators produce outputs that cannot be reproduced, such as the sequence obtained by flipping a coin 100 times, whose chance of exact reproduction is $1/2^{100}$.

★ Must-know

📌 Stream ciphers encrypt individual bits by combining each plaintext bit with a key-stream bit, whereas block ciphers encrypt a block of b plaintext bits under the same key.

📌 In a synchronous stream cipher the key stream depends only on the key, whereas in an asynchronous stream cipher it also depends on the ciphertext.

📐 Formula — For plaintext, ciphertext, and key-stream bits in {0,1}, stream-cipher encryption and decryption are both modulo-2 addition: $y_i \equiv x_i+s_i \pmod{2}$ and $x_i \equiv y_i+s_i \pmod{2}$.

• Modulo-2 addition is equivalent to the exclusive-OR, or XOR, operation.

Further detail

• Encrypting the ASCII value of uppercase A, 1000001, with the key-stream bits 0101100 produces 1101101, the ASCII value of lowercase m.

💡 Memory Hook

Stream ciphers process individual bits, whereas block ciphers process complete blocks.

📖 7. Randomness and One-Time Pads

🔑 Key Concepts & Definitions

• CSPRNG : a PRNG for which, given consecutive output bits, computing subsequent or preceding bits is computationally infeasible
• Unconditional Security : that a cryptosystem cannot be broken even with infinite computational resources
• One-Time Pad : a stream cipher whose key stream is generated by a true random number generator, is known only to the legitimate parties, and uses every key-stream bit exactly once

★ Must-know

📌 True random number generators produce non-reproducible outputs from physical processes, whereas pseudorandom number generators compute deterministic sequences from an initial seed.

📌 Practical stream ciphers replace the one-time pad’s true-random key stream with a deterministic pseudorandom key stream generated from a short secret key, so they aim for computational rather than unconditional security.

Further detail

• A general pseudorandom number generator can generate a sequence recursively as $s_0=\mathrm{seed}$ and $s_{i+1}=f(s_i)$, while a linear congruential generator uses $s_{i+1}\equiv a s_i+b\pmod m$.

📌 A one-time pad requires one true-random key bit for every plaintext bit, so its key is as long as the plaintext and the key material cannot be reused.

💡 Memory Hook

TRNGs are unpredictable physical sources, PRNGs are deterministic, and CSPRNGs are deterministic but computationally unpredictable.

📖 8. LFSR Structure and Attacks

🔑 Key Concepts & Definitions

• Linear Feedback Shift Register : a clocked register whose input is the XOR-sum of selected register bits, with the number of flip-flops defining its degree

★ Must-know

📐 Formula — For an LFSR of degree $m$ with feedback coefficients $p_0,\ldots,p_{m-1}$, the output sequence satisfies $s_{m+i}\equiv\sum_{j=0}^{m-1}p_j s_{i+j}\pmod 2$.

• The maximum sequence length of an LFSR of degree $m$ is $2^m-1$, because the all-zero state is excluded and would remain stuck forever.

• A known-plaintext attack on a degree-$m$ LFSR reconstructs the key stream from plaintext and ciphertext, forms $m$ linear equations from the recurrence, and solves for the feedback coefficients using Gaussian elimination or matrix inversion.

Further detail

• An LFSR with degree 4 and feedback coefficients $(p_3,p_2,p_1,p_0)=(0{,}0{,}1{,}1)$ has period 15, whereas coefficients $(1{,}1{,}1{,}1)$ produce period 5.

💡 Memory Hook

Linearity enables reconstruction of the feedback coefficients, making a single LFSR insecure.

📖 9. Practical Stream Cipher Constructions

★ Must-know

📌 Salsa20 and ChaCha20 XOR a key stream generated from a key, nonce, and block number with the plaintext for encryption and with the ciphertext for decryption.

📌 A nonce must change for every encryption session so that two encryptions under the same key do not reuse the same key stream.

• Trivium is a hardware-oriented stream cipher designed by Christophe De Cannière and Bart Preneel that uses an 80-bit key and combines three shift registers with nonlinear components.

• 🔄 Trivium setup consists of: loading the 80-bit key into register A, loading the 80-bit initialization vector into register B, setting the remaining bits to zero except for the three rightmost bits of register C, clocking the cipher 1152 times without producing output

Further detail

• Salsa20 is a software-efficient ARX stream cipher developed by Daniel J. Bernstein in 2005; Salsa20/20 uses 20 rounds, and Salsa20 also has 12-round and 8-round variants.

• Salsa20 and ChaCha20 generate 512-bit key-stream blocks from 32-bit words and can compute blocks independently for parallel processing.

• ChaCha20 is a software-oriented stream cipher developed by Daniel J. Bernstein in 2008 and uses twenty rounds with a 256-bit key in the configuration described.

• Trivium’s three registers have lengths 93, 84, and 111 bits, for a total internal length of 288 bits.

💡 Memory Hook

Salsa20 and ChaCha20 target efficient software, whereas Trivium targets efficient hardware.

📖 10. Trivium Design and Operation

📝 Essential Points

• Trivium uses three nonlinear registers with lengths 93, 84, and 111 bits, and their feedback, feedforward, and AND-input positions are specified by the register parameters.

📐 Formula — The Trivium register updates are $a_i \equiv c_{i-66}+c_{i-111}+c_{i-110}c_{i-109}+a_{i-69} \pmod 2$, $b_i \equiv a_{i-66}+a_{i-93}+a_{i-92}a_{i-91}+b_{i-78} \pmod 2$, and $c_i \equiv b_{i-69}+b_{i-84}+b_{i-83}b_{i-82}+c_{i-87} \pmod 2$.

📐 Formula — Trivium produces its keystream bit as $s_i \equiv a_{i-66}+a_{i-93}+b_{i-69}+b_{i-84}+c_{i-66}+c_{i-111} \pmod 2$.

• Trivium initialization loads an 80-bit key into register A, an 80-bit initialization vector into register B, sets all other bits to zero, and sets the three rightmost bits of register C to one.

• Trivium performs a warm-up phase of 1152 clock cycles, equal to four times its total register length of 288 bits, before producing output.

• Trivium output begins with the bit produced in cycle 1153, and the resulting keystream is XORed with plaintext for encryption or ciphertext for decryption.

💡 Memory Hook

AND-based nonlinear feedback → resistance to linear attacks

📖 11. Trivium Security and Stream Cipher Context

🔑 Key Concepts & Definitions

• True random number generator : exploits an entropy source that behaves truly randomly to produce random bits

★ Must-know

• No attack on full Trivium was known that required fewer than 2^80 steps, but a weakened version with only 799 initialization iterations could be attacked in 2^68 steps.

Further detail

• A hardware implementation of Trivium occupies approximately 3500 to 5500 gate equivalents, and an implementation with 4000 gates can produce 16 bits per clock cycle.

• At a clock rate of 500 MHz, a 16-bit-per-cycle Trivium implementation achieves an encryption rate of 8 Gbit/s.

• True random number generators can use hardware phenomena such as electronic jitter and uncorrelated oscillators, or system events such as keystroke timings, interrupt timings, packet arrival times, memory or disk checksums, and the Linux-like system source /dev/random.

• Gilbert Vernam developed the stream-cipher concept in 1917 with an electromechanical machine that automated encryption and transmission of teletypewriter communication.

• The selected software-oriented ciphers were:

  • HC-128
  • Rabbit
  • Salsa20/12
  • SOSEMANUK
  • Grain v1
  • MICKEY v2
  • Trivium

💡 Memory Hook

True randomness supplies entropy; pseudorandomness supplies efficient keystreams

📖 12. DES Architecture and Core Principles

🔑 Key Concepts & Definitions

• Confusion : Claude Shannon — an encryption operation that obscures the relationship between the key and the ciphertext, commonly through substitution
• Diffusion : Claude Shannon — an encryption operation that spreads the influence of one plaintext symbol over many ciphertext symbols, commonly through permutations

📝 Essential Points

• DES encrypts 64-bit blocks with a 56-bit key and performs 16 rounds using different round keys derived from the main key.

📐 Formula — Each DES Feistel round applies $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus f(R_{i-1},k_i)$ for $i=1,\ldots,16$.

• The DES f function expands 32 input bits to 48 bits, XORs them with a 48-bit round key, applies eight S-boxes that each map 6 bits to 4 bits, and then applies a permutation P.

• DES S-boxes are the only nonlinear elements of the cipher and provide its principal source of confusion, while the expansion and P permutation contribute to diffusion and the avalanche effect.

💡 Memory Hook

Permutation → Feistel rounds → S-box confusion → P-permutation diffusion

📖 13. DES Key Schedule and Decryption

★ Must-know

• DES derives 16 round keys of 48 bits from an effective 56-bit key, although the input is commonly represented as 64 bits containing eight parity bits.

• The DES key schedule removes the eight parity bits with PC–1, splits the resulting key into 28-bit halves C0 and D0, rotates both halves left each round, and applies PC–2 to produce each 48-bit subkey.

• DES decryption uses the same Feistel structure as encryption but applies the subkeys in reverse order, namely k16, k15, through k1.

Further detail

📌 In DES rounds 1, 2, 9, and 16, the two key halves are rotated left by one bit, whereas in all other rounds they are rotated left by two bits.

• The total DES rotation is 28 positions, so the key-schedule halves satisfy C0 = C16 and D0 = D16.

💡 Memory Hook

PC–1 → rotations → PC–2 → reversed schedule

📖 14. Security and Attacks on DES

★ Must-know

• DES can be attacked by exhaustive key search because its key space contains only 256 possible keys.

• A DES exhaustive key search takes a known plaintext–ciphertext pair and tests keys until a key satisfies $DES^{-1}_{k_i}(y)=x$.

• Differential cryptanalysis requires 247 chosen plaintext–ciphertext pairs in its favorable setting and 255 pairs for random plaintext, whereas linear cryptanalysis requires 243 plaintext–ciphertext pairs.

📌 Single DES should no longer be used for confidential data because its 56-bit key can be searched at relatively low cost, although current analytical attacks are not practically efficient against it.

Further detail

• The Electronic Frontier Foundation’s Deep Crack machine broke DES by brute force in 1998 in 56 hours, using 1800 integrated circuits and costing less than $250,000.

💡 Memory Hook

Brute force breaks the short key; analytical attacks face resistant S-boxes

📖 15. DES Alternatives and PRESENT

🔑 Key Concepts & Definitions

• PRESENT : a lightweight 64-bit substitution-permutation block cipher with 31 rounds and supported key lengths of 80 and 128 bits

★ Must-know

• AES supports key lengths of 128, 192, and 256 bits and is the algorithm of choice for many modern applications.

📐 Formula — Triple DES applies encryption–decryption–encryption as $y=DES_{k_3}(DES^{-1}_{k_2}(DES_{k_1}(x)))$.

• Each PRESENT round XORs a round key into the state, applies the nonlinear sBoxLayer, and applies the linear pLayer; after round 31, the final subkey K32 is XORed into the state.

Further detail

📌 NIST limits 3TDEA to 220 64-bit plaintext blocks under one key set, and 3DES is being discontinued as a U.S. standard after 2023.

💡 Memory Hook

AES targets general security, while PRESENT targets constrained hardware

📖 16. AES Design and Overview

★ Must-know

• AES is the most widely used symmetric cipher and is incorporated into standards such as TLS, IPsec, IEEE 802.11i, and numerous commercial applications.

• In 2001, NIST declared Rijndael the new AES and published it as the U.S. standard FIPS PUB 197.

• AES candidates were required to use a 128-bit block size, support key lengths of 128, 192, and 256 bits, provide competitive security, and be efficient in software and hardware.

📌 AES uses a 128-bit block for all supported key lengths, whereas Rijndael also permits block lengths of 192 and 256 bits.

• AES has 10 rounds for a 128-bit key, 12 rounds for a 192-bit key, and 14 rounds for a 256-bit key.

Further detail

📌 Unlike DES, AES is not a Feistel network and encrypts all 128 state bits in each iteration.

💡 Memory Hook

DES/3DES limitations → public NIST competition → Rijndael becomes AES

📖 17. Finite and Galois Fields

🔑 Key Concepts & Definitions

• Group : a set with a closed associative operation, a neutral element, and an inverse for every element; it is abelian when the operation is commutative
• Field : a set whose elements form an additive abelian group and whose nonzero elements form a multiplicative abelian group, with multiplication distributing over addition
• Prime field : contains the elements 0 through p−1, with addition and multiplication performed modulo the prime p

★ Must-know

📌 A finite field with order q exists only when q is a prime power, $q=p^m$, where p is prime and is the field characteristic.

• AES represents each byte as an element of GF(2^8), a finite field with 256 elements, represented by a polynomial of degree at most 7 with coefficients in GF(2).

Further detail

📐 Formula — AES constructs GF(2^8) using the irreducible polynomial $P(x)=x^8+x^4+x^3+x+1$.

💡 Memory Hook

Prime-power order → finite field existence

📖 18. AES Internal Structure

🔑 Key Concepts & Definitions

• Byte Substitution : The Byte Substitution layer replaces each of the 16 state bytes using the same bijective nonlinear AES S-box.

📝 Essential Points

• The AES round layers are:

  • byte substitution
  • ShiftRows
  • MixColumns
  • key addition

• The AES S-box first computes inversion in GF(2^8), with zero mapped to zero, and then applies an affine transformation.

• ShiftRows leaves the first state row unchanged and cyclically shifts the second, third, and fourth rows right by three, two, and one byte, respectively.

📐 Formula — MixColumns multiplies each four-byte state column by a fixed matrix over GF(2^8), whose first output column is computed as $\begin{bmatrix}C_0\C_1\C_2\C_3\end{bmatrix}=\begin{bmatrix}02&03&01&01\\01&02&03&01\\01&01&02&03\\03&01&01&02\end{bmatrix}\begin{bmatrix}B_0\B_5\B_{10}\B_{15}\end{bmatrix}$.

📌 The Key Addition layer combines the 16-byte state with a 16-byte subkey using bitwise XOR, which is addition in GF(2).

• The AES key schedule produces 11, 13, or 15 128-bit subkeys for 128-, 192-, or 256-bit keys, respectively, because the number of subkeys equals the number of rounds plus one.

• AES uses a word-oriented key schedule in which one word equals 32 bits and expanded subkeys are stored in a word array W.

• AES-128 uses 11 subkeys stored in 44 words W[0] through W[43], AES-192 uses 13 subkeys stored in 52 words W[0] through W[51], and AES-256 uses 15 subkeys stored in 60 words W[0] through W[59].

📐 Formula — For AES-128, the first word of each later subkey is computed as $W[4i] = W[4(i-1)] \oplus g(W[4i-1])$ for i from 1 through 10.

• The AES key-schedule function g rotates four bytes, applies the byte-wise S-box substitution, and adds a round coefficient to the leftmost byte.

📌 Precomputation expands and stores all subkeys before encryption or decryption, whereas on-the-fly generation derives a new subkey during each AES round.

📌 Because AES is not based on a Feistel network, decryption must invert the AES layers rather than reuse the encryption layers unchanged.

• 🔄 The decryption structure uses:

  1. Inverse Byte Substitution
  2. Inverse ShiftRows
  3. Inverse MixColumns
  4. Key addition

• The first decryption round omits inverse MixColumns because the last encryption round omitted MixColumns.

• Inverse MixColumns multiplies each four-byte state column by the constant matrix with rows (0E, 0B, 0D, 09), (09, 0E, 0B, 0D), (0D, 09, 0E, 0B), and (0B, 0D, 09, 0E) over GF(2^8).

💡 Memory Hook

Substitute → ShiftRows → MixColumns → AddRoundKey

📊 Synthesis Tables

Main Cryptographic Branches

Branch	Key structure or method	Typical role
Symmetric algorithms	Shared secret key	Data encryption and message integrity checking
Asymmetric algorithms	Private key and public key	Digital signatures, key establishment, and data encryption
Cryptographic protocols	Algorithms combined as building blocks	Complex functions such as secure web communication

Stream and Block Ciphers

Feature	Stream cipher	Block cipher
Basic unit	Individual bit	Block of b bits
Key-stream dependence	Key only or key and ciphertext	Same key encrypts each block
Typical block size	Not applicable	128 bits for AES; 64 bits for DES and 3DES