从使用场景上说，RSA非对称加密就是提供了公钥和私钥一对密钥，其中公钥公开给其他人，私钥自己保密。使用公钥加密的数据只有私钥可以解密；使用私钥签名的数据，公钥可以验证的确是使用这个私钥来签名的。这个和对称加密相比的优势是不需要双方传递一个约定的密钥，这样避免了密钥泄露双方扯皮，或者在传递过程中被截获（RSA根本不需要传递任何约定的东西，公钥是可以公开传递的）
从原理上说，其理论依据为：一个大素数由两个小素数乘积获得，从两个小素数获得大素数比较容易，而从大素数分解为两个小素数则非常困难。
RSA的公式如下：
公钥（KU）：
n=两个素数p和q的乘积（注意p和q必须保密，否则是可以破解的）
e=与(p-1)(q-1)互质的任意数，最好小于(p-1)(q-1)
私钥（KR）：
n=和公钥的n一致
d需要满足这个公式：e*d mod (p-1)(q-1)=1
先举个例子验证一下，先搞一个简单的例子。
假设p=3，q=11，n=33，(p-1)*(q-1)=20
随便取一个e=17，17是和20互质的。
d的话需要满足公式：e*d mod (p-1)(q-1)=1，这个只能靠枚举了。
| d | e*d | (p-1)(q-1) | e*d mod (p-1)(q-1) |
|---|---|---|---|
| 1 | 17 | 20 | 3 |
| 2 | 34 | 20 | 14 |
| 3 | 51 | 20 | 11 |
| 4 | 68 | 20 | 8 |
| 5 | 85 | 20 | 5 |
| 6 | 102 | 20 | 2 |
| 7 | 119 | 20 | 19 |
| 8 | 136 | 20 | 16 |
| 9 | 153 | 20 | 13 |
| 10 | 170 | 20 | 10 |
| 11 | 187 | 20 | 7 |
| 12 | 204 | 20 | 4 |
| 13 | 221 | 20 | 1 |
找到了一个d=13，满足ed mod (p-1)(q-1)=1，即1317=221 mod 20 = 1
于是得出公钥KU=（e，n）=（17，33）
私钥KR=（d，n）=（13，33）
加密和解密的算法为：
明文=密文^e （mod n），密文=明文^d (mod n）
假设需要加密的明文是13，14，15，密文是x，y，z，那么密文的公式为：
x^e ( mod n）= 13 即 x^17 （mod 33）= 13
y^e ( mod n）= 14 即 x^17 （mod 33）= 14
z^e ( mod n）= 15 即 x^17 （mod 33）= 15
通过枚举获得x=19，y=5，z=9
明文13对应密文19
明文14对应密文5
明文15对应密文9
通过密文计算明文的算法为
明文^d ( mod n ) = 19 即 明文^13 （mod n）=19，计算得到明文=13
一小段验证代码：
public static void main(String[] args) {
int e = 17;
int d = 13;
int n = 33;
int ming = 19;
BigDecimal number = new BigDecimal(1);
while (true) {
BigDecimal number2 = number.pow(d).remainder(new BigDecimal(n));
if (number2.intValue() != ming) {
System.out.println(number + " " + number.pow(e) + " " + number2);
number = number.add(new BigDecimal(1));
} else {
int mi = number2.intValue();
System.out.println("success");
System.out.println(number + " " + number.pow(e) + " " + number2);
break;
}
}
}
