主题：【原创】闲扯一下RSA受贿事件 -- 晨池

哈哈，是呀，我一开始也有点纳闷，因为从原理和来讲要让一个算法完蛋除非数学上出问题，比如利用两个大质数的非对称加密要完蛋，要么是一开始发表论文的时候作者就留了后手还没有被各大牛人发现（不可能）要么有新的非常快的计算质数的办法，这都不太可能嘛！

但是给微波上还有新闻里一通忽悠，一开始我真的以为是非对称要完蛋，后来看了那两条新闻的具体内容才知道完全不是这么一回事儿嘛

一直以为RSA1024就是牢不可破的，没想到RSA4096都岌岌可危了

除非计算理论出现重大突破，4k RSA key还是很保险的。但EC跟RSA比优势明显，就是key的长度短得多，结果就是SSL certificate的长度也短得多，想像一下像mail.google.com这种每天被访问几十亿次的网站，每次连接都要做SSL handshake，用2048的RSA key跟224的EC key相比，效果差不多，长度缩短了快1.8K，这是个很惊人的加速。

大约是2001年左右（前后两年吧，记不清不想查了），自己做了两款共享软件在网上卖。用的是序列号机制。其中一款序列号用的是一般加密算法，结果发布5天时间后，网上就有了生成序列号的注册机。当时RSA算法刚刚兴起，于是我就想尝试下。于是网上看了基本原理，找了个开源的RSA基本算法库（很基本，就是原理的直接应用，没有RSA公司用于藏猫腻的区区弯弯），再稍加修改，就应用到下一款软件的序列号机制中了。记得当时生成的密匙位数较低（受限于算法库的位数，也不想花时间改进了）。然后，大约是半年左右才出现注册机。

由此，感觉RSA算法还比较行。后来在考虑一个版权保护软件项目时有想正式使用RSA算法，当时RSA公司已经申请了相关版权，于是还和RSA公司做了初步联系。当时咨询授权价格，RSA公司回答说要报项目应用的细节然后才给报价，当时觉得麻烦就没有再联系了。

当然最后从了，卖了个好价钱。

RSA算法出来好几十年了，基本上是认可其安全性的。缺点就是密钥长度太长了。有人提到4k-bit的RSA，可以肯定，这么长的密钥，应用是非常受限的。智能卡的应用，目前也就只定义到不到2Kbit。如果非要求用4kbit RSA级别的安全，肯定会用其他算法了。比如国内pboc 3.0，就定义了256-bit的椭圆曲线。但是，对于密码用户来说，椭圆曲线还是太新了，其算法以及实现的安全性都有待证明。NSA的这个做法，就不得不让人怀疑，他们可能比别人对该椭圆曲线知道更多的东西。随机数是安全的核心功能，各种安全协议都会用到大量的随机数。如果NSA在随机数发生器里有后门的话，很可能其产生的随机数是夹杂里某些关键信息的。这些信息混杂在随机数里。外人看上去就是随机数，NSA却可以从中提取关键信息。这就非常可怕了。

DES让人诟病的主要原因是，其Sbox的代数结构从未公开，是直接给的几张查找表；AES则完全公开。当然，经过这么多年的分析，大家的确没有发现什么漏洞。主要就是对其56-bit的密钥长度有意见，也许NSA认为当时这么长的密钥只有NSA的机器能够暴力破解吧。

PS，另外一个类似的奇葩就是咱们中国的SM4算法，sbox也只给了查找表，没有给出其代数结构和设计原理。当然了，大家都知道sbox的设计依赖非线性的特性。有了AES的先例，拿某个gf(2^8)的逆运算为基础来设计sbox有优良的特性。有人就去猜SM4的sbox必然是某个gf(2^8)加上一些简单运算。经过一些穷举，把SM4 sbox的代数结构就找到。

兄台05年注册一共就发了两个贴，还有一个回给了我，太幸福了！你也是太能潜水啦

RSA密钥太长确实是问题，而且RSA好像解密的效率也很低。我记得是会用RSA来传递一个对称加密的密钥，这个对称加密的密钥尽量一次一密或者尽量提高加密强度。把RSA直接用来解密文件就有点效率太低了

当然要是数字签名，就没办法啦

椭圆曲线这个我还是刚刚在看新闻的时候才知道的，毕竟不是这方面的专业人士，只有一点当时上课的积累，我已经太落后了太落后了

椭圆曲线的点乘操作，比RSA的幂乘一点也不省时间。有限域下的求逆操作也很费时间。好处恐怕就是，对同样安全级别，椭圆曲线的需要传的数据量比RSA小一些。

对称加密的密钥尽管可以一次一密，但是这样的临时密钥产生都是标准里规定好的方式，通过随机数发生器产生的。NSA把后门下在随机数发生器这里不是偶然的。比如，用户用NSA的随机数发生器产生了一个128-bit的临时密钥。对不掌握后门的人来看，有2^128种组合。要想穷举这么大的数是不可能的。但是，NSA知道后门。比如可以通过搜集若干组的临时密钥，把需要穷举的组合数量大大降低。

RSA算法的专利在2000年就失效了。如果需要用，自己写一个也可以。倒是Phil Zimmermann创建的PGP, 当时的确是侵犯了RSA的专利。