数学重学 - 28 密码学数学进阶

这是 数学重学路线图 阶段五的子页面

📌 前置知识：密码学数学

密码学数学进阶：现代密码背后的硬核数学

上一篇 密码学数学 讲了 RSA 和基础数论

这一篇进入更现代的领域：椭圆曲线、零知识证明、后量子密码

这些是当前安全领域最前沿的数学工具

一、椭圆曲线密码学（ECC）

什么是椭圆曲线

方程：y² = x³ + ax + b（满足 4a³ + 27b² ≠ 0，保证没有奇点）

不是椭圆！名字来源于椭圆积分的计算，跟椭圆形状无关

曲线关于 x 轴对称

椭圆曲线上的”加法”

这是 ECC 的核心操作，定义了一种特殊的”加法”：

两点相加 P + Q：

1. 过 P、Q 画直线

2. 直线与曲线交于第三点 R’

3. R’ 关于 x 轴取对称点 R

4. R = P + Q
   点的倍乘 2P = P + P：

5. 过 P 画曲线的切线

6. 切线与曲线交于另一点 R’

7. R’ 取对称得 R = 2P
   无穷远点 O：相当于”零元”，P + O = P

离散椭圆曲线（密码学用的）

实际密码学中，在有限域 F_p 上做运算（所有坐标 mod p）

曲线不再是连续的，变成了散点

但”加法”规则完全一样（只是所有运算都 mod p）

椭圆曲线离散对数问题（ECDLP）

已知点 P 和 Q = kP（P 自加 k 次）

求 k 极其困难（没有已知的高效算法）

这就是 ECC 安全性的数学基础

ECC 的优势

| 安全等级 | RSA 密钥长度 | ECC 密钥长度 |
| 80 bit | 1024 bit | 160 bit |
| 112 bit | 2048 bit | 224 bit |
| 128 bit | 3072 bit | 256 bit |
| 256 bit | 15360 bit | 512 bit |

ECC 用短得多的密钥达到相同安全级别

更快、更省资源，特别适合移动设备和 IoT

应用

HTTPS/TLS：现代 TLS 几乎都用 ECDHE 密钥交换

比特币：使用 secp256k1 曲线做签名

SSH：Ed25519 密钥就是椭圆曲线

Python 简单椭圆曲线点运算

class EllipticCurve:
"""有限域上的椭圆曲线 y² = x³ + ax + b (mod p)"""

def __init__(self, a, b, p):
    self.a = a
    self.b = b
    self.p = p

def is_on_curve(self, point):
    if point is None:  # 无穷远点
        return True
    x, y = point
    return (y * y - (x * x * x + self.a * x + self.b)) % self.p == 0

def add(self, P, Q):
    """椭圆曲线点加法"""
    if P is None: return Q
    if Q is None: return P
    
    x1, y1 = P
    x2, y2 = Q
    
    if x1 == x2 and y1 != y2:
        return None  # P + (-P) = O
    
    if P == Q:
        # 点倍乘：切线斜率
        lam = (3 * x1 * x1 + self.a) * pow(2 * y1, -1, self.p) % self.p
    else:
        # 两点相加：割线斜率
        lam = (y2 - y1) * pow(x2 - x1, -1, self.p) % self.p
    
    x3 = (lam * lam - x1 - x2) % self.p
    y3 = (lam * (x1 - x3) - y1) % self.p
    return (x3, y3)

def multiply(self, P, n):
    """标量乘法：n * P（快速倍乘法）"""
    result = None  # 无穷远点
    addend = P
    while n:
        if n & 1:
            result = self.add(result, addend)
        addend = self.add(addend, addend)
        n >>= 1
    return result

# 示例：小曲线 y² = x³ + 2x + 3 (mod 97)
ec = EllipticCurve(a=2, b=3, p=97)

# 找一个曲线上的点
G = (3, 6)
print(f"G = {G} 在曲线上? {ec.is_on_curve(G)}")

# 点的倍乘
P2 = ec.multiply(G, 2)
P5 = ec.multiply(G, 5)
P10 = ec.multiply(G, 10)

print(f"2G = {P2}")
print(f"5G = {P5}")
print(f"10G = {P10}")

# 验证：5G + 5G = 10G
P5_plus_P5 = ec.add(P5, P5)
print(f"5G + 5G = {P5_plus_P5}")
print(f"等于 10G? {P5_plus_P5 == P10}")

二、离散对数问题（DLP）

问题定义

给定素数 p、生成元 g、结果值 h

已知 h = g^x mod p

求 x 极其困难（p 足够大时）

直觉比喻

正向计算：给你一个齿轮比，转动把手 x 圈，告诉你指针指向哪

反向破解：告诉你指针位置和齿轮比，让你猜转了几圈

当圈数可能是天文数字时，逐一尝试不现实

Diffie-Hellman 密钥交换

两个人（Alice 和 Bob）在不安全的信道上协商出一个共享密钥

过程：

1. 公开约定素数 p 和生成元 g
2. Alice 选秘密数 a，发送 A = g^a mod p
3. Bob 选秘密数 b，发送 B = g^b mod p
4. Alice 计算密钥：K = B^a mod p = g^(ab) mod p
5. Bob 计算密钥：K = A^b mod p = g^(ab) mod p
   窃听者知道 g, p, A, B，但算不出 a 或 b → 算不出 K

Python DH 密钥交换模拟

import random

def dh_key_exchange():
"""模拟 Diffie-Hellman 密钥交换"""
# 公开参数（实际中 p 要非常大，这里用小数演示）
p = 23    # 素数
g = 5     # 生成元

# Alice 的秘密
a = random.randint(2, p - 2)
A = pow(g, a, p)  # Alice 公开发送

# Bob 的秘密
b = random.randint(2, p - 2)
B = pow(g, b, p)  # Bob 公开发送

# 各自计算共享密钥
key_alice = pow(B, a, p)
key_bob = pow(A, b, p)

print(f"公开参数: p={p}, g={g}")
print(f"Alice: 秘密 a={a}, 公开 A={A}")
print(f"Bob:   秘密 b={b}, 公开 B={B}")
print(f"Alice 算出的密钥: {key_alice}")
print(f"Bob   算出的密钥: {key_bob}")
print(f"密钥一致? {key_alice == key_bob}")

# 窃听者知道的信息
print(f"\n窃听者知道: p={p}, g={g}, A={A}, B={B}")
print("窃听者要求解: g^a mod p = A，这就是离散对数问题")

dh_key_exchange()

# 用更大的素数演示
def dh_large():
"""用大素数的 DH（更接近实际）"""
# 一个 256 bit 的素数（实际中用 2048+ bit）
p = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF
g = 2

a = random.getrandbits(256)
b = random.getrandbits(256)

A = pow(g, a, p)
B = pow(g, b, p)

key_alice = pow(B, a, p)
key_bob = pow(A, b, p)

print(f"\n大素数 DH:")
print(f"密钥一致? {key_alice == key_bob}")
print(f"共享密钥前 32 hex: {hex(key_alice)[:34]}...")

dh_large()

三、零知识证明（ZKP）

核心思想

向别人证明你知道某个秘密，但不透露秘密本身

听起来不可能，但数学上做到了

阿里巴巴洞穴比喻

洞穴有 A、B 两条路，在最深处有一扇需要密码的门连接两条路

Alice（证明者）说她知道密码

Bob（验证者）站在洞口

过程：

1. Alice 随机选一条路进去（Bob 不知道选了哪条）
2. Bob 站在洞口喊”从 A 路出来”或”从 B 路出来”
3. 如果 Alice 知道密码 → 不管 Bob 说哪条，她都能走通
4. 如果 Alice 不知道密码 → 50% 概率走错
5. 重复 20 次，每次都对 → 骗过的概率 < 1/百万
   Bob 看到 Alice 每次都能从正确的路出来

但 Bob 完全不知道密码是什么！

三大性质

完备性：如果证明者确实知道秘密，验证者一定会被说服

可靠性：如果证明者不知道秘密，几乎不可能骗过验证者

零知识性：验证者除了”他知道”这个事实外，得不到任何额外信息

应用场景

身份验证：证明你是某人，不需要发送密码

隐私保护：证明你年龄 ≥ 18，不暴露具体年龄

区块链 zk-SNARKs：证明交易合法，不暴露交易细节（Zcash、zkSync）

合规审计：证明数据满足某条件，不暴露原始数据

Python 简单 ZKP 演示（离散对数知识证明）

import random
import hashlib

def simple_zkp_demo():
"""
零知识证明：证明者知道 x，使得 y = g^x mod p
不透露 x 的值
"""
# 公开参数
p = 10007  # 素数
g = 5      # 生成元

# 证明者的秘密
x = 42  # 这是秘密！
y = pow(g, x, p)  # y 是公开的

print(f"公开参数: p={p}, g={g}, y={y}")
print(f"证明者要证明：她知道 x 使得 g^x mod p = y")
print(f"（秘密 x={x}，验证者看不到这个值）\n")

# Schnorr 协议（交互式零知识证明）
success_count = 0
rounds = 20

for i in range(rounds):
    # 步骤1：证明者选随机数 r，发送承诺 t = g^r mod p
    r = random.randint(1, p - 2)
    t = pow(g, r, p)
    
    # 步骤2：验证者发送随机挑战 c
    c = random.randint(0, 100)
    
    # 步骤3：证明者计算响应 s = r + c*x (mod p-1)
    s = (r + c * x) % (p - 1)
    
    # 步骤4：验证者检查 g^s = t * y^c (mod p)
    left = pow(g, s, p)
    right = (t * pow(y, c, p)) % p
    
    if left == right:
        success_count += 1

print(f"验证通过 {success_count}/{rounds} 轮")
if success_count == rounds:
    print("验证者相信：证明者知道秘密 x")
    print("但验证者完全不知道 x 的具体值！")

simple_zkp_demo()

四、同态加密简介

核心思想

在密文上直接运算，解密后的结果等于在明文上运算的结果

Enc(a) ⊕ Enc(b) = Enc(a + b)

不需要解密就能计算！

直觉比喻

把数据锁在透明但不可触摸的盒子里

别人可以用特殊工具隔着盒子操作数据

操作完后你打开盒子，结果和直接操作一样

同态加密的类型

部分同态：只支持加法或只支持乘法

RSA 天然支持乘法同态：Enc(a) × Enc(b) = Enc(a × b)

Paillier 支持加法同态

有限全同态（SHE）：支持有限次加法和乘法

完全同态（FHE）：支持任意次加法和乘法

理论上可以在密文上做任何计算

但目前非常慢（比明文计算慢百万倍+）

应用场景

隐私计算：云端处理加密数据，云不知道数据内容

医疗数据分析：医院加密上传数据，第三方做统计分析

安全投票：加密选票求和，不暴露个人选票

Python Paillier 同态加密演示

# 简化的 Paillier 加法同态加密演示
import random
from math import gcd

def generate_paillier_keys(bits=16):
"""生成 Paillier 密钥（简化版，实际中 bits 要 2048+）"""
def gen_prime(bits):
    while True:
        n = random.getrandbits(bits)
        if n < 2: continue
        if all(n % i != 0 for i in range(2, min(n, 1000))):
            return n

p = gen_prime(bits)
q = gen_prime(bits)
while p == q:
    q = gen_prime(bits)

n = p * q
n_sq = n * n
g = n + 1  # 简化选择
lam = (p - 1) * (q - 1) // gcd(p - 1, q - 1)

# L(x) = (x-1)/n
def L(x):
    return (x - 1) // n

mu = pow(L(pow(g, lam, n_sq)), -1, n)

return {'n': n, 'g': g}, {'lam': lam, 'mu': mu, 'n': n}

def paillier_encrypt(pub, m):
n, g = pub['n'], pub['g']
r = random.randint(1, n - 1)
while gcd(r, n) != 1:
    r = random.randint(1, n - 1)
c = (pow(g, m, n * n) * pow(r, n, n * n)) % (n * n)
return c

def paillier_decrypt(priv, pub, c):
n = pub['n']
lam, mu = priv['lam'], priv['mu']
def L(x):
    return (x - 1) // n
m = (L(pow(c, lam, n * n)) * mu) % n
return m

# 演示加法同态
pub, priv = generate_paillier_keys(bits=16)

a, b = 15, 27
enc_a = paillier_encrypt(pub, a)
enc_b = paillier_encrypt(pub, b)

# 密文相乘 = 明文相加 (Paillier 的同态性质)
enc_sum = (enc_a * enc_b) % (pub['n'] ** 2)

result = paillier_decrypt(priv, pub, enc_sum)
print(f"a = {a}, b = {b}")
print(f"Enc(a) * Enc(b) 解密后 = {result}")
print(f"a + b = {a + b}")
print(f"同态性质成立? {result == a + b}")

五、后量子密码学

量子计算机的威胁

Shor 算法：量子计算机可以高效分解大整数和求离散对数

这意味着：RSA、ECC、DH 全都不安全了

目前大规模量子计算机还没造出来，但在加速推进

NIST 已经开始标准化后量子密码算法

哪些会被破？哪些安全？

| 算法类型 | 量子计算下 | 说明 |
| RSA | 不安全 | Shor 算法直接破解 |
| ECC | 不安全 | Shor 算法直接破解 |
| DH | 不安全 | Shor 算法直接破解 |
| AES-256 | 安全（密钥翻倍即可） | Grover 算法只能加速到平方根 |
| SHA-256 | 基本安全 | 同上 |
| 格密码 | 安全 | 后量子候选方案 |

后量子密码方案

格密码（Lattice-based）

基于格上的困难问题（如 LWE: Learning With Errors）

目前最被看好的后量子方案

NIST 选中的 ML-KEM（原 CRYSTALS-Kyber）就是格密码

哈希签名（Hash-based）

只依赖哈希函数的安全性

简单可靠，但签名较大

SPHINCS+ 是 NIST 选中的哈希签名方案

编码密码（Code-based）

基于纠错码的困难问题

McEliece 方案已有 40+ 年历史

多变量密码（Multivariate）

基于求解多变量多项式方程组的困难

LWE 问题直觉

给你一组近似的线性方程（加了小噪声）

求解这些方程极其困难

b ≈ A·s + e（A 公开，b 公开，s 是秘密，e 是小噪声）

没有噪声 → 高斯消元轻松解

有噪声 → 已知最好的算法也是指数级

Python LWE 问题演示

import numpy as np

def lwe_demo():
"""LWE (Learning With Errors) 问题演示"""
np.random.seed(42)

# 参数
n = 5        # 秘密向量维度
m = 20       # 方程数
q = 97       # 模数

# 秘密向量（这是要保护的秘密）
s = np.random.randint(0, q, n)
print(f"秘密向量 s = {s}")

# 公开矩阵
A = np.random.randint(0, q, (m, n))

# 小噪声
e = np.random.randint(-2, 3, m)  # 噪声很小

# 公开值：b = A·s + e (mod q)
b = (A @ s + e) % q

print(f"\n公开信息:")
print(f"A (矩阵 {m}x{n}): 前3行 = {A[:3]}")
print(f"b (向量): 前10个 = {b[:10]}")
print(f"噪声 e: {e}")

# 没有噪声的情况：可以用最小二乘法求解
b_no_noise = (A @ s) % q
# 有噪声时：最小二乘法给出的是错误答案
s_guess = np.linalg.lstsq(A, b, rcond=None)[0]
s_guess_rounded = np.round(s_guess) % q

print(f"\n尝试破解（最小二乘法）: {s_guess_rounded.astype(int)}")
print(f"真实秘密:              {s}")
print(f"破解成功? {np.allclose(s_guess_rounded % q, s)}")
print("噪声让简单方法失效！这就是 LWE 的安全性来源")

lwe_demo()

六、ECDH 密钥交换

原理

和 DH 相同的思路，但用椭圆曲线代替模幂运算

更短的密钥，更高的效率

过程

1. 公开约定椭圆曲线参数和基点 G
2. Alice 选秘密 a，发送 A = aG（点的标量乘法）
3. Bob 选秘密 b，发送 B = bG
4. Alice 计算 K = aB = a(bG) = abG
5. Bob 计算 K = bA = b(aG) = abG
6. 共享密钥 K = abG

安全性

窃听者知道 G, aG, bG

要求 a 或 b → 椭圆曲线离散对数问题（ECDLP）

目前无已知高效算法

Python ECDH 简单演示

# 用之前定义的 EllipticCurve 类
class EllipticCurve:
def __init__(self, a, b, p):
    self.a = a
    self.b = b
    self.p = p

def add(self, P, Q):
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and y1 != y2:
        return None
    if P == Q:
        lam = (3*x1*x1 + self.a) * pow(2*y1, -1, self.p) % self.p
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, self.p) % self.p
    x3 = (lam*lam - x1 - x2) % self.p
    y3 = (lam*(x1 - x3) - y1) % self.p
    return (x3, y3)

def multiply(self, P, n):
    result = None
    addend = P
    while n:
        if n & 1:
            result = self.add(result, addend)
        addend = self.add(addend, addend)
        n >>= 1
    return result

import random

# 曲线参数（小曲线演示）
ec = EllipticCurve(a=2, b=3, p=97)
G = (3, 6)  # 基点

# Alice
a_secret = random.randint(2, 95)
A_public = ec.multiply(G, a_secret)

# Bob
b_secret = random.randint(2, 95)
B_public = ec.multiply(G, b_secret)

# 共享密钥
key_alice = ec.multiply(B_public, a_secret)
key_bob = ec.multiply(A_public, b_secret)

print(f"基点 G = {G}")
print(f"Alice 公钥: {A_public}")
print(f"Bob   公钥: {B_public}")
print(f"Alice 算的密钥: {key_alice}")
print(f"Bob   算的密钥: {key_bob}")
print(f"密钥一致? {key_alice == key_bob}")

七、密码学哈希函数的数学性质

三大安全性质

抗原像攻击：给定 h，找不到 m 使得 H(m) = h

抗第二原像攻击：给定 m₁，找不到 m₂ ≠ m₁ 使得 H(m₁) = H(m₂)

抗碰撞攻击：找不到任意 m₁ ≠ m₂ 使得 H(m₁) = H(m₂)

生日攻击

找碰撞比找原像容易得多

n bit 哈希的碰撞攻击复杂度：约 2^(n/2)

所以 SHA-256 的碰撞攻击需要 2^128 次 → 安全

但 MD5（128 bit）碰撞只需 2^64 次 → 不安全

Python 哈希碰撞演示

import hashlib
import random
import string
import time

def find_partial_collision(prefix_bits=16):
"""找哈希值前 prefix_bits 位相同的两个不同输入"""
seen = {}
attempts = 0

start = time.time()
while True:
    msg = ''.join(random.choices(string.ascii_letters, k=10))
    h = hashlib.sha256(msg.encode()).hexdigest()
    prefix = h[:prefix_bits // 4]  # 取前几个hex字符
    
    attempts += 1
    if prefix in seen and seen[prefix][0] != msg:
        elapsed = time.time() - start
        print(f"找到部分碰撞！（前 {prefix_bits} 位）")
        print(f"  输入1: '{seen[prefix][0]}' → {seen[prefix][1][:16]}...")
        print(f"  输入2: '{msg}' → {h[:16]}...")
        print(f"  尝试次数: {attempts}")
        print(f"  理论期望: ~{2**(prefix_bits//2)} 次")
        print(f"  耗时: {elapsed:.3f}s")
        return
    
    seen[prefix] = (msg, h)

find_partial_collision(prefix_bits=24)  # 找前24位碰撞

八、实际应用总览

你每天用的密码学

| 场景 | 使用的数学 |
| HTTPS 访问网站 | ECDHE + AES + SHA |
| SSH 登录服务器 | Ed25519（椭圆曲线）|
| 比特币转账 | secp256k1 + SHA256 |
| git commit 签名 | GPG (RSA 或 ECC) |
| JWT token | HMAC-SHA256 或 RS256 |
| 密码存储 | bcrypt/argon2（哈希）|

后端开发者需要知道的

不要自己实现密码算法（用成熟库）

密钥长度选择：RSA ≥ 2048，ECC ≥ 256，AES ≥ 128

密码存储永远用专用哈希（bcrypt, argon2），不要用 SHA

考虑后量子迁移：关注 NIST 后量子标准化进展

九、练习题

题目1：ECC 概念

为什么 256 位的 ECC 密钥能提供与 3072 位 RSA 相当的安全性？从数学难题的角度解释。

答案

RSA 基于大整数分解问题，已有亚指数级算法（数域筛法）

ECC 基于椭圆曲线离散对数问题，已知最好算法是指数级的（Pollard rho）

同样安全级别，ECC 的问题”更难”，所以需要的密钥更短

256 位 ECC 的最佳攻击需要约 2^128 次运算 ≈ 3072 位 RSA

题目2：DH 安全性

在 Diffie-Hellman 密钥交换中，如果中间人（MITM）能篡改通信内容（不只是窃听），DH 还安全吗？为什么？

答案

不安全！经典 DH 不能防中间人攻击

中间人可以分别和 Alice、Bob 各做一次 DH，建立两个不同的密钥

Alice 以为在和 Bob 通信，实际是和中间人

解决方案：用数字签名认证对方身份（这就是 TLS 要证书的原因）

题目3：零知识证明

用自己的话解释：为什么阿里巴巴洞穴实验中，重复 20 次后验证者可以相信证明者，但仍然不知道密码？

答案

每次不知道密码的人有 50% 概率蒙对

20 次全蒙对的概率 = (1/2)^20 ≈ 百万分之一

所以连续 20 次成功几乎可以确定对方知道密码

但验证者每次看到的只是”从某条路出来”的结果

这个结果不包含密码的任何信息

验证者甚至无法向第三方证明这件事（因为可以伪造录像）

题目4：Python 实践

修改本页的椭圆曲线代码，找出曲线 y² = x³ + 2x + 3 (mod 97) 上的所有点，并数一数有多少个

答案

ec = EllipticCurve(a=2, b=3, p=97)
points = []
for x in range(97):
rhs = (x**3 + 2*x + 3) % 97
for y in range(97):
    if (y * y) % 97 == rhs:
        points.append((x, y))
print(f"曲线上有 {len(points)} 个点（不含无穷远点）")
print(f"加上无穷远点共 {len(points) + 1} 个点")

题目5：后量子思考

如果明天就出现了实用的量子计算机，你负责的后端系统需要做哪些密码学迁移？列出具体步骤。

答案

1. TLS 证书：从 RSA/ECDSA 迁移到后量子签名（如 ML-DSA）
2. 密钥交换：从 ECDHE 迁移到后量子 KEM（如 ML-KEM）
3. SSH 密钥：从 Ed25519 迁移到后量子方案
4. JWT 签名：从 RS256/ES256 迁移到后量子签名
5. 密码存储：bcrypt/argon2 基于哈希，影响较小
6. AES 密钥：从 128 位升级到 256 位（应对 Grover 算法）
7. 历史数据：用后量子算法重新加密存储的敏感数据

十、总结与关联

现代密码学的数学根基：

ECC → 椭圆曲线离散对数问题

DH → 离散对数问题

ZKP → 证明知识而不泄露内容

同态加密 → 密文上直接计算

后量子 → 格问题等新型困难问题

关联笔记

← 密码学数学 RSA 和基础数论

← 27-信息论基础 熵与密码强度

← 数学重学/12-模运算 模运算是密码学的基础运算

---

上一章	目录	下一章
27-信息论基础	数学重学路线图	29-费米估算实战