量子计算机8小时暴力破解史上最安全的2048位RSA加密

据arXiv报道，谷歌的Craig Gidney和瑞典斯德哥尔摩KTH皇家理工学院的Martin Ekera一项最新研究成果，演示了量子计算机如何用2000个量子位来计算，他们证明了2048位RSA密码，如何在八个小时被暴力破解。

而这种密码用超级计算机，破解需要80年。

本文将用最直白的语言，描述一下什么是2048RSA加密，看看量子计算机的威力。

传递保密信息，是历史以来非常大的需求，大到国家机密，小到商业秘密，甚至小时候喜欢某个人，匿名求爱信都需要换个字体，让人看不出来是谁的字迹。

密码学有两种经典的加密方式：

对称加密与非对称加密。

什么是对称加密？

我们在谍战片中经常可以看到，当时传递信息用的是摩尔电码，摩尔码就是典型的对称加密。

双方约定一个规则，比如论语这本书就是密码本，摩尔码翻译过来的数字，组成了页码，根据页码查询论语得到关键词，组合起来就是要传递到信息。

这种加密信息传递，就是对称加密，双方都能互译对方密码。

缺点也很明显，如果密码本泄露，比如有人背叛，所有的加密都失效了，加密电报就成了明码，变成广播了。

什么是非对称加密？

非对称加密就是只有一方有密码规则，而另一方的密码只能打开自己权限的信息，而无法知晓密码规则。

那么非对称加密如何实现呢？

有个信息m，A想传给B，B于是生成了两个钥匙p和q，p和q的逻辑关系只有B自己知道。

其中p是由q生成的，p称为公钥，而q就是私钥。

然后B把p公开传递给A，自己留着q。

A收到p之后，就把m利用p的加密规则进行加密，加密后的信息M，公开传递给B。

B利用q的私钥，就能打开信息M，转化成m。

听起来是不是没那么复杂了？

那2048RSA加密是什么回事？

RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。

RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名。（从左到右）

这个算法经历过多轮攻击。

但是，密码分析者既不能证明，也不能否定RSA的安全性。

但这恰恰说明该算法有一定的可信性，目前它已经成为最流行的公开密钥算法。

1999年，一台Cray超级电脑用了5个月时间分解了512位长的密钥。

2009年，768位RSA算法被破解，分解一个768位RSA密钥所需时间是512位的数千倍，而1024位所需时间则是768位的一千多倍，因此在短时间内1024位仍然是安全的。

而目前典型密钥长度是2048位，破解这种密码需要最好的超级计算机用80年时间。

RSA算数就是最大质数分解法，为什么这么难破解呢？

例如，将两个数字相乘很简单:593乘以829等于491,597。但是很难算出491,597是由哪两个质数相乘才能得到。

随着数字的增大，比如2048位数字，计算变得越来越困难。

事实上，计算机科学家认为经典计算机几乎不可能分解出大于2048位的数字，而2048位是RSA加密最常用的基础形式。

量子位提供了难以想象的海量数字存储和运算能力，配合可怕性能的量子算法，使得量子计算具备了实际用途。

目前人类对于量子算法研究里，影响最大的领域就是信息安全，也就是加密和解密，尤其解密。

1994年，数学家Shor提出堪称量子算法经典的Shor算法，可指导量子计算机轻松进行大数因子分解，而大数因子分解正是RSA加密的核心。

想象一下，一个1024位的RSA密钥，在调用Shor算法的量子计算机面前连一秒种都不到就会被攻破。

这种效率让暴力破解看起来闲庭信步。

举个例子：要破解现在常用的一个RSA密码系统，用当前最大、最好超级计算机需要花80年，但用一个有相当储存功能的量子计算机，则只需花上8小时。