《第五讲 公钥密码体制》由会员分享，可在线阅读，更多相关《第五讲 公钥密码体制（91页珍藏版）》请在金锄头文库上搜索。
1、1Chapter 8 Number Theory and RSA公开密钥密码学公开密钥密码学计算机学院孟博2Chapter 8 Number Theory and RSA内内 容容q数论简介数论简介q公钥密码学公钥密码学qRSARSA算法算法3Chapter 8 Number Theory and RSAl 素数和互素l 模运算l 费尔玛定理l 欧拉函数l 中国剩余定理l 离散对数数论简介数论简介4Chapter 8 Number Theory and RSA素数和互素数素数和互素数数论简介数论简介1. 因子因子设设a，b(b0)是两个整数，如果存在另一整数是两个整数，如果存在另一整数m，使得
2、使得a=mb，则称则称b整除整除a，记为记为b|a，且称且称b是是a的因子。的因子。5Chapter 8 Number Theory and RSA2. 素数素数称整数称整数p(p1)是素数，如果是素数，如果p的因子只有的因子只有1，p。任一整数任一整数a(a1)都都能能唯一唯一地分解为以下形式地分解为以下形式(这一性质称为整数分解的惟一性这一性质称为整数分解的惟一性)： 其中其中p1p2pt是素数，是素数，ai0(i=1,t)。例如例如:91=7136Chapter 8 Number Theory and RSA3. 互素称c是两个整数a、b的最大公因子，如果 c是a的因子也是b 的因子，即
3、c是a、b的公因子。 a和b的任一公因子，也是c的因子。表示为c=gcd(a, b)。如果gcd(a,b)=1，则称a和b互素。7Chapter 8 Number Theory and RSA设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0rd。Euclid（f, d）1. Xf; Yd；2. if Y=0 then return X=gcd(f,d)；3. R=X mod Y；4. X=Y；5. Y=R；6. goto 2。21Chapter 8 Number Theory and RSA求gcd(1970, 1066)。1970=11066+904, gcd(
4、1066, 904)1066=1904+162,gcd(904, 162)904=5162+94,gcd(162, 94) 162=194+68,gcd(94, 68) 94=168+26, gcd(68, 26)68=226+16, gcd(26, 16) 26=116+10, gcd(16, 10) 16=110+6, gcd(10, 6) 10=16+4,gcd(6, 4)6=14+2,gcd(4, 2) 4=22+0,gcd(2, 0)因此gcd(1970, 1066)=2。22Chapter 8 Number Theory and RSA2. 求乘法逆元如果gcd(a, b)=1 ，
5、则b在mod a下有乘法逆元（不妨设ba），即存在一x (x512bits) security relies on hard problems more generally the hard problem is known, but is made hard enough to be impractical to break requires the use of very large numbers hence is slow compared to private key schemes56Chapter 8 Number Theory and RSARSA by Rivest, Sha
6、mir & Adleman of MIT in 1977 best known & widely used public-key scheme uses large integers (eg. 1024 bits) security due to cost of factoring large numbers l nb. factorization takes O(e log n log log n) operations (hard)57Chapter 8 Number Theory and RSARSA Key Setupeach user generates a public/priva
7、te key pair by: selecting two large primes at random : p, q computing their system modulus n=pql note (n)=(p-1)(q-1) selecting at random the encryption key el where 1e(n), gcd(e,(n)=1 solve following equation to find decryption key d l ed= 1 mod (n) and 0dn publish their public encryption key: PU=e,
8、n keep secret private decryption key: PR=d,n58Chapter 8 Number Theory and RSAFigure 9.5 RSA setup59Chapter 8 Number Theory and RSARSA Use to encrypt a message M the sender:l obtains public key of recipient PU=e,n l computes: C = Me mod n, where 0Mn to decrypt the ciphertext C the owner:l uses their
9、private key PR=d,n l computes: M = Cd mod n note that the message M must be smaller than the modulus n (block if needed)60Chapter 8 Number Theory and RSAFigure 9.5 RSA encryption and decryption61Chapter 8 Number Theory and RSARSA Example - Key Setup1.Select primes: p=17 & q=112.Compute n = pq =17 x
10、11=1873.Compute (n)=(p1)(q-1)=16 x 10=1604.Select e: gcd(e,160)=1; choose e=75.Determine d: de=1 mod 160 and d 160 Value is d=23 since 23x7=161= 10x160+16.Publish public key PU=7,1877.Keep secret private key PR=23,18762Chapter 8 Number Theory and RSARSA Example - En/Decryptionsample RSA encryption/d
11、ecryption is: given message M = 88 (nb. 88187) encryption:C = 887 mod 187 = 11 decryption:M = 1123 mod 187 = 8863Chapter 8 Number Theory and RSAFigure 9.6 Example of RSA Algorithm64Chapter 8 Number Theory and RSA E E和和D D的可逆性的可逆性要证明：D(E(M)=M MCd (Me)dMed mod n因为ed1 mod(n)，这说明edt(n)+1,其中t为某整数。所以， Med
12、 Mt(n)+1 mod n 。因此要证明 Med M mod n ，只需证明 M t(n)+1 M mod n 。RSA算法论证算法论证65Chapter 8 Number Theory and RSA在gcd（M，n）1的情况下，根据数论， M t(n) 1 mod n ，于是有， M t(n)+1 M mod n 。66Chapter 8 Number Theory and RSA在gcd（M，n）1的情况下，分两种情况：第一种情况：M1,2,3,n-1 因为n=pq，p和q为素数， M1,2,3,n-1，且（M，n）1 。 这说明M必含p或q之一为其因子，而且不能同时包含两者，否则将有
13、Mn，与M1,2,3,n-1矛盾。67Chapter 8 Number Theory and RSA不妨设Map 。又因q为素数，且M不包含q，故有（M，q）1， 于是有，M (q) 1 mod q 。进一步有，M t(p-1)(q) 1 mod q。 因为q是素数，(q)（q-1），所以t(p-1)(q)t(n)，所以有 M t(n) 1 mod q。68Chapter 8 Number Theory and RSA于是，M t(n) bq+1，其中b为某整数。两边同乘M， M t(n)+1 bqM+M 。因为Map，故 M t(n)+1 bqap+M =abn+M 。取模n得， M (n)
14、+1 M mod n 。69Chapter 8 Number Theory and RSA第二种情况：M0当M0时，直接验证，可知命题成立。70Chapter 8 Number Theory and RSA加密和解密运算的可交换性 D(E(M)=(Me)d =Med =(Md)e =E(D(M) mod n所以，RSA密码可同时确保数据的秘密性和数据的真实性。加解密算法的有效性 RSA密码的加解密运算是模幂运算，有比较有效的算法。71Chapter 8 Number Theory and RSA在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于
15、大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这一时间下限将不低于O（EXP（lnNlnlnN）1/2）。根据这一结论，只要合数足够大，进行因子分解是相当困难的。72Chapter 8 Number Theory and RSA 假设截获密文C，从中求出明文M。他知道 MCd mod n ， 因为n是公开的，要从C中求出明文M，必须先求出d，而d是保密的。但他知道， ed1 mod (n)e是公开的，要从中求出d，必须先求出(n)，而(n)是保密的。73Chapter 8 Number Theory and RSA但他又知道， (n)=(p-1)(q-
16、1)要从中求出(n)，必须先求出p和q，而p和q是保密的。但他知道， n=pq要从n求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的。74Chapter 8 Number Theory and RSA 只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破译破译RSARSA密码的困难性密码的困难性 对对n n因子分解的困难性。因子分解的困难性。目前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。75Chapter 8 Number Theory and RSA1 1、参数选择、参数选择为了确保RSA密码的安全，必须认真选
17、择密码参数： p p和和q q要足够大；要足够大； 一般应用：一般应用：p p和和q q应应 512 512 位位. .重要应用：重要应用：p p和和q q应应 1 1024 024 位位 因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（102002664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。RSA密码的实现密码的实现7
18、6Chapter 8 Number Theory and RSAp p和和q q应为强素数应为强素数文文献献指指出出，只只要要(p-1)(p-1)、(p+1)(p+1)、(q-1)(q-1)、(q+1)(q+1)四四个个数数之之一一有有小小的的素素因因子，子，n n就容易分解。就容易分解。 p p和和q q的差要大；的差要大；（p-1p-1）和（和（q-1q-1）的最大公因子要小。的最大公因子要小。如果（如果（ p-1p-1）和（和（q-1q-1）的最大公因子太大，则易受的最大公因子太大，则易受迭代加密攻击迭代加密攻击77Chapter 8 Number Theory and RSA若 ，即
19、，则有 ，即 ，所以在上述重复加密的倒数第2步就已恢复出明文m，这种攻击法只有在t较小时才是可行的。为抵抗这种攻击，p、q的选取应保证使t很大。78Chapter 8 Number Theory and RSA 设m在模n下阶为k，由 得 ，所以k|(et-1)，即et1(mod k)，t取为满足上式的最小值（为e在模k下的阶）。又当e与k互素时t|(k)。 为使t大，k就应大且(k)应有大的素因子。又由k|(n)，所以为使k大，p-1和q-1都应有大的素因子。 此外，研究结果表明，如果en且dn1/4，则d能被容易地确定。79Chapter 8 Number Theory and RSA e
20、 e的选择的选择 随机且含随机且含1 1多就安全多就安全.有的学者建议取有的学者建议取e e2 21616+1+16553765537 d d的选择的选择 d d要足够大要足够大 不要许多用户共用一个模不要许多用户共用一个模 n n；易受共模攻击易受共模攻击80Chapter 8 Number Theory and RSA2 2、大素数的产生、大素数的产生 概率性算法产生概率性算法产生 目目前前最最常常用用的的概概率率性性算算法法是是MillerMiller检检验验算算法法。MillerMiller检检验验算算法法已已经经成为美国的国家标准。成为美国的国家标准。 确定性算法产生确定性算法产生q
21、q 确定性测试确定性测试 qq 确定性构造确定性构造81Chapter 8 Number Theory and RSA3 3、大素数的运算、大素数的运算 反复平方乘算法反复平方乘算法 快速模乘算法快速模乘算法qq 反反复复平平方方乘乘算算法法解解决决了了快快速速乘乘方方取取模模的的问问题题，仍仍未未解解决决快快速速模模乘乘的的问题；问题；qq MontgomeryMontgomery算法是一种快速模乘的好算法；算法是一种快速模乘的好算法；qq 将以上两种算法结合成为实现将以上两种算法结合成为实现RSARSA密码的有效方法。密码的有效方法。qq 硬件协处理器是提高运算效率的有效方法。硬件协处理器
22、是提高运算效率的有效方法。82Chapter 8 Number Theory and RSA RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。如果RSA的模数n被成功地分解为pq，则立即获得(n)=(p-1)(q-1)，从而能够确定e模(n)的乘法逆元d，即de-1 mod (n)，因此攻击成功。RSA的安全性的安全性83Chapter 8 Number Theory and RSA 随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。例如RSA-129（即n为129位十进制数，大约428
23、个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解。84Chapter 8 Number Theory and RSA 对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分解。而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA130时所做的计算仅比分解RSA-129多10%。将来也可能还有更好的分解算法，因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是
24、安全的。85Chapter 8 Number Theory and RSA对对RSA的攻击的攻击RSA存在以下存在以下7种攻击，有的并不是因为算法本身存在缺陷，而是由种攻击，有的并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。于参数选择不当造成的。1. 共模攻击共模攻击在实现在实现RSA时，为方便起见，可能给每一用户相同的模数时，为方便起见，可能给每一用户相同的模数n，虽然加虽然加解密密钥不同，然而这样做是不行的。解密密钥不同，然而这样做是不行的。86Chapter 8 Number Theory and RSA设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明
25、文消息是m，密文分别是c1me1 (mod n)c2me2(mod n)敌手截获c1和c2后，可如下恢复m。因为GCD(e1,e2)=1,可以先计算 最后计算87Chapter 8 Number Theory and RSA2. 低指数攻击假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni(i=1,2,3)，当ij时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。他们的公钥分别是（ n1 ，3 3），（ n2 ，3 3），（ n3 ，3 3），设明文消息是m,则密文Ci=m3 m
26、od ni, ，则c1 (mod n1)m3c2 (mod n2)m3c3 (mod n3)m3由中国剩余定理可求出m3(mod n1n2n3)。由于mni ，m3n1n2n3，可直接由m3开立方根得到m。88Chapter 8 Number Theory and RSA3.选择密文攻击RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装 (Blind)，让拥有私钥的实体签名。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： 这个固有的问题来自于公钥密码系统的最有用的特征 -每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有 两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体 意产生的信息解密，不对自己一无所知的信息签名；另一条是决不 对陌生人送来的随机文档签名。89Chapter 8 Number Theory and RSA90Chapter 8 Number Theory and RSA4. 计时攻击 攻击者可以通过记录计算机解密消息所用的时间来确定私钥。5. 暴力破解6. 数学攻击7. 明文数据过短91Chapter 8 Number Theory and RSA谢 谢 !
