RSA算法简要介绍.pptVIP

RSA的简要介绍 RSA公钥密码体制在密码学中占有重要的地位，已经成为现在最流行的公钥加密算法和数字签名算法之一。其必威体育官网网址性强，密钥管理方便，并且具有数字签名、认证和鉴别等多种功能，特别适合于现代必威体育官网网址通讯的需要。大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。 RSA算法原理分析 1977年由MIT的Rivest, Shamir和Adleman 三人提出 是一个分组加密方法 目前被最广泛地采用 采用的单向函数是大素数相乘，相乘很容易，但因子分解很困难 基于数论中的欧拉定理实现 欧拉定理的一个推论 给定两个素数p、q，两个整数n和m，n=p*q，n的欧拉函数Φ(n)＝(p-1)(q-1)，0mn，并对于任意整数k，下列关系成立： m kΦ(n)+1=mk(p-1)(q-1)+1≡m mod n 假设ed=kΦ(n)+1，等价于： ed≡1 mod Φ(n) d ≡e-1 mod Φ(n) 对mod的分析： mod是求余运算符，如果x、y的乘积除以z所得的余数为1，即可表示成x*y=1(modz),x、y对于模数z来说互为逆元。 RSA算法－－加解密过程 假设公钥为e，私钥为d 加密过程： 明文：Mn 密文： C = Me (mod n) （4） 解密过程： 密文： C 明文： M = C d (mod n) = (Me)d mod n = Med mod n （5） RSA算法的实例 选取两个素数p=47, q=79, 得出n=p*q=3 713, Φ( n) =46×78=3 588, 由于37 和3 588 没有公因子, 故设e=37, 根据e*d≡ 1 mod Φ( n) , 即37d≡ 1 mod Φ( 3 588) , 解之可得d=97。将加密密钥( e, n) =( 37, 3 713) 公开, 而( d, n) =( 97, 3 713) 则是只有用户知道的解密密钥。 假定明文M=120, 加密时, 根据明文加密公式C= Me (mod n)以及( e, n) = ( 37, 3 713) , 即C= mod3 713, 得到密文C=1 404; 解密时, 根据密文解密公式M = C d (mod n)以及用户知道的( d, n) =( 97, 3 713) , 即M= mod 3 713, 解得明文M=120。 RSA算法的实现主要包括两部分 （1）素数的选取 （2）密钥对的生成 素数的选取 大素数p、q 的选取,是构造RSA 算法的关键。 1、 实际考虑 1）产生一个n位的随机大素数p。 2) 设p的最高位和最低位都为1，以确保达到要求的长度，和确保该大数是奇数。 3) 检查以确保p不能被任何小素数整除，如3，5，7，11等等。有效的方法是测试小于2000的素数。使用字轮方法更快。 4) 对某随机数a运行Rabin-Miller检测，如果p通过，则另外产生一个随机数a,在测试。选取较小的a值，以保证速度。做5次Rabin-Miller测试，如果有一次失败，返回第一步，从新产生p，再测试。 Miller-Rabin 素数检测算法 对一个待测的随机大数p，计算p的有效位n，比如p＝0x5A，则n＝7。 1) 选择一个小于p的随机数a。 2) 令z＝1，i＝n。 3) x=z, z=d*d mod N。 4) 如果z＝1并且x1并且xp－1，那么测试通不过，p不是素数。 5) 如果p－1的第i位为1，令z＝z*a mod p，i＝i－1。如果i=0，则转到第三步。 6) 如果z1，则同不过检测，p不是素数，否则通过检测，p可能为素数。 这个测试算法速度快，但是有很小的概率会出错。如果用5次该算法进行检测，p是 素数的概率可达到99.9％（1－（0.25）^5）。 密钥对的生成 RSA 算法中, 在找到了素数p、q 并计算出Euler函数Φ( n) =( p- 1)( q- 1) 后, 就可以计算多个公开密钥、秘密密钥对( e, d) 。由于e、d 均与Φ( n) 互素, 且Φ( n) 为偶数, 因此e、d 都是奇数。有人提出RSA 算法的实现是在d 与Φ( n) 互素的条件下先选取d, 然后在e*d≡1 mod Φ( n) 条件下求得e。这样所求得的加密密钥e 可能相当大, 使加密操作时间很长。为了提高加密运算速度, 选择加密密钥要适当小一些, 所以首先要选取e。 RSA算法的缺点分析 1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。 2)安全性, RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分