第五章 公钥密码体制

1、 第五章第五章 公钥密码体制公钥密码体制本章重点：本章重点：公钥密码体制的性质公钥密码体制的性质公钥密码学的理论基础：单向陷门函数公钥密码学的理论基础：单向陷门函数 数论的部分知识数论的部分知识 公钥密码学的实例：公钥密码学的实例：RSARSA算法的原理和工算法的原理和工作过程；作过程；ElGamalElGamal密码体制密码体制5.1 5.1 公钥密码体制的基本原理公钥密码体制的基本原理 公钥密码体制采用了两个不同的密公钥密码体制采用了两个不同的密钥，这对在公开的网络上进行钥，这对在公开的网络上进行保密通信保密通信、密钥分配密钥分配、数字签名和认证数字签名和认证有着深远的有着深远的影响。影响

2、。 5.1.1 对称算法的不足对称算法的不足 密钥管理量的困难：密钥管理量的困难：两两分别用一个密钥时，两两分别用一个密钥时，则则n n个用户需要个用户需要C(n,2)=n(n-1)/2C(n,2)=n(n-1)/2个密钥，当用户个密钥，当用户量增大时，密钥空间急剧增大。如量增大时，密钥空间急剧增大。如:n=100 :n=100 时，共时，共4,9954,995个；个；n=5000n=5000时增加到时增加到12,497,50012,497,500个。个。 密钥建立问题：密钥建立问题：对协商密钥的信道的安全性对协商密钥的信道的安全性的要求比正常的传送消息的信道的安全性要高。的要求比正常的传送消

3、息的信道的安全性要高。 数字签名的问题：数字签名的问题：传统加密算法无法实现抗传统加密算法无法实现抗抵赖的需求。抵赖的需求。 5.1.2 公钥密码体制的起源公钥密码体制的起源q公钥密码又称为双钥密码和非对称密码，是公钥密码又称为双钥密码和非对称密码，是19761976年由年由DiffieDiffie和和HellmanHellman在其在其“密码学新方向密码学新方向”一文中提出一文中提出的，见划时代的文献：的，见划时代的文献：W.Diffie and M.E.Hellman, W.Diffie and M.E.Hellman, New Directrions in Cryptography, I

4、EEE New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-Transaction on Information Theory, V.IT-22.No.6, Nov 1976,PP.644-65422.No.6, Nov 1976,PP.644-654qRSARSA公钥算法是由公钥算法是由Rivest,ShamirRivest,Shamir和和AdlemanAdleman在在19781978年年提出来的提出来的, , 见见Communitions of the ACM. Communitio

5、ns of the ACM. Vol.21.No.2. Feb.1978, PP.120-126Vol.21.No.2. Feb.1978, PP.120-126 5.1.3 公开密钥密码的重要特性：公开密钥密码的重要特性：q加密与解密由不同的密钥完成加密与解密由不同的密钥完成加密加密: XY: Y = E: XY: Y = EKUKU(X)(X)解密解密: YX: X = D: YX: X = DKRKR(Y) = D(Y) = DKRKR(E(EKUKU(X)(X)q知道加密算法知道加密算法, ,从加密密钥得到解密密钥在计算上是不从加密密钥得到解密密钥在计算上是不可行的。（单向函数的性质）

6、可行的。（单向函数的性质）q两个密钥中任何一个都可以用作加密而另一个用作解两个密钥中任何一个都可以用作加密而另一个用作解密密( (单向函数的交换性，不是必须的单向函数的交换性，不是必须的) )X = DX = DKRKR(E(EKUKU(X) = E(X) = EKUKU(D(DKRKR(X)(X) 基于公开密钥的加密过程基于公开密钥的加密过程图图4.1 4.1 公钥密码体制的通信保密过程公钥密码体制的通信保密过程 基于公开密钥的鉴别过程基于公开密钥的鉴别过程图图4.2 4.2 公钥密码体制的数字签名和验证签名过程公钥密码体制的数字签名和验证签名过程 公钥密钥的应用范围公钥密钥的应用范围 加密

7、加密/ /解密解密 数字签名数字签名( (身份鉴别身份鉴别) ) 密钥交换密钥交换 1、涉及到各方：发送方、接收方、攻击者涉及到各方：发送方、接收方、攻击者 2 2、涉及到数据：公钥、私钥、明文、密文、涉及到数据：公钥、私钥、明文、密文 3 3、公钥算法的条件：、公钥算法的条件： 产生一对密钥是计算可行的；产生一对密钥是计算可行的； 已知公钥和明文，产生密文是计算可行的；已知公钥和明文，产生密文是计算可行的； 接收方利用私钥来解密密文是计算可行的；接收方利用私钥来解密密文是计算可行的； 对于攻击者，利用公钥来推断私钥是计算不可行的对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢

8、复明文是计算不可行的；已知公钥和密文，恢复明文是计算不可行的； ( (可选可选) )加密和解密的顺序可交换。加密和解密的顺序可交换。5.1.4 5.1.4 公钥密码系统基本思想和要求公钥密码系统基本思想和要求 涉及计算复杂性、近世代数等内容。涉及计算复杂性、近世代数等内容。q严格单向函数严格单向函数 一个单射函数一个单射函数f f: : 如果下述条件成立：如果下述条件成立： 存在一个有效的方法，对所有的存在一个有效的方法，对所有的xXxX可计算可计算f f（x x），但不存在一个有效的办法由），但不存在一个有效的办法由y= y= f f（x x）计）计算算x,x,所有的所有的yYyY。 则称则

9、称XYXY称为是严格单向函数。称为是严格单向函数。5.1.5 部分数学基础部分数学基础q陷门单向函数陷门单向函数单向陷门函数是满足下列条件的函数单向陷门函数是满足下列条件的函数f f：(1)(1)给定给定x x，计算，计算y=fy=fk k(x)(x)是容易的；是容易的；(2)(2)给定给定y, y, 计算计算x x使使x=fx=fk k-1-1(y)(y)是不可行的。是不可行的。(3)(3)存在存在k k，已知，已知k k时时, ,对给定的任何对给定的任何y y，若相应的，若相应的x x存存在，则计算在，则计算x x使使f fk k-1-1(x)(x)是容易的。是容易的。q背包问题背包问题q

10、大整数分解问题（大整数分解问题（The Integer Factorization The Integer Factorization Problem,RSA Problem,RSA 体制体制）q离散对数问题：离散对数问题：q有限域的乘法群上的离散对数问题有限域的乘法群上的离散对数问题(The Discrete (The Discrete Logarithm Problem,ElGamalLogarithm Problem,ElGamal体制）体制）q椭圆曲线上的离散对数问题（椭圆曲线上的离散对数问题（The Elliptic Curve The Elliptic Curve Discrete

11、 Logarithm Problem,Discrete Logarithm Problem,类比的类比的ElGamalElGamal体制）体制）大整数分解问题和离散对数是构造大整数分解问题和离散对数是构造RSARSA算法的重算法的重要基础要基础5.1.6 5.1.6 公钥密码基于的数学难题公钥密码基于的数学难题整数因子分解问题整数因子分解问题 许多密码系统的安全性都依赖于整数许多密码系统的安全性都依赖于整数因子分解的困难性。如因子分解的困难性。如RSARSA加密方案，加密方案，RSARSA签名方案和签名方案和RabinRabin公钥加密方案。公钥加密方案。定义：定义：给定一个正整数给定一个正整

12、数n n，找到它的素因子，即找到它的素因子，即n=pn=p1 1e1e1p p2 2e2e2ppk kekek, ,这里这里p pi i是是不同的素数，并且不同的素数，并且e ei i11。如：。如：91=791=713 ; 3600=213 ; 3600=24 43 32 25 52 2 至今没有有效的求解方法至今没有有效的求解方法。指数函数及其性质指数函数及其性质 指数函数指数函数y=ay=ax x mod pmod p，已知，已知x x求求y y是是一个可解问题，但其逆过程：已知一个可解问题，但其逆过程：已知y y求求x x称为离散对数问题，所以指数函数被认称为离散对数问题，所以指数函数

13、被认为是一个单向函数。为是一个单向函数。FermatFermat定理：定理：p p素数，素数，a a是整数且不能被是整数且不能被p p整除，则整除，则:a:ap-1p-11modp1modpq乘法逆元：乘法逆元：n n是整数是整数 当当ax=1modnax=1modn，x x是是a a的乘法逆元。的乘法逆元。a a的逆元记作的逆元记作a a-1-1，根据，根据FermatFermat定理，定理，p p是素数，若是素数，若gcb(a,p)=1gcb(a,p)=1， a ap-2p-2modpmodp是是a a的乘法逆元。的乘法逆元。qEuclidEuclid计算公因数计算公因数gcd(agcd(

14、a，b)=gcdb)=gcd（b b，a mod ba mod b）; ;可以通过扩展的可以通过扩展的EuclidEuclid算法可以算算法可以算 : :ed=k(n)+1 ed=k(n)+1 知道知道e e，d d，(n)(n)其中两个求另一个。因此：其中两个求另一个。因此：a aed ed amodnamodnqEulerEuler定理定理: : 若若a a与与n n为互素的正整数为互素的正整数, ,则则: : a a(n)(n)1modn1modn，推论，推论: : 若若n=pq, pqn=pq, pq都是素数都是素数, , k k是任意整数是任意整数,m,mk(nk(n）+1+1m m

15、 k(p-1)(q-1)+1k(p-1)(q-1)+1 m mod m mod n, n, 对任意对任意0mn0mn证明证明(n)= (p-1)(q-1)(n)= (p-1)(q-1)q离散对数的计算离散对数的计算: :ygygx x mod p mod p已知已知g,x,p,g,x,p,计算计算y y是容易的是容易的已知已知y,g,p,y,g,p,计算计算x x是困难的。是困难的。q密码学中常用的主要有三个群的离散对数密码学中常用的主要有三个群的离散对数有限域有限域GFGF（p p）的乘法群）的乘法群有限域有限域GFGF（2 2n n）上的乘法群）上的乘法群有限域有限域F F上的椭圆曲线群上

16、的椭圆曲线群 利用指数函数设计一个公钥密码体利用指数函数设计一个公钥密码体制用于密钥协商制用于密钥协商：通信双方根据对方公通信双方根据对方公开的信息，通过协商获得一对密钥（对开的信息，通过协商获得一对密钥（对称密钥），用来对以后的信息数据进行称密钥），用来对以后的信息数据进行加密。加密。5.1.7 5.1.7 设计公钥密码体制设计公钥密码体制算法：通信方算法：通信方A A和和B B双方选择素数双方选择素数p p以及以及p p的一个原根的一个原根a a用户用户A A选择一个随机数选择一个随机数X Xa a p p，计算，计算Y Ya a=a=aXaXa mod p mod p用户用户B B选择一

17、个随机数选择一个随机数X Xb b p 1n1是素数，那么是素数，那么( ) mod n ( ) mod n 另一方面，如果另一方面，如果n n是合数，则至多有一半的是合数，则至多有一半的整数整数a a满足满足( ) mod n( ) mod n。 根据这两个定理，我们就可以对一个随根据这两个定理，我们就可以对一个随机数进行素性检测了。机数进行素性检测了。pa2/ )1( pana2/ )1( nana2/ )1( na素性检测：素性检测：1 1）随机选取一个整数随机选取一个整数a,(1a,(1a an-1)n-1)；2 2）计算（）计算（ ）；）；3 3）如果）如果( ) mod n( )

18、mod n，则回到步骤，则回到步骤1 1，否则认为是合数，退出；否则认为是合数，退出；4 4）重复步骤）重复步骤1 1，2 2，3 3，共，共t t次，如果每次都次，如果每次都有有,( ) mod n,( ) mod n,则一般认为则一般认为n n是素数。是素数。na2/ )1( nanana2/ )1( naqDES和和RSA性能比较性能比较(同等强度）同等强度）DES密钥长度（bit） RSA密钥长度（bit）563846451211217921282304 ElGamal算法是在密码协议中有着广泛算法是在密码协议中有着广泛应用的一类公钥密码算法，它是利用具有应用的一类公钥密码算法，它是利

19、用具有可交换性单向函数设计的公钥密码系统。可交换性单向函数设计的公钥密码系统。狭义的狭义的ElGamal算法的安全性是算法的安全性是基于求解基于求解离散对数的困难性。离散对数的困难性。5.3 ElGamal密码体制密码体制1、参数选择：、参数选择： （1）要产生一对密钥，首先选择一素数）要产生一对密钥，首先选择一素数p，整数模整数模p的一个原根的一个原根g，随机选取，随机选取x，g和和x都小都小于于p，然后计算：，然后计算：y=gx mod p （2）公开密钥是）公开密钥是y,g,p，其中，其中g,p可以为一组可以为一组用户共享，私有密钥是用户共享，私有密钥是x。将明文信息将明文信息m m表示

20、成表示成0,1,p-10,1,p-1范围内的数。范围内的数。（1 1）加密）加密: :秘密选择随机数秘密选择随机数k k，计算：，计算： K=yK=yk kmod pmod pC C1 1=g=gk k mod p mod pC C2 2=Km mod p=Km mod p (C (C1,1,C C2 2 ) )作为密文传递。作为密文传递。 （2 2）解密）解密: :K=CK=C1 1x x mod p mod p；m=Cm=C2 2K K-1 -1 mod pmod p。2 2、加解密过程、加解密过程3 3、ElGamal ExampleElGamal Example选择选择 p=97 及本

21、原根及本原根 g=5 Bob 选择选择 密钥密钥xB=58 & 计算并发布公钥计算并发布公钥yB=558 mod 97 =44Alice 要加密要加密 M=3 to Bob 首先得到首先得到 Bob的公开密钥的公开密钥 yB=44 选择随机选择随机 k=36 计算计算:K=4436 mod 97 =75计算密文对计算密文对: C1 = 536 mod 97 = 50 C2 = 75*3 mod 97 = 31 发送发送 50,31 to Bob Bob 恢复恢复 K=5058 mod 97 =75Bob 计算计算 K-1 = 22 Bob 恢复明文恢复明文 M = 31*22 mod 97 =

22、 3 5.4 背包体制 背包体制是基于求解背包问题的困难背包体制是基于求解背包问题的困难性提出的。性提出的。 背包问题：给定一些物体，每个物体有不同背包问题：给定一些物体，每个物体有不同的重量，是否有可能将其中一些物体装入一个背的重量，是否有可能将其中一些物体装入一个背包中，使得背包重量等于一个给定的值。这个问包中，使得背包重量等于一个给定的值。这个问题可以形式化的描述为：给定一组值题可以形式化的描述为：给定一组值 ， 和一个和数和一个和数S S，计算，计算 的值，使得的值，使得 其中其中 的值为的值为0 0或或1 1，1 1表示将该物体放入背包表示将该物体放入背包中，中，0 0表示不放入。表

23、示不放入。 nMMM,21ixnnxMxMxMS2211ix 背包问题，已经被证实是一个背包问题，已经被证实是一个NP-NP-完全问完全问题。因此，背包问题不是在多项式时间内可以题。因此，背包问题不是在多项式时间内可以解决的问题。虽然如此，并非所有的背包问题解决的问题。虽然如此，并非所有的背包问题都是都是NP-CompleteNP-Complete问题，其实在许多特定的序问题，其实在许多特定的序列，要解上述的背包问题是非常简单的。我们列，要解上述的背包问题是非常简单的。我们称此类的序列为易解背包问题。其中，称此类的序列为易解背包问题。其中，超递增超递增背包序列背包序列就是其中一种。就是其中一种

24、。5.4.1 5.4.1 超递增序列超递增序列 超递增序列是这样一个序列：超递增序列是这样一个序列：其中每个元素都大其中每个元素都大于前面所有元素的和。于前面所有元素的和。 定义：定义：正整数序列正整数序列 称为超递增的，若对任称为超递增的，若对任何何 ，有，有 例例：（：（1 1，2 2，4 4，8 8，16 16 ）就是一个超递增序列。）就是一个超递增序列。 naaa,2111nl11lliiaan2超递增序列算法：解方程超递增序列算法：解方程 For i=n down to 1 doFor i=n down to 1 do Begin Begin If Sbi If Sbi then xi=1 then xi=1 else xi=0; else xi=0; S=S-bi S=S-bixi;xi; End End If S=0 then “solution exists” If S=0 then “solution exists” else “no solution e