量子信息学对信息安全的影响浅析

　　量子信息学是研究量子信息处理技术的科学。量子信息处理技术包括量子计算技术、量子密码和量子通信技术等，对信息安全的影响巨大。量子计算机和量子算法令许多曾经的数学难题被轻松破解，这威胁到众多传统密码体系的安全性，也使得防量子算法攻击的密码体系成为理论研究热点。量子密码和量子隐形传态可有效提高量子通信网络和量子签名技术的安全性。人们在研究量子信息学的过程中遇到了诸多挑战，亦取得的可喜进展。应当充分预估量子信息学对信息时代的商业、军事、网络、银行等领域的影响。

　　1 量子信息学和量子信息处理技术

　　1946年第一台数字电子计算机问世，1971年第一块计算机硅芯片诞生。此后芯片集成度遵循摩尔定律成指数增长，到今天，芯片的能耗问题已凸显，而其尺寸不久将达到原子分子量级，根据量子物理理论，这一微观领域内，电子将呈现出波粒二象性，量子干涉效应会导致芯片功能不再稳定[1]。这是研究量子计算机的直接动力。

　　研究量子计算机离不开对量子算法的研究，量子算法的研究成果反过来又激励人们对量子计算机的热情。量子计算机和量子算法是量子信息处理技术的一个重要组成部分。

　　量子力学原理促成量子密码、量子隐形传态和量子通信、量子签名等理论和技术的发展，后者是量子信息处理技术的又一重要组成部分。

　　今天的量子信息处理技术还囊括了量子纠错编码、量子密集编码、量子图像处理等领域，形成了量子信息学。

　　量子信息处理技术的直接目标是设计和实现量子计算机和量子通信网络。

　　量子计算机的优势之一是计算能力强[2]，利用芯片内的量子态的线性叠加性完成指数级的并行计算，可结束摩尔定律的历史。NP(非确定性多项式)计算难题是传统计算机无法应对的，量子计算机可将众多此类问题转化为P(多项式)问题解决，征服了数学难题，也动摇了传统密码系统安全性的理论基础;在对非结构化数据库的进行搜索时，如果运行全新的量子搜索算法，转眼可从海量的数据库中找出精确的信息。其第二个优势是可以建立量子模拟与仿真系统，用于武器、飞机仿真测试和模拟核试验。1982年，n提出一个猜想，认为量子计算机具有模拟任何局域量子系统的能力，1996年希斯·罗埃德证明了这一猜想[3][4]。第三个优势是可用于实现计算机视觉。

　　量子通信网络因高安全性及多端计算的特点成为下一代通信网络的重要发展方向。

　　未来量子信息学可对网络、检索、建模、预报、调度，尤其是密码破译等信息安全领域造成强烈影响。

　　2 量子计算和量子算法

　　2.1 传统加密算法

　　基于计算安全性的现代密码学是各国金融和国防等领域的基石，也是保障网络信息安全的核心。密码算法是保证信息机密性的最有效途径。保密通信、密级存储、身份鉴别及数据完整性等信息安全技术均依赖于现代密码学理论。

　　传统加密算法分为对称加密算法和公钥加密算法。对称加密算法运算快，典型代表有的DES、AES和IDEA等。算法较复杂的RSA(基于大整数分解困难性问题)、NTRU(基于高维格中寻找最短向量困难性问题)、ElGamal(基于离散对数问题)、椭圆曲线(基于椭圆曲线离散对数问题)和MH背包密码系统是公钥密码体系的代表。

　　1977年发明的公开密钥加密算法RSA，是第一个也是对信息安全贡献最大的公钥密码算法[5]。

　　RSA密钥对生成过程：

　　①选取两个保密的不同的大素数p、q，计算乘积

　　n=p×q

　　和欧拉乘积

　　φ(n)= (p-1)×(q-1)

　　②随机选取一个与欧拉乘积φ(n)互质的较大的数e，(e，n)就是加密公钥，通过e和φ(n)得到

　　d≡e-1modφ(n)

　　(d，n)即为解密私钥。

　　加密过程：

　　①发送者将明文M分段，使其每个分段mi的长度小于log2n。

　　②对每个明文的分段mi做加密运算，并合并得到密文

　　C=c1c2…ct

　　其中

　　ci≡mie mod n (1?燮I?燮t)

　　密文C发送给接收者。

　　解密过程：

　　接收者收到密文C，将其分段得

　　C=c1c2…ct

　　利用仅接收者拥有的私钥来计算明文

　　M=m1m2…mt

　　其中

　　mi≡cid mod n (1?燮I?燮t)

　　大数因子分解相对传统电子计算机而言是难解的，这一计算复杂性理论是现代密码学的基础[6]136。RSA算法的运算复杂度为O(n3)。有人计算过，如果对一个60位的正整数进行因子分解，最快的超级电子计算机也要耗时若干亿年[2]。

　　1996年ein，，man提出基于多项式环的“NTRU”公钥加密体制，运算复杂度为O(n2)，比RSA高效且防攻击性好，有人预测，只有拥有强大并行计算能力的量子计算机可能攻破它[6]113-116。

　　2.2 量子算法攻击技术

　　相对于量子计算机的计算能力，某些曾经的难题不再难。量子计算机具有强大攻击潜能。量子攻击分为两类[7]：量子物理攻击和量子算法攻击。其中物理攻击技术尚不成熟;算法攻击方面成果颇丰，最著名的有Shor算法攻击和Grover算法攻击。

　　2.2.1 Shor算法攻击

　　主要针对公钥密码体制。

　　1994年，美国学者Peter Shor提出了一种量子算法，以“量子计算可破解离散对数、大整数因子分解难题” 为理论基础，是一个超越传统的高效算法[8，9]。该算法将大数因子分解问题变换为求一个指数函数周期的问题，经过快速的量子傅里叶变换计算，求周期仅需多项式步骤即可得解。

　　Shor算法(秀尔算法，大整数质因子分解的量子多项式算法)：

　　已知：N是两个大素数n1和n2的乘积。求：n1和n2。

　　①随机选取一个比N小的正整数a，计算a和N的最大公因子gcd(a，N)。判断：若

　　gcd(a，N)>1

　　则已成功找到一个因子gcd(a，N)，输出

　　n1=gcd(a，N)

　　进入第4步;否则进入第2步。

　　②定义f(x)=ax mod N，f(x)是一个周期函数。设周期为r，即

　　ax mod N=ax+r mod N

　　故有

　　ar=1 mod N

　　利用量子算法求r。判断和循环：若r是奇数，重新取a，重新求r，直到r为偶数为止。

　　③因为

　　(ar/2)2 -1=0 mod N

　　所以

　　(ar/2+1) (ar/2-1)=0 mod N

　　求出ar/2和N的最大公因子gcd(ar/2，N)，输出

　　n1=gcd(ar/2，N)

　　④输出

　　n2=N/n1

　　以上步骤中第二步必须靠量子计算机来完成，其他步骤可在传统计算机上进行[10]。对一个60位的数字进行因子分解，采用Shor算法只需一瞬间[2]。这就是量子计算对今天各国采用的主要密码体制和信息安全理论构成巨大威胁的直接原因。应当注意，此算法是个随机算法，即不保证每次都成功。

　　2.2.2 Grover算法攻击

　　主要针对对称加密算法和大容量数据库。

　　1995年，美国人Grover证明出：搜索一个未经整理、容量为N的数据库的时间复杂度，用量子图灵机为O(N1/2)，比用传统算法的时间复杂度O(N)要好，据此，Grover设计出了一个基于量子态并行计算特性的量子快速搜索算法[8，11，12，13]。Grover算法极大降低了计算的复杂度，使传统计算机要用百年时间才能完成的破译DES密码的任务在几分钟内即完成，还可用来探索、搜索最值和均值，这些理论已通过光学系统、核磁共振(NMR)等实验方案验证[14]。与Shor算法一样，Grover算法也是一种随机算法。

　　受到以上算法的启迪，许多经优化而提高了成功率的量子攻击算法被先后设计出来。

　　2.3 抗量子算法攻击的密码体制

　　寻找防范量子算法攻击的抗量子密码体制成了信息安全领域紧迫的课题。可以遵循以下几条思路：

　　一是采用与数学难题无关的密码体制。量子算法攻击一些数学难题的计算能力强大，然而量子密码、DNA密码等新型密码不以数学难题为基础，量子算法攻击对此将无能为力[15]。

　　二是采用能防范量子计算攻击的数学难题有关的密码体制[10]。量子计算不是万能的，目前尚未证明量子计算机可以破解所有已知的数学难题，因此不排除用“与离散对数问题、大数分解问题无关的算法”来构造防范量子攻击密码体制的可行性，这方面的成果有：基于纠错编码问题由Robert McEliece发明的McEliece密码体制(M公钥)和由Niederreiter创造的代数码公钥密码体制(N公钥)[16，17]。

　　3 量子密码、量子隐形传态与量子通信、量子签名

　　量子密码、量子隐形传态与量子通信、量子签名是量子信息学的又一重要领域。

　　科学家推测将量子态作为信息加解密的密钥具有的无法窃听和破译的独特性，利用这种密码实现保密通信网络，必会提高通信技术的安全程度，可以规避当今众多信息拦截者的攻击[7]。

　　未来的量子通信网络可基于卫星或基于光纤组网，具有无条件安全性、多端计算的优点，利用“点到点”量子密钥分发装置可组建一个跨全球的量子保密通信网络。

　　量子保密通信网络的未来趋向[18]：一是出现技术井喷并实现各种技术融合，量子交换机、量子路由器、不同结构的量子密钥分配(QKD)网络逐渐出现;二是向层次化、标准化方向发展，实现互联互通;三是采用中继技术突破传输距离的局限，扩展延伸量子保密通信网络，形成广域网络;四是密钥长度数量逐渐增长，传输速率亦逐渐提高。

　　1984年，第一个可实现安全秘密通信的量子密钥协议BB84协议被提出来，解决了密钥分配这一带根本性的问题，5年以后IBM根据这个协议成功进行了第一次传输量子密钥的演示性实验。目前还有BBM92、B92和EPR等量子密钥分发协议[19][20]，其安全性都基于Werner Heisenberg线性叠加(测不准)原理和单量子无法克隆的理论。

　　量子密码还可用在量子数字签名、投票、认证等方面，国内外一些关于量子签名的仲裁协议方案已经相继被提出来[7]。

　　量子密码学的另一实现手段是利用量子隐形传态原理进行远距离的中继转发。

　　4 量子信息学的挑战和进展

　　4.1 挑战

　　首先，需要解决量子脱散现象(消相干)的问题[21]，生成稳定的量子位是设计量子计算机的关键问题。从简单量子逻辑门到形成量子逻辑门网络仍有很长一段路要走[22]。其次，原子难以保持稳定，观察很困难。观察原子的同时破坏了观察前的不确定状态，致使实验价值大打折扣。量子纠错方案仍有待分析和改进。再次，编制算法进行一定数目的量子运算、量子传输技术、单光子源技术同样困难。此外，研发量子计算相关的各种器件，统一各类接口的标准，制定量子保密通信网络的各类协议规范，更需要长久的研究实践来解决。

　　以上挑战表明，量子信息学短期内还不会对现有信息安全体系造成实质性改变。

　　4.2 进展

　　4.2.1 理论方面的进展

　　Shor提出的量子纠错思想等量子纠错理论在解决脱散问题方面取得了根本性的突破。受到Shor算法启发，科学家们发明了更多量子并行快速算法，量子复杂性理论随之产生[21]。NMR等技术可以扩展量子位(昆比特qubit)信息，获得间接测量的效果，并可在相位一致中分析错误并修正，使量子计算系统稳定可靠。通过量子点操纵、冷阱束缚离子(ion trap)、NMR、腔量子电动力学(QED)和高温超导约瑟夫森结等[23]技术方案，可成功推进量子计算实验计划。2002年，美国政府制定的量子信息科技发展规划提出了光量子计算等八个技术方向[24]。

　　4.2.2 实践方面的进展

　　2000年，IBM宣布7量子位量子计算机研制成功，用一步计算完成了传统计算机需多次循环才能解决的数学题。2010年英、日、荷、以色列等合作制成了一款芯片，可进行量子计算。2011年加拿大发布了一款能处理经过优化的特定任务的量子计算机。2012年维也纳造出隐秘量子计算机。

　　中国1995年通过实验展演了BB84协议，2004年建成世界首个实用光纤量子密码网络[25]，2007年造出量子路由器[26]、实现量子搜索算法和Shor量子分解算法[10]，2009年建成世界首个光量子电话网，2010年实现16千米距离自由空间量子隐形传态[27]，2011年提高至约100千米，向全球量子保密通信网络的建立迈出重要一步[28]。

　　5 结束语

　　量子信息学是一柄双刃剑，给信息安全相关领域带来了前所未有的影响。

　　量子信息处理技术可解决许多数学难题，同时也使得传统信息安全理论危机重重。量子计算机、量子通信网络等量子信息处理技术如果使用得当，则传统互联网、电话网、国防通信网等设施都将迎来一次飞跃，人类将向未来信息社会前进一大步;而一旦被用于恶意攻击和破解安全密码，则银行、网络、军事、商业等信息安全有关的领域都将面临巨大威胁，信息安全领域的争斗或许会从目前的电子对抗进入到“量子对抗”的新阶段。 .

　　作者：周旭峰 来源：价值工程 2015年33期