（基础数学专业论文）公开信道密钥协商中的信息协调.pdf

公开信道密钥协商中的信息协调 计算数学专业 指导教师 硕士研究生郑严 包小敏教授 摘要 信息安全是一个具有重要意义的研究课题，密码学是保障信息安全的重要工具之一，目前广 泛应用的计算安全密码大多依赖于没有严格证明的数学难题和计算困难性。然而，随着经典计算 机计算能力的提高和量子计算机研究的重大突破，依赖于计算安全的信息安全体制将面临着严 峻的挑战，无条件安全密码体制的建立迫在眉睫。以经典密码学和量子物理学为基础的量子密码 作为种新型的密码体制，其安全性受到量子力学基本规律的保证；其中量子不可克隆定理和测不 准原理保证了量子密码的无条件安全性和对窃听的可检测性，使得量子密码具有良好的性能和 前景，作为量子密码研究重点的量子密钥分发( q k d ) 也倍受关注。由于产生和检测单光子比较 困难，基于离散变量的量子密钥分发和量子直接安全通信难以获得高通信速率，量子密码的开发 和应用受到了很大的阻力。而量子密钥分发中的密钥协商却由w ”l 盯、c s i s z a r 、k o r n e r 、m a u r e r 等 人先后与有扰信道、离散无记忆广播信道、卫星广播信道结合构成了无条件安全秘密协商的模 型。在无条件安全的密钥协商中无论是量子信道还是有扰信道，都可以抽象为这样一个模型：通 信双方a l i c e 和b o b 及敌手e v e 分别得到概率分布为p x y z 的x y ：z 三个随机变量，之后他们在公 共信道上进行无条件安全的密钥协商。利用有扰信道的密钥协商一般可以分为优先提取、信息 协调和保密增强三个阶段，量子密钥协商中只有后两个阶段。在这一研究领域，本文的主要研 究成果如下： ( 1 ) 总结公开信道上信息协调前数据处理模型，对已有的优先提取协议进行了阐述，并且以概 率和信息理论为基础对协议进行了分析，证明了协议的可行性，计算得出协议操作过程中 泄露信息的界限和对最终密钥的影响。 ( 2 ) 从数学证明的角度阐述了密钥协商的理论基础：揭示了密钥率与原始串相关系数之间的关 系：在公开信道上的协商中，研究了舢i c e 和b 0 b 间的信息协调泄露信息对e v e 的r c n y i 的熵 影响，揭示了信息协调与保密增强问的联系；并在信息论的基础上的推导出密钥协商得到 的最终密钥的上界和下界。 ( 3 ) 详细介绍了国内外密钥协商所用的经典协议：b b b s c 算法、c a s c a d e 协议、w i n n o w 算法、 d i s t i l l a t i o n 和r c o n c i l a t i o n 的结合协议，分析了协议过程中在经典信道通信的次数和泄露给 窃听者的信息，以及协议对合法通信双方最终密钥的影响和对窃听者的影响。 关键词：量子安全通信，量子密钥分发，协商过程，密钥协商协议 a b s t r a c t i n f o r m a t i o ns e c u r i t yi sav e r ys i g n i t i e a n ti s s u e 。c r y p t o g r a p h yi so n eo ft h ee f f i c i e n tm e t h o d st h a t l 翻r o t e e t st h es e c r e ti n f o r m a t i o nf r o mb e i n ge a v e s d r o p 阻1 1 他c o m p u t a t i o n a le r y p t o g 阳p h yi sb a s e d 0 1 1t h eu n p r o v e dc o m p u t a t i o n a la s s u m p t i o n s h o w e v e r , w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c e a n dt h eb r e a k t h r o u g ho ft h eq u a n t u mc o m p u t e r , t t l ci n f o r m a t i o ns e c u r i t ym e c h a n i s md e p e n d i n g0 1 1 t h ec o n v e n t i o n a lm a t h e m a t i c a lc r y p t o g r a p h yw i l lf a c et h ec h a l l e n g e s q u a n t u me r y p t o g r a p h yi sb a s e d o nb o t ht i l ec o n v e n t i o n a lc r y p t o g r a p h ya n dq u a n t u mp h y s i e s i t ss e c u r i t yi sg u a r a n t e e db yt h ef u n d a - m e n t a ll a w s o fp h y s i c s b o t hq u a n t u mn o - c l o n i n ga n dt h eh e i s e n b e r gt m e e r t a i n t yr e l a t i o ne n s u t h e a b s o l u t es e c u r i t ya n dt h ea b i l i t yo fd e t e c t i n ge a v e s d r o p p e r t h e s ef a c t sg u a r a n t e et h a tq u a n t u me r y p - t o g r a p h yh a st h ee x c e l l e n tc a p a c i t ya n dt h ea t i i a c t i l c cf o r e g r o u n d a sa l li m p o r t a n tr e s e a r c hi s s u eo f q u a n t u mc r y p t o g r a p h y , q u a n t u mk e yd i s t r i b u t i o n ( q k d ) i st h em o s tp r o m i s i n gq u a n t u m i n f o r m a t i o n t e c h n o l o g y h o w e v e r , d u et ot h ed i f f i c u l t yi nb o t hs i n g l ep h o t o ng e n e r a t i o na n dd e t e c t i o n , t h ei r a n s - m i s s i o nr a t eo fd i s c r e t ev a r i a b l eq k da n dq u a n t u m 剐x ：u d i r e c tc o m m u n i c a t i o ni sv e r yl o w k e y a g r e e m e n to fq u a n t u mk e yd i s t r i b u t i o ni sc o m b i n e dw i t ht h ei n t e r r u p t i v ee h a m a e l , d i s c r e t em e m o f y - l e s sb r o a d c a s tc h a n n e l sa n ds a t e l l i t er a d i oe h a t m e lt oc o n s t i t u t eam w ：0 n d i t i o n a ls e c u r i t ym o d e ls e c r e t c o n s u l t a t i o n sb yw y n c r , c s i s z a r , k o l l t l c r , m a u r e ra n do t h e r s s u c has c e n a r i oc a l lb ea b s t r a c t e df r o m q u a n t u mc h a n n e l sa n dn o i s yc h a n n e l s t w oc o m m u n i c a n t s a l i c ea n db o b ，a n da l la d v e r s a r y , e v e ，l 争 e e i v et h r e ev a r i a b l e sxy zw h i c ha 托d i s t r i b u t e da c c o r d i n gt os 伽p r o b a b i l i t yd i s t r i b u t i o n 局【y z t h e na l i c ea n db o bb e g i ns e c r e t - k e ya g r e e m e n to v c l rap u b l i cc h a n n e l s u e l aas e c r e tk e ya g r e e m e n t o v e rap u b l i cc h a n n e lu s u a l l yc o n s i s t so ft h r e ep h a s e s ：a d v a n t a g ed i s t i l l a t i o n i n f o r m a t i o nr e c o n e i l i - a t i o na n dp r i v a c ya m p l i f i c a t i o n ，b u ta d v a n t a g ed i s t i l l a t i o ni s n tr e q u i r e df o rt h eq u a n t u ms e c r e t - k e y a g r e e m e n t 1 1 km a i nw o r ki nt h i st h e s i si sa sf o l l o w s ： ( 1 ) s u m m a r yo fd a t a - p l - o c e s s i n gm o d e lp u b l i cc o n s u l t a t i o n sb e f o r ei n f o r m a t i o nr e c o n c i l i a t i o n ，t h e m o r i t yo f t i l ee x t r a c t i o np r o t o c o lh a sb e e ne l a _ b a 国t e d a n dt h ep r o t o c o la n a l y s i sf r o mt h ev i e w o fp r o b a b i l i t ya n di n f o r m a t i o nt h e o r y , p r o v i n gt h ef e a s i b i l i t yo ft h ep r o t o c o l ，c a l c u l a t i n gt h e b o u n d a r i e so fi n f o r m a t i o nl e a k e di np r o t o c o l sa n dt h ei m m e to ff i n a l l yl 【e y ( 2 ) f r o mt h ev i e wo f m a t h e m a t i c sp r o o f ，t h et h e o r e t i c a lb a s i so ft h ek e ya g r e e m e n th a sb e e ne l a b - 堪删；r e v e a l i n gt h er e l a t i o n s h i pb e t w e e nf i l ei 【i 巧r a t ea n dt h ee o r r e l a t i o nc o e f f i c i e n to ft h e o r i g i n a ts t r i n g ：i nt h eo p e nc h a n n e lo fe o m t t l t a t i o n s ；r e s e a r c h i n gt h ei m p a c to ft h ed i s e l o - s u 佗i n f o r m a t i o nw h i e l ab e e nd i s c l o s e di nt h ei n f o r m a t i o nr e c o n c i l i a t i o np r o c e s sb e t w e e na l i c e a n db o bi ne v e sr e n y ie n u o p y ，r e v e a l i n gt h er e l a t i o n s h i pb e t w e e ni n f o r m a t i o nr e c o n c i l i a t i o n a n dl ，r i v a e ya m p l i f i c a t i o na n da tt h eb a s i so fi n f o r m a t i o nt h e o r yd e r i v a t i n gt h es e c t o ra n dl o w e r b o u n d so ff i n a l l yk e yw h i c hc o m ef r o mt w os t r i n g sn o te x a c t l ys a m eb ys e c r e t - k e ya g r e e m e n t ( 3 ) d e t a i l i n gt h ec l a s s i ci n f o r m a t i o nr e c o n c i l i a t i o np r o t o c o l s ：b b b s ca l g o r i t h m , c a s c a d e 伊o t o e o k w i n n o wa l g o r i t h m , d i s t i l l a t i o na n dr e c o n c i l i a t i o nc o m b i n a t i o no fp r o t o c o l ，d o i n ga n a l y s i so f t h en u m b e ro f e o m m t m i e a t i o na n dt h o s ei n f o r m a t i o nl e a k e dt oe v e0 1 1t h ec l a s s i c a lc h a n n e li nt h e 目录 p r o t o c o lp r o c e s s a sw e l la st h ei m p a c to ft h ef i n a l l yk e yb e l o n gt oe a v e s d r o p p e ra n dl e g i t i m a t e c o m m u n i c a t i o n k e yw o r d s ：q u a n t u ms e c u r ec o m m u n i c a t i o n ，q u a n t u mk e yd i s t r i b u t i o n , i n f o r m a t i o nr e c o n c i l i a t i o np r o c e s s ，i n f o r m a t i o nr e c o n c i l i a t i o np r o t o c o l 独创性声明 学位论文题目：公开信道密钥协商中的信息协调 本人提交的学位论文是在导师指导下进行的研究工作及取得的研 究成果。论文中引用他人已经发表或出版过的研究成果，文中已加了特 别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同仁在文 中做了明确说明并表示衷心感谢。 学位论文作者： 备手 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权西南大学研究生院( 筹) 可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作者签名： 知孚 i ， 导师签名： 己心白乏 签字日期： 川年岁月巾 签字日期：一年歹月日 1 1 问题的由来 第1 章绪论 随着经济的发展、科学的进步、全球信息高速公路建设的兴起和通信的网络 化，数字化，个人化，智能化，宽带化进程的不断加快，人类的信息交换和传递越 来越频繁，人们对信息的依赖也越来越严重，用户对信息的安全存储，安全处理和 安全传输的需求愈益迫切。特别地，随着网络上各种新业务的兴起，比如电子商 务( e l e c t r o n i cc o m m e r c e ) 、电子现金( e l e c t r o n i cc a s h ) 、网络银行( n e t w o r kb a n k ) 等【l ，2 1 ，以及各种专用网络的建设，比如金融网、军事网等，使得网络信息的安全 保护问题就更加显著，解决这一问题的唯一有效的手段是发展和应用密码学。密码 学也多次在战争中发挥了至关重要的作用，二十世界大战中的珍珠港、中途岛海战 便是著名实例之一。因此可以说，密码学的应用已经渗透到包括军事、政治、经济 等社会生活的各个方面。 由于密码学的特殊作用，世界各国对密码学的研究一直秘密进行，密码学方面 的文献非常少。第二次世界大战之后，密码学方面的一些著名著作【3 。4 ，5 】的问世揭 开了密码学的神秘面纱。密码学包括两个分支：密码编码学和密码分析学。密码编 码学研究密码体制的设计，对信息进行编码以实现隐蔽信息；而密码分析学是研究 如何破解被加密信息从而获取有效信息的方法和理论。密码编码学和密码分析学是 相互对立，相互依存并发展的。密码学的起源可以追溯到远古时代，它的发展历史 基本上可以分为四个阶段：艺术密码【6 】，古典密码【7 】，计算密码与物理密码【8 】。 艺术密码是密码学的原始表现形式，这种形式的密码主要通过一些技巧将信息 隐藏在语言文字、符号、图片等公开的代码中。从某种意义上来说，这种密码形式 更多的是作为一种游戏和欣赏，而不是作为实用的信息保护体制。艺术密码可以通 过多种方式来实现，主要方式包括：文字变形、在艺术作品中加入巧妙的手笔、符 号的适当排列等等，在现代社会中，艺术密码仍是人们感兴趣的密码形式，常在艺 西南大学硕士学位论文 术作品和文字游戏中出现。 由于政治、军事和外交等领域的需要，安全性成为密码的关键因素，原始的艺 术密码不能保证这种安全，于是古典密码形式诞生了。古典密码历史可以追溯到公 元前一世纪，c a e s a r 大帝就曾在战争中使用过一种极简单的代换式密码【9 】：每个字 母都由其后的第三个字母( 依字母表顺序) 所代换，这就是所谓的c a e s a r 密码系统 的雏型。古典密码学的发展主要出现了两种密码体制：置换密码体制和代换密码体 制。置换密码体制的特点是明文和密文中所含的元素式相同的，仅仅是位置不同而 己；代换密码体制中，密文和明文不是直接的置换关系，而是通过一个或多个明文 字母表到密文字母表的映射将明文加密成密文，可以分为单表代换密码体制和多表 代换密码体制。因此，古典密码本质上是一种以线性代数为基础的密码形式。虽然 许多古典密码已经经受不住现代手段的攻击，但是它们对于现代密码学的研究是功 不可没的，其思想至今仍然被广泛使用。 在密码学发展的很长一段时间内，密码仅限于军事、政治和外交的用途，密码 学的知识和经验也仪掌握在与军事、政治和外交有关的密码机关之中，再加上通信 手段比较落后，所以，不论是密码理论还是密码技术，发展都很缓慢。1 9 4 9 年，信息 论的创始人s h a n n o n 提出了保密通信系统模型。他将当时的各种加密体制概括成一 对加密和解密变换器，把保密通信系统概括为一条传输密钥的秘密信道和通过密钥 进行的加、解密变换，以及传输这种变换结构的普通信道。他的这一工作为其后的 保密通信系统开辟了一条用数学模型和现代信息论进行定量分析的密码学之路。 2 0 世纪中期以后计算机技术的快速发展，使我们进入了信息化社会，信息的传 输、处理等过程逐渐转移到计算机中，信息的加密、解密也从人工、机械方式转由计 算机方式来处理。通过计算机来处理信息变换就有无可比拟的优势，其中最重要的 就是能够实现加、解密的自动化，这对于大容量、高速率的保密性数据通信尤其显 得重要。由此产生了可在计算机和电脑芯片上运行的计算密码形式。对称密钥体制 便是计算密码中的一种重要的密码体制，这种密码体制的基本思想是加密密钥和解 密密钥相同。因此，这种密码体制要求所有密钥都被严格保密，不得有任何泄露。对 称密码可分为两类。一次只对明文中的单个位( 或字节) 运算的算法称为序列算法或 序列密码。另一类算法是对明文的一组进行运算，相应的算法称为分组密码。现代计 算机密码算法的典型分组长度为6 4 位、1 2 8 位、2 5 6 位。典型的对称密码包括d e s ( 数 据加密标准) ，i d e a ( 国际数据加密算法) 等。美国早在1 9 7 7 年就制定了自己的数 2 1 绪论 明文 e v e 窃听 图1 1 ：s h a n n o n 的保密通信系统模型 明文 据加密标准一d e s 。随着d e s 的出现，人们对分组密码展开了深入的研究和讨论。 现在已有大量的分组密码，如d e s 的各种变形：i d e a 、s a f e r 、r c s 、s k i p j a c k 、 f e a l 等，美国国家标准技术研究所( m s t ) 在2 0 0 1 年1 1 月2 6 日，正式公布了新标 准a e s ，来取代d e s 。 网络和通信技术的飞速发展导致了对身份认证、数字签名和消息确认等方面 的强烈需求，计算密码中的公钥密码便应孕而生。1 9 7 6 年，美国斯坦福大学的d i f i e 与h e l l m a n 在“密码学的新方向 一文中提出了公钥密码体制( p u b l i ck e yc r y p t o s y s t e m ) 的新概念，开创了现代密码学的新领域。公钥密码体制是计算密码中的另一 种重要的密码体制，基本思想是加密密钥和解密密钥不同，部分密钥可以象电话号 码一样公开。公钥密码的主要思想概括如下g 若用户舢波拥有公开密钥和秘密 密钥，并且从公开密钥中无法计算出秘密密钥，将公开密钥公开，秘密密 钥保密。若用户b o b 要向a l i c e 保密送去明文m 可查a l i c e 的公开密钥，用加 密得密文c = 取。( m ) 。a l i c e 收到c 后，用只有自己才能掌握的秘密密钥对c 解 密得m = d h ( m ) 。1 9 7 8 年，r i v e s t ，s h a m i r 与a d l e m a n 基于大整数分解的困难性 提出了第一个公钥密码算法( r s a 公钥密码算法) 【1 0 。随后许多公钥密码算法被 提出，如基于有限域上离散对数的e i g m a l 公钥密码算法【l l 】，基于多项式、不同模 混合运算的相互作用，也依赖于最大格及寻找最短向量的困难性的n t r u 公钥密码 3 西南大学硕士学位论文 体制等。然而，所有这些公钥密码的安全性均建立在没有被严格证明的数学难题之 上，比如大数分解问题或者有限循环群的离散算法。 图1 2 ：公钥密码通信模型 因此，公钥密码体制本质上就是一个单向函数，计算密码中使用的单向函数都 是基于计算复杂度的，对应的安全性也属于计算安全 1 2 1 。 虽然计算密码在信息安全方面发挥重要作用，在维护信息安全方面取得了很 大的成功，但也存在一些问题。首先，计算密码不能提供具有无条件安全性的密码 方案。现代密码学认为，任何加密体系的加密解密算法都是可以公开的，其安全性 在于密钥的保密性。实际上，由于存在被动窃昕的可能性，如果通信双方完全通过 在经典信道上传输信息，则在双方之间建立保密的密钥是不可能的。其次，随着技 术的不断发展，计算机的计算速度呈级数增长，量子计算机的即将出现更是威胁着 计算密码的安全性。研究表明，用量子计算机破译r s a 算法只要几分钟量级的时 间 1 3 ，1 4 1 ；说明现有的计算密码在计算机技术的发展面前已经力不从心，要维护信 息安全需求构建更科学更完善的密码体制。 如何才能构建出完善保密的密码体制呢? 信息论的奠基人s h a n n o n 曾给出了完 善保密的定义：如果日( m ) = h ( a , t l c ) ，明文数据和密文数据统计独立，密文不能 给出明文的任何信息。在试验模型中公认具有绝对安全的加密算法是采用一次一密 乱码本，一次一密乱码本要求合法通信双方a l i c e 和b 0 b 拥有和明文相同长度的密 钥，发送者a l i c e 首先把明文和对应的密钥进行异或操作，然后把得到的密文发送给 4 1 绪论 接受者b o b ，b o b 把接收到的密文和自己拥有的密钥再次进行异或操作，恢复出明 文。一次一密乱码本是唯一可被严格证明的安全密码算法，然而，一次一密乱码本 要求密钥具有和明文同样的长度，并且密钥只能利用一次。因此为了使一次一密乱 码本得到绝对安全的保密通信，关键在于找到绝对安全的密钥分发方法来提供大量 绝对安全的密钥。 在计算机计算能力的飞速发展的前提下能否实现不可破译、不可窃听的保密 通信? 近年来，物理学者加入了解决这些问题的研究行列，他们设想用微观粒子作 为信息的载体，构造利用量子效应工作的电子元件，在量子力学理论之上研究信息 的行为，成功地将量子理论和信息科学结合起来，孕育出量子信息学理论，为信息 科学的持续发展开创了新的空间。利用微观粒子的状态表示的信息就称为量子信 息。信息一旦量子化，描述“原予水平上的物质结构及其属性”的量子力学特性便 成为描述信息行为的物理基础，在此基础上研究信息的存储、传输和处理的一般规 律的学科称为量子信息学【1 5 】。量子信息学是量子力学与经典信息学结合的新兴学 科，微观系统的量子特性为信息学带来许多令人耳目一新的现象，在信息的表示、 加工、处理和传输上生长出一些新的概念、原理和方法。在量子信息的研究过程中 不断爆出惊人的结果，揭示出超越经典信息学与量子力学两个理论体系本身所包含 内容的预想不到的全新概念，完成了现代信息科学中以下两个根本性的发现： ( 1 ) 将经典信息( s h a n n o ni n f o r m a t i o n ) 映射到量子状态上，依照量子状态的特性 对信息实施存储、传输和处理，此时科学家发现了若干基于经典信息理论认为 是不可能的“信息机能 。例如信道容量的超加法性等。 ( 2 ) 将量子状态的构造定义为量子信息，量子信息的定量化用q u b i t 表示。遵从量子 力学规则存储、处理和传送量子信息，此时科学家观察到了量子力学预见的、 有关量子计算机以及量子远程瞬间传送实现信息通信等科学技术。 两个根本性的发现在提高计算机信息的处理速度、增大信息的存储容量等方面 都可以突破现有计算机性能的极限，为计算机科学与技术的可持续发展开辟了崭新 空间。同时以经典密码学和量子物理学为基础的量子密码 1 6 ，1 7 ，1 8 ，作为一种新 型密码体制是量子物理学和密码学相结合的- - f l 新兴交叉科学，它成功地解决了传 统密码学中单靠数学无法解决的问题( 无条件安全的密钥分发) 并引起国际上高度 的重视，是主要应用于量子信息领域的一个重要课题。量子力学的基本规律量子测 不准原理【l9 】和量子不可克隆定理 2 0 1 保证了量子密码的安全性【2l 】；还有对窃听的 5 西南大学硕士学位论文 可检测性，使得量子密码具有良好的性能和前景，同时也为密码学的发展提供了新 的动力，开辟了更广阔的领域。 与计算密码计算安全性不同的是量子密钥分发模型【2 2 】建立在量子信息理论基 础上，假定敌手拥有无限的时间、设备和资金，对敌手的计算能力不做任何限制。 不管敌手使用多长的时间以及有多大的运算能力，他采用任何破译方法都不会比在 未知密文的情况下对明文进行随机猜测强。随着科技的迅猛发展，具有无限计算能 力的量子计算机和d n a 计算机的实现也不是梦想，故量子密钥分发模型的建立有 着非常现实的意义。 1 2 密钥协商的发展 随着科技的进步，2 0 世纪9 0 年代以来，量子密码受到了人们的高度重视，并取 得了迅速的发展。量子密钥分发与经典密钥分发的目的是致的，都是为信息安全 提供保密性；但它们的不同之处在于两者的实现方式。经典密钥分发建立在数学 理论的基础上，而量子密钥分发以量子物理特性为基础，采用不同于经典密钥分发 的通信模式实现。目前量子密码研究主要采用离散物理变量作为信号载波，如单光 子、微弱激光脉冲等，但是离散变量量子密码需要单光子产生和检测装置，实验实 现困难，并且信道容量低，即单信号所能传输的信息量较低。然而，如压缩态、相干 态、双模纠缠态等连续变量量子信号容易产生，可以采用外差、零差平衡接收机检 测，容易对其量子信号进行操作，同时具有相对高的信道容量。无论是连续变量量 子密钥分发还是离散变量量子密钥分发都可以归结为信息论意义上安全的密钥分 发协议 2 3 ，2 4 1 ，可以使用信息论意义对其进行安全性分析，从而从更高的一个层次 来理解量子密钥分发协议。量子密钥分发使得合法通信双方a l i c e 和b o b 在异地可以 随时建立起秘密的随机序列，通常称为密钥。然而由于实际量子信道存在不可避免 的噪声，以及非法窃听者干扰，使得合法双方生成的密钥中存在一定的误码。因此， 当密钥分发完成后，若其误码率在一定范围内，则通信双方通常利用信息协调技术 来消除误码。量子密钥分发过程一般需要4 个步骤：量子传输，数据筛选，信息协调 和信息保密增强。大致过程如下：首先必须利用一个确定的量子信源产生随机量子 比特串，并将所产生的量子比特串通过量子信道传输到另个授权用户，然后进行 安全性检测，获得原始密钥。原始密钥不能作为最终的密钥，因为在原始密钥中可 能存在由于各种因素导致的错误，使得a l i c e 和b o b 的密钥不完全相同，甚至攻击者 6 1 绪论 可能知道原始密钥中的部分信息，这些问题都会影响到密钥的安全性和准确性。为 了获得无条件安全的共享密钥，原始密钥可通过信息协调( r e c o n c i l i a t i o n ) 【2 5 1 和保 密增强( p r i v a c ya m p l i f i c a t i o n ) 【2 6 技术实现。利用公共经典信道对筛选数据进行纠 错的全过程称为信息协调。由于量子通道噪音的存在或e v e 的窃听，a l i c e 发送的密 钥和b o b 接收的密钥并不完全相同。信息协调就是通过公共通道的讨论，找到并除 去a l i c e 发送端和b o b 接收端密钥串中的不同，同时使e v e 所得到的信息尽可能地少。 公共信道通信中的信息协调技术常会伴随通信信息的泄漏，而且泄漏的信息也可通 过保密增强技术来消除。因此信息协调是通信系统中不可缺少的部分，在量子保密 通信中通常利用奇偶比较方法来构造各种信息协调协议，通常双方按照协议将生成 的密钥分成段，并计算其奇偶性，然后在经典信道中进行奇偶校验。为了消除窃听 者获得的信息，在每次奇偶校验结束双方丢掉一位。利用奇偶校验完全消除误码， 需要多次在经典信道上迸行通信，最终使得a l i c e 和b o b 拥有相同的密钥串。 后来量子密钥分发中的密钥协商模型由w y n e r 、c s i s z a r 、k o m e r 、m a u r e r 等人先 后与有扰信道、离散无记忆广播信道、卫星广播信道结合构成了无条件安全秘密 协商的模型。以卫星广播信道模型【2 7 】为例：卫星以低信噪比不断地向地面发送信 号，a l i c e ，b o b 及敌手e v e 分别用不同的接收天线接收卫星发送的信号，由于天线不 会是完善的，故一定会有噪声，三者分别得到三个随机变量x ，y 及z ，联合概率分 布服从取y z 。此外，a l i c e 和b o b 间还存在一个具有可窃听但不能窜改信息的公共 信道。双方可以在该公共信道上进行协调，最后得到两方共有的密钥。无论是量子 信道还是有扰信道，他们共同的特点都是敌手不可能得到与接收方相同的信息。故 我们可以将无条件安全秘密协商的模型抽象成为如下形式： ( 1 ) 初始化阶段：a l i c e 、b o b 及敌手e v e 分别接收到三个随机变量x ，y 及z 作为初始 信息，联合概率分布服从取y z 。 ( 2 ) 通信阶段：a l i c e 和b o b 之间公开地交流信息c = ( c 1 ，c a ，) ，其中a l i c e 发 送c 1 ，6 , 3 ，b o b 发送俨，c 4 ，每条消息的内容可能依赖于当时发方对协议 的认识及自己产生的一些随机比特。 ( 3 ) 决策阶段：a l i c e 和b o b 决定接受或拒绝协议执行的结果，如果m i c e 决定接受， 则根据她对协议的认识生成一个密钥s ，类似地，如果b o b 决定接受，则根据他 也生成一个密钥9 。成功的密钥协商要求以很大的概率保证s = 伊，再通过秘 密放大消除在信息协调过程中泄露给e v e 的信息，最终e v e 对s 几乎一无所知。 7 西南大学硕士学位论文 图1 3 ：m a u r e r 的卫星广播信道模型 公开信道密钥协商发展到今天，出现了很多经典协议；例如：信息协调前的数据处 理中出现重复编码协议、迭代协议、比特对迭代协议等优先提取协议；在信息协调 中出现了：b b b s c 算法、c a s c a d e 协议、w i n n o w 算法、d i s t i l l a t i o n 和r e c o n c i l i a t i o n 的 结合协议。在保密增强阶段相邻无碰撞函数也是各国密码学家关注和重点研究的课 题。 1 3 论文主要内容和章节安排 第二章主要介绍一些论文用到的概率论、信息熵、信道安全容量和密钥分发速 率的基木概念。 第三章主要讨论信息协调前的数据处理，介绍和分析了重复编码协议、迭代协 议、比特对迭代协议等优先提取协议 第四章主要从理论上证明无条件安全密钥协商的可行性。其中包括密钥率与原 始串相关系数的关系、合法通信者的密钥协商对窃听者的影响、密钥协商的上界和 下界。 第五章主要研究信息协调协议和协议分析：b b b s c 算法、c a s c a d e 协议、w m n o w 算 法、d i s t i l l a t i o n 和r e c o n c i l i a t i o n 的结合协议。 8 1 绪论 第六章主要研究密钥协商协议在量子密钥分发协议- - s s s 4 中的应用，并通过 实例对于b b 8 4 协议作出相应的安全性分析。 9 2 1 概率论基础 第2 章知识预备 首先给出以下几个定义1 2 8 1 ：随机实验：满足下列三个条件的试验称为随机 试验； ( 1 ) 试验可在相同条件下重复进行； ( 2 ) 试验的可能结果不止一个，且所有可能结果是己知的； ( 3 ) 每次试验哪个结果出现是未知的；随机试验以后简称为试验，并常记为e 。 随机事件：随机事件分为必然事件与不可能事件；每次试验必发生的事情称为必然 事件，每次试验都不可能发生的事情称为不可能事件。 基本事件：试验中直接观察到的最简单的结果称为基本事件。 样本空间：从集合观点看，称构成基本事件的元素为样本点，常记为u 。例如，在日 中，用数字l ，2 ，6 表示掷出的点数，而由它们构成的单点集 1 ) ， 2 ) ， 6 ) 便是毋中的基本事件。在易中，用日表示正面，t 表示反面，掷出硬币正反面试 验的样本点有( 日，日) 、( 日，t ) 、( z 日) 、( t ) ，掷出硬币正反面试验基本事件便 是 ( 日，日) ) 、 ( 日，t ) ) 、 ( z 日) ) 、 ( 正t ) ) 。显然，任何事件均为某些样本点构成 的集合。例如，在毋中”掷出偶数点“的事件便可表为 2 ，4 ，6 ，试验中所有样本点 构成的集合称为样本空间，记为q 。样本空间q 是一个有限或者可数的集合。q 中的 一个元素u 就称为元素事件，而q 的一个子集a 就称为事件。概率函数所将q 的一 个子集映射为一个大于等于0 4 , 于等于l 的实数。其满足下面的条件： ( 1 ) 0 p ，_ f a 】1 ，a q ( 2 ) p r a 1 = 0 ( 3 ) p r 【q 】= l 西南大学硕士学位论文 ( 4 ) 如果a b 则p “州p r 【b 】 ( 5 ) n 陋u h i = n 【卅+ 所一n 陋n 矧 如果p r 陋nb 】= p r a 宰p r 【矧，则称2 个事件a 和b 独立。 条件概率的概念： 在己知事件b 发生条件下，事件a 发生的概率称为事件a 的条件概率，记 为p r i a i b 。条件概率p r a i b 与无条件概率所渊通常是不相等的。 条件概率的定义 p r 陋i 冽= 可p r a a b ，尸r h i 。 如果随即变量x 的取值范围为x ，则随机变量x 的数学期望为 e 闷= z p r = 司 随机变量x 的方差为 d x 】= 吲( x e 】) 2 】= e x 2 】一e x 】2 ( 2 1 ) ( 2 2 ) ( 2 3 ) 二点分布的分布列： 圈a 10 2 2 信息论基础 论文中，我们用x 代表集合，x 代表集合中元素的个数论文所有的对数定 为以2 为底 2 2 1 s h a n n o n 熵、条件熵、互信息 s h a n n o n 熵是对随机变量的不确定性的度量，也是随机变量取各个可能值后 所显示的信息的平均度量【3 】。其定义如下： 1 2 2 知识预备 定义1 设z 为取值于集合x 的一个随机变量，概率分布为& ，剐x 的s h a n n o n 熵 定义为日( z ) = 一善xp x ( z ) l o g p x ( z ) 设y 为取值于集合y 的一个随机变量， 则在y 的条件下x 的s 地n 佗d 佗熵定义为日( x l y ) = v yp y ( y ) h ( i l y = y ) ，其 中日( x l y = s ，) 由概率分布p x l g ；掣确定。 定义2 设x 为取值于集合x 的一个随机变量，概率分布为b f ，y 为取值于集合y 的 一个随机变量，概率分布为p y 两者的联合概率分布为p x y ，则x 和y 问的互信息 定义为，( x ；y ) = 。fp x g ( x y ) 1 0 9 错 互信息描述了两个集合之间，一个集合中事件出现后所给出的关于另一个集合 中的事件出现的信息量的平均值。可得到关系式 2 9 】 j ( x ；y ) = h ( x ) 一h ( x i y ) = h ( y ) 一h ( y t x ) 2 2 2 冲突概率j f i l r e n y i 熵 r e n y i 熵 3 0 ，3 1 - 与s h a n n o n 熵一样定量地描述信息的一种方法。在无条件安全 的秘密钥提取中，二阶r e n y i 熵是从理论上分析所能提取出的秘密钥长度的一种有 效方法。设x 为取值于集合x 的一个随机变量，概率分布为b 【。 定义3 x 的二阶冲突概率如( z ) 定义为x 在两次独立实验中取相同值的概率， 即吃( z ) = x 磺( z ) 。 定义4 x 的二阶r e n y i 熵定义为x 的二阶冲突概率的对数的负值为 日2 ( x ) = 一l 0 9 2 如( z ) 定义5 设x 为取值于集合x 的一个随机变量，概率分布为玖，x 的三阶冲突概 率如( x ) 定义为x 在三次独立实验中取相同值的概率，即如( x ) = 霉x 磺 ) 定义6 x 的三阶r e n y i 熵定义为x 的三阶冲突概率的对数的负值的一半即 1 凰( x ) = 一言1 0 9 2 如( z ) 定义7 对于在某一事件a t x 的二阶冲突概率、二阶r e n y i 熵、三阶冲突概率和三 阶r e n y i 熵分别表示为： p a ( x l a ) ，凰( x i a ) ，如( x l a ) ，日3 ( x l a ) 西南大学硕士学位论文 其中 如( x l a ) ；磺( z ) z x 吼( x i a ) = 一l 0 9 2 如( x i a ) p 日( x i a ) = 磺( x l a ) 霉x 1 风( x t a ) = 一言l 0 9 2 如( x l a ) 定义8 在随机变量y 条件下的二阶和三阶r e n y i 熵分别定义为： 2 ( x i y ) = 5 , ( y ) t t 2 ( x i y = y ) 掣 风( x i y ) = p y ( 可) h 3c x i y = 可) p 日2 ( x ) 可以表示为凰( x ) = - l 0 9 2e 【p x ) 】，而