RSA算法

目录•RSA概述•RSA算法详解•测试脚本中的函数介绍RSA概述•1976年，Diffie和Hellman在文章“密码学新方向（NewDirectioninCryptography）”中首次提出了公开密钥密码体制的思想，1977年，Rivest、Shamir和Adleman三个人实现了公开密钥密码体制，现在称为RSA公开密钥体制。•RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。•RSA算法是一种非对称密码算法。•RSA算法的安全性基于数论中大整数分解的困难性。•迄今为止理论上最为成熟完善的公钥密码体制。概况：RSA概述RSA安全性：RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此，为了防止可以很容易地分解n，模数n必须选大一些一般RSA算法的模数n要到1024位甚至2048位才能保证安全。RSA概述RSA的速度：由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右RSA概述RSA不足：•产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。•安全性受到攻击：时间攻击、模数n攻击•速度太慢，由于RSA的分组长度太大，为保证安全性，n至少也要600bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。因此，使用RSA只能加密少量数据，大量的数据加密还要靠对称密码算法。RSA与DES的区别：DES：对称加密算法，加解密用同一个密钥，安全性差，但速度快。RSA：非对称加密算法，加解密双方都使用自己的公钥和私钥，私钥只有自己知道（也可能丢失），安全性好，但速度慢。RSA概述RSA算法详解数学的基本概念：素数：除了能表示为自身和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，15不是素数；13=13＊1，13是素数。素数也称为“质数”互素数：公约数只有1的两个自然数，叫做互质数，即互素数模指数运算：模运算是整数运算，有一个整数m，以n为模做模运算，即mmodn。即m去被n整除，只取所得的余数作为结果，就叫做模运算。例如，10mod3=1；28mod2=0等。模指数运算就是先做指数运算，取其结果再做模运算。如53mod7=125mod7=6RSA算法详解RSA算法既可用于加密、又可用于数字签名，且加解密的算法完全相同的。其中，公钥用于加密、验签；私钥用于解密、签名。下表为公钥、私钥的组成，以及加密、解密的公式：RSA算法描述：（1）选择一对不同的、足够大的素数p和q。（2）计算n=p·q。（3）计算f(n)=(p-1)(q-1)，同时对p和q严加保密，不让任何人知道。（4）找一个与f(n)互质的数e，且1ef(n)。（5）计算d，使得d·e≡1modf(n)或d≡e-1modf(n)（6）公钥KU=(e,n)，私钥KR=(d,n)。（7）加密时，先将明文变换成0至n-1的一个整数m。若明文较长，可先分割成适当的组，然后再进行交换。设密文为C，则加密过程为：c≡me(modn)（8）解密过程为：m≡cd(modn)RSA算法详解注：≡是数论中表示同余的符号。公式中，≡符号的左边必须和符号右边同余，也就是两边模运算结果相同。显而易见，不管f(n)取什么值，符号右边1modf(n)的结果都等于1；符号的左边d与e的乘积做模运算后的结果也必须等于1。这就需要计算出d的值，让这个同余等式能够成立RSA算法详解选p=7，q=17。求n=p×q=119，f(n)=(p-1)(q-1)=96。取e=5，满足1ef(n)，且gcd(f(n),e)=1。确定满足d·e=1mod96且小于96的d，因为77×5=385=4×96+1，所以d为77。因此公开钥为{5，119}，秘密钥为{77，119}。设明文m=19，则由加密过程得密文为C=195mod119≡2476099mod119=66解密为6677mod119=19示例：RSA算法详解Q&A