目前量子计算算法的Grover算法和Shor算法已经可以破译当今广泛使用的密码。Shor算法是一种量子计算机求解离散对数问题的算法，它能够攻破RSA、DSA和ECDSA密码，Grover算法没有Shor算法有效，它的作用相当于把密码的秘钥长度减少一半，密码技术人员可以通过加长秘钥长度来抵抗Grpver算法攻击。
    值得注意的是，国外的量子计算机发展迅速，已有像谷歌这样的著名公司将量子计算机投入使用，用于提高信息搜索效率和研究量子人工智能。如今的量子计算机还不足以通过执行Shor算法或Grover算法来大肆攻击现有密码，尽管如此，随着科技发展，总有一天信息安全将受到威胁。因此，在威胁到来之前，科学家应尽快研究出能够有效抵制量子计算机和电子计算机的新型密码体制。除了RSA、DSA和ECDSA密码之外还有许多重要密码是能够抵抗量子计算机攻击的。如基于Hash函数的密码、基于纠错码的密码、基于格的密码、多变量二次方程组密码和秘密钥密码。这些密码被认为是能够抵抗两种计算机攻击的，目前还没有人能够给出一种用Shor算法攻击这些密码体制的有效方法。

[ （美）伯恩斯坦（Bernstein,D. J.），（德）布赫曼 （Buchmann,J. ），（德）达门（Dahmen,E.）， 张焕国，王后珍，杨昌等译，抗量子计算密码[M]，北京：清华大学出版社，2015]

本文将对这几种抗量子计算密码进行介绍，并对其优劣进行分析。
基于Hash函数的密码
Hash算法有MD4，MD5，SHA-1和SHA-2，RIPEMD，以及HAS。HAS函数从未真正被使用过，而MD4的安全性严重缺乏抵抗力。

[  Y. Sasaki, L. Wang, K. Ohta and N. Kunihiro, New message difference for md4, Fast
Software Encryption, ed. A. Biryukov, Vol. 4593 of Lecture Notes in Computer Science
(Springer Berlin, Heidelberg, 2007), pp. 329-348.]

MD5最初为代替MD4而设计，但却不是碰撞稳固的。

[ Y. Sasaki, L. Wang, N. Kunihiro and K. Ohta, New message differences for collision
attacks on md4 and md5, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E91-A
(2008) 55-63.][ W. Xiaoyun, F. Dengguo, L. Xuejia and Y. Hongbo, \Collisions for hash functions md4,
md5, haval-128 and ripemd."]

至于RIPEMD，它是在开放的学术社区被设计出，因而容易被攻击者攻破，

W. Xiaoyun, F. Dengguo, L. Xuejia and Y. Hongbo, \Collisions for hash functions md4,
md5, haval-128 and ripemd."[ X. Wang and H. Yu, How to break md5 and other hash functions, Advances in Cryptology
EUROCRYPT 2005, ed. R. Cramer, Vol. 3494 of Lecture Notes in Computer Science
(Springer Berlin/Heidelberg, 2005), pp. 561-561.]

并且从报告中看出它不常被使用。

[  J. Joshi, Network Security: Know It All (Morgan Kaufmann Publishers (imprint of
Elsevier), Burlington, USA, 2008).]

SHA-1和SHA-2在几乎每个密码系统及安全协议中，都被用在认证和数字签名服务上。

J. Joshi, Network Security: Know It All (Morgan Kaufmann Publishers (imprint of
Elsevier), Burlington, USA, 2008).

尽管SHA-1被查出有一些安全缺陷，

[  X. Wang, Y. Yin and H. Yu, Finding collisions in the full sha-1, Advances in Cryptology
CRYPTO 2005, ed. V. Shoup, Vol. 3621 of Lecture Notes in Computer Science (Springer
Berlin/Heidelberg, 2005), pp. 17-36.]

但这些都被认为是非关键缺陷，并且没有成功延伸到SHA-2中。

J. Joshi, Network Security: Know It All (Morgan Kaufmann Publishers (imprint of
Elsevier), Burlington, USA, 2008).

2004年中国密码专家王小云教授研究小组宣布已破解MD5、SHA-1等加密算法，随着密码学研究的不断深入和计算机技术的快速发展，美国政府计划从2010年起不再使用SHA-1，全面推广使用SHA-256、SHA-384和SHA-512等加密算法。SHA256、SHA-384和SHA-512算法是SHA-1的变体，也被称作SHA-2。
SHA-2算法安全性
基于Hash函数的公钥签名方案需要一个标准的密码学Hash函数，它产生位的输出。对于，一个可选的Hash函数是SHA-256。

（美）伯恩斯坦（Bernstein,D. J.），（德）布赫曼 （Buchmann,J. ），（德）达门（Dahmen,E.）， 张焕国，王后珍，杨昌等译，抗量子计算密码[M]，北京：清华大学出版社，2015

目前已有的对Hash函数攻击的方法包括生日攻击、彩虹表攻击、差分攻击等，下面介绍SHA-256在生日攻击和差分攻击下的安全性。
用于消息唯一性和数据完整性验证的Hash函数，其安全性全依赖于函数本身的属性和对碰撞的抵抗。Hash函数的算法结构特点和Hash值的长度是决定函数抗碰撞性的主要因素，Hash值越长，越能抵抗生日攻击。SHA-256有256比特Hash值，MD5和SHA-1分别有128和160比特的Hash值。因此，SHA-256比MD5和SHA-1能抵抗生日攻击。通过对Chabaud-Joux攻击SHA-256的分析，找到了SHA-256的一个部分碰撞，其复杂度为，但无法找到SHA-256的一个整体碰撞，因此，SHA-256也能抵御现有的差分攻击。
Merkle数字签名方案
基于Hash的数字签名源于一次签名体制，经典的一次签名体制称为Lamport-Diffie一次签名体制，之后又出现更多改进方案，Bos-Chaum方案、Winternitz方案等。然而一次签名方案具有“一次一密”的特点，即每个密钥对只能签署一条消息，否则签名将以很高的概率暴露更多的私钥信息，因此很容易伪造针对新消息的签名。

[ 抗量子计算密码体制研究，张焕国 王后珍，1671-1122（2011）06-0056-04]

  虽然一次签名具有较高的安全性，但缺乏实用性。更先进的基于Hash函数签名体制是Merkle Hash树签名体制，其树的层数与要签名的消息数有对数关系。Merkle数字签名方案的优点是签名和验证签名效率较高；缺点是签名和密钥较长，产生密钥的代价较大。随着研究的发展，出现了一些修改方案，如CMSS方案、GMSS方案、DMSS方案等。Buchmann，Dahmen等提出了XOR树算法，只需要采用抗原像攻击和抗第二原象攻击的Hash函数，便能构造出安全的签名方案。而在以往的Merkle树签名方案中，要求Hash函数必须是抗强碰撞的。这是对原始Merkle签名方案的有益改进。上述这些成果，在理论上己基本成熟，在技术上已基本满足工程应用的要求，一些成果已经应用到了Microsoft OutLook以及移动代理路由协议中。

抗量子计算密码体制研究，张焕国 王后珍，1671-1122（2011）06-0056-04

目前，基于Hash函数的数字签名的理论和技术都还需要深入研究，仍有许多开放性课题。如增加签名的次数、减小签名和密钥的尺寸、优化认证树的遍历方案以及实现相比其他公钥体制所不具备的功能（如基于身份的认证）等均值得进一步研究探讨。

抗量子计算密码体制研究，张焕国 王后珍，1671-1122（2011）06-0056-04

（未完待续）

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)