密码学公钥密码1.ppt

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公钥密码体制以及一些相关知识。
公钥密码的理论基础是单向函数。5.2RSA公钥密码定理5.1(中国剩余定理)设是两两互素的正整数，设是整数。则同余方程组
模有唯一解:
例1（孙子算经中物不知数）今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
解：例2（韩信点兵）有兵一对,若列5行纵队,则末行1人,成6行纵队，则末行5人，成7行纵队，则末行4人，成11行纵队，末行10人.求兵数？
解：5.2.2Euler函数定理5.2如果定理5.3如果推论5.1(Fermat小定理)5.2.4RSA公钥密码体制RSA合理性证明练习例：取p=13，q=17，则n=13*17=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的安全性讨论除了指定n的大小之外，p和q的选取应做如下限制：5.2.6模n求逆的方法扩展的Euclid算法定理5.6设是一个正整数，模n求逆的算法5.2.7模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.8（素数定理）5.3.2Legendre符号和Jacobi符号定理5.9设n>2是一个奇素数.
5.3.3Solovay-Strassen素性测试法定理5.11定理5.125.3.4Miller-Rabin素性测试法定理5.13证明定理5.14