密码学核心公式全攻略

Chuck Chen

· 2019年6月19日

数论

扩展欧几里得算法 (EEA)

公式：

ax + by = \gcd(a, b)

说明： 扩展欧几里得算法用于计算两个整数 $a$ 和 $b$ 的最大公约数，并找到满足该等式的系数 $x$ 和 $y$ （裴蜀系数）。

实际应用： 计算模逆（modular multiplicative inverse）的基础，这是 RSA 密钥生成和椭圆曲线密码学中点除法的必要步骤。

实现：

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

模幂运算

公式：

c \equiv b^e \pmod m

说明： 计算底数 $b$ 的 $e$ 次方对 $m$ 取模的余数。对于大指数，通常使用“平方求模法”（Square-and-Multiply）以保持效率。

实际应用： 这是 RSA 加密、解密以及 Diffie-Hellman 密钥交换协议中的核心操作。

实现：

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

蒙哥马利模乘

公式：

\text{REDC}(T) = T R^{-1} \pmod n

说明： 一种通过避免昂贵的除法操作来实现快速模乘的方法。它将数字转换为“蒙哥马利形式”，使得模运算简化为简单的位移操作。

实际应用： 广泛应用于加密库（如 OpenSSL）中，用于加速 RSA 和 DSA 签名。

实现：

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 乘法

公式：

xy = z_2 B^{2m} + z_1 B^m + z_0

说明： 一种分治算法，通过将乘积表示为三个较小的乘积，减少了大整数相乘所需的乘法次数。

实际应用： 用于 RSA 中的大整数运算以及格密码（Lattice-based）后量子方案中的多项式乘法。

实现：

# z1 的简化逻辑
z0 = x0 * y0
z2 = x1 * y1
z1 = (x1 + x0) * (y1 + y0) - z2 - z0

Miller-Rabin 素性检验

公式：

a^d \equiv 1 \pmod n \quad \text{或} \quad a^{2^r d} \equiv -1 \pmod n

说明： 一种概率性素性检验算法，根据见证数 $a$ 确定奇整数 $n$ （其中 $n-1 = 2^s \cdot d$ ）是否为“强伪素数”。

实际应用： 生成 RSA 及其他非对称算法所需的超大安全素数时不可或缺。

实现：

def is_prime(n, k=5): # k 为测试次数
    # 将 n-1 分解为 2^s * d
    # 检查 a^d % n == 1 或 a^(2^r * d) % n == -1
    pass

中国剩余定理 (CRT)

公式：

x = \sum_{i=1}^k a_i M_i y_i \pmod N

说明： 允许通过 $x$ 对一组两两互质的因子 $n_i$ 取模的余数 $a_i$ ，来重构 $x \pmod N$ 的值。

实际应用： 用于加速 RSA 解密。通过分别对 $p$ 和 $q$ 进行独立计算，速度比直接对 $pq$ 取模计算快得多。

实现：

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

抽象代数与有限域

有限域 (伽罗瓦域)

公式：

\mathbb{F}_{p^k} \cong \mathbb{F}_p[x] / \langle P(x) \rangle

说明： 有限域是包含有限个元素的代数结构，其加、减、乘、除运算定义完备。

实际应用： $\mathbb{F}_{2^8}$ 用于 AES 的 S 盒（S-Box），而大素数域 $\mathbb{F}_p$ 是 ZK-SNARK 电路算术的标准。

实现： 元素是次数小于 $k$ 的多项式，运算过程对不可约多项式 $P(x)$ 取模。

椭圆曲线 (Weierstrass 形式)

公式：

y^2 = x^3 + ax + b

说明： 定义了一组点 $(x, y)$ ，这些点连同无穷远点在特定的几何加法法则下构成一个阿贝尔群。

实际应用： 为 ECDSA（比特币/以太坊）和 Ed25519 提供安全基础，在同等安全强度下所需的密钥长度比 RSA 小得多。

实现：

# 点加运算 (P != Q)
slope = (y2 - y1) / (x2 - x1)
x3 = slope**2 - x1 - x2
y3 = slope * (x1 - x3) - y1

双线性配对

公式：

e(aP, bQ) = e(P, Q)^{ab}

说明： 一种非退化映射 $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ ，它在两个参数上都是线性的，允许在不同群的指数之间进行“乘法”运算。

实际应用： BLS 签名（以太坊 2.0）、KZG 多项式承诺以及身份基加密（IBE）的核心。

实现： 在特定的“配对友好型”曲线（如 BLS12-381 或 BN254）上通过 Miller 循环（Miller Loop）计算。

多项式算术

数论变换 (NTT)

公式：

\alpha_{k} = \sum_{j=0}^{n-1} a_j \omega^{jk} \pmod p

说明： FFT 的变体，在有限域上使用单位原根代替复数进行计算。

实际应用： 格后量子密码（Kyber/Dilithium）中高效的多项式乘法，以及 STARKs 中的证明生成。

实现： 通常使用蝶形网络（butterfly network）实现，以达到 $O(n \log n)$ 的复杂度。

拉格朗日插值

公式：

L(x) = \sum_{j=0}^{k-1} y_j \ell_j(x)

说明： 一种构造唯一 $k-1$ 次多项式的方法，该多项式通过给定的 $k$ 个点 $(x_j, y_j)$ 。

实际应用： Shamir 秘密共享方案的数学基础，以及 ZKP 中约束系统（如 PLONK）的编码。

实现：

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

格理论

LLL 算法 (Lovász 条件)

公式：

\lVert\mathbf{b}^*_i\rVert^2 \ge (\delta - \mu_{i,i-1}^2) \lVert\mathbf{b}^*_{i-1}\rVert^2

说明： 一种格基规约算法，能在多项式时间内为给定的格找到一组“短”且“接近正交”的基。

实际应用： 对格密码进行分析的关键工具，用于求解最短向量问题（SVP）的近似值。

实现： 基于 Lovász 条件（通常 $\delta = 0.75$ ）进行“尺寸规约”和“交换”的迭代算法。

同态

群同态

公式：

\phi(g_1 + g_2) = \phi(g_1) \cdot \phi(g_2)

说明： 两个群之间的映射，它保持了群运算。这使得在加密或承诺数据上的操作能够反映在底层数值的操作上。

实际应用： 实现了加法同态加密（Paillier）、Pedersen 承诺以及可验证秘密共享。

实现： 通常在离散对数问题困难的群中实现为幂运算 $\phi(x) = g^x$ 。