密码学基础

1976 年，斯坦福大学的两位研究者惠特菲尔德·迪菲（Whitfield Diffie）和马丁·赫尔曼（Martin Hellman）发表了一篇论文，标题听起来平淡无奇：《密码学的新方向》（New Directions in Cryptography）。他们在其中解决了一个看似矛盾的问题：两个从未见过面、也没有秘密沟通渠道的人，如何在公开的网络上安全地协商出一个只有他们两人知道的秘密密钥？

这个问题的解决，颠覆了两千年来密码学的基本假设，也成为今天所有 HTTPS 网站、银行交易、消息加密的底层基础。

破除误解：密码学不只是"打乱和还原"#

古典密码学（凯撒密码、维吉尼亚密码等）的核心思路是：用一把"密钥"把明文打乱成密文，收信方用同一把密钥还原。这种对称加密有一个根本问题：如何安全地传递密钥？

这被称为"密钥分发问题"（key distribution problem），两千年来人们的解决方案是：物理手段（信使、外交邮袋、预先约定的密码本）。数字通信时代，这个方法无法扩展。

现代密码学的突破不仅仅是"更复杂的打乱"，而是在计算复杂性理论的基础上，把"安全性"定义为数学上可证明的属性，并建立了一套无需预先共享秘密就能安全通信的体系。

核心一：香农的信息论基础#

1949 年，克劳德·香农发表《保密系统的通信理论》，用信息论的语言奠定了密码学的理论基础：

完美安全（Perfect Secrecy）：若密文不提供关于明文的任何信息（即 $I(\text{明文}; \text{密文}) = 0$），则称加密方案具有完美安全性。

香农证明了：一次性密码本（one-time pad）是唯一实现完美安全的加密方案——用与明文等长的、真正随机的密钥对明文逐位异或（XOR），密文对攻击者而言与随机串不可区分。

代价是显而易见的：香农同时证明了一条不可能定理——任何完美安全方案，其密钥空间必须不小于明文空间（$|K| \geq |M|$），换句话说密钥至少要和明文一样长，且每个密钥只能用一次（"一次性"由此得名）。密钥分发问题不但没有消除，反而更加严峻：你要安全传一条 1GB 的消息，就得先安全传一把 1GB 的密钥。完美安全在理论上是绝对的，在实践中几乎无法大规模使用——这正是它历史上只用于"红色电话"等极少数最高机密信道的原因。

这就是为什么现代密码学从完美安全退而求其次：在计算上安全（computationally secure），即破解的计算量超过了攻击者可用的资源。

核心二：单向函数与公钥密码学的诞生#

迪菲-赫尔曼的核心洞察是：某些数学函数计算容易，逆转困难——即使知道函数本身，给你看函数值，你也无法在合理时间内找到输入。这类函数叫单向函数（one-way function）。

迪菲-赫尔曼密钥交换（1976）利用了模幂运算的这种不对称性：

• 计算 $g^a \bmod p$（离散幂运算）：容易
• 给定 $g^a \bmod p$，求 $a$（离散对数问题）：目前对大素数 $p$ 极难

两方分别选取私钥 $a$ 和 $b$，公开 $g^a \bmod p$ 和 $g^b \bmod p$，各自计算 $(g^b)^a = (g^a)^b = g^{ab} \bmod p$——这个共享值只有双方知道，窃听者只有 $g^a$ 和 $g^b$，需要解离散对数才能得到 $g^{ab}$。

重要限制：单向函数的存在至今未被严格证明。这里有一个常被科普说错的微妙关系：单向函数存在会推出 P $\neq$ NP（实际上更强，推出 NP $\not\subseteq$ BPP），但反过来不成立——即使证明了 P $\neq$ NP，也未必能得到单向函数。原因在于，P vs NP 谈的是最坏情况的难度（存在某些难实例），而密码学需要的是平均情况的难度（随机抽一个实例就难），后者是强得多的要求。"P≠NP 能否推出单向函数存在"至今是开放问题。现代密码学建立在"单向函数存在"这一比 P≠NP 更强的假设之上——这是密码学最深的基础性未解问题之一。

核心三：RSA 算法（1977）#

1977 年，MIT 的罗纳德·李维斯特（Ron Rivest）、艾迪·沙米尔（Adi Shamir）和伦纳德·阿德尔曼（Leonard Adleman）发表了 RSA 算法，实现了完整的公钥加密：每人有一对公钥/私钥，公钥公开，私钥保密。用对方公钥加密，只有对方私钥能解密。

RSA 的安全性依赖于大整数分解的困难性：

• 将两个大素数 $p, q$ 相乘得 $n = pq$：极容易
• 给定 $n$，分解出 $p$ 和 $q$：目前对足够大的 $n$ 极难

RSA 加密：密文 $c = m^e \bmod n$（$e$ 为公钥指数） RSA 解密：明文 $m = c^d \bmod n$（$d$ 为私钥指数，满足 $ed \equiv 1 \pmod{\phi(n)}$）

至今没有已知的多项式时间经典算法能分解大整数。但 Shor 算法（1994）证明量子计算机可以在多项式时间内分解整数——这意味着足够强大的量子计算机将击破当前 RSA 部署，推动了后量子密码学（Post-Quantum Cryptography，PQC）的研究。美国国家标准与技术研究院（NIST）于 2022 年选定了首批抗量子算法（CRYSTALS-Kyber 等），并在 2024 年 8 月正式发布为标准（FIPS 203/204/205，基于格密码学与哈希函数）——选定与发布相隔两年，中间是漫长的规范撰写、实现测试与公开评审。

核心四：可证明安全与现代密码学定义#

1980 年代，Shafi Goldwasser、Silvio Micali 等人将密码学建立在严格的数学基础上，核心贡献包括：

语义安全（Semantic Security）：攻击者在看到密文后，无法获得关于明文的任何计算上可行的信息。这是"可证明安全"的基本定义，比香农的完美安全弱（允许计算困难性假设），但在实践中是可实现的。

零知识证明（Zero-Knowledge Proofs，ZKP）：证明者（Prover）向验证者（Verifier）证明自己知道某个秘密，而不泄露秘密本身的任何信息。例如，证明"我知道这个图的三着色方案"，而不说出方案本身。

ZKP 由 Goldwasser、Micali、Rackoff 在 1985 年形式化，其应用从身份认证扩展到了区块链隐私协议（zk-SNARK 等）。

代价与争议#

量子威胁的紧迫性：关于量子计算机何时能达到破解 RSA 所需的规模（估计需要数百万物理量子比特），争议相当大，不同专家预测从 10 年到 30 年不等。当前的后量子密码学标准化是"提前布局"，而非应对已有威胁。

"后门"与信任危机：2013 年斯诺登泄露的文件揭示，美国国家安全局（NSA）曾向 NIST 推动一个带有潜在后门的伪随机数生成算法（DualECDRBG）被纳入标准。这严重损害了公众对密码学标准化机构的信任，也提醒人们：密码算法的安全性不只是数学问题，还是政治和制度问题。

密码学与隐私权：强加密是个人隐私的技术基础，同时也被犯罪和恐怖主义组织利用。各国政府关于是否应强制要求加密"后门"的争论持续至今，没有简单答案。

哈希函数：密码学的瑞士军刀#

密码学哈希函数（Cryptographic Hash Function）是密码学基础设施的另一块基石，与公钥密码学并列：

一个密码学哈希函数 $H$ 把任意长度的输入映射到固定长度的输出（如 SHA-256 输出 256 位），并需要满足： - 单向性：给定 $h = H(m)$，找到 $m$ 在计算上不可行 - 碰撞抵抗：找到 $m_1 \neq m_2$ 使得 $H(m_1) = H(m_2)$ 在计算上不可行 - 雪崩效应：输入的微小变化导致输出完全不同

哈希函数的用途极广： - 数字签名：对消息哈希值签名（而非对原文），避免公钥算法处理大量数据的效率问题 - 密码存储：存储密码的哈希值而非明文，即使数据库泄露也不直接暴露密码 - 区块链：比特币等区块链用 SHA-256 哈希把区块链起来，任何历史区块的篡改都会导致后续所有哈希值无效 - 完整性校验：软件发布附带哈希值，用户下载后可验证文件是否被篡改

MD5 和 SHA-1 已被证明存在碰撞攻击（Wang et al., 2004/2005），不再适合安全用途。目前推荐使用 SHA-2（SHA-256、SHA-512）和 SHA-3（基于 Keccak 算法，2012 年 NIST 标准化）。

椭圆曲线密码学：更小、更快#

RSA 的安全性依赖整数分解的困难性，但它的一个实际问题是：需要很长的密钥（2048 位或更长）才能达到足够安全性。

1985 年，Neal Koblitz 和 Victor Miller 独立提出了椭圆曲线密码学（ECC，Elliptic Curve Cryptography），基于椭圆曲线上的离散对数问题：

椭圆曲线是满足 $y^2 = x^3 + ax + b$ 的点集（在有限域上）。曲线上的点之间可以定义一种"加法"运算，使曲线上的点构成一个循环群。离散对数问题在椭圆曲线群中似乎比有限域整数中更难，因此同样安全性只需更短的密钥。

ECC 256 位密钥的安全强度大约等同于 RSA 3072 位密钥，这在计算资源受限的设备（智能卡、物联网设备）上有显著优势。TLS 1.3（现代 HTTPS 的核心）默认使用基于椭圆曲线的密钥交换（ECDH）。

后量子密码学：应对量子威胁的准备#

如前所述，Shor 算法使量子计算机能在多项式时间内破解 RSA 和基于离散对数的密码系统（包括 ECC）。

NIST 从 2016 年开始征集后量子密码（PQC）标准，2024 年正式发布了首批标准：

• ML-KEM（基于 CRYSTALS-Kyber，格密码）：用于密钥封装（key encapsulation）
• ML-DSA（基于 CRYSTALS-Dilithium，格密码）：用于数字签名
• SLH-DSA（基于 SPHINCS+，哈希函数）：用于数字签名

这些算法的安全性依赖于格上的困难问题（如带错误学习，LWE），目前没有已知的经典或量子算法能在多项式时间内解决这些问题——但"没有已知算法"不等于"不存在算法"，这仍是密码学界持续监测的问题。

从现有基础设施迁移到后量子算法是一项巨大的工程挑战，涉及互联网协议栈的每一层，预计需要数年到数十年。

跨域连接#

• 计算复杂性：这门学科的地基是一个假设而非定理。单向函数存在能推出 P≠NP，反向却推不回来——因为复杂度类谈的是最坏情况，而密码需要随机抽一个实例就难。这条最坏与平均的落差，决定了"证明了 P≠NP 就有安全密码"是错的。
• 信息论：完美保密可以被精确定义为密文与明文互信息为零，并由此推出密钥不能短于明文。这是不依赖任何难度假设的不可能性结论，也正因为代价太高，实用密码才整体退到计算安全：不是攻击者做不到，而是他做不起。
• 数论：公钥体系把安全性挂在群结构上：模幂容易、离散对数难。换一个群，已知攻击算法的形态就变，于是同等安全强度所需的密钥长度可以差一个量级。密钥"多少位才够"因此不是一个通用数字，它随群的选择而变。
• 证伪：没有哪个实用密码方案被证明安全，能被证明的只是"若某问题难，则它安全"这种归约。方案的信誉来自长期抗攻击的记录，这在结构上是可证伪而不可证实的。所以"至今无人破解"是恰当的表述，"绝对安全"不是。
• 全球治理：算法要被全世界采用，必须先经过某个标准化程序，而这个程序本身可以被影响——曾被写进标准的随机数生成器带有后门嫌疑，这件事损伤的不是数学而是信任链。密码的安全性因此包含一段非数学的制度部分，后量子迁移同样是跨国协调问题。

参考文献#

• Shannon, C. E. Communication Theory of Secrecy Systems. Bell System Technical Journal 28 (1949): 656–715.
• Diffie, W. & Hellman, M. New Directions in Cryptography. IEEE Transactions on Information Theory 22 (1976): 644–654.
• Rivest, R. L., Shamir, A., & Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21 (1978): 120–126.
• Goldwasser, S., Micali, S., & Rackoff, C. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing 18 (1989): 186–208. （零知识证明原始论文）
• Boneh, D. & Shoup, V. A Graduate Course in Applied Cryptography. 免费在线版 (2023). [crypto.stanford.edu/~dabo/cryptobook/]