公钥密码学

概述

公钥密码学（Public Key Cryptography）于 1976 年由 Diffie 和 Hellman 首次提出，其核心思想是使用密钥对（公钥 + 私钥）替代对称密钥密码学中的单一共享密钥。公钥公开用于加密和验证，私钥保密用于解密和签名。这一范式解决了对称密码学中密钥分发的根本难题。基于离散对数困难性的 Diffie-Hellman 密钥交换协议允许双方在不安全信道上协商共享密钥。数字签名利用私钥签名、公钥验证实现消息认证与不可否认性。同态加密允许在密文上直接执行计算，其中 RSA 具有乘法同态性，而全同态加密（FHE）支持任意计算，是密码学的前沿方向。

定义

公钥密码学（Public Key Cryptography）

公钥密码学的核心思想是：

每个用户拥有一对密钥：公钥（public key）和私钥（private key）

公钥公开，任何人都可以用于加密消息或验证签名

私钥保密，仅所有者可以用于解密消息或生成签名

知道公钥（加密方法）不等于知道私钥（解密方法）

与对称密钥密码学的本质区别：

特性对称密钥密码学公钥密码学
密钥加密/解密使用相同密钥密钥对：公钥 + 私钥
密钥分发需要安全信道无需安全信道
速度快慢（约慢 1000 倍）
代表 AES, DES RSA, ECC
典型用途大量数据加密密钥交换、数字签名
密钥管理 $n$ 用户需 $n (n - 1) /2$ 个密钥 $n$ 用户仅需 $2 n$ 个密钥

特性	对称密钥密码学	公钥密码学
密钥	加密/解密使用相同密钥	密钥对：公钥 + 私钥
密钥分发	需要安全信道	无需安全信道
速度	快	慢（约慢 1000 倍）
代表	AES, DES	RSA, ECC
典型用途	大量数据加密	密钥交换、数字签名
密钥管理	$n$ 用户需 $n (n - 1) /2$ 个密钥	$n$ 用户仅需 $2 n$ 个密钥

Diffie-Hellman 密钥交换协议（Diffie-Hellman Key Exchange）

由 Whitfield Diffie 和 Martin Hellman 于 1976 年提出（Malcolm Williamson 于 1974 年在英国 GCHQ 秘密发明）。

协议步骤（在 $Z_{p}$ 中计算）：

Alice 和 Bob 公开约定素数 $p$ 和 $p$ 的原根 $a$

Alice 选择秘密整数 $k_{1}$ ，发送 $a^{k_{1}} mod p$ 给 Bob

Bob 选择秘密整数 $k_{2}$ ，发送 $a^{k_{2}} mod p$ 给 Alice

Alice 计算 $(a^{k_{2}})^{k_{1}} mod p$

Bob 计算 $(a^{k_{1}})^{k_{2}} mod p$

共享密钥： $(a^{k_{2}})^{k_{1}} mod p = (a^{k_{1}})^{k_{2}} mod p = a^{k_{1} k_{2}} mod p$

安全性：窃听者知道 $p, a, a^{k_{1}} mod p, a^{k_{2}} mod p$ ，但要求出 $k_{1}$ 或 $k_{2}$ 需要解决离散对数问题（给定 $a^{k} mod p$ 求 $k$ ），这在计算上是不可行的（当 $p$ 超过 300 位时）。

数字签名（Digital Signatures）

数字签名利用公钥密码学实现消息认证：接收者可以确认消息确实来自声称的发送者，且发送者无法否认。

签名协议（以 RSA 为例，Alice 发送签名消息）：

Alice 的公钥为 $(n, e)$ ，私钥为 $d$

Alice 将消息分为块 $m_{1}, m_{2}, \dots, m_{k}$

Alice 对每块应用私钥变换（签名）： $s_{i} = m_{i}^{d} mod n$

Alice 将签名后的块 $s_{1}, s_{2}, \dots, s_{k}$ 发送给所有接收者

接收者对每块应用 Alice 的公钥变换（验证）： $m_{i} = s_{i}^{e} mod n$

因为只有 Alice 知道私钥 $d$ ，所以只有 Alice 能产生有效的签名。

签名 + 加密的秘密通信：

Alice 先用自己的私钥 $d_{A}$ 签名： $s = m^{d_{A}} mod n_{A}$

再用 Bob 的公钥 $(n_{B}, e_{B})$ 加密： $c = s^{e_{B}} mod n_{B}$

Bob 收到后先用自己的私钥 $d_{B}$ 解密： $s = c^{d_{B}} mod n_{B}$

再用 Alice 的公钥 $(n_{A}, e_{A})$ 验证： $m = s^{e_{A}} mod n_{A}$

这样同时保证了机密性（只有 Bob 能读）和认证性（只有 Alice 能签）。

同态加密（Homomorphic Encryption）

同态加密允许在密文上直接执行计算，计算结果解密后等于对明文执行相同计算的结果。

RSA 是乘法同态的：

$E_{(n, e)} (M_{1}) \cdot E_{(n, e)} (M_{2}) mod n = (M_{1}^{e} mod n) (M_{2}^{e} mod n) mod n = (M_{1} M_{2})^{e} mod n = E_{(n, e)} (M_{1} M_{2})$

即密文相乘等于明文乘积的加密。

但 RSA 不是加法同态的： $E (M_{1}) + E (M_{2}) \neq = E (M_{1} + M_{2})$ 。

全同态加密（Fully Homomorphic Encryption, FHE）：

允许在密文上执行任意计算（包括加法和乘法）

由 Craig Gentry 于 2009 年首次实现（基于格密码学）

意义：可以在不解密的情况下对加密数据运行程序

应用前景：云计算中的隐私保护计算

现状：尚无实用的 FHE 方案（计算和内存开销过大）

核心性质

性质	描述	说明
密钥对分离	公钥加密/验证，私钥解密/签名	公钥密码学的核心特征
密钥分发简化	公钥可公开传输	无需安全信道， $n$ 用户仅需 $2 n$ 个密钥
加密不蕴含解密	知道公钥无法推导私钥	基于数学问题的计算困难性
DH 共享密钥	$a^{k_{1} k_{2}} mod p$	双方独立计算得到相同密钥
DH 安全性	离散对数问题困难性	已知 $a^{k} mod p$ 求 $k$ 不可行
数字签名认证	私钥签名，公钥验证	保证消息来源的真实性
数字签名不可否认	签名者无法否认发送过消息	私钥唯一性保证
RSA 乘法同态	$E (m_{1}) \cdot E (m_{2}) = E (m_{1} \cdot m_{2})$	密文运算对应明文运算
FHE 任意计算	支持加法和乘法的任意组合	密码学前沿，尚无实用方案
速度劣势	比对称密码慢约 1000 倍	实际中与 AES 互补使用

关系网络

graph TB
    A["公钥密码学"] --> B["密钥对机制"]
    A --> C["Diffie-Hellman 密钥交换"]
    A --> D["数字签名"]
    A --> E["同态加密"]
    A --> F["RSA密码系统"]

    B --> B1["公钥：加密/验证"]
    B --> B2["私钥：解密/签名"]

    C --> C1["离散对数困难性"]
    C --> C2["原根"]
    C --> C3["共享密钥: a^(k1*k2) mod p"]

    D --> D1["签名：私钥变换"]
    D --> D2["验证：公钥变换"]
    D --> D3["认证性 + 不可否认性"]
    D --> D4["签名+加密组合"]

    E --> E1["RSA 乘法同态"]
    E --> E2["全同态加密 FHE"]
    E --> E3["格密码学"]

    F --> F1["大整数分解困难性"]
    F --> F2["费马小定理"]

    A --> G["密码学"]
    C --> H["模运算"]
    F --> H
    F --> I["模逆元"]
    F --> J["素数"]

    style A fill:#5cb85c,color:#fff
    style C fill:#4a90d9,color:#fff
    style D fill:#d9534f,color:#fff
    style E fill:#e8a838,color:#fff
    style F fill:#9b59b6,color:#fff

RSA密码系统是公钥密码学的核心实例：基于大整数分解困难性，支持加密、解密和数字签名
密码学是公钥密码学的上位概念：公钥密码学是密码学的两大范式之一
原根是 Diffie-Hellman 协议的基础：需要选取素数 $p$ 的原根 $a$ 作为生成元
模逆元是 RSA 密钥生成的关键：计算 $d = e^{- 1} mod φ (n)$
素数是 RSA 和 DH 安全性的共同根基：大素数的选取和性质

章节扩展

第4章：数论与密码学

公钥密码学是第 4 章 4.6 节的后半部分核心内容，综合运用了本章的数论工具：

4.6 密码学：公钥密码学的基本思想（密钥对机制）、RSA 密码系统的完整推导、Diffie-Hellman 密钥交换协议、数字签名（签名 + 验证）、同态加密（RSA 乘法同态、全同态加密前沿）
4.4 解同余方程：模逆元的计算是 RSA 密钥生成的核心；离散对数问题是 DH 安全性的基础
4.3 素数与最大公因数：大素数的选取是 RSA 和 DH 安全性的共同前提
4.5 同余的应用：原根的概念是 Diffie-Hellman 协议选取生成元 $a$ 的理论基础

补充

公钥密码学的历史与学术背景

公钥密码学的概念由 Whitfield Diffie 和 Martin Hellman 在 1976 年的里程碑论文 “New Directions in Cryptography” 中首次提出，这篇论文获得了 2015 年的图灵奖。Diffie-Hellman 密钥交换协议是该论文的核心贡献，其安全性基于离散对数问题的计算困难性。几乎同时期，Malcolm Williamson 在英国 GCHQ 秘密发明了相同的方案（1974 年），但直到 1997 年才解密公开。RSA 密码系统由 Rivest、Shamir 和 Adleman 于 1977 年提出，成为最广泛使用的公钥密码系统。数字签名的概念由 Diffie 和 Hellman 在 1976 年的论文中首次提出，RSA 数字签名方案由 Rivest、Shamir 和 Adleman 于 1978 年实现。全同态加密（FHE）由 Craig Gentry 于 2009 年在斯坦福大学的博士论文中首次实现，基于理想格（ideal lattices）的数学结构，被认为是密码学的”圣杯”之一。

学术来源：Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th ed.). McGraw-Hill, Section 4.6.

参考链接：Diffie, W., & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644-654.

参见

RSA密码系统 — 基于大整数分解困难性的公钥密码系统，支持加密、解密和数字签名
密码学 — 密码学的基本概念、密码系统五元组、对称密钥 vs 公钥密码学
原根 — Diffie-Hellman 协议中生成元 $a$ 的选取基础
模逆元 — RSA 密钥生成中 $d = e^{- 1} mod φ (n)$ 的计算方法
素数 — RSA 和 Diffie-Hellman 安全性的共同数学根基

CS Wiki

探索

公钥密码学

公钥密码学

定义

核心性质

关系网络

章节扩展

第4章：数论与密码学

补充

参见

关系图谱

目录

反向链接