Số học modular là nền tảng toán học cho hầu hết các hệ mật mã.

Modular arithmetic is the mathematical foundation for most cryptographic systems.

// Congruence

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

// Modular Inverse

$$a \cdot a^{-1} \equiv 1 \pmod{n}$$

Tồn tại khi $\gcd(a, n) = 1$. Tìm bằng Extended Euclidean Algorithm:

Exists when $\gcd(a, n) = 1$. Found via the Extended Euclidean Algorithm:

fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if a == 0 {
        return (b, 0, 1);
    }
    let (gcd, x1, y1) = extended_gcd(b % a, a);
    (gcd, y1 - (b / a) * x1, x1)
}

fn mod_inverse(a: i64, m: i64) -> Option<i64> {
    let (gcd, x, _) = extended_gcd(a, m);
    if gcd != 1 { None }
    else { Some(((x % m) + m) % m) }
}
rust

// Fermat's Little Theorem

$$a^{p-1} \equiv 1 \pmod{p}$$

Hệ quả: $a^{-1} \equiv a^{p-2} \pmod{p}$

Corollary: $a^{-1} \equiv a^{p-2} \pmod{p}$

// Euler's Theorem

$$a^{\varphi(n)} \equiv 1 \pmod{n}, \quad \gcd(a, n) = 1$$

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

// Binary Exponentiation

Tính $a^n \bmod m$ trong $O(\log n)$:

Computes $a^n \bmod m$ in $O(\log n)$:

fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
    let mut result = 1u64;
    base %= modulus;
    while exp > 0 {
        if exp % 2 == 1 {
            result = result * base % modulus;
        }
        exp /= 2;
        base = base * base % modulus;
    }
    result
}
rust

// RSA

$$\text{Encrypt: } c = m^e \bmod n \quad | \quad \text{Decrypt: } m = c^d \bmod n$$

let (p, q) = (61u64, 53u64);
let n = p * q;                    // 3233
let phi = (p - 1) * (q - 1);     // 3120
let e = 17u64;
let d = mod_inverse(e as i64, phi as i64).unwrap() as u64;

let msg = 42u64;
let cipher = mod_pow(msg, e, n);
let plain  = mod_pow(cipher, d, n);
assert_eq!(msg, plain); // 42 == 42
rust