后量子密码前置基础 05密码难题迭代史经典数论难题与后量子四大数学难题对照前言一、经典公钥密码的数学根基1.1 RSA 与大整数分解1.2 DH 与离散对数1.3 ECC 与椭圆曲线离散对数二、量子算法带来的影响2.1 Shor 算法2.2 Grover 算法2.3 “先收集、后解密”三、第一类路线格密码3.1 格与短向量3.2 LWE 与 Module-LWE3.3 格密码的工程特点四、第二类路线纠错码密码4.1 线性码与噪声4.2 公钥隐藏结构五、第三类路线哈希签名5.1 单向函数与一次性签名5.2 Merkle 树与无状态签名六、第四类路线多变量密码6.1 多变量方程组6.2 为什么必须谨慎看待七、四类路线横向比较八、后量子密码真正改变了什么九、本文小结前言后量子密码不是把 RSA 的密钥长度简单加大也不是换一条更长的椭圆曲线。它真正改变的是安全性所依赖的数学问题。RSA、Diffie-Hellman 和 ECC 分别建立在大整数分解、有限群离散对数和椭圆曲线离散对数等问题之上。Shor 算法在理想的大规模容错量子计算模型下会对这些问题产生根本性威胁。因此后量子密码需要寻找目前没有已知高效量子算法解决的问题。学习时可以先把常见路线归为四类格密码、纠错码密码、哈希签名和多变量密码。“后量子四大数学难题”是便于理解的课程分类不代表所有标准文件都采用完全相同的分类方式。一、经典公钥密码的数学根基1.1 RSA 与大整数分解RSA 使用两个大质数构造N p q NpqNpq公开N NN但希望攻击者难以恢复p pp与q qq。加密可以抽象为c m e ( m o d N ) cm^e\pmod Ncme(modN)私钥指数d dd依赖于p pp、q qq相关的数论信息。攻击者如果能够高效分解N NN就可能恢复构造私钥所需的信息。RSA 的关键不是模幂运算不可逆而是大整数分解在经典计算模型下难以完成。1.2 DH 与离散对数在循环群中公开G , g , y g x G,\quad g,\quad yg^xG,g,ygx如果从g gg和y yy恢复x xx很困难就可以构造密钥交换和签名算法。Diffie-Hellman 中A g a , B g b Ag^a,\qquad Bg^bAga,Bgb双方分别计算K A B a g a b K_AB^ag^{ab}KA​BagabK B A b g a b K_BA^bg^{ab}KB​Abgab攻击者看到A AA和B BB但不能直接得到共享值。1.3 ECC 与椭圆曲线离散对数ECC 把群运算放到椭圆曲线上Q d P QdPQdP其中P PP是公开基点d dd是私钥Q QQ是公钥。已知P PP、Q QQ恢复d dd就是椭圆曲线离散对数问题。ECC 的密钥短、运算效率高但仍然依赖离散对数这一类结构。二、量子算法带来的影响2.1 Shor 算法Shor 算法能够在量子计算模型下高效处理整数分解和离散对数问题。因此RSA、DH、DSA、ECDH 和 ECDSA 都需要进行后量子迁移规划。这不是把密钥从 2048 位加到 4096 位就能解决的问题因为密钥长度变化没有改变底层难题更大的参数 ≠ 更换数学问题 \text{更大的参数}\neq\text{更换数学问题}更大的参数更换数学问题2.2 Grover 算法对于无结构搜索Grover 算法提供平方级加速。经典搜索复杂度为2 n 2^n2n理想量子搜索复杂度约为2 n / 2 2^{n/2}2n/2所以对称密码和哈希函数通常不是像 RSA/ECC 那样直接失效而是通过增加密钥长度、摘要长度或安全参数来抵消部分影响。2.3 “先收集、后解密”攻击者可以今天收集加密流量等未来量子计算能力成熟后再解密。这类风险对于保密周期很长的数据尤其重要政府和军事资料医疗与基因数据工业设计长期身份和密钥材料。因此后量子迁移需要提前规划不能等到量子计算机出现后再开始。三、第一类路线格密码3.1 格与短向量格可以表示为L ( B ) { B z : z ∈ Z n } \mathcal L(B)\{B\mathbf z:\mathbf z\in\mathbb Z^n\}L(B){Bz:z∈Zn}短向量问题要求在格中寻找非零短向量v ∈ L , v ≠ 0 \mathbf v\in\mathcal L,\quad \mathbf v\neq0v∈L,v0并使∥ v ∥ \|\mathbf v\|∥v∥尽可能小。高维格中的基变换、近似短向量和带噪声关系构成了格密码的安全基础。3.2 LWE 与 Module-LWE学习带噪声问题可以写成b A s e ( m o d q ) \mathbf b\mathbf A\mathbf s\mathbf e\pmod qbAse(modq)公开A \mathbf AA、b \mathbf bb攻击者需要推断小秘密s \mathbf ss。模块格方案把其中的矩阵元素换成多项式A ∈ R q k × k \mathbf A\in R_q^{k\times k}A∈Rqk×k​其中R q Z q [ x ] / ( x n 1 ) R_q\mathbb Z_q[x]/(x^n1)Rq​Zq​[x]/(xn1)ML-KEM 和 ML-DSA 都建立在模块格结构上分别用于密钥封装和数字签名。NIST 已通过 FIPS 203、FIPS 204 对这两类方案进行标准化。3.3 格密码的工程特点格密码的优势是功能完整、性能较均衡既能构造 KEM也能构造签名代价是公钥、密文或签名通常比 ECC 更大而且采样、压缩、解密失败和侧信道实现都需要严谨处理。四、第二类路线纠错码密码4.1 线性码与噪声设生成矩阵为G GG消息为m \mathbf mm编码结果为c m G \mathbf c\mathbf mGcmG攻击者看到带错误的向量y c e \mathbf y\mathbf c\mathbf eyce其中e \mathbf ee的重量较小。攻击者需要寻找一个距离y \mathbf yy足够近的合法码字这就是译码问题。4.2 公钥隐藏结构合法接收者掌握私钥中的特殊码结构可以快速纠错公开密钥经过变换后看起来像随机线性码攻击者只能面对一般译码问题。McEliece 类方案的安全研究历史较长解密失败概率也较低但公钥尺寸大是工程应用中最显著的代价。五、第三类路线哈希签名5.1 单向函数与一次性签名最基本的哈希签名使用单向关系y H ( x ) yH(x)yH(x)签名者掌握x xx公开y yy验证者检查H ( x ) ? y H(x)\stackrel?yH(x)?y一次性签名不能无限重复使用因此需要通过树结构组织大量一次性密钥。5.2 Merkle 树与无状态签名如果叶节点是一次性公钥摘要L 1 , L 2 , … , L N L_1,L_2,\ldots,L_NL1​,L2​,…,LN​父节点可以计算为P i H ( L 2 i − 1 ∥ L 2 i ) P_iH(L_{2i-1}\|L_{2i})Pi​H(L2i−1​∥L2i​)不断向上得到根节点R RR。签名携带认证路径验证者从叶节点重新计算到根节点即可。哈希签名的安全假设比较直接但签名通常较大签名系统还必须处理密钥使用状态问题。NIST FIPS 205 标准化了无状态哈希签名方案 SLH-DSA通过无状态设计降低了密钥状态管理风险。六、第四类路线多变量密码6.1 多变量方程组多变量密码可以建立在有限域上的非线性方程组{ f 1 ( x 1 , … , x n ) y 1 f 2 ( x 1 , … , x n ) y 2 ⋮ f m ( x 1 , … , x n ) y m \begin{cases} f_1(x_1,\ldots,x_n)y_1\\ f_2(x_1,\ldots,x_n)y_2\\ \vdots\\ f_m(x_1,\ldots,x_n)y_m \end{cases}⎩⎨⎧​f1​(x1​,…,xn​)y1​f2​(x1​,…,xn​)y2​⋮fm​(x1​,…,xn​)ym​​公开系统看起来是难以求解的多变量问题私钥掌握特殊结构可以快速生成签名或执行逆运算。6.2 为什么必须谨慎看待多变量方案历史上出现过多次结构被识别、参数被攻破的情况。方程数量多、次数高并不自动意味着安全隐藏结构是否能被代数攻击利用才是关键。因此后量子方案的安全性必须依赖长期公开分析而不是“公式看起来足够复杂”。七、四类路线横向比较路线主要难题典型用途优势代价格密码LWE、Module-LWE、短向量问题KEM、签名性能和功能较均衡参数与实现复杂纠错码一般译码、近码字搜索KEM研究历史长、解密可靠公钥较大哈希签名原像、第二原像、碰撞签名假设清晰、结构保守签名较大、性能受限多变量非线性方程组求解签名为主代数结构独特历史攻击较多等轴曲线密码曾经是重要候选路线但代表性方案 SIKE/SIDH 已被公开攻击击破因此不能把“曾经参加标准化竞争”理解为“当前仍然安全”。八、后量子密码真正改变了什么经典公钥密码的路线是分解 / 离散对数 \text{分解}\quad/\quad\text{离散对数}分解/离散对数后量子密码的路线则是格 / 译码 / 哈希 / 多变量 \text{格}\quad/\quad\text{译码}\quad/\quad\text{哈希}\quad/\quad\text{多变量}格/译码/哈希/多变量但算法安全不等于系统安全更完整的表达是算法安全 数学难题 参数选择 实现安全 协议组合 \boxed{ \text{算法安全}\text{数学难题}\text{参数选择}\text{实现安全}\text{协议组合} }算法安全数学难题参数选择实现安全协议组合​九、本文小结RSA、DH 和 ECC 面临的核心问题是量子算法对整数分解和离散对数的结构性加速后量子密码则更换了数学根基。需要记住Shor 算法直接威胁 RSA/ECC 类公钥密码Grover 算法主要带来平方级搜索加速格、码、哈希和多变量是常见后量子路线任何路线都必须同时考虑数学安全、参数、实现和协议。下一步进入具体算法时应该始终问四个问题它依赖什么难题公钥关系和秘密关系是什么正确性依赖什么噪声或编码条件安全证明针对什么攻击模型。