非对称加密

1. 非对称加密基础

1.1 基本概念

非对称加密使用一对密钥：公钥（公开）和私钥（保密）。

$E_{pub}(M)=C,D_{priv}(C)=M$

1.2 核心应用

1.3 与对称加密对比

2. RSA 算法

2.1 数学基础

RSA 安全性基于大整数分解困难性。

密钥生成：

1. 选择两个大素数 $p,q$（通常 1024+ 位）
2. 计算 $n=pq$
3. 计算欧拉函数 $\varphi (n)=(p-1)(q-1)$
4. 选择 $e$，满足 $1<e<\varphi (n)$，$\gcd (e,\varphi (n))=1$（通常 $e=65537$）
5. 计算 $d$，满足 $ed\equiv 1(\mathrm{mod}\varphi (n))$

• 公钥：$(n,e)$
• 私钥：$(n,d)$

加密：$C=M^e\mathrm{mod}n$

解密：$M=C^d\mathrm{mod}n$

2.2 正确性证明

由 $ed\equiv 1(\mathrm{mod}\varphi (n))$，存在 $k$ 使 $ed=k\varphi (n)+1$

$C^d=(M^e{)}^d=M^{ed}=M^{k\varphi (n)+1}=M^{k\varphi (n)}\cdot M\equiv M(\mathrm{mod}n)$

（由欧拉定理 $M^{\varphi (n)}\equiv 1(\mathrm{mod}n)$，当 $\gcd (M,n)=1$）

2.3 RSA 填充方案

OAEP 填充：

m' = m || 0...0  ← 填充到 n 的长度
m' = MGF(seed) XOR m' || seed = MGF(m') XOR seed
C = (m')^e mod n

2.4 RSA 代码示例

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

# 生成密钥对
private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
)
public_key = private_key.public_key()

# 加密
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# 解密
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

2.5 RSA 攻击

3. ECC 椭圆曲线加密

3.1 数学基础

椭圆曲线定义：

$y^2=x^3+ax+b(\mathrm{mod}p)$

点加法：$P+Q=R$

标量乘法：$kP=P+P+\cdots +P$（$k$ 次）

离散对数问题（ECDLP）：已知 $P$ 和 $kP$，求 $k$ 是困难的。

3.2 常用曲线

3.3 ECDH 密钥交换

Alice: 生成私钥 a，计算 aG（G 为基点）
Bob:   生成私钥 b，计算 bG

交换: Alice → aG → Bob
      Bob   → bG → Alice

共享密钥:
Alice: a(bG) = abG
Bob:   b(aG) = abG

3.4 ECDSA 签名

from cryptography.hazmat.primitives.asymmetric import ec

# 生成密钥
private_key = ec.generate_private_key(ec.SECP256R1())
public_key = private_key.public_key()

# 签名
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# 验证
public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))

3.5 EdDSA（Ed25519）

from cryptography.hazmat.primitives.asymmetric import ed25519

# 生成密钥
private_key = ed25519.Ed25519PrivateKey.generate()

# 签名（无需指定哈希算法）
signature = private_key.sign(message)

# 验证
public_key = private_key.public_key()
public_key.verify(signature, message)

Ed25519 优势：

• 确定性签名（无随机数依赖）
• 快速
• 抗侧信道
• 无歧义验证

4. Diffie-Hellman 密钥交换

4.1 经典 DH

$A=g^a\mathrm{mod}p,B=g^b\mathrm{mod}p$

$s=B^a\mathrm{mod}p=A^b\mathrm{mod}p=g^{ab}\mathrm{mod}p$

4.2 安全参数

4.3 前向保密

使用临时密钥（Ephemeral DH / DHE），每次会话生成新的 DH 参数，即使长期私钥泄露，历史会话仍安全。

5. 算法选择指南