RSA是否已经被破解？如果不是，为什么还没有呢？如果发现代码不安全，那么如果发现RSA不安全，那么对我们公司，我们的用户以及Internet上的任何人来说都是一个巨大的问题。
更新：有关D-Wave的最新公告，请点击此处
#1 楼
RSA尚未破解。没有人证明在打破RSA领域中任何地方都可行的实用计算。没有理由改变您的任何做法。首先要了解的是，D-Wave有着悠久的历史，
反复向大众媒体宣称是假的。多年来，量子计算领域的专家一直在批评和揭穿D-Wave的主张。 （例如，尝试单击最后七个单词中的每个单词。）因此，这家公司信誉不高。
最新消息是D-Wave在《自然》杂志上发表了一篇论文，描述了量子计算方面非常有限的进展。它不是成熟的量子计算机。它不能进行通用计算；它只能解决一种算法。特别是，它不能用于分解数字或破坏RSA。它无法处理现实的问题大小；它只有8个量子位，因此只能解决玩具大小的问题（无论如何，用铅笔和纸本可以解决的问题）。没有证据表明它比经典算法更快。它并不比现有的经典计算机快。它确实代表了向前迈出的一步，但这是有限的一步。
过去十年左右的时间里，研究人员一直在深入研究量子计算。已经取得了一些进展，但是进展缓慢，并且要构建一台工作的量子计算机将要求我们克服一些当今没人知道如何应对的基本挑战（例如，退相干）。 D-Wave受到了很多媒体的关注（主要是因为他们对媒体发表不负责任的声明，以夸大其作品的真实性），但其他方面做出了更大的贡献。您使用短语“商业上可行的量子计算机”。这不是一个有用的短语。请理解，D-Wave尚未展示出可行的量子计算机。 D-Wave可能已经将产品卖给了一个或两个客户，但这并不意味着他们已经解决了量子计算问题，也不意味着他们的主张必然具有任何有效性。蛇油推销员也设法将自己的东西卖给了很多客户，但他们的主张总是虚假的。退相干问题，那就不一样了：在这种情况下，我们必须摆脱RSA的束缚。但是，我们还有很长的路要走。目前，我们是否会在一生中看到这样的量子计算机（甚至有可能建造一台这样的量子计算机）是一个悬而未决的问题—量子计算专家喜欢辩论诸如喝酒之类的问题。我怀疑，如果可以使用通用量子计算，那么在威胁RSA的量子计算机问世之前，我们将发出很多警告。
总之，不，您不需要更改策略或删除RSA。我不会继续使用RSA是完全合理的，并且符合行业惯例。
评论
$ \ begingroup $
值得注意的是，您的所有七个屏蔽链接均来自一个人的博客。我并不反对您认为RSA目前（以及可预见的未来）似乎是安全的，因为我认为这是安全的。但是来自同一来源的七个链接并不像说的那么可信。来自四个或五个不同来源的七个链接。
$ \ endgroup $
– corsiKa
2011年8月21日在22:09
$ \ begingroup $
@glowcoder，请继续阅读，您会发现其他量子计算专家也表达了极大的怀疑，包括Umesh Vazirani，Seth Lloyd和David Bacon，他们都是该领域的领导者。 （而且，如果您阅读评论主题并发表文章并知道评论者是谁，您还会看到许多其他人对此表示怀疑。）Scott Aaronson一直是最引人注目的评论家，因为，Scott是该领域最有效率的人。与公众交流与量子计算有关的一切事物（不仅仅是D-Wave）的领域。
$ \ endgroup $
– D.W.
2011年8月22日在3:54
$ \ begingroup $
@DW而且我一点也不否认。我只是说...想像您发表了一篇论文，并且有10篇参考文献（如本篇文章），其中8篇来自同一来源（如本篇文章），您可能不会将其发表在期刊上。我将是第一个承认质量检查网站上的帖子与专业提交的文章遵循不同标准的人，但我确实看到人们可能会质疑从单一来源获得这么多文章。我确实读过一些文章（在发表评论之前），发现他只是在传达其他人的信息...继续...
$ \ endgroup $
– corsiKa
2011年8月22日下午14:55
$ \ begingroup $
...，而且在某些情况下，那些“其他”是D-Wave混为一谈的已出版作品的作者。阅读它们之后，我当然同意您对内容的有效性。但是我仍然认为，如果有更多的来源，它将大大增加文章的结构。 :-)
$ \ endgroup $
– corsiKa
2011年8月22日14:56
$ \ begingroup $
以上D.W.的评论是因为我问量子计算机是否真的需要“无限数量的量子位”。但是，我使用无限而不是无限，这当然是完全不同的。 @ D.W。是的，我了解得足够清楚，为什么D-Wave的解决方案与我们在谈论量子计算时所期望的不同？我只是在您的出色回答中固定了一个词，但我对将“无限”更改为其他内容存有疑问-正当如此它似乎。
$ \ endgroup $
–马腾·博德威斯♦
15年1月24日在20:46
#2 楼
在与D-Wave联系并询问他们的量子计算机对RSA的含义后，他们回答说他们没有破解RSA是出于以下原因...简短的回答： RSA是否被您的量子计算机有效地破解了？
A. No.
Q.我们的客户是否应该担心拥有量子计算机的公司正在拦截我们的加密流量？
A.否。
更长的答案：
量子计算机在密码破解和其他数字理论问题中的实用性远胜于炒作。
实践中的工作具有不太适合于解决理论类型问题的体系结构。他们擅长的领域是机器学习，这是我们的合作伙伴专注于他们的应用程序开发工作的地方。
我怀疑传统的加密技术可以抵御除极其复杂的攻击之外的所有攻击。
评论
$ \ begingroup $
也许他们不能回答，因为国家安全局是客户，并告诉他们否认有关量子计算机可以用来破解加密的任何说法？ （纯粹是我的猜测）
$ \ endgroup $
–克里斯托弗·马汉（Christopher Mahan）
11年8月17日在17:02
$ \ begingroup $
@Christopher Mahan-国家安全局无法保守您所期望的秘密。如果他们真的破解了RSA，那么公众可能（现在）已经发现了，我们已经进入了第三次世界大战。
$ \ endgroup $
– IDWMaster
2011年8月17日17:37
$ \ begingroup $
@IDWMaster-Clifford Cocks在Rivest，Shamir和Adleman论文发表之前的五年中就描述了该算法，但是25年来没人听说过。 Grant Cocks'隶属于GCHQ，而不是NSA，但人们确实知道如何保持沉默。
$ \ endgroup $
– Rob Z
11年8月17日在17:47
$ \ begingroup $
@Rob Z-欧洲各国政府似乎比美国更好。以WikiLeaks为例，但这还不是开始。美国国立卫生研究院还丢失了笔记本电脑上的敏感数据washingtonpost.com/wp-dyn/content/article/2008/03/23/…，因为它没有加密。我们的政府已经失去了在数字时代保守秘密的能力。
$ \ endgroup $
– bbosak
11年8月18日在14:17
$ \ begingroup $
“他们声称比传统算法更快的速度似乎是基于对我的同事van Dam，Mosca和我在“绝热量子计算的力量”上写的一篇论文的误解。因此，即使D-Wave的“量子计算机”被证明是一台真正的量子计算机，即使它可以缩放到数千个量子比特，也可能没有手机强大。加州大学伯克利分校的Umesh Vazirani
$ \ endgroup $
–固定
11-10-15在0:44
#3 楼
正如@Jono在他的回答中指出的那样，D-Wave设备不是通用计算机。摘自2010年1月的IEEE Spectrum，“ D波不能进行量子计算”：他说，D-Wave尚未证明量子计算机必不可少的“签名”，例如纠缠，量子位之间的耦合。评论
$ \ begingroup $
您可能会惊讶于最新技术的发展速度，他们最近在《自然》杂志上发表了有关其技术的论文-nature.com/nature/journal/v473/n7346/full/ nature10012.html同样，Nature在解决相同问题时也有一篇有关它们的新闻文章-nature.com/news/2011/110531/full/474018a.html
$ \ endgroup $
– Rob Z
11年8月17日在17:44
$ \ begingroup $
@Rob，继续阅读。他们只演示了8个量子位，而不是用于通用计算。它们距离能够与经典计算竞争的路途遥遥。量子计算专家仍然有很多[怀疑论]（），他们使用“虚假陈述”，“烟和镜子”，“炒作”之类的词来描述Dwave的过去行为。
$ \ endgroup $
– D.W.
2011年8月19日下午4:43
$ \ begingroup $
（续）斯科特·亚伦森（Scott Aaronson）表示，他们的最新系统“本身并没有做任何有用的事情”，并没有宣称要实现量子加速，而是“重要的一步”。
$ \ endgroup $
– D.W.
2011年8月19日下午4:45
#4 楼
D-Wave进行量子退火。它不是通用的量子计算。实际上，该CEO声称量子计算机的门模型是该领域有史以来最糟糕的事情。我在2012年就从事量子研究，而门模型仍然主要研究经费。
Shor的因式分解算法（在量子计算机上多时间运行）不在D-Wave计算机上运行。它需要一个电路来计算大数的模指数并计算其输出的量子傅立叶变换。
它实际上是一个简单的算法...很难实现去相干和纠错。
#5 楼
现在，绝对可以运行Shor算法的最大量子计算机现在达到14量子位。这是去年某个时候实现的。不过，这台计算机可能实际上并不用于运行Shor的算法。 Shor的算法实际上在2001年被证明可以使用7个量子比特来工作。非对称密码算法。关于D波量子计算机可以做什么的讨论（他们声称128量子位），但似乎不太可能将它们用于运行Shor算法。
评论
$ \ begingroup $
量子计算专家对Dwave声称具有128量子位的说法非常怀疑。他们最新的《自然》论文仅声称8个量子位（甚至不用于通用计算）。简而言之：Dwave的许多主张都是伪造的。
$ \ endgroup $
– D.W.
2011年8月19日下午4:52
#6 楼
为了尝试对此加以了解，D-Wave系统具有（或至少要求拥有）128量子位处理器。要分解1024位RSA密钥，大约需要2000量子位（当然，许多人已经在使用比1024位大得多的密钥）。如果您使用的是椭圆曲线密码学，您会更容易受到伤害。您可以在大约1000个qubit的160位ECC密钥上执行离散对数。
对于D-Wave系统是否真的适合实现Schor算法，尚有争议。 ，当前系统并不真正适合于破坏当前的公共密钥密码系统-尤其是，任何具有足够小的密钥足以使当前D-Wave系统进行攻击的东西，对于使用更传统的计算机来说也是不容易的。
还要注意，扩展量子计算机与扩展传统计算机大不相同。尽管速度不是很快，但我可以设计功能正常的256位或1024位常规计算机，并相当容易地在大型FPGA之类的系统中实现它。建造一个具有更多量子比特的（运行中的）量子计算机是完全不同的故事-生产具有两倍量子比特的量子计算机不仅仅是重复一个量子比特两倍或类似次数的问题。
评论
$ \ begingroup $
除非最近有所变化，否则市场上它们只有128量子位模型。
$ \ endgroup $
–user560
2011年8月17日在23:17
#7 楼
只是另一点。对于长度为n位的复合N，仅因为量子分解的复杂度相对于n是二次方，并不意味着它便宜。在具有大量qbit（> = 2n）的量子计算机上，仍然需要很长时间。这种差异是，如果您可以生成足够快的常规系统来破解1024位RSA（例如TWIRL设计），则只需将n加倍即可使其无法执行。但是，如果您可以构建一个足够大且快速的量子计算机，那么将n翻一番只会使所需的qbit倍增，并将时间因子增加适量，因此可能不足以重新保护系统。好的，我应该说，建造量子门将花费很长时间：至少有1,000,000,000,000个因数可用于分解1024位RSA（并且必须为要分解的每个整数重新设计门布局）。还有一个错误比特定位问题（量子ECC只能做很多事情）以及去相干性问题。随着门数量的增加，误码率将增加，直到ECC无法校正它为止，并且总的门传播时间也将增加，直到最终等于系统的去相干时间为止。很有可能量子计算机无法变得更加复杂（鉴于目前的编码qbit的想法）
#8 楼
TL; DR：从2015年开始，量子计算对RSA来说不是立即的威胁。但这是一个长期威胁（数十年之久）。是否应该担心取决于您是否对保存这么长时间的秘密感兴趣（如果您想悲观地猜测，则要保留2035年）。量子计算机，它将永远不会对RSA密码学产生任何影响（即使您接受D-wave的主张，也并非为此而建）。据该领域的大多数专家称，通用量子计算机距今已有数十年的路程。此外，第一批执行有用的计算的量子计算机经典上将是很小的（50-100个逻辑量子位），并且不会对量子密码术构成直接威胁。要打破甚至很小（512位）的RSA密钥，至少需要提高qubit数量级。但是随后，多项式缩放将允许快速破解越来越大的密钥。根据您的要求，这可能会在现在（2035-2065年）的20至50年内发生，换句话说，这超出了可预测的技术范围：没有人真正知道RSA何时会被量子计算机破坏，但是它真的可能会在二十年内发生，并且共识是肯定会在本世纪发生。不要相信有人告诉他们在当前十年内将拥有RSA突破性的量子计算机；但是也不要相信有人说没有20年的希望（这是乐观的，但并非不可能）。
正如其他人已经回答的那样，这意味着基于RSA的加密技术今天安全，并将在未来十年保持安全。但是，如果要使用它来保证长期安全性（例如，到2035年以后），则量子计算机是您需要考虑的威胁。
来自量子计算研究所的Michele Mosca在本次演讲中（从42:00开始）讨论了这种特定的威胁。
#9 楼
量子计算机尚未处于可以将其部署为蛮力使用的公共RSA模数的阶段。没有证据表明量子计算机使用了超过7个量子位。D-Wave公司提出了几项大胆的主张，但提供的证据很少。
通过technologyreview.com：世界上最大的量子计算使用84个量子位：
量子物理学家说，世界上最大的量子计算使用84个量子位
历史上最广泛的量子计算仅用了270毫秒。失去光彩。这些机器利用量子力学的奇怪规则来进行计算，其计算能力比传统计算机所能执行的任何功能都要强大得多。一种或另一种形式的量子计算机已经进行了十多年的计算。但是，这些设备并没有让普通计算机蒙羞，还远不及小学生的计算能力。
十年前，物理学家使用量子计算机使用七个量子位或量子位分解因数15。结果获得广泛好评。去年，他们通过使用四个qubit分解143来打破这个记录。
但是，这种令人沮丧的状况可能最终会随着今天宣布宣布计算涉及84量子位的计算而最终改变，该计算由郑炳边在加拿大温哥华的量子计算机制造商D-Wave Systems进行，他们的任务是计算各种所谓的“双色拉姆西数”，这是一种奇特的数学实体，与无序系统中的有序出现密切相关。
用来解释拉姆齐数的著名示例是聚会问题，它可以这样表示：您需要邀请多少人参加聚会，以确保其中的一个子集（称为“ m”）彼此认识，另一个子集它们中的“ n”表示彼此不认识，因此被迫打成一片。所需的数字R（m，n）是两个颜色的拉姆齐数。
这些数字很难计算。数学家保罗·鄂尔多斯（Paul Erdos）曾经说过，如果除非我们能告诉他们R（5,5）拉姆西数，否则外来物种威胁毁灭人类，我们最好的选择是让人类的智者来解决这个问题，因为我们
但是如果外星人要求R（6,6），我们最好的选择是立即对外星人进行全面罢工，因为计算将很难考虑。
任务本质上是一个计数问题。可以将参加聚会的来宾视为图上的节点，并将其连接（或不存在）视为边缘。计算Ramsey数实际上是一个计算给定数量的来宾的连接排列的问题。
但是即使对于少数来宾，排列也可能很小。例如，即使在今天，R（5,5）仍然未知，尽管数学家认为它位于43到49之间。 3）和R（m，2），其中m = 4、5、6、7和8。
他们的量子计算机使用超导电路形式的量子位，其中1s和0s对应于沿相反方向传播的电流量子力学定律允许两种状态同时存在。因此，单个电路可以同时表示0和1。
此计算的用处是，每当解决方案出现时，都是将来宾人数增加一倍的结果。因此，在R（3,3）中，具有1、2、3、4和5位来宾的参与者将产生空结果。但是，当问题的动态对象为6位客人时，其动力学会发生巨大变化，这可以通过适当的量子算法直接发现。
Bian and co说R（8,2）的计算使用了84个量子比特，其中28用于计算，其余用于纠错。仅花费了270毫秒。结果是8（传统方法已经知道很多年了）。
这是令人印象深刻的结果。 Bian和同事说：“据我们所知，R（8，2）计算……是科学上有意义的量子算法的最大实验实现。”
对于D-Wave系统，它也是一种证明。该公司制造这种计算机并以1000万美元的价格销售一台128量子位的计算机。各种各样的物理学家都说，机器背后的理论是有缺陷的，而且该公司几乎没有证据表明这种机器有望比传统计算机有所改进。 ，包括Google和洛克希德·马丁公司。退火
评论
研究人员还弄清楚了如何将光子从一个位置传输到另一个位置，但这并不意味着我们已经准备好开始讨论航空旅行的未来。 Quantam计算机还有很长的路要走，它们甚至可以远程用于任何现实情况。来自Sec.SE的一些相关帖子：security.stackexchange.com/questions/4286/…和security.stackexchange.com/questions/6345/…
在这个问题的上下文中，有一个有趣的现象可能是，使用Shor算法分解出的最大质数是-等待-21。而不是2 ^ 21。 21.或3x7。
我想指出这一观点是有价值的，并报告有关D-Wave计算机的近期事件。尤其是那部分内容：“ Matthias Troyer的小组花了几个月的时间仔细研究D-Wave问题，之后他们能够在普通的现成经典计算机上编写优化的模拟退火代码来解决D-Wave问题。 ，解决D-Wave问题的速度比D-Wave机器本身快15倍！“
@MichaelJonathanSimpson当您担心量子计算机时，较大的RSA密钥将不会给您带来很多麻烦。所需的理想qbit数在密钥大小中是线性的。通过纠错，这种增加可能会更大，但仍然不会那么大。一旦QC可以分解2048位密钥，那么可能仅需要几年就可以分解4096位密钥。