Mathematical and Information-Theory Foundations

Introduction

Cryptography is often presented through algorithms such as AES, RSA, and elliptic-curve cryptography. However, secure implementation depends on ideas that are more fundamental than any individual algorithm. Modular arithmetic explains how cryptographic calculations are performed; prime numbers and finite fields provide the mathematical structures used by public-key and symmetric cryptography; probability and entropy help describe uncertainty and secret strength; computational complexity explains why some problems are practical to solve while others are deliberately difficult.

This chapter develops these foundations at diploma level. The emphasis is on accurate concepts, practical interpretation, and the ability to perform basic calculations without requiring advanced mathematical proofs.

Learning Objectives

By the end of this chapter, you should be able to:

1. Perform basic modular arithmetic and explain its role in cryptography.
2. Identify prime numbers, greatest common divisors, and modular inverses.
3. Describe finite fields and explain why they are useful in cryptographic algorithms.
4. Use basic probability concepts to reason about guessing, collisions, and security events.
5. Explain entropy, min-entropy, randomness, and the difference between pseudorandom and truly random values.
6. Distinguish computational complexity from mathematical difficulty.
7. Explain why factoring, discrete logarithms, and related problems support public-key cryptography.
8. Apply these ideas to password security, key generation, authentication, and secure system design.

1. Mathematical Structures Used in Cryptography

A cryptographic algorithm transforms information according to precisely defined mathematical rules. A mathematical structure consists of a set of elements together with operations that satisfy particular properties. The most important structures in introductory cryptography are integers, modular residue classes, groups, rings, and fields.

A set is a collection of objects. An operation is closed on a set if applying it to members of the set produces another member of that set. For example, addition is closed on the integers because the sum of any two integers is an integer. Division is not closed on the integers because 1 ÷ 2 is not an integer.

These distinctions matter because cryptographic algorithms require operations that are predictable, efficiently computable, and suitable for reversibility or one-wayness.

2. Integers, Divisibility, and Prime Numbers

An integer a divides an integer b if there is an integer k such that:

This is written as a ∣ b. For example, 3 ∣ 12 because 12 = 3 × 4, but 3 does not divide 14.

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. The first primes are 2, 3, 5, 7, 11, and 13. The number 1 is not prime because it has only one positive divisor. An integer greater than 1 that is not prime is composite.

Prime numbers are important because every integer greater than 1 has a unique prime factorisation, apart from the order of factors. For example:

This property is central to the security intuition behind RSA. Multiplying two large primes is efficient, but recovering the primes from their product is believed to be computationally difficult when the primes are sufficiently large and properly generated.

Greatest Common Divisor

The greatest common divisor of integers a and b, written gcd(a, b), is the largest positive integer that divides both. For example:

Two integers are relatively prime, or coprime, when their greatest common divisor is 1. For instance, 8 and 15 are coprime even though neither number is prime.

The Euclidean algorithm efficiently calculates the greatest common divisor. It uses the identity:

for positive integers a and b with a ≥ b. The process ends when the remainder is zero.

Worked Example: Euclidean Algorithm

Calculate gcd(252, 105):

252 = 2 × 105 + 42

105 = 2 × 42 + 21

42 = 2 × 21 + 0

Therefore:

The Euclidean algorithm is used in cryptographic key generation and in finding modular inverses.

3. Modular Arithmetic

Modular arithmetic works with remainders. The expression a mod n is the remainder obtained when a is divided by n, where n is a positive integer. The notation

means that a and b have the same remainder when divided by n. Equivalently, n divides a − b.

For example:

because 17 − 5 = 12, which is divisible by 12.

The integers from 0 through n − 1 form the residue system modulo n:

Calculations are reduced after operations. For example:

and:

Modular arithmetic is useful in cryptography because it creates finite computational spaces. Values can grow during a calculation but are repeatedly reduced to remain within a defined range.

Addition, Subtraction, and Multiplication

For modulus n:

These rules allow calculations to be reduced at intermediate stages without changing the final result.

Modular Exponentiation

Public-key systems frequently calculate:

where a is a base, e is an exponent, and n is the modulus. Directly calculating a^e may be inefficient because the number can become extremely large. Algorithms such as repeated squaring calculate the result efficiently.

#### Worked Example

Calculate 3^5 mod 7:

3^2 = 9 ≡ 2 (mod 7)

3^4 ≡ 2^2 = 4 (mod 7)

3^5 ≡ 3^4 × 3 ≡ 4 × 3 = 12 ≡ 5 (mod 7)

Thus:

Modular Inverses

The modular inverse of a modulo n is a number a⁻¹ satisfying:

A modular inverse exists if and only if gcd(a, n) = 1. For example, the inverse of 3 modulo 7 is 5 because:

The inverse does not exist for 2 modulo 6 because gcd(2, 6) = 2, not 1.

The extended Euclidean algorithm finds modular inverses by expressing the greatest common divisor as a linear combination:

If gcd(a, n) = 1, then x is a modular inverse of a modulo n.

4. Groups, Rings, and Finite Fields

A group is a set with an operation satisfying closure, associativity, an identity element, and inverses for all elements. In cryptography, groups provide a controlled environment for operations such as addition or multiplication.

A ring supports addition, subtraction, and multiplication, with addition forming a group. The integers modulo n form a ring, commonly written Z_n.

A field is a set in which addition, subtraction, multiplication, and division by every nonzero element are defined and behave consistently. A finite field contains a finite number of elements. It is often written GF(q), where q is the number of elements and q is a prime power.

When p is prime, the integers modulo p form the finite field GF(p). Every nonzero element has a multiplicative inverse. For example, GF(5) contains {0, 1, 2, 3, 4}; the inverse of 2 is 3 because 2 × 3 = 6 ≡ 1 (mod 5).

Finite fields are used in:

• AES, which operates on bytes represented using GF(2^8).
• Elliptic-curve cryptography, which uses finite fields to define curve operations.
• Error-detecting and error-correcting codes.
• Secret-sharing and secure multiparty computation.

The field GF(2^8) is not simply the integers from 0 to 255 with ordinary arithmetic modulo 256. Its elements are polynomials with binary coefficients, and arithmetic is performed modulo an irreducible polynomial. This distinction is important when implementing AES.

5. Probability in Security

Probability measures uncertainty. For an event A, its probability is written P(A), with:

A probability of 0 means the event is impossible under the stated model, while a probability of 1 means it is certain.

The complement of A, written Aᶜ, has probability:

For mutually exclusive events A and B, the addition rule is:

If events are not mutually exclusive, the correct rule is:

For independent events, the probability that both occur is:

Independence must not be assumed merely because events appear unrelated. For example, repeated password guesses may not be independent if an attacker uses information from previous attempts.

Guessing Probability

If a secret is selected uniformly from N possible values, one guess succeeds with probability:

If an attacker makes g distinct guesses, and g ≤ N, the success probability is:

This assumes uniform selection, distinct guesses, and no additional information. If choices are biased, the probability depends on the distribution and may be much higher for common values.

Birthday Collisions

A collision occurs when two inputs produce the same output, such as two messages having the same hash value. For a hash function with an n-bit output, there are 2ⁿ possible outputs. The approximate number of randomly selected inputs needed for a 50% collision probability is:

This is the birthday bound. It explains why an n-bit hash provides approximately n/2 bits of collision resistance, not n bits. For SHA-256, collision resistance is conventionally estimated at approximately 2¹²⁸ operations under ideal assumptions.

6. Entropy and Information Content

Entropy measures uncertainty or average information. For a discrete random variable X with possible outcomes x₁, x₂, ..., xₙ and probabilities p(xᵢ), Shannon entropy is:

The unit is bits because the logarithm is base 2. The probabilities must satisfy:

Entropy is maximised when all outcomes are equally likely. If X is uniform over N outcomes:

#### Worked Example

A uniformly selected six-sided die has six possible outcomes. Its entropy is:

A fair coin has two equally likely outcomes and therefore has 1 bit of entropy.

If a password character is selected uniformly from 26 lowercase letters, the entropy per character is:

A uniformly random password of L characters from an alphabet of size A has entropy:

This formula does not apply accurately to human-created passwords because human choices are not uniform. A password such as “Password123” may have a large apparent search space but low effective entropy because it is predictable.

Min-Entropy

Shannon entropy describes average uncertainty. Security systems often need a worst-case measure. Min-entropy is:

It is determined by the most likely outcome. Min-entropy is particularly useful for passwords, biometric measurements, and random-number sources because attackers try the most probable guesses first.

7. Randomness and Pseudorandomness

Randomness is essential for keys, nonces, salts, initialization vectors, challenges, and authentication tokens. A random source should be unpredictable and should not allow an attacker to infer future outputs from past outputs.

A true random number generator, or TRNG, obtains randomness from a physical process such as electronic noise, oscillator variation, or radioactive decay. A pseudorandom number generator, or PRNG, expands a short internal state into a longer sequence using a deterministic algorithm.

A cryptographically secure pseudorandom number generator, or CSPRNG, is designed so that observing outputs does not make future or past outputs feasibly predictable, assuming the internal state remains protected and properly seeded.

Ordinary functions such as spreadsheet random functions or programming-language convenience generators are not automatically suitable for cryptography. Security software should use the operating system’s approved cryptographic random source or a vetted cryptographic library.

Randomness Failures

Common causes of failure include:

• predictable seeds, such as timestamps;
• insufficient entropy during system startup;
• reuse of nonces where uniqueness is required;
• poor library selection;
• exposing internal generator state;
• generating keys with ordinary statistical random functions.

Randomness is not the same as unpredictability. A sequence may pass simple statistical tests and still be predictable if its generating algorithm is known or its seed is weak.

8. Computational Complexity and Security

Computational complexity studies how resource requirements grow as input size increases. The principal resources are time and memory. Big-O notation describes an asymptotic upper-growth classification while ignoring constant factors.

Examples include:

• O(1): approximately constant time;
• O(log n): logarithmic growth;
• O(n): linear growth;
• O(n²): quadratic growth;
• O(2ⁿ): exponential growth.

An algorithm with O(n²) complexity may be acceptable for small inputs but expensive for large inputs. Exponential algorithms become infeasible rapidly, although complexity notation alone does not prove that an algorithm is secure.

Cryptographic security often depends on a problem being easy in one direction but difficult to reverse. Encryption should be efficient for legitimate users, while an attacker without the key should face a problem requiring excessive time or resources.

Security Parameters

A security parameter controls the intended work factor. Increasing a key size generally increases the attacker’s search space, but the relationship depends on the algorithm. A 256-bit symmetric key does not necessarily provide the same security level as a 256-bit RSA modulus or a 256-bit elliptic-curve key.

Security estimates also depend on the attacker model, available hardware, parallelism, implementation weaknesses, and future algorithms. Therefore, key sizes should follow current standards rather than informal comparisons.

9. Hard Mathematical Problems

Integer Factorisation

Given a composite integer n, factorisation asks for its prime factors. Multiplication is efficient, but factoring a properly generated large RSA modulus is believed to be difficult for classical computers. RSA security is not based on the claim that factoring is mathematically impossible; it is based on the expected computational cost of the best known relevant attacks under stated assumptions.

Discrete Logarithm Problem

In a cyclic group, given a generator g, an element y, and a relation:

finding x is the discrete logarithm problem. Computing y from g and x is generally efficient, while recovering x may be difficult in suitable groups.

Diffie–Hellman key exchange relies on related problems. Its security also requires correct parameter selection and protection against active attackers, including man-in-the-middle attacks.

Elliptic-Curve Problems

Elliptic-curve cryptography defines a group using points on a curve over a finite field. The elliptic-curve discrete logarithm problem asks for the integer k when given points P and Q = kP. For suitable curves, the best known classical attacks are much more expensive than comparable attacks against ordinary finite-field discrete logarithms, allowing smaller keys for similar classical security levels.

The mathematics is sophisticated, but the operational lesson is simple: use standardised curves and trusted libraries rather than designing new curves or implementing field arithmetic without expert review.

Quantum Considerations

A sufficiently capable quantum computer could use Shor’s algorithm to threaten widely deployed public-key systems based on factoring and discrete logarithms. Grover’s algorithm can provide a quadratic speedup for brute-force search against symmetric keys, reducing the idealised search cost of an n-bit key from approximately 2ⁿ to 2^(n/2). This does not make all symmetric encryption insecure, but it motivates appropriate key sizes and migration planning.

Post-quantum cryptography develops public-key algorithms intended to resist known classical and quantum attacks. Organisations should monitor standards and plan crypto-agility: the ability to replace cryptographic algorithms without redesigning an entire system.

10. Applied Case: Secure Password Reset Service

Background

This illustrative case concerns a university password-reset service. Users request a reset link, receive a token by email, and use the token once to create a new password.

Problem

An initial implementation generated tokens using a general-purpose pseudorandom function seeded with the current time. Tokens were stored in plaintext, remained valid for 48 hours, and could be reused. An attacker who learned the generation pattern could predict tokens or exploit leaked database records.

Analysis

The design failed at several foundational levels:

1. The token source was not a CSPRNG, so unpredictability was not established.
2. The token lifetime was unnecessarily long.
3. Plaintext storage meant database compromise immediately exposed active tokens.
4. Reuse created a replay opportunity.
5. The system did not adequately limit repeated requests or verify contextual information.

If a token is selected uniformly from 2¹²⁸ possibilities, a single blind guess has probability 1/2¹²⁸. That estimate is meaningful only if the token is genuinely unpredictable, the attacker cannot make unlimited attempts, and the token is invalidated after use.

Approach and Solution

The service should:

• generate tokens with an approved CSPRNG;
• use sufficient length, such as 128 bits or more of random data according to current policy;
• store only a cryptographic hash of each token;
• enforce a short expiration period;
• invalidate the token immediately after successful use;
• rate-limit requests and verification attempts;
• use HTTPS and avoid placing tokens in referrer-leaking pages;
• notify the account owner of reset activity;
• require multifactor authentication for high-risk accounts.

When the user submits a token, the service hashes the presented value and compares it with the stored value. The server does not need to recover the original token.

Outcome

The revised design reduces the impact of database disclosure, makes prediction infeasible under the assumed model, and limits replay. It does not eliminate all risk: compromised email accounts, malware on user devices, phishing, and implementation errors remain possible.

Learning Points

This case demonstrates that probability, entropy, randomness, hashing, and operational controls must work together. A long token generated predictably is weak; a random token stored carelessly may still be exposed; and a strong token with unlimited verification attempts can be attacked operationally.

11. Practical Design Principles and Limitations

The following principles apply broadly:

1. Use vetted, standard cryptographic algorithms rather than inventing new ones.
2. Use cryptographic libraries and secure random APIs supplied by trusted platforms.
3. Separate mathematical assumptions from implementation claims.
4. Treat entropy estimates as model-dependent; human behaviour is rarely uniform.
5. Protect keys, seeds, nonces, and internal states as sensitive assets.
6. Document key sizes, algorithms, modes, rotation rules, and intended security lifetimes.
7. Test failure conditions, including repeated use, malformed inputs, low-entropy startup, and clock changes.
8. Review systems against current standards and threat intelligence.
9. Design for algorithm replacement because mathematical assumptions and regulations change.

Cryptographic mathematics does not guarantee security by itself. Side-channel leakage, poor access control, insecure storage, weak authentication, supply-chain compromise, and social engineering may defeat a mathematically strong algorithm.

12. Ethical, Governance, and Professional Issues

Security professionals must use cryptographic tools lawfully and proportionately. Strong encryption protects privacy, safety, intellectual property, and democratic participation, but systems must also support legitimate governance requirements such as auditability, incident response, retention policies, and lawful access procedures. Any access mechanism that weakens cryptographic protection must be evaluated carefully because exceptional access can create systemic risk.

Organisations should maintain cryptographic inventories, define ownership of keys, document acceptable algorithms, and establish procedures for compromise and algorithm deprecation. Personal data should be protected according to applicable privacy and data-protection laws. Cryptography should support data minimisation and privacy by design rather than being treated as a substitute for sound governance.

Chapter Summary

Cryptography depends on mathematical structures and probabilistic reasoning. Prime numbers and factorisation support RSA; modular arithmetic enables finite calculations; modular inverses support reversible operations; and finite fields provide the algebraic setting for AES, elliptic-curve systems, and coding techniques.

Probability describes guessing, collisions, and attack success under explicit assumptions. Shannon entropy measures average uncertainty, while min-entropy focuses on the most likely outcome and is often more relevant to attackers. Secure systems require unpredictable randomness, usually obtained through a CSPRNG rather than an ordinary random function.

Computational complexity explains why some operations are practical while their inverses are expensive. Factoring and discrete logarithms are important hard problems, although their security depends on parameters, implementation, attack models, and future technology. Quantum computing motivates post-quantum migration and crypto-agility.

The practical lesson is that security depends on the complete system: mathematical assumptions, algorithms, random generation, key management, implementation, monitoring, governance, and user behaviour.

Key Terms

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

Composite number: An integer greater than 1 that is not prime.

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

Coprime: Two integers whose greatest common divisor is 1.

Modular arithmetic: Arithmetic based on remainders after division by a modulus.

Congruence: A relationship in which two integers have the same remainder modulo a number.

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

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

Finite field: A finite set supporting field operations, including division by nonzero elements.

Probability: A numerical measure of the likelihood of an event.

Independence: A condition in which the occurrence of one event does not change the probability of another.

Collision: Two different inputs producing the same output, especially the same hash value.

Entropy: A measure of uncertainty or average information in a random variable.

Min-entropy: An entropy measure based on the probability of the most likely outcome.

Randomness: Unpredictability or variation produced by a physical or algorithmic source.

CSPRNG: A pseudorandom generator designed to resist prediction and state-recovery attacks.

Computational complexity: The resources required by an algorithm as input size grows.

Discrete logarithm problem: The problem of recovering an exponent from a group relation such as y = gˣ.

Crypto-agility: The ability to replace cryptographic algorithms and parameters with limited system disruption.

Review Questions

Short Answer Questions

1. What does the notation a ≡ b (mod n) mean?
2. Under what condition does a modular inverse exist?
3. Define a finite field and name one cryptographic application.
4. What is the difference between Shannon entropy and min-entropy?
5. Why is a CSPRNG preferred to an ordinary random-number function for generating keys?

Long Answer Questions

1. Explain the Euclidean algorithm and demonstrate how it can be used to calculate a greatest common divisor.
2. Describe modular exponentiation and explain why repeated squaring is useful in public-key cryptography.
3. Explain how probability and the birthday bound influence the security interpretation of hash functions.
4. Compare true random number generators, pseudorandom number generators, and CSPRNGs.
5. Explain the role of hard mathematical problems in RSA, Diffie–Hellman, and elliptic-curve cryptography.

Analytical / Application Questions

1. A system generates six-digit verification codes uniformly at random. Assuming one guess per code and no rate limiting, calculate the probability of success after 100 distinct guesses and explain why operational controls are necessary.
2. A password policy permits 12 characters selected uniformly from 26 lowercase letters and 26 uppercase letters. Calculate the idealised entropy using H = L log₂ A, then explain why the estimate may not represent human-created passwords.
3. Analyse the password-reset case in this chapter and identify which weaknesses are mathematical, which are implementation weaknesses, and which are governance or operational weaknesses.

Multiple Choice Questions with Answers

Question 1

What is the value of 17 mod 12?

A. 3

B. 5

C. 7

D. 12

Correct Answer: B. 5

Question 2

When does the modular inverse of a modulo n exist?

A. When a is prime

B. When n is even

C. When gcd(a, n) = 1

D. When a is greater than n

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

Question 3

Which set forms the finite field GF(5)?

A. {1, 2, 3, 4, 5}

B. {0, 1, 2, 3, 4}

C. {0, 2, 4, 6, 8}

D. All integers

Correct Answer: B. {0, 1, 2, 3, 4}

Question 4

What is the idealised probability of success for one guess against a uniformly selected secret from 2¹²⁸ possibilities?

A. 1/128

B. 1/2⁶⁴

C. 1/2¹²⁸

D. 2¹²⁸

Correct Answer: C. 1/2¹²⁸

Question 5

Which expression gives Shannon entropy for a discrete random variable X?

A. H(X) = ∑ p(xᵢ)

B. H(X) = −∑ p(xᵢ) log₂ p(xᵢ)

C. H(X) = log₂(max p(x))

D. H(X) = 2ⁿ

Correct Answer: B. H(X) = −∑ p(xᵢ) log₂ p(xᵢ)

Question 6

What does min-entropy primarily measure?

A. The average message length

B. The probability of the least likely outcome

C. The probability of the most likely outcome

D. The number of possible algorithms

Correct Answer: C. The probability of the most likely outcome

Question 7

Which generator is specifically designed to resist prediction of future outputs?

A. A spreadsheet random function

B. A CSPRNG

C. A counter with a public starting value

D. A timestamp generator

Correct Answer: B. A CSPRNG

Question 8

The birthday bound for an n-bit hash is approximately proportional to which quantity?

A. 2ⁿ

B. n²

C. 2^(n/2)

D. log₂ n

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

Question 9

Which problem asks an attacker to recover x from y = gˣ in a suitable group?

A. Integer sorting

B. Discrete logarithm

C. Data compression

D. Checksum generation

Correct Answer: B. Discrete logarithm

Question 10

Why are post-quantum cryptographic algorithms being developed?

A. Because modular arithmetic no longer works

B. Because quantum algorithms may threaten factoring- and discrete-logarithm-based systems

C. Because all symmetric encryption is already broken

D. Because entropy cannot be measured

Correct Answer: B. Because quantum algorithms may threaten factoring- and discrete-logarithm-based systems