2. Mathematical Foundations of Cryptography

Introduction and Context

Cryptography is often presented through algorithms such as AES, RSA, elliptic-curve systems, and digital signatures. Yet secure implementation depends on mathematical ideas that are more fundamental than any particular algorithm. Modular arithmetic determines how values wrap around finite spaces; number theory explains divisibility, primes, inverses, and factorisation; finite fields provide the algebraic setting for many symmetric and asymmetric algorithms; probability and entropy describe uncertainty; and computational complexity clarifies what an attacker can feasibly compute.

These foundations are not merely theoretical. A cryptographic protocol may fail because a random-number generator produces predictable values, a modulus is poorly chosen, a key space is too small, or an assumption about computational difficulty is no longer defensible. Security engineers therefore need to reason mathematically about both the construction and its operating environment. This chapter develops that reasoning and connects it with practical decisions in key generation, encryption, authentication, digital signatures, and protocol design.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Apply modular arithmetic, congruences, and modular inverses to cryptographic problems.

2. Explain the role of primes, greatest common divisors, Euler’s theorem, and the Chinese Remainder Theorem.

3. Distinguish groups, rings, fields, and finite fields, and relate them to cryptographic algorithms.

4. Use probability, entropy, conditional probability, and the birthday bound to assess security.

5. Explain computational complexity, security parameters, reductions, and hardness assumptions.

6. Evaluate the importance of randomness and identify consequences of weak random-number generation.

7. Connect mathematical properties with practical security engineering and professional decision-making.

From Integers to Cryptographic Algebra

Congruence and modular arithmetic

For integers a, b, and a positive integer n, the expression

a ≡ b (mod n)

means that n divides a − b. Equivalently, a and b leave the same remainder when divided by n. Thus, 29 ≡ 5 (mod 12), because 29 − 5 = 24, which is divisible by 12.

Congruence is compatible with addition and multiplication:

• If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n).
• Under the same conditions, ac ≡ bd (mod n).

This permits calculations to be reduced after every operation. For example, 7 × 8 mod 5 = 56 mod 5 = 1. Cryptographic algorithms exploit this bounded arithmetic to operate over finite sets while preserving useful algebraic structure.

The set of residue classes modulo n is commonly written Z_n. When discussing multiplication, it is important to distinguish all residues from those relatively prime to n. The latter form the multiplicative group Z_n*.

Greatest common divisors and inverses

The greatest common divisor, written gcd(a, b), is the largest positive integer dividing both a and b. Two integers are relatively prime when their greatest common divisor is 1.

A modular inverse of a modulo n is an integer a⁻¹ such that:

aa⁻¹ ≡ 1 (mod n).

The inverse exists if and only if gcd(a, n) = 1. For example, 3⁻¹ mod 7 is 5, because 3 × 5 = 15 ≡ 1 mod 7. In contrast, 2 has no inverse modulo 6 because gcd(2, 6) = 2.

The extended Euclidean algorithm efficiently computes gcd(a, n) and, when the gcd is 1, coefficients x and y satisfying:

ax + ny = 1.

Reducing x modulo n produces a⁻¹. This algorithm is central to RSA key generation, elliptic-curve calculations, and many finite-field operations.

Exponentiation and repeated squaring

Cryptographic systems frequently calculate x^e mod n for very large e. Direct multiplication is inefficient, but repeated squaring reduces the number of operations to approximately the logarithm of e. The method expresses e in binary, repeatedly squares the base, and multiplies only for binary positions containing 1.

The distinction between a mathematical operation and its efficient implementation is significant. Modular exponentiation is computationally feasible even for very large integers, whereas reversing it—recovering an exponent or solving a related problem—may be difficult under appropriate assumptions.

Number Theory as a Security Resource

Prime numbers and Euler’s totient function

A prime number has exactly two positive divisors: 1 and itself. Prime numbers are important because they generate simple algebraic structures and because certain problems involving large primes are believed to be computationally difficult.

Euler’s totient function, φ(n), counts the positive integers no greater than n that are relatively prime to n. If p is prime, φ(p) = p − 1. If p and q are distinct primes, then:

φ(pq) = (p − 1)(q − 1).

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

a^φ(n) ≡ 1 (mod n).

For prime p, this gives Fermat’s little theorem: a^(p−1) ≡ 1 (mod p) whenever p does not divide a. These results explain why exponentiation can be reversed in RSA when keys are constructed correctly.

The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) states that if m and n are coprime, a system such as

x ≡ a (mod m), x ≡ b (mod n)

has a unique solution modulo mn. CRT also generalises to more than two pairwise coprime moduli.

In RSA implementations, CRT permits decryption modulo p and q separately, followed by recombination. This can substantially improve performance. However, CRT introduces an implementation concern: a fault in one partial computation may reveal information about the private key. Consequently, robust implementations use verification or fault-detection techniques.

Hard number-theoretic problems

Cryptography does not depend on the statement that a mathematical problem is impossible. It depends on the expectation that solving it is infeasible with available resources. Examples include:

• Integer factorisation: Given N = pq, recovering p and q when they are large primes.
• Discrete logarithm: Given g and y = g^x in a suitable group, recovering x.
• Computational Diffie–Hellman problem: Given g, g^a, and g^b, computing g^(ab).
• Elliptic-curve discrete logarithm problem: The analogous problem in an elliptic-curve group.

These assumptions are domain-specific. A problem may be hard in one group and easy in another, or secure at one parameter size and inadequate at another. Security analysis must therefore consider the exact mathematical structure, not merely the name of an algorithm.

Groups, Rings, and Finite Fields

A group is a set with an operation satisfying closure, associativity, an identity element, and inverses. If the operation is commutative, the group is abelian. Groups provide the abstract structure behind many public-key systems.

A ring supports addition and multiplication, with addition forming an abelian group and multiplication being associative and distributive over addition. The integers modulo n form a ring, but they do not always form a field.

A field is a ring in which every nonzero element has a multiplicative inverse. A finite field contains a finite number of elements and is commonly denoted GF(q), where q is a prime power. Finite fields exist precisely for sizes q = p^m, with p prime and m a positive integer.

When q is prime, GF(q) can be represented by integers modulo q. When q = p^m with m greater than 1, field elements are represented using polynomials over GF(p), reduced modulo an irreducible polynomial of degree m. The irreducibility condition plays a role similar to primality: it ensures that every nonzero element has an inverse.

AES operates on bytes and uses arithmetic related to GF(2^8). In this setting, addition is bitwise exclusive OR, and multiplication is polynomial multiplication reduced by a fixed irreducible polynomial. This explains why AES operations are not ordinary integer arithmetic and why implementation errors in finite-field multiplication can compromise correctness.

Elliptic-curve cryptography uses points on a curve over a finite field. The points, together with a specially defined addition operation, form a group. Scalar multiplication—repeatedly adding a point to itself—is easy to compute, while recovering the scalar from a point and its product is assumed to be difficult for properly selected curves and parameters.

Probability, Uncertainty, and Entropy

Cryptographic security is fundamentally about uncertainty. If an adversary can predict a key, nonce, password-derived value, or protocol decision, an otherwise sound algorithm may fail.

Probability and conditional probability

For an event A, probability P(A) measures its likelihood. Conditional probability is written P(A|B), meaning the probability of A given that B has occurred. The relation

P(A|B) = P(A ∩ B) / P(B)

is useful when analysing authentication failures, attack paths, and information leakage.

Independence means that knowing one event does not change the probability of another: P(A|B) = P(A). Cryptographic constructions often seek outputs that are computationally indistinguishable from independent random values, even though they are generated deterministically from a key.

Entropy

Entropy quantifies uncertainty. For a discrete random variable X with outcomes x, Shannon entropy is:

H(X) = −Σ P(x) log₂ P(x).

Entropy is measured in bits. A uniformly selected value from 2^k possibilities has k bits of entropy. A biased distribution has less entropy than a uniform distribution with the same number of possible outcomes.

For example, a six-sided die has entropy log₂6, approximately 2.585 bits, when fair. If one outcome is much more likely than the others, the entropy decreases. The number of possible values is therefore not sufficient to determine security; the distribution used to select them matters.

Min-entropy is often especially relevant to guessing attacks. It is defined as:

H∞(X) = −log₂(max P(x)).

It focuses on the most likely outcome and is useful when estimating an attacker’s best single guess.

Birthday phenomena

The birthday effect explains why collisions appear sooner than intuition may suggest. For a hash function with an n-bit output, a generic collision attack typically requires about 2^(n/2) evaluations, not 2^n. This is the birthday bound.

The implication is important: a 128-bit hash output offers approximately 64-bit generic collision resistance, assuming no better attack is known. This does not mean that finding a preimage also requires 2^64 operations; preimage resistance and collision resistance are different properties.

Computational Complexity and Security Reasoning

Computational complexity studies how resource requirements grow with input size. Polynomial-time algorithms are generally treated as feasible in cryptographic models, while exponential-time algorithms are generally infeasible for sufficiently large parameters. This is an approximation rather than a universal law: constants, hardware, parallelism, memory, and specialised algorithms all matter.

A security parameter, often denoted λ, controls the intended difficulty of attacks. Increasing λ should increase the cost of the best known attack sufficiently to meet a defined security target. Parameters must therefore be selected based on current cryptanalysis, expected system lifetime, and available adversarial resources.

Reductions and security definitions

A reduction argues that breaking a cryptographic construction would allow an adversary to solve a presumed hard problem. For example, a proof may show that an efficient attacker against a scheme could be transformed into an efficient solver for a number-theoretic problem. A reduction does not prove that the underlying assumption is true; it connects the construction’s security to that assumption.

Security definitions specify what an attacker may do and what constitutes success. Examples include indistinguishability under chosen-plaintext attack, existential unforgeability under chosen-message attack, and authenticated encryption security. A mathematically secure primitive can still be used insecurely if the protocol provides the adversary with capabilities not covered by the assumed model.

Security is not a single number

Security strength depends on the weakest relevant component. A system may use a strong cipher but a predictable key, a secure hash but an unsafe password policy, or a sound public-key algorithm with a vulnerable implementation. Effective security is therefore a system property involving algorithms, parameters, randomness, code, protocols, users, and operational controls.

Randomness and the Cryptographic Boundary

Cryptographic randomness must be unpredictable to an adversary. A conventional pseudorandom number generator may produce statistically plausible output but still be unsuitable if its internal state can be guessed or reconstructed. Cryptographic pseudorandom generators are designed so that their output is computationally indistinguishable from random, provided that the seed has sufficient entropy and the generator is correctly implemented.

A cryptographically secure random-number generator should be seeded from an operating-system or hardware entropy source, protect its internal state, support reseeding where appropriate, and prevent output prediction after partial compromise as far as its design allows. Randomness is required for keys, nonces, salts, authentication challenges, ephemeral secrets, blinding values, and many signature schemes.

A nonce need not always be secret, but it must satisfy the uniqueness or unpredictability requirement of the relevant construction. Reusing a nonce in a stream cipher or an authenticated-encryption mode can reveal relationships between plaintexts or permit forgery. In contrast, a salt is usually public and is intended to prevent identical passwords from producing identical stored values and to frustrate precomputed attacks.

Applied Scenario: Failure of a Predictable Session-Key Generator

Background

Consider an illustrative financial application that establishes encrypted sessions between mobile clients and a server. The application uses a modern authenticated-encryption algorithm, but an early version generates session keys by seeding a standard pseudorandom generator with the current time in seconds.

Situation and analysis

An attacker observes the approximate time at which a victim logs in. The possible seed space is small because the login time can be bounded to a few minutes. The attacker reproduces candidate generator outputs and tests them against captured protocol data. Although the encryption algorithm itself is computationally strong, the effective key entropy is limited by the timestamp seed rather than by the nominal key length.

The failure illustrates several principles. First, the output length of a key does not establish its entropy. Second, cryptographic security depends on the unpredictability of inputs to the generator. Third, a secure primitive cannot compensate for a weak key-generation process. Finally, security analysis must consider the adversary’s auxiliary information, such as timestamps and protocol structure.

Remediation and outcome

The engineering team replaces the generator with the platform’s cryptographically secure random-number facility, obtains keys directly from a protected entropy pool, and adds automated tests that reject unsuitable randomness APIs. Existing sessions are invalidated, affected credentials are rotated, and monitoring is introduced for suspicious reuse or replay. A security review also verifies nonce generation and key separation between encryption and authentication functions.

The application’s algorithm did not need to be replaced; the failure occurred at the mathematical and operational boundary surrounding key generation. The principal lesson is that security strength must be assessed end to end.

Challenges, Limitations, and Common Mistakes

Several errors recur in cryptographic engineering:

• Treating a large range of possible values as equivalent to high entropy.
• Assuming that a difficult problem is difficult for every parameter choice or group.
• Confusing collision resistance with preimage resistance.
• Using ordinary random functions for keys, nonces, or salts.
• Reusing nonces because they are not secret.
• Ignoring side-channel leakage from timing, power consumption, memory access, or faults.
• Relying on a proof while implementing a protocol outside the proof’s assumptions.
• Selecting parameters once and never reassessing them as algorithms and hardware improve.

Mathematical models also have limitations. Complexity classifications do not predict exact attack costs, and asymptotic notation can conceal important constants. Hardness assumptions are supported by evidence and cryptanalysis, not absolute proof of universal difficulty. Quantum algorithms may also change the status of currently relied-upon problems, particularly integer factorisation and discrete logarithms.

Professional and Governance Considerations

Security professionals should document algorithm choices, parameter sizes, threat models, randomness sources, key lifetimes, and assumptions. Cryptographic agility—the ability to replace algorithms and parameters without redesigning an entire system—is increasingly important. Organisations should follow applicable standards and validated implementation guidance rather than inventing primitives or protocols.

Key management deserves governance equal to algorithm selection. Policies should address generation, storage, distribution, rotation, revocation, backup, destruction, access separation, and auditability. In regulated environments, evidence that approved algorithms and validated modules are used may be as important as the mathematical design itself.

Current Developments

Post-quantum cryptography is reshaping parameter selection and migration planning. Quantum algorithms threaten some classical public-key assumptions, while symmetric cryptography and cryptographic hashing are affected differently. Current practice therefore includes inventorying public-key dependencies, designing crypto-agile systems, and evaluating standardised post-quantum mechanisms.

Automated cryptographic analysis tools can check algebraic properties, protocol models, implementation correctness, and configuration errors. Formal verification and symbolic analysis are particularly useful for identifying whether a protocol actually achieves its stated security goal. Nevertheless, tools depend on accurate models and cannot eliminate the need for expert judgement about assumptions, deployment, and human behaviour.

Best Practices for Mathematical Security Reasoning

1. State the security goal and adversary model before selecting an algorithm.

2. Identify the exact hardness assumption and parameter set on which security depends.

3. Use standard, peer-reviewed primitives and well-reviewed libraries.

4. Obtain randomness from a cryptographically secure, operating-system-supported source.

5. Distinguish secrecy, unpredictability, uniqueness, and collision resistance.

6. Analyse the weakest component, including implementation and key management.

7. Account for side channels, faults, misuse, and operational exposure.

8. Document assumptions and plan for cryptographic migration.

9. Test mathematical edge cases, including zero, identity elements, non-invertible values, and malformed inputs.

10. Treat security proofs as conditional arguments, not substitutes for engineering review.

Chapter Summary

Cryptographic security rests on mathematical structure and computational assumptions. Modular arithmetic enables bounded operations, while the Euclidean algorithm provides inverses. Prime numbers, Euler’s theorem, and the Chinese Remainder Theorem support public-key constructions. Groups, rings, and finite fields provide the algebraic environments used by RSA, AES, and elliptic-curve systems. Probability and entropy describe uncertainty, and the birthday bound explains why hash collision security is roughly half the output length in bits. Complexity theory frames feasibility through security parameters, reductions, and hardness assumptions. Secure randomness is essential because weak or predictable values can defeat strong algorithms. In professional practice, mathematical reasoning must be combined with sound implementation, key management, governance, side-channel awareness, and migration planning.

Key Terms

Modular arithmetic: Arithmetic in which values are considered equivalent when they have the same remainder modulo a specified integer.

Congruence: A relation a ≡ b (mod n) indicating that n divides a − b.

Greatest common divisor: The largest positive integer that divides two given integers.

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

Extended Euclidean algorithm: An algorithm that computes greatest common divisors and coefficients useful for finding modular inverses.

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

Chinese Remainder Theorem: A theorem that combines compatible congruences with coprime moduli into a unique solution modulo their product.

Group: A set with an operation satisfying closure, associativity, identity, and inverse requirements.

Ring: An algebraic structure supporting addition and multiplication with distributive operations.

Field: A ring in which every nonzero element has a multiplicative inverse.

Finite field: A field containing a finite number of elements, usually of size p^m.

Entropy: A measure of uncertainty in a probability distribution.

Min-entropy: An entropy measure determined by the probability of the most likely outcome.

Birthday bound: The approximate 2^(n/2) work needed for a generic collision attack on an n-bit hash output.

Security parameter: A parameter controlling the intended computational difficulty of attacks.

Hardness assumption: An assumption that a specified computational problem is infeasible for an adversary.

Reduction: An argument connecting the security of a construction to the difficulty of another problem.

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

Cryptographically secure pseudorandom generator: A generator whose output is computationally unpredictable or indistinguishable from random under stated assumptions.

Cryptographic agility: The capability to replace algorithms or parameters without redesigning the complete system.

Review Questions

Short Answer Questions

1. Under what condition does a modular inverse of a modulo n exist?

2. State Euler’s theorem and identify its required condition.

3. Why are finite fields useful in cryptographic algorithms?

4. What does entropy measure in a random variable?

5. Why is a nonce not necessarily required to be secret?

Long Answer Questions

1. Explain modular arithmetic, the extended Euclidean algorithm, and their roles in RSA or elliptic-curve implementations.

2. Compare groups, rings, and fields, and explain how GF(2^8) is relevant to AES.

3. Discuss the relationship between computational complexity, security parameters, and hardness assumptions.

4. Explain Shannon entropy, min-entropy, and the birthday bound, including their practical security implications.

5. Describe how weak randomness can compromise a cryptographic system even when strong encryption is used.

Analytical / Application Questions

1. An application generates 128-bit session keys using a generator seeded by a 20-bit timestamp-derived value. Analyse the effective security and recommend a remediation.

2. A system uses a 256-bit hash and requires collision resistance. Explain why the generic security level is approximately 128 bits and discuss whether this is sufficient for a stated threat model.

3. An RSA implementation uses CRT but does not verify its two partial computations. Analyse the potential risk and recommend implementation controls.

22. Multiple Choice Questions with Answers

Question 1

Which condition is necessary and sufficient for a modular inverse of a modulo n to exist?

A. a must be prime

B. n must be even

C. gcd(a,n) must equal 1

D. a must be greater than n

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

Question 2

What does the Chinese Remainder Theorem allow an implementation to do when moduli are coprime?

A. Replace multiplication with addition in every field

B. Combine compatible modular results into a unique result modulo the product

C. Guarantee that discrete logarithms are easy

D. Generate entropy without a random source

Correct Answer: B. Combine compatible modular results into a unique result modulo the product

Question 3

Why does AES use arithmetic associated with GF(2^8)?

A. Because every byte can be treated as an element of a finite field

B. Because integer division is unavailable in modern processors

C. Because GF(2^8) eliminates the need for keys

D. Because finite fields provide unlimited values

Correct Answer: A. Because every byte can be treated as an element of a finite field

Question 4

A uniformly selected value has 2^40 possible outcomes. What is its Shannon entropy?

A. 20 bits

B. 40 bits

C. 80 bits

D. 2^40 bits

Correct Answer: B. 40 bits

Question 5

For an ideal hash function with an n-bit output, the generic work factor for finding a collision is approximately:

A. 2^n

B. 2^(n/2)

C. n^2

D. log₂(n)

Correct Answer: B. 2^(n/2)

Question 6

Which statement best distinguishes a hardness assumption from a security proof?

A. A hardness assumption is a conditional belief about computational difficulty; a proof connects security to that assumption

B. A hardness assumption proves that all attacks are impossible

C. A security proof guarantees secure implementation in every environment

D. There is no difference between the two

Correct Answer: A. A hardness assumption is a conditional belief about computational difficulty; a proof connects security to that assumption

Question 7

A cryptographic key is generated by a standard pseudorandom generator seeded with the current time. What is the primary mathematical weakness?

A. The key is too long to use efficiently

B. The possible seed space may be small and predictable

C. Time values cannot be represented as integers

D. Modular arithmetic no longer applies

Correct Answer: B. The possible seed space may be small and predictable

Question 8

Which statement about a nonce is generally correct?

A. It must always be kept secret

B. It may be public, but the construction may require it to be unique or unpredictable

C. It can safely be reused in every authenticated-encryption operation

D. It is identical to a password salt in every purpose

Correct Answer: B. It may be public, but the construction may require it to be unique or unpredictable

Question 9

What is the main reason that increasing a security parameter can improve security?

A. It makes all algorithms mathematically perfect

B. It increases the intended computational cost of the best known attacks

C. It removes the need for key management

D. It guarantees resistance to unknown future algorithms

Correct Answer: B. It increases the intended computational cost of the best known attacks

Question 10

Why can RSA-CRT improve performance while also creating an implementation risk?

A. It removes the private key from the device

B. It performs computations modulo smaller factors, but faulty partial results may leak key information

C. It replaces primes with random bytes

D. It prevents all side-channel attacks automatically

Correct Answer: B. It performs computations modulo smaller factors, but faulty partial results may leak key information