第6章RSA密码信息理论密码学加密演算法邓安文.ppt

1.1 2006第第第第6 6章章章章 RSA RSA密码密码密码密码第6章RSA密码信息理论密码学加密演算法邓安文 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望1.2 2006第第第第6 6章章章章 RSA RSA密码密码密码密码教学目的教学目的了解公开密匙密码系统了解公开密匙密码系统了解公开密匙密码系统了解公开密匙密码系统了解了解了解了解RSARSARSARSA算法、数论背景和数字签名算法、数论背景和数字签名算法、数论背景和数字签名算法、数论背景和数字签名了解了解了解了解二次筛法与二次筛法与二次筛法与二次筛法与PollardPollard的的的的p-1p-1法法法法了解了解了解了解利用利用利用利用RSARSA私钥因数分解私钥因数分解私钥因数分解私钥因数分解 了解了解了解了解WienerWiener低幂次低幂次低幂次低幂次d d攻击攻击攻击攻击 了解了解了解了解RabinRabin密码密码密码密码1.3 2006第第第第6 6章章章章 RSA RSA密码密码密码密码 公开密钥密码系统公开密钥密码系统公开密钥密码系统公开密钥密码系统本章内容本章内容本章内容本章内容 RSARSA算法算法算法算法 RSARSA的数论背景的数论背景的数论背景的数论背景 RSARSA数字签名数字签名数字签名数字签名 同时进行同时进行同时进行同时进行RSARSA加密和加密和加密和加密和RSARSA数字签名数字签名数字签名数字签名 RSA-129RSA-129挑战与因数分解挑战与因数分解挑战与因数分解挑战与因数分解1.4 2006第第第第6 6章章章章 RSA RSA密码密码密码密码 二次筛法与二次筛法与二次筛法与二次筛法与PollardPollard的的的的p-1p-1法法法法本章内容本章内容本章内容本章内容 利用利用利用利用RSARSA私钥因数分解私钥因数分解私钥因数分解私钥因数分解 RSARSA密码系统实用的注意事项密码系统实用的注意事项密码系统实用的注意事项密码系统实用的注意事项 WienerWiener低幂次低幂次低幂次低幂次d d攻击攻击攻击攻击 RabinRabin密码密码密码密码1.5 2006第第第第6 6章章章章 RSA RSA密码密码密码密码公开密匙密码系统公开密匙密码系统6.1 公开密匙密码系统（1 1）将一已加密的信息）将一已加密的信息mm解密，即可还原解密，即可还原mm，即，即（2 2）加密以及解密函数）加密以及解密函数 、必须是容易计算的。必须是容易计算的。（3 3）公开加密函数）公开加密函数 ，并不会提供任何简易计算解密函数，并不会提供任何简易计算解密函数 的方的方法，在实际应用中，这意味着只有法，在实际应用中，这意味着只有BobBob才能将任何经加密函数才能将任何经加密函数 加密加密的信息有效地解密，也只有的信息有效地解密，也只有BobBob知道知道“陷门陷门”（TrapdoorTrapdoor）从而有效计算）从而有效计算 。（4 4）若将任何信息）若将任何信息mm先用解密函数运算，再用加密函数运算，亦可还原信先用解密函数运算，再用加密函数运算，亦可还原信息息mm，即，即 定义 单向陷门函数，单向陷门函数，Trapdoor One-Way Function Trapdoor One-Way Function 函数函数 若满足性质（若满足性质（1 1）、（）、（2 2）、（）、（3 3），就称为单向陷门函数，），就称为单向陷门函数，若性质（若性质（1 1）、（）、（2 2）、（）、（3 3）、（）、（4 4）皆满足，就称为单向陷门置换）皆满足，就称为单向陷门置换（Trapdoor One-Way PermutationTrapdoor One-Way Permutation）。）。1.6 2006第第第第6 6章章章章 RSA RSA密码密码密码密码数字封装数字封装1.7 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA算法算法6.2 RSA算法密匙产生：密匙产生：BobBob取相异质数取相异质数p p、q q（保密），计算（保密），计算RSARSA模数（模数（RSA ModulusRSA Modulus）n=pqn=pq，将其公开，取，将其公开，取e e为加密密钥将其公开，其中为加密密钥将其公开，其中e e必须与必须与(n)(n)互质，在此情况下，互质，在此情况下，BobBob的公开密钥为的公开密钥为(n,e)(n,e)；BobBob计算计算d d为解密密钥（保密），为解密密钥（保密），(n,d)(n,d)为为BobBob的私钥的私钥（Private KeyPrivate Key）其中）其中加密：加密：AliceAlice取得取得BobBob的公开密钥的公开密钥(n,e)(n,e)，用加密函数计算，用加密函数计算 将密文将密文c c传给传给BobBob。解密：解密：BobBob用解密函数计算用解密函数计算 解密还原成明文。解密还原成明文。1.8 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA算法举例算法举例l 密匙产生密匙产生BobBob取质数取质数p=241p=241、q=311q=311，计算，计算n=pq=74951n=pq=74951，取取e=1033e=1033为加密钥，在此情况为加密钥，在此情况 ，BobBob的公开密钥为的公开密钥为(n,e)=(74951,1033)(n,e)=(74951,1033)；BobBob用用广义辗转相除法计算解密密钥广义辗转相除法计算解密密钥 1.9 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA算法举例算法举例l加密加密AliceAlice的明文的明文（令（令a=0a=0、b=1b=1、z=25z=25），取得），取得BobBob的公开密钥为的公开密钥为 ，加密得密文，加密得密文 1.10 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA算法举例算法举例l解密解密所以所以1.11 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA的数论背景的数论背景6.3 RSA的数论背景 Euler定理 令整数令整数a a、n n，其中，其中a a与与n n互质。则互质。则 EulerEuler定理推广了费马小定理定理推广了费马小定理 定理 令整数令整数a a、n n，其中，其中a a与与n n互质。则互质。则 1.12 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA加密解密函数加密解密函数 定理 RSARSA加密解密函数加密解密函数 令令p p、q q为相异质数，令为相异质数，令n=pqn=pq，令，令e e为与为与(p-1)(q-1)(p-1)(q-1)互质的整数，互质的整数，令令d d满足满足 令加密函数令加密函数 ，解密函数，解密函数 则对所有整数则对所有整数mm皆满足皆满足 且且1.13 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA修订版修订版令令AliceAlice想将明文想将明文mm加密成密文加密成密文c c传至传至BobBob，而，而BobBob将密文将密文c c解密还解密还原成明文原成明文mm。密匙产生密匙产生BobBob取相异质数取相异质数p p、q q（保密），计算（保密），计算RSARSA模数模数n=pqn=pq，将其公开，将其公开，取取e e为密钥将其公开，其中为密钥将其公开，其中e e必须与必须与 互质，互质，BobBob的公开密钥为的公开密钥为(n,e)(n,e)；计算；计算 加密加密AliceAlice取得取得BobBob的公开密钥的公开密钥(n,e)(n,e)，用加密函数计算，用加密函数计算 将密文将密文c c传给传给BobBob。解密解密BobBob有两种解密计算方式：一是有两种解密计算方式：一是 以及用中国余式定理加速解密以及用中国余式定理加速解密 BobBob的私钥为的私钥为 1.14 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA数论背景数论背景 定理对所有整数对所有整数mm皆满足皆满足 且且证明：证明：若若q|mq|m，此时，此时 同理可得：同理可得：再用中国余式定理得再用中国余式定理得 (某整数某整数K K1 1)(某整数K2）)1.15 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA数字签名数字签名6.4 RSA数字签名RSARSA数字签名是一种可回复式数字签名法（数字签名是一种可回复式数字签名法（Recovery SchemeRecovery Scheme）BobBob利用利用RSARSA密码系统，数字签名一简短的文件密码系统，数字签名一简短的文件 ，并传递给他所有认识的人。并传递给他所有认识的人。例：1.16 2006第第第第6 6章章章章 RSA RSA密码密码密码密码密匙产生密匙产生 密匙产生密匙产生BobBob的的RSARSA密钥为密钥为 其中其中RSARSA模数模数 加密密钥为加密密钥为e=31e=31，解密密钥为，解密密钥为 1.17 2006第第第第6 6章章章章 RSA RSA密码密码密码密码数字签名数字签名 数字签名数字签名假设代码空白假设代码空白=0=0、a=1a=1、b=2b=2、z=26z=26，又，又 故以全文为一组编码，得代码故以全文为一组编码，得代码 再以解密函数再以解密函数 分别对此代码分别对此代码“数字签名数字签名”并将并将“数字签名数字签名”传给所有她想要传送的人。传给所有她想要传送的人。1.18 2006第第第第6 6章章章章 RSA RSA密码密码密码密码签名还原签名还原 签名还原签名还原AliceAlice收到了收到了BobBob的的“数字签名数字签名”，经过计算，经过计算 1.19 2006第第第第6 6章章章章 RSA RSA密码密码密码密码同时同时RSARSA加密和加密和RSARSA签名签名6.5 同时RSA加密和RSA签名1.20 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSA-129RSA-129挑战与因数分解挑战与因数分解6.6 RSA-129挑战与因数分解 例：BobBob的的RSARSA公开密钥为公开密钥为(n,e)=(782741,7)(n,e)=(782741,7)。攻击者。攻击者EveEve截收截收到到AliceAlice传给传给BobBob的密文的密文144310144310，并知道，并知道AliceAlice与与BobBob的通信的通信代码为：代码为：a=0 a=0、b=1b=1、c=2c=2、z=25z=25。计算计算 ，知道每，知道每4 4个字母为一组代码。如个字母为一组代码。如果果EveEve知道知道n n的质因数分解，即知道是何质数的质因数分解，即知道是何质数p p、q q 使得使得pq=782741pq=782741，就，就可计算可计算 ，再以广义辗转相除法或，再以广义辗转相除法或xeuclidean()xeuclidean()程序计算程序计算得解密密钥得解密密钥便可还原明文的代码便可还原明文的代码 1.21 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSA-129RSA-129挑战与因数分解挑战与因数分解如何找到质因数如何找到质因数p p、q q使得抛弃使得抛弃782741782741？EveEve试着从试着从2 2到小于等于到小于等于 的质数试除，（共计有的质数试除，（共计有153153个质数）在第个质数）在第150150个质数时发现个质数时发现因此，因此，。以广义辗转相除法得。以广义辗转相除法得 所以明文代码为所以明文代码为 而而因此因此明文明文为为“help”“help”。1.22 2006第第第第6 6章章章章 RSA RSA密码密码密码密码质数分解的记录质数分解的记录年份十进制的位数备注19642019744519836922511用二次筛法1989106用二次筛法1994129RSA-129用二次筛法1996130RSA-130用代数数体筛法1999155RSA-155用代数数体筛法1.23 2006第第第第6 6章章章章 RSA RSA密码密码密码密码二次筛法二次筛法PollardPollard的的p p1 1法法 6.7 二次筛选法Pollard的p-1法 定义 B-smooth B-smooth 令令B B为某若干质数与为某若干质数与-1-1所形成的集合。令所形成的集合。令x x为一整数：称为一整数：称x x为为 B-smooth x B-smooth x的质因子均在集合的质因子均在集合B B中。中。1.24 2006第第第第6 6章章章章 RSA RSA密码密码密码密码利用利用RSARSA私钥因数分解私钥因数分解 6.8 利用RSA私钥因数分解 例：假设假设AliceAlice的的RSARSA密钥为密钥为 AliceAlice自行因数分解自行因数分解n n如下：如下：（1 1）随机找一个整数）随机找一个整数 很正常地很正常地 （2）计算计算计算1.25 2006第第第第6 6章章章章 RSA RSA密码密码密码密码教学目的教学目的（3 3）计算）计算计算计算（4）因此其中一个因数为 而另一个因数为1.26 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA密码系统使用的注意事项密码系统使用的注意事项 6.9 RSA密码系统使用的注意事项 通用模数协议错误，通用模数协议错误，Common Modulus Protocol Failure Common Modulus Protocol Failure 令令mm为明文，假设为明文，假设AliceAlice欲将此明文分别利用欲将此明文分别利用RSARSA加密传讯给加密传讯给BobBob以及以及CarlCarl，她取得的公开密钥分别是她取得的公开密钥分别是(n,e(n,eB B)以及以及(n,e(n,eC C)，当中两组，当中两组RSARSA模数模数n n是相同的。是相同的。解密解密首先两把加密密钥首先两把加密密钥e eB B与与e eC C以极高的概率是互质的，即以极高的概率是互质的，即 ，不互质的概率微乎其微。此时不互质的概率微乎其微。此时EveEve只需要使用广义辗转相除法或程只需要使用广义辗转相除法或程序序xeuclidean()xeuclidean()，便可求出整数，便可求出整数s s、t t使得：使得：如此如此1.27 2006第第第第6 6章章章章 RSA RSA密码密码密码密码低幂次低幂次e e攻击攻击 低幂次低幂次e e攻击攻击 由中国余式定理，只需要计算由中国余式定理，只需要计算x x1 1、x x2 2、x x3 3满足满足 解得解得令令因此：因此：1.28 2006第第第第6 6章章章章 RSA RSA密码密码密码密码循环攻击循环攻击循环攻击，Cycling Attack 循环攻击就是将密文循环攻击就是将密文c c多次用加密函数作用，直至多次用加密函数作用，直至此时 广义循环攻击，则是将密文广义循环攻击，则是将密文c c多次用加密函数作用，直至多次用加密函数作用，直至1.29 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RSARSA密码系统使用的注意事项密码系统使用的注意事项u 绝对不可泄漏RSA密码系统的任何参数：p、q、一个，这与公开自己的私钥无异。u使用RSA数字签名，建议先使用Hash函数，以防止利用其乘法代数性质伪造数字签名。u绝对不要使用相同的RSA模数犯下相同模数协议的错误。u加密密钥的长度不得少于RSA模数长度的1/4 u另外因为数论家在因数分解上的进展，为防止n被质因数分解，也应考虑以下建议：1 1）p p、q q的大小，长度应有数字之差。的大小，长度应有数字之差。2 2）p p、q q建议采用建议采用“强质数强质数”（不少专家仍有不同意见）。（不少专家仍有不同意见）。3 3）n n的长度至少应为的长度至少应为1024-bit1024-bit以上，上个世纪曾建议的以上，上个世纪曾建议的512-bit512-bit的的长度，如长度，如RSA-155RSA-155也于世纪交替前被破解）。也于世纪交替前被破解）。4 4）的值越小越好。的值越小越好。1.30 2006第第第第6 6章章章章 RSA RSA密码密码密码密码WienerWiener低幂次低幂次d d攻击攻击 6.10 Wiener低幂次d攻击 定理令令 （且（且 ）为实数）为实数x x的某项连分数的收敛值的某项连分数的收敛值 定理 WienerWiener攻击攻击 令RSA密码系统中各参数满足下列条件：则存在多项式时间算法可因数分解RSA模数n。1.31 2006第第第第6 6章章章章 RSA RSA密码密码密码密码RabinRabin密码密码 6.11 Rabin密码 密匙产生密匙产生令令p p、q q为大质数且为大质数且 。p p、q q为私钥，为私钥，BobBob计算计算RabinRabin模数模数n=pqn=pq公开之，为公钥。公开之，为公钥。AliceAlice加密加密 密文密文（mm为明文）为明文）BobBob解密解密 由费马小定理知由费马小定理知 由中国余式定理得由中国余式定理得 其中其中