Mathematical Foundations of Cryptography

Introduction

Cryptography is applied mathematics used to protect information against unauthorized disclosure, alteration, impersonation, and denial of service. Modern cryptographic systems depend not on secrecy of their algorithms, but on carefully studied mathematical structures and computational assumptions. Modular arithmetic supports block ciphers and public-key systems; prime numbers and finite fields support key generation and algebraic operations; probability and entropy quantify uncertainty; computational complexity explains what an attacker can feasibly compute; and security notions define what it means for a construction to be secure.

This chapter develops the mathematical vocabulary required to understand and evaluate cryptographic algorithms. The emphasis is not merely on calculation, but on the assumptions behind calculations and on the distinction between mathematical truth and computational security.

Learning Objectives

After completing this chapter, you should be able to:

• perform modular arithmetic and use the Euclidean algorithm;
• explain prime numbers, greatest common divisors, inverses, and congruences;
• describe finite fields and their relevance to cryptography;
• calculate probability, entropy, min-entropy, and collision likelihood;
• distinguish polynomial-time computation from infeasible computation;
• explain randomness, pseudorandomness, and cryptographic unpredictability;
• state important number-theoretic assumptions used in public-key cryptography;
• distinguish computational, statistical, and perfect security;
• apply these concepts to cryptographic design and risk analysis.

1. Integers, Divisibility, and Congruence

The integers are denoted by ℤ. For integers a and b, with b ≠ 0, we say that b divides a, written b ∣ a, if there exists an integer k such that a = bk. For example, 3 ∣ 21 because 21 = 3 × 7.

The greatest common divisor of a and b, written gcd(a,b), is the largest positive integer dividing both. Two integers are relatively prime when gcd(a,b) = 1. Relative primality is central to modular inversion and RSA.

The division algorithm states that for any integer a and positive integer n, there exist unique integers q and r such that:

Here q is the quotient and r is the remainder. The expression a mod n denotes r. Congruence modulo n is defined by:

Thus 29 ≡ 5 (mod 12), because 29 − 5 = 24, which is divisible by 12. Congruence permits addition, subtraction, and multiplication:

Exponentiation can therefore be performed by repeated squaring, reducing after each multiplication. This is essential when exponents are hundreds or thousands of bits long.

Worked Example: Modular Exponentiation

Compute 7^13 mod 20. Since 13 = 8 + 4 + 1:

• 7^2 ≡ 49 ≡ 9 (mod 20)
• 7^4 ≡ 9^2 = 81 ≡ 1 (mod 20)
• 7^8 ≡ 1^2 ≡ 1 (mod 20)

Therefore:

The calculation is exact because every reduction is performed modulo 20.

2. Euclid’s Algorithm and Modular Inverses

The Euclidean algorithm computes gcd(a,b) through repeated division. If a = qb + r, then:

The extended Euclidean algorithm also finds integers x and y satisfying Bézout’s identity:

If gcd(a,n) = 1, then a has a multiplicative inverse modulo n. The inverse, written a⁻¹ mod n, is the value x satisfying:

An inverse exists if and only if a and n are relatively prime.

Worked Example: Finding an Inverse

Find 17⁻¹ mod 43. Applying the Euclidean algorithm:

Back-substitution gives:

Thus −5·17 ≡ 1 (mod 43), so 17⁻¹ ≡ −5 ≡ 38 (mod 43). Verification: 17 × 38 = 646 ≡ 1 (mod 43).

3. Prime Numbers and Arithmetic Functions

A prime number is an integer greater than 1 with exactly two positive divisors: 1 and itself. Every integer greater than 1 has a unique prime factorization, apart from ordering. This is the Fundamental Theorem of Arithmetic.

Primes are used in cryptography because factoring a large composite number into its prime factors is believed to be computationally difficult when the factors are suitably chosen. This statement is about computational difficulty, not mathematical impossibility.

Euler’s totient function φ(n) counts the integers in {1, …, n} that are relatively prime to n. If p is prime:

If p and q are distinct primes:

Euler’s theorem states that if gcd(a,n) = 1, then:

Fermat’s little theorem is the special case where n = p is prime:

These theorems justify exponent reduction in some cryptographic computations. They must not be applied when their coprimality or primality conditions are absent.

4. Groups, Rings, and Fields

Abstract algebra provides a common language for cryptographic operations.

A group is a set G with an operation satisfying closure, associativity, an identity element, and inverses. A group is abelian if the operation is commutative. The integers modulo n under addition form the group ℤ_n. The invertible elements modulo n form the multiplicative group ℤ_n^*.

A ring supports addition and multiplication, with addition forming an abelian group and multiplication being associative and distributive over addition. ℤ_n is a ring, but it may contain zero divisors. For example, in ℤ_8, 2 × 4 ≡ 0 (mod 8), although neither factor is zero modulo 8.

A field is a commutative ring in which every nonzero element has a multiplicative inverse. The integers modulo p form a field GF(p) exactly when p is prime. Finite fields are also written GF(q), where q = p^m for a prime p and positive integer m.

Finite fields are important because they provide predictable algebraic operations over a finite set. AES uses the field GF(2^8) for byte-oriented transformations. Elliptic-curve cryptography uses groups of points defined over finite fields.

Polynomial Representation in GF(2^m)

In GF(2), coefficients are either 0 or 1 and addition is XOR. A field GF(2^m) can be constructed using polynomials of degree less than m, with arithmetic performed modulo an irreducible polynomial of degree m. An irreducible polynomial cannot be factored into lower-degree nonconstant polynomials over GF(2).

For AES, bytes are interpreted as polynomials over GF(2) and reduced modulo an irreducible polynomial of degree 8. The field structure ensures that every nonzero byte has a multiplicative inverse, a property used in the S-box. This is not ordinary integer arithmetic modulo 256: GF(256) has characteristic 2 and uses polynomial reduction.

5. Probability and Random Variables in Cryptography

Probability models uncertainty about keys, messages, adversarial choices, and algorithmic outcomes. A random variable X maps outcomes to values. Its probability mass function is P(X = x), with:

For events A and B, conditional probability is:

Bayes’ theorem is:

Independence means P(A ∩ B) = P(A)P(B). Cryptographic analyses often require careful attention to whether trials are independent. Sampling without replacement, repeated nonce use, and adaptive attacks can invalidate independence assumptions.

Birthday Bound

If a hash function has an n-bit output and behaves like a random function, a collision becomes likely after approximately 2^(n/2) trials rather than 2^n trials. A common approximation for q distinct random inputs is:

This approximation assumes independent uniform outputs and is most useful when q is not close to the full domain size. It explains why a 256-bit hash has roughly 128-bit collision security.

6. Entropy and Information

Entropy measures uncertainty. Shannon entropy of a discrete random variable X is:

The unit is bits when the logarithm is base 2. If X is uniform over N possibilities, then H(X) = log₂ N. Entropy is maximized by a uniform distribution.

Min-entropy is especially relevant to guessing attacks:

It measures the difficulty of guessing the most likely value. A password distribution can have high Shannon entropy while having low min-entropy if a small number of passwords are disproportionately common.

For independent variables X and Y, H(X,Y) = H(X) + H(Y). In general, the chain rule is:

Cryptographic keys should be generated from sources with sufficient min-entropy, not merely from long strings or apparently complex user input.

7. Complexity and Security Parameters

Computational complexity studies how resource requirements grow with input size. An algorithm is polynomial-time if its running time is bounded by O(n^k) for a constant k, where n is input length. Polynomial-time algorithms are generally treated as feasible in asymptotic cryptographic models, although constants and engineering constraints matter.

Exponential-time algorithms, such as O(2^n), become infeasible much more rapidly. Security parameters are chosen so that the best known attack requires resources beyond an acceptable threat budget.

Complexity notation includes:

• O(f(n)): an asymptotic upper bound;
• Ω(f(n)): an asymptotic lower bound;
• Θ(f(n)): a tight asymptotic bound.

Security estimates must consider time, memory, parallelism, hardware cost, data requirements, and attack success probability. A 128-bit security claim usually means that the best generic attack requires approximately 2^128 basic operations, not that every operation literally costs the same or that all attack types have this complexity.

Quantum computing changes some estimates. Grover’s algorithm can provide a quadratic speedup for generic search, reducing an ideal 2^n search to approximately 2^(n/2). Shor’s algorithm threatens classical factoring and discrete-logarithm assumptions. These results motivate post-quantum cryptography.

8. Randomness and Pseudorandomness

A true random source produces outcomes governed by a physical or mathematical random process. A pseudorandom generator (PRG) expands a short uniformly random seed into a longer sequence that is computationally indistinguishable from a uniform sequence.

A cryptographic PRG must resist efficient distinguishers. A cryptographically secure pseudorandom number generator (CSPRNG) also requires properties such as forward security or backtracking resistance, depending on its design and threat model.

Security depends on entropy collection, seeding, state protection, reseeding policy, and resistance to prediction. A deterministic generator with a secret, high-entropy seed can be cryptographically secure; a physically random source can still be insecure if its output is biased, observable, or poorly conditioned.

Nonces and initialization vectors require special treatment. Some algorithms require unpredictability; others require only uniqueness. Reusing a nonce in a stream cipher or authenticated-encryption mode can expose relationships between plaintexts and may completely undermine confidentiality.

9. Number-Theoretic Assumptions

Public-key cryptography relies on problems believed to be easy in one direction and difficult in the other.

Integer Factorization

Given primes p and q, computing N = pq is easy. Given N, recovering p and q is believed difficult for properly sized, randomly generated primes. RSA security is related to factoring, but RSA’s exact security does not automatically equal the factoring problem; padding and implementation conditions are essential.

Discrete Logarithm

In a cyclic group G generated by g, computing g^x is easy when x is known. Given g and g^x, finding x is the discrete logarithm problem. Diffie–Hellman systems rely on variants such as the computational Diffie–Hellman and decisional Diffie–Hellman assumptions.

Elliptic-Curve Groups

Elliptic-curve cryptography uses points satisfying an equation such as:

over a finite field, subject to a non-singularity condition. For fields of characteristic other than 2 or 3, the curve must satisfy:

The group operation is geometric in intuition but algebraic in implementation. The elliptic-curve discrete logarithm problem is believed difficult for carefully selected curves and parameters.

Assumptions are never absolute guarantees. They depend on parameter sizes, algorithmic advances, implementation correctness, and the attack model.

10. Security Notions

Perfect secrecy means that observing the ciphertext does not change the adversary’s probability distribution for the plaintext. Formally, an encryption scheme has perfect secrecy if for every message m and ciphertext c with positive probability:

The one-time pad achieves perfect secrecy when the key is uniformly random, at least as long as the message, used once only, and kept secret. These requirements make perfect secrecy costly.

Computational security permits a negligible probability of successful attack for any efficient adversary. A function μ(n) is negligible if, for every positive polynomial p(n), there exists N such that μ(n) < 1/p(n) for all n > N.

Indistinguishability-based definitions compare an adversary’s ability to distinguish two experiments. For example, semantic security requires that an efficient adversary learn no meaningful information from ciphertext beyond what was already available from public information. Modern encryption definitions commonly use IND-CPA and IND-CCA models, where the latter additionally allows carefully restricted decryption queries.

Authentication has corresponding notions. Message authentication codes are commonly evaluated under existential unforgeability under chosen-message attack (EUF-CMA). Digital signatures should prevent an efficient adversary from producing a valid signature on a new message after observing signatures on chosen messages.

Security proofs usually have the form: if a primitive could be attacked efficiently, then an underlying hard problem could also be solved efficiently. Such reductions may be tight or loose. A proof does not guarantee security if the model omits side channels, faulty randomness, weak parameters, or implementation errors.

11. Worked Application: Evaluating a Password-Derived Key

Consider an illustrative enterprise system that derives a 128-bit encryption key from a user password. The password database shows that the most common password has probability 2^−10, while the system documentation reports an average Shannon entropy of 35 bits.

The relevant guessing measure is min-entropy. Since the most likely password has probability 2^−10:

An offline attacker who obtains a password-verification record may test guesses without interacting with the service. A 128-bit cipher key does not provide 128 bits of effective security if the key is derived from a distribution whose easiest guesses are concentrated in only about 10 bits.

A sound approach is to use a memory-hard password-based key derivation function with a unique salt per account, calibrated work factors, rate controls where possible, and migration support for stronger parameters. The salt does not add secrecy; it prevents precomputed tables and forces separate computation for each account. The work factor increases attacker cost but does not create entropy. The fundamental remedy is improving password selection or using randomly generated secrets.

Learning points: key length, password entropy, derivation cost, and online rate limiting are different security variables. A design review must analyze all of them rather than quoting the cipher’s nominal key size.

12. Practical and Governance Implications

Cryptographic engineering should follow several principles:

1. Use standardized, peer-reviewed algorithms and approved parameter sets.
2. Use a well-reviewed cryptographic library rather than implementing primitives directly.
3. Generate keys and nonces with an operating-system CSPRNG.
4. Separate keys by purpose and use authenticated encryption where appropriate.
5. Document the threat model, security level, assumptions, and lifecycle.
6. Plan rotation, revocation, backup, recovery, and secure destruction.
7. Test failure paths, malformed inputs, timing behavior, and error handling.
8. Monitor developments in cryptanalysis and post-quantum migration.

Governance requires accountability for key custody, access control, auditability, privacy, and regulatory obligations. Cryptography can protect data, but it can also impede lawful recovery or incident investigation if key-management responsibilities are unclear. Automated and AI-assisted systems must not be trusted to generate secrets through ordinary language models or uncontrolled software randomness. AI may assist code review or threat analysis, but cryptographic decisions require expert validation and reproducible testing.

13. Limitations and Contemporary Developments

Mathematical security models simplify reality. They may assume ideal random functions, independent samples, noiseless computation, or adversaries limited to black-box access. Real systems leak through timing, power consumption, electromagnetic emissions, cache behavior, fault injection, and memory disclosure.

Post-quantum cryptography replaces factoring- and discrete-log-based mechanisms with constructions based on problems such as lattice learning, code decoding, hash-based signatures, and multivariate or isogeny-related structures. Each family has different assumptions, performance characteristics, and implementation risks. Migration requires inventorying cryptographic dependencies, prioritizing long-lived confidential data, and supporting algorithm agility without permitting downgrade attacks.

The most reliable evaluation therefore combines mathematical analysis, formal security definitions, implementation testing, independent review, operational controls, and continuous reassessment.

Chapter Summary

Cryptography rests on modular arithmetic, divisibility, prime numbers, groups, rings, and finite fields. Congruence and modular inverses support efficient arithmetic and public-key algorithms. Finite fields provide structured operations used by AES and elliptic-curve systems. Probability and entropy quantify uncertainty, with min-entropy being particularly useful for guessing resistance. Complexity theory distinguishes feasible from infeasible attacks and explains the role of security parameters. Randomness must be generated, conditioned, stored, and consumed correctly. Public-key systems rely on assumptions such as factoring and discrete-logarithm hardness, while security notions such as perfect secrecy, indistinguishability, and unforgeability define protection goals. Sound cryptographic evaluation must combine mathematical assumptions with implementation, operational, governance, and future-technology analysis.

Key Terms

Modular arithmetic: Arithmetic in which values are reduced by a fixed positive modulus.

Congruence: A relation indicating that two integers have the same remainder modulo n.

Greatest common divisor: The largest positive integer dividing two integers.

Bézout’s identity: An expression of the gcd as an integer combination of two values.

Modular inverse: A value that multiplies another value to produce 1 modulo n.

Prime number: An integer greater than 1 with exactly two positive divisors.

Euler’s totient function: The number of positive integers up to n that are relatively prime to n.

Group: An algebraic set with a closed operation, identity, associativity, and inverses.

Finite field: A finite algebraic field, commonly denoted GF(q).

Probability mass function: A function assigning probabilities to discrete outcomes.

Shannon entropy: Average uncertainty measured from a probability distribution.

Min-entropy: Uncertainty determined by the most likely outcome.

Birthday bound: The approximate collision threshold near the square root of an output space.

Computational complexity: Analysis of resource requirements as input size grows.

CSPRNG: A cryptographically secure pseudorandom number generator.

Perfect secrecy: Security in which ciphertext does not change plaintext probabilities.

Negligible function: A function eventually smaller than the reciprocal of every positive polynomial.

Security assumption: A computational or mathematical claim on which security depends.

Nonce: A value intended for one-time or unique use in a cryptographic operation.

Security parameter: A parameter controlling the intended computational security level.

Review Questions

Short Answer Questions

1. What condition is necessary and sufficient for a modular inverse of a modulo n to exist?
2. State Euler’s theorem and its coprimality condition.
3. Why is min-entropy useful in password security analysis?
4. What distinguishes a finite field from the ring ℤ_n when n is composite?
5. What is the purpose of a nonce in authenticated encryption?

Long Answer Questions

1. Explain the Euclidean and extended Euclidean algorithms, including a worked modular-inverse example.
2. Compare Shannon entropy, min-entropy, and uniform key generation in cryptographic systems.
3. Explain how finite fields support AES and elliptic-curve cryptography.
4. Discuss the relationship between computational complexity, security parameters, and practical attack cost.
5. Compare perfect secrecy with computational security and explain why the one-time pad is rarely used for general-purpose encryption.

Analytical / Application Questions

1. A system chooses one of 1,000 passwords uniformly. Calculate its Shannon entropy in bits and explain why a non-uniform real-world password distribution may have lower effective guessing security.
2. An n-bit hash is used for integrity protection. Explain why collision resistance is approximately n/2 bits and identify an appropriate output size for a target of about 128-bit collision security.
3. An application reuses a stream-cipher nonce with two different plaintexts. Analyze the information exposed and recommend design controls to prevent recurrence.

Multiple Choice Questions with Answers

Question 1

Which condition is necessary and sufficient for a to have a multiplicative inverse modulo n?

A. a is prime

B. n is prime

C. gcd(a,n) = 1

D. a is larger than n

Correct Answer: C. gcd(a,n) = 1

Question 2

What is 17⁻¹ modulo 43?

A. 5

B. 17

C. 38

D. 41

Correct Answer: C. 38

Question 3

Which structure is a field when p is prime?

A. ℤ_p

B. ℤ_8

C. The integers under multiplication

D. All composite integers modulo p

Correct Answer: A. ℤ_p

Question 4

For a uniform random variable over 256 possibilities, what is its Shannon entropy?

A. 4 bits

B. 8 bits

C. 128 bits

D. 256 bits

Correct Answer: B. 8 bits

Question 5

Which entropy measure is directly determined by the probability of the most likely guess?

A. Shannon entropy

B. Min-entropy

C. Conditional variance

D. Collision distance

Correct Answer: B. Min-entropy

Question 6

For an ideal 256-bit hash function, collision attacks require approximately what generic work factor?

A. 2^64

B. 2^128

C. 2^256

D. 256^2

Correct Answer: B. 2^128

Question 7

What does a cryptographically secure pseudorandom generator require from its seed?

A. It must be publicly predictable

B. It must contain sufficient unpredictable entropy

C. It must always be physically generated

D. It must be longer than every output

Correct Answer: B. It must contain sufficient unpredictable entropy

Question 8

Which problem is classically associated with RSA-style public-key cryptography?

A. Integer factorization

B. Sorting

C. Lossless compression

D. Linear regression

Correct Answer: A. Integer factorization

Question 9

Perfect secrecy requires which relationship for every relevant message m and ciphertext c?

A. P(M=m | C=c) = 0

B. P(M=m | C=c) = P(M=m)

C. P(C=c | M=m) = 1

D. P(M=m) = 1/2

Correct Answer: B. P(M=m | C=c) = P(M=m)

Question 10

Why does a password-derived 128-bit key not necessarily provide 128-bit security?

A. AES keys cannot contain 128 bits

B. Passwords may have low entropy and be efficiently guessed

C. Hash functions always remove all secrecy

D. Nonce uniqueness increases password predictability

Correct Answer: B. Passwords may have low entropy and be efficiently guessed