前阵子做内部技术分享我把一套加密方案的选型和部署从头到尾捋了一遍台下有开发同学问了一句你说了这么多算法名到底凭什么让我们相信这套密码学方案是安全的我愣了一下因为要讲清楚这件事绕不开一个常被科普视频一带而过、但恰恰是整套体系最底层的地基——计算困难性理论。市面上绝大多数密码学科普都会不厌其烦地告诉你“数学上不可破解”“安全强度极高”。这种说法其实把密码学的信任基础说窄了甚至有点误导。严格来说现代密码学并不承诺任何“不可破解”它只承诺一句话在所有现实参与者的计算资源预算内破解成本高到不划算。这句话听起来没有“不可破解”带劲却更接近事实也更接近工程里真正需要理解的东西。把这个逻辑讲透就是这个系列第3论想做的事。这篇内容适合后端开发、安全工程师以及所有对“密码学为什么能信”还有疑问的爱好者——搞清楚底层逻辑比多记几个算法缩写有用得多。1. “数学上不可破解”并不存在先有完美保密再有现实退让1.1 完美保密一次性密码本及其代价在讲计算困难之前先把“安全”这个词在密码学里的定义方式说清楚。信息论的开山鼻祖们很早就给出过一个极其苛刻的安全标准无条件安全也叫完美保密。它要求的是就算攻击者拥有无限计算能力只要没拿到密钥密文对他而言就是纯随机噪声他唯一能做的就是瞎猜。能达到这个标准的方法不是没有一次一密就是经典代表。它的使用规则非常苛刻密钥必须和消息一样长每个密钥只能用一次密钥必须真随机且不能重复使用。只要这四个条件全部满足这种方案在数学上是不可破的。注意这里的“不可破”跟加密算法本身关系不大它靠的是信息量的严格论证密文不透露任何关于明文的统计信息猜明文等于在无限大的空间里捞针。但问题也恰恰在这。一次一密对密钥管理的要求大到工程上几乎没法落地。你想想一条1GB的机密文件就需要一个1GB的真随机密钥双方还得把这个密钥安全地送到对方手里送完之后立刻作废。这本质上只是把“传数据的问题”换成了“传密钥的问题”而且密钥比数据还难传。所以现实世界从来没有大规模用一次一密保护日常通信它更多出现在理论教材和极少数特殊场景里。1.2 计算安全从绝对安全退到“足够安全”既然无条件安全不现实密码学家就只能退一步重新定义安全目标。这条退路就是我们常说的计算安全不再要求“无限计算力下不可破”而是要求“所有现实参与者在可接受的时间与成本内无法以不可忽略的概率攻破方案”。这里有三个关键词计算资源预算、时间成本、成功概率。计算安全并不拒绝攻击者成功它只要求成功概率低到可以忽略。“可忽略”通常被定义为随着安全参数比如密钥长度的增长成功概率衰减得比任何多项式都快——这句话听起来像绕口令落回工程语言就是在128位安全强度下攻击者连“碰巧撞对”都做不到。我平时跟人解释这个概念时喜欢用锁具类比绝对安全相当于一扇理论上没有锁孔的门谁都开不了计算安全则是一把极其结实的锁配了一把复杂的钥匙。理论上有锁孔就有人能撬但撬锁的成本比整栋楼的价值还高理性人不会去撬。密码学要解决的不是让锁不存在而是让撬锁这件事在数学上变成一笔亏本买卖。这个退让不是密码学家的妥协而是工程世界的唯一可行解。搞清楚“为什么必须退这一步”才能真正理解后面所有关于计算困难性的讨论——因为计算安全定义里的“可接受时间”和“不可忽略概率”全部建立在“某些数学问题足够难”这个前提上。这就是计算困难性理论登场的理由。1.3 安全定义里的攻击者模型光有难题还不够光说“计算安全”还不够严谨。一个方案在攻击者只能拿到密文的场景里安全不意味着攻击者能主动提交明文、诱导加密的场景里也安全。所以现代密码学把攻击者模型也写进了安全定义经典的有选择明文攻击、选择密文攻击更强的安全级别还要求密文不可区分、恶意篡改能被发现。这意味着计算困难性只是安全性的一半另一半是方案的结构设计能不能把困难性转化成攻击者绕不过去的关卡。拿公钥加密举例如果方案里不加随机化同一个明文多次加密出来的密文完全一样攻击者一眼就能判断两段密文是否出自同一原文这一下就破坏了语义安全。所以哪怕底层用的是同一个困难假设加密结构怎么设计直接决定安全强度能不能兑现。为什么提这个因为很多人把“计算困难性理论”理解成一堆孤立的复杂度结果但它在密码学里的真正角色是给安全证明提供“最底层的砖”。砖好还不够砌法也必须对这就是安全模型与攻击者模型要解决的问题。把这几层概念分清楚后面所有讨论才有落点。2. 计算困难性到底难在哪里复杂度、平均情形与没人能证明的押注2.1 多项式时间可行计算与不可行计算的工程分界线计算困难性理论的地基是算法复杂度里的“多项式时间”概念。一个算法如果运行时间随输入规模n的增长呈多项式增长比如n、n²甚至n³我们就认为它在工程上是可行的如果时间呈指数增长比如2ⁿ哪怕n只有几十它也会迅速变成宇宙尺度都不可能完成的任务。这个分界线用一张表就能看得很直观。以操作次数为例输入规模 nn³ 计算量2ⁿ 计算量64262144约1.8×10¹⁹128约210万约3.4×10³⁸256约1680万约1.2×10⁷⁷注意“输入规模n”在密码学里的工程化身就是密钥长度。密钥从64位提到128位多项式时间算法的计算量只是多了几十倍穷举攻击的计算量却直接从“一台机器跑一会儿”变成“全人类所有算力加一起跑几十亿年都跑不完”。密码学要找的难题恰恰是那些“正向操作易如反掌、逆向操作指数爆炸”的单行道。这里要区分一下对称加密里加密和解密是正方向穷举密钥是反方向公钥密码里更典型密钥生成是正方向从公钥恢复出私钥是反方向。问题难不难看的不是“有没有办法解”而是“有没有多项式时间的办法解”。2.2 最坏情形困难与平均情形困难密码学只认证“普遍难”复杂度理论里最出名的概念是NP困难但这里有个很多初学者容易踩的坑——NP困难说的是“最坏情形下困难”。最坏情形困难对密码学来说远远不够。你可以想象一把锁99.9%的钥匙孔结构都复杂但存在一种极其特殊的钥匙胚子只要一捅就开。如果攻击者恰好拿到了对应这种特殊胚子的锁再强的防撬设计也形同虚设。密码学要的是平均情形困难不仅大多数实例难而且随机生成的实例都难。因为用户没法保证自己用的恰好不是那个“坏”实例。这个问题在格密码里尤其明显。最坏情形下困难的问题可以通过精巧的归约变成平均情形也困难的问题所以格基密码在这轮后量子研究里被寄予厚望。反过来有些数学问题在最坏情形下很有名但没人知道它的平均情形是否难这类问题就不适合直接当密码学地基——难度再高不稳定也没用。2.3 困难性假设所有人都在赌但没人能证明的命题最难接受但也最真实的一点是现代密码学依赖的那些困难性问题到目前为止都没有任何数学证明说它们“真的难”。更准确地说在现有数学体系下我们甚至不知道这些问题属于哪个复杂度类只知道它们不在已知低复杂度算法的射程之内而且全世界最聪明的一批研究者几十年撞得头破血流也没找到多项式算法。所以密码学里的困难性其实是一种“假设”大整数分解是困难的、离散对数是困难的、特定格问题是困难的。这些命题全部被学术界统称为困难性假设。没有人能证明它们哪怕复杂度领域的大难题被解决了也并不意味着这些具体问题在平均情形下一定难反过来哪怕某个假设被证伪了整个密码学大厦也不会瞬间崩塌只会把依赖它的那一角替换掉。面对这种局面从业者通常的态度是不追问“能不能证明”而是问“已经有多少年没人攻破了、攻破的经济代价多大、如果被攻破影响面多广”。这种务实态度不完美却构成密码学信任链条的实际运转方式。把困难性假设理解成“一场全世界密码学家都在参与的长期压力测试”比“数学上绝对安全”准确得多。3. 现代密码学脚下的几座大山从分解、对数到格问题3.1 大整数分解乘法是单行道除法不是公钥密码最著名的地基之一是大整数分解问题。给定两个大素数p和q把它们乘起来得到一个合数N这个过程小学生都会计算机更是毫秒级完成但只知道N要把p、q重新找出来在没有额外信息的前提下目前全世界都没有多项式时间算法。这种“正向极快、反向极难”的不对称性正是RSA这类经典公钥方案信任的全部来源。这里有个细节经常被忽略大整数分解难题并不是对所有合数都难。如果N的因子没选好比如p和q非常接近或者p-1恰好由很小的素数因子组成那么存在专门的算法可以快速分解。所以工程上选参数时必须保证素数是“安全素数”加上足够大的随机性否则你以为自己在享受难题保护实际坐的是纸糊的保险柜。这类参数选型问题我在评审项目时几乎每次都要专门盯一遍。3.2 离散对数幂运算的单行道第二座山是离散对数问题。取一个大素数p和一个生成元g给定x计算yg的x次方再对p取模很容易但给定y、g、p反求x就难得多。这个难题支撑着DH类密钥交换协议、DSA类签名方案等一大票经典体系。你平时用TLS、SSH时跑的握手动作很多都在背后做离散对数运算。离散对数问题有一座“伴生山”也得注意确保使用的群是素数阶大群。如果群的阶数存在小的素数因子攻击者可以利用小子群攻击把搜索空间压到极小一道本来很牢固的难题就直接报废。这也是为什么标准化的曲线和参数都是精心挑选的敢自己随手定义参数的生产代码往往就是漏洞代码。3.3 换个赛道椭圆曲线离散对数为什么更实用椭圆曲线是个更精巧的构造。它把离散对数搬到椭圆曲线点群的加法结构上同样已知一个点和它的倍数要求出倍数因子难度比有限域离散对数还要高。因此同等安全强度下椭圆曲线密钥可以做得更短。256位椭圆曲线密钥大概能顶得上3072位有限域密钥的安全强度带来的带宽和计算优势非常直观也是现代移动端、物联网设备普遍偏爱椭圆曲线的直接原因。当然“密钥更短”不等于“方案更安全”。实际部署里曲线参数选得对不对、实现是否做了常数时间处理、有没有对输入点做合法性校验每个环节都可能把理论安全吃光。历史上那些扭曲曲线攻击、无效曲线攻击全是实现细节惹的祸。这也是为什么我一直觉得椭圆曲线是那种“上限很高、下限也很低”的技术。3.4 格问题后量子时代接棒的那批山近几年最受关注的困难问题已经从“分解/对数”转向了格上的问题。最短向量问题、最近向量问题、带错误学习问题等等这些问题的共同点是在格这种高维离散几何结构上既没有经典多项式算法目前也没看到能高效攻击它们的量子算法。换句话说它们是当前少数几座被公认还有较长期“保质期”的山。格密码的代价也很直白公钥和密文尺寸普遍比椭圆曲线大一个量级计算量也更高。所以后量子迁移不只是换算法是重新做一遍资源预算和性能规划。我自己做技术选型时会先把“迁移后的带宽和算力涨幅”算清楚再谈方案先进不先进。后量子不是万能解药它只是一批新的、更沉的、目前还没被攻破的山。3.5 几座大山一览困难问题反向操作难度依赖它的经典方案128位安全强度下的规模量子威胁大整数分解分解大合数极难RSA类公钥方案约3072位模数有专用加速算法基线失效有限域离散对数求离散对数极难DH类密钥交换、DSA类签名约3072位素域有专用加速算法基线失效椭圆曲线离散对数曲线上求离散对数极难ECDH类、ECDSA类约256位曲线有专用加速算法基线失效格问题高维格求短向量极难后量子候选方案公钥/密文数千字节起步目前未发现高效量子攻击4. 归约证明密码学信任链条里的关键跳板4.1 反证法思路怎么变成安全证明光有困难问题还不够。密码学家必须回答一个更尖锐的问题你怎么知道破解我的加密方案就一定等同于解决某个困难问题万一这个方案有一个没人发现的漏洞攻击者根本不用碰那个世纪难题呢这个问题靠的是归约证明。构造一个证明说明“如果有人能在多项式时间内以不可忽略概率破解方案B那我就能写一个算法调用这个破解者作为子程序在多项式时间内解决困难问题A”。这个逻辑绕得很妙它不直接证明“方案B难破解”而是证明“如果B被破解那么A就被解决”。但A被全世界公认为难所以B也必须难。这就是数学里最标准的反证法只是在密码学里做成了算法化构造。我在审查一个方案时第一步绝对是先看它有没有归约、归约到哪个问题、归约过程松不松而不是先看它用的哈希函数是哪一个。没有归约的方案不管工程上多漂亮都只是一堆启发式技巧的堆叠。启发式不是不能用但你和用户谈“安全”的时候最好分清楚哪些有证明背书、哪些只是经验上安全。4.2 随机预言机与现实模型信任度从满分打八折归约不是想建就能建。很多方案的安全证明只能在理想化模型里成立最典型的就是随机预言机模型——把哈希函数当成一个完全随机的黑盒。在这个模型里攻击者除了把哈希当成真随机函数没有任何其他可用的结构信息。但现实世界的哈希函数是有确定数学结构的不是真随机。所以我们会看到一个现象大量方案标着“可证明安全”但证明条件写的是“在随机预言机模型下”。这类证明能不能泛化到现实模型往往需要用更强的假设或更复杂的构造。行业里有句话叫“随机预言机模型下的安全证明只是启发式安全感”虽然苛刻但也提醒我们归约证明给出来的安全强度不等于同等数值躺在现实项目里。谁要是拿“可证明安全”当免死金牌我一般会更严格地翻实现细节。4.3 归约的松紧度可证明安全到底值多少分归约还有一个常被忽略的维度紧致性。一个理想的安全归约应该做到“攻击者破解方案的效率几乎等同于解决底层问题的效率”。但现实中很多归约是松的攻击者破解方案可能只需要很小的代价而证明过程中把这笔代价放大了成百上千倍导致所谓的“128位安全强度”实际只提供了远低于128位的保护。松归约不是假归约它在学术上仍有价值但工程落地时必须把折算损失算进去。很多基于双线性配对的方案论文证明推理本身没毛病归约损失却大得惊人这时候我就会把密钥参数往上扩两倍才算安心。这种“理论安全强度”和“工程安全强度”之间的差距恰恰是归约理论里最需要从业者盯住的地方——也是我最想在评审会上跟人强调的点。5. 密钥长度、量子威胁与信任的保质期安全强度怎么算5.1 一把尺子用对称密钥位数统一衡量安全强度不同难题、不同算法之间的安全怎么比行业通行做法是归一到“等价对称密钥位数”也就是安全强度。一把128位的尺子意味着攻击者要付出大约2的128次方次操作才能成功。其他方案不管参数多大只要攻击它所需的最快已知算法复杂度达到2的128次方这个量级就算它有128位安全强度。在128位安全强度下业内通行的参数规模大致是这样方案类别实际参数规模对称分组密码128位密钥大整数分解类约3072位模数有限域离散对数类约3072位素域椭圆曲线离散对数类约256位曲线格基后量子类公钥/密文数千字节起步从这张表能看出参数大小和安全强度之间不是线性关系。用3072位的大整数分解类方案换来的其实只是和128位对称密钥同等级别的保护。所以密钥不是越长越好的拍脑袋问题而是由已知最佳攻击算法复杂度推导出来的预算表。调参数尽量对照标准建议别自己发明一套“我用4096位肯定更安全”的逻辑安全强度够用之后剩下的资源应该花在工程加固上。5.2 量子计算计算困难性假设也有保质期量子计算对密码学的冲击不是“算得快一点”而是直接改变了一些困难问题的复杂度类别。对对称密码通用搜索加速技术把穷举从2的n次方降到2的n/2次方128位变成约64位——还有救密钥长度翻倍就能补回来。对大整数分解和有限域离散对数量子环境里存在指数级加速算法直接让那批经典地基批量塌方加长密钥也没用必须换山。这也是为什么格基密码会成为后量子化的重点候选。不是说格问题就一定安全而是到目前为止还没人找到能像打击分解问题一样打击格问题的量子算法而且格问题的平均情形困难还能从最坏情形困难归约过来理论上更让人安心。不过后量子算法的公钥、密文、签名普遍膨胀得厉害升级时要做全链路性能评估而不是简单换一套接口。5.3 工程实现是算不清的损耗项最后一公里决定信任成色计算困难性理论给出的是数学层面的“上限”工程实现却会在上限下面挖出各种洞。最典型的三个损耗项我得分量级强调一下。第一是随机数生成器质量。随机数出问题密钥空间再大也是白搭。历史上出现过因随机源被污染导致大量“独立密钥”彼此能互相推导的事故。第二是侧信道泄漏。攻击者从时间、功耗、电磁信号里捞私钥数学再难也挡不住别人偷看你草稿纸上写的数字。第三是参数校验缺失。不检查对方发来的公钥点是否在合法曲线上、是否属于合法子群协议的安全强度可以直接降级成玩具。所以我看别人方案时有个固定习惯先问随机数来自哪里再问常数时间实现做了没有最后才问困难问题和参数选型。数学上的山再陡也架不住工程上有人在山脚修了一条直通山顶的缆车。计算困难性理论是“信任”的源头但每一次真正的信任都要在工程的最后一公里重新考一次试。说了这么多我自己现在评估任何一个密码学方案就核对三件事它踩在哪座山上——也就是依赖的困难性假设是什么山的海拔够不够——也就是安全强度和参数规模匹不匹配山脚有没有被人挖地道——也就是随机数、侧信道、参数校验这些工程环节有没有失守。三关都过我才会放下心来。密码学的奇妙之处在于它的每一次信任都是暂时的、有条件的、依赖前提的。带着这种“有条件信任”的心态去做设计和评审未必能让你避开所有坑但至少能让你在坑出现之前提前想清楚自己站在哪座山上。