计算机非对称密钥.

第四章计算机非对称密钥加密算法•4.1非对称密钥加密简史•4.2非对称密钥加密概述•4.3RSA算法•4.4对称与非对称密钥加密•4.5背包算法•4.6数字签名•4.7其他算法4.1非对称密钥加密简史•对称密钥加密快速而高效，但也存在很大的缺点，就是密钥交换问题。加密消息的发送方与接收方要在对称密钥加密中使用相同密钥，协定密钥时很容易被别人知道。非对称密钥加密可以解决这一问题，每个通信方要用两个密钥构成密钥对：一个是私钥，自己保密；一个是公钥，是公开的。•20世纪70年代中期，斯坦福大学的学生WhifieldDiffie和他的导师MartinHellman开始考虑密钥交换问题。经过一些研究和复杂的数学分析他们发明了非对称密钥加密思想。许多专家认为，这个发明是密码学史上的一次真正的革命性概念。因此，WhifieldDiffie与MartinHellman可以称为非对称密钥加密之父。•但是，关于非对称密钥加密的荣誉归谁的问题，存在许多争议。有人认为，英国通信电子安全小组（CSEG）的JamesEllis早在20世纪60年代就提出了非对称密钥加密的思想，但是JamesEllis没有提出可行的算法。后来CliffordCocks提出了可行的算法。第二年，CSEG的另一个成员Williamson开发了非对称密钥加密算法。但是，由于CSEG是个秘密机构，因此这些成果没有发表，是他们无法得到应有的荣誉。4.2非对称密钥加密概述•非对称密钥加密（AsymmeticKeyCryptography)也称公钥加密（PublicKeyCryptography)，它使用两个密钥，构成一对，一个用于加密，一个用于解密，其他密钥都无法解密这个消息，包括用于加密的密钥，这个机制的妙处在于每个通信方只要一对密钥，就可以和多个其他方通信。一旦取得密钥之后，就可以和任何其他人通信。•两个密钥中，一个是公钥，一个是私钥。私钥是保密的，不能向别人披露，但是公钥是公开的，可以向任何人公布。•假设A要向B发送消息，而不担心其安全性。则A和B都要有公钥和私钥。•A的私钥保密•B的私钥保密•A要将公钥告诉B•B要将公钥告诉A•非对称密钥加密的工作原理如下：•(1)A要给B发消息时，A用B的公钥加密消息，因为A知道B的公钥。•(2)A将这个消息发给B（已经用B的公钥加密消息）。•(3)B用自己的私钥解密A发过来的消息。注意：只有B知道自己的私钥，另外，这个消息只能用B的私钥解密，而不能用别的密钥解密。因此，即使别人截获这个消息，不知道B的私钥，也无法看懂这个消息。明文密文密文发送方A接收方B明文公共网络用B的公钥加密用B的私钥解密图4.1非对称密钥加密•同样，B要向A发送消息时，过程正好相反，B用A的公钥加密消息，这个消息只能用A的私钥解密。•我们考虑一个非对称密钥加密的实际情形。银行具有公钥/私钥对。银行向所有客户发布公钥，客户用银行公钥加密消息之后再发给银行。银行可以用自己的私钥解密所有这些加密消息，只有银行知道这个私钥，才能解密这些消息。如图4.2所示。客户A客户B客户C银行的公钥银行的公钥银行的公钥银行银行的私钥图4.2银行使用公钥/私钥对主要算法•RSA、ElGamal（厄格玛尔）、背包算法、Rabin(勒宾的加密法可以说是RSA方法的特例)、Diffie-Hellman(D-H)密钥交换协议中的公钥加密算法、EllipticCurveCryptography（ECC,椭圆曲线加密算法）。使用最广泛的是RSA算法（由发明者Rivest、Shmir和Adleman姓氏首字母缩写而来）是著名的公开金钥加密算法，ElGamal是另一种常用的非对称加密算法。4.3RSA算法•4.3.1概述•RSA公钥加密算法是1977年由罗纳德.李维斯特（RonRivest）、阿迪·萨莫尔（AdiShamir）和伦纳德·阿德曼（LeonardAdleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。•RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。•今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。•RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。•素数：就是只能被1和本身整除的数。RSA中的公钥和私钥基于大素数(100位以上），算法本身要比对称加密算法简单，但实际难度在于RSA选择和生成公钥和私钥。如何生成公钥和私钥，如何进行加密和解密：(1)选择两个大素数P和Q。(2)计算N=PxQ。(3)选择一个公钥（即加密密钥）E，使其不是（P-1）与（Q-1）的因子。(4)选择私钥（即解密密钥）D，满足下列条件：（DxE）mod（P-1）x（Q-1）=1•(5)加密时，从明文PT计算密文CT如下：•(6)将密文CT发送给接收方。•(7)解密时，从密文CT计算明文PT如下：modECTPTNmodDPTCTN4.3.2RSA示例•(1)取P=7，Q=17。•(2)因此，N=PxQ=119。•(3)（P-1）x（Q-1）=6x16=96，96的因子为2、2、2、2、2和3，因此公钥E不能有2和3的因子。我们可以选择5。•(4)选择一个私钥，使（DxE）mod（P-1）x（Q-1）=1。可以选择77，因为（5x77）mod96=385mod96=1,满足条件。•根据这些值，考虑下图的加密与解密过程。A是发送方，B是接收方。可以用编码机制编码字母：•A=1，B=2,···，Z=26。假设用这个机制编码字母，那么B的公钥为5（A和B都知道），B的私钥为77（只有B知道）。如图4.5。•对RSA算法的攻击方式可能有以下四种方式：1、穷举攻击：这种方式视图穷举所有可能的私钥。2、数学攻击：有多种数学攻击方法，它们的实质都是试图把大数因子分解为两个素数的乘积。3、计时攻击：这种算法依赖于解密算法的运行时间。4、选择密文攻击：这种类型的攻击试图发现算法的规则。4.4对称与非对称密钥加密•4.4.1对称与非对称密钥加密比较•这两种密码算法的不同之处主要有如下几个方面：•1、加解密时采用的密钥的差异：对称密钥加解密使用的同一个密钥；而非对称密钥算法加解密使用的不同密钥。•2、算法上区别：•①对称密钥算法采用的分组加密技术，即将待处理的明文按照固定长度分组，并对分组利用密钥进行数次的迭代编码，最终得到密文。解密的处理同样，在固定长度密钥控制下，以一个分组为单位进行数次迭代解码，得到明文。而非对称密钥算法采用一种特殊的数学函数，单向陷门函数，即从一个方向求值是容易的，而其逆向计算却很困难，或者说是计算不可行的。加密时对明文利用公钥进行加密变换，得到密文。解密时对密文利用私钥进行解密变换，得到明文。•②对称密钥算法具有加密处理简单，加解密速度快，密钥较短，发展历史悠久等特点，非对称密钥算法具有加解密速度慢的特点，密钥尺寸大，发展历史较短等特点。3、密钥管理安全性的区别：•对称密钥算法由于其算法是公开的，其保密性取决于对密钥的保密。由于加解密双方采用的密钥是相同的，因此密钥的分发、更换困难。而非对称密钥算法由于密钥已事先分配，无需在通信过程中传输密钥，安全性大大提高，也解决了密钥管理问题。•4、安全性：•对称密钥算法由于其算法是公开的，其安全性依赖于分组的长度和密钥的长度，常的攻击方法包括：穷举密钥搜索法，字典攻击、查表攻击，差分密码分析，线性密码分析，其中最有效的当属差分密码分析，它通过分析明文对密文对的差值的影响来恢复某些密钥比特。非对称密钥算法安全性建立在所采用单向函数的难解性上，如椭圆曲线密码算法，许多密码专家认为它是指数级的难度，从已知求解算法看，160bit的椭圆曲线密码算法安全性相当于1024bitRSA算法。•4.4.2对称与非对称密钥的结合•对称密钥与非对称密钥各有所长，也都有需要改进的问题。如果能将这两种加密机制组合起来，则能达到两全其美，不失各自的优点。可以达到以下目标：•（1）解决方案完全安全。•（2）加密/解密速度要快。•（3）生成的密文长度要小。•（4）伸缩性要好，不能引入更多的复杂性。•（5）要解决密钥发布问题。•举个例子，假设A是发送方，B是接收方。•（1）A利用标准对称加密算法加密明文消息PT，产生密文CT，A加密时使用的密钥K1称为一次性对称密钥，用完即放弃。发送方A明文对称密钥加密算法密文对称密钥K1•（2）A用B的公钥K2加密第一步的一次性密钥K1,这个过程称为对称密钥的密钥包装。对称密钥K1B的公钥K2•（3）A把密文CT和加密的对称密钥一起放在数字信封中。•（4）A将数字信封（包含密文CT和用B的公钥包装起来的对称密钥K1）用网络发送给B。•（5）B接收并打开数字信封，收到密文CT和用B的公钥包装起来的对称密钥K1。密文•（6）B用A所用的非对称密钥算法和自己的私钥K3解密逻辑箱，其中包含B的公钥包装的非对称密钥K1。即得到一次性对称密钥K1。对称密钥K1B的私钥K3B的公钥K2锁住的•（7）B用A所用的对称密钥K1解密密文CT，得到明文PT。接收方B对称密钥解密算法密文明文对称密钥K14.5背包算法•背包问题是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。•假设已知M1，M2，···，Mn以及总和S，试求出bi，使得：S=b1M1+b2M2+···+bnMn•每个bi可以取0或1:1表示把该项目放进背包，0表示不把该项目放进背包。•与堆中项目数长度相同的明文块选择背包中的东西，密文得到的是和。•例如：如果背包为1、7、8、12、14、20，则下图显示了明文和得到的密文。•明文011011111000010110•背包1、7、8、12、14、20•密文7+8+14+20=49•1+7+8=16•7+12+14=334.7其他算法•4.7.1椭圆加密算法•RSA是公钥加密技术中最常用的加密和数字签名算法但是随着RSA的密钥长度的不断增加给RSA带来了很大开销。另一个加密技术越来越普及，即椭圆曲线加密法（ECC）。•设椭圆曲线E上有点P，现在生成一个随机数d。假设Q=dxP。E、P、Q是公开的，而求d则不容易，这个是椭圆曲线的离散对数问题。只要曲线足够大，就很难求d。因此，E、P、Q构成公钥，而d是私钥。•椭圆曲线算法与RSA算法的比较•椭圆曲线公钥系统是代替RSA的强有力的竞争者。椭圆曲线加密方法与RSA方法相比，有以下的优点：•（1）安全性能更高如160位ECC与1024位RSA、DSA有相同的安全强度。•（2）计算量小，处理速度快在私钥的处理速度上（解密和签名），ECC远比RSA、DSA快得多。•（3）存储空间占用小ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多，所以占用的存储空间小得多。•（4）带宽要求低使得ECC具有广泛的应用前景。•ECC的这些特点使它必将取代RSA，成为通用的公钥加密算法。比如SET协议的制定者已把它作为下一代SET协议中缺省的公钥密码算法。•4.7.2ElGamal•ElGamal算法，是一种较为常见的加密算法，它是基于1984年提出的公钥密码体制和椭圆曲线加密体系。既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。在加密