第二讲之第4章 公钥密码体制

1、第第2章章 密码技术基础密码技术基础第第3章章 对称密码体系对称密码体系第第4章章 公钥密码体系公钥密码体系第第5章章 公钥基础设施公钥基础设施PKI第第6章章 信息隐藏技术信息隐藏技术4.1公钥密学概述公钥密学概述4.2 Diffie-Hellman 密钥交换算法密钥交换算法4.3 RSA算法算法u19761976年，年，DiffieDiffie 和和HellmannHellmann提出了公开密提出了公开密钥密码体制（简称钥密码体制（简称公钥体制公钥体制），它的加密），它的加密、解密密钥是不同的，也是不能（在有效、解密密钥是不同的，也是不能（在有效的时间内）相互推导。所以，它可称为的时间内）

2、相互推导。所以，它可称为双双钥密码体制钥密码体制。u公开密钥密码体制的产生，是密码学革命公开密钥密码体制的产生，是密码学革命性的发展。一方面，为数据的保密性、完性的发展。一方面，为数据的保密性、完整性、真实性提供了有效方便的技术。另整性、真实性提供了有效方便的技术。另一方面，科学地解决了密码技术的瓶颈一方面，科学地解决了密码技术的瓶颈密钥的分配问题密钥的分配问题。u第一个公钥体制是第一个公钥体制是1977年由年由Rivest，Shamir，Adleman提出的，称为提出的，称为RSA公钥体制，其安全性是基于整数的因子公钥体制，其安全性是基于整数的因子分解的困难性。分解的困难性。RSA公钥体制已

3、得到了公钥体制已得到了广泛的应用。广泛的应用。u基于背包问题的基于背包问题的Merkle-Hellman背包公背包公钥体制钥体制u基于有限域上离散对数问题的基于有限域上离散对数问题的ElGamal公钥体制公钥体制u基于椭圆曲线的基于椭圆曲线的ECC密码体制密码体制uu公钥密码体制加解密过程主要有以下几步公钥密码体制加解密过程主要有以下几步 ： 不一样的密码公钥体制用于数据加密时：公钥体制用于数据加密时： 用户用户将自己的将自己的公开（加密）密钥公开（加密）密钥登记在一个公登记在一个公开密钥库或实时公开，开密钥库或实时公开，秘密密钥秘密密钥则被严格保密。则被严格保密。信源信源为了向为了向信宿信宿

4、发送信息，去公开密钥库查找对发送信息，去公开密钥库查找对方的公开密钥，或临时向对方索取公钥，将要发方的公开密钥，或临时向对方索取公钥，将要发送的信息用这个公钥加密后在公开信道上发送给送的信息用这个公钥加密后在公开信道上发送给对方，对方收到信息（密文）后，则用自己的秘对方，对方收到信息（密文）后，则用自己的秘密（解密）密钥解密密文密（解密）密钥解密密文，读取，读取信息信息。可见可见，这里省去了从秘密信道传递密钥的过程。，这里省去了从秘密信道传递密钥的过程。这是公钥体制的一大优点。这是公钥体制的一大优点。 一对密钥 公钥体制用于数字签名时：信源为了他人能够验证自己发送的消息确实来自本人，他将自己的

5、秘密（解密）密钥公布，而将公开（加密）密钥严格保密。与别人通信时，则用自己的加密密钥对消息加密称为签名，将原消息与签名后的消息一起发送.对方收到消息后，为了确定信源的真实性，用对方的解密密钥解密签名消息称为（签名）验证，如果解密后的消息与原消息一致，则说明信源是真实的，可以接受，否则，拒绝接受。u定义素数定义素数p的原元（原始根）为这样一个的原元（原始根）为这样一个数，他能生成数，他能生成1p-1所有数的一个数。现所有数的一个数。现设设a为为p的原元，则的原元，则两两互不相同，构成一个两两互不相同，构成一个1p-1的全体数的全体数的一个排列。对于任意数的一个排列。对于任意数b及素数及素数p的原

6、元的原元a，可以找到一个唯一的指数，可以找到一个唯一的指数 i，满足，满足则称指数则称指数i为以为以a为底、模为底、模p的的b的离散对数。的离散对数。21 mod , mod , mod pap apap mod p , 0=i=p-1ibaXAXBYAYBKA计算KB计算用户A用户B公开秘密秘密会话秘密会话秘密公开u(1)选择一个素数P和它的一个原元a;u(2)通信方A选择自己的秘密密钥XA,并计算自己的公开密钥YA: YA=a XA mod Pu(3)通信方B选择自己的秘密密钥XB,并计算自己的公开密钥YB: YB=a XB mod Pu(4)通信双方A和B交换YA和YB；u(5)A独立计

7、算会话密钥，B独立计算会话密钥KS；u(6)通信双方利用会话密钥KS进行通信。为了计算简单，使用很小数字。设P=47和47的一个原元，a=3。uA选择秘密密钥XA=8，B选择秘密密钥XB=10，各自计算其公开密钥。u（1）双方各自计算用户A计算：YA=3 8mod 47=6561 mod 47=28 mod 47用户B计算：YB=3 10mod 47= 59049 mod 47=17 mod 47u（2）交换YA和YB；u（3）交换密钥后，A、B分别计算共享的秘密会话密钥KA、KB：用户A计算： KA=YB XA mod 47=178 mod 47=4 mod 47用户B计算： KB=YA X

8、B mod 47=2810 mod 47=4 mod 47u A和B双方独立地决定采用数据“4”作为会话密钥。 特征：特征：（1）仅当需要时才产生密钥，减少储存时间，减）仅当需要时才产生密钥，减少储存时间，减少受攻击的机会；少受攻击的机会；（2）除对全局参数的约定外，密钥交换不需要事）除对全局参数的约定外，密钥交换不需要事先存在的基础结构。先存在的基础结构。不足：不足：（1）没有通信双方身份的信息；）没有通信双方身份的信息；（2）计算是密集性的，容易受到）计算是密集性的，容易受到阻塞性攻击阻塞性攻击；（3）没办法防止）没办法防止重放攻击重放攻击；（4）容易受到）容易受到中间人攻击中间人攻击。u

9、1978年由年由Ron Rivest、AdiShamir和和Len Adleman发明。发明。“A method for obtaining digital signatures and public key cryptosystem”u是一种块加密算法。是一种块加密算法。明文和密文在明文和密文在0n-1之间之间,n是一个正整数是一个正整数u应用最广泛的公钥密码算法应用最广泛的公钥密码算法u只有美国专利，且已于只有美国专利，且已于2000年年9月到期月到期算法产生一对密钥，一个人可以用密钥对中算法产生一对密钥，一个人可以用密钥对中的一个加密消息，另一个人则可以用密钥对的一个加密消息，另一个人则

10、可以用密钥对中的另一个解密消息。同时，任何人都无法中的另一个解密消息。同时，任何人都无法通过公钥确定私钥，也没有人能使用加密消通过公钥确定私钥，也没有人能使用加密消息的密钥解密。只有密钥对中的另一把可以息的密钥解密。只有密钥对中的另一把可以解密消息。解密消息。u加密：加密： C=Me mod N, where 0MNu解密：解密： M=Cd mod N u公钥为（公钥为（e，N），）， 私钥为（私钥为（d，N）u必须满足以下条件：必须满足以下条件：计算计算Me和和Cd是比较容易的是比较容易的由由e和和N确定确定d是不可行的是不可行的u随机选择两个随机选择两个互质互质大素数大素数 p, q (p

11、，q 必须保密必须保密)u计算计算 n=p.qu计算计算z =(p-1)(q-1) u随机随机选择选择整数整数 e，使得使得1ez且且gcd(e,z)=1 u计算计算d ：d=e-1 mod z 且且 0 d n u公布公钥公布公钥: KU=e，n u保存私钥保存私钥: KR=d，n u发送方要加密明文发送方要加密明文M:获得接收方的公钥获得接收方的公钥 KU=e,N 计算计算: C=Me mod N, where 0MNu接收方解密密文接收方解密密文C: 使用自己的私钥使用自己的私钥 KR=d,N 计算计算: M=Cd mod N u注意：注意：M必须比必须比N小小u取两个质数取两个质数p=

12、11，q=13，p和和q的乘积为的乘积为n=pq=143，算出另一个数，算出另一个数z=(p-1)(q-1)=120；u再选取一个与再选取一个与z=120互质的数，例如互质的数，例如e=7，则，则 公开密钥公开密钥=（n，e）=（143，7）。）。u 对于这个对于这个e值，可以算出其逆：值，可以算出其逆：d=103。u 因为因为ed=7103=721，满足，满足ed mod z =1；即；即721 mod 120=1成立。成立。 则秘密密钥则秘密密钥=（n，d）=（143，103）。）。u张小姐需要发送机密信息（明文）张小姐需要发送机密信息（明文）m=85给李给李先生，她已经从公开媒体得到了李

13、先生的公开密先生，她已经从公开媒体得到了李先生的公开密钥钥(n，e)=(143，7)，于是她算出加密值：，于是她算出加密值： c= me mod n=857 mod 143=123，并发送给并发送给李先生。李先生。u李先生在收到密文李先生在收到密文c=123后，利用只有他自己后，利用只有他自己知道的秘密密钥计算：知道的秘密密钥计算：m= cd mod n =123103 mod 143=85，所以，李先生可以得到张小姐发，所以，李先生可以得到张小姐发给他的真正的信息给他的真正的信息m=85，实现了解密。，实现了解密。 依赖于大数分解，但是否等同于大数分解一直依赖于大数分解，但是否等同于大数分解

14、一直未能证明。不管怎样，分解未能证明。不管怎样，分解n是最显然的攻击方法是最显然的攻击方法。 1994年年4月月26日，美国各大媒体报道：由日，美国各大媒体报道：由RSA发发明人在明人在17年前出的年前出的129位数字已被因子分解，并破位数字已被因子分解，并破解了附带的密语：解了附带的密语： The magic words are squeamish ossifrage. 目前，已能分解目前，已能分解140位十进制的大素数。因此，位十进制的大素数。因此，模数模数n必须选大一些。必须选大一些。 RSA最快的情况也比最快的情况也比DES慢上慢上100倍，无论是软倍，无论是软件还是硬件实现。速度一直

15、是件还是硬件实现。速度一直是RSA的缺陷。一般只的缺陷。一般只用于少量数据加密。用于少量数据加密。不能证明不能证明RSA密码破译等同于大数因子分解密码破译等同于大数因子分解1) 速度问题：增大速度问题：增大pq将使开销指数级增长将使开销指数级增长2) 至少有至少有9个明文，加密后不变，即个明文，加密后不变，即me mod n=m3) 普通用户难于选择普通用户难于选择p、q。对。对p、q的基本要求：的基本要求：p、q不相同，即不要太接近，又不能差别太大不相同，即不要太接近，又不能差别太大p-1、q-1都有大素数因子，增加猜测都有大素数因子，增加猜测(r) 难度难度gcd( p-1，q-1)应当小

16、应当小4)p、q选择不当，则变换周期性、封闭性而泄密选择不当，则变换周期性、封闭性而泄密 例：例：p=17，q=11，e=7，则，则n=187。 设设m=123，则，则 C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文明文m经过经过4次加密，恢复成明文。次加密，恢复成明文。总之，总之，RSA对用户要求太苛刻，密钥不能常更换。对用户要求太苛刻，密钥不能常更换。（1）选择密文攻击选择密文攻击（2）过小加密指数过小加密指数e（3） RSA的公共模数攻击的公共模数攻击（4）RSA的计时攻击法的计

17、时攻击法u公开密钥密码体制有优点公开密钥密码体制有优点,但它的运算量大但它的运算量大,计算复杂。计算复杂。 u结合对称密钥密码体制使用结合对称密钥密码体制使用uRSA算法在互联网的许多方面得以广泛应算法在互联网的许多方面得以广泛应用。用。u基于基于RSA算法的公钥加密系统具有数据加算法的公钥加密系统具有数据加密、数字签名密、数字签名(Digital Signature)、信息、信息源识别及密钥交换等功能。源识别及密钥交换等功能。u优点优点密钥密钥空间大空间大u缺点缺点 1)1)产生密钥很麻烦，受到素数产生技术的限产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。制，因而难以做到一次

18、一密。2)2)速度太慢速度太慢。RSARSA速度比速度比DESDES慢得多，无论是慢得多，无论是软件还是硬件实现，速度软件还是硬件实现，速度一直是一直是RSARSA的缺陷的缺陷。3)3)为为保证安全性，保证安全性，n n 至少也要至少也要 600 600 bitsbits以上以上，且还在增加。在运算上要付出代价。，且还在增加。在运算上要付出代价。 比较比较1 在加密、解密的处理效率方面，在加密、解密的处理效率方面，DES算法算法优于优于RSA算法。因为算法。因为DES密钥的长度只有密钥的长度只有比特，可以利用软件和硬件实现高速处理；比特，可以利用软件和硬件实现高速处理；RSA算法需要进行诸如比

19、特整数的乘幂算法需要进行诸如比特整数的乘幂和求模等多倍字长的处理，处理速度明显慢于和求模等多倍字长的处理，处理速度明显慢于DES算法。算法。 u比较比较2 在密钥的管理方面，在密钥的管理方面，RSA算法比算法比DES算法更加优越。因为算法更加优越。因为RSA算法可采用公开算法可采用公开形式分配加密密钥，对加密密钥的更新也形式分配加密密钥，对加密密钥的更新也很容易，并且对不同的通信对象，只需对很容易，并且对不同的通信对象，只需对自己的解密密钥保密即可；自己的解密密钥保密即可；DES算法要求算法要求通信前对密钥进行秘密分配，密钥的更换通信前对密钥进行秘密分配，密钥的更换困难，对不同的通信对象，困难

20、，对不同的通信对象，DES需产生和需产生和保管不同的密钥。保管不同的密钥。u比较比较3 在安全性方面，在安全性方面，DES算法和算法和RSA算法算法的安全性都较好，还没有在短时间内破译的安全性都较好，还没有在短时间内破译它们的有效的方法。它们的有效的方法。u比较比较4 在签名和认证方面，在签名和认证方面，DES算法从原理算法从原理上不可能实现数字签名和身份认证，但上不可能实现数字签名和身份认证，但RSA算法能够容易地进行数字签名和身份算法能够容易地进行数字签名和身份认证。认证。 u设发送方为设发送方为A(A(加密密钥为加密密钥为Kea,Kea,解密密钥为解密密钥为KdaKda),),接收方为接

21、收方为B(B(加密密钥为加密密钥为KebKeb, ,解密密钥为解密密钥为KdbKdb) )。u具体实现步骤具体实现步骤: :(1)(1)发送方发送方A A生成用于生成用于DESDES加密的密钥加密的密钥K,K,为了为了提高数据的安全性提高数据的安全性, ,每一个密钥只用一次。每一个密钥只用一次。 (2)(2)发送方从密钥服务器中获取接收方的发送方从密钥服务器中获取接收方的RSARSA的公开加密密钥的公开加密密钥KebKeb, ,并用并用KebKeb加密加密DESDES的密的密钥钥K K形成密文形成密文CkCk。 (3)发送方发送方A生成需要签名的信息生成需要签名的信息,并用并用自己的自己的RS

22、A的解密密钥的解密密钥Kda和和Keb共同形成共同形成数字签名。数字签名。 (4)发送方用发送方用K加密明文和签名的信息加密明文和签名的信息,然后连同然后连同Ck一起形成密文一起形成密文C发往接收方。发往接收方。(5)接收方接收到接收方接收到C后后,先用自己的解密先用自己的解密密钥密钥Kdb解密出解密出C中的中的DES密钥密钥K,再利用再利用K解密出明文和签名信息。解密出明文和签名信息。 (6)接收方用发送方的公开密钥接收方用发送方的公开密钥Kea和自己的解密密钥和自己的解密密钥Kdb对签名信息进对签名信息进行身份认证行身份认证,然后对签名信息作适当处然后对签名信息作适当处理后理后(例如填写自

23、己的标识号等例如填写自己的标识号等),再形再形成自己的数字签名信息发往发送方。成自己的数字签名信息发往发送方。 (7)发送、接收双方均删除发送、接收双方均删除DES密钥密钥K。 1 . 对称密码体制和非对称密码体制各有何优缺点？对称密码体制和非对称密码体制各有何优缺点？2. 在使用在使用RSA公钥中如果截取了发送给其他用户的公钥中如果截取了发送给其他用户的密文密文C10，若此用户的公钥为，若此用户的公钥为e5，n35，请问明文的内容是什么请问明文的内容是什么?3. 已知有明文已知有明文public key encryptions，先将明文，先将明文以以2个字母为组分成个字母为组分成10块，如果

24、利用英文字母表块，如果利用英文字母表的顺序，即的顺序，即a00，b01，将明文数据化。，将明文数据化。现在令现在令p53，q58，请计算得出，请计算得出RSA的加密的加密密文。密文。4. 试试简要比较简要比较DES算法和算法和RSA算法的优缺点。算法的优缺点。5.假定假定A和和B要用要用RSA方法进行一次保密又认证的通方法进行一次保密又认证的通信。信。A的公钥是的公钥是(nA, eA) =(33, 7), B的公钥是的公钥是(nB, eB)=(15, 5)。 (a) A和和B的秘密密钥的秘密密钥dA和和dB各是什么各是什么? (b)A送消息送消息m=2给给B，保密又认证，密文，保密又认证，密文

25、C是什么是什么? (c)B如何从如何从C解得解得m？ 6.用用Diffie-Hellman密钥交换方法在密钥交换方法在Alice和和Bob之间之间建立一个会话密钥。建立一个会话密钥。Alice向向Bob送去送去(p, , xA) = (719, 3, 191)，Bob以以543回答。回答。Alice的秘密的秘密xA为为16，求他们之间形成的会话密钥。，求他们之间形成的会话密钥。u由于由于RSA密文是通过公开渠道传播的，攻密文是通过公开渠道传播的，攻击者可以获取密文。击者可以获取密文。u假设攻击者为假设攻击者为H，密文收件人为，密文收件人为T，H得到得到了发往了发往T的一份密文的一份密文c，他想

26、不通过分解质，他想不通过分解质因数的方法得到明文因数的方法得到明文m。u换句话说，换句话说，H需要需要 m = cd 。u 为了恢复为了恢复 m，H找一个随机数找一个随机数 r ， r n，当然他有，当然他有T的公匙的公匙(e,n)。u他计算：他计算： x=re % n （用（用 T 的公匙加密的公匙加密 r） y=x*c % n （将临时密文（将临时密文x与与c相乘）相乘） t=r-1 % nuA 知道知道RSA具有下面的一个特性：具有下面的一个特性： 如果如果 x=re % n，那么，那么 r=xd % n 因此他想办法让因此他想办法让T对对 y 用用T自己的私匙签自己的私匙签名（实际上就

27、是把名（实际上就是把 y 解密了），然后将结解密了），然后将结果果 u=yd % n 寄回给寄回给A。A只要简单地计只要简单地计算：算： m = t*u % n 上面结论的推导是这样的：上面结论的推导是这样的： t*u % n = (r-1)*(yd) & n = (r-1)*(xd)(cd) % n = (cd) % n = m 要防止这种攻击的办法就是不要对外来的要防止这种攻击的办法就是不要对外来的随机信息签名，或者只对信息的随机信息签名，或者只对信息的MD5特征特征值签名。在这里就很容易明白为什么要强调值签名。在这里就很容易明白为什么要强调MD5的单向性了，因为的单向性了，因为MD5的结

28、果是不能预的结果是不能预定的，就是说定的，就是说A难以凑出一份刚好能产生难以凑出一份刚好能产生 y 这样的这样的MD5特征值的明文来让特征值的明文来让T签名。签名。ue 是一个小数并不降低是一个小数并不降低RSA的安全性。从的安全性。从计算速度考虑，计算速度考虑，e 越小越好。越小越好。u可是，当明文也是一个很小的数时就会出可是，当明文也是一个很小的数时就会出现问题。例如取现问题。例如取 e=3 ，而且明文，而且明文 m比比 n 的三次方根要小，那么密文的三次方根要小，那么密文 c = me % n 就会等于就会等于 m3。这样只要对密文开三次方。这样只要对密文开三次方就可以得到明文。就可以得

29、到明文。若系统中共有一个模数，只是不同的人拥有不同的若系统中共有一个模数，只是不同的人拥有不同的e和和d，系统将是危险的。，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到公钥共模而且互质，那末该信息无需私钥就可得到恢复。设恢复。设P为信息明文，两个加密密钥为为信息明文，两个加密密钥为e1和和e2，公共模数是公共模数是n，则：，则：C1 = Pe1 mod n C2 = Pe2 mod n 攻击者知道攻击者知道n、e1、e2、C1和和C2，就能得到，就能得到P。因为。因为e1和和e2互质，故用互质，故用Euclidean算法能找到算法能找到r和和s，满足：，满足：r * e1 + s * e2 = 1 。由由 Paul Kocher 发