RSA加密算法是一种公钥加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman在1977年发明。RSA算法的安全性基于数论中的两个重要问题：质因数分解和求离散对数。RSA算法通过将一组大素数与其他参数结合起来生成公钥和私钥，用公钥加密数据，用私钥解密数据，实现了信息的安全传输。
具体来说，RSA算法的加密过程如下：
- 选择两个大素数p和q，计算N=p*q。
- 然后引入N的欧拉函数，即φ(N)，φ(N)=(p-1)*(q-1)
- 选择一个整数e，1<e<φ(N)，且e与φ(N)互质，通常写成gcd(e, φ(N))=1； 即e和φ(N)的最大公约数为1.
- 计算d，使得e*d对φ(N)取余得1， 也可以写成e*d与1关于φ(N)同余: e*d=1 mod φ(N)，
- 将N和e作为公钥，N和d作为私钥。
- 加密原始数据M时，得到加密数据 Me=M^e mod N。
- 此处省略加解密求解证明的步骤。
- 解密数据时，只需要通过计算M=Me^d mod N 得到原始数据M。
举一个小例子：
假设 p=3,q=11,
得到 φ(n)=(p-1)(q-1) = 20
本例中取私钥 d=7;
由d*e=1modφ(p*q), 代入d=7，得到7*e=1 mod20，即7*e 与1 关于20余数相同 ,而1除以20余数为1 , 则7*e=20k+1 ,其中k为整数，e要小于20（φ(p*q)）的整数，简单计算和刷选后得到公钥 e=3。
加密数字5: 得到密文Me=M^e mod N = 5^3 mod 33 = 26
解密密文得到原文：M=Me^d mod N=26^7 mod 33 = 5
在RSA算法中，公钥（N，e）用于加密数据，私钥（N，d）用于解密数据。由于在不知道q和p的情况下φ(N)难以计算，因此在已知N和e的情况下，计算d是困难的，这就保证了RSA算法的安全性。同时，由于N是两个大素数p和q的乘积，因此破解RSA算法的关键在于分解N为p和q两个素数的乘积，这是一个极其困难的问题，因此RSA算法被认为是一种安全的加密算法。
//通常认为RSA算法的安全性是由“分解N为p和q两个素数的乘积的复杂度”来保证的，但目前尚无数学证明来支持这个想法。
//我是算法小白，总觉得RSA的弱点在于素数的选择，目前已知的素数虽然不少但也是有限的，如果把所有的素数两两乘积结果做Hash存放在键值数据库中，然后对公钥中的N进行Hash，并在数据库中做检索，应该不难找到q和p两个素数。
//根据文档 https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf ， RSA会随机生成质数，但受限于生成和校验大素数的算法复杂度，RSA代码也会接受Probable Prime Number 可能的质数。