很多人聊到密码学时第一反应往往是算法本身AES、RSA、SM2、SHA-256……但真要在系统里做选型你会发现算法清单反而是最简单的部分。难的是回答一个问题凭什么信它这个“信”字才是密码学里最核心、也最容易被绕开的工程命题。我入行这些年来被问得最多的不是“怎么实现”而是“为什么这个方案是安全的”。有些人觉得只要算法公开还能扛住攻击就是安全有些人则指望某些机构替自己背书。但真正支撑密码方案可信的不是神秘感也不是权威而是藏在背后的计算困难性理论——一句话概括密码方案的强度不建立在“攻击者看不懂算法”上而建立在“攻击者在计算资源足够多、时间足够长的情况下仍然无法高效解决某个数学问题”上。这篇是系列第3论前两篇分别聊了对称密码的设计哲学和公钥密码的运作逻辑这一篇想认真拆解一下它们共同的地基为什么“已知很难”这件事本身是所有现代密码学立身的根本。内容适合刚接触密码学、被“可证明安全”这类词绕晕的人也适合平时要在系统里做技术选型、需要判断风险边界的工程同学。1. 密码方案的“可信”到底建立在什么上1.1 先别谈算法谈谈“安全”这个词的定义很多人对密码学安全的第一印象来自谍战片里那种“密文打死也猜不出来”的绝对保密。但那是绝对安全的范畴现实中只有一个方案能真正做到一次一密密钥和明文等长、随机且永不复用。这个方案数学上无懈可击但工程上几乎没法用——你得先把同等体量的密钥安全送到对端那这个密钥本身又该怎么送这直接变成了鸡生蛋问题。所以实际密码学退了一步把安全定义为计算安全只要破解某个方案所需的时间或资源超出攻击者能承受的上限就可以认为它在现实里是安全的。比如你要暴力枚举256位密钥假设用地球上全部算力并行计算所需时间也远远超过宇宙年龄。这就是“计算上不可行”不是“逻辑上不可能”。这个定义有一个关键推论安全的根基必须依赖一个“我们相信很难”的计算问题。为什么是“相信”而不是“证明”因为严格数学意义上我们其实还无法证明大多数困难问题真的困难。P和NP是否相等至今悬而未决一旦两者相等大量看起来很难的问题都会瞬间变得可解。所以密码学本质上是一门把安全建立在假设上的工程学科这也解释了为什么“假设是否可靠”永远比“算法是否复杂”更重要。1.2 困难问题要的不是“最坏情况”难而是“平均情况”难这里有一个非常容易踩的认知陷阱。复杂性理论里说的“难”通常指最坏情况某个问题在规模增大时至少存在一个实例让所有算法都束手无策。比如很多NP完全问题你想找反例很容易但想让每一个随机实例都难反而很麻烦。密码学恰恰要的是平均情况下的困难。想象一把锁它的锁芯安全性不是取决于“世界上存在一扇打不开的门”而是取决于“每一扇装这把锁的门都很难被打开”。攻击者当然可以挑选对自己有利的实例来破解但你的密钥是随机生成的密码方案也是在随机化场景里运行的所以只要“随机抽取一个实例求解它仍然困难”安全就能成立。这也是为什么密码学没有直接押注在那些“定理级困难”的问题上而是选择了大整数分解、离散对数、椭圆曲线离散对数等表面上“没有证明、但几十年来全世界顶尖研究者都没找到快速算法”的问题。换句话说密码学信的不是数学定理而是长期对抗时间沉淀下来的共识。2. 单向函数密码学信任的最小公约数2.1 单向函数到底是个什么东西如果说计算困难性理论是密码学的地基那单向函数就是地基里的第一块砖。单向函数的定义很直白正向计算很容易逆向计算极其困难。比如把两个大质数乘在一起几毫秒就能算完但给你一个大数让你分解回质数可能耗尽所有算力也拆不开。这就是一个典型的“正向容易、反向困难”过程。哈希函数也体现单向性。你可以很快算出某个文件的SHA-256摘要但你想从摘要反推原文唯一可行的方式就是暴力猜。公钥密码更不用说了公钥和私钥之间靠的就是单向关系别人拿到公钥也推不出私钥否则整个体系直接崩塌。但是注意一个残酷的事实到现在为止还没有人证明单向函数真的存在。如果有人证明了单向函数不存在那绝大多数现代密码学都会失效。所以在密码学内部大家心照不宣地使用一个假设单向函数存在。所有看似坚固的方案最终都归到这个假设上。这不是密码学家的偷懒而是现实约束下的理性选择——毕竟人类目前造不出一种既足够高效又已被数学证明不可逆的运算。2.2 公钥密码学是如何依附在单向性上的以公钥加密为例。整个体系要成立需要两把钥匙公钥可以公开私钥必须保密。攻击者拿到公钥后做什么他想从公钥推导出私钥或者从密文还原明文。无论哪条路最终都会撞上某个困难问题。RSA风格的方案依赖大整数分解的困难性公钥里包含一个大合数私钥本质上对应它的质因子知道质因子就能解密但不知道质因子就只能硬扛。离散对数类的方案比如ElGamal、ECDSA则是另一个逻辑给你一个群里的元素和它的幂让你反推出指数这在大群里同样没有快速算法。椭圆曲线加密则更进一步把离散对数放到椭圆曲线群上同样的安全强度下密钥可以做得短很多。有意思的地方在于这些方案的安全证明都不是“一步步证明攻击者无法攻击”而是“如果攻击者能攻破方案那他就一定能解决某个公认困难的数学问题”。这就把安全判断从复杂的密码协议收敛到相对简单、被研究了几十年的数学难题上。这也是为什么“归约证明”会成为现代密码学的主流方法后文会单独展开。3. 几大困难问题家族的现状与安全成本3.1 大整数分解RSA为什么要把密钥堆到2048位大整数分解是一个经典问题。小学我们就知道任意整数可以唯一分解成质数乘积但“唯一分解”和“很快分解出来”是两回事。试除法在小数上很好使一旦数到了几百位直接枚举质因子就变成天文数字。后来的算法不断优化从Pollard rho到数域筛法复杂度从指数级降到了亚指数级但依然无法处理足够长的合数。这直接决定了RSA的密钥长度。风险在于如果你用1024位RSA业界普遍认为它已经处于可被国家级力量攻破的边缘很多合规要求会明确拒绝。而2048位RSA的安全强度大约相当于112位对称密钥考虑到未来十年算力增长和安全边际很多场景已经建议直接上3072位。这里有一个很多新手容易误解的点位数的意义不是线性增加的。RSA从2048位升级到3072位不是把安全强度从112提到168那么简单你得看具体分解算法的复杂度增长曲线。实际工程里与其纠结“差几十位”不如先确认自己使用的协议、填充模式、随机数来源是否可靠——这些环节的漏洞往往比位数不足更致命。3.2 离散对数与椭圆曲线为什么256位曲线能扛住128位安全强度离散对数问题和大整数分解是“表兄弟”形式不同但结构相似在一个大循环群里给定生成元和某个元素求指数很难。传统有限域离散对数需要与RSA相当的长度来保证安全比如2048位有限域才能达到112位左右的安全强度。但椭圆曲线离散对数更“抗打”目前已知最好的通用算法是指数级的不存在像数域筛法那样明显的亚指数加速所以256位曲线就能达到约128位安全强度。这也是ECC最大的工程价值密钥短、签名短、握手数据小对移动设备和物联网设备尤其友好。但这里要提醒一句ECC的安全性不光看曲线位数更要看曲线参数来源和具体实现。历史上出现过不少因为曲线选择不当或随机数重复导致私钥泄露的真实事故。一块短板就能让几百位安全的数学基础形同虚设。对日常选型来说我会给这样一个判断顺序先把AES、SHA这类对称原语的基础打牢再根据系统交互场景选公钥算法最后才是“用多大参数”的问题。参数再大如果方案逻辑或实现有洞一切都白搭。3.3 格困难问题量子时代的接班人说起量子计算对密码学的冲击很多人只知道“RSA会被破解”但对为什么还没全面替换感到困惑。原因在于当前真正有实用价值的量子计算机还造不出来但理论威胁已经真实存在。比如Shor算法表明一旦量子计算机发展到足够规模大整数分解和离散对数都能在多项式时间内解决。也就是说RSA、ECC这些传统公钥体系在量子时代会整体失效。格密码是当前呼声最高的替代方向。它的困难性基于格上的一些问题比如最短向量问题SVP、带误差学习问题LWE目前既没有经典高效算法也没有已知的量子高效算法。很多后量子密码标准候选方案都建立在格问题上行业也在逐步推进相关标准的落地。但格密码不是“免费的午餐”。它的密钥和密文通常比传统方案大很多计算开销也更重直接替换会带来明显的性能压力。更重要的是格问题也还没有被证明困难它同样是一个计算困难性假设只是受损于量子计算的风险目前相对可控。所以“后量子安全”这个词更多是指“当前已知攻击手段下仍安全”而不是绝对安全。4. 可证明安全把“假设”翻译成“保证”4.1 一条归约链的完整逻辑如果你看过密码学论文一定见过这句话在某某困难性假设下某方案是选择密文安全的。这句话听起来晦涩本质却很简单通过归约证明把一个安全目标绑定到一个困难问题假设上。具体流程大概是这样的。假设存在一个敌手A能以不可忽略的概率攻破某个加密方案。证明者设计另一个算法BB要做的事情是伪装成一个正常的加密环境让A在里面“干活”同时B偷偷把困难问题的实例嵌入到方案参数或密文中。如果A真能攻破方案B就能借着A的输出解开那个困难问题。这与你我认知中的困难问题假设矛盾。于是结论成立A不可能存在或者说如果A存在那困难问题也不困难了。这个逻辑链等于在说你不需要一行一行审查加密方案本身是否完美你只需要相信那个底层数学难题确实难解。这就把复杂的系统安全问题收敛成了一个相对简单的判断。像ElGamal加密、RSA-OAEP等经典方案都有类似的归约支撑行业里把它们统称为“可证明安全”。不过这里要泼一盆冷静水。归约证明里的“模拟环境”往往有条件限制比如某类随机化的分布必须理想化或者敌手不能问某些额外的问题。现实攻击者不一定会按论文里的假设行动。所以可证明安全不是万能的免死金牌而是一张“在特定模型下可信”的质检报告。4.2 随机预言机与理想模型信任在这个环节是怎么分配的论文里经常出现一个词随机预言机模型Random Oracle Model。这个模型把哈希函数当作一个完全均匀的随机函数每次查询都返回一个相互独立的结果。这在理论上非常方便因为设计证明时可以让一个模拟器悄悄观察敌手的查询记录针对性构造答案从而完成归约。问题是真实世界里的哈希函数比如SHA-256并不是随机预言机它有确定的内部结构。虽然目前没有发现破坏性的弱点但“理论证明依赖的假设”和“工程实际使用的原语”之间天然存在一道缝隙。也正因如此密码学界一直有人追求所谓的“标准模型”可证明安全不依赖随机预言机这种理想化假设。从工程角度怎么看待这个问题我的态度是不要迷信“有论文证明”就高枕无忧也不要因为“证明很理想化”就全盘否定。更务实的做法是看两层一是方案所依赖的困难问题是否被长期研究、是否可靠二是方案的原语选择是否主流、有没有经过充分的公开分析。这两层都过关即使证明模型存在理想化成分工程风险依然可控。4.3 安全强度的量化bits of security与实际参数选择我们经常听到“128位安全强度”的说法这个数字到底什么意思它指的是破解该方案所需的计算量大约等同于暴力破解一个128位密钥的计算量。通俗讲就是攻击者最多需要尝试2的128次方次操作这在现实中是不可能完成的。安全强度概念的价值是让你能把不同算法放在同一把尺子上比较。比如RSA-2048大约相当于112位安全强度ECDSA使用256位曲线大约相当于128位安全强度AES-256则是256位。你不需要自己去复现攻击复杂性分析只需要查阅成熟的安全强度对照表就能判断一套方案的“安全余量”是否符合要求。下面是我在项目里常用的一个粗略对照参考技术路线困难问题常见参数大致安全强度量子威胁RSA大整数分解2048位约112位Shor算法威胁大有限域离散对数DLP2048位约112位Shor算法威胁大椭圆曲线ECDLP256位曲线约128位Shor算法威胁大后量子方案格问题LWE/SIS视方案而定视参数而定目前相对乐观实际选参数时我还会多考虑一层兼容性。比如有些老旧系统只支持某个固定长度的证书强行上太长参数会导致协议握手失败。这种问题不是“算力不够”而是“生态不兼容”在迁移时往往更磨人。提前做兼容性验证比事后调参重要得多。5. 信任的边界可证明安全没证明什么5.1 假设本身也只是一块“信任积木”写到这里必须把话说透计算困难性理论给密码学提供了可信地基但这块地基并不是花岗岩它更像一块经过长期压力测试的钢板。钢板很结实但依然可能在未来被发现裂缝。密码学界常用的表述是“在某某假设下安全”这个条件句本身就说明一切如果假设被推翻方案的安全论证也随之作废。这带来一个非常实际的工程教训不要在一套系统里把所有安全都押在同一块“困难问题”上。比如当你使用RSA时至少应该在协议层引入良好的随机数机制、使用经过验证的填充方案而不是单纯相信“算法安全”就完事。很多真实攻击根本不碰数学困难问题而是专挑实现细节下手。安全是一个叠加态困难性只是其中一维。另外要对“被证明安全”这句话持有合理的怀疑。归约证明解决的是“方案本身有没有结构性漏洞”的问题不解决“实现过程中有没有被注入旁路缺陷”的问题。如果你用的是纯软件实现还要考虑侧信道攻击、内存泄露、随机数退化等现实威胁。这些都不是数学难题但往往比数学难题更容易被攻破。5.2 量子计算的威胁到底有多大量子计算对密码学的冲击要分场景看不能一刀切。对传统公钥密码RSA、ECC威胁是实质性的。Shor算法把分解和离散对数拉到多项式时间一旦实用型量子计算机出现这类方案就形同虚设。所以如果有数据需要在未来很长时间内保持机密现在就得开始评估迁移到后量子方案的路线。对对称密码AES和哈希函数情况就缓和得多。Grover算法可以把密钥搜索的计算量降为原来的平方根也就是说128位密钥在量子攻击下等效强度降为64位256位密钥降为128位。所以业界普遍认为AES-256在量子时代依然够用这也是很多系统开始要求对称密钥长度至少256位的原因之一。后量子密码的标准和实现还在演进直接大规模替换并不现实但“逐步备胎化”是值得做的在允许的情况下对核心敏感数据采用混合方案关键业务兼容多种算法族。等到哪天真有实用的量子算力出现你不需要从零开始重构系统只需切换算法即可。5.3 常见误区自查表下面这张表是我在评审方案时经常拿出来对照的清单你可以把它当成一篇快速自检工具常见误区实际情况“可证明安全就等于绝对安全”可证明安全是条件性的依赖困难问题假设和证明模型“参数越大越安全”参数过大可能导致兼容性和性能问题且不弥补协议或实现漏洞“哈希函数只是单向的”哈希还需要抗碰撞、抗长度扩展等额外性质不同用途要求不同“后量子方案反正还没量产先不管”对长期敏感数据而言威胁是现实的建议提前做迁移评估“密钥长度决定一切”随机数质量、协议设计、实现正确性同样至关重要这些误区在真实项目中几乎每隔一段时间就会遇到一次。特别是第四条很多人觉得量子计算是远水不解近渴但在数据保密期长的高安全场景里今天加密的数据明天就可能被记录下来留给未来破解。密码学里的一个基本原则就是数据保密时间必须长于你的安全预期寿命。6. 我踩坑多年后留下的三点习惯如果非要把这些年的经验压缩成可执行的东西我会留下三句话。第一句写设计文档时先明确“这个方案的安全最终依赖于哪个困难问题”。把假设写清楚等于把信任边界画出来。一旦依赖的假设变化系统受影响的范围立刻就能看出来。第二句看方案时先看有没有归约证明再看证明依赖什么模型最后才看算法参数。顺序搞反了很容易被看起来很长的密钥长度迷惑忽略了真正的结构性风险。第三句永远给随机数生成器留最高的关注度。很多公钥密码系统的崩溃不是数学难题被解开而是随机数发生器被污染、重复导致密钥可预测。故障是偶发还是必然往往就在这一处。这三点是我在几次惨痛的项目复盘里沉淀下来的谈不上创新但确实帮我避掉了很多坑。密码学技术上承抽象数学、下接工程实现中间那一层“计算困难性”承重墙值得每一个做系统的人花时间理解。它决定了你建立在数学和代码之上的信任到底有多大的安全边际。
