Abstract Algebra (Groups, Rings & Cryptography)

Learning Goal: Build a rigorous mathematical foundation in Group and Ring theory to master modern security architectures, specifically key generation, encryption, and verification processes in the RSA and Elliptic Curve Cryptography (ECC) cryptosystems.

• Estimated Total Study Time: 24 Hours
• Prerequisites: Basic high school algebra, elementary set theory notation, and comfort with logical reasoning.

---

Module 1: Foundations of Modular Arithmetic & Number Theory

This module establishes the arithmetic bedrock of computer security. You will transition from basic division to formal modular structures, learning how properties of prime numbers and greatest common divisors (GCD) ensure computational uniqueness and secure "one-way" transformations in cryptography.

• Why this video: This video provides an elegant, highly intuitive visualization of clock arithmetic and congruence classes. It is the perfect introduction to thinking of numbers as points on a circular path of wrap-around values rather than a linear sequence, laying a solid geometric foundation for modular equivalence.

---

• Why this video: Finding the greatest common divisor is fundamental, but modular division requires calculating modular multiplicative inverses. This video explains Bézout's Identity ($ax + by = \gcd(a,b)$), showing how the Extended Euclidean Algorithm constructively uncovers these integer coefficients—a process essential for finding decryption keys in public-key cryptosystems.

---

• Why this video: This video links pure mathematics to security, detailing why prime numbers behave as the "atoms" of cryptography. It explains the asymmetry of multiplication vs. factorization (the "trapdoor" property) and illustrates why finding large primes is computationally trivial, while factoring their product is practically impossible.

Knowledge Checkpoint

• Understand the concept of congruence classes modulo $n$ ($a \equiv b \pmod n$).
• Perform the Extended Euclidean Algorithm manually to express $\gcd(a,b)$ as a linear combination of $a$ and $b$.
• Explain why primes are the foundational building blocks of asymmetric key generation.

---

Module 2: Introduction to Group Theory & Cyclic Groups

In this module, we move from individual numbers to algebraic structures. You will explore Groups—sets paired with operations that satisfy properties of closure, identity, associativity, and invertibility. Special emphasis is placed on cyclic groups and generators, which form the mathematical backbone of discrete logarithm cryptosystems.

• Why this video: This comprehensive university lecture establishes formal definitions of a Group. It carefully proves the four defining properties (associativity, identity, inverses, closure) with rigorous whiteboard-by-whiteboard examples, ensuring you can formally recognize whether an algebraic system constitutes a group.

---

• Why this video: Directly addressing a key prerequisite in cryptography, this video explains how a single generator element can reconstruct an entire group through repeated applications of its operation. It connects cyclic structures to discrete mathematics, explaining "element order" and showing why finite cyclic groups are isomorphic to integers under addition modulo $n$ ($\mathbb{Z}_n$).

---

• Why this video: Lagrange's Theorem is a cornerstone of group theory. By visualizing groups through cosets and partitions, this short lecture provides an intuitive, geometric proof of why the size of any subgroup must cleanly divide the size of the parent group, preventing structural anomalies.

Knowledge Checkpoint

• Prove whether a given set and binary operation constitute a valid mathematical group.
• Determine the order of an element in a finite cyclic group and identify all of its generators.
• Apply Lagrange’s Theorem to show how subgroup partitions restrict group options.

---

Module 3: Ring Theory and Finite Fields

Cryptographic systems operate on limited memory spaces, meaning infinite numbers must be mapped to finite domains without losing algebraic properties. This module details Rings (two operations: addition and multiplication) and Finite Fields (Galois Fields, or $GF(p)$), which allow secure, lossless addition, subtraction, multiplication, and division on computers.

• Why this video: This clear introduction defines Rings by contrasting them with Groups. It highlights how multiplication interacts with addition through distributivity, introduces additive identities ($0$), and discusses the distinction between rings with and without multiplicative identities (often referred to as rings vs. "rngs").

---

• Why this video: Bridging abstract ring concepts with practical computer architecture, this video introduces Galois Fields ($GF(p)$ and $GF(p^m)$). It explains how polynomial arithmetic with coefficients restricted to $\{0, 1\}$ (GF(2)) allows hardware to compute cryptographic transformations (like AES block cipher mix-columns) extremely quickly.

---

• Why this video: This short video shows modular reduction in action over polynomial extension fields. It details how computers divide and multiply elements inside $GF(2^m)$ using irreducible polynomials as moduli, ensuring that operations never overflow the designated bit length.

Knowledge Checkpoint

• Differentiate between a Group, a Ring, and a Field based on their allowed binary operations.
• Define Galois Field $GF(p)$ and explain why division is only possible when the modulus $p$ is prime.
• Perform basic polynomial addition and multiplication in $GF(2^3)$ using an irreducible polynomial.

---

Module 4: The RSA Cryptosystem & Number Theory

We now connect Group Theory and Number Theory to explain RSA, the first widely implemented public-key cryptosystem. You will learn how the group of units modulo $n$ ($U(n)$) and Euler's Totient Theorem provide the algebraic mechanism to encrypt messages and securely decrypt them using a private key.

• Why this video: This video addresses a key theoretical gap: the rigorous linkage between group structures and Euler's Totient Theorem. It shows that coprime integers modulo $n$ form a multiplicative group of order $\phi(n)$, and uses group theory properties to prove why $a^{\phi(n)} \equiv 1 \pmod n$ for any coprime element.

---

• Why this video: This video walks through the practical mechanics of RSA key generation. It breaks down the five critical setup steps: picking primes $p$ and $q$, computing modulus $n$, calculating Euler's totient $\phi(n)$, choosing public exponent $e$, and deriving the decryption exponent $d$.

---

• Why this video: This concise lecture provides the formal proof of correctness for RSA. It demonstrates why decrypting a ciphertext ($c^d \equiv (m^e)^d \pmod n$) recovers the original message $m$, checking both cases where $\gcd(m, n) = 1$ and when $m$ shares a factor with $n$ using the Chinese Remainder Theorem.

Knowledge Checkpoint

• Calculate Euler’s Totient $\phi(n)$ for a composite modulus $n = pq$.
• Given public parameters $(e, n)$, calculate the corresponding private exponent $d$ using the Extended Euclidean Algorithm.
• Prove why the decryption process $m \equiv c^d \pmod n$ successfully restores the plaintext using Euler's Totient Theorem.

---

Module 5: Elliptic Curve Cryptography (ECC)

Modern computer security relies heavily on Elliptic Curve Cryptography (ECC). In this module, you will learn how points on an elliptic curve, combined with an artificial point at infinity, form an abelian group under a unique geometric "addition" law. This structure yields smaller key sizes and stronger security margins than RSA.

• Why this video: While real-number elliptic curves look smooth, cryptographic implementations require exact integers. This visual breakdown explains how plotting elliptic curves over Galois Fields $F_p$ transforms curves into a scatterplot of discrete integer points, preventing rounding errors and maintaining perfect group closure.

---

• Why this video: This video illustrates the algebraic addition law ($P + Q + R = 0$) and the point duplication formulas. It then walks through the Elliptic Curve Diffie-Hellman (ECDH) key exchange, demonstrating how point multiplication is easy to compute but incredibly difficult to reverse.

---

• Why this video: This masterclass lecture by renowned security professor Christof Paar provides an in-depth academic look at ECC. It explores the Elliptic Curve Discrete Logarithm Problem (ECDLP), details parameter selection (like Secp256k1), and compares ECC's key size advantages to RSA.

Knowledge Checkpoint

• Explain the geometric and algebraic "tangent-and-chord" rule for adding two points on an elliptic curve.
• Understand how a point at infinity ($\mathcal{O}$) acts as the identity element in the ECC group.
• Define the Elliptic Curve Discrete Logarithm Problem (ECDLP) and describe how it secures the ECDH exchange.

---

Course Map

This map outlines the conceptual progression of the curriculum, tracing the path from basic arithmetic up to advanced public-key cryptosystems.

---

Key People Index

The development of modern cryptosystems was driven by researchers who recognized deep connections between abstract mathematical structures and computer security.

• Leonhard Euler (1707–1783): Swiss mathematician who formulated the Totient function ($\phi$) and proved Euler's Theorem. This group-theoretic foundation secures RSA key decryption.
• Étienne Bézout (1730–1783): French mathematician who proved Bézout's Identity. The Extended Euclidean Algorithm uses this theorem to compute modular inverses, which are essential for private keys.
• Evariste Galois (1811–1832): French mathematical prodigy who laid the foundations for Group Theory and Finite Fields ($GF(p)$) before dying in a duel at age 20.
• Ron Rivest, Adi Shamir, & Leonard Adleman: Computer scientists who combined modular arithmetic, prime factorization, and Euler's Totient Theorem in 1977 to create the RSA algorithm.
• Neal Koblitz & Victor Miller: Mathematicians who independently proposed using elliptic curves over finite fields for public-key cryptography in 1985, creating Elliptic Curve Cryptography (ECC).

---

Final Course Self-Assessment

Complete these challenges to test your understanding of abstract algebra and cryptography.

• Extended GCD Check: Given $a = 120$ and $b = 23$, find integers $x$ and $y$ such that $120x + 23y = \gcd(120, 23)$ using the Extended Euclidean Algorithm.
• Modular Inversion Check: Find the modular inverse of $9 \pmod{26}$. Confirm that $9 \cdot 9^{-1} \equiv 1 \pmod{26}$.
• Group Verification: Determine if the set of odd integers under standard addition forms a group, and justify your answer using the group axioms.
• Cyclic Group Analysis: For the group $(\mathbb{Z}_7^\times, \cdot)$, list all elements, identify a generator, and find the order of each element.
• Coset Partitioning: Identify a subgroup $H$ of $(\mathbb{Z}_{12}, +)$, construct its distinct cosets, and show how they satisfy Lagrange's Theorem.
• Galois Arithmetic: Compute $(x^2 + 1) \cdot (x + 1)$ in the finite field $GF(2^3)$ modulo the irreducible polynomial $P(x) = x^3 + x + 1$.
• Euler Totient Calculation: Find $\phi(33)$ using prime factorization and list the elements of the multiplicative group of units $U(33)$.
• RSA Walkthrough: Choose $p=3, q=11$, and $e=3$. Find $d$, encrypt message $m=4$, and confirm that decrypting your ciphertext returns $4$.
• ECC Geometry Verification: Given the curve $y^2 = x^3 + x + 1$ over $\mathbb{R}$, algebraically show why adding point $P$ to its reflection $-P$ results in the point at infinity ($\mathcal{O}$).
• Discrete Logarithm Challenge: Explain why finding $k$ in the equation $Q = kP$ (where $P$ and $Q$ are known points on an elliptic curve over $F_p$) is computationally infeasible for large primes.