Elliptic Curve Cryptography (ECC) là nền tảng của nhiều hệ mật mã hiện đại, từ Bitcoin đến TLS.

Elliptic Curve Cryptography (ECC) underpins many modern cryptographic systems, from Bitcoin to TLS.

// Defining Elliptic Curves

Một đường cong elliptic trên trường thực có dạng Weierstrass:

An elliptic curve over the reals takes the Weierstrass form:

$$y^2 = x^3 + ax + b$$

Với điều kiện discriminant khác 0:

With non-zero discriminant:

$$\Delta = -16(4a^3 + 27b^2) \neq 0$$

// Point Addition

Cho $P \neq Q$ trên đường cong, công thức cộng điểm:

Given $P \neq Q$ on the curve, the addition formula:

$$\lambda = \frac{y_Q - y_P}{x_Q - x_P}, \quad x_R = \lambda^2 - x_P - x_Q, \quad y_R = \lambda(x_P - x_R) - y_P$$

Point doubling ($P = Q$):

$$\lambda = \frac{3x_P^2 + a}{2y_P}$$

// Curves over Finite Fields

Trong cryptography, ta làm việc trên $\mathbb{F}_p$:

In cryptography, we work over $\mathbb{F}_p$:

$$y^2 \equiv x^3 + ax + b \pmod{p}$$

Hasse's theorem:

$$|E(\mathbb{F}_p)| = p + 1 - t, \quad |t| \leq 2\sqrt{p}$$

// ECDLP

Cho $G$ (generator) và $Q = kG$, tìm $k$ là bài toán ECDLP. Thuật toán tốt nhất: $O(\sqrt{n})$.

Given $G$ (generator) and $Q = kG$, finding $k$ is the ECDLP. Best known: $O(\sqrt{n})$.

// ECDH Key Exchange

$$\text{Alice: } a \xrightarrow{} A = aG \quad | \quad \text{Bob: } b \xrightarrow{} B = bG$$

$$\text{Shared secret: } S = aB = bA = abG$$

// secp256k1 (Bitcoin)

// secp256k1: y² = x³ + 7 over F_p
p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a  = 0
b  = 7
n  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
text

// Rust Implementation

use num_bigint::BigUint;
use num_traits::{One, Zero};

#[derive(Clone, Debug)]
struct Point {
    x: Option<BigUint>,
    y: Option<BigUint>,
}

struct EllipticCurve {
    a: BigUint,
    b: BigUint,
    p: BigUint,
}

impl EllipticCurve {
    /// Scalar multiplication: k * P using double-and-add
    fn scalar_mul(&self, k: &BigUint, p: &Point) -> Point {
        let mut result = Point { x: None, y: None };
        let mut temp = p.clone();
        let mut n = k.clone();

        while !n.is_zero() {
            if &n % 2u32 == BigUint::one() {
                result = self.add(&result, &temp);
            }
            temp = self.add(&temp, &temp);
            n >>= 1;
        }
        result
    }
}
rust

// ECC vs RSA

$$\underbrace{256\text{-bit ECC}}_{\text{key size}} \approx \underbrace{3072\text{-bit RSA}}_{\text{key size}} \approx 128\text{-bit security}$$