（计算机软件与理论专业论文）量子密码中若干重要问题的研究.pdf

量子密码中若干重要问题的研究 专业：计算机软件与理论 博士生：李琴 指导老师：龙冬阳教授 摘要 在瞬息万变的信息社会里，实现通信安全显得更为迫切和重要。目前，经 典密码被认为是一种有效的解决办法并且得到广泛应用。然而，大多数经典密 码算法的安全性依赖于计算复杂性理论。随着计算机和互联网技术的迅速发展， 原本安全的密码算法也可能变得不安全。尤其是量子算法和量子技术的出现对 经典密码体制构成了严重的威胁。因此需要寻求新的能够抵挡量子攻击的密码 体制。 量子密码是利用量子力学理论实现安全通信。这些理论主要包括量子叠 加原理，h e i s e n b e r g 澳l j 不准原理，量子不可克隆定理，量子不可区分性，信息获 取一干扰原理以及量子纠缠特性等。利用这些量子特性，空间上分离的两个通信 方可以产生和协商出完全随机的密钥。因而量子密码与一次一密的结合，能够 保证通信的绝对安全。量子密码包括诸多内容，本文主要对量子签名( q s ) ，量 子秘密共享( q s s ) 以及量子比特承诺( q b c ) 进行研究。 q s ，类似于手写签名和经典数字签名，同样可以用来认证签名方的身份， 保证数据的完整性和提供不可否认服务，而且它的安全性基于量子力学原理而 不是一些密码假设。关于q s 的研究，已取得以下结果： 观测到文献 1 ，2 】的仲裁q s 方案中，仲裁方与另外两个参与方( 即签名方 和验证方) 之间的量子态关联并没有使用，于是基于b e l l 态提出一个仲 裁q s 方案，这个方案类似于原来- 于= g r e e n b e r g e r - h o m e - z e i l i n g e r ( g h z ) 态 的q s 方案 1 ，2 】，能够保留原有方案的优点，并能提高传输效率和降低执 行复杂度。 量子密码中若干重要问题的研究 通过给出一些相关方案来说明量子纠缠有利于改善仲裁q s 方案的安全。 在没有利用量子纠缠属性的仲裁q s 方案中可能出现一种伪造，而利用量 子纠缠属性的仲裁q s 方案中，这种伪造就可以避免。 结合量子密码和经典密码的技术提出一个高效的q s 方案。通过将密钥与 随机数一起使用的方法，签名方和接收方均能与仲裁方共享和使用一个长 期密钥。而现有的q s 方案中，签名方和接收方与仲裁方共享的密钥仅能被 使用一次。因而每次签名之前，签名方和接收方都必须与仲裁方执行量子 密钥分配协议以获得新的密钥。研究结果表明，所提出的方案效率高，且 在给出的模型中具有可证明安全性。 即使存在窃听者，q s s 也可用来保护经典信息和量子信息。通常，在一般 的( 七，n ) q s s 协议中，某个实体与n 个参与方共享一个经典秘密或量子秘密，并使 得至少需要尼个参与方合作才能重构出这个秘密，而少于k 个参与方不能获得秘 密的任何信息。本论文主要考虑当并非所有的参与方都拥有量子信息处理能力 时设计q s s 以及在可信第三方不存在时实现q s s 的问题： 基于g h z 型最大纠缠态提出两个非完全量子的秘密共享协议。在这两个 协议中，并不需要所有的参与方都具有量子信息处理能力，量子的a l i c e 与 经典的b o b 和c h a r l i e 共享秘密，并使得当且仅当b o b 和c h a r l i e 相互合作才 能重构a l i c e 的秘密，而其中一个则无法完成重构。而且，这两个协议同样 可以检测窃听行为。 给出无可信方存在时共享量子秘密的基本构造方法。通常是可信方将某个 秘密分成多份并分配给各个参与方。而当这样的可信方不存在时，则由各 个参与方自己选择秘密态，并且这些秘密态对最终共享的量子态所做的贡 献是均等的。此外，主要基于c l e v e 等的传统量子( 后，礼) 门限方案f 3 1 设计具 体的无需可信方的q s s 方案，以此来说明这种构造方法的可行性。 比特承诺允许承诺方( 通常称为a l i c e ) 承诺一个比特，之后再向被承诺 方( 通常称为b o b ) 公开所承诺的比特值。如果a l i c e 一旦做出承诺就不能更改其 承诺值，则称协议满足绑定性。若b o b 在a l i c e 公开承诺值之前无法得知她所承 诺的比特值，则称协议满足隐藏性。一个安全的比特承诺协议必须同时满足绑 定性和隐藏性。尽管m a y e r s - l o - c h a un o - g o 定理已经证明无条件安全的q b c 不 存在f 4 ，5 】，仍从两个不同的角度对q b c 进行研究： 改进k e n t 基于狭义相对论提出的比特承诺协议r b c l 6 】。通过引入随机选 择的方法，使得改进的协议只需固定容量的信道。尽管k e n t 之前提出的改 进协议r b c 2 【7 】同样能够解决r b c i 中存在的问题，使得信道的容量不再 随着承诺时间呈指数增长，但是其解决方法有点复杂。本文提出的改进协 议( 称之为冗b c 3 ) 为解决r b c l 中的问题提供一种更简单的方式。 观测至! j j c h o i 等在文献f 8 ，9 1 中揭示了一个有关m a y e r s - l o - c h a un o - g o 定理 成立的假设，即在a l i c e 公开其承诺值之前，整个系统的状态对两个参与 方来说是不变的。尽管c h o i 等通过消除该假设提出安全的非静态q b c 协 议f 8 ，9 1 ，可是由于引入可信第三方( t t p ) ，使得提出的协议不同于一般 的q b c 协议。针对静态q b c 和非静态q b c ，就它们的不可能性给出更一 般的见解。 关键词：量子密码，量子签名，量子秘密共享，量子比特承诺，窃听检测， 无条件安全 r e s e a r c ho ns e v e r a li m p o r t a n tt o p i c so f q u a n t u mc r y p t o g r a p h y m a j o r ： n a m e ： s u p e r v i s o r ： c o m p u t e rs o f t w a r ea n dt h e o r y q i nl i p r o f e s s o rd o n g - y a n gl o n g a b s t r a c t s e c u r ec o m m u n i c a t i o nb e c o m e sm o r eu r g e n ta n di m p o r t a n ti nt h ee v e r - c h a n g i n g i n f o r m a t i o ns o c i e t y c l a s s i c a lc r y p t o g r a p h yi ss u p p o s e dt op r o v i d eas o l u t i o n a n dh a sb e e nw i d e l yu s e dt or e a c ht h eo b j e c t i v e h o w e v e r ，t h es e c u r i t yo fm o s t c l a s s i c a lc r y p t o g r a p h i ca l g o r i t h m sr e l i e so i lc o m p u t a t i o n a lc o m p l e x i t yt h e o r y w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e r sa n di n t e r n e tt e c h n o l o g i e s ，s o m ec r y p - t o g r a p h i ca l g o r i t h m sw h i c hw e r ec o n s i d e r e ds e c u r eo r i g i n a l l ym a yb ei n s e c u r e e s p e c i a l l y , t h ee m e r g e n c eo fq u a n t u ma l g o r i t h m sa n dq u a n t u mt e c h n i q u e ss e r i - o u s l yt h r e a t e n e dc l a s s i c a lc r y p t o g r a p h y t h u si ti sn a t u r a l t os e e ka na l t e r n a t i v e w h i c hc a nw i t h s t a n dq u a n t u ma t t a c k s q u a n t u mc r y p t o g r a p h yc a np r o v i d eu n c o n d i t i o n a ls e c u r i t yf o rc o m m u n i c a - t i o nu s i n gt h et h e o r i e so fq u a n t u mm e c h a n i c ss u c ha st h es u p e r p o s i t i o np r i n c i p l e ， h e i s e n b e r gu n c e r t a i n t yp r i n c i p l e ，q u a n t u mn o - c l o n i n gt h e o r e m ，q u a n t u md i s t i n - g u i s h a b i l i t y , i n f o r m a t i o ng a i n - d i s t u r b a n c ep r i n c i p l e ，a n dq u a n t u me n t a n g l e m e n t t h r o u g ht h e u s eo fs u c hq u a n t u mf e a t u r e s ，t o t a l l yr a n d o mk e yc a nb eg e n e r a t e d a n dn e g o t i a t e db e t w e e nt w os p a t i a l l ys e p a r a t e dp a r t i e s h e n c et h ec o m b i n a t i o n o fq u a n t u mc r y p t o g r a p h ya n do n e - t i m ep a dc a ng u a r a n t e et h ea b s o l u t es e c u - r i t yo fc o m m u n i c a t i o n q u a n t u mc r y p t o g r a p h ye n c o m p a s s e sm a n yi s s u e s i n t h i st h e s i s ，w em a l i i 衄i n v e s t i g a t et h r e ei m p o r t a n tt o p i c so fq u a n t u mc r y p t o g r a - p h y ：q u a n t u ms i g n a t u r e ( q s ) ，q u a n t u ms e c r e ts h a r i n g ( q s s ) ，a n dq u a n t u mb i t c o m m i t m e n t ( q b c ) 、r l 量子密码中若干重要问题的研究 q s ，a sa na n a l o g yt om a n u s c r i p ts i g n a t u r ea n dc l a s s i c a ld i g i t a ls i g n a t u r e ， c a nb eu s e dt oa u t h e n t i c a t et h ei d e n t i t yo ft h eo r i g i n a t o r ，e n s u r ed a t ai n t e g r i t y a n dp r o v i d en o n r e p u d i a t i o ns e r v i c e f u r t h e r m o r e ，t h es e c u r i t yo fq si sb a s e d o nq u a n t u m m e c h a n i c a lp r i n c i p l e sb u tn o to ns o m ec r y p t o g r a p h i ca s s u m p t i o n s b yi n v e s t i g a t i n gi t ，w eo b t a i nt h ef o l l o w i n gr e s u l t s w eo b s e r v et h a tt h eq u a n t u mc o r r e l a t i o n sb e t w e e nt h ea r b i t r a t o ra n dt h e o t h e rt w op a r t i e sw e r en o tb e e nu s e di nt h ea r b i t r a t e dq ss c h e m eo fr e f s 1 ，2 】，a n dt h u sp r o p o s ea na r b i t r a t e dq ss c h e m eu s i n gt w o - p a r t i c l ee n t a n - g l e db e l ls t a t e ss i m i l a rt ot h eo r i g i n a ls c h e m e 【1 ，2 】u s i n gt h r e e - p a r t i c l ee l l - t a n g l e dg r e e n b e r g e r h o m e z e i l i n g e r ( g h z ) s t a t e s t h ep r o p o s e ds c h e m e c a np r e s e r v et h em e r i t si nt h eo r i g i n a ls c h e m ew h i l ep r o v i d i n ga h i g h e r e f f i c i e n c yi nt r a n s m i s s i o na n dr e d u c i n gt h ec o m p l e x i t yo fi m p l e m e n t a t i o n w es h o wt h a tq u a n t u me n t a n g l e m e n ti sh e l p f u li ni m p r o v i n gt h es e c u r i t yo f a r b i t r a t e dq ss c h e m e s t h ef a c ti si l l u s t r a t e db ys o m er e l e v a n ts c h e m e s a p o t e n t i a lf o r g e r ym i g h to c c u ri na r b i t r a t e dq ss c h e m e sw i t h o u tu s i n gt h e p r o p e r t i e so fq u a n t u me n t a n g l e m e n t ，w h i l ei tc a nb ea v o i d e di na r b i t r a t e d q ss c h e m e st h a te n t a n g l e m e n tf e a t u r e sa r ee m p l o y e d a ne f f i c i e n tq ss c h e m ei sp u tf o r w a r db yc o m b i n i n gq u a n t u m c r y p t o g r a p h i c a n dc l a s s i c a lc r y p t o g r a p h i ct e c h n i q u e s i nt h ep r e s e n t e ds c h e m e ，t h es i g - n a t o r ya n dt h er e c e i v e rc o u l ds h a r ea n du s eal o n g - t e r ms e c r e tk e yw i t h t h ea r b i t r a t o rb yu t i l i z i n gt h ek e yt o g e t h e rw i t har a n d o mn u m b e r w h i l e i np r e v i o u sq ss c h e m e s ，t h ek e ys h a r e db e t w e e nt h es i g n a t o r ya n dt h e a r b i t r a t o ro rb e t w e e nt h er e c e i v e ra n dt h ea r b i t r a t o rc o u l db eu s e do n l y o n c e ，a n dt h u se a c ht i m ew h e nas i g n a t o r yn e e d st os i g n ，t h es i g n a t o r ya n d t h er e c e i v e rh a v et oo b t a i nan e w k e ys h a r e dw i t ht h ea r b i t r a t o rt h r o u g ha q u a n t u mk e yd i s t r i b u t i o np r o t o c 0 1 r e s u l t ss h o wt h a tt h ep r o p o s e ds c h e m e i se f f i c i e n ta n dp r o v a b l ys e c u r ei nt h eg i v e nm o d e l q s so f f e r sag o o dw a yt op r o t e c tb o t hc l a s s i c a li n f o r m a t i o na n dq u a n t u m i n f o r m a t i o ne v e ni nt h ep r e s e n c eo fe a v e s d r o p p i n g i na g e n e r a l ( k ，n ) q s sp r o - t o c 0 1 ap a r t ys h a r e sac l a s s i c a lo rq u a n t u ms e c r e tw i t h 佗p a r t i c i p a n t ss u c ht h a t 七o ft h e ma r es u 伍c i e n tt or e c o n s t r u c tt h es e c r e tw h i l e 七一1o rf e w e ro ft h e m c a no b t a i nn o t h i n ga b o u tt h es e c r e t i nt h i st h e s i s ，w em a i n l yc o n s i d e rt h es e c r e t s h a r i n gw h e nn o ta l lt h ep a r t i c i p a n t so w nq u a n t u mc a p a b i l i t i e sa n dh o wt os h a r e as e c r e ti nt h ea b s e n c eo fat r u s t e dp a r t y w ep r o p o s et w os e m i q s sp r o t o c o l su s i n gm a x i m a l l ye n t a n g l e dg h z - t y p e s t a t e si nw h i c hq u a n t u ma l i c es h a r e sas e c r e tw i t ht w oc l a s s i c a lp a r t i e s ， b o ba n dc h a r l i e ，i naw a yt h a tb o t hp a r t i e sa r es u f f i c i e n tt oo b t a i nt h e s e c r e t ，b u to n eo ft h e mc a n n o t t h ep r e s e n t e dp r o t o c o ka r ea l s os h o w e d t ob es e c u r ea g a i n s te a v e s d r o p p i n g w eg i v eab a s i cm e t h o df o rs h a r i n ga q u a n t u ms e c r e tw i t h o u tt h ea s s i s t a n c e o fat r u s t e dp a r t y , w h og e n e r a t e sa n dd i s t r i b u t e ss h a r e sa m o n gt h ep a r t i c - i p a n t s i n s t e a d ，e a c hp a r t i c i p a n tc h o o s e sh i sp r i v a t es t a t ea n dc o n t r i b u t e s t h es a m et ot h ed e t e r m i n a t i o no ft h el l n a ls e c r e tq u a n t u ms t a t e a n dw e i l l u s t r a t ei t sf e a s i b i l i t ym a i n l yb yo f f e r i n gas p e c i f i cs c h e m eb a s e do nt h e c o n v e n t i o n a l l yq u a n t u m ( k ，n ) t h r e s h o l ds c h e m ep r e s e n t e db yc l e v ee ta 1 3 】t oe l i m i n a t et h en e e do ft h et r u s t e dp a r t y b i tc o m m i t m e n ta l l o w sac o m m i t t e r ( c o n v e n t i o n a l l yn a m e da l i c e lt ob i n d h e r s e l ft oav a l u e ，a n dr e v e a li tl a t e rf o rac o m m i t t e e ( c o n v e n t i o n a l l yn a m e d b o b ) i fa l i c ec a n n o ta l t e rt h ec o m m i t t e dv a l u eo n c es h eh a sc o m m i t t e di t w es a yt h a tt h ep r o t o c o ls a t i s f i e st h ep r o p e r t y b i n d i n g i fb o bc a n n o tl e a r n t h ev a l u eo ft h ec o m m i t t e db i tu n t i la l i c er e v e a l si t w es a yt h a tt h ep r o t o c o l s a t i s f i e st h ep r o p e r t y c o n c e a l i n g as e c u r eb i tc o m m i t m e n tp r o t o c o ls h o u l db e b o t hb i n d i n ga n dc o n c e a l i n g a l t h o u g hm a y e r s - l o - c h a un o - g ot h e o r e ms h o w e d t h ei m p o s s i b i l i t yo fu n c o n d i t i o n a l l ys e c u r eq b c 4 ，5 】，w es t i l li n v e s t i g a t ei tf r o m t w od i f f e r e n tp e r s p e c t i v e s w ei m p r o v et h er e l a t i v i s t i cb i tc o m m i t m e n tp r o t o c o lr b c lp r o p o s e db y k e n t 6 】b ya d d i n gaw a yo fr a n d o mc h o i c e ，t h ei m p r o v e dp r o t o c o lj u s t n e e d sf i x e dc a p a c i t yc h a n n e l a l t h o u g hk e n to n c eo f f e r e da ni m p r o v e d p r o t o c o lr b c 2 7 】w h i c ha l s oc a ns o l v et h ep r o b l e mi nr b c ls ot h a tt h e 量子密码中若干重要问题的研究 c a p a c i t yo fc h a n n e lc a n n o tb ee x p o n e n t i a l l yi n c r e a s i n gw i t ht h ec o m m i t m e n tt i m e ，i tw a ss o m e w h a tc o m p l i c a t e d t h ei m p r o v e dp r o t o c o lp r e s e n t e d i nt h i st h e s i s ( n a m e dr b c 3 ) o f f e r sas i m p l e rw a yt os o l v et h ep r o b l e mi n r b c l w eo b s e r v et h a ti nr e f s f 8 ，9 1 ，c h o ie ta 1 r e v e a l e da na s s u m p t i o no f m a y e r s - l o - c h a un o - g ot h e o r e mt h a tt h ew h o l eq u a n t u ms t a t eb e f o r ea l i c e r e v e a l st h ec o m m i t t e db i ti ss t a t i ct ob o t hp a r t i c i p a n t s a l t h o u g hc h o ie t a 1 p r o p o s e da s e c u r en o n - s t a t i cq b c p r o t o c o lb yd r o p p i n gt h ea s s u m p t i o n ， i ti ss t i l ld i f f e r e n tf r o ma g e n e r a lq b cp r o t o c o ls i n c eat r u s t e dt h i r dp a r t y ( t t p ) i si n t r o d u c e d s of o rt h es t a t i cq b ca n dn o n - s t a t i cq b c ，w eg i v e am o r eg e n e r a lv i e w p o i n ta b o u tt h ei m p o s s i b i l i t yo ft h e m k e y w o r d s ：q u a n t u mc r y p t o g r a p h y ，q u a n t u ms i g n a t u r e ，q u a n t u ms e c r e t s h a r i n g ，q u a n t u mb i tc o m m i t m e n t ，e a v e s d r o p p i n gd e t e c t i o n ，u n c o n d i t i o n a l s e c u r i t y 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含 何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重 贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 的法律结果由本人承担。 学位论文作者签名：垄丝 日期：21 立垒丕理墨星 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质 ，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书 、院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检 。可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：疹缪 日期：7 , , j o 年易月多日 导师签名：前壶差洳 日期：2 , o1 - 年舌月乡日 第1 章绪论 本章首先介绍密码形式的发展，尤其是经典密码和新兴的量子密码，然后 概述量子密码的发展与现状，最后给出本文主要研究的问题及其成果。 1 1密码形式的发展 自人类文明开始，保密通信就成为一种需求。为满足这个需要，密码学的雏 形也应运而生，并在实践中逐渐得到应用和发展，但是直至u 1 9 4 9 年s h a n n o n 提出 保密通信理论【1 0 】才为系统地研究密码学提供科学依据。根据密码学在形成与 发展过程中的不同特征，其表现形式可以分为：艺术密码形式，古典密码形式， 经典密码形式以及新兴的量子密码、混沌密码和生物密码等1 1 1 。目前，在新兴 的密码形式中，量子密码特别引人注目，因此也是本论文主要研究的对象。 艺术密码 1 2 】主要是通过一些简单的变形与变换等技巧将容易理解的用于 交流的信息隐藏在文字、符号、图片等公开的代码中，变为难以理解的信息，是 密码学最原始的形式。现在的隐写术就是在古代的艺术密码与现代信息科学结 合的基础上发展而成的。 随着社会的不断发展，安全性成为重要需求，尤其是在政治、军事以及外 交等领域。而原始的艺术密码无法满足当时的安全性需求，于是密码学逐渐摆 脱艺术形式，发展成为古典密码形式1 3 1 。古典密码使用的基本方法主要是置换 和代换。置换是将明文消息中的字母按某种特殊的顺序重新排列。代换是将明 文消息中的字母用其他的字母、数字或符号来代替。在实际应用中，通常将这 两种技术结合使用。 经典密码形式主要有两种密码体制：对称密码体制( 也称私钥密码体制) 和非对称密码体制( 也称公钥密码体制) 。对称密码体制的思想是要求加密 密钥和解密密钥相同，而非对称密码体制的思想是加密密钥和解密密钥不 同。s h a n n o n 从数学形式上建立了密码学f 1 0 1 ，特别是对称密码的基础理论，而 且首次证明了v e r n a m 密码( 或称一次一密) 1 4 1 是绝对安全的。一次一密的基 本思想为：假设a l i c e 和b o b 共享完全随机的密钥串k ，a l i c e 对密钥串k 和消息 比特串m 按位做异或运算得到c = kom ，然后将c 发送给b o b 。b o b $ 1 j 用密钥 2 量子密码中若干重要问题的研究 串k 则可以恢复出消息m = k0c 。这种一次一密的实现要求通信双方协商 出完全随机的密钥串，密钥串的长度至少和消息串的长度一样，并且密钥不能 重复使用。因此在实际应用中，这种方法很少使用。常用的对称密码算法主要 有d e s ，3 d e s ，a e s 等1 5 1 0 非对称密码体制是1 9 7 6 年d i f f e 和h e l l m a n 首先提出 来的【1 6 1 ，解决了对称密码体制中存在的密钥分配问题。随后，许多公钥密码算 法被提出，例如著名的r s a 算法，r a b i n 密码算法以及椭圆曲线密码算法等1 5 1 。 目前，尽管这些经典密码算法在信息保护方面发挥着至关重要的作用，但 是也存在着一些不容忽视的问题。 首先，大多经典密码算法不具有无条件安全性。尽管一次一密算法能够提 供无条件安全性，但是在实际中利用经典的方法无法产生真正随机的、无重复 的、和消息一样长的密钥，因而较少使用。对称密码算法和非对称密码算法都 是通过增加计算复杂性来保证安全，密钥的长度总是不断增长，但是只要给予 足够的时间就能找到密钥破译算法。因此，随着算法和计算机技术的不断发展， 这些密码算法的破译时间将逐渐缩短。此外，这些密码算法本身可能存在缺陷， 一旦某些缺陷被发现，它们将受到巨大的威胁。例如，在2 0 0 5 年王小云教授等找 到了广泛应用于签名中的哈希函数m d 4 ，m d 5 ，h a 、，a l l 2 8 ，r i p e m d ，s h a 一 0 ，s h a - 1 等的碰撞1 7 1 9 1 ，因而一旦签名算法中使用这些函数，敌手就有可能 在较短时间内成功伪造签名。 其次，对称密码存在密钥分配的问题，所有的算法都必须事先假设密 钥安全。非对称密码虽然能够解决密钥分配的问题，但是它的主要缺陷在 于其安全基础建立在未被证明的数学困难问题之上，例如著名的r s a 算法 是基于分解大整数的困难性f 2 0 1 和e 1 g a m a l 算法是基于求解离散对数的困难 性2 1 1 等。一旦这些困难问题有了突破性的进展，这些密码算法将不再安全。例 如，c a v a l l a r 等于1 9 9 9 年利用数域筛选法成功分解了r s a - 1 5 5 ( 用做r s a 模的十 进制位数为1 5 5 或二进制位数为5 1 2 的大整数) 2 2 。目前有关大整数分解的最好 的记录是k l e i n j u n g 等在2 0 0 9 年成功分解了r s a 7 6 8 ( 用做r s a 模的十进制位数 为2 3 2 或二进制位数为7 6 8 的大整数) f 2 3 1 。 此外，量子计算机和量子算法的迅速发展，严重威胁着经典密码的安 全。g r o v e r 的量子查询算法只需要运算0 ( 何) 次就能在规模为的无序数据库 中找到特定的数据2 4 1 。若假定某计算机的运算速度为1 0 6 次秒，利用g r o v e r 算 法则只需大约四分钟的时间就能破译出d e s 算法中长为5 6 位的密钥。更为轰动 第1 章绪论3 的是s h o r 的量子算法能够在多项式时间内分解大整数和求解离散对数f 2 5 1 。例 如使用c p u 时频为1 g h z 的计算机分解5 1 2 位的大整数，利用s h o r 算法只需3 5 个 小时2 6 1 ，而利用经典的数域筛选法需要8 4 0 0 m i p s 年( 1 m i p s 是指按照每秒执 行1 0 6 次指令的速度，一年所能执行的指令总数) 2 2 1 。可见，一旦量子计算机研 制成功，公钥密码的主要安全基础将完全崩溃，因此有必要寻找能够抵抗量子 计算机攻击，提供无条件安全的密码体制。到目前为止，许多新型的密码形式 如量子密码、混沌密码和生物密码等已经被提出来了，其中基于量子力学原理 的量子密码，由于能够实现无条件安全通信，已经受到广泛关注并且取得较大 进展 2 7 _ 2 9 】。 1 2量子密码的发展与现状 量子密码( 早期等同于量子密钥分配) 是利用量子力学原理来解决密码问 题。这些原理主要包括h e i s e n b e r g 澳1 不准原理，量子不可克隆定理，量子不可区 分性，信息获取一干扰原理以及量子纠缠特性等3 0 ，3 1 1 。这些原理都会在下一章 进行详细介绍。利用这些量子特性，量子密码可以为密码系统提供所需的密钥。 量子态的叠加原理能够产生真正的随机性，并且量子密码能允许空间上相隔的 两个参与方协商出安全的密钥。因此量子密码与一次一密的结合，能够保证通 信的绝对安全。 首先将量子力学理论应用于密码学的是哥伦比亚大学年轻学者w i e s n e r ， 他于1 9 6 9 年指出可利用量子力学理论制造不可伪造的“量子钞票( 1 9 8 3 年 才发表) 3 2 1 。遗憾的是这个设想的实现需要长时问保存量子态，在当时的 技术条件下不太现实，因此没有受到重视，量子密码发展比较缓慢。幸运的 是b e n n e t t 和b r a s s a r d 知晓并发展了这一思想，并于1 9 8 2 年首次使用了“量子 密码”这个术语f 3 3 1 。随后b e n n e t t 和b r a s s a r d 发现量子态虽然不易保存但是可 被利用来传输信息，并于1 9 8 4 年提出了第一个量子密钥分配( q u a n t u mk e y d i s t r i b u t i o n ，简称为q k d ) 协议，这就是著名的b b 8 4 协议 3 4 1 。 b b 8 4 协议的执行需要假设通信双方之间存在认证的经典信道和不安全的 量子信道。认证的经典信道可以通过已有的无条件安全经典认证码3 5 ，3 6 来实 现，因此这种假设是合理的。在这些认证方案中，通常需要事先共享一定长度 的密钥，因此这类q k d 实际上可以看作是一种密钥扩展。b b 8 4 协议的主要步骤 可以描述如下： 4 量子密码中若干重要问题的研究 1 ) 发送方a l i c e 准备一串随机的量子态并发送给接收方b o b ，其中每个量子态 均为这四个非正交态( i _ ) ，it ) ，l ) ，i ) ) 中的一个， l _ ) ，l 下) ) 组成直 线基，而 i ) ，ij ) ) 构成对角基。 2 ) 对接收到的每一个量子态，b o b 随机地选择直线基或对角基进行测量，若 测量结果为l _ ) 或l ) ，记为0 ，否则记为1 。这些测量结果将秘密保存。 3 ) a l i c e 和b o b 通过经典信道比较他们各自选择的基，然后保存基相同的测量 结果，而丢弃基不同的那些结果。 4 ) a l i c e 和b o b 公开比较一些比特，并且对剩下的比特实行纠错和保密) j n 强i 等 操作以获得最终共享的密钥。 量子不可克隆定理保证了窃听者e v e 不能任意复制信道上传输的量子态，而 一旦e v e 对传输的量子态进行测量以获取信息，就会对该状态造成干扰，从 而a l i c e 和b o b 可以检测到窃听者的存在。自从b b 8 4 协议提出之后，q k d 得到广 泛研究。总体来说，主要有两种类型的q k d 协议：基于单粒子态的q k d 协议和 基于纠缠态的q k d 协议。1 9 9 1 年，e k e r t 基于e p r 对f 3 7 】的纠缠特性以及b e l l 不 等式f 3 8 提出一个q k d 协议( 艮p e 9 1 协议) 3 9 1 ，尽管这个协议可规约至u b b 8 4 协 议4 0 1 ，但是它的提出开启了对纠缠态的研究。随后b e n n e t t 等给出了e 9 1 协 议的简化协议，该简化协议不再需要使用b e l l 不等式来检测窃听情况，并 证明了该协议能规约至u b b 8 4 协议，从而认为纠缠在q k d 协议中并不是必 须的 4 0 1 。1 9 9 2 年，b e n n e t t 基于两个非正交态提出一个更简单但效率减半 的q k d 方案( 即b 9 2 协议) 4 1 1 。1 9 9 8 年，b r u 了基于六个非正交态提出一个安全 性更高的q k d 方案( 即六态协议) f 4 2 1 。研究表明这些q k d 方案利用量子力学 原理均能提供无条件安全性 4 3 - 4 6 1 。 q k d 是量子密码中研究最多也最深的问题，甚至最开始量子密码就等 同于q k d 。q k d 不仅在理论上取得很大进展，在实验上也发展迅速，主要 是在自由空间和光纤中实现q k d 。1 9 8 9 年，i b m 和加拿大蒙特利尔大学合作 首次完成了b b 8 4 的实验，在相隔3 0 c m