Cryptographic Mathematics, Entropy, and Randomness

Introduction and Context

Cryptography is often presented through algorithms such as AES, RSA, and elliptic-curve cryptography. However, secure implementation depends equally on mathematical foundations. A cipher can be expertly designed yet become insecure if keys are generated from predictable values, if arithmetic is misunderstood, or if the available keyspace is too small.

This chapter develops the mathematical and statistical concepts needed to reason about cryptographic protection. It explains binary representation, modular arithmetic, prime numbers, probability, entropy, randomness, keyspace, computational security, and brute-force resistance. The focus is foundational: the aim is not to prove advanced cryptographic theorems, but to enable a cybersecurity practitioner to understand security claims, identify weak designs, and make sound implementation decisions.

Learning Objectives

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

1. Explain how information is represented in bits and bytes.
2. Perform basic modular-arithmetic calculations.
3. Describe the role of prime numbers in public-key cryptography.
4. Use probability concepts to reason about guessing and collisions.
5. Calculate and interpret Shannon entropy for simple distributions.
6. Distinguish true randomness, pseudorandomness, and cryptographic randomness.
7. Calculate keyspace size and estimate brute-force work.
8. Explain computational security and the limits of brute-force estimates.
9. Select appropriate practices for secure random-number and key generation.

1. Bits, Bytes, and Binary Representation

A bit is a binary digit whose value is either 0 or 1. A byte contains eight bits and therefore has 2⁸ = 256 possible patterns, from 00000000 to 11111111. If a system uses n independent bits, the number of possible bit strings is:

Here, N is the number of possible strings and n is the number of bits. The formula assumes every bit can independently take either value and that all combinations are allowed.

For example, a 4-bit value has 2⁴ = 16 possible values, normally represented from 0000 to 1111, or 0 to 15 in decimal. A 128-bit key has 2¹²⁸ possible bit patterns. The key is not “128 numbers”; it is one value selected from an extremely large set.

Binary positional notation assigns weights to positions. The binary value 101101₂ equals:

1 × 2⁵ + 0 × 2⁴ + 1 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰ = 32 + 8 + 4 + 1 = 45₁₀.

Hexadecimal is a compact representation of binary. Each hexadecimal digit represents four bits: for example, hexadecimal F represents 1111₂, and hexadecimal A represents 1010₂. Thus, a 256-bit key is commonly displayed as 64 hexadecimal digits.

Why representation matters in security

Representation affects storage, transmission, comparison, and interpretation. A hexadecimal string may look random but may contain little effective entropy if it was generated predictably. Conversely, a short password containing many visible characters is not automatically secure. Security depends on how many plausible values an attacker must distinguish, not on appearance alone.

2. Modular Arithmetic

Modular arithmetic works with remainders. The expression a mod m is the remainder when integer a is divided by positive integer m. For example:

Two integers a and b are congruent modulo m when they have the same remainder:

This means m divides a − b. For instance, 17 ≡ 2 (mod 5), because 17 − 2 = 15, which is divisible by 5.

The main operations obey these rules:

These rules allow large calculations to be reduced at each step. They are fundamental to block ciphers, message authentication, hash constructions, and public-key algorithms.

Worked example: modular exponentiation

Calculate 3⁴ mod 7:

3⁴ = 81, and 81 mod 7 = 4.

Alternatively, reduce during the calculation:

3² mod 7 = 9 mod 7 = 2;

3⁴ mod 7 = 2² mod 7 = 4.

Efficient algorithms such as repeated squaring make it practical to calculate enormous powers modulo a number without first constructing the enormous ordinary integer.

Modular inverses

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

An inverse exists exactly when gcd(a, m) = 1, meaning a and m share no common factor greater than 1. For example, the inverse of 3 modulo 7 is 5, because 3 × 5 = 15 ≡ 1 (mod 7).

Modular inverses are important in algorithms such as RSA and in finite-field operations. They should not be confused with ordinary division: division modulo m is valid only when the divisor has an inverse.

3. Prime Numbers and Cryptographic Structure

A prime number is an integer greater than 1 with exactly two positive divisors: 1 and itself. Examples include 2, 3, 5, 7, and 11. Every integer greater than 1 has a unique prime factorization, apart from the order of the factors.

Prime numbers support several cryptographic constructions because certain operations are easy in one direction and difficult to reverse without additional information. In RSA, two large primes are multiplied to create a composite modulus. Multiplication is efficient, while factoring the product is believed to be computationally difficult when parameters are properly selected.

The security of a scheme is not created by the word “prime” alone. It depends on parameter sizes, algorithm choice, implementation, and current cryptanalytic knowledge. Small primes provide no meaningful protection. A prime generated with a weak random source may also create a predictable or repeated key.

The greatest common divisor, written gcd(a, b), is the largest positive integer that divides both a and b. The Euclidean algorithm computes it efficiently:

The process continues until the remainder is zero. The last nonzero remainder is the gcd. This algorithm is used in modular-inverse calculations and in key-generation procedures.

4. Probability in Cryptography

Probability measures uncertainty. For an event A, its probability P(A) lies between 0 and 1. If all outcomes are equally likely and there are N possible outcomes, the probability of one specified outcome is:

This simple expression applies only when outcomes are equally likely. If a key generator favors some keys, the probability of guessing the most likely key may be much greater than 1/N.

Guessing a uniformly selected key

Suppose a key is selected uniformly from N possibilities and an attacker tests guesses without repetition. The probability of success after g guesses is:

provided 0 ≤ g ≤ N. If the attacker stops after half the keyspace on average, the expected number of trials to find a randomly selected key is approximately N/2. These are idealized estimates: real attacks may exploit implementation errors, leaked information, or nonuniform generation.

Collision probability

A collision occurs when two independently generated values are equal. For a hash output with n bits, there are 2ⁿ possible outputs. The birthday effect means collisions become plausible after roughly 2ⁿᐟ² samples, not 2ⁿ samples. This is why a 256-bit hash has an idealized collision-resistance level of approximately 128 bits, assuming no better attack is known.

The exact probability that at least one collision occurs after k independent uniform samples from N possible values is:

The formula assumes independent, uniformly distributed samples and k ≤ N. It is commonly approximated for relatively small k compared with N by:

This distinction between guessing one secret and finding any collision is essential in security analysis.

5. Entropy and Information Content

Entropy describes uncertainty. In information theory, the Shannon entropy of a discrete random variable X is:

Here, pᵢ is the probability of outcome i, the sum includes all possible outcomes, and entropy is measured in bits because the logarithm is base 2. The probabilities must be nonnegative and sum to 1.

For N equally likely outcomes, pᵢ = 1/N, so entropy becomes:

This is the maximum entropy for a variable with N possible outcomes. If a six-sided die is fair, H = log₂(6) ≈ 2.585 bits. If it always produces 6, H = 0 bits because there is no uncertainty.

Worked example: biased binary source

Suppose a bit is 1 with probability 0.75 and 0 with probability 0.25. Its entropy is:

H(X) = −[0.75 log₂(0.75) + 0.25 log₂(0.25)] ≈ 0.811 bits.

Although one output bit is produced, it contains only about 0.811 bits of uncertainty on average. Treating biased or predictable output as one full bit of security would overstate protection.

Entropy is not merely length

A 12-character password chosen by a user may have much less effective entropy than a uniformly generated 12-character value. Common words, predictable substitutions, names, dates, and reused passwords reduce the attacker’s search effort. Password entropy estimates must therefore consider the generation process and attacker knowledge, not only character count.

For a uniformly random selection from an alphabet of size A using L independent characters, the theoretical entropy is:

The formula assumes every character is independently and uniformly selected. It does not accurately describe ordinary human-created passwords.

6. Randomness and Random-Number Generators

Randomness is a property of unpredictability or statistical behavior, depending on context. Cryptography particularly requires unpredictability: an attacker should not be able to predict future outputs from available observations.

True, physical, and pseudorandom sources

A physical or true random-number generator (TRNG) derives values from physical phenomena such as electronic noise or timing variation. A pseudorandom number generator (PRNG) is deterministic: it expands a short internal state, called a seed, into a longer sequence. If the algorithm and seed are known, the sequence can be reproduced.

A cryptographically secure pseudorandom number generator (CSPRNG) is designed so that, without its internal state or seed, feasible observations do not allow an attacker to predict future output or reconstruct past output, subject to the generator’s security design and correct implementation.

Ordinary programming functions such as basic language-level random utilities are often suitable for simulations, games, or randomized testing but not for keys, tokens, salts, or nonces. Security-sensitive values should come from an operating-system or hardware-backed cryptographic random source.

Seeds and state

A CSPRNG cannot compensate for a predictable seed. If a generator starts from a timestamp, process identifier, or small counter, an attacker may reproduce its output. Systems should obtain seed material from an approved operating-system entropy facility and protect the generator’s internal state.

A nonce is a value intended to be used once in a specified cryptographic context. A nonce need not always be secret, but accidental reuse can be catastrophic for some schemes, including stream-cipher and authenticated-encryption constructions. A random value is not automatically a nonce policy: uniqueness requirements must be analyzed separately.

Testing randomness

Statistical tests can detect obvious bias, repetition, or correlation, but passing tests does not prove cryptographic unpredictability. A predictable sequence can appear statistically random over a limited sample. Security evaluation therefore requires an appropriate construction, a sound entropy source, correct seeding, and implementation review—not only a frequency test.

7. Keyspace and Brute-Force Resistance

The keyspace is the set of all possible keys accepted by a cryptographic system. If a key contains n uniformly random bits, its keyspace has 2ⁿ elements and its ideal brute-force security is n bits.

For a uniformly generated key, an exhaustive search may require up to 2ⁿ trials and approximately 2ⁿ⁻¹ trials on average if guesses are not repeated. If an attacker can test R candidates per second, the worst-case time in seconds is:

The average time under the same assumptions is approximately:

Here, n is the number of effective key bits and R is the attack rate in trials per second. The equations assume that testing a candidate is feasible, verification is reliable, keys are uniformly distributed, and no shortcut attack exists.

Worked example

Consider a uniformly random 40-bit key and an attacker capable of 1,000,000,000 trials per second. The worst-case number of trials is 2⁴⁰ = 1,099,511,627,776. Therefore:

t ≈ 1,099,511,627,776 ÷ 1,000,000,000 ≈ 1,099.5 seconds, or about 18.3 minutes.

The average is about 9.2 minutes. This example shows why key length must be assessed against realistic attack rates and current technology.

Effective keyspace

A nominal key length may overstate security. If a 128-bit key is generated from only 32 bits of unpredictable seed material, an attacker may need to search only approximately 2³² likely states. Similarly, if a password is selected from a dictionary of one million candidates, its practical search space is closer to 10⁶ than to the much larger space implied by its visual character set.

8. Computational Security

A cryptographic system is computationally secure when the best known attack requires resources considered infeasible under a defined threat model. “Infeasible” is contextual: it depends on time, money, hardware, parallelism, data access, and the value of the protected information.

Security is not the same as absolute impossibility. A scheme may be secure against an online attacker but vulnerable to offline guessing, or secure against classical computers but threatened by a future quantum computer. A sound assessment identifies:

• the attacker’s capabilities;
• the number of guesses or operations available;
• whether verification is online or offline;
• whether parallel hardware can be used;
• whether side channels or implementation flaws reduce the search;
• the required confidentiality period.

Brute force is also not always the best attack. Cryptanalysis may exploit structure, weak keys, poor modes, reused nonces, leaked plaintext, timing behavior, or flawed randomness. Thus, a large keyspace is necessary for modern cryptography but is not sufficient by itself.

9. Practical Security Design

The following practices provide a reliable foundation:

1. Use standardized, reviewed algorithms and recommended parameter sizes.
2. Generate keys, salts, reset tokens, and nonces with approved CSPRNG facilities.
3. Separate random values by purpose; do not reuse keys across unrelated protocols without a documented design.
4. Use password-hashing functions designed for offline resistance, with unique salts and an appropriate work factor.
5. Protect keys throughout their lifecycle: generation, storage, use, backup, rotation, and destruction.
6. Treat encoding as representation, not encryption. Base64 and hexadecimal do not add secrecy.
7. Avoid inventing cryptographic algorithms or random-number schemes.
8. Document assumptions, including threat model, key lifetime, algorithm version, and entropy source.
9. Test for implementation errors, but do not treat statistical randomness tests as proof of security.
10. Plan migration because computational capabilities and recommended parameters change.

Applied Case: Predictable Session Tokens

Background

This illustrative case concerns a web application that issues a six-digit password-reset token. The development team uses the current time in seconds as the seed for a conventional pseudorandom function. Tokens appear varied during normal testing.

Problem

An attacker requests a reset and observes one token. Because the approximate creation time is visible in application logs and HTTP metadata, the attacker can test a narrow range of possible timestamps. The effective seed space may contain only a few thousand candidates, even though the token format appears to offer 1,000,000 possibilities.

Analysis

A six-digit decimal token has at most 10⁶ possible values. If it were uniform and rate-limited, an online attack might be manageable. In this case, however, the predictable seed dramatically reduces the likely candidate set. If the generator is deterministic, reproducing one output may reveal adjacent outputs or future tokens. Lack of rate limiting and long token validity further increase risk.

Approach and solution

The application should use an operating-system CSPRNG to generate a token with sufficient security strength, store only a securely protected verifier where possible, enforce short expiration, bind the token to the intended account and purpose, and apply strict rate limiting and attempt limits. The token should be invalidated after successful use. Logging should avoid exposing token values.

Outcome

The redesign removes dependence on predictable time values, reduces the opportunity for offline guessing, and limits the impact of token disclosure. Security now depends on both randomness and surrounding controls rather than on token length alone.

Learning points

The case demonstrates four principles: apparent randomness is not necessarily unpredictability; effective entropy is determined by the generation process; rate limiting changes attack economics; and cryptographic protection requires system-level controls around the primitive.

Limitations, Ethics, and Governance

Entropy estimates are models, not guarantees. Assumptions about independence, uniformity, attacker speed, and algorithm strength may be wrong. Security professionals should communicate uncertainty rather than promise that a system is “unbreakable.”

Poor cryptographic randomness can expose personal data, financial records, health information, and authentication credentials. Organizations therefore have a duty to use competent review, maintain cryptographic inventories, follow applicable privacy and security regulations, and document risk decisions. Security testing must be authorized, controlled, and designed to avoid exposing real secrets.

Emerging technologies also matter. Specialized hardware can accelerate password guessing and symmetric-key search. Quantum algorithms may alter the security assumptions of some public-key systems, although practical impact depends on future hardware and migration timelines. Post-quantum transition planning should preserve sound random generation and key-management practices; replacing an algorithm does not repair weak entropy.

Chapter Summary

Cryptographic security rests on mathematical and statistical foundations. Binary representation determines the number of possible bit strings, while modular arithmetic enables efficient operations in many cryptographic algorithms. Prime numbers and greatest-common-divisor methods support important public-key constructions.

Probability quantifies guessing and collision risk. Shannon entropy measures uncertainty, but effective cryptographic entropy depends on the actual generation process. A value that is long or visually complex may still be predictable. CSPRNGs, properly seeded from strong entropy sources, are essential for keys, tokens, salts, and other security-sensitive values.

A uniformly random n-bit key has a keyspace of 2ⁿ, but practical brute-force resistance depends on effective entropy, attack rate, verification conditions, and possible shortcut attacks. Computational security is therefore contextual rather than absolute. Secure systems combine sound mathematics, approved algorithms, reliable randomness, key management, rate limiting, monitoring, and governance.

Key Terms

Bit: A binary digit with value 0 or 1.

Byte: A group of eight bits.

Binary: A base-2 number system.

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

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

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

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

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

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

Collision: An occurrence in which two inputs produce the same output value.

Entropy: A measure of uncertainty or average information.

Keyspace: The complete set of possible keys.

CSPRNG: A cryptographically secure pseudorandom number generator.

Seed: Initial input used to establish a pseudorandom generator’s state.

Nonce: A value intended for one-time use in a cryptographic context.

Brute-force attack: Systematic testing of possible keys or secrets.

Effective entropy: The actual unpredictability available to an attacker.

Computational security: Security based on attacks being infeasible with available resources.

Salt: A unique value added to password processing to prevent identical inputs from producing identical stored results.

Review Questions

Short Answer Questions

1. How many possible values can be represented by 12 independent bits?
2. What condition must hold for a modular inverse of a modulo m to exist?
3. Why does a predictable seed weaken a pseudorandom generator?
4. What is the difference between nominal key length and effective entropy?
5. Why can statistical tests not prove that a generator is cryptographically secure?

Long Answer Questions

1. Explain modular arithmetic and describe its importance in cryptographic algorithms.
2. Define Shannon entropy and compare the entropy of a fair binary source with that of a biased binary source.
3. Explain how keyspace size affects brute-force resistance, including the assumptions behind time estimates.
4. Distinguish a TRNG, a conventional PRNG, and a CSPRNG.
5. Discuss why cryptographic security is computational and contextual rather than absolute.

Analytical / Application Questions

1. A system generates 32-bit session identifiers using a timestamp-based seed. Analyze the likely attack opportunities and propose a safer design.
2. A password policy allows 20 characters, but users commonly choose names and dates. Explain why character length alone is an unreliable entropy estimate and recommend controls.
3. An organization uses a 128-bit key but obtains all keys from a generator seeded with only 24 unpredictable bits. Assess the effective security and explain the consequences for risk management.

Multiple Choice Questions with Answers

Question 1

How many possible bit strings can be formed from 8 independent bits?

A. 8

B. 16

C. 128

D. 256

Correct Answer: D. 256

Question 2

What is 17 mod 5?

A. 1

B. 2

C. 3

D. 4

Correct Answer: B. 2

Question 3

A modular inverse of a modulo m exists when:

A. a is larger than m

B. m is prime in every case

C. gcd(a, m) = 1

D. a is even

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

Question 4

What is the Shannon entropy of a source that always produces the same outcome?

A. 0 bits

B. 1 bit

C. The length of the output

D. Infinite bits

Correct Answer: A. 0 bits

Question 5

Which property is especially required of a cryptographic random generator?

A. Fast graphical output

B. Predictability from timestamps

C. Unpredictability to an attacker

D. A fixed repeated sequence

Correct Answer: C. Unpredictability to an attacker

Question 6

A uniformly selected 40-bit key has approximately how many possible values?

A. 40

B. 1,024

C. 2⁴⁰

D. 40²

Correct Answer: C. 2⁴⁰

Question 7

If an attacker can test R candidates per second, which expression estimates worst-case exhaustive-search time for an n-bit uniform key?

A. nR

B. 2ⁿ/R

C. R/2ⁿ

D. 2Rⁿ

Correct Answer: B. 2ⁿ/R

Question 8

Why does the birthday effect matter for an n-bit hash output?

A. It makes every hash reversible

B. Collisions may become plausible near 2ⁿᐟ² samples

C. It doubles the key length

D. It prevents all duplicate outputs

Correct Answer: B. Collisions may become plausible near 2ⁿᐟ² samples

Question 9

Which statement about a password’s effective entropy is correct?

A. It always equals the number of characters

B. It depends on the generation process and attacker knowledge

C. It is determined only by capitalization

D. It is zero for every human-created password

Correct Answer: B. It depends on the generation process and attacker knowledge

Question 10

Which practice is most appropriate for generating reset tokens?

A. Use the current timestamp as a seed

B. Use a conventional non-security PRNG

C. Use an approved CSPRNG and enforce expiration and rate limits

D. Encode the username with Base64

Correct Answer: C. Use an approved CSPRNG and enforce expiration and rate limits