The Most Important Cryptography Equations: A Comprehensive Guide

Number Theory

Extended Euclidean Algorithm (EEA)

Equation:

Explanation: The Extended Euclidean Algorithm computes the greatest common divisor of two integers $a$ and $b$ and identifies the coefficients $x$ and $y$ (Bézout coefficients) that satisfy the identity.

Practical Use: Fundamental for computing modular multiplicative inverses, which is a required step in RSA key generation and point division in Elliptic Curve Cryptography.

Implementation:

def xgcd(a, b):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

Modular Exponentiation

Equation:

Explanation: Computes the remainder of a base $b$ raised to an exponent $e$ modulo $m$. For large exponents, this is performed using the Square-and-Multiply method to maintain efficiency.

Practical Use: This is the primary operation in RSA encryption, decryption, and the Diffie-Hellman key exchange protocol.

Implementation:

def power(b, e, m):
    res = 1
    b %= m
    while e > 0:
        if e % 2 == 1: res = (res * b) % m
        b = (b * b) % m
        e //= 2
    return res

Montgomery Modular Multiplication

Equation:

Explanation: A method for performing fast modular multiplication by avoiding expensive division. It transforms numbers into “Montgomery form” where the modulus operation becomes a simple bit-shift.

Practical Use: Heavily utilized in cryptographic libraries (like OpenSSL) to accelerate RSA and DSA signatures.

Implementation:

def redc(T, n, r, n_prime):
    m = ((T % r) * n_prime) % r
    t = (T + m * n) // r
    return t - n if t >= n else t

Karatsuba Multiplication

Equation:

Explanation: A divide-and-conquer algorithm that reduces the number of multiplications needed for large integers by expressing the product in terms of three smaller products.

Practical Use: Used for large integer arithmetic in RSA and polynomial multiplications in lattice-based post-quantum schemes.

Implementation:

# Simplified logic for z1
z0 = x0 * y0
z2 = x1 * y1
z1 = (x1 + x0) * (y1 + y0) - z2 - z0

Miller-Rabin Primality Test

Equation:

Explanation: A probabilistic primality test that determines if an odd integer $n$ (where $n-1 = 2^s \cdot d$) is a “strong probable prime” based on a witness $a$.

Practical Use: Essential for generating the large, secure prime numbers required for RSA and other asymmetric algorithms.

Implementation:

def is_prime(n, k=5): # k is number of tests
    # Decompose n-1 into 2^s * d
    # Check if a^d % n == 1 or a^(2^r * d) % n == -1
    pass

Chinese Remainder Theorem (CRT)

Equation:

Explanation: Allows for the reconstruction of a value $x$ modulo $N$ from its remainders $a_i$ modulo smaller, pairwise coprime factors $n_i$.

Practical Use: Used to speed up RSA decryption by performing calculations modulo $p$ and $q$ independently, which is significantly faster than calculating modulo $pq$.

Implementation:

# x = (a1 * M1 * y1 + a2 * M2 * y2 + ...) % N
# where Mi = N / ni and yi = inverse(Mi, ni)

Abstract Algebra & Finite Fields

Finite Fields (Galois Fields)

Equation:

Explanation: Finite fields are algebraic structures with a finite set of elements where addition, subtraction, multiplication, and division are well-defined.

Practical Use: $\mathbb{F}_{2^8}$ is used in the AES S-Box, while large prime fields $\mathbb{F}_p$ are the standard for ZK-SNARK circuit arithmetic.

Implementation: Elements are polynomials of degree less than $k$, with operations performed modulo an irreducible polynomial $P(x)$.

Elliptic Curves (Weierstrass Form)

Equation:

Explanation: Defines a set of points $(x, y)$ that, along with a point at infinity, form an abelian group under a specific geometric addition law.

Practical Use: Provides the security foundation for ECDSA (Bitcoin/Ethereum) and Ed25519, requiring smaller key sizes than RSA for equivalent security.

Implementation:

# Point Addition (P != Q)
slope = (y2 - y1) / (x2 - x1)
x3 = slope**2 - x1 - x2
y3 = slope * (x1 - x3) - y1

Bilinear Pairings

Equation:

Explanation: A non-degenerate map $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ that is linear in both arguments, allowing “multiplication” in the exponent across different groups.

Practical Use: Core of BLS signatures (Ethereum 2.0), KZG polynomial commitments, and Identity-Based Encryption.

Implementation: Computed via the Miller Loop on specific “pairing-friendly” curves like BLS12-381 or BN254.

Polynomial Arithmetic

Number Theoretic Transform (NTT)

Equation:

Explanation: An FFT variant computed over finite fields using primitive roots of unity instead of complex numbers.

Practical Use: Efficient polynomial multiplication in Lattice-based PQC (Kyber/Dilithium) and generating proofs in STARKs.

Implementation: Typically implemented using a butterfly network (butterfly operations) to achieve $O(n \log n)$ complexity.

Lagrange Interpolation

Equation:

Explanation: A method for constructing the unique polynomial of degree $k-1$ that passes through $k$ given points $(x_j, y_j)$.

Practical Use: The mathematical basis for Shamir’s Secret Sharing and encoding constraint systems (like PLONK) in ZKPs.

Implementation:

# l_j(x) = product((x - xi) / (xj - xi)) for i != j

Lattice Theory

LLL Algorithm (Lovász Condition)

Equation:

Explanation: A lattice basis reduction algorithm that finds a “short” and “nearly orthogonal” basis for a given lattice in polynomial time.

Practical Use: Critical for lattice-based cryptanalysis and solving the Shortest Vector Problem (SVP) approximations.

Implementation: Iterative algorithm involving “Size Reduction” and “Swapping” based on the Lovász condition (typically $\delta = 0.75$).

Homomorphisms

Group Homomorphism

Equation:

Explanation: A map between two groups that preserves the group operation, allowing operations on encrypted or committed data to reflect operations on the underlying values.

Practical Use: Enables additive homomorphic encryption (Paillier), Pedersen commitments, and verifiable secret sharing.

Implementation: Usually implemented as exponentiation $\phi(x) = g^x$ in a group where the Discrete Logarithm Problem is hard.