Number theory and mathematics of cryptography notes — Unit 2

Almost all modern cryptographic algorithms (like RSA and AES) are based on modular arithmetic, because it restricts calculations to a finite set of integers, preventing numbers from growing infinitely large during encryption.

⇒1.1 The Modulo Operator

Given any positive integer `n` and any integer `a`, if we divide `a` by `n`, we get an integer quotient `q` and an integer remainder `r`.
`a = q * n + r` (where 0 ≤ r < n)

The remainder `r` is often referred to as a residue. We write this as `a mod n = r`.

Example: `11 mod 7 = 4` because 11 = 1 * 7 + 4.

Two integers `a` and `b` are said to be congruent modulo `n` if they have the same remainder when divided by `n`. This is written as `a ≡ b (mod n)`.

Example: `73 ≡ 4 (mod 23)` because both have a remainder of 4 when divided by 23. Equivalently, `23` divides `(73 - 4)`.

⇒2.1 Properties

• Addition: `(a + b) mod n = [(a mod n) + (b mod n)] mod n`
• Multiplication: `(a b) mod n = [(a mod n) (b mod n)] mod n`

These properties allow us to perform complex math on huge numbers by taking the modulo at each step, preventing overflow.

One of the most important concepts in number theory is the Greatest Common Divisor (GCD). `gcd(a, b)` is the largest integer that divides both `a` and `b` without leaving a remainder.

If `gcd(a, b) = 1`, the numbers are said to be relatively prime or coprime.

⇒3.1 Finding the GCD

The Euclidean algorithm is an efficient way to find the GCD of two large numbers. It is based on the theorem: `gcd(a, b) = gcd(b, a mod b)`.

Example: Find gcd(1970, 1066).
1970 = 1 x 1066 + 904 --> gcd(1066, 904)
1066 = 1 x 904 + 162 --> gcd(904, 162)
904 = 5 x 162 + 94 --> gcd(162, 94)
... until remainder is 0. The last non-zero remainder is the GCD.

In normal arithmetic, the inverse of `x` is `1/x`. In modular arithmetic, there are no fractions. The modular inverse of `a` modulo `n` is an integer `x` such that:
`(a * x) ≡ 1 (mod n)`

⇒4.1 Existence

The inverse of `a` modulo `n` exists if and only if `a` and `n` are relatively prime (`gcd(a, n) = 1`).

Example: Find inverse of 3 mod 7.
We need `(3 x) mod 7 = 1`. Test values: 31=3, 32=6, 33=9=2, 34=12=5, 35=15=1.
Therefore, the inverse of 3 mod 7 is 5.

Finding the inverse by guessing is impossible for large cryptographic numbers. The Extended Euclidean Algorithm finds the GCD, but also finds coefficients `x` and `y` such that:
`ax + by = gcd(a, b)`

⇒5.1 Finding Inverses

If `gcd(a, n) = 1`, the equation becomes `ax + ny = 1`. If we take this modulo `n`:
`(ax + ny) mod n = 1 mod n`
Since `ny mod n = 0`, we get: `(ax) mod n = 1`

Thus, the coefficient `x` generated by the Extended Euclidean Algorithm is the modular inverse of `a` mod `n`. This is how RSA calculates its decryption keys.

A field is a set of elements where addition, subtraction, multiplication, and division (by non-zero elements) can be performed without leaving the set. Real numbers form an infinite field.

A finite field (or Galois Field) has a finite number of elements. They are critical in cryptography (used heavily in AES).

⇒6.1 Galois Field GF(p)

The set of integers `{0, 1, ..., p-1}` where `p` is a prime number forms a finite field under modulo `p` arithmetic. Because `p` is prime, every non-zero element has a multiplicative inverse.

Computers work in binary. We want to do math on 8-bit bytes (values 0 to 255). Modulo 256 arithmetic is not a field because 256 is not prime (even numbers have no inverse mod 256).

⇒7.1 Polynomial Arithmetic

Instead of integers, GF(2^n) treats numbers as polynomials with binary coefficients.

The binary byte `10000011` represents the polynomial `x^7 + x^1 + 1`.

Addition and subtraction are performed via bitwise XOR. Multiplication is performed modulo an irreducible polynomial (a polynomial that cannot be factored, acting like a prime number). AES uses GF(2^8) with the irreducible polynomial `x^8 + x^4 + x^3 + x + 1`.

A prime number is an integer greater than 1 whose only divisors are 1 and itself. Primes are the building blocks of number theory and public-key cryptography.

⇒8.1 Prime Factorization

The Fundamental Theorem of Arithmetic states that every integer can be factored into a unique product of prime numbers. Example: `91 = 7 x 13`.

Crucially, multiplying two large primes together is easy for a computer. But taking the large result and figuring out what primes created it (factoring) is incredibly hard. This one-way mathematical function secures RSA.

If `p` is a prime and `a` is a positive integer not divisible by `p`, then:
`a^(p-1) ≡ 1 (mod p)`

Alternatively: `a^p ≡ a (mod p)`

⇒9.1 Cryptographic Use

Fermat's theorem provides a way to simplify huge exponents in modular arithmetic, and is the foundation for prime-testing algorithms (like Miller-Rabin).

Euler's totient function, `φ(n)`, is the number of positive integers less than `n` that are relatively prime to `n`.

⇒10.1 Calculating φ(n)

• If `p` is prime, every number less than `p` is coprime to it. Therefore: `φ(p) = p - 1`.
• If `n` is the product of two different primes `p` and `q`, then: `φ(p q) = (p - 1) (q - 1)`.

Example: `n = 21` (which is 3 7). `φ(21) = (3-1)(7-1) = 2 * 6 = 12`. There are exactly 12 numbers less than 21 that do not share a factor with 21. This simple multiplication is the core secret of RSA key generation.

Euler's theorem is a generalization of Fermat's Little Theorem that works for non-primes.

If `a` and `n` are relatively prime, then:
`a^φ(n) ≡ 1 (mod n)`

⇒11.1 The Magic Trick

If we raise a message `M` to a power `e` to encrypt it `(C = M^e mod n)`, and then raise it to a power `d` to decrypt it `(C^d mod n)`, we are calculating `M^(e*d) mod n`.

Using Euler's theorem, we can prove that if we choose `e` and `d` such that `ed ≡ 1 (mod φ(n))`, then `M^(ed) mod n` perfectly equals `M`. This is the exact math behind RSA.

RSA requires generating huge prime numbers (e.g., 2048 bits long). You cannot use trial division to test if a 2048-bit number is prime; it would take longer than the age of the universe.

⇒12.1 Miller-Rabin Test

This is a probabilistic algorithm. You pick a random number `a` and perform a modular exponentiation test on `n`. If it fails the test, `n` is 100% composite (not prime). If it passes, there is a 75% chance `n` is prime.

By running the test 100 times with different random `a` values, the probability that a composite number passes all 100 tests is less than `(1/4)^100`, which is virtually zero. Thus, we can declare the number 'industrial-grade prime'.

In normal math, if `y = g^x`, you can find `x` using a logarithm: `x = log_g(y)`.

In modular arithmetic, the equation becomes `y ≡ g^x (mod p)`. Finding `x` given `y`, `g`, and `p` is called the Discrete Logarithm Problem (DLP).

⇒13.1 Cryptographic Significance

For large prime numbers `p`, there is no known fast algorithm to calculate discrete logarithms. Like factoring, it is a one-way function. Calculating `g^x mod p` is easy, but finding `x` is practically impossible. This mathematical hardness secures Diffie-Hellman Key Exchange and Elliptic Curve Cryptography.

A primitive root of a prime number `p` is a number `g` such that its powers `g^1, g^2, ..., g^(p-1)` generate all the numbers from 1 to `p-1` (in a scrambled order) under modulo `p`.

Example: For `p = 7`, `g = 3` is a primitive root.
`3^1 mod 7 = 3`
`3^2 mod 7 = 2`
`3^3 mod 7 = 6`
`3^4 mod 7 = 4`
`3^5 mod 7 = 5`
`3^6 mod 7 = 1`
All numbers 1 through 6 were generated.

Primitive roots are necessary for discrete logarithm-based algorithms to ensure that the generated keys span the entire possible key space.