Untitled

1 Symmetric Cryptography

• Cryptography historically about two parties, Alice and Bob, communicating securely despite Eve eavesdropping; modern uses include web server identity, digital signatures, online transactions, file storage protection, and wireless packet confidentiality.

• Symmetric cryptography uses the same key for encryption and decryption.

• The AES (Advanced Encryption Standard) is the symmetric algorithm recommended by NIST to replace DES; AES is a block cipher designed for 128-bit blocks with key lengths of 128, 192, or 256 bits (AES-128, AES-192, AES-256).

• This chapter builds intuition from classic ciphers to AES.

1.1 Attacks

• Cryptanalysis is the study of breaking cryptosystems; cryptanalysts know the algorithms but not the keys (open design principle).

• Four primary attack types (ordered by information available to the attacker):

  • Ciphertext-only attack: attacker has ciphertexts from the same key and seeks plaintexts or the key.

  • Known-plaintext attack: attacker has plaintext–ciphertext pairs; aims to determine the key.

  • Chosen-plaintext attack: attacker can choose plaintexts and obtain their ciphertexts; offline vs adaptive variants exist.

  • Chosen-ciphertext attack: attacker can choose ciphertexts and obtain plaintexts; offline vs adaptive variants exist.

• Security by obscurity is unreliable; attacker may learn the algorithm or implementation through disclosures, bribery, reverse engineering, etc.

• Unicity distance: the minimum amount of ciphertext needed so that there is a unique intelligible plaintext; typically much less than the key length due to natural language redundancy.

• Figure 2 (illustrative) shows attacks: ciphertext-only, known-plaintext, chosen-plaintext, and chosen-ciphertext.

1.2 Substitution Ciphers

• Simple substitution (e.g., Caesar cipher) replaces each plaintext letter with another; easily broken by frequency analysis.

• English letter frequencies (example from The Adventures of Tom Sawyer) show E ≈ 12.22%, T ≈ 9.67%, etc. Such frequencies reveal the substitution mapping.

• With 26-letter English alphabet, there are 26! possible substitutions;
  $26! \,\approx\, 4.03 \times 10^{26}$
  possible substitution ciphers.

• Polygraphic substitution: groups of letters encrypted together (e.g., digrams). A digram substitution has 676 possible digrams (26^2); the number of possible digram substitutions is 676! (huge).

• Digram substitution can be visualized with an S-box (substitution box) that maps input digrams to output digrams via a 2D table; the S-box is invertible if its mappings are unique.

• S-box examples: a 4×4 S-box for 4-bit blocks (binary form in Figure 3); Serpent was a finalist for AES but not chosen.

• Limitations: simple letter frequency/digram substitutions leak statistics about the plaintext; hence insecure for real use.

1.3 One-Time Pads

• The one-time pad is the only substitution scheme that is provably unbreakable under the two rules below:
  1) The pad length m must equal the plaintext length n.
  2) Each shift (or key) ki must be chosen completely at random.

• With a truly random pad, every ciphertext symbol is equally likely, so no statistical attack can reveal the plaintext.

• If pads are reused, security collapses and statistical methods can reveal parts of the plaintext.

• The historical claim that Moscow–Washington communications were protected by one-time pads is mentioned.

• Binary one-time pad: C = M ⊕ P, with M = C ⊕ P and P a random bit string of length n. XOR is associative: C ⊕ P = (M ⊕ P) ⊕ P = M.

• Why impractical: pad length must be as long as the message; reuse hazards led to Venona-era analysis revealing pad reuse.

• Practical take-away: one-time pads provide perfect secrecy when used once and never reused; otherwise, security degrades rapidly.

1.4 Pseudo-Random Number Generators (PRNGs)

• True randomness is hard to obtain efficiently; PRNGs expand a small random seed into a longer sequence that approximates randomness.

• Linear Congruential Generator (LCG):
  $x<em>{i+1} = (a x</em>i + b) \bmod n,$
  where a > 0, b ≥ 0 chosen randomly from [0, n−1]; if gcd(a, n) = 1 and especially when n is prime, the sequence can be uniform. However, LCGs have cryptographic weaknesses.

• In cryptographic contexts, LCGs are insufficient as random sources because the sequence can be predicted after observing a few consecutive values.

• A more secure PRNG approach: use a secure encryption algorithm (e.g., AES) to drive a deterministic sequence from a seed. Example: encrypt a deterministic sequence of inputs with a fixed key to produce a pseudorandom stream.

• Such a generator can have a period of 2^n when used with block ciphers in certain configurations; it can be used as a keystream for encryption (XOR with plaintext) but must avoid reuse of the stream key to maintain security.

• Practical guidance: use a cryptographically secure PRNG for key streams; never reuse keystream for different messages under the same key; ideal usage is in a streaming cipher where the keystream length is shorter than the period.

1.5 The Hill Cipher and Transposition Ciphers

• Hill cipher (1929) uses linear algebra. A block of m letters is interpreted as a vector in Z_{26}^m. The key is an invertible m×m matrix K modulo 26.

  • Encryption: $\mathbf{c} = K \mathbf{x} \quad (\bmod 26)$ where \mathbf{x} is the plaintext block vector and \mathbf{c} is the ciphertext block vector.

  • Decryption: $\mathbf{x} = K^{-1} \mathbf{c} \quad (\bmod 26).$

• Entire message treated as a matrix M of size m×N; ciphertext C = K M; decryption M = K^{-1} C.

• Hill cipher illustrates the use of numbers and linear algebra in cryptography; still vulnerable to linear-analysis attacks with enough plaintext–ciphertext pairs.

• Transposition ciphers: shuffle letters within blocks according to a fixed permutation π of length m.

  • Encryption: Ci = π(Bi); Decryption: Bi = π^{-1}(Ci).

  • Transposition as a Hill cipher special case: any permutation can be realized as matrix multiplication; this shows why transposition alone does not hide frequency data (the letter distribution remains exposed), and thus is vulnerable when used alone.

1.6 The Advanced Encryption Standard (AES)

• AES chosen in 1997 as replacement for DES; designed as Rijndael by Daemen and Rijmen; 128-bit blocks; key lengths: 128, 192, or 256 bits (AES-128/192/256).

• Block size fixed at 128 bits; 10 rounds for AES-128; state is a 128-bit array (state) processed through rounds.

• Encryption process:

  • Initial AddRoundKey: $X_0 = P \oplus K$

  • 10 rounds (i = 1..10): each round applies four steps to the 128-bit state: SubBytes, ShiftRows, MixColumns, AddRoundKey; final round omits MixColumns.

  • Ciphertext: $C = X_{10}.$

• AES round structure (Figure 5): X1, X2, …, X10 with steps: SubBytes (S-box substitution), ShiftRows (row-wise permutation), MixColumns (matrix multiplication in GF(2^8)), AddRoundKey (XOR with a round key derived from the cipher key K).

• Implementation notes:

  • Software often uses eight 256-entry lookup tables (T-tables) mapping a byte to a 32-bit word; enables fast rounds using only 3 operation types: XOR, byte-splitting, and table lookups.

  • Each round uses a derived round key; key schedule is a separable process that expands the initial key into 11 round keys for AES-128 (including the initial round key).

• Attacks and countermeasures:

  • AES is currently extremely secure; known practical attacks are side-channel attacks (timing attacks) on implementations that use lookup tables because cache timing leaks table access patterns.

  • Constant-time implementations and defensive programming mitigate timing attacks; hardware attacks (faults on FPGAs) require hardened designs.

• Details of AES internals (brief reference):

  • SubBytes: uses an S-box based on GF(2^8) operations; the S-box is a fixed lookup table (Figure 14).

  • ShiftRows: 4×4 matrix row-wise cyclic shifts (0, 1, 2, 3) for rows 0–3 respectively.

  • MixColumns: column-wise linear mixing using GF(2^8) arithmetic (GF(2^8) with the irreducible polynomial x^8 + x^4 + x^3 + x + 1).

  • AddRoundKey: XOR the state with a round key derived from the main key.

• AES key schedule (brief):

  • The initial key is divided into four 4-byte words W[0], W[1], W[2], W[3].

  • For each round i, compute the first column: W[4i] = W[4i-4] ⊕ Ti(W[4i-1]), where Ti is a transformation involving a cyclic byte rotation, S-box substitutions, and an R(i) round constant.

  • Other columns are computed as: W[4i+1] = W[4i-3] ⊕ W[4i], W[4i+2] = W[4i-2] ⊕ W[4i+1], W[4i+3] = W[4i-1] ⊕ W[4i+2].

• Round constants: R(i) is the 8-bit representation of x^{i-1} mod (x^8 + x^4 + x^3 + x + 1). The first ten constants in hex are: 01, 02, 04, 08, 10, 20, 40, 80, 1B, 36.

• The AES design emphasizes invertibility of each step, enabling decryption by reversing the rounds with inverse operations.

1.7 Modes of Operation

• Modes of operation describe how to apply a block cipher to a sequence of blocks; common modes: ECB, CBC, CFB, OFB, CTR.

• Electronic Codebook (ECB) mode:

  • Encryption: $C<em>i = E</em>K(B_i)$ for each block Bi.

  • Decryption: $B<em>i = D</em>K(C_i).$

  • Advantages: simplicity; can tolerate block loss because each block is independent.

  • Disadvantages: identical plaintext blocks yield identical ciphertext blocks; exposes patterns (e.g., in images).

• Cipher-Block Chaining (CBC) mode:

  • Encryption: start with an initialization vector C0; $C<em>i = E</em>K(B<em>i \oplus C</em>{i-1})$.

  • Decryption: $B<em>i = D</em>K(C<em>i) \oplus C</em>{i-1}$ with the same IV C0.

  • Identical plaintext blocks encrypted in different places are unlikely to yield identical ciphertexts due to chaining.

  • Decryption must be done sequentially because it depends on the previous ciphertext block; however, decryption of later blocks can be parallel if all ciphertext blocks are known.

  • CBC tolerates loss of a ciphertext block in the sense that decryption of later blocks is affected only by the lost block and beyond.

• Cipher Feedback (CFB) mode:

  • Encryption: start with IV C0; $C<em>i = E</em>K(C<em>{i-1}) \oplus B</em>i.$

  • Decryption: $B<em>i = E</em>K(C<em>{i-1}) \oplus C</em>i.$

  • The decryption process uses the encryption of the previous ciphertext block; encryption and decryption can be adapted for potential faster decryption in some implementations.

• Output Feedback (OFB) mode:

  • Use a chain of generated pad blocks: Vi = EK(V{i-1}) with V0 as an IV generated per message.

  • Encryption: $C<em>i = V</em>i \oplus B_i.$

  • Decryption: $B<em>i = V</em>i \oplus C_i$.

  • OFB can tolerate block losses and supports parallel encryption and decryption if the pad sequence is precomputed.

• Counter (CTR) mode:

  • Encryption/decryption both parallelizable; uses a keystream generated by encrypting successive counter values.

  • Process: start with seed s, compute $V<em>i = E</em>K(s + i - 1)$; then $C<em>i = B</em>i \oplus V<em>i$ and $B</em>i = C<em>i \oplus V</em>i.$

  • CTR can tolerate dropped blocks and supports parallel operations.

2 Public-Key Cryptography

2.1 Modular Arithmetic

• When working with large numbers, arithmetic is done modulo n, i.e., in the ring $\mathbb{Z}_n = {0,1,2,\dots,n-1}.$

• Modulo operation: for any integer x and positive n, x mod n is the remainder when x is divided by n, with the convention that negative x is adjusted by adding a multiple of n to land in [0, n-1].

• Modular inverses: y is the modular inverse of x modulo n if $x y \equiv 1 \pmod{n}.$

  • 1 has a modular inverse modulo n as long as gcd(1, n) = 1 (trivial), and similarly gcd(n-1, n) = 1.

  • Not every element in $\mathbb{Z}_n$ has an inverse; if n is prime, every nonzero element has an inverse; otherwise, only elements coprime to n have inverses.

• Euler’s totient function, $\phi(n)$, counts the numbers between 1 and n that are coprime to n. Examples: $\phi(p) = p-1$ for prime p; for n = pq (p and q prime), $\phi(n) = (p-1)(q-1).</p></li><li><p>Euler’s Theorem: if gcd(x, n) = 1, then$x^{\phi(n)} \equiv 1 \pmod{n}.$</p></li><li><p>Corollary: for any x coprime to n and any integer k,$x^k \equiv x^{k \bmod \phi(n)} \pmod{n}.$</p></li><li><p>Modular multiplication table and exponentiation patterns are illustrated by examples (Figure 8 and Figure 9 in the text).</p></li><li><p>Primality testing and generation of primes: primality tests determine whether a number is prime (but do not factor it); RSA security relies on the difficulty of factoring large n; random primes are typically generated by repeatedly testing random odd numbers for primality.</p></li></ul><h4 id="f90a68c6-86d7-4950-843c-b383fb550e89" data-toc-id="f90a68c6-86d7-4950-843c-b383fb550e89" collapsed="false" seolevelmigrated="true">2.2 The RSA Cryptosystem</h4><ul><li><p>Public-key cryptosystem: public key (e, n) used to encrypt; private key d used to decrypt; private primes p, q and φ(n) are kept secret.</p></li><li><p>Setup:</p><ul><li><p>Choose two large primes p, q; compute n = p q.</p></li><li><p>Compute φ(n) = (p-1)(q-1).</p></li><li><p>Choose e such that gcd(e, φ(n)) = 1.</p></li><li><p>Compute d ≡ e^{-1} (mod φ(n)); i.e., e d ≡ 1 (mod φ(n)).</p></li></ul></li><li><p>Encryption:$C \equiv M^e \pmod{n}.$</p></li><li><p>Decryption:$M \equiv C^d \pmod{n}.$</p></li><li><p>Correctness sketch (for M coprime to n):$C^d = M^{ed} \equiv M^{1 + k\phi(n)} \equiv M \; (\bmod n)$for some integer k, using Euler’s theorem.</p></li><li><p>When M is not coprime to n, a similar argument uses Euler’s theorem with p or q as factors of n.</p></li><li><p>Security: based on the difficulty of factoring n to derive p, q, and thus φ(n); recommends 2048-bit modulus as of 2010; deterministic encryption is a side-channel and timing attack consideration; ciphertexts with the same M under the same key reveal identity (no randomness).</p></li><li><p>Efficient RSA tasks include primality testing, gcd, modular inverse, and modular exponentiation; these are treated in detail in Section 5.2.</p></li></ul><h4 id="df9f1a62-3463-427b-aaf8-5e53487108a9" data-toc-id="df9f1a62-3463-427b-aaf8-5e53487108a9" collapsed="false" seolevelmigrated="true">2.3 The ElGamal Cryptosystem</h4><ul><li><p>A public-key cryptosystem based on discrete logarithms with randomized encryption; produces different ciphertexts for the same plaintext, thanks to randomization.</p></li><li><p>Setup: pick prime p, generator g for Z_p; choose secret x in [1, p-2], compute y = g^x mod p. Public key: (p, g, y); private key: x.</p></li><li><p>Encryption: Alice uses Bob’s public key (p, g, y); chooses random k in [1, p-2], computes</p><ul><li><p>a = g^k mod p,</p></li><li><p>b = M y^k mod p.</p></li><li><p>Ciphertext: (a, b).</p></li></ul></li><li><p>Decryption: Bob computes M = b (a^x)^{-1} mod p.</p><ul><li><p>Proof of correctness: b (a^x)^{-1} = M y^k (g^k)^x)^{-1} = M, since y = g^x mod p.</p></li></ul></li><li><p>Security: relies on hardness of the discrete logarithm problem; to break, an eavesdropper would have to compute x from y = g^x mod p.</p></li><li><p>Randomization ensures distinct ciphertexts for the same plaintext, avoiding deterministic leakage.</p></li></ul><h4 id="e5e8ecfd-2580-41cb-a441-02aca21afe6c" data-toc-id="e5e8ecfd-2580-41cb-a441-02aca21afe6c" collapsed="false" seolevelmigrated="true">2.4 Key Exchange</h4><ul><li><p>Symmetric encryption requires a shared secret key; key exchange protocols establish this over an insecure channel.</p></li><li><p>Diffie–Hellman (DH) protocol relies on modular exponentiation and the hardness of the discrete logarithm problem.</p></li><li><p>Setup parameters: a prime p and a generator g for the multiplicative group modulo p.</p></li><li><p>DH protocol steps:<br>1) Alice picks random x ∈ Z<em>p and computes X = g^x mod p; sends X to Bob. 2) Bob picks random y ∈ Z</em>p and computes Y = g^y mod p; sends Y to Alice.<br>3) Alice computes K1 = Y^x mod p.<br>4) Bob computes K2 = X^y mod p.</p></li><li><p>Both derive the same shared key K = g^{xy} mod p, i.e., K1 = K2.</p></li><li><p>Security assumption: it is difficult to determine K from public parameters p, g and the observed X, Y (i.e., solving discrete logarithms). Difficulty extends to the Diffie–Hellman problem: computing K from p, g, X = g^x mod p and Y = g^y mod p.</p></li><li><p>Vulnerability: man-in-the-middle attack is possible if an attacker can intercept/modify messages; a malicious party can establish separate keys with Alice and Bob, decrypting and re-encrypting messages in transit (Figure 11).</p></li></ul><h3 id="1af6c5ae-ae17-4606-aeb5-e106b24ffac9" data-toc-id="1af6c5ae-ae17-4606-aeb5-e106b24ffac9" collapsed="false" seolevelmigrated="true">3 Cryptographic Hash Functions</h3><h4 id="9009ab02-565a-4aa0-89b7-64d8599aa763" data-toc-id="9009ab02-565a-4aa0-89b7-64d8599aa763" collapsed="false" seolevelmigrated="true">3.1 Properties and Applications</h4><ul><li><p>Hash functions compress messages to a fixed-size digest; properties include determinism, one-wayness, and collision resistance.</p></li><li><p>Desired properties: ease of computing H(M) for any M; hard to find M' ≠ M with H(M') = H(M); digest length is typically much smaller than the input; e.g., SHA-256 outputs 256 bits.</p></li><li><p>Collision resistance: weak vs strong collisions:</p><ul><li><p>Weak collision resistance: given M, find M' ≠ M with H(M') = H(M).</p></li><li><p>Strong collision resistance: find any two distinct M1, M2 with H(M1) = H(M2).</p></li></ul></li><li><p>Merkle–Damgård construction: builds a hash function from a compression function C(X, Y) that takes fixed-length inputs X (m bits) and Y (n bits) and outputs n bits.</p><ul><li><p>Process: split M into blocks M1, M2, …, Mk of length m; pad the last block to length m.</p></li><li><p>Initialize with fixed IV v; set d1 = C(M1, v), d2 = C(M2, d1), …, dk = C(Mk, d_{k-1}); H(M) = dk.</p></li><li><p>Collision caveat: if there exists a collision H(M1) = H(M2), then for any P, H(M1 || P) = H(M2 || P); hence, compression function must be strongly collision resistant to ensure overall hash security.</p></li></ul></li><li><p>Practical hash functions: SHA-256 and SHA-512 (NIST standards) based on Merkle–Damgård; MD5 is deprecated due to known weaknesses; MD5 collisions can be constructed; MD5 is no longer recommended for cryptographic security.</p></li><li><p>SHA-256 uses a 512-bit compression function with 256-bit output; SHA-512 uses a 1024-bit compression function with 512-bit output.</p></li></ul><h4 id="90330cd0-0874-4319-8a72-a4772e2d343c" data-toc-id="90330cd0-0874-4319-8a72-a4772e2d343c" collapsed="false" seolevelmigrated="true">3.2 Birthday Attacks</h4><ul><li><p>Hash collisions can be found faster than trying all 2^b hash values due to the birthday paradox.</p></li><li><p>If a hash function has b-bit output, the number of possible hash values is 2^b. A birthday attack suggests that after about 2^{b/2} random hashes, a collision is likely:</p><ul><li><p>For a 256-bit hash, security is about 128 bits (i.e., collisions are expected after about 2^{128} trials).</p></li></ul></li><li><p>This underpins the practical security level of hash functions against collision attacks.</p></li></ul><h3 id="4d777a94-c067-4106-8b8b-0bece67b4d16" data-toc-id="4d777a94-c067-4106-8b8b-0bece67b4d16" collapsed="false" seolevelmigrated="true">4 Digital Signatures</h3><p>A digital signature binds a message to the signer’s identity and enables verification of authenticity.</p><ul><li><p>Signing process: Alice uses her private key to produce a signature SAlice(M) on message M; verification uses Alice’s public key to verify the signature on M.</p></li><li><p>Desired properties:</p><ul><li><p>Non-forgeability: forging a signature on M should be computationally hard without the private key.</p></li><li><p>Non-mutatability: given SAlice(M), it should be hard to transform it into a valid signature on a different message N.</p></li><li><p>Non-repudiation: signer cannot later repudiate signing M.</p></li></ul></li><li><p>This section recalls RSA and ElGamal digital signatures and how to combine signatures with hash functions to improve practicality and security.</p></li></ul><h4 id="b23c1471-341b-4c0a-a20a-05a2a2d33786" data-toc-id="b23c1471-341b-4c0a-a20a-05a2a2d33786" collapsed="false" seolevelmigrated="true">4.1 The RSA Signature Scheme</h4><ul><li><p>RSA signature is closely related to RSA encryption; the signing operation uses the private key:</p><ul><li><p>Signature:$S \equiv M^d \pmod{n}.$</p></li><li><p>Verification: check that$M \equiv S^e \pmod{n}$(since$S^e = (M^d)^e = M^{de} \equiv M \pmod{n}$when de ≡ 1 (mod φ(n))).</p></li></ul></li><li><p>Non-forgeability follows from the difficulty of breaking RSA encryption.</p></li><li><p>Mutable-signature risk: using two valid signatures for M1, M2 could produce a forged signature on M1 M2 if hash chaining is not used; in practice, digital signatures hash the message first to avoid such risks.</p></li></ul><h4 id="20762333-4c66-4a55-ae3b-ae7172e52010" data-toc-id="20762333-4c66-4a55-ae3b-ae7172e52010" collapsed="false" seolevelmigrated="true">4.2 The ElGamal Signature Scheme</h4><ul><li><p>Parallels ElGamal encryption with a signing variant:</p><ul><li><p>Given public key (p, g, y) with y = g^x mod p and private key x.</p></li><li><p>To sign M, pick fresh random k in [1, p−2] and compute</p></li><li><p>a = g^k mod p,</p></li><li><p>b = k^{-1} (M − x a) mod (p − 1).</p></li><li><p>Signature is (a, b).</p></li><li><p>Verification: check that$y^a a^b \equiv g^M \pmod{p}$; this holds because y^a a^b = g^{x a} g^{k b} = g^{x g^k + k(M − x a)} ≡ g^M (mod p).</p></li></ul></li><li><p>Security hinges on the discrete logarithm problem; reusing k (as in poor RNG practice) reveals the secret key x.</p></li><li><p>Important: never reuse k for two signatures; otherwise, attackers can solve for x.</p></li></ul><h4 id="3f4aaad0-775a-4d7c-bc39-52b6d05da201" data-toc-id="3f4aaad0-775a-4d7c-bc39-52b6d05da201" collapsed="false" seolevelmigrated="true">4.3 Using Hash Functions with Digital Signatures</h4><ul><li><p>In practice, sign hash digests (H(M)) rather than the entire message M to improve efficiency and reduce mutability risks.</p></li><li><p>Hashing also mitigates birthday-attacks by compressing large messages into fixed-size digests; but one must ensure the hash function used has strong collision resistance to prevent forgery via collisions.</p></li><li><p>If an attacker can cause collisions H(M1) = H(M2), they could trick the signer into signing two messages with one signature; hence, collision-resistant hash functions are essential.</p></li></ul><h3 id="9bafa300-1bf9-4750-a3ca-b14c72800751" data-toc-id="9bafa300-1bf9-4750-a3ca-b14c72800751" collapsed="false" seolevelmigrated="true">5 Details of AES and RSA Cryptography</h3><h4 id="541fb678-c9ee-4ed4-9b46-4126a99145c1" data-toc-id="541fb678-c9ee-4ed4-9b46-4126a99145c1" collapsed="false" seolevelmigrated="true">5.1 Details for AES (128-bit version shown; analogous for 192/256)</h4><ul><li><p>Input/output: AES operates on 128-bit blocks; with 128/192/256-bit keys.</p></li><li><p>Ten rounds for 128-bit keys; initial AddRoundKey, then 9 rounds, then a final 10th round without MixColumns.</p></li><li><p>Matrix representation: the 16-byte block is viewed as a 4×4 matrix (column-major order):<br>$\begin{pmatrix}
  a{0,0} & a{0,1} & a{0,2} & a{0,3} \
  a{1,0} & a{1,1} & a{1,2} & a{1,3} \
  a{2,0} & a{2,1} & a{2,2} & a{2,3} \
  a{3,0} & a{3,1} & a{3,2} & a{3,3}
  \end{pmatrix}$</p></li><li><p>SubBytes: each byte replaced by its S-box substitution; S-box is a fixed table based on GF(2^8) arithmetic (GF(2^8) with irreducible polynomial x^8 + x^4 + x^3 + x + 1).</p></li><li><p>ShiftRows: cyclic left shifts within rows: 1st row shift by 0, 2nd by 1, 3rd by 2, 4th by 3 (in the matrix above).</p></li><li><p>MixColumns: each column is transformed by a fixed 4×4 matrix multiplication over GF(2^8); GF(2^8) arithmetic is defined via polynomial operations: addition is XOR, multiplication is modulo the irreducible polynomial x^8 + x^4 + x^3 + x + 1.</p></li><li><p>AddRoundKey: state XORed with a round key derived from the secret key; key schedule expands the 128-bit key into 11 round keys for AES-128.</p></li><li><p>Key schedule (brief):</p><ul><li><p>Represent the 128-bit key as a 4×4 matrix W[0]..W[3]. First round key is the initial key; for each round i, compute the first column W[4i] = W[4i−4] ⊕ Ti(W[4i−1]); then the next three columns follow:</p></li><li><p>W[4i+1] = W[4i−3] ⊕ W[4i],</p></li><li><p>W[4i+2] = W[4i−2] ⊕ W[4i+1],</p></li><li><p>W[4i+3] = W[4i−1] ⊕ W[4i+2].</p></li><li><p>Ti(W[4i−1]) = [S(w1) ⊕ R(i), S(w2), S(w3), S(w0)]^T where W[4i−1] = [w0, w1, w2, w3]^T and S is the S-box substitute; R(i) is the i-th round constant defined below.</p></li></ul></li><li><p>Round constants: R(i) is 8-bit, defined by the representation of x^{i−1} modulo (x^8 + x^4 + x^3 + x + 1).</p></li><li><p>First ten round constants (in hex): 01, 02, 04, 08, 10, 20, 40, 80, 1B, 36.</p></li><li><p>Inverse operations exist for decryption; AES is symmetric and uses the same key for encryption and decryption.</p></li><li><p>Implementation notes: common optimization uses 8 T-tables of 256 32-bit entries each; a round is performed via three operation types: XOR, splitting, and table lookups.<br>-AES in practice: resistant to known practical cryptanalytic attacks; timing and side-channel attacks are the main concerns in implementations; constant-time implementations reduce the vulnerability.</p></li></ul><h4 id="119be143-d0a8-43df-8695-af101d074b3a" data-toc-id="119be143-d0a8-43df-8695-af101d074b3a" collapsed="false" seolevelmigrated="true">5.2 Details for RSA</h4><ul><li><p>Theoretical prerequisites: Fermat’s little theorem, Euler’s theorem, Euclid’s algorithm, modular exponentiation, primality testing.</p></li><li><p>Fermat’s little theorem: for prime p and any integer g with 1 ≤ g < p,<br>$g^{p-1} \equiv 1 \pmod{p}.$</p></li><li><p>Euler’s theorem: for x with gcd(x, n) = 1,<br>$x^{\phi(n)} \equiv 1 \pmod{n}.$</p></li><li><p>Corollary:$x^k \equiv x^{k\bmod \phi(n)} \pmod{n}.$</p></li><li><p>Euclid’s algorithm (and extended Euclidean algorithm) for gcd and modular inverses.</p></li><li><p>Modular exponentiation: repeated squaring algorithm to compute$g^n \bmod p efficiently; binary expansion of n yields linear-in-bitlength number of multiplications.

• Primality testing: efficient tests exist to distinguish primes; factoring is hard; the difficulty of factoring large n underpins RSA security.

• Typical RSA usage: hybrid approach—encrypt a symmetric key with RSA, then use symmetric encryption (e.g., AES) for the data.

• RSA efficiency caveat: RSA is slower than symmetric ciphers; practical deployments combine RSA for key exchange with AES for data encryption.