你每天点开浏览器里那把小小的锁头时，有没有想过：我们凭什么信任它？

做了这些年安全相关的工作，我几乎每天都要和加密、签名、密钥协商打交道。不管是给设备做固件签名，还是给业务系统设计数据保护方案，每次在文档里写下“密钥长度 2048”“使用标准椭圆曲线”，本质上都是在做同一个动作：把系统的安全寄托在某个数学问题的“难”上面。这个“难”到底是什么、从哪来、凭什么让我们相信，其实值得认认真真拆一遍。这篇是这个系列的第三论，核心话题就是密码学信任的底层逻辑——计算困难性理论。我会从“难”的定义讲起，聊到支撑现有密码体系的具体困难问题，再讲透归约证明这个最容易被误解的概念，最后看看量子计算和工程实践给我们提了什么醒。适合想深究原理的开发者，也适合刚入行想建立安全直觉的同学。

1. 先把“难”这件事说清楚

1.1 理论上的不可能与工程上的不可行

先说一个很多人没绕过来的弯。密码学几乎从不承诺“数学上不可能破解”。严格地说，一个加密算法对攻击者而言，理论上永远存在破解路径——最笨的办法就是把密钥空间穷举一遍。真正被依赖的，是“计算上不可行”：完成破解所需的时间和资源，大到在现实世界里没有任何人或机构愿意承担。

拿一个生活化的例子来体会：假如我把一张额度极高的银行卡锁在保险柜里，并且告诉全世界“密码是 12 位纯数字，你随意试”。理论上只要尝试组合可能中的 10¹² 个，就一定能打开，但若每秒试一亿次，也要三小时左右——这还不算锁具本身的防暴拆机制。要是把密码变成 20 位，一亿次每秒的速度需要约 3 万年，这个“困难”就不是时间长短的问题，而是本质上已经排除了现实攻击。密码学的“难”，就是这种把破解成本抬高到天文数字的工程学设计。

所以评估一个密码方案是否安全，首先要问的不是“能不能破解”，而是“以今天的算力，破解它需要付出什么代价”。这个代价通常用“操作次数”计量，和算法复杂度直接挂钩。

1.2 复杂度语言的入门翻译

要理解“难”，绕不开复杂度这个基本工具。计算机科学家把算法按运行时间随输入规模增长的速度分类：能在多项式时间（比如 n² 或 n³，这里的 n 是输入尺寸）内跑完的，叫“高效”；需要指数时间（比如 2ⁿ）的，叫“困难”。排序 n 个数是多项式复杂度，所以几亿条记录排序也就是秒级的事；反过来，如果某个任务只能靠 2ⁿ 级别搜索，n 到 128，这个数字已经超过可观测宇宙中原子的数量级，就是字面意义上的“算到天荒地老也搜不完”。

由此引出 P 与 NP 这对概念：P 是能在多项式时间内解决的问题集合，NP 是“给出答案后能在多项式时间验证”的问题集合。密码学感兴趣的困难问题多数落在 NP 里，但这里有个关键细节——NP 困难指的是最坏情况困难，而密码学需要的是平均情况也困难，最好还得有随机化生成实例的途径。换句话说，“这是一个 NP 问题”这句话，离“用一个密钥长度就能放心”还差得很远。常有同学把我这个点搞混，把 NP-Hard 和“密码学安全”直接划等号，中间其实隔着一整条“世间是否存在足够多的难实例”的河。

具体到数字，不同问题的难度形状差别很大。比如分解一个 n 位合数，目前最好的一类通用算法，运行时间约是 exp(O(n^(1/3) · (log n)^(2/3))) 这个量级，既不是多项式也不是纯指数，被称为次指数复杂度。正因为难度曲线的斜率不够“陡”，这类问题才需要非常大的参数来补偿。

1.3 安全参数与安全级别

密码学里衡量强度用的是“安全级（security level）”，单位叫 bit。一个方案有 128 bit 安全级，意思是攻破它的最优算法，平均需要执行约 2¹²⁸ 次基本操作。2¹²⁸ 是什么概念？就算全世界所有计算机加一起，每秒能执行 2⁵⁰ 次操作（这早就远超现实），连续算一年也只有大约 2⁷⁵ 次，距离 2¹²⁸ 还差着 2⁵³ 倍。所以 128 bit 安全级被普遍当作“够用”的基线，也是目前绝大多数在线系统默认的安全水位。

这个体系顺带解释了一个参数直觉：密钥每增加 1 bit，暴力破解的搜索空间就翻一倍。这也是为什么 AES-128 和 AES-256 的安全性差异，不是“大两倍”，而是“大 2¹²⁸ 倍”。很多人问我要不要从 AES-128 升到 AES-256，我的回答通常是：如果只是怕暴力破解，128 已经很稳；真正要担心的是随机数质量、密钥管理流程和协议实现里的旁路漏洞，那才是现实中出事的地方。

2. 密码学赖以生存的“困难问题家族”

理论归理论，落到实处，工程上真正依赖的是几个被研究了数十年的具体困难问题。我把它们按“地基”的方式列一下，每个都附上应用场景和攻击难度画像。

2.1 大整数分解：RSA 类方案的地基

第一个里程碑是大整数分解。把两个大致同数量级的大质数乘起来是一瞬间的事，但给一个上千位的合数找出它的质因数，目前全世界都找不到多项式时间算法。最好的一类通用算法（数域筛法系列）的运行时间是非多项式的，换算一下会发现：想达到 128 bit 安全级，模数得选 3072 bit，而不能像 RSA 早期那样用 512 bit。说白了，就是因为分解问题的“难”长得不是特别快，才需要用更大的数字把安全级顶上去。

公钥加密体系里，RSA 一类方案的安全性就建立在这个假设上：没有模数的质因数，就无法完成解密所需的计算。所以要评估 RSA 是否安全，重点不在“加密算法本身”，而在“给你一个 2048 位的合数，能不能在合理时间内把它分解”。

2.2 离散对数问题：密钥协商的传统支柱

第二个常驻角色是离散对数问题，发生在循环群上。给一个生成元 g 和元素 h=gˣ，求指数 x，被公认为很难。这个问题的历史比 RSA 还早，经典的密钥协商协议和一系列签名算法都建立在它的变体上——双方不需要预先共享秘密，能在公开通信里完成密钥交换，完全依赖离散对数的难解性。

在有限域版本中，攻击算法（指标计算一类）依然是非多项式但成长较快的，所以传统 DH 参数动不动就要 2048/3072 bit 的大素数。这里有个容易被忽略的细节：并不是所有群都一样难，同样的离散对数，在特定结构异常的群里可能脆到一碰就碎，所以现代实践都强调“必须用标准化且经过审计的群参数”。这个“参数陷阱”在我的项目评审里出现次数不少。

2.3 椭圆曲线离散对数：为什么能“小马拉大车”

第三个主角让密码学第一次尝到“小钥匙”的甜头：椭圆曲线离散对数问题。跟有限域离散对数不同，椭圆曲线上目前最优的通用攻击算法仍然是指数级（针对精心挑选的曲线），这就导致同样的 128 bit 安全级，曲线参数只要 256 bit 就够了——相对 RSA 的 3072 bit，存储、传输和计算量全都大幅下降。这也是为什么移动端、嵌入式设备和车机部件普遍偏爱 ECC 类方案。

但要小心：“椭圆曲线安全”这句话只在“曲线本身没被埋雷”的情况下成立。历史上出现过参数选择不当导致生成子群阶过于光滑、或实现时没校验点是否在曲线上的经典翻车案例。我的经验是：既不要随便拿一条自造的曲线，也不要为了省几个字节手动实现一组点运算，直接用经过审查的命名曲线，把倍点运算交给经过验证的库。

2.4 格上问题：后量子时代的新地基

第四个家族是近年最热门的格上问题，代表是带错误学习问题（LWE）及其变体。格的直观形象可以理解成一个多维空间的“晶体点阵”，困难在于高维空间里找到最短非零向量这类几何问题，即使在量子计算机上也没有已知的高效算法。这类问题有一个非常强的性质：可以从最坏情形的问题实例归约到平均情形，这意味着“随便抽一个随机实例”的难度都有理论保障，比很多老问题更接近密码学需要的平均困难性。

因为量子算法能把前面三个家族“团灭”，格上问题就成了后量子密码方案的首选地基。目前已进入标准化视野的密钥封装方案和数字签名方案，相当一部分都是从格上难度出发的。它们用相对紧凑的参数换来较高的安全强度，代价是实现复杂度和密钥尺寸比传统方案大一些——这就是“换地基”必须付的工程成本。

为了直观，我把四个家族放在一起对比：

表格里的“次指数”和“指数”的差别，正是 RSA 需要 3072 而 ECC 只需 256 的根源。同样的 128 bit 安全级，不同家族付出的参数代价相差一个数量级。安全级是“结果的衡量”，而参数选多大，要看具体难题的攻击曲线长什么样。

3. 信任的真正载体：归约证明

3.1 为什么“问题难”还不够

很多人以为密码学安全等于“背后的问题难”，这其实只对了前半截。问题再难，如果加密方案的构造方式存在漏洞，攻击者可以直接绕过难题去拆你的算法。所以现代密码学建立安全信任的方式非常特别：归约证明（reduction proof）。简单说，就是写一份数学论证，证明“如果存在一个有效的攻击者能攻破我的方案，那么我就能拿这个攻击者当子程序，构造出一个解决底层困难问题的算法”。由于底层问题被公认为不可解，这个攻击者就不可能存在。一句话：把方案的安危，死死拴在公认难题的脖子上。

3.2 一次简化归约的推演

丢掉复杂的公钥背景，直接看骨架。假设有一个方案 S，它的公钥是 h=gˣ，私钥是 x。我们想证明：如果 S 被攻破，就能解离散对数。归约构造一个挑战者 C，它收到一个离散对数实例 (g, h*)，需要算出 x*。C 把 h* 伪装成 S 的公钥发给攻击者 A，A 声称能攻破 S。这里的关键是，C 不知道 x*，但它依然可以在不加密真实消息的情况下回答 A 的各种询问——只要方案设计允许 C 做“模拟”。最终，如果 A 成功输出一个能把消息正确解密出来的能力，C 就能从 A 的输出中提取出关于 x* 的信息，从而解决离散对数。逻辑闭环完成。

# 归约骨架（伪代码） def reduce_CDH_to_breaking_scheme(adversary): dlp_instance = receive_dlp_instance() # 拿到一个难问题实例 pk_for_adversary = embed_instance_into_public_key(dlp_instance) oracle = create_simulated_decryption_oracle() # 注意：这不是真解密 attack_output = adversary(pk_for_adversary, oracle) solution = extract_solution(attack_output) # 从攻击者输出中提取答案 return solution # 若顺利返回，则难问题被解决 -> 矛盾

这段伪代码展示了归约的标准套路：模拟、嵌入、提取。每一处设计都要保证攻击者看不出公钥是被修改过的；一旦看出任何异常，归约就失效。这也是为什么做归约证明的论文动辄几十页——细节全在这些“不能穿帮”的模拟里。

3.3 随机预言机模型与现实之间

现实中的归约往往需要模型假设。最常见的做法是随机预言机模型（ROM）：证明时把哈希函数当成一个完全随机的函数，也就是每次查询都返回一个均匀随机数，且相同输入一定返回相同输出。在这个模型里，攻击者访问哈希只能靠“问”，而证明者可以“偷看”查询列表并暗中做手脚——正是这个自由度，让很多漂亮证明得以成立。

麻烦在于，真实世界没有随机预言机，任何实现里哈希都是确定性的算法。因此 ROM 下的证明是一个“强有力的参考信号”，却不是百分之百的定心丸。工程上怎么处理这种不确定性？我的做法是遵循两条铁律：第一，尽量选用同时在标准模型下有证据、或者经过长期对抗检验的方案；第二，绝不因为某个变体在 ROM 下“证明了安全”，就去魔改它的哈希链路。

3.4 归约能证明什么、不能证明什么

读了上面这些，你应该已经能判断，一个归约证明到底承诺了什么。它承诺的是：只要底层假设成立，在特定的攻击模型内（比如攻击者只能黑盒访问、不能看时间抖动和功耗），攻破方案和解决难题是等价的。这就是“条件安全”。

它不能承诺的至少有三件事。第一，假设本身没被证明，连 P≠NP 都没有定论，更别提具体难题的平均难度了。第二，归约的“紧密度”——如果从“攻破方案”到“解决难题”的转化过程额外放大了很大的计算量，归约虽成立，却几乎不提供任何可操作的安全参数指导。第三，也是实战中最关键的：所有形式化证明都默认攻击者只按模型内的规则玩。真实世界里层出不穷的时间攻击、缓存侧信道、故障注入，全都不在这个数学模型里。我审过不少带着漂亮证明的方案，最后出事的地方从不在数学，而在实现。

4. 参数和密钥长度背后的“算账逻辑”

4.1 安全级别的本质

理解了归约，再看密钥长度就顺了。安全级本质是“攻击者必须付出的运算量上界”。128 bit 安全级不是说“加密 128 bit 的密钥”，而是说任何攻击都要 2¹²⁸ 量级的操作。由于并行化并不能减少总操作数，只会缩短墙钟时间，所以评估安全级时可以完全无视攻击者有多少台机器——那只是速度问题，不是总成本问题。

这也顺便解释了为什么量子搜索算法对对称密码的影响是“降级一半”：它把 N bit 密钥的安全级从 2ᴺ 压到 2^(N/2)。AES-128 被压到 2⁶⁴，这在长期对抗中有点边缘化；AES-256 被压到 2¹²⁸，依然是可靠水位。所以后量子时代的一句话版本是：对称密码加长密钥就能续命，公钥密码加长密钥也没用，必须换算法。

4.2 一批常用的密钥长度对照

下面这张表是业界常用的换算关系，也可以当作方案选型时的起点：

注意这表只能当参考坐标，不同标准机构的建议存在细微差异，落地时以当前主流配置基线为准。它真正想告诉你的是比例感：同样是 128 bit 安全级，RSA 类要用 3072 bit，ECC 只用 256 bit；到了 256 bit 安全级，RSA 类已经膨胀到 15360 bit，而 ECC 不过 512 bit。公钥长度和签名、密文大小的差距，直接影响握手包大小、存储成本和电池寿命——这也是现代生态普遍拥抱 ECC 的物理原因。

4.3 破解的成本账

再算一笔更世俗的账：破解要花多少钱。假设一个攻击系统每秒能做 2⁴⁰ 次运算（这已经是很豪华的算力池，大约相当于数万台高性能服务器全速运转），一年也只有约 2⁵⁷ 次。想凑够 2¹²⁸ 次，需要让它连续跑 2⁷¹ 年。这个数字远超恒星寿命，所以从工程视角看，“暴力破解 128 bit 密钥”是一个永远不会进入成本预算的选项。真正可能进入预算的，是那些安全级被算错的边缘场景——比如 64 bit 安全级的陈旧算法、被量子搜索压到 2⁶⁴ 的旧对称协议、或者被裁剪到安全冗余不足的签名参数。攻击者不傻，他们只挑成本收益最划算的软柿子。

4.4 参数之外的信任拼图

最后必须提一嘴：密钥长度只是信任等式的一边，随机源质量是另一边。如果随机数生成器坏了，哪怕你用了 4096 bit 的 RSA，因为多台设备偶然共享了某个素数因子，攻击者可以靠批量求最大公约数还原出私钥。这类事故在现实里出现过不止一次，根因几乎都不是数学，而是熵源不足、种子重复、或者设备在启动早期产出可预测的随机数。

所以我在落地项目里的固定评审项必然包含三件事：随机数生成器的熵源与状态管理、私钥的生命周期与备份策略、密钥轮换与吊销流程。数学给你的是“上界安全”，只有把这套工程拼图补上，才算真正把信任落到了地上。

5. 困难性理论的裂缝：量子危机与假设失效

5.1 量子算法如何改写难度排序

计算困难性是历史产物，不是自然法则。量子计算对它的冲击，本质上是改变了我们估算“操作次数”的方式。对对称密码，量子搜索算法带来大约平方根级别的加速，所以威胁可控，把密钥长度翻倍就能对冲；对 RSA 和离散对数这类问题，量子周期估计算法直接把难题降成了多项式级别的问题，意味着“密钥再长也没用”。这个差别是很戏剧性的：一个是把安全级减半，一个是把安全级清零。

理解周期估计不需要太多物理。假如有一个函数 f(x) 满足某种周期性，量子计算机可以通过巧妙叠加把周期信息“提取”出来；而质因数分解恰好可以转化成一个求周期的问题。于是，大整数分解从“被认为需要几千年”一下子变成“理论上是多项式时间”。这正是整个行业着急忙慌往格上搬的原因。

5.2 后量子方案的新地基

既然老地基在量子视角下会塌，就要换新地基。目前信任度最高的是格上问题，其次是哈希函数签名、纠错码类和多变量类方案。格方案的优势前文已经说过：有最坏情况到平均情况的归约，参数紧凑，性能可用。哈希类签名走的是另一条思路，不依赖任何数论难题，只依赖抗碰撞哈希的存在性，安全性直觉最朴素，但签名与密钥尺寸偏大。基于纠错码和多元方程式的方案各有特色，也都经历了从理论到工程筛选的过程。标准化机构这几年陆续推出了第一批后量子算法清单，方向性已经很明确：先过渡、再替换、老算法逐步退役。

5.3 历史上“假设崩塌”的教训

回看密码学的发展史，真正让方案崩掉的往往不是“理论被彻底推翻”，而是“参数落后于算力或算法进步”。早年流行的短模数公钥，被证明在有限预算内可以分解，于是全行业被迫把参数大幅上调；也曾有哈希函数被找到高效的碰撞攻击，当年跑在它上面的签名方案一夜之间变得不靠谱。这些教训的共同点是：困难性假设本身没被“证伪”，但它的实际难度曲线比当初估计的更陡，原先的安全级在现实里缩水了。

这也给了我一个很深的工作习惯：永远把“迁移能力”当作系统设计的一等公民。密钥参数、算法标识、协议版本都要做成可配置、可独立升级的，而不是把某一代的数学假设焊死在代码里。不是每条代码都能活到量子时代，但一条留有迁移通道的代码，可以随时被新方案接替。

5.4 工程里怎么维护这份信任

总结成四句操作建议。第一，用标准库和标准算法，不要自创、不要魔改参数字段；第二，优先选带认证加密、前向保密的现代协议，少碰那些“只加密不看完整性”的原始构件；第三，关注生态迁移节奏，定期核对自身组件以及依赖链上那些算法的退役时间表；第四，为长远计，在允许混合加密的场合把传统算法和后量子算法叠加，两头下注，避免将来某天被迫一把梭。我在好几个存量系统的升级方案里就是这么做的：先是双算法并行，观察性能和兼容性，再逐步把旧算法流量切走。信任不是一朝建立的，切换信任也一样，得给迁移留出时间。

6. 常见困惑与经验速查

6.1 五个高频困惑

问得最多的五个问题，我统一回一遍：

Q1：P≠NP 还没证明，凭什么敢用密码学？ 因为密码学需要的不是“证明问题真的难”，而是“全世界的顶尖攻击者长期找不到高效算法”，这是经验事实，不是数学定理。准确表述是：我们生活在一个需要“足够难”而不是“绝对难”的世界里，而工程决策本来就是基于证据和概率下注的。

Q2：AES 这类对称密码靠哪个困难问题？ 严格说，对称密码并不归约到某个公开的困难问题。它的安全性靠的是自身结构足够复杂，经过大量密码分析后没发现本质弱点，所以安全预期一般用穷举密钥的下界来标定。这也是 AES-256 对量子搜索仍然够稳的原因——对抗措施就是密钥长度。

Q3：量子计算机现在能做什么？ 这里要区分理论算法和物理实现。周期估计算法的理论潜力早就清楚，但目前还没有能对实际密码学规模跑出优势的机器。问题是没有人能承诺“哪天不会”，所以迁移动作必须提前，而不是等灾难发生。

Q4：随机预言机模型下的证明算数吗？ 算数，但要当成“重要参考”而不是“绝对保证”。它说明方案设计没有结构性缺陷，却不保证任何具体哈希实例化以后仍然安全。落地时用保守参数、用经过多年实战检验的方案，比单纯迷信一个证明更稳。

Q5：我该用多长的密钥？ 以当前主流配置为锚：对称加密不低于 128 bit 安全级；公钥加密与签名选择标准化机构推荐的当代算法和参数；能上 ECC 的时代就优先 ECC，但涉及旧系统兼容、后量子顾虑时按迁移灰度逐步升级。不要拍脑袋，也不要为了省几个字节把安全边际压榨到零。

6.2 一张误区对照表

和团队讨论方案时，我最爱用下面这张表做开场，把常见话术里的模糊地带直接摊平：

把“数学难”“证明有”“参数够长”这些离散的碎片拼到一起，才会得到一个不夸张也不焦虑的判断。后面如果有人再跟你说“我们的系统用了银行级加密”，你可以心平气和地问一句：它归约到哪个困难问题、采用什么模型、安全级多少、随机数来源在哪。问完这四句，大部分含混的话术就自动退场了。

做了这么多年和密码学相关的事，我自己的心态从“觉得数学很强大”慢慢变成了“敬畏它的脆弱”。计算困难性理论给了我们一个珍贵的礼物：它在“绝对安全不可得”的现实里，为互联网凿出了一个“足够安全”的容身之所。但这个礼物本身是一份概率性的信任，靠的是几十年全球攻击者没能找到快捷键，靠的是一轮又一轮标准化和参数升级的接力。所以每次给一个系统划上安全参数，我总会多问自己一遍：如果这个假设明天突然变得不成立，我的系统能不能活着走完迁移的过渡期？把退路想清楚了，剩下的工程操作反而简单。第三论就先到这里，下一篇打算从“信任锚”的角度继续走，聊聊证书体系里那根最顶端的信任到底是怎么安置、怎么传递的。