密码学公钥密码1

《密码学公钥密码1》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、5.1公钥密码的理论基础5.2RSA公钥密码5.2.2RSA公钥密码体制5.2.3RSA的安全性讨论5.2.4模n求逆的方法5.2.5模n的大数幂乘的快速算法5.2.6因子分解5.3大素数生成第五章公钥密码1976年，W.Diffie和M.E.Hellman首先提出了公钥密码学。在公钥密码体制中，加密密钥（Public-key)和解密密钥(private-key)是不一样的，由两者任何一个不能推出另一个，本章介绍RSA公钥密码体制，ElGamal公钥密码体制,Menezes-Vanstone公钥密码体制以

2、及一些相关知识。公钥密码的理论基础是单向函数。5.1公钥密码的理论基础定义5.1设f是一个函数。如果对任意给定的x，计算y使得y=f(x)是容易的，但对任意给定的y，计算x使y=f(x)是难解的，即求f的逆函数是难解的，则称y=f(x)是一个单向函数(one-wayfunction)。定义5.2设f是一个函数，t是与f有关的一个参数，对任意给定的x，计算y使得y=f(x)是容易的，如果当不知参数t时，计算f的逆函数是难解的，但当知道参数t时，计算f的逆函数是容易的，则称f是一个陷门单向函数（trapdoo

3、rone-wayfunction),参数t称为陷门。在公钥密码中，加密变换是一个陷门单向函数。5.2RSA公钥密码5.2.1基本的数论知识定义5.3设a,b,n都是整数。如果n

4、(a-b)则称a和b模n同余，记为,n称为这个同余式的模。同余的性质：定理5.1(中国剩余定理)设是两两互素的正整数，设是整数。则同余方程组模有唯一解:证明：对任意，考虑下面我们来证明式（5.2）是同余方程组（5.1)的模唯一解，假设和是同余方程组（5.1)的两个解，即因此，式（5.2）是同余方程组(5.1)的模唯一解。则即故例1

5、（孙子算经中物不知数）今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？解：例2（韩信点兵）有兵一对,若列5行纵队,则末行1人,成6行纵队，则末行5人，成7行纵队，则末行4人，成11行纵队，末行10人.求兵数？解：5.2.2Euler函数定义5.4设n是一个正整数。称为Euler函数。Euler函数是定义在正整数集合上的函数。由定义可以立即得出，如果p是一个素数，则定理5.2如果证明：定理5.3如果证明：首先证明对于任意素数和任意正整数有根据定理5.2，我们有定理5.5（Euler定理）

6、5.2.3Euler定理和Fermat小定理推论5.1(Fermat小定理)定理5.5(Fermat小定理)证明：因为p是素数，所以x或者与p互素或者是p的倍数，如果x与p互素，则由推论5.1知结论显然成立。如果x是p的倍数，则也是p的倍数，因此,结论也成立。设x和p都是正整数，则5.2.4RSA公钥密码体制RonRivest、AdiShamir以及LeonardAdleman于1978年提出了RSA公钥密码体制。RSA公钥密码体制描述如下：RSA合理性证明练习例：取p=13，q=17，则n=13*17=

7、221，∮(n)=12*16=192,随机取e=71，要求e与∮(n)互素，将后者分解即可。这里选取e有很多原则，加上∮(n)较大的时候，e的选取也较麻烦.d=e-1mod∮(n)=119.(该过程需用辗转相除法和欧几里德扩展定理)这里RSA公钥密码系统建立，其中公钥为（e，n）公开；私钥（d，n）仅解密者知道。加密消息m=5，则密文c=m^emodn=112(该过程用的其他定理)解密的时候，对密文c=112，进行d次方m=c^dmodn=112^119modn=5.5.2.5RSA的安全性讨论RSA公钥

8、密码体制的安全性是基于大整数的素分解问题的难解性。随着计算能力的持续增长和因子分解算法的不断完善，为保证RSA的安全性，在实际应用中选取的素数p和q越来越大，现在来看，n的长度为1024位至2048位是比较合理的。注意以下事实：除了指定n的大小之外，p和q的选取应做如下限制：5.2.6模n求逆的方法求两个正整数的最大公因子gcd(n,u)的Euclid算法如下：扩展的Euclid算法存在正整数a和b,使得扩展的Euclid算法如下：定理5.6设是一个正整数，证明必要性。显然，对任意存在整数使得充分性.假设

9、则存在整数使得模n求逆的算法求模n求逆的算法如下：故5.2.7模n的大数幂乘的快速算法模n的大数幂乘的快速算法如下：例5.3计算5.2.8因子分解J.M.Pollard(1974):p-1因子分解法：警告!!由P-1因子分解算法可以看出，在RSA公钥密码体制中，大素数p和q的选取应满足p-1和q-1都至少有一个大的素因子。否则n可被分解，RSA被破译。5.3大素数的生成本节介绍快速生成大素数的一些常用基本方法5.3.1素数的分