RSA由Ron Rivest、Adi Shamir和Leonard Adleman于1977年提出，当时他们三人都在MIT。RSA取自他们三人姓氏开头字母拼在一起组成的。
RSA是Diffie-Hellman公钥加密的实现，其安全性部分依赖于大整数分解的困难。之所以说“部分依赖于”，是因为至今还没证明RSA的安全性完全依赖于大整数分解。
1.公钥和密钥的生成
（1）随意两个大素数p和q，计算 n=p*q ；
（2）根据gcd(d, (p-1)*(q-1))=1 计算 d；
（3）由*%5Cleft(&space;%7B%7B%5Crm%7Bq%7D%7D&space;-&space;%7B%5Crm%7B1%7D%7D%7D&space;%5Cright)%7D&space;%5Cright)%24%24 "$${\rm{e}}*{\rm{d }} \equiv {\rm{ 1 }}\left( {{\rm{mod }}\left( {{\rm{p}} - {\rm{1}}} \right)*\left( {{\rm{q}} - {\rm{1}}} \right)} \right)$$")
求得e 。
加密密钥(e,n)，解密密钥(d,n)，由n分解为p、q是困难的。
2.加密与解密
加密：&space;%5Cequiv&space;%7BM%5Ee%7D&space;%5C&space;%7Bmod&space;%5C&space;n%7D%24%24 "$$C \equiv E(M) \equiv {M^e} \ {mod \ n}$$")
，其中M是消息，E(
)是加密函数，C是加密后的密文。
解密：&space;%5Cequiv&space;%7BC%5Ed%7D%7B%5C&space;%7B&space;mod&space;%5C&space;n&space;%7D%7D&space;%5Cequiv&space;%7B%7B%5Crm%7BM%7D%7D%5E%7Bed%7D%7D%7B%5C&space;%7B&space;mod&space;%5C&space;n%7D%7D&space;%5Cequiv&space;M%24%24 "$$D(C) \equiv {C^d}{\ { mod \ n }} \equiv {{\rm{M}}^{ed}}{\ { mod \ n}} \equiv M$$")
，其中D(
)是解密函数。
3.证明
证明需要用到欧拉定理，先引出几个概念。
（1）欧拉函数φ(n)，是指小于n且与n互素的整数的个数。特别地，有φ(1)=1，对素数p有φ(p)=p-1 。
（2）欧拉定理：对任意互素的a和n，有&space;+&space;1%7D%7D&space;%5Cequiv&space;a%5C&space;mod&space;%5C&space;n%24%24 "$${a^{\varphi (n) + 1}} \equiv a\ mod \ n$$")
。关于欧拉定理详细证明，请参看其他书籍。
RSA解密的证明：
&space;%5Cequiv&space;%7BM%5E%7Bed%7D%7D&space;%5Cequiv&space;%7BM%5E%7Bk*%5Cvarphi&space;(n)&space;+&space;1%7D%7D&space;%5Cequiv&space;M%5C&space;mod&space;%5C&space;n%24%24 "$$D(C) \equiv {M^{ed}} \equiv {M^{k*\varphi (n) + 1}} \equiv M\ mod \ n$$")
4. 参考文献
[1]R.Rivest,A.Shamir,andL.Adleman. "Amethodforobtainingdigitalsignaturesandpublic-keycryptosystems".CommunicationsoftheACM,vol.21,no.2,pp.120–126,1978.
分享到：
相关推荐
只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。 RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想...
RSA加密解密C#实现调用实例 public string RSAEncrypt(string xmlPublicKey, string m_strEncryptString) { try { byte[] PlainTextBArray; byte[] CypherTextBArray; string Result; System.Security....
* RSA加密解密：私钥解密，公钥加密。 * RSA数字签名-俗称加签验签：私钥加签，公钥验签。 * RSA加密解密：私钥解密，公钥加密。 * RSA数字签名-俗称加签验签：私钥加签，公钥验签。 * RSA加密解密：私钥...
用PowerBuilder实现RSA加密算法
RSA加密算法在VBRSA加密算法在VBRSA加密算法在VB
QT上RSA加密算法实现，附带图形界面，更加直观
RSA加密解密算法源码,功能齐全,没有密码,使用方便,学习用.
unity工具类RSA加密和解密
RSA加密算法的实现，使用c++语言编程，使用dev c++平台编码，文件为cpp格式。经过反复测试代码正确，可搭配RSA讲解教程一起使用，讲解教程点击我的个人主页即可查看，希望能够对你有帮助，谢谢。
RSA加密演算法是一种非对称加密演算法。在公开密钥加密和电子商业中RSA被广泛使用。 典型的应用 1. 苹果App签名, iOS App 签名的原理; 2. 支付宝签名验证 ; 2. HTTPS 加密连接; 3. 程序直接用RSA+AES加密通信 ...
RSA加密算法，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。...加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开...本资源是通过Android、java实现的RSA加密的例子，可供大家参考学习。
由于项目需求，需要对一些重要信息进行RSA加密再传给服务器，网上找了挺久相关内容，终于解决，总结一下。 前端使用jsencrypt进行RSA加密解密（uniapp也可用） 一、引入jsencrypt.js文件 jsencrypt.js下载：...
C#做的RSA加密解密， 带winform界面， 测试通过， 代码完整。
RSA加密解密算法 C++ 密码学 RSA加密解密算法 C++ 密码学 RSA加密解密算法 C++ 密码学
RSA加密算法实验报告.pdf
易语言调用JSEncrypt实现RSA加密解密。Tags：JSEncryptRSA加密解密。
可实用的RSA加密算法(PB12.5源码含Demo).zip
IOS RSA加密 分段解密
RSA加密算法.ppt
rsa加密解密算法C语言代码 #include #include #include <stdlib.h> #include <time.h> #include #include #define MAX 100 #define LEN sizeof(struct slink) void sub(int a[MAX],int b[MAX] ,int c[MAX] ); ...