信息安全原理与实践-第二版04-公开密钥加密课件.ppt

1、1Information Security:Principles and Practice,2nd Edition美Mark Stamp著张 戈译第4章 公开密钥加密24.1 引言 公开密钥加密技术 单向陷门函数 公开密钥 私有密钥 数字签名 公开密钥加密体系 椭圆曲线加密方案34.2 背包加密方案Merkle-Hellman背包加密系统基于一个数学问题，该问题往往被看成NP完全问题。定定义：义：给定一个集合，共包含n个权重值，分别标识为：W0,W1,Wn-1，以及期望的和S，要求找到a0,a1,an-1，其中每一个ai0，1使得等式S=a0W0+a1W1+.+a n-1Wn-1,能够成立。例

2、例子：子：假设权重值为85,13,9,7,47,27,99,86 期望的和S=172 对于这个问题存在一个解决方案：a=(a0,a1,a2,a3,a4,a5,a6,a7)=(11001100)因为85+13+47+27=1724 超递增的背包问题当将权重值从小到大排列起来时，每一个权重值都大于前面所有权重值相加的和。-相对容易解决！例子：权重值集合为：3,6,11,25,46,95,200,411期望的和S=309我们只需从最大权重值开始，逐步向最小的权重值进行计算，就有望在线性时间内恢复出ai。5因为S200，那么一定有a6=1，因为剩余所有权重值的和要小于200。接着计算S=S-200=1

3、09，这是新的目标和值。因为S95，我们得到a5=1。然后再计算S=109-95=14。继续如法炮制，就得到了最终结果a=10100110。我们能够轻松地证实这个问题获得了解决，因为3+11+95+200=309。构造背包加密系统的流程(1)生成一个超递增的背包。(2)将这个超递增的背包转换为常规的背包。(3)公钥便是常规背包。(4)私钥就是超递增的背包以及相关的转换因子。6 实例（1）我们选择如下超递增的背包：(2,3,7,14,30,57,120,251)（2）为了将这个超递增的背包转换成常规背包，我们必须选择乘数m和模数n，m和n必须是互素的，且n要大于超递增背包中所有元素值的和。假设选

4、取的乘数m=41，模数n=491。通过模乘法运算，根据超递增背包计算常规背包，得到：（3）公钥就是这个常规背包公钥公钥：(82,123,287,83,248,373,10,471)（4）私钥就是这个超递增背包，加上转换因子的乘法逆，如m1 mod n。对于这个实例，计算结果如下私钥私钥：(2,3,7,14,30,57,120,251)以及41-1 mod 491=127如果Alice想要加密消息M=10010110并发送给Bob，她就利用消息中值为1的二进制位，据此来选择常规背包中的元素，将这些元素相加求和就得到了对应的密文。Alice执行计算：C=82+83+373+10=548要想解密这个

5、密文，Bob使用他的私钥执行如下计算，得到：Cm-1 mod n=54812 mod 491=193然后Bob针对值193求解超递增背包问题。因为Bob拥有私钥，所以要从中恢复出明文是比较容易的。最后，明文的二进制表示为M=10010110，其换算成十进制是M=150。8总结：在背包加密系统里，陷门函数存在于运用模运算将超递增背包问题转换为常规背包问题时，因为该转换因子对于攻击者来说是无法得到的。该函数的单向特性在于一个事实：使用常规背包实施加密非常容易，但是在没有私钥的情况下，要想解密显然是非常困难的。当然，有了私钥，我们就能够将问题转换为超递增背包问题，解决起来就容易了。背包问题看起来确实

6、是对症下药了。首先，构造包含公钥和私钥的密钥对是相当容易的。而且，给定了公钥，实施加密是非常容易的，而了解了私钥则会使解密过程非常容易。最后，在没有私钥的情况下，攻击者就将不得不去解决NP完全问题了。可惜这个精巧的背包加密系统是不安全的。该方案于1983年被Shamir使用一台Apple II计算机破解。该攻击依赖于一种称为格基规约的技术。问题的根本在于该方案中从超递增背包问题派生出的所谓“常规背包问题”并不是真正的常规背包问题事实上，它是一种非常特殊的高度结构化的背包案例，而格基规约攻击能够利用这种结构的特点比较容易地恢复出明文(可以较高的概率完成)。94.3 RSA RSA体制的命名来自于

7、它的三个公认的发明者：Rivest、Shamir和Adleman。10为了生成RSA算法的公钥和私钥的密钥对，先要选择两个大素数p和q：1.计算出它们的乘积N=pq。2.选择与乘积(p-1)(q-1)互素的数e。3.计算出数e的模(p-1)(q-1)的乘法逆元素，命名该逆元素为d。这些数值满足公式ed=1 mod(p-1)(q-1)。数N是模数，e是加密指数，而d是解密指数。RSA密钥对的组成如下：公钥：(N,e)私钥：d加密：加密：将明文文本消息M视为一个数，对其按指数e求幂并模NC=M e mod N解密：解密：要解密要解密C，求幂模运算使用解密指数d完成相应的操作过程M=C d mod

8、N RSA加密体制真的确实有效吗？给定C=M e mod N，我们必须证明如下等式：M=C d mod N=M ed mod N 欧拉定理欧拉定理：如果数x与数n互素，那么x(n)=1 mod n。再回顾之前对e和d的选取符合等式：ed=1 mod(p-1)(q-1)，而且N=pq，这意味着：(N)=(p-1)(q-1)这两个事实结合在一起，就意味着下面的等式成立：ed-1=k(N)11这就证实了RSA体制的解密指数确实解密了密文C。4.3.1教科书式的RSA体制范例12AliceBob生成Alice的密钥对：1.选择两个“大的”素数：p=11，q=3。模数就是N=pq=33，并且可以计算出(

9、p-1)(q-1)=20。2.选取加密指数为e=3。3.计算相应的解密指数d=7，因为ed=37=1 mod 20。Alice的公钥：(N,e)=(33,3)Alice的私钥：d=7假定Bob想要发送一条消息M=15 给Alice。Bob先查找Alice的公钥(N,e)=(33,3)，再计算密文 C=M e mod N=153 =3375=9 mod 33 =9Alice使用她的私钥d=7进行解密计算：M=C d mod N=97=4,782,969 =144,93833+15 =15 mod 33 =15 存在的问题 所谓“大的”素数其实并不大，对Trudy来说分解这个模数将是小菜一碟。在现

10、实世界中，模数N典型的大小通常至少是1024位，而长度为2048位或更大的模数值也是常常会用到的。可能遭受前向检索攻击。134.3.2 重复平方方法重复平方方法通过每次构建一个二进制位的方式来生成指数并完成计算。在每个步骤中，我们将当前的指数值乘以2，如果其二进制扩展形式在相应的位置有值1，我们就还要对指数计算的结果再加上1。例子：计算520。指数20以二进制形式表示为10100，指数10100可以一次一位地被构建出来，从高阶二进制位开始，如下：(0,1,10,101,1010,10100)=(0,1,2,5,10,20)现在计算520，重复平方方法的执行过程如下：14So easy！4.3.

11、3 加速RSA加密体制另外一个可用于加速RSA加密体制的技巧是，对于所有用户使用同一加密指数e。而这并不会在任何方面削弱RSA加密体制的强度。通常加密指数的合适选择是e=3。选择这个e值，每一次公钥加密仅仅需要两次乘法运算。不过，私钥的运算操作仍然代价高昂。如果多个用户都使用e=3作为他们的加密指数，那么还存在另一种类型的立方根攻击。如果对于同一个消息M，使用三个不同用户的公钥分别加密，生成的密文比如是C0、C1和C2，那么中国剩余定理可用于恢复明文消息M。在实践中，这也很容易避免，方法就是对每个消息M随机附加填充信息，或者在每个消息M中增加一些用户指定的信息，这样每个消息实际上就会互不相同了

12、。另一个流行的通用加密指数是e=216+1。选取这个e值，每个加密运算仅需要执行17个重复平方算法的步骤。e=216+1的另一个优势是，在运用中国剩余定理的攻击者成功破解消息密文之前，同样的加密消息密文必须已经先行发送给e=216+1个用户。154.4 Diffie-Hellman密钥交换算法Diffie-Hellman密钥交换算法，或简称为DH，是由英国政府通信总部(GCHQ)的Malcolm Williamson所发明，其后不久，该算法又被它的命名者Whitfield Diffie和Martin Hellman独立地再次发明。这里讨论的Diffie-Hellman算法版本是密钥交换算法，因

13、为它仅仅能够用于建立共享的秘密。DH算法的安全性依赖于离散对数问题的计算难度。假设给定g以及x=gk。那么，要想确定k，就需要计算对数logg(x)。16 DH算法的数学构造设定p为素数，并假定g是生成器，即对于任何的x1,2,.,p-1，都存在指数n，使得x=gn mod p。素数p和生成器g是公开的。对于实际的密钥交换过程，Alice随机地选择秘密的指数a，Bob随机地选择秘密的指数b。Alice计算ga mod p，并将结果发送给Bob，而Bob计算gb mod p，也将结果发送给Alice。Alice执行如下计算：(gb)a mod p=gab mod pBob执行如下计算：(ga)b

14、 mod p=gab mod p最后，gab mod p就是共享的秘密，其典型的用途是作为对称密钥。17DH密钥交换攻击者Trudy能够看到ga mod p 和 gb mod p，而且看起来她距离那个共享秘密gab mod p也非常接近。但是：gagb=ga+bgab mod p显然，Trudy需要找到a或b，看起来这就需要她去解决一个困难的离散对数问题。18DH算法容易遭受中间人攻击（简称为MiM攻击）Trudy将自己置于Alice和Bob之间，截获从Alice发送给Bob的消息，同样也截获从Bob发送给Alice的消息。Trudy如此部署，将使DH密钥交换很容易地就被彻底破坏了。在这个过程

15、中，Trudy建立共享的秘密，比方说，和Alice共享gat mod p，和Bob共享另一个秘密gbt mod p。无论是Alice还是Bob，都不会觉察到这其中有任何问题，于是，Trudy就能够读到或改写Alice和Bob之间传递的任何消息了。19 预防中间人攻击的方法 使用共享对称密钥对DH密钥交换过程实施加密。使用公钥对DH密钥交换过程实施加密。使用私钥对DH密钥交换过程中的值进行数字签名。204.5 椭圆曲线加密 椭圆曲线加密体制(Elliptic Curve Cryptography，ECC)提供了另一个“实施复杂难解的数学操作”的方法。优势优势：要获得同样等级的安全性，需要的二进制

16、位数较少 缺点缺点：椭圆曲线体制的数学计算更加复杂，因此，椭圆曲线体制中的每个数学操作的代价都相对而言更加昂贵。典型的椭圆曲线图214.5.1椭圆曲线的数学原理从加密技术的角度来说，我们希望处理的是离散的点集。这可以通过在通用椭圆曲线的计算等式上执行“mod p”运算来轻松地实现。y2=x3+ax+b(mod p)例子：y2=x3+2x+3(mod 5)对于x的所有取值，逐个选取并计算相应的y值(一个或多个值)。因为我们是基于模数5实施运算，所以我们只需考虑x=0,1,2,3,4的情况。在这个例子中，我们最后获得如下这些点：x=0 y2=3 no solution mod 5x=1 y2=6=

17、1 y=1,4 mod 5x=2 y2=15=0 y=0 mod 5x=3 y2=36=1 y=1,4 mod 5x=4 y2=75=0 y=0 mod 5y2=x3+2x+3(mod 5)曲线对应的点为：(1,1)(1,4)(2,0)(3,1)(3,4)(4,0)和22在椭圆曲线上增加两个点的代数计算方法的说明为了确定椭圆曲线上的点P3=(1,4)+(3,1)，首先进行如下计算：m=(1-4)/(3-1)=-32-1=-33=1 mod 5然后计算x3=12-1-3=-3=2 mod 5y3=1(1-2)-4=-5=0 mod 5这样，在椭圆曲线y2=x3+2x+3(mod 5)上，就得到(

18、1,4)+(3,1)=(2,0)。请注意这个和值，点(2,0)也位于该椭圆曲线上234.5.2 基于椭圆曲线的Diffie-Hellman密钥交换方案探讨Diffie-Hellman密钥交换方案的椭圆曲线版本，其公开信息包括一条椭圆曲线及该曲线上的一点。例子：对于椭圆曲线y2=x3+11x+b(mod 167)，暂时不给定b的值。我们选择任何一点(x,y)以及b的值，使得这一点位于最终的椭圆曲线之上。我们选择了(x,y)=(2,7)。将x=2和y=7代入曲线中，就可以确定b=19。于是，该方案的公开信息就是y2=x3+11x+19(mod 167)和 点(2,7)Alice和Bob每人都必须随

19、机选择他们自己的秘密乘法因子。24Alice和Bob就已经建立了共享的秘密，共享秘密可用作对称密钥。25Alice执行如下计算：A(2,7)=15(2,7)=(102,88)并将她的计算结果发送给BobBob执行如下计算：B(2,7)=22(2,7)=(9,43)也将他的计算结果发送给Alice假设假设Alice选择了选择了A=15，而，而Bob选择了选择了B=22。Alice将从Bob那接收的值乘以她自己的秘密乘法因子A：A(9,43)=15(9,43)=(131,140)Bob执行类似计算：B(102,88)=22(102,88)=(131,140)Diffie-Hellman密钥交换方案

20、的椭圆曲线版本之所以能够有效工作，全在于ABP=BAP，其中A和B分别是秘密乘法因子，而P是椭圆曲线上指定的点。这个方案的安全性依赖于如下事实：即使Trudy能够看到AP和BP，但是很显然，她也必须找到A或B，然后才能够确定共享秘密。据目前所知，这个Diffie-Hellman密钥交换方案的椭圆曲线版本和常规的Diffie-Hellman密钥交换方案同样难于破解。事实上，对于给定长度的二进制位数，椭圆曲线版本的Diffie-Hellman密钥交换方案要难破解得多，而且它使得我们可以使用更小的数值获得同等级别的安全性。因为数值越小，其算法的效率越高。264.5.3 现实中的椭圆曲线加密案例设定p

21、=564538252084441556247016902735257a=321094768129147601892514872825668b=430782315140218274262276694323197考虑椭圆曲线E：y2=x3+ax+b(mod p)，我们令P点为(97339010987059066523156133908935,149670372846169285760682371978898)该点位于椭圆曲线E之上，再令k=281183840311601949668207954530684。然后，将P点与自身相加k次，表示为kP，于是我们得到点(446467696974058610

22、57630861884284,522968098895785888047540374779097)这个点也位于椭圆曲线E上。274.6 公开密钥体制的表示方法对于公开密钥加密体制中的加密、解密和签名，我们将采用下面的表示方法：使用Alice的公钥加密消息M：C=MAlice 使用Alice的私钥解密密文消息C：M=CAlice Alice签名的消息M的表示方法：S=MAlice花括号表示使用公钥的操作，方括号代表使用私钥的操作，下标用来表明使用谁的密钥。既然公钥操作和私钥操作是互相消解的，于是可以得到如下等式：MAliceAlice=MAliceAlice=M公钥是公开的，因而任何人都能够去计

23、算MAlice。私钥是私密的，所以只有Alice能够执行计算CAlice或MAlice。这意味着任何人都能够为Alice加密消息，但是仅有Alice本人能够解密相应密文。284.7 公开密钥加密体制的应用能够使用对称密钥加密方案完成的任何事情，也都可以通过公开密钥加密方案来完成，只不过要慢一些，包括保护数据的机密性，类似的应用形式还有：通过不安全的通道传送数据，或者在不安全的媒介上安全地存储数据等。此外，我们还能够将公开密钥加密体制用于保护数据的完整性数字签名就能够起到对称密钥加密体制中消息认证码(MAC)的作用。相比对称密钥加密体制，公开密钥加密体制提供了两大主要优点。第一个主要优点是，基于

24、公开密钥加密体制，我们不需要事先建立共享的密钥。第二个主要优点是，数字签名提供了完整性和不可否认性。294.7.1真实世界中的机密性相比公开密钥加密技术，对称密钥加密技术的主要优势是效率。我们是否能够既拥有对称密钥加密方案的效率，又不必提供事先的预共享密钥呢？要得到这样超级完美的结果，方法就是构建混合加密系统，其中公开密钥加密体制用于建立对称密钥，将这个生成的对称密钥用于加密数据。304.7.2 数字签名和不可否认性 不可否认性 假设Alice从她最中意的股票商Bob那里订购了100股股票。为了确保她的订单的完整性，Alice使用共享的对称密钥KAB计算消息认证码MAC。现在，假定在Alice

25、下订单后不久，并且恰恰在她向Bob进行支付之前，股票交易系统丢失了该交易的所有数据。事情发生在这个节骨眼上，这提供了一种可能，即Alice可以声明她并未下过订单，也就是说，她能够否认这次交易。Bob是否能够证明Alice下过订单呢？如果他所拥有的只是Alice的消息认证码MAC，那么他不能证明。因为既然Bob也知道共享的对称密钥KAB，他就能够伪造一条消息，并在该消息中显示“Alice下了订单”。这里请注意，Bob是知道Alice下过订单的，但是他不能够在法庭上证明这一点，他缺少证据。31在同样的场景下，假设Alice使用数字签名，而不是消息认证码MAC。和消息认证码MAC一样，数字签名也能够

26、提供数据完整性的验证。我们再一次假定股票交易系统丢失了交易的所有数据，并且Alice试图否认这次交易。这时Bob能够证实来自Alice的订单吗？是的，他能够做到，因为只有Alice可以访问她自己的私钥。于是，数字签名就提供了数据完整性和不可否认性，而消息认证码MAC却只能够用于保护数据完整性。这是因为对称密钥是Alice和Bob都知道的，然而Alice的私钥则仅有Alice本人可知。324.7.3 机密性和不可否认性假设Alice和Bob有公开密钥加密系统可用，Alice想要发送一条消息M给Bob。为了机密性起见，Alice将使用Bob的公钥加密消息M。另外，为了获得数据完整性和不可否认性保护

27、，Alice可以使用她自己的私钥对消息M进行签名。但是，如果Alice是个非常关注安全性的人，想要既有机密性，又有不可否认性，她就不能只对消息M签名，因为那样不能提供数据机密性保护，她也不能只对消息M加密，因为这不能提供数据完整性保护。如何同时提供机密性和不可否认性？Alice可以对消息进行签名和加密，然后再将其发送给Bob，具体操作为：MAlice Bob 或者先加密消息M，再对该结果实施签名：MBobAlice33先签名再加密方式的缺陷34 先加密后签名方式的缺陷35结论消息的接收者并不是清楚地理解公开密钥加密技术的工作原理和方式。对于公开密钥加密技术，有一些内在的局限性。其中大部分是因为

28、任何人都可以实施公开密钥的操作这一事实。也就是说，任何人都可以加密一条消息，任何人也都可以验证数字签名。这个事实可能成为造成混乱的根源，如果你不够小心的话。364.8 公开密钥基础设施 术语 公开密钥基础设施公开密钥基础设施，或简称为PKI，是指在现实世界中，安全地使用公开密钥加密技术所必须具备的一切条件的总和。数字证书数字证书(或称为公钥证书，抑或简称为证书)包含了用户的名称以及伴随的相关用户的公钥，该证书由证书权威机构签名，证书权威机构也可简称为CA。例如，Alice的证书就包括如下内容 M=(“Alice”,Alice的公钥的公钥)和和S=MCA 为了验证这个证书，Bob将执行计算SCA

29、，并要检验该结果是否与M相匹配。权威机构CA扮演可信的第三方，或简称为TTP(Trusted Third Party)。通过对证书签名，CA就为这样一个事实提供了担保：分发了相应的私钥给Alice。37数字证书撤销问题通常，签发的数字证书都有一个有效期。但是，如果私钥被破解了，或者已经发现数字证书的签发有错误，那么证书必须立即撤销。大部分的PKI框架都需要定期发布证书撤销列表(Certificate Revocation Lists，或简称为CRL)，用于过滤受到损害不再适用的数字证书。某些情况下，这可能会给用户带来沉重的负担，因为可能会进一步导致错误或安全缺陷。任何PKI体系必须解决如下问题

30、：密钥生成和管理 数字证书授权(建立CA体系)数字证书撤销38 典型实例（一）垄断模型 所谓垄断模型就是一套统一的信任体系架构，意即建立全局范围内的CA。主要缺陷就是为攻击提供了一个巨大的目标。垄断型CA一旦受到损害，整个PKI体系就都将失效。（二）寡头模型有多个可信的CA。这正是如今在使用的方案一个Web浏览器可能会配置上80个，甚至更多个CA的证书。（三）混乱模型 在这种模型中，任何人都可以是CA，完全由用户自己来决定他们想信任哪些CA。混乱模型可能会给用户带来巨大的负担。394.9 小结 本章回顾 背包加密体制 椭圆曲线加密体制(Elliptic Curve Cryptography，ECC)数字签名和不可否认性 数字证书40