Cryptographic Mathematics

Security built on mathematical hardness.

Modular Arithmetic

The Foundation

All modern cryptography rests on modular arithmetic:

\[a \equiv b \pmod{n} \iff n \mid (a - b)\]

Read: "a is congruent to b modulo n" means n divides their difference.

Properties

Property Statement

Addition

\((a + b) \mod n = ((a \mod n) + (b \mod n)) \mod n\)

Multiplication

\((a \cdot b) \mod n = ((a \mod n) \cdot (b \mod n)) \mod n\)

Exponentiation

\(a^k \mod n\) computable efficiently via repeated squaring

Prime Numbers

Fundamental Theorem of Arithmetic

Every integer \(n > 1\) has a unique prime factorization:

\[n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}\]

Prime Density

The prime counting function \(\pi(x)\) counts primes up to x:

\[\pi(x) \sim \frac{x}{\ln x}\]

Probability a random n-bit number is prime: approximately \(1/n\).

RSA

Key Generation

  1. Choose large primes p and q

  2. Compute \(n = pq\)

  3. Compute \(\phi(n) = (p-1)(q-1)\)

  4. Choose e coprime to \(\phi(n)\) (commonly 65537)

  5. Compute \(d \equiv e^{-1} \pmod{\phi(n)}\)

Public key: \((n, e)\), Private key: \(d\)

Encryption/Decryption

\[c = m^e \mod n\]
\[m = c^d \mod n\]

Security Basis

RSA security relies on the integer factorization problem:

Given \(n = pq\), finding p and q is computationally hard for large n.

Current recommendation: \(n\) should be at least 2048 bits.

Discrete Logarithm

The Problem

Given generator g, prime p, and \(y = g^x \mod p\):

Finding x is the discrete logarithm problem (DLP).

Diffie-Hellman Key Exchange

  1. Alice and Bob agree on public p, g

  2. Alice: choose secret a, compute \(A = g^a \mod p\)

  3. Bob: choose secret b, compute \(B = g^b \mod p\)

  4. Exchange A and B publicly

  5. Shared secret: \(K = B^a = A^b = g^{ab} \mod p\)

Elliptic Curves

Definition

Curves of the form:

\[y^2 = x^3 + ax + b\]

over a finite field \(\mathbb{F}_p\).

Point Addition

Points on the curve form a group under a geometric addition operation.

ECDSA

Elliptic Curve Digital Signature Algorithm:

  • 256-bit key provides ~128-bit security

  • Same security as 3072-bit RSA with smaller keys

  • Standard for TLS, SSH, code signing

Hash Functions

Requirements

A cryptographic hash \(H: \{0,1\}^* \to \{0,1\}^n\) must satisfy:

Property Definition

Preimage resistance

Given h, hard to find m where \(H(m) = h\)

Second preimage

Given m, hard to find \(m' \neq m\) where \(H(m) = H(m')\)

Collision resistance

Hard to find any \(m \neq m'\) where \(H(m) = H(m')\)

Birthday Bound

By the birthday paradox, finding collisions in an n-bit hash requires approximately \(2^{n/2}\) operations.

SHA-256 (n=256): collision attack requires \(~2^{128}\) operations.

Symmetric Encryption

AES

Block cipher operating on 128-bit blocks.

Key schedule expands key into round keys:

  • AES-128: 10 rounds

  • AES-192: 12 rounds

  • AES-256: 14 rounds

Security Level

Symmetric key of n bits provides n-bit security (brute force: \(2^n\) operations).

Related