datasheet

量子计算核心突破!Shor算法实现或使密码成摆设

2016-03-06来源: 互联网 关键字:量子  计算机  Shor算法  密码

  文章来源:新智元微信公众号

  互联网时代绝大多数的加密,都由RSA算法完成。过去我们认为RSA不可破解,但随着量子计算的发展,RSA的安全性正受到挑战。今天刊发在《科学》杂志的最新论文,量子计算机有史以来第一次以可扩展的方式,用Shor算法完成对数字15的质因数分解。IBM 物理科学高级主管Mark Ritter表示,将Shor算法实现出来这件事,能够与经典计算中的‘Hello,World’ 相提并论。

  互联网时代,密码和网络安全是通信的基础,无论是微信聊天,还是淘宝交易,都需要密码技术保障个人隐私和财产安全。

  而现在的大部分加密,都由RSA算法完成,它基于一个非常简单的数论事实:

  将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。

  例如在一套 RSA 算法下,给定一对解密密钥3和5,由用户自己保存,那么3和5的乘积15,就成为公开的加密密钥。

  当把3和5变成1024位的素数A和B时,令C是A和B的乘积。那么验证A乘以B等于C,是一件计算起来比较简单的事,即用户自己的密码可以获得通过;但是要从C倒推回A和B,却是无比的艰难,其运算时间超出计算机的能力,所以密码很难被破解。

  所以RSA可以在公开加密密钥、加密和解密算法的情况下,通过验证和求解在时间复杂度上的极端不对称性,建立电子加密的基础。

  RSA 是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准。

  今天,只有短的RSA钥匙才可能被强力方式解破。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战。

  Shor 算法

  整数的质因数分解,进入多项式的时间

  早在 1994 年,Peter Shor就发明了一个量子算法(Shor算法),在整数的质因数分解上,能实现

  的时间。这在当年引起了轰动,它展示了一个足够大的量子计算机,在理论上是能够把质因数分解的时间复杂性降到多项式的时间。

  多项式时间在这里意义重大。因为RSA加密之所以有效,最重要的是因为整数的质因数分解,在数字特别大的时候,传统的计算方法根本看不到算完的那一天。现在最快的质因数分解算法,其花费的次指数时间,也达到了

  但如果能把解密复杂度变成多项式的时间,那么基本任何的RSA模型下的大数,都能够很“轻易”的被破解。所以RSA加密在理论上已经不再安全。

  然而,这种算法需要依赖可操作大量量子的计算机。虽然有些人已经尝试了用各种量子系统来实现Shor的算法,但是没有人能在超过几个量子比特的系统上以可扩展(scalable)的方式这么做。所以Shor算法虽然具有理论的意义,但一直没法真正在工程上使用。而世界上也很难找到比RSA更加简单而有效的加密手段,所以RSA加密一直统治着世界,直到现在。

  进入21世纪以来,量子计算机开始加速发展。2001 年,IBM的一个小组展示了Shor算法的实例,使用核磁共振的量子计算机,以及7个量子位元,将15分解成3×5。然而,对IBM的实验的是否是量子计算的真实展示,有一些疑虑出现,因为没有缠结现象被发现。在IBM 的实验后,有其他的团队以光学量子位元实现Shor算法,并强调其缠结现象可被观察到。

  《科学》杂志最新论文

  论文标题:Realization of a scalable Shor algorithm

  作者:Thomas Monz,Daniel Nigg,Esteban A。 Martinez,Matthias F。 Brandl,Philipp Schindler,Richard Rines,Shannon X。 Wang,Isaac L。 Chuang,Rainer Blatt

  今天,在《科学》杂志最新发表的一篇论文中,量子计算机有史以来第一次以可扩展的方式,实现了 Shor 算法。

  MIT和奥地利Innsbruck大学的研究者们报告说,他们设计并搭建了一台在离子陷阱中只有5个原子的量子计算机。这台计算机使用激光脉冲来在每一个原子上实行Shor的算法,分解数字15的质因数。这个系统的设计允许通过增加原子和激光来搭建更大型更快速、能够分解更大数字的质因数的量子计算机。

  “我们展示了,Shor的算法——目前为止已知的最复杂的量子算法——能够以一种可扩展的方式实现:你需要做的一切就是,到实验室去,用上更多的技术,然后你应该就能做出更大的量子计算机了,”Isaac Chuang说道,他是MIT物理学教授、电机工程和计算机科学教授,“量子计算机可能还是要耗费大量金钱才能造出来——暂时来看你还不会去造一台量子计算机然后把它放在你的书桌上——不过现在它更多地成为了一个工程问题,而不是一个基础物理学问题。”

  穿越量子森林

  在经典计算中,用0和1的组合来表示数字,而计算是根据算法的“指导”来进行的,通过操作这些0和1将输入的数字转变为输出的数字。与经典计算不同,量子计算依赖于原子标度的单位,或者叫做“量子比特”,它们可以同时是0和1——这种状态被称作“叠加态”。处于叠加态时,一个量子比特在本质上可以同时进行2个独立的计算流,使得计算效率大大高于经典计算机。

  2001年时,量子计算领域的开拓者之一,Chuang,设计了一台基于一个分子的量子计算机,这个分子可以处于叠加态,通过核磁共振来进行操作,分解数字15的质因数。实验结果发表在了《自然》杂志上,这是第一次以实验的方式实现Shor的算法。不过这个系统是无法扩展的:随着加入的原子数量增多,控制这个系统变得越来越难。

  “一旦你有太多的原子,它就好像成了一片森林——很难逐次控制单个原子,”Chuang说道,“难点在于,如何在一个分离程度足够高的系统里实现这个算法。这样的系统在量子力学的状态里可以维持足够久的时间,让你能够真正有机会完成整个算法。”

  “直白明了的可扩展性”

  Chuang和他的同事们现在终于研究出了一种全新的、可扩展的量子系统,能够高效地分解质因数。一般来说,分解数字15的质因数需要用到12个量子比特,但是他们找到了一种方法使得对量子比特的需求降低到5个,每个量子比特都用一个单一原子来表示。每个原子都能处于叠加态,同时处在两种不同的能量态中。研究者们在其中4个原子上使用激光脉冲来达到“逻辑门”——或者说Shor算法的元素——的效果。计算结果随后由第5个原子来储存、传递、提取、循环利用,由此以并行的方式实行了Shor的算法,用到的量子比特数量大为降低。

  这支团队通过在离子陷阱中控制这些原子来让量子系统保持稳定。量子陷阱中,他们在每个原子上都移除一个电子,让它们带电,随后通过电场来摆放原子的位置。

  “通过这种方式,我们能够精确地知晓某个原子的位置,”Chuang解释道,“然后我们用同样的方式处理几微米之外的另一个原子——这个距离大约是人类头发宽度的1/100。把一些这样的原子放在一起的话,它们仍然有相互作用,因为它们带有电荷。这种相互作用让我们能够进行逻辑门的操作,而逻辑门的操作带来了实现Shor算法的基础。无论我们把系统做得多大,我们都可以对其中任何一个原子进行逻辑门操作。”

  Chuang的团队首先完成了量子计算机的设计,随后他在Innsbruck大学的同事基于他的理论方法搭建了一台实验设备。他们让这个量子系统分解数字15的质因数——这是能有意义地展示Shor算法的最小数字。在对答案没有先验知识的情况下,这个系统返回了正确的质数,置信度超过99%。

  “我们预见到了它未来能拥有直白明了的可扩展性——一旦仪器能够捕获更多的原子、用更多的激光束来控制激光脉冲,”Chuang说道,“我们没有看出有任何物理学的理由阻止它成真。”

  IBM物理科学高级主管Mark Ritter表示,这支团队通过循环利用量子比特的方式将量子系统所需的资源降低了1/3——这是通往扩大量子计算规模的路上很小却很重要的一步。

  “将最新的技术改进1/3是很好的事,”Ritter说道,不过真正将系统扩大“需要的量子比特数量是现在的几个量级,而这些量子比特必须穿梭在更先进的、有数以千计同时发射的激光控制脉冲的陷阱中。”

  如果这支团队能够成功地向系统中加入更多量子元件,Ritter说,他们将会达成一项长期没有人能完成的成就。

  “Shor的算法是第一个不容小觑的量子算法,拥有对经典算法进行指数级加速的潜力,”Ritter说道,“许多研究者都在关注量子计算,因为它或许能为算法带来可观的加速效果。因此,将Shor算法实现出来这件事能够与经典计算中的‘Hello, World’相提并论。”

  这一切最终对于未来的加密机制来说有什么意义呢?

  “好吧,一个影响是,作为一个国家,你可能不希望使用某些加密方法来储存你的机密信息——那些基于分解质因数是一个难以操作的问题而开发的加密方法,”Chuang说道,“因为当这些量子计算机开始进入使用阶段时,你将能够解密所有过去使用这些方法加密的机密文件。”

  这个研究获得了美国高级情报研究计划署(IARPA)和MIT-Havard超低温原子中心(一所国家科学基金会物理前沿中心)的支持。

关键字:量子  计算机  Shor算法  密码

编辑:鲁迪 引用地址:http://www.eeworld.com.cn/afdz/article_201603069367.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:美媒称中国将发射量子科学实验卫星 改变加密学
下一篇:五维数据存储技术:容量可达蓝光3000倍

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利

推荐阅读

专注睡眠场景监测,量子慧智心率监测准确率可达98%

智能硬件利用先进的数字及科技化手段对传统设备进行智能化改造。2013年是智能硬件元年,2014和2015年智能硬件行业销量爆发式增长。根据网络数据显示,近年来,全球智能硬件装机量增长迅速。2014年全球智能硬件装机量为60亿台,到2016年全球智能硬件装机量达到107亿台,较上年同比增长32%,实现了1.5倍以上的增长。随着人们对智能硬件设备包含智能家居、智能医疗、可穿戴设备等产品需求量的不断提升,在全球智能硬件装机量不断增加的促进下,行业的市场规模不断增加。2013年智能硬件发展元年全球行业市场规模为650亿美元,随后几年规模快速增加至2016年,全球智能硬件市场规模超过1500亿美元。近日,猎云网采访到量子慧智创始人曾平桂
发表于 2018-12-20
专注睡眠场景监测,量子慧智心率监测准确率可达98%

三星宣布更新The Frame画框电视:搭载量子点屏幕

根据外媒的消息,在CES之前,三星宣布即将更新其两款时尚的4K电视,型号包括The Frame和Serif。The Frame将会迎来升级,相比前两次迭代产品的画质有所改进。2019年的型号将采用三星的量子点显示技术,以实现更广泛的HDR。除了提供更好的画面外,The Frame现在还将采用新的49英寸尺寸(去年的版本有43英寸,55英寸和65英寸三种尺寸)。  据介绍,三星旨在向那些不喜欢把电视放在起居室中心的人推出了The Frame画壁电视,当电视关闭时,它可以与家装融为一体,看起来就像是一件艺术品。在艺术模式中,The Frame画壁电视会适应房间的光线,使屏幕上的内容看起来更自然。
发表于 2018-12-20
三星宣布更新The Frame画框电视:搭载量子点屏幕

汽车设计中量子计算攻击全新解决方案—TCU-ECU

汽车系统互联是一个令人期待的高速增长的市场,同时也面临一个难题亟待解决。如今数据安全变得日益重要,然而,汽车系统中有许多设备都存在安全隐患。例如,相对于现在大多数汽车电控单元(ECU)的8位、16位和32位处理器,现有的数据安全算法,ECC和RSA内存占用过高,运行速度太慢。此外,随着汽车的平均寿命超过11.6年,未来还必须考虑量子计算攻击的风险,因为量子计算攻击可能会破解ECC和RSA秘钥。 为解决这些问题,SecureRF公司和意法半导体合作开发出一项即使在最小的汽车处理器上仍能极速运行的面向未来的低功耗安全解决方案。最近,SecureRF的WalnutDSA(数字签名算法DSA)和Ironwood KAP(密钥协商
发表于 2018-12-13
汽车设计中量子计算攻击全新解决方案—TCU-ECU

全球首款商用量子计算控制系统发布

瑞士苏黎世仪器 Zurich Instruments 量子科研仪器今年11月,瑞士苏黎世仪器 Zurich Instruments发布了两款新产品,分别是 UHFQA Quantum Analyzer 超高频量子分析仪和 PQSC Programmable Quantum System Controller 可编程量子系统控制器。与已有的 HDAWG Arbitrary Waveform Generators 多通任意波形发生器和 LabOne® 仪器控制软件一起,他们构成了世界首款Quantum Computing Control System (QCCS) 量子计算控制系统。瑞士苏黎世仪器 Zurich Instruments
发表于 2018-12-11
全球首款商用量子计算控制系统发布

国产量子计算机控制系统产品首次发布

12月6日,本源量子2018年度产品发布会在本源量子云展厅圆满召开。本源量子首席科技顾问、中国科学院量子信息重点实验室主任郭光灿院士出席并致辞,安徽省经济和信息化厅党组成员、副厅长王厚亮随后发表致辞。此次产品发布会发布人为本源量子公司董事长、量子测控部总监孔伟成。此次发布的是首款国产量子计算机控制系统——本源量子测控一体机OriginQ Quantum AIO,该产品能够实现对大型量子芯片的精准测控。本源量子2018年度产品发布会现场本源量子首席科技顾问郭光灿院士发表致辞安徽省经济和信息化厅党组成员、副厅长王厚亮发表致辞本源量子公司董事长、量子测控部总监孔伟成发表致辞本源量子测控一体机本源量子团队秉持着“用量子技术追溯科技本源
发表于 2018-12-07
国产量子计算机控制系统产品首次发布

量子罗盘问世,未来导航不靠GPS?

在古代,中国的风水先生们首先发明了罗盘。罗盘后来传入了西方,恩格斯在《机器、自然力和科学的应用》一书中写道:“罗盘(指南针)打开了世界市场并建立了殖民地。”  古代中国人的这项发明被西方人应用于大航海时代,对地理大发现以及资本主义兴起起到了推动作用。  几百年过去了……  2018年11月,英国帝国理工学院研究人员和M Squared公司携手,研制出全球首款用于导航的量子加速度计,这款导航设备被称为“量子罗盘”。它是不依赖全球定位卫星(GPS)的防干扰导航装置。  这个由西方人发明的“量子罗盘”看起来在未来的导航产业中具有巨大的价值。  这年头,只要与“量子”挂钩的技术都显得十分高大上,比如不久前还有人提出了“量子针灸”等概念
发表于 2018-11-28

小广播

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: 视频监控 智能卡 防盗报警 智能管理 处理器 传感器 其他技术 综合资讯 安防论坛

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2018 EEWORLD.com.cn, Inc. All rights reserved
pt type="text/javascript" src="//v3.jiathis.com/code/jia.js?uid=2113614" charset="utf-8">