第10章密码学的新方向.ppt

《第10章密码学的新方向.ppt》由会员分享，可在线阅读，更多相关《第10章密码学的新方向.ppt（62页珍藏版）》请在优知文库上搜索。

1、第10章 密码学的新方向10.1 量子密码学n量子密码学是密码学上的一大分支。当前广泛使用的密码系统通常是利用数学难题来设计密码协议和算法，利用求解数学难题的困难性来保障密码方案的安全性。而量子密码则不同，它是利用求解物理问题的困难性或不可能性来保障方案的安全性。量子密码学n量子密码的主要特点是对外界任何扰动的可检测性和易于实现的无条件安全性。这些特征依赖于量子系统的内在属性：测不准性和不可克隆性。扰动的可检测性的物理基础是Heisenberg测不准原理，而无条件安全性的物理基础是量子不可克隆定理。n在量子力学中，任何两组不可同时测量的物理量都是共轭的，满足互补性。Heisenberg测不准原

2、理指的是在进行测量时，对任何一个物理量的测量都不可避免地对另一物理量产生干扰，这就使得通信双方能够检测到信息是否被窃听，这一性质使通信双方无须事先交换密钥即可进行保密通信。1982年，Wootters和Zurek在Nature杂志上发表了一篇题为单量子态不可被克隆的文章，他们在文章中提出了著名的量子不可克隆定理，即：在量子力学中，不可能实现对一个未知量子态的精确复制，使得每个复制态与初始量子态完全相同。这一特性使得窃听者不可能将量子信道上传输的信息进行复制。Bennett-Brassard量子密钥分配协议n通过对Bennett和Brassard提出的量子密钥分配协议（BB84），可进一步地了解

3、量子密码。nBB84协议是量子密码中提出的第一个密钥分配协议，是由Bennett和Brassard于1984年提出的，发表在IEEE的国际计算机、系统和符号处理（International Conference on Computers，Systems and Signal Processing）会议上。BB84协议以量子互补性为基础，协议实现简单，具有无条件安全性。n光子在传导时会在某个方向上发生振荡，上、下、左、右，多数则是按照某个角度振荡。正常的太阳光是非极化的，在每一个方向上都有光子振荡。当大量的光子在同一方向振荡时，它们是极化的（polarized），极化滤波器只允许在同方向极化的光

4、子通过，而其余方向则不能通过。例如，水平极化滤波器只允许水平方向极化的光子通过，将计划滤波器旋转，则只允许垂直方向极化的光子通过。光子的偏振有两个基，一是水平线和垂直线组成的基，称为线偏振光子，另一个是左对角线和右对角线组成的基，称为圆偏振光子。如果一个光子脉冲在一个给定的基上被极化后发送，而接收方在同一组基上测量，则可得到极化强度。反之，若接收方使用的是一个错误的基，则得到的是随机结果。n使用这个特性可通过如下步骤来共享密钥：n（1）Alice将一串光子脉冲发送给Bob，其中每一个脉冲都随机的在四个方向被极化：水平线、垂直线、左对角线和右对角线。例如，Alice向Bob发送的是n n（2）B

5、ob随机设置极化检测器的基来检测接收到的光子脉冲，例如Bob如下设置：nn则Bob获得的结果为n n（3）Bob通过公共信道告诉Alice 他对极化检测器的设置。Alice则告诉Bob哪些设置是正确的。在上面的例子当中，第2、6、7、9位设置是正确的。n（4）双方只保存测量基相同的测量结果，放弃测量基不一致的测量结果。在上面的例子中，它们保存：nn然后使用预先设置的代码，将所保存的测量结果转变为比特。n利用上述方法，可共享足够多的比特，不过Bob正确设置检测器的概率为50%，因此，要共享比特密钥，Alice必须发送个光子脉冲。n（5）Bob随机选取少量比特与Alice 进行比较，经Alice

6、确认无误，断定无人窃听后剩下的比特串就可留下建立为密码本。n在光子的四个偏振态中，水平偏振和垂直偏振是线偏振态，左对角线偏振和右对角线偏振是圆偏振态。线偏振和圆偏振是共轭态，满足测不准原理。根据测不准原理，对线偏振光子的测量结果越精确，意味着对圆偏振光子的测量结果越不精确。因此，任何攻击者的测量必定会带来对原来量子比特的扰动，而合法通信者可以根据测不准原理检测出该扰动，从而检测出窃听是否存在与否。另外，线偏振态和圆偏振态是非正交的，因此它们是不可区分的，攻击者不可能精确地测量所截获的每一个量子态，因而窃听者不可能采取穷搜索的攻击方法。量子测不准原理和量子不可克隆定理保证了BB84协议的无条件安

7、全。量子密码的应用与进展n量子密码起初的主要目标是为了解决密钥管理问题。因此，量子密码的研究主要集中在量子密钥的分配方面。但是经过三十余年的研究，逐渐形成了系统的量子密码理论体系，内容涉及量子密钥管理、量子加密、量子认证、量子密码信息理论、量子密码分析等方面。可以说，经典密码能发挥作用的领域，量子密码几乎都能起到相应的作用。随着计算技术和量子芯片技术的发展，量子密码有可能像经典密码一样，既可以通过硬件来实现，也可以通过软件来实现。n量子密码不仅在理论上形成了自身的框架体系，在技术上也取得了飞速的发展。Bennett等人于1989年首次用实验验证了BB84协议。然而，量子信道仅32cm。在长距离

8、上实现其系统出现的问题是光缆瓦解了光的极化，因此，光子需要通过一个真空直管发送。20世纪90年代以来，世界各国的科学家对量子密码通信的研究出现了迅猛发展，并取得很大成功，瑞士University of Geneva 在原有光纤系统中已建立22.8km 量子保密通信线路并投入了实用；英国BT实验室已实现在常规光缆线路上量子密码通信传输距离达55km；美国Los Alamos 实验室已成功实现48km量子密钥系统运行两年，2000年，他们在自由空间中使用QKD 系统成功实现传输距离为1.6km。2007年，一个由奥地利、英国、德国研究人员组成的小组在量子通信研究中创下了通信距离达144km的最新纪

9、录，并认为利用这种方法有望在未来通过卫星网络实现信息的太空绝密传输。n我国在量子密码实现方面也做了大量的工作。2007年1月，由清华大学、中国科学技术大学等单位组成的联合研究团队最近在远距离量子通信研究上取得重大突破。他们采用诱骗信号方法，在国际上率先实现了以弱激光为光源、绝对安全距离大于100km的量子密钥分发。这是我国科学家继五光子纠缠态制备与操纵、自由空间量子纠缠分发以及复合体系量子态隐形传输等重要研究成果后，在量子通信实验领域取得的又一国际领先的研究成果。2007年4月2日上午，中国科学技术大学在北京举行新闻发布会，正式向外界透露：由中国科学技术大学教授、中科院院士郭光灿领导的中科院量

10、子信息重点实验室，利用自主创新的量子路由器，目前在北京网通公司商用通信网络上率先完成四用户量子密码通信网络的测试运行并确保了网络通信的安全。据悉，这是迄今为止国际公开报道的唯一无中转、可同时、任意互通的量子密码通信网络，标志着量子保密通信技术从点对点方式向网络化迈出关键性的一步。2007年3月，该课题组在北京网通的商用光纤线路上进行多用户的测试运行，四个用户节点的分布构成方式为北京市朝阳区的望京东小口南沙滩望京，路由器位于东城区的东皇城根地区，用户之间最短距离约32km，最长约42.6km。测试系统演示了一对三和任意两点互通的量子密钥分配，并在对原始密钥进行纠错和提纯的基础上，完成了加密的多媒

11、体通信实验 10.2 多变量公钥密码n近年来，量子计算机的发展对于基于数论问题的密码体制的安全性造成了本质威胁。1994年，Peter Shor发现了一种在量子计算机上多项式时间运行的整数因子分解算法。这意味着一旦人们能建造出实用的量子计算机，那么RSA体制就完全不再安全。这种威胁应当严肃对待，因为目前已经做了大量研制量子计算机的工作，而且在2001年已经构造出了示例性的量子计算机。该计算机利用Shor的算法成功地分解了15。因此有必要去寻找更高效、更安全的公钥密码系统来替代RSA密码系统。n多变量公钥密码系统被认为是这样一种有希望的选择。近年来，多变量公钥密码逐渐成为密码学研究的一个热点。多

12、变量公钥密码系统的安全性建立在求解有限域上随机多变量多项式方程组是NP-困难问题的论断之上。由于运算都是在小的有限域上进行，所以多变量公钥密码体制中的计算速度非常快。到目前为止，已经构造出很多新的多变量公钥密码体制，这些密码体制当中有一些非常适用于诸如无线传感器网络和动态 RFID标签等计算能力有限的设备。2003年，一个多变量签名体制SFLASH已经被欧洲NESSIE密码计划接受用于低耗智能卡的推荐算法。多变量公钥密码体制的一般形式n多变量公钥密码（Multivariate Public Key Cryptosystem，MPKC）的一般形式如下：令k是一个有限域，n和m是正整数，L1和L2

13、分别是kn和km上的随机选取的可逆仿射变换。取映射为一个从kn到km的容易求逆的非线性映射。令n其中F是一个从kn到km的映射。它总可以被表示成有限域k上m个n元多项式，其最高次数等于的次数。11211(,)(,)(,)mnnYyyF xxLL xxn在多变量公钥密码系统中，F的表达式为公钥，它是一组多变量多项式，而私钥设为L1和L2的表达式。多变量公钥密码设计的关键在于构造映射，后者称为多变量密码体制的中心映射。的表达式可以公开，也可以保密。为了节省公钥多项式的存储，中心映射和公钥多项式通常选取为最简单的非线性函数即二次函数。n作为加密体制，一般要求 ，而作为签名体制一般有 。n作为加密体制

14、加密消息 ，需要计算 。而解密密文 ，则需要通过依次求解映射L2、和L1的逆来求解如下方程组：n （1）n作为签名体制签署文件 ，则需要找到方程（1）的解 。验证一个签名是否合法需要检查下式是否成立：mnmn1(,)nXxx()F X1(,)mYyy1(,)nF xxY1(,)mYyy1(,)nXxx1(,)nF xxYMI多变量公钥密码体制nMI加密体制也称为，是1988年由Matsumoto 和 Imai提出的。它是第一个使用“小域大域”思想来构造多变量公钥密码体制的方法。它是多变量公钥密码学发展史上的一座里程碑，是第一个实用的多变量公钥密码体制，它为这个领域带来了一种全新的数学思想，并且

15、得到广泛的研究和推广。MI 加密体制的简化版本 签名体制n公钥：域的结构和多项式组。n私钥与MI加密体制一样。n签名过程如下：n要签名的文件（或它的Hash值）为。合法用户要生成签名首先随机选择个元素，将这些值与合在一起得到，然后类似于解密过程，利用私钥计算n即为文件的签名。n验证过程如下：n在接收到文件和相应的签名后，验证者检查下式是否成立：n如果等式成立，则签名合法；反之，则拒绝。彩虹：多层油醋签名体制n原始的油醋体制是Patarin在1997年受到线性化方程的启发构造出来的签名体制。这个体制的关键是应用了一种所谓的油醋多项式。令k是一个含q个元素的有限域。n定义1 （油醋多项式）n设f

16、kx1,xo,1,，v，我们称如下形式的多项式为油醋多项式：n其中aij,bij,ci,dj,e k,x1,xo称为油变量，1,v称为醋变量。111111ovvvovi jiji jijiijjijijijfa x xb x xc xd xe n注意在油醋多项式中，若给定醋变量的值，那么油醋多项式就转变为关于油变量的一次多项式。油醋签名体制的中心映射是由一组油醋多项式构成的。生成签名时只需随机选取一组醋变量的值，然后解一个关于油变量的线性方程组。n油醋签名体制分为三类：平衡的油醋体制、不平衡的油醋体制以及彩虹体制。在平衡的油醋体制中，油变量和醋变量的个数相等。但平衡的油醋体制并不安全，Kipnis和Shamir在1998年利用与二次多项式相关的矩阵方法有效地构造与原私钥等价的密钥，并且由此可以伪造合法签名。随即，Kipnis等人在1999年提出了不平衡油醋体制。在不平衡油醋体制中，醋变量的个数大于油变量的个数。彩虹体制是一种多层的油醋体制，即每一层都是油醋多项式，而且该层的所有变量都是下一层的醋变量。与彩虹体制具有类似层级结构的还有TTS和TRMS，尽管它们是通过不同的思想（三角形构造