密码学基础

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

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

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

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

另一层常被忽略的误解是：把"算法公开"当成不安全。现代设计遵循柯克霍夫原则——保密应只依赖密钥，规范与实现可以公开评审。安全性来自密钥空间与困难假设，而不是藏起算法细节。与此对照，古典密码常靠"没人知道规则"支撑；规则一旦泄露便整体崩溃。公钥体系把密钥分成可公开的与必须私藏的两半，正是把这一原则推到了极致。

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

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

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

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

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

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

密码学表述里，这一退让常写成计算不可区分性：在多项式时间敌手面前，真实密文分布与某个理想对象（随机串、模拟器输出）无法区分。它与信息论上的"互信息严格为零"不是同一句话——后者禁止任何信息泄露，前者允许泄露，但提取代价在复杂度上不可行。语义安全、IND-CPA/CCA 等游戏化定义，都是把这句话变成可检验的攻防规则：敌手选消息、看密文、再猜比特，优势必须可忽略。工程协议对标的是这些游戏，而不是一次性密码本的绝对静默。

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

迪菲-赫尔曼的核心洞察是：某些数学函数计算容易，逆转困难——即使知道函数本身，给你看函数值，你也无法在合理时间内找到输入。这类函数叫单向函数（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 更强的假设之上——这是密码学最深的基础性未解问题之一。自然证明指出：一类对随机函数也成立的电路下界技术，若强到能分开 P 与 NP，就会毁掉伪随机发生器所依赖的那种硬度。Karp–Lipton 从另一侧说：若 SAT 只有多项式规模电路、没有均匀算法，多项式层次会塌——密码学同样不希望那张表存在。硬度换随机性见 Nisan–Wigderson 1994：难函数可以冒充硬币；指数电路硬度把 $P=\mathrm{BPP}$ 收成条件句，见 Impagliazzo–Wigderson 1997：那是去随机化，不是把 RSA 写成步骤。

协议层面还要分清：迪菲—赫尔曼解决的是密钥协商，不是直接加密长消息。实践中双方先得到共享密钥，再交给对称算法（AES-GCM 等）承载业务流量；TLS 的握手与记录层正是这一分工。裸 DH 还需要认证，否则中间人可以各与两端协商——因此现实部署几乎总与证书、预共享密钥或口令认证绑定。把"1976 年论文"直接等同于"浏览器锁图标"，中间省略了认证与对称层，故事会失真。

核心三：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，基于格密码学与哈希函数）——选定与发布相隔两年，中间是漫长的规范撰写、实现测试与公开评审。

教材上的"裸 RSA"与线上安全的 RSA 不是同一物件：没有随机填充的确定性加密不满足语义安全，历史教训包括选择密文与填充预言攻击。现代用法依赖 OAEP 一类填充，或更多时候根本不拿 RSA 直接加密载荷，而是加密对称会话密钥（混合加密）。密钥长度的军备竞赛（1024→2048→3072）反映的是分解算法与算力的渐进改进，不是数学突变；量子威胁则是另一条曲线，逼着生态准备可替换的算法套件，而不是把模数再加长一倍了事。

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

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

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

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

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

可证明安全的工作方式是归约：先假定某底层问题（分解、离散对数、LWE）困难，再证明若敌手能赢加密游戏，就可构造算法破解该问题。得到的不是"绝对安全"证书，而是一张条件支票。零知识则在交互证明里多加一条：验证者视图可被模拟器伪造，因而协议誊本不泄漏见证之外的知识。zk-SNARK 把交互压缩成短证明，代价是可信设置或通用设置假设；把它理解成"区块链魔法"不如理解成"把 NP 陈述的可验证性做成简洁证据"。

代价与争议#

量子威胁的紧迫性：关于量子计算机何时能达到破解 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 标准化）。

哈希在协议里几乎从不单独完成机密性：它提供完整性与绑定。口令存储若只做一次快速哈希，仍会被预计算表打穿，因此要用缓慢的密钥导出（如 Argon2）加盐；数字签名先哈希再签，是为了把任意长消息压进代数群能处理的摘要。碰撞抵抗被攻破时，受害的是依赖"摘要唯一代表文件"的场景（证书、软件包），而不是所有哈希用法同步失效——区分单向性与碰撞抵抗，才能正确退役算法。

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

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）。

曲线选择本身是安全边界的一部分：弱随机曲线、错误种子或非刚性生成方式，都曾引发不信任。工程上偏好可刚性构造、参数公开可审计的曲线（如 Curve25519 一类），并把常数时间实现当作与数学假设同级的要求——侧信道往往比"突然找到离散对数算法"更早打穿系统。ECC 同样裸奔在 Shor 算法射程内，因此它是当下的效率冠军，不是后量子终点。

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

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

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

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

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

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

迁移的现实策略多是混合握手：经典 ECDH 与 ML-KEM 并行，共享密钥两者都贡献，这样在 PQC 实现尚未久经考验时仍保有经典层的底线，同时开始抵御"现在存储、将来解密"的收获攻击。公钥与密文变长会碰到证书链、UDP 分片与嵌入式内存上限；谁先换、如何双栈、如何回滚，是运维与标准体的活，不是单篇论文能结束的争论。监测格上算法的密码分析进展，应被视为与部署同等重要的持续工作。

跨域连接#

• 计算复杂性：这门学科的地基是一个假设而非定理。单向函数存在能推出 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/]