公钥密码-信息安全概论课件.ppt

1、 起源起源 公钥密码又称为双钥密码和非对称密码，是公钥密码又称为双钥密码和非对称密码，是1976年由年由Diffie和和Hellman在其在其“密码学新方向密码学新方向”一文中提出的，见划时代的文献：一文中提出的，见划时代的文献：W.Diffie and M.E.Hellman,New Directrions in Cryptography,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654 RSA公钥算法是由公钥算法是由Rivest,Shamir和和Adleman在在1978年提出来的年提出来的,见见

2、 Communitions of the ACM.Vol.21.No.2.Feb.1978,PP.120-126公开密钥密码的重要特性公开密钥密码的重要特性加密与解密由不同的密钥完成加密与解密由不同的密钥完成加密加密:XY:Y=EKU(X)解密解密:YX:X=DKR(Y)=DKR(EKU(X)知道加密算法知道加密算法,从加密密钥得到解密密钥从加密密钥得到解密密钥在计算上是不可行的在计算上是不可行的两个密钥中任何一个都可以用作加密而两个密钥中任何一个都可以用作加密而另一个用作解密另一个用作解密X=DKR(EKU(X)=EKU(DKR(X)基于公开密钥的加密过程基于公开密钥的加密过程基于公开密钥的

3、鉴别过程基于公开密钥的鉴别过程 用公钥密码实现保密用公钥密码实现保密用户拥有自己的密钥对用户拥有自己的密钥对(KU,KR)公钥公钥KU公开公开,私钥私钥KR保密保密AB:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X)=X 用公钥密码实现鉴别用公钥密码实现鉴别条件条件:两个密钥中任何一个都可以用作加密而两个密钥中任何一个都可以用作加密而另一个用作解密另一个用作解密鉴别鉴别:AALL:Y=DKRa(X)ALL:EKUa(Y)=EKUa(DKRa(X)=X鉴别鉴别+保密保密:AB:Z=EKUb(DKRa(X)B:EKUa(DKRb(Z)=X 公钥密钥的应用范围加密加密/解密解密数字签

4、名数字签名(身份鉴别身份鉴别)密钥交换密钥交换算法算法加加/解密解密 数字签名数字签名密钥交换密钥交换RSA是是是是是是Dieffie-Hellman否否否否是是DSS否否是是否否基本思想和要求基本思想和要求 涉及到各方：发送方、接收方、攻击者涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文涉及到数据：公钥、私钥、明文、密文 公钥算法的条件：公钥算法的条件：产生一对密钥是计算可行的产生一对密钥是计算可行的 已知公钥和明文，产生密文是计算可行的已知公钥和明文，产生密文是计算可行的 接收方利用私钥来解密密文是计算可行的接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥

5、来推断私钥是计算不对于攻击者，利用公钥来推断私钥是计算不可行的可行的 已知公钥和密文，恢复明文是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选可选)加密和解密的顺序可交换加密和解密的顺序可交换陷门单向函数陷门单向函数单向陷门函数是满足下列条件的函数单向陷门函数是满足下列条件的函数f f：(1)给定给定x，计算，计算y=fk(x)是容易的；是容易的；(2)给定给定y,计算计算x使使x=fk-1(y)是不可行的。是不可行的。(3)存在存在k，已知，已知k 时时,对给定的任何对给定的任何y，若相应的，若相应的x存在，则计算存在，则计算x使使x=fk-1(y)是容易的。是容易的。公钥密码基于

6、的数学难题公钥密码基于的数学难题 背包问题背包问题 大整数分解问题（大整数分解问题（The Integer FactorizationThe Integer Factorization Problem,RSA Problem,RSA体制）体制）有限域的乘法群上的离散对数问题有限域的乘法群上的离散对数问题 (The Discrete Logarithm Problem,(The Discrete Logarithm Problem,ElGamal ElGamal体制）体制）椭圆曲线上的离散对数问题（椭圆曲线上的离散对数问题（The EllipticThe Elliptic Curve Discr

7、ete Logarithm Problem,Curve Discrete Logarithm Problem,类比的类比的ElGamalElGamal体制）体制）数学基础数学基础 同余同余：给定任意整数给定任意整数a和和m，以，以q除除a，余数是，余数是r，则可以表示为，则可以表示为a=sm+r,0 rm，其中，其中s=a/m,表示小于表示小于a/m的最大整数。的最大整数。定义定义r为为a mod m的剩余的剩余，记为，记为r a mod q.若整数若整数a和和b有有(a mod m)=(b mod m)，则称，则称a与与b在在mod m下同余下同余。同余关系的性质：同余关系的性质：（1）为等

8、价关系，即具有自反性，对称性和可传递性）为等价关系，即具有自反性，对称性和可传递性 自反性：自反性：a a mod m 对称性：对称性：若若a b mod m，则，则 b a mod m 传递性：若传递性：若a b mod m且且b c mod m，则，则a c mod m同余同余（2）同余式可以进行运算）同余式可以进行运算 若若a b mod m，c d mod m，则则a+c b+d mod m，ac bd mod m，an bn mod m（3）若）若ac bc mod m，且（，且（c，m）d，则则 a b mod m/d；特别的，若特别的，若(c,m)=1，则，则a b mod m（

9、4）若）若m1，(a,m)=1，则存在，则存在c使得使得 ac 1 mod m，称，称c是是a对模对模m的逆，记做的逆，记做a-1同余同余（5）设）设a1和和a2为任意整数，为任意整数，op为操作符，如、为操作符，如、等，则：等，则：(a1 op a2)mod m=(a1 mod m)op (a2 mod m)mod m eg.a1=23，a2=8，m=3 238 mod 331 mod 3 1 （23 mod 3 8 mod 3）22 mod 3 1 238 mod 3 184 mod 3 1 （23 mod 3 8 mod 3）22 mod 3 1同余（剩余）类同余（剩余）类 假定假定m为

10、正整数，任一整数除为正整数，任一整数除m得到的最小非负剩余必得到的最小非负剩余必定为定为0，1，.，m-1中的一个，即任一整数对于模中的一个，即任一整数对于模m必定必定与与0，1，.，m-1中的某一个同余。因此，我们把全体整中的某一个同余。因此，我们把全体整数分成若干两两不相交的集合，使得在同一个集合中的任数分成若干两两不相交的集合，使得在同一个集合中的任意两个数对模意两个数对模m同余，而属于不同集合的两个数对模同余，而属于不同集合的两个数对模m一定一定不同余。每一个这样的集合称作关于模不同余。每一个这样的集合称作关于模m的同余类。的同余类。完全剩余系完全剩余系 从模从模m的每一个同余类中任取

11、一数就得到的每一个同余类中任取一数就得到m个数，这个数，这m个数称作个数称作m的完全剩余系。如模的完全剩余系。如模4的一个完全剩余系的一个完全剩余系0，5，2，11。通常选取的不大于。通常选取的不大于m的的m个非负整数集合个非负整数集合0，1，2，.，m-1。同余类同余类既约（互素）同余类和既约剩余系既约（互素）同余类和既约剩余系 对于模对于模m的同余类的同余类r mod m，如果，如果(r,m)=1，则称该同余，则称该同余类是模类是模m的既约同余类。的既约同余类。在模在模m的一个完全剩余系中，所有与的一个完全剩余系中，所有与m互素的数的集合互素的数的集合构成模构成模m的既约剩余系。的既约剩余

12、系。eg.m=5 0,1,2,3,4 1,2,3,4 m=10 0,1,2,.9 1,3,7,9欧拉函数欧拉函数 模模m的所有既约同余类的个数记为的所有既约同余类的个数记为(m)，通常称作，通常称作Euler函数。函数。eg.(5)4，(10)4欧拉函数欧拉函数Euler函数和函数和Euler定理定理 p是素数，是素数，(p)=p-1 若若gcd(m,n)=1,则则(mn)=(m)(n),特别地特别地,若若p q且都是素数且都是素数,(pq)=(p-1)(q-1)eg.(10)(2)(5)144 Euler定理：若定理：若(a,m)=1，则，则a(m)1 mod m eg.a7，m5，则，则7

13、4=7272=44 mod 51 通过欧拉定理，可以求得通过欧拉定理，可以求得a的逆的逆a-1 a(m)-1 mod mEuler定理定理若若(a,m)=1，则，则a(m)1 mod m证明证明:R=x1，x2，x(m)为所有小于为所有小于m且与且与m互素互素的正整数，即为一个既约剩余系，考虑集合的正整数，即为一个既约剩余系，考虑集合S=ax1 mod m,ax2 mod m，ax(m)mod m axi mod m与与m互素互素 axi mod m与与axj mod m不同余，其中不同余，其中ij:axi=axj mod m xi=xj mod n 故故S也是一个剩余系，那么也是一个剩余系，

14、那么 xi mod m=(axi mod m)(axi)mod m (a(m)xi)mod m a(m)1 mod m Fermat小定理小定理FermatFermat小定理小定理:p:p素数素数,(a,p)=1,(a,p)=1,则则:a:ap-1p-1 1 mod 1 mod p p推论推论:p:p素数素数,a,a是任意整数是任意整数,则则:a:ap p a mod p a mod p定理定理 若若(a,m)=1(a,m)=1，则同余方程，则同余方程 axax 1 mod m1 mod m有唯一的解有唯一的解 eg.7x eg.7x 1 mod 5 x=3,8,13,.1 mod 5 x=3

15、,8,13,.证明：一定有解，因为证明：一定有解，因为aaaa(m)-1 1 mod m1 mod m 若有不同的解若有不同的解x x1 1,x,x2 2，则，则axax1 1 ax ax2 2 mod mmod m 由于由于(a,m)=1a,m)=1，则，则x x1 1 x x2 2 mod mmod m 用于在用于在RSARSA中计算密钥中计算密钥 Euler定理推论定理推论推论推论:若若m=pq,p q都是素数都是素数,k是任意整数是任意整数,则则 ak(p-1)(q-1)+1 a mod m,对任意对任意0 am证明证明:若若(a,m)1，(m)=(p-1)(q-1),由由Euler定

16、理有定理有 a(m)1 mod m，所以有结论成立；，所以有结论成立；否则否则a必定是必定是p或者或者q的倍数的倍数,不妨设不妨设a=sp,则则 0sq为正整数为正整数,a与与q互素互素,由由Euler定理得到定理得到:a(q)1 mod q (a(q)k(p)1 mod q ak(p-1)(q-1)=tq+1 t是整数是整数 等式两边乘以等式两边乘以a=sp,得到得到:ak(p-1)(q-1)+1=(tq+1)sp=tspq+sp a mod m 原根原根(primitive root)Euler定理表明定理表明,对两个互素的整数对两个互素的整数a,n,a(n)1 mod n 定义：定义：素

17、数素数p的原根定义：如果的原根定义：如果a是素数是素数p的原根，则数的原根，则数a mod p,a2 mod p,ap-1 mod p是不同的并且包含是不同的并且包含1到到p-1的整数的某种排列。的整数的某种排列。对任意的整数对任意的整数b且且(b,p)=1，我们可以找到唯一的，我们可以找到唯一的幂幂i满足满足 b=ai mod p 0i(p-1)离散对数离散对数若若a是素数是素数p的一个原根的一个原根,则对任意整数则对任意整数b,(b,p)=1,存在唯一的整数存在唯一的整数i,1 i(p-1),使得使得:b ai mod pi称为称为b以以a为基模为基模p的的指数指数(离散对数离散对数),记

18、作记作inda,p(b).容易容易知道知道:inda,p(xy)=inda,p(x)+inda,p(y)mod(p)inda,p(xr)=r inda,p(x)mod(p)离散对数的计算离散对数的计算:y gx mod p已知已知g,x,p,计算计算y是容易的是容易的已知已知y,g,p,计算计算x是困难的是困难的经典例子经典例子 Diffie-Hellman密钥交换算法密钥交换算法 背包算法背包算法 RSA算法算法 Diffie-Hellman密钥交换密钥交换 允许两个用户可以安全地交换一个秘密信息，用于后续的允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程通讯过程 算法的安全性依赖

19、于计算离散对数的难度算法的安全性依赖于计算离散对数的难度素数素数p的原根定义：如果的原根定义：如果a是素数是素数p的原根，则数的原根，则数a mod p,a2 mod p,ap-1 mod p是不同的并且包含是不同的并且包含1到到p-1的整数的某种排列。的整数的某种排列。对任意的整数对任意的整数b，(b,p)=1,我们可以找到唯一的幂我们可以找到唯一的幂i满足满足b=ai mod p 0=i=(p-1)i 在离散对数算法中称为以在离散对数算法中称为以a为基的指数为基的指数 mod p。记为。记为inda,p(b)Diffie-Hellman密钥交换密钥交换 算法：算法：双方选择素数双方选择素数

20、p以及以及p的一个原根的一个原根a 用户用户A选择一个随机数选择一个随机数Xa p，计算，计算 Ya=aXa mod p 用户用户B选择一个随机数选择一个随机数Xb p，计算，计算 Yb=aXb mod p 每一方保密每一方保密X值，而将值，而将Y值交换给对方值交换给对方 用户用户A计算出计算出 K=YbXa mod p 用户用户B计算出计算出 K=YaXb mod p 双方获得一个共享密钥双方获得一个共享密钥(aXaXbmod p)素数素数p以及以及p的原根的原根a可由一方选择后发给对方可由一方选择后发给对方 Generate randomXa pCalculateYa=aXa mod pG

21、enerate randomXb pCalculateYb=aXb mod pUser AUser BYaYbCalculateK=(Yb)Xa mod pCalculateK=(Ya)Xb mod pDiffie-Hellman Key Exchange Diffie-Hellman密钥交换的攻击密钥交换的攻击中间人攻击图示中间人攻击图示ABK=aXaXoOK=aXbXo Diffie-Hellman密钥交换的攻击密钥交换的攻击中间人攻击中间人攻击1 双方选择素数双方选择素数p以及以及p的一个原根的一个原根a(假定假定O知道知道)2 A选择选择Xap,计算计算Ya=aXa mod p,AB:

22、Ya3 O截获截获Ya,选选Xo,计算计算Yo=aXo mod p,冒充冒充AB:Yo4 B选择选择Xb aj(j=1,i-1)这样的背包也被称为超递增背包这样的背包也被称为超递增背包 求解求解 从最大的从最大的ai开始，如果开始，如果S大于这个数，则减去大于这个数，则减去ai,记记xi为为1，否则记否则记xi为为0 如此下去，直到最小的如此下去，直到最小的ai 例如背包序列例如背包序列2,3,6,13,27,52 求解求解70的背包的背包 结果为结果为2,3,13,52 所以，密文所以，密文70对应的明文为对应的明文为110101 转换背包转换背包 简单背包用作私钥简单背包用作私钥 如何产生

23、相应的公钥如何产生相应的公钥转换转换 做法：做法：选择一个整数选择一个整数 m ai(i=1,n)然后选择一个与然后选择一个与m互素的整数互素的整数w，然后，然后ai=wai(mod m)(i=1,n)这里的这里的ai 是伪随机分布的是伪随机分布的这样得到的背包是非超递增背包这样得到的背包是非超递增背包 基于背包问题的公钥密码系统基于背包问题的公钥密码系统MH公钥算法公钥算法 加密加密 将明文分为长度为将明文分为长度为n的块的块X=(x1,xn)然后用公钥然后用公钥A =(a1,an)，将明文变为密文，将明文变为密文S=E(X)=ai xi 解密解密 先计算先计算S =w-1S mod m 再

24、求解简单背包问题再求解简单背包问题S =aixiEaxmple-从私钥计算公钥从私钥计算公钥 私钥私钥2,3,6,13,27,52 w=31,m=1052*31 mod 105=623*31 mod 105=936*31 mod 105=8113*31 mod 105=8827*31 mod 105=10252*31 mod 105=37 公钥公钥62,93,81,88,102,37Eaxmple-加密加密 消息消息=011000 110101 101110 明文明文:0 1 1 0 0 0 背包背包:62 93 81 88 102 37 密文密文:93+81=174 011000 对应于对应

25、于93+81=174 110101对应于对应于62+93+88+37=280 101110对应于对应于62+81+88+102=333Eaxmple-解密解密 解密者知道解密者知道2,3,6,13,27,52,w,m 计算计算w(w-1)=1mod(m)w-1=61 密文为密文为174,280,333 174*61 mod 105=9=3+6,对应于对应于 011000 280*61 mod 105=70=2+3=13+52,对应于对应于110101 333*61 mod 105=48=2+6+13+27,对应于对应于101110 因此因此,消息消息=011000 110101 101110

26、背包密码系统的意义背包密码系统的意义 是第一个公钥密码系统是第一个公钥密码系统 有较好的理论价值有较好的理论价值 在实践过程中，大多数的背包方案都已被破解，在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷或者证明存在缺陷 经典例子经典例子 Diffie-Hellman密钥交换算法密钥交换算法 背包算法背包算法 RSA算法算法 RSA算法算法 1977年由年由Ron Rivest、Adi Shamir和和Len Adleman发明，发明，1978年公布年公布 是一种分组加密算法。是一种分组加密算法。明文和密文在明文和密文在0n-1之间之间,n是一个正整数是一个正整数 应用最广泛的公钥密

27、码算法应用最广泛的公钥密码算法 只在美国申请专利，且已于只在美国申请专利，且已于2000年年9月到期月到期 RSA算法描述算法描述 RSA加、解密算法加、解密算法(1978 Rivest,Shamir,Adelman)分组大小为分组大小为k,2k n 2k+1 公开密钥公开密钥 n(两素数两素数p和和q的乘积的乘积)（推荐（推荐p,q等长）等长）e，满足（，满足（e，(n)）1 （其中（其中(n)=(p-1)(q-1)保密保密）ed 1 (mod (n)私人密钥私人密钥 d（e-1 mod(p-1)(q-1)加密加密 c=me mod n 解密解密 m=cdmod n )(mod)(mod1)

28、()1)(1(nmnmmmmmciiqpkiedideidii RSA密钥生成原理密钥生成原理 令令n=pq,p q都是素数都是素数,(n)=(p-1)(q-1)是是n的的Euler数数 Euler定理推论定理推论:若若n=pq,p q都是素数都是素数,k是任意整数是任意整数,则则 mk(p-1)(q-1)+1 m mod n,对任意对任意0 m n 只要选择只要选择e,d,满足满足ed=k(n)+1,即即ed 1 mod (n)d e-1 mod (n)公钥公钥:KU=e,n,私钥私钥:KR=d,n example（1）若）若Bob选择了选择了p=7和和q5（2）那么，）那么，n=35,(n

29、)=6424；（3）然而）然而24233，一个正整数，一个正整数e能用作加密指数，当且能用作加密指数，当且仅当仅当e不能被不能被2，3所整除。假设所整除。假设Bob选择选择了了e=11，（4）那么用）那么用Euclidean算法将求得：算法将求得：d=e-1 11(mod 24),于是于是Bob的解密密钥的解密密钥d=11.（5）Bob在一个目录中公开在一个目录中公开n=35和和e=11（6）现假设）现假设Alice想发送明文想发送明文2给给Bob，她计算：，她计算：211(mod 35)=25 26(mod 35)=32*64=32*29=928(mod 35)=18，且在一个信道上发送密文

30、且在一个信道上发送密文18。（7）当）当Bob接收到密文接收到密文18时，他用他的秘密解密指数（私时，他用他的秘密解密指数（私钥）钥）d11进行解密：进行解密：1811（mod 35)=(18)2*5+1=182*182*182*182*182*18=9*9*9*9*9*18=11*11*162=16*22=352=2 mod 35RSA安全性依据安全性依据 RSA的安全性是基于加密函数的安全性是基于加密函数ek(x)=xe(mod n)是一是一个单向函数，所以对攻击的人来说求逆计算不可行。个单向函数，所以对攻击的人来说求逆计算不可行。而而Bob能解密的陷门是分解能解密的陷门是分解n=pq，知

31、，知 (n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥从而用欧氏算法解出解密私钥d.（猜想：攻破（猜想：攻破RSA与分解与分解n是多项式等价的。然是多项式等价的。然而，这个猜想至今没有给出可信的证明！）而，这个猜想至今没有给出可信的证明！）每个合数都可以唯一地分解出素数因子每个合数都可以唯一地分解出素数因子6=2 3999999=333711133727641 =131121从从2 开始试验每一个小于等于开始试验每一个小于等于27641 的素数。的素数。素数：只能被素数：只能被1和它本身整除的自然数；否则为合数。和它本身整除的自然数；否则为合数。整数整数n的十进制位数的十进制位数 因子

32、分解的运算次数因子分解的运算次数 所需计算时间（每微秒一次）所需计算时间（每微秒一次）501.4x10103.9小时小时759.0 x1012104天天1002.3x101574年年2001.2x10233.8x109年年3001.5x10294.0 x1015年年5001.3x10394.2x1025年年对对RSA的攻击方法的攻击方法1、强力攻击（穷举法）：尝试所有可能的私强力攻击（穷举法）：尝试所有可能的私 有密钥有密钥2 2、数学分析攻击：各种数学方法，等价与两、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解个素数乘积的因子分解3 3、对对RSA实现的攻击实现的攻击对对RSA的

33、攻击的攻击 对对RSA的具体实现存在一些攻击方法，但不是的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。针对基本算法的，而是针对协议的。对对RSA的选择密文攻击的选择密文攻击 对对RSA的公共模攻击的公共模攻击 对对RSA的小加密指数攻击的小加密指数攻击 对对RSA的小解密指数攻击的小解密指数攻击 时间性攻击：取决于解密算法的运算时间时间性攻击：取决于解密算法的运算时间对对RSA的选择密文攻击的选择密文攻击 例例1：E监听监听A的通信，的通信，收集由收集由A的公开密钥加密的公开密钥加密的密文的密文c，E想知道消息想知道消息的明文的明文m,使使 m=cd mod n 他首先选择

34、随机数他首先选择随机数r,使使rn.然后用然后用A的公开密的公开密钥钥e计算计算 x=re mod n y=xc mod n t=r-1 mod n 如果如果x=re mod n，则，则 r=xd mod n现在现在E让让A对对y签名，即解密签名，即解密y,A向向E发送发送u=yd mod n而而E计算计算 tu mod n=r-1yd mod n=r-1xdcd mod n=cd mod n=m对对RSA的选择密文攻击的选择密文攻击 例例2：E 让让A对对m3签名。他产生两个消息签名。他产生两个消息m1和和m2，满足，满足 m3=m1m2(mod n)如果如果E能让能让A分别对分别对m1和和

35、m2签名，则可以计算签名，则可以计算m3：m3d=(m1d mod n)(m2d mod n)注意：不要用注意：不要用RSA对陌生人的随机文件签名，签名前对陌生人的随机文件签名，签名前先使用一个散列函数先使用一个散列函数对对RSA的公共模攻击的公共模攻击 一种可能的一种可能的RSA实现方实现方法是给每个人相同的法是给每个人相同的n,但但指数指数d和和e不同。不同。问题：如果相同的消息问题：如果相同的消息曾用两个不同的指数加曾用两个不同的指数加密，而这两个指数是互密，而这两个指数是互素的，则明文可以不用素的，则明文可以不用任何一个解密密钥来恢任何一个解密密钥来恢复。复。令令m为明文消息，两个加为

36、明文消息，两个加密密钥为密密钥为e1，e2,两个密两个密文消息为文消息为c1,c2c1=me1 mod nc2=me2 mod n由于由于e1和和e2互素，所以可互素，所以可以用扩展的以用扩展的Euclid算法找算法找到到r,s使使re1+se2=1,假设假设r是负数，可以用扩展是负数，可以用扩展的的Euclid算法计算算法计算c1-1,而而(c1-1)-r*c2s=m mod n注意注意:不要让一群用户共享一个模不要让一群用户共享一个模n 对对RSA的小加密指数攻击的小加密指数攻击 如果使用一个较小的如果使用一个较小的e值，则进行值，则进行RSA签名和加密会很签名和加密会很快，但也不安全。快

37、，但也不安全。如果用相同如果用相同e值的不同公开密钥加密值的不同公开密钥加密e(e+1)/2个线性相个线性相关的消息，则系统是可破的。如果有少于这些的消息关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。或消息不相关，则无问题。比如：消息为比如：消息为mj,使用同样的指数使用同样的指数e,模数分别为模数分别为q1,q2,qs（两两互素）（两两互素）,则密文为则密文为mjemod q1，mjemod q2，mjemod qs，根据中国剩余定理，根据中国剩余定理，m=mjemod q1 q2 qs.可以计算出来，对于较小的可以计算出来，对于较小的e，可以解出，可以解出mj。解决

38、办法：加密前将消息与随机值混合，并保证解决办法：加密前将消息与随机值混合，并保证m与与n有相同的长度。有相同的长度。对对RSA的小解密指数攻击的小解密指数攻击 使用较小的使用较小的d会产生穷尽解密攻击的可能会产生穷尽解密攻击的可能 当当d为为n的的1/4长度时，而长度时，而e小于小于n时，可以恢复时，可以恢复d，当当e,d是随机选择的时，这种情况很少发生，当是随机选择的时，这种情况很少发生，当e很小时不会发生。很小时不会发生。注意：应选择一个大的注意：应选择一个大的d值值RSA密码体制的实现密码体制的实现实现的步骤如下：实现的步骤如下：Bob为实现者为实现者(1)Bob寻找出两个大素数寻找出两

39、个大素数p和和q(2)Bob计算出计算出n=pq和和 (n)=(p-1)(q-1).(3)Bob选择一个随机数选择一个随机数e(0e (n)，满足（，满足（e，(n)）1(4)Bob使用辗转相除法计算使用辗转相除法计算d=e-1(mod (n)(5)Bob在目录中公开在目录中公开n和和e作为她的公开钥。作为她的公开钥。选好这些参数后，将明文划分成块，使得每个明文报文选好这些参数后，将明文划分成块，使得每个明文报文P长长度度m满足满足0mn。加密。加密P时，计算时，计算CPe(mod n)，解密，解密C时计时计算算PCd(mod n)。由于模运算的对称性，可以证明，。由于模运算的对称性，可以证明

40、，在确定的范围内，加密和解密函数是互逆的。在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开为实现加密，需要公开(e,n)，为实现解密需要，为实现解密需要(d,n)。实现要求实现要求 于是要求：若使于是要求：若使RSA安全，安全，p与与q必为足够大的必为足够大的素数，使分析者没有办法在多项式时间内将素数，使分析者没有办法在多项式时间内将n分分解出来。建议选择解出来。建议选择p和和q大约是大约是100位的十进制素位的十进制素数。数。模模n的长度要求至少是的长度要求至少是512比特。比特。EDI攻击攻击标准使用的标准使用的RSA算法中规定算法中规定n的长度为的长度为512至至1024比特

41、位之间，但必须是比特位之间，但必须是128的倍数。国际数的倍数。国际数字签名标准字签名标准ISO/IEC 9796中规定中规定n的长度位的长度位512比特位比特位.至至1996年，建议使用年，建议使用768位的模位的模n。素数的选取素数的选取 为了抵抗现有的整数分解算法，对为了抵抗现有的整数分解算法，对RSA模模n的的素因子素因子p和和q还有如下要求：还有如下要求：(1)|p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同；(2)p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1(3)P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2(4)p+1和和q+1分

42、别含有大素因子分别含有大素因子p3和和q3加密指数加密指数e的选取的选取 为了提高加密速度，通常取为了提高加密速度，通常取e为特定的小整数，为特定的小整数，如如EDI国际标准中规定国际标准中规定 e2161，ISO/IEC9796中甚至允许取中甚至允许取e3。这时加密速。这时加密速度一般比解密速度快度一般比解密速度快10倍以上。倍以上。e2161优于优于e3之处在于它能够抵抗对之处在于它能够抵抗对RSA的小加密指数攻击的小加密指数攻击实现中的问题实现中的问题 （1）如何计算）如何计算ab mod n（2）如何判定一个给定的整数是素数？）如何判定一个给定的整数是素数？（3）如何找到足够大的素数）

43、如何找到足够大的素数p和和q?(1)要点要点1：(a x b)mod n=(a mod n)x(b mod n)mod n 要点要点2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的问题：更一般性的问题：amm的二进制表示为的二进制表示为bkbk-1b0,则则 m=2ii 0c0;d 1for i k downto 0do c 2 x c d(d d)mod n if bi=1then c c+1 d (d a)mod nreturn d计算计算am mod nam mod n=a(2i)mod n =a(2i)mod nbi 0bi 0检测素数检测素数 直接判

44、断一个整数是否为素数是困难的直接判断一个整数是否为素数是困难的 命题命题:如果如果p是素数是素数,则方程则方程x2 1 mod p只有平凡解只有平凡解x 1 mod p.证明证明:x2 1 mod p p|(x2-1)p|(x+1)(x-1)p|(x+1),或者或者p|(x-1)x+1=kp,或者或者x-1=jp,k,j是整数是整数x=kp-1,或者或者x=jp+1x 1 mod p,或者或者x -1 mod p 若方程若方程x2 1 mod p存在的解不是存在的解不是x 1，则，则P不是素数。不是素数。(2)目前还没有一个高效的办法，实际中应用最多目前还没有一个高效的办法，实际中应用最多Mi

45、ller and Rabin,WITNESS算法算法WITNESS(a,n)判定判定n 是否为素数，是否为素数，a是某些小于是某些小于n的整数的整数1.令令bkbk-1b0 为为(n-1)的二进制表示，的二进制表示，2.d 13.for i k downto 04.do x d5.d (d d)mod n6.if d=1 and x 1 and x n-17.then return TRUE8.if bi=19.then d (d a)mod n10.if d 111.then return TRUE12.return FALSE 返回值：返回值：TRUE:n一定一定不是素数不是素数FALSE

46、:n可能是素数可能是素数应用：应用：随机选择随机选择a n,计算计算s次，次，如果每次都返回如果每次都返回FALSE，则这时则这时n是素数的概率为是素数的概率为(1-1/2s)(3)通常的办法是随机选取一个大的奇数，然后进行素性检验通常的办法是随机选取一个大的奇数，然后进行素性检验1.随机选一个奇数随机选一个奇数n(如如:可使用伪随机数发生器可使用伪随机数发生器)2.随机选择一个整数随机选择一个整数a n3.执行概率素数判定测试执行概率素数判定测试(如如:用用WITNESS(a,n),如果如果n 未测试通未测试通过过,则拒绝数值则拒绝数值n,转向步骤转向步骤14.如果如果n已通过足够的测试已通过足够的测试,则接受则接受n,否则转向步骤否则转向步骤2;说明：说明：随机选取大约用随机选取大约用 ln(N)/2的次数，如的次数，如 ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。好在生成密钥对时才用到，慢一点还可忍受。确定素数确定素数p和和q以后，只需选取以后，只需选取e,满足满足gcd(e,(n)=1,计算计算 d=e-1 mod (n)（sieve扩展的欧拉算法）扩展的欧拉算法）