第8章中国剩余定理和RSA算法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,8.4,中国剩余定理,8.4,中国剩余定理,定理,1-10,中国剩余定理,(CRT,：,Chinese Remainder Theorem),设,m,1,m,2,，,m,k,是两两互素的正整数，即：,(,m,i,m,j,)=1,，,ij,，,i,j=1,2,，,k,，则同余方程组：,Xb,1,mod m,1,Xb,2,mod m,2,Xb,k,mod,m,k,模,m,1,m,2,，,m,k,有惟一解，,xM,1,M,1,-1,b,1,+M,2,M,2,-1,b,2,+M,k,M,k,-1,b,k,mod m,m=m,1,m,2,m,k,M,i,=m/m,i,，,M,i,M,i,-1,1 mod m,i,例：,今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？,X2 mod 3,X3 mod 5,X2 mod 7,解：,问题归结为解,m=m,1,m,2,m,3,=3*5*7=105,M,1,=m/m,1,=105/3=35,M,2,=m/m,2,=105/5=21,M,3,=m/m,3,=105/7=15,M,1,M,1,-1,1 mod m,1,M,2,M,2,-1,1 mod m,2,M,3,M,3,-1,1 mod m,3,即：,35M,1,-1,1 mod 3,得：,M,1,-1,2,21M,2,-1,1 mod 5 M,2,-1,1,15M,3,-1,1 mod 7 M,3,-1,1,答案是：,三人同行七十稀,五树梅花廿一枝,七子团圆月正半,除百零五便得知,xM,1,M,1,-1,b,1,+M,2,M,2,-1,b,2,+M,3,M,3,-1,b,3,70 b,1,+21 b,2,+15 b,3,mod 105,70*2+21*3+15*2 mod 105,23 mod 105,第,9,章公钥密码学与,RSA,公钥密码学与以前的密码学完全不同。首先，公钥算法是基于数学函数而不是基于替换、置换等运算，更重要的是，与只使用一个密钥的对称传统密码不同，公钥密码是非对称的，它使用两个独立的密钥（公钥和私钥）。,9.1,公钥密码体制的基本原理,9.1.1,公钥密码体制,公钥密码体制的特点：,仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的。,有些公钥密体制还有如下特点：,两个密钥中的任何一个都可用来加密，另一个用来解密。,9.1.2,公钥密码体制的应用,加密,/,解密,:,发送方用接收方的公钥对消息加密。,数字签名：,发送方用其私钥对消息“签名”。签名可以通过对整条消息加密或者对消息的一个小的数据块加密来产生。其中该小数据块是整条消息的函数。,密钥交换：,通信双方交换会话密钥。,单向陷门函数的定义：,一个函数，若计算函数值很容易，并且在缺少一些附加信息时计算函数的逆是不可行的，但是已知这些附加信息时，可在多项式时间内计算函数的逆，那么我们称这样的函数为单向陷门函数。即单向陷门函数是满足下列条件的一类不可逆函数,f,k,若,k,和,X,已知，则容易计算,Y=,f,k,(X,),。,若,k,和,Y,已知，则容易计算,X=f,k,-1,(Y),若,Y,已知但,k,未知，则计算,X=f,k,-1,(Y),是不可行的。,1976,年,9,月，一篇题为,“,New Directions in Cryptography(,密码术的新方向,)”,的文章，打破了几千年来对称密码技术的垄断局面，开辟了现代密码技术的新领域,公钥密码技术。这篇文章是一个名叫,Whitfield,Diffie,的自学成才的的密码学专家和一个与他兴趣相投的斯坦福大学学生,Hellman,共同发表的。其中阐述了一种实用的密钥交换技术，解决了在对称密码技术中一直困扰人们的密钥传递问题，这就是著名的,Diffie-Hellman,(,简称,DH),密码技术,（以后再介绍）。,但,Diffie-Hellman,的开创性论文却引起了美国麻省理工学院（,MIT,）的年青教授,Ron,Rivest,对公钥加密技术的极大兴趣，他下决心要开发一个最终的公钥加密技术。于是他邀请两位同事,Adi,Shamirt,和,Len,Adleman,一起来解决这个问题。,1977,年，三人开发出了一个能够真正加密数据的公钥加密算法，并于,1978,年在一篇题为“,A Method for Obtaining Digital Signatures and Public Key Cryptosystems(,获取数字签名和公钥加密系统的方法,)”,中公开了这个算法，这就是著名的,RSA,算法（以三位发明者名字的首字母缩写命名）。,RSA,先后被,ISO,、,ITU,、,SWIFT,等国际化标准组织采用作为标准。,RSA,密码体制描述,参数的构成,:,（,1,）选取两个不同的大素数,p,、,q,。,（,2,）计算,n,：,n=,pq,和,(n)=,（,p-1,）,(q-1),（,3,）随机选取,e,，使,e,满足,1e(n),，且（,e,(n,),）,=1,那么公钥就是,(e,，,n),(4),计算,d,：满足,ed1(mod,(n,),那么私钥就是,(d,，,n),(5),销毁,p,、,q,、,(n,),；自己保存好私钥,(d,，,n),；公开公钥,(,e,n,).,明文和密文空间就是,0,到（,n-1,）之间的整数值。,加密,:,Cm,e,mod n,这里，,m,是明文，,C,是密文,解密,:,mC,d,mod n.,使用,RSA,算法要满足：,mn,举例：,（,1,）构造用户,A,的参数：,p=5 q=11,n=,pq,=55,(n)=,（,p-1,）,(q-1)=410=40,选择一个整数,e,，使,e,与,(n,),互素。现选择,e=17,公钥为（,e,，,n,），即（,17,，,55,）,从,ed1 mod,(n,),即,17d1 mod 40,中求得,d,，解得,d=33,。,私钥（,d,，,n,）即为（,33,，,55,）。,（,2,）假如,B,想把明文,m=25,发给,A,，那么他就利用公式,C=m,e,mod n,把明文,m,加密成密文,C,，即,C=m,e,mod n=25,17,mod 55=20,并把,C=20,发送给,A,。,（,3,）,A,收到密文,C,后，利用公式,m=,C,d,mod,n,把密文,C,恢复成明文,m,。即,m=,C,d,mod,n=,20,33,mod 55=25,A,把,B,发给他的密文,C=20,恢复为明文,m=25,。,课堂练习：,p=11,q=7,e=13,，问私钥是什么，若加密明文,m=10,，则对应的密文是什么？,（,1,）,RSA,算法原理基于,Euler,定理及大数分解的困难性,下面证明,RSA,解密过程的正确性：,DC,C,d,m,ed,(mod,n),（,1,）,ed 1 mod,(n,),ed=1+k(n),这里,k,是整常数，代入（,1,）有,DC,m,ed,(mod,n)m,1+,k(n,),（,mod n,）,=,m.(m,(n),),k,(mod,n),（,2,）,RSA,算法分析,若（,m,，,n,）,=1,，由,Euler,定理有,m,(n,),1,（,mod n,），即,DC m,。,若（,m,，,n,）,1,，又,n=,pq,，由素数性质得,（,m,n,）,=p,或,q,。,假设,（,m,，,n,）,=p,有,m=sp,这里,s,是正整数,1mn,，,1sq,(,p,q,)=1,(s,q)=1,又,p,、,q,都是素数，故,从而,(,sp,q,)=1,即（,m,，,q,）,=1,由,Euler,定理有,m,(q,),1 mod q,于是,（,m,(q,),）,k(p),1 mod q,写成,m,k(n,),1 mod q,或,m,k(n,),=1+jq,这里,j,是正整数,由（,2,）式有,DC,m.(m,(n),),k,(mod,n),m(1+jq),m+mjqm+spjq,=,m+sjnm(mod,n),即,DC=m,(2)m,e,mod n,是将明文以指数形式表示出来，或者说以指数形式将明文隐藏起来。,(3),如果攻击者设法得到了一个明、密文对（,m,c,）,他想得到解密密钥,d,，则必须在,Zn=1,2,，,n-1,中求解（离散）对数问题：,d=,log,c,m,这是一个困难问题。,(4),加密、解密过程中的主要运算是,Zn,中的幂运算。由于,n,可能非常大，所以模,n,的幂运算的效率就成为算法效率的关键。,（,5,）在找到一个可用的数，即与,(n,),互素的数之前，要测试多少个随机数呢？可以很容易地证明，两个随机数互素的概率约为,0.6,。,*,计算方面的问题,运用中国剩余定理可以加快运算速度。,先计算一些中间结果：,V,p,C,d,mod p V,q,C,d,mod q,X,p,qq,-1,mod p X,q,pp,-1,mod q,M(V,p,X,p,+V,q,X,q,)mod n,进一步，可以用费马定理来简化计算,V,p,C,d,mod pC,d,mod(p-1),mod p,V,q,C,d,mod qC,d,mod(q-1),mod q,RSA,的安全性,对,RSA,算法的攻击可能有如下四种方式：,穷举攻击,：这种方法试图穷举所有可能的私钥；,数学攻击：,有多种数学攻击方法，它们的实质都是试图分解两个素数的乘积；,计时攻击,：这类方法依赖于解密算法的运行时间；,选择密文攻击,：这种攻击利用了,RSA,算法的性质。,因子分解问题,用数学方法攻击,RSA,的途径有以下三种：,分解,n,为两个素因子,。这样就可以计算出,(n,)=,（,p-1,）（,q-1,），从而可以确定,d,e,-1,(mod,(n,),),。,直接确定,(n),而不先确定,p,和,q,。,直接确定,d,，而不先确定,(n),。,对,RSA,的密码分析的讨论大都集中于第一种攻击方法，即分解,n,。在选择,RSA,的,n,时，密钥大小在,1024,至,2048,位范围内是合适的。,除了要指定,n,的大小外，研究者还提出了其他一些限制条件：,p,和,q,的长度应仅相差几位。这样对,1024,位（,309,个十进制位）的密钥而言，,p,和,q,都应约在,10,75,到,10,100,之间。,（,p-1,）和（,q-1,）都应有一个大的素因子。,（,p-1,，,q-1,）应该较小。,另外，已经证明，若,en,且,dn,1/4,，则,d,很容易被确定。,计时攻击,攻击者可以通过记录计算机解密消息所用的时间来确定私钥。,解决方法：,不变的幂运算时间,随机延时,隐蔽,*,选择密文攻击和最佳非对称加密填充,基本的,RSA,算法易受选择密文攻击（在此不深入讲解），可以采用最佳非对称加密填充（,OAEP,）来解决：,第一步，待加密的消息,M,被填充。可选参数集,P,作为散列函数,H,的输入，输出用,0,加以填充以获得期望的长度，从而可以放入整体数据块（,DB,）内。,第二步，随机选择一个种子，并作为一个散列函数的输入，该散列函数称为掩码生成函数（,MGF,）。输出散列值和,DB,进行按位异或运算产生掩码,DB,（,maskedDB,）。,第三步，该,maskedDB,反过来又作为,MGF,的输入产生一个散列值，该散列值和种子进行异或运算产生掩码种子。掩码种子和掩码,DB,连接起来构成加密后的消息,EM,。注意，,EM,包含填充过的消息，该消息由种子进行隐蔽，而种子又由,maskedDB,进行隐蔽。最后用,RSA,对整个,EM,进行加密。,课后习题：,1.,韩信点兵的故事。今有兵员不知其数，每五个数之，剩下,1,人；每六个数之，剩下,5,人；每七人数之，剩下,4,人；每十一人数之，剩下,10,人，问兵员多少？,*编写中国剩余定理算法程序。,2.,什么是单向陷门函数？,3.P201 9.2 a,b,9.3,