Mathematical Foundations of Cryptography

Mathematical Foundations of Cryptography

Modern cryptographic systems derive their security guarantees from the computational intractability of specific mathematical problems. Before examining how these problems are embedded within encryption schemes, hash functions, and digital signature algorithms, one must first establish a rigorous understanding of the underlying mathematical structures. This chapter develops the essential mathematical vocabulary and theoretical framework that will recur throughout the subsequent chapters of this volume. We begin with modular arithmetic—the arithmetic of remainders that forms the backbone of public-key cryptography—before progressing to group theory and finite field mathematics. These algebraic structures provide the formal language necessary for describing how cryptographic primitives operate and why they resist attack.

The mathematical foundations presented here are not merely academic exercises; they directly inform the design decisions and security analyses that appear in later chapters. Understanding why certain groups are chosen for Diffie-Hellman key exchange, why elliptic curves provide advantages over integer factorization, and why the security of RSA depends critically on the distribution of prime numbers—these insights emerge only from grappling with the mathematics at a fundamental level. The reader who masters the concepts in this chapter will possess the analytical tools required to evaluate cryptographic constructions and assess the validity of security claims.

Modular Arithmetic and Congruence Relations

The Algebra of Remainders

Modular arithmetic, sometimes called "clock arithmetic," operates on the principle of wrapping values around a fixed modulus. When we say that two integers $a$ and $b$ are congruent modulo $n$, written $a \equiv b \pmod{n}$, we mean that $n$ divides the difference $a - b$. Equivalently, $a$ and $b$ leave the same remainder when divided by $n$. This seemingly simple concept gives rise to a rich algebraic structure with properties that prove extraordinarily useful in cryptographic applications.

The set of integers modulo $n$, denoted $\mathbb{Z}_n$ or $\mathbb{Z}/n\mathbb{Z}$, consists of the equivalence classes $\{0, 1, 2, \ldots, n-1\}$ where two numbers are considered equivalent if they differ by a multiple of $n$. Within this set, we can define addition, subtraction, and multiplication operations that produce results within the set—these operations are said to be closed on $\mathbb{Z}_n$. The formal definition proceeds as follows: for any $a, b \in \mathbb{Z}_n$, we define $a + b \pmod{n}$ as the unique element $c \in \{0, 1, \ldots, n-1\}$ such that $c \equiv a + b \pmod{n}$, with analogous definitions for subtraction and multiplication.

These operations satisfy the familiar axioms of a commutative ring: addition forms an abelian group, multiplication is associative and commutative with an identity element, and multiplication distributes over addition. However, division presents complications. Not all elements in $\mathbb{Z}_n$ possess multiplicative inverses—that is, for a given $a$, there may not exist $b$ such that $ab \equiv 1 \pmod{n}$. An element $a$ is invertible in $\mathbb{Z}_n$ if and only if $\gcd(a, n) = 1$, meaning $a$ and $n$ share no common factors other than 1. The set of invertible elements in $\mathbb{Z}_n$ forms a multiplicative group denoted $\mathbb{Z}_n^*$, whose structure is central to many cryptographic constructions.

Extended Euclidean Algorithm and Modular Inverses

The existence of multiplicative inverses in $\mathbb{Z}_n^*$ connects to the extended Euclidean algorithm, which computes the greatest common divisor of two integers while simultaneously expressing this gcd as a linear combination of the inputs. Given $a$ and $n$, if $\gcd(a, n) = 1$, the extended Euclidean algorithm produces integers $x$ and $y$ such that $ax + ny = 1$. Reducing this equation modulo $n$ yields $ax \equiv 1 \pmod{n}$, showing that $x$ is the modular inverse of $a$.

This algorithm operates recursively by exploiting the identity $\gcd(a, n) = \gcd(n \bmod a, a)$. The extended version maintains coefficients tracking how each remainder relates to the original inputs, allowing recovery of the Bézout coefficients $x$ and $y$. In cryptographic implementations, this algorithm appears repeatedly—in RSA decryption where the private exponent is computed as the modular inverse of the public exponent modulo $\phi(n)$, in Diffie-Hellman parameter generation, and in numerous elliptic curve operations.

The computational complexity of the extended Euclidean algorithm is $O(\log \min(a, n))$ arithmetic operations on numbers of size $O(\log n)$ bits, making it efficient for the large integers encountered in cryptographic practice. Implementations often use the binary variant, which replaces division with subtraction and bit-shifting operations, achieving constant-time execution that resists timing side-channel attacks.

Euler's Totient Function and Counting Invertible Elements

Euler's totient function $\phi(n)$ counts the number of positive integers less than or equal to $n$ that are coprime to $n$—equivalently, the size of the multiplicative group $\mathbb{Z}_n^*$. For a prime power $p^k$, we have $\phi(p^k) = p^k - p^{k-1} = p^k(1 - 1/p)$. For a general integer $n = \prod_{i=1}^r p_i^{e_i}$ with distinct prime factors $p_i$, the function is multiplicative:

$$\phi(n) = n \prod_{i=1}^r \left(1 - \frac{1}{p_i}\right)$$

This multiplicative property follows from the Chinese Remainder Theorem, which we examine later in this chapter. For cryptographic purposes, $\phi(n)$ appears directly in RSA: given $n = pq$ for distinct primes $p$ and $q$, we have $\phi(n) = (p-1)(q-1)$. The security of RSA depends partly on the difficulty of computing $\phi(n)$ from $n$ when the factorization is unknown—a connection we explore further when examining computational hardness assumptions.

The distribution of $\phi(n)$ values and the density of invertible elements in $\mathbb{Z}_n$ have implications for key generation procedures. Approximately $1 - 1/p$ fraction of elements in $\mathbb{Z}_{p^k}$ are invertible, approaching 1 rapidly as $p$ grows. For RSA moduli of typical sizes (1024 to 4096 bits), the probability that a randomly chosen element is invertible exceeds $1 - 2^{-1024}$, effectively guaranteeing success in random invertible element generation.

Group Theory Foundations

Algebraic Structures and Their Properties

Group theory provides the abstract framework within which we describe the algebraic objects that underpin modern cryptography. A group $(G, \cdot)$ consists of a set $G$ together with a binary operation $\cdot: G \times G \to G$ satisfying three axioms: closure (the product of any two elements lies in $G$), associativity (for all $a, b, c \in G$, we have $(a \cdot b) \cdot c = a \cdot (b \cdot c)$), and the existence of an identity element $e$ such that $e \cdot a = a \cdot e = a$ for all $a \in G$. If additionally every element has an inverse (for each $a \in G$ there exists $a^{-1} \in G$ with $a \cdot a^{-1} = a^{-1} \cdot a = e$), the group is called a group.

When the operation is commutative—meaning $a \cdot b = b \cdot a$ for all $a, b \in G$—the group is termed abelian. Additive notation $(G, +)$ is conventional for abelian groups, while multiplicative notation $(G, \cdot)$ is used for non-abelian groups or when the structure is not necessarily commutative. The groups arising in cryptography are predominantly abelian, though certain constructions involve non-abelian structures.

The order of a group is the cardinality of its underlying set, denoted $|G|$. A group may be finite or infinite; cryptographic applications exclusively employ finite groups because their size directly limits the computational resources required for exhaustive search. The order of an element $g \in G$ is the smallest positi