公钥密码学

概述

公钥密码学（Public-Key Cryptography）是一种使用公钥（public key）加密、私钥（private key）解密的密码体系，解决了传统对称加密中密钥分发困难的核心问题。

定义

形式化定义

一个公钥密码系统由三个算法组成：

• 密钥生成 $\text{KeyGen}(1^{\lambda })\to (pk,sk)$：输入安全参数 $\lambda$，输出公钥 $pk$ 和私钥 $sk$
• 加密 $\text{Enc}(pk,m)\to c$：用公钥 $pk$ 加密消息 $m$，输出密文 $c$
• 解密 $\text{Dec}(sk,c)\to m$：用私钥 $sk$ 解密密文 $c$，恢复消息 $m$

安全性要求：在不知道 $sk$ 的情况下，从 $pk$ 和 $c$ 计算 $m$ 是计算不可行的。

核心思想

公钥密码学的安全性基于计算困难性假设（computational hardness assumption）：

密码系统	困难问题	安全性基础
RSA	大整数分解	给定 $n=pq$（$p,q$ 为大素数），难以恢复 $p,q$
Diffie-Hellman	离散对数	给定 $g,g^a\mathrm{mod}p$，难以计算 $a$
ElGamal	离散对数	同 Diffie-Hellman
椭圆曲线密码	椭圆曲线离散对数	比传统离散对数更短密钥达到同等安全

RSA 密码系统

密钥生成

1. 选择两个大素数 $p$ 和 $q$（通常各 1024 位以上）
2. 计算 $n=pq$（模数）和 $\varphi (n)=(p-1)(q-1)$（Euler 函数）
3. 选择 $e$ 使得 $1<e<\varphi (n)$ 且 $\gcd (e,\varphi (n))=1$（$e$ 通常取 65537）
4. 计算 $d\equiv e^{-1}(\mathrm{mod}\varphi (n))$（模逆元）
5. 公钥 $(n,e)$，私钥 $(n,d)$

加密与解密

• 加密：$c\equiv m^e(\mathrm{mod}n)$
• 解密：$m\equiv c^d(\mathrm{mod}n)$

正确性由 Euler 定理保证：$m^{ed}\equiv m(\mathrm{mod}n)$。

Diffie-Hellman 密钥交换

两个通信方在不安全信道上协商共享密钥：

1. 公开参数：大素数 $p$ 和生成元 $g$
2. Alice 选择随机 $a$，发送 $A=g^a\mathrm{mod}p$
3. Bob 选择随机 $b$，发送 $B=g^b\mathrm{mod}p$
4. 共享密钥：$K=B^a\mathrm{mod}p=g^{ab}\mathrm{mod}p=A^b\mathrm{mod}p$

窃听者只知道 $g,p,A,B$，无法计算 $g^{ab}$（离散对数困难性）。

核心性质

• 单向性：公钥到私钥的推导在计算上不可行
• 陷门性（trapdoor）：拥有私钥（陷门信息）可以高效解密
• 非对称性：加密和解密使用不同的密钥，解决了密钥分发问题
• 数字签名：私钥签名、公钥验证，提供不可否认性

应用场景

• RSA 加密/签名：HTTPS、电子邮件加密（S/MIME、PGP）
• SSL/TLS 协议：使用 RSA 或 ECDHE 进行密钥交换，建立安全通道
• 数字证书：CA 用私钥签名证书，浏览器用 CA 公钥验证
• SSH：基于 RSA 或 ECDSA 的身份认证

参见

• 整除
• 布尔代数