01
RSA算法要被破解了？！
这几天一篇文章引起了密码学界的广泛关注，
《Fast Factoring Integers by SVP Algorithms》
作者声称自己破解了RSA算法
其正是Claus Peter Schnorr
Claus Peter Schnorr何许人也？
德国最有名的密码学家之一、
法兰克福歌德大学数学和信息学系教授、
Schnorr 签名算法发明人。
以他的名字命名的“Schnorr数字签名方案”，
今天全世界都在应用。
而其可以构建更高效和隐私性更强的区块链系统，
一直备受区块链开发者们的关注。
一个词总结那就是
正是这样一位大佬
提出自己破解了RSA算法
但很多人还是持质疑态度的
一开始，有人怀疑“标题党”
有人猜测是别人假冒Schnorr发布的“旧文”
（马上Schnorr自己出面认领了 ……）
但Schnorr本人也闹了个“乌龙”
一开始将文章错发成了2019年的版本
经人提醒后更新为3月3日的最新版本
并且摘要包含了
“This destroys the RSA cryptosystem。”
GitHub上也有人开始尝试进行算法实现，
不过，结果都显示不可行。
人们对于这篇“天降文章”还有很多疑惑：
Schnorr为何要发布这样一篇文章？
文章中的问题是不小心的遗漏还是有意为之？
RSA算法真的要被破解了吗？
……
对于这些问题，我们只能让子弹再飞一会
但这篇文章的出现再次提出一个问题：
我们距离RSA算法不再可信任的那天
还有多远？
02
RSA算法是什么？
如果要解释RSA的重要性：
“地球上最重要的算法之一”
“所有密码的根基”
觉得夸张？
那了解了RSA算法后你可能就不这么想了。
1977年，三位数学家
Rivest、Shamir 和 Adleman 设计了一种算法，
可以实现非对称加密。
算法用他们三个人的名字命名，
叫做 RSA 算法。
这种算法非常可靠，
它运用了数学“两个大的质数相乘，
难以在短时间内将其因式分解”
这样一套看似简单
事实上真的非常非常非常困难的数学难题。。。。。。
且密钥越长，它就越难被破解。
近40年过去，
RSA 算法经历了各种攻击的考验。
根据已经披露的文献，
目前被破解的最长RSA密钥是768个二进制位。
也就是说，长度超过768位的密钥，
还无法破解，至少没人公开宣布。
（Schnorr大佬这不就来了嘛）
因此。目前一般认为，
1024位的RSA密钥基本安全，
2048位的密钥极其安全。
而RSA算法作为被研究得最广泛的公钥算法，
被普遍认为是目前最优秀的公钥方案之一。
也是最广泛使用的“非对称加密算法”：
HTTPS协议中就使用了RSA加密算法，
金融、互联网、电子商务……
我们生活中的各个领域都有RSA算法的身影，
毫不夸张地说，
只要有计算机网络的地方，
就有 RSA 算法。
而在1982年，
RSA算法的发明者创立了RSA公司。
2013年左右，RSA在全球拥有8000万客户，
客户基础遍及各行各业，
包括银行、政府机构、电信、宇航业、大学等。
超过7000家企业，逾800万用户
使用RSA SecurID认证产品保护企业资料，
（包括财富杂志排行前百家企业的80%）
而超过500家公司在逾1000种应用软件
安装有RSA Bsafe软件。
现在你是否理解，
为何密码学家Schnorr说自己破解了RSA算法
会引起如此大的轰动了吧？
03
密码攻防会有尽头吗 ？
几千年来，
人们追求的信息安全一直藏在无尽的密码攻防里，
不断升级的密码算法和不断提升的计算算力 。
对于人们来说，
RSA
真的足够安全了么？
2012年国家互联网应急中心发布
“关于RSA1024算法存在被破译风险的通报”
美国国家标准与技术研究所（NIST） 在 07 年 3 月就要求在 2010 年 12 月 31 日之前停止使用 1024 位RSA 算法。
RSA 公司相关负责人也明确表示，虽然没有证据表明 RSA1024 算法已经被破译，但是破译只是时间问题。
RSA1024 算法被破译可能引发加密信息被破译、数字签名被伪造、通信过程被窃听等安全事件。
2013年“棱镜门”事件爆发，
据路透社报道，
美国国安局（NSA）曾与加密技术公司RSA
达成了1000万美元的协议，
要求在移动终端广泛使用的加密技术中放置后门。
RSA SecurID密钥卡
此举将让NSA通过随机数生成算法Bsafe的后门程序
轻易破解各种加密数据。
RSA否认了相关的内容，
声称自己的加密算法只使用了国家认证的协议。
而NSA则拒绝发表评论。
曾有互联网安全专家在接受采访时表示，
“美国国安局在RSA中设置后门意味着，
密码动态密码部分已经被美国政府掌握。”
彼时，RSA在中国有很多客户
包括中国电信、中国移动、中国银行、中国农业银行、
中国工商银行、中国建设银行、华为、海尔等。。。。。
另一个“不安全”因素，在于算力和算法的发展
在1994 年，
美国数学家 Peter Shor 就发现了一种量子算法，
其性能优于经典算法。
在此之前因数分解确实被认为是很难的数学题，
计算机科学家认为经典计算机
几乎不可能分解出大于 2048 位的数字，
（2048位正是目前RSA加密最常用的基础形式）
Shor却证明了，
只要量子计算机有足够的逻辑量子比特来执行操作，
该算法就可以完全破坏基于RSA
和椭圆曲线密码学的加密机制。
还有一种称为Grover的算法，
可以将AES加密从128位彻底削弱至64位，
然后就能通过普通计算机算法来破解了。
越来越多的专家认为，
大规模量子计算机将在未来十年问世。
人们对于破解 2048 位 RSA 加密信息时间的预估
也在不断缩短。
在达沃斯举行的世界经济论坛上，
谷歌首席执行官皮查伊（Sundar Pichai）曾预言：
在5到10年的时间周期，量子计算将会打破我们今天所知道的加密技术。
Shor也曾在接受采访时表示：
我认为用安全的后量子密码系统取代RSA的唯一阻碍是意志和编程时间。我认为我们已经知道要如何做到这一点，只是不清楚是否能及时做到。
不论是通过算力的提升，
还是后门的植入，
围绕保密与破解的斗争，似乎永远不会停止。
04
不怕量子计算的密码？有！
或许是厌恶了你来我往无休止的攻防
也或许是出于防患于未然的谨慎
学界及产业界已经将目光
投向了量子保密通信和抗量子算法。
美国国家标准与技术研究所（NIST）
正在制定一套抗量子算法（QRA）标准，
希望在2024年前完成。
综合考虑量子计算机建造时间、
信息需要保护的时间、
升级基础设施需要的时间等因素，
在重要领域及环节尽早布局量子安全
正逐渐成为各界共识。
One more question：
理论上，
任何以计算复杂度为基础的密码算法及其应用
都是可以被攻破的。
有没有完全不怕算力破解的密码？
有！量子密码！
比如我国正在大力发展的
量子密钥分发（QKD）技术：
用量子力学物理原理实现共享密钥在线生成，
密钥的安全性依赖于基本的物理原理，
而不是具体的数学假设。
因此，结合信息论安全的对称加密算法，
能保证用量子密钥加密的内容不可破译。
而且，《量子安全技术白皮书》中提出：
在当前以及近未来的技术条件下，可以将 QKD 与后量子密码相结合。
后量子密码能应用于 QKD 网络中实现设备间的签名认证……QKD 技术能够为后量子密码系统生成所需要的成对临时密钥或工作密钥，通过QKD不断更换加密密钥，可获得很强的前向安全性。
这种“QKD + PQC”类型的应用方案使密码系统整体能够应 对量子攻击。
从“阴符”、“阴书”到凯撒密码，
从密码机到生活中无处不在的RSA……
人们对于信息安全的追求永无止境，
我们也期待随着科学的发展、技术的普及，
会有真正的“无条件安全” 出现。
