近年来，量子安全成为信息安全研究的热点和产业界关注的新一轮投入重点。原因也非常显而易见，密码是信息安全的底线，如果底线要被突破了，之前设置的防线再纵深、再综合恐怕也都沦为了摆设。所以量子安全是信息安全发展里程中的大事件和大趋势。中国信息协会量子信息分会顾问专家孙林红老师从事密码理论和攻防研究多年，近来对量子安全密码技术从科学和发展的角度进行了梳理。我们在此特将孙老师的有关观点和报告尽可能通俗化的整理编辑为系列文章供各位读者朋友交流研讨。
安全不可证明，不安全可以证明。算法的安全性能否说清道明？看待密码亦需要多样性的角度，网络空间信息安全愈加趋向于抽象复杂，可否回归到更直观的安全？
1、密码学需要什么样的理想算法？——从陷门性说起
密码是对于输入信息进行保密编码或变换，过程可以用以下的简图表示。其中Alice是加密方，Bob是解密方，Eve是窃听者。
我们将使用密码算法进行的保密编码简化表示为：
Y=H(X) （1）
其中X是输入信息、Y是形成的密文。为了达到保密，密码学家希望变换函数H没有办法逆向求解，也就是无法通过Y来推算出X，读者肯定会想到——使用单向函数就可以啊。但只有单向性对加密算法来说是不够的，即在保证“别人对它没办法”的同时，合法的用户还得要“有办法”解密。这就需要“妥协”，对加密算法来说，变换H需要具有“陷门性”，就是在变换H里隐藏一定的结构，通俗的讲就类似于“后门”，有结构才可以解密。在现代密码里，构造公钥密码、对称密码等价于构造密码学里的单向陷门函数。对公钥密码来说陷门性尤其重要。在此列举几种公钥密码中所构建的陷门性。
RSA：单向函数是大整数分解n=p1p2…，退化为n=p1p2是陷门性要求；DSA：单向函数是模整数的群中求离散对数，a=b的x次方mod n，已知a, b求x; 满足陷门性；ECCDSA：单向函数是椭圆曲线点群中求离散对数，a=bx（椭圆曲线点群中数乘），已知a, b求x;满足陷门性；格密码：单向函数是随机格中求最短向量，或最近向量，或近似最短向量，或近似最近向量，对于NTRU密码体制，为满足陷门性，将随机格退化为理想格（循环格），对于LWE密码体制，对任意向量限定为小范数的向量；多变量公钥密码：单向函数是有限域上非线性多变量方程组求解，已知{f(x1,…,xt）=0}，求x1,…,xt;，为了满足陷门性，将f退化为简单函数（线性与特殊二次的复合）；基于编码的公钥密码：单向函数是大矩阵分解，D=ABC,由D求A,B,C; 为了满足陷门性，B必须是纠错码，在实际中都是特殊的纠错码。
陷门性不像单向性那样广为人知和易于理解，而用陷门性刻画加密算法的本质性特征简捷易懂。那问题来了，算法具有陷门，不就成了不安全的算法了吗？要回答这个问题，需要进一步讨论到可证明安全。
2、从可证明安全到启发式安全“可证明安全”（provable security）的学术概念，是若能将破解某算法的难度归约化为寻找某个公认的数学困难问题的多项式时间复杂度求解算法，就称其为可证明安全的。通俗的解释，就是需要把解域里面的所有可能都穷举了，都符合这一要求，才能认为该算法是可证明安全的。典型的这类问题是NP（Non-deterministic Polynomial）问题里面最难的NP完全问题（也称NPC问题）。我们不做展开，还是先抛结论——NPC问题不多，也很难界定，只能一个一个独立的花很大力气寻找和论证。所幸一个NPC问题经过多项式时间的、不影响其困难性的变换可以形成一个问题族，要获得可证明安全的算法往往可以依此构造和选择。显而易见，对这个问题族来说，如果里面任意一个问题有了多项式的解，即找到一个破解算法，那么所有的问题都可以有多项式的解，也就是都被破解了。但对密码学家来说可称其为不幸的是，可用的密码算法并不等同于困难问题，困难问题到算法实现之间往往存在着各种难以衡量的差异和妥协，而这些差异和妥协可能已经“悄悄地”削弱了“号称”安全可证明算法的安全性。换句话说，真正严格依照NPC 问题是做不出实用的密码算法的。那读者至此可能会问，如果某个算法没有被验证是可证明安全的，那如何衡量其安全性呢？没有别的方法了吗？这就要引入学术上的“计算安全”（computational security）概念，它通过衡量攻破一个密码算法所需的计算开销来刻画其安全性。通俗的说，使用现有人们公认最好的算法破解某个密码算法所需的计算资源远远超出攻击者的既有能力时，可称其是计算安全的。可证明安全性需要从已知NPC问题的转换、规约和严格证明，计算安全性需要定量计算（没有定量计算也就无从衡量比较）。为便于理解，可以通俗的称由计算安全性获得的安全性为“启发式安全”或“经验式安全”。首先，它不是基于某个数学上的可证明难题，也不属于经可证明难题的多项式时间上转换而来的难题族；其次，这个定量计算的途径和方法是研究者各自想定的，是否会有更高效的破解算法，只能说可能未来会有。具备启发式安全特征的密码常见构造思路包括：随机函数发生器、伪随机函数发生器，通过小置换和小矩阵，横向扩散，纵向迭代等。列举代表性算法如下。
杂凑函数：通过小置换和小矩阵，横向扩散，纵向迭代，如SHA2；分组密码：在通过小置换和小矩阵，横向扩散，纵向迭代后，进一步，要求整体是置换,为了能快速解密，还必须要求单轮是简单置换（如三角置换），例如DES、AES；序列密码：设计一个质量不高的源序列，通过小置换和小矩阵，横向扩散，纵向迭代，输出序列；或者通过输出反馈模式，反复迭代；例如Zuc;公钥密码：基于Hash函数的数字签名，例如Winternitz一次签名方案。
3、只分析算法是否足够？前面两部分讨论了算法的问题，本篇最后部分讨论密码安全的一个重要因素——密钥管理问题。密钥管理技术与系统是密码系统的必备组成，现代密码发展和攻防对抗的历史早已告诉我们，密码算法和密钥管理技术是一个整体，二者缺一不可、各负其责、同等重要。安全的密码，必然要求两者在安全性、实用性、可实现性等方面的折衷和统一。回到第一部分列出的简化公式（1），现在我们把密钥因素考虑进去，也就是说，保密编码一般是带有参数的，编码主体H是密码算法，参数就是密钥K。自然的有公式（2）：
Y=H(X, K) （2）
当然（2）同样是便于读者理解的简化公式，刻画的是加密过程必然需要明文、密钥和算法的共同参与。而对密钥的保护、分发等密钥管理相关细节问题在此还未体现，容后续文章详述。在此读者只需理解，在现代密码学的多年实践中，人们普遍认可了密码算法应尽可能公开和标准化，而起支撑密码应用系统作用的密钥管理应尽可能做到保密，以防止在密钥管理这点上被攻破而导致全局安全性的丧失，这就对密钥管理提出了非常严格的要求。显然，密钥管理技术与加密应用的技术体系上彼此尽可能独立是满足这种严格要求的有效措施。
本期结语：构造和评估密码算法的安全性，是否是一个“付出多就收获多”或者说“求仁得仁”的工作呢？读者至此应该能理解，陷门的存在是加密算法的硬性需求，而亦可能是算法不安全的“后门”；算法构造中离不开“妥协”；算法评估显然受制于人的认知。从算法安全性研究的普遍认知上，可证明安全这个被认为是“得其上”的结果是否就真得到数学上、理论上可证明的“加持”了也未必如此，需要具体分析；启发式安全这个“得其中”的结果则完全是基于计算开销和已有“经验”的，往往造成大部分研究者认为它是难题、它是安全的，它就安全，大部分研究者觉得它不安全，它就不安全这样一个颇具“启发性的”结果。那么，有没有“上上之策”呢？容后续系列文章中探讨。下一期内容，我将集中讨论为什么量子计算攻击是现代密码面临的最危险最紧迫威胁。