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

1、1信息安全原理与实践Information 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

2、 n-1Wn-1, 能够成立。例子： 假设权重值为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，那么

3、一定有a6=1，因为剩余所有权重值的和要小于200。接着计算S=S-200=109，这是新的目标和值。因为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）为了将这个超递增的背包转换成常规

4、背包，我们必须选择乘数m和模数n，m和n必须是互素的，且n要大于超递增背包中所有元素值的和。假设选取的乘数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的二进制位，据此来选择常规背

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

6、，要想解密显然是非常困难的。当然，有了私钥，我们就能够将问题转换为超递增背包问题，解决起来就容易了。背包问题看起来确实是对症下药了。首先，构造包含公钥和私钥的密钥对是相当容易的。而且，给定了公钥，实施加密是非常容易的，而了解了私钥则会使解密过程非常容易。最后，在没有私钥的情况下，攻击者就将不得不去解决NP完全问题了。可惜这个精巧的背包加密系统是不安全的。该方案于1983年被Shamir使用一台Apple II计算机破解。该攻击依赖于一种称为格基规约的技术。问题的根本在于该方案中从超递增背包问题派生出的所谓“常规背包问题”并不是真正的常规背包问题事实上，它是一种非常特殊的高度结构化的背包案例，而

7、格基规约攻击能够利用这种结构的特点比较容易地恢复出明文(可以较高的概率完成)。94.3 RSARSA体制的命名来自于它的三个公认的发明者：Rivest、Shamir和Adleman。10为了生成RSA算法的公钥和私钥的密钥对，先要选择两个大素数p和q：计算出它们的乘积N=pq。选择与乘积(p-1) (q-1)互素的数e。计算出数e的模(p-1) (q-1)的乘法逆元素，命名该逆元素为d。这些数值满足公式ed = 1 mod (p-1) (q-1)。数N是模数，e是加密指数，而d是解密指数。RSA密钥对的组成如下：公钥：(N, e)私钥：d加密：将明文文本消息M视为一个数，对其按指数e求幂并模N

8、C=M e mod N解密：要解密C，求幂模运算使用解密指数d完成相应的操作过程M=C d mod NRSA加密体制真的确实有效吗？ 给定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生成

9、Alice的密钥对：选择两个“大的”素数：p=11，q=3。模数就是N=pq=33，并且可以计算出 (p-1)(q-1)=20。选取加密指数为e=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

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

11、 10100)=(0, 1, 2, 5, 10, 20)现在计算520，重复平方方法的执行过程如下：14So easy！4.3.3 加速RSA加密体制另外一个可用于加速RSA加密体制的技巧是，对于所有用户使用同一加密指数e。而这并不会在任何方面削弱RSA加密体制的强度。通常加密指数的合适选择是e=3。选择这个e值，每一次公钥加密仅仅需要两次乘法运算。不过，私钥的运算操作仍然代价高昂。如果多个用户都使用e=3作为他们的加密指数，那么还存在另一种类型的立方根攻击。如果对于同一个消息M，使用三个不同用户的公钥分别加密，生成的密文比如是C0、C1和C2，那么中国剩余定理可用于恢复明文消息M。在实践中，

12、这也很容易避免，方法就是对每个消息M随机附加填充信息，或者在每个消息M中增加一些用户指定的信息，这样每个消息实际上就会互不相同了。另一个流行的通用加密指数是e=216+1。选取这个e值，每个加密运算仅需要执行17个重复平方算法的步骤。e=216+1的另一个优势是，在运用中国剩余定理的攻击者成功破解消息密文之前，同样的加密消息密文必须已经先行发送给e=216+1个用户。154.4 Diffie-Hellman密钥交换算法Diffie-Hellman密钥交换算法，或简称为DH，是由英国政府通信总部(GCHQ)的Malcolm Williamson所发明，其后不久，该算法又被它的命名者Whitfie

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

14、mod p，也将结果发送给Alice。Alice执行如下计算：(gb)a mod p=gab mod pBob执行如下计算：(ga)b 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之间，截获从Alic

15、e发送给Bob的消息，同样也截获从Bob发送给Alice的消息。Trudy如此部署，将使DH密钥交换很容易地就被彻底破坏了。在这个过程中，Trudy建立共享的秘密，比方说，和Alice共享gat mod p，和Bob共享另一个秘密gbt mod p。无论是Alice还是Bob，都不会觉察到这其中有任何问题，于是，Trudy就能够读到或改写Alice和Bob之间传递的任何消息了。19预防中间人攻击的方法使用共享对称密钥对DH密钥交换过程实施加密。使用公钥对DH密钥交换过程实施加密。使用私钥对DH密钥交换过程中的值进行数字签名。204.5 椭圆曲线加密椭圆曲线加密体制(Elliptic Curve

16、 Cryptography，ECC)提供了另一个“实施复杂难解的数学操作”的方法。优势：要获得同样等级的安全性，需要的二进制位数较少缺点：椭圆曲线体制的数学计算更加复杂，因此，椭圆曲线体制中的每个数学操作的代价都相对而言更加昂贵。典型的椭圆曲线图214.5.1椭圆曲线的数学原理从加密技术的角度来说，我们希望处理的是离散的点集。这可以通过在通用椭圆曲线的计算等式上执行“mod p”运算来轻松地实现。y2=x3+ax+b(mod p)例子：y2=x3+2x+3(mod 5)对于x的所有取值，逐个选取并计算相应的y值(一个或多个值)。因为我们是基于模数5实施运算，所以我们只需考虑x=0, 1, 2,

17、 3, 4的情况。在这个例子中，我们最后获得如下这些点：x=0 y2=3 no solution mod 5x=1 y2=6=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然后

18、计算x3=12-1-3=-3=2 mod 5y3=1(1-2)-4=-5=0 mod 5这样，在椭圆曲线y2 =x3+2x+3(mod 5)上，就得到(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,

19、7)。将x=2和y=7代入曲线中，就可以确定b=19。于是，该方案的公开信息就是y2= x3+11x+19(mod 167) 和 点(2,7)Alice和Bob每人都必须随机选择他们自己的秘密乘法因子。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

20、, 43)=15(9, 43)=(131, 140)Bob执行类似计算：B(102, 88)=22(102, 88)=(131, 140)Diffie-Hellman密钥交换方案的椭圆曲线版本之所以能够有效工作，全在于ABP=BAP，其中A和B分别是秘密乘法因子，而P是椭圆曲线上指定的点。这个方案的安全性依赖于如下事实：即使Trudy能够看到AP和BP，但是很显然，她也必须找到A或B，然后才能够确定共享秘密。据目前所知，这个Diffie-Hellman密钥交换方案的椭圆曲线版本和常规的Diffie-Hellman密钥交换方案同样难于破解。事实上，对于给定长度的二进制位数，椭圆曲线版本的Diff

21、ie-Hellman密钥交换方案要难破解得多，而且它使得我们可以使用更小的数值获得同等级别的安全性。因为数值越小，其算法的效率越高。264.5.3 现实中的椭圆曲线加密案例设定p = 564538252084441556247016902735257a = 321094768129147601892514872825668b = 430782315140218274262276694323197考虑椭圆曲线E：y2 = x3+ax +b(mod p)，我们令P点为(97339010987059066523156133908935,14967037284616928576068237197889

22、8)该点位于椭圆曲线E之上，再令k=281183840311601949668207954530684。然后，将P点与自身相加k次，表示为kP，于是我们得到点(44646769697405861057630861884284,522968098895785888047540374779097)这个点也位于椭圆曲线E上。274.6 公开密钥体制的表示方法对于公开密钥加密体制中的加密、解密和签名，我们将采用下面的表示方法：使用Alice的公钥加密消息M：C=MAlice使用Alice的私钥解密密文消息C：M=CAliceAlice签名的消息M的表示方法：S=MAlice花括号表示使用公钥的操作，方

23、括号代表使用私钥的操作，下标用来表明使用谁的密钥。既然公钥操作和私钥操作是互相消解的，于是可以得到如下等式：MAliceAlice=MAliceAlice=M公钥是公开的，因而任何人都能够去计算MAlice。私钥是私密的，所以只有Alice能够执行计算CAlice或MAlice。这意味着任何人都能够为Alice加密消息，但是仅有Alice本人能够解密相应密文。284.7 公开密钥加密体制的应用能够使用对称密钥加密方案完成的任何事情，也都可以通过公开密钥加密方案来完成，只不过要慢一些，包括保护数据的机密性，类似的应用形式还有：通过不安全的通道传送数据，或者在不安全的媒介上安全地存储数据等。此外，

24、我们还能够将公开密钥加密体制用于保护数据的完整性数字签名就能够起到对称密钥加密体制中消息认证码(MAC)的作用。相比对称密钥加密体制，公开密钥加密体制提供了两大主要优点。第一个主要优点是，基于公开密钥加密体制，我们不需要事先建立共享的密钥。第二个主要优点是，数字签名提供了完整性和不可否认性。294.7.1真实世界中的机密性相比公开密钥加密技术，对称密钥加密技术的主要优势是效率。我们是否能够既拥有对称密钥加密方案的效率，又不必提供事先的预共享密钥呢？要得到这样超级完美的结果，方法就是构建混合加密系统，其中公开密钥加密体制用于建立对称密钥，将这个生成的对称密钥用于加密数据。304.7.2 数字签名

25、和不可否认性不可否认性 假设Alice从她最中意的股票商Bob那里订购了100股股票。为了确保她的订单的完整性，Alice使用共享的对称密钥KAB计算消息认证码MAC。现在，假定在Alice下订单后不久，并且恰恰在她向Bob进行支付之前，股票交易系统丢失了该交易的所有数据。事情发生在这个节骨眼上，这提供了一种可能，即Alice可以声明她并未下过订单，也就是说，她能够否认这次交易。 Bob是否能够证明Alice下过订单呢？如果他所拥有的只是Alice的消息认证码MAC，那么他不能证明。因为既然Bob也知道共享的对称密钥KAB，他就能够伪造一条消息，并在该消息中显示“Alice下了订单”。这里请注

26、意，Bob是知道Alice下过订单的，但是他不能够在法庭上证明这一点，他缺少证据。31在同样的场景下，假设Alice使用数字签名，而不是消息认证码MAC。和消息认证码MAC一样，数字签名也能够提供数据完整性的验证。我们再一次假定股票交易系统丢失了交易的所有数据，并且Alice试图否认这次交易。这时Bob能够证实来自Alice的订单吗？是的，他能够做到，因为只有Alice可以访问她自己的私钥。于是，数字签名就提供了数据完整性和不可否认性，而消息认证码MAC却只能够用于保护数据完整性。这是因为对称密钥是Alice和Bob都知道的，然而Alice的私钥则仅有Alice本人可知。324.7.3 机密性

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