密码信息理论密码学加密演算法邓安

《密码信息理论密码学加密演算法邓安》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、返回总目录第6章RSA密码教学目的了解公开密匙密码系统了解RSA算法、数论背景和数字签名了解二次筛法与Pollard的p-1法了解利用RSA私钥因数分解了解Wiener低幂次d攻击了解Rabin密码公开密钥密码系统本章内容RSA算法RSA的数论背景RSA数字签名同时进行RSA加密和RSA数字签名RSA-129挑战与因数分解二次筛法与Pollard的p-1法本章内容利用RSA私钥因数分解RSA密码系统实用的注意事项Wiener低幂次d攻击Rabin密码公开密匙密码系统6.1公开密匙

2、密码系统（1）将一已加密的信息m解密，即可还原m，即（2）加密以及解密函数、必须是容易计算的。（3）公开加密函数，并不会提供任何简易计算解密函数的方法，在实际应用中，这意味着只有Bob才能将任何经加密函数加密的信息有效地解密，也只有Bob知道“陷门”（Trapdoor）从而有效计算。（4）若将任何信息m先用解密函数运算，再用加密函数运算，亦可还原信息m，即定义单向陷门函数，TrapdoorOne-WayFunction函数若满足性质（1）、（2）、（3），就称为单向陷门函数，若性质（1）、（2）、（3

3、）、（4）皆满足，就称为单向陷门置换（TrapdoorOne-WayPermutation）。数字封装RSA算法6.2RSA算法密匙产生：Bob取相异质数p、q（保密），计算RSA模数（RSAModulus）n=pq，将其公开，取e为加密密钥将其公开，其中e必须与φ(n)互质，在此情况下，Bob的公开密钥为(n,e)；Bob计算d为解密密钥（保密），(n,d)为Bob的私钥（PrivateKey）其中加密：Alice取得Bob的公开密钥(n,e)，用加密函数计算将密文c传给Bob。解密：Bob用解密函

4、数计算解密还原成明文。RSA算法举例密匙产生Bob取质数p=241、q=311，计算n=pq=74951，取e=1033为加密钥，在此情况，Bob的公开密钥为(n,e)=(74951,1033)；Bob用广义辗转相除法计算解密密钥RSA算法举例加密Alice的明文（令a=0、b=1、…、z=25），取得Bob的公开密钥为，加密得密文RSA算法举例解密所以RSA的数论背景6.3RSA的数论背景Euler定理令整数a、n，其中a与n互质。则Euler定理推广了费马小定理定理令整数a、n，其中a与n互质。则

5、RSA加密解密函数定理RSA加密解密函数令p、q为相异质数，令n=pq，令e为与(p-1)(q-1)互质的整数，令d满足令加密函数，解密函数则对所有整数m皆满足且RSA修订版令Alice想将明文m加密成密文c传至Bob，而Bob将密文c解密还原成明文m。密匙产生Bob取相异质数p、q（保密），计算RSA模数n=pq，将其公开，取e为密钥将其公开，其中e必须与互质，Bob的公开密钥为(n,e)；计算加密Alice取得Bob的公开密钥(n,e)，用加密函数计算将密文c传给Bob。解密Bob有两种解密计算方

6、式：一是以及用中国余式定理加速解密Bob的私钥为RSA数论背景定理对所有整数m皆满足且证明：若q

7、m，此时同理可得：再用中国余式定理得(某整数K1)(某整数K2）)RSA数字签名6.4RSA数字签名RSA数字签名是一种可回复式数字签名法（RecoveryScheme）Bob利用RSA密码系统，数字签名一简短的文件，并传递给他所有认识的人。例：密匙产生密匙产生Bob的RSA密钥为其中RSA模数加密密钥为e=31，解密密钥为数字签名数字签名假设代码空白=0、a=1、b=2、…、z=26，又故以全文为一组编

8、码，得代码再以解密函数分别对此代码“数字签名”并将“数字签名”传给所有她想要传送的人。签名还原签名还原Alice收到了Bob的“数字签名”，经过计算同时RSA加密和RSA签名6.5同时RSA加密和RSA签名RSA-129挑战与因数分解6.6RSA-129挑战与因数分解例：Bob的RSA公开密钥为(n,e)=(782741,7)。攻击者Eve截收到Alice传给Bob的密文144310，并知道Alice与Bob的通信代码为：a=0、b=1、c=2、…、z=25。计算，知道每4个字母为一组代码。如果Eve

9、知道n的质因数分解，即知道是何质数p、q使得pq=782741，就可计算，再以广义辗转相除法或xeuclidean()程序计算得解密密钥便可还原明文的代码RSA-129挑战与因数分解如何找到质因数p、q使得抛弃＝782741？Eve试着从2到小于等于的质数试除，（共计有153个质数）在第150个质数时发现因此，。以广义辗转相除法得所以明文代码为而因此明文为“help”。质数分解的记录年份十进制的位数备注1964201974451983692251－1用二