帮我解释一下RSA算法的原理

给你个java的代码你，希望对你有帮助
package standard.system;

import java.io.UnsupportedEncodingException;
import java.net.URLDecoder;
import java.net.URLEncoder;
import java.util.Random;

public class RSACrypt {
private static int _PrivateKey = 32823; // 私钥

private static int _PublicKey = 20643; // 公钥

private static int _Modulus = 29893; // 模数

// 对数字进行加密解密运算,根据key为公钥或是私钥来判断对数字进行加密或解密操作
private static int Crypt(int number, int key) {
int mod;
int i;
int result = 0;

try {
mod = number * number % _Modulus;
if (key % 2 == 0) {
result = 1;
for (i = 0; i < key / 2; i++) {
result = mod * result % _Modulus;
}
} else {
result = number;
for (i = 0; i < key / 2; i++) {
result = mod * result % _Modulus;
}
}
} catch (Exception e) {
}
return result;
}

// 根据字符位置将字符的ASCII数值进行偏移,并得到密文
public static String Encode(String message) {
int length = message.length(); // 明文的长度
int ascCode; // ASCII码
int cryptCode; // 密码
int rndCode; // 随机码
int index;
String encodeString = ""; // 密文

if (length == 0) {
return null;
}

// 产生随机码
Random rnd = new Random();
rndCode = 1 + rnd.nextInt(99);

for (index = 0; index < length; index++) {
// 获取单字符的ASCII码
ascCode = (int) message.charAt(index);
// 同一字符根据随机码偏移保证每次不同
ascCode += rndCode;
// 同一字符在不同位置保证不同
ascCode += index + 1; // 因索引值与domino不同（domino起始为1），所以此处加1
// 同一字符在字符串长度变化时保证不同
ascCode += length;
ascCode = ascCode % 128;

// 加密为密码
cryptCode = Crypt(ascCode, _PublicKey);
// 将密码转换为4位16进制字符串
encodeString += DecimalToHex(cryptCode, 4);
}

// 最后附上随机码的2位16进制字符串
encodeString += DecimalToHex(rndCode, 2);

return encodeString;
}

// 将密文转换为明文,再对明文进行字位偏移,最终得到原文
public static String Decode(String message) {
int length = message.length() - 2; // 剥离随机码后的密文长度
int ascCode; // ASCII码
int cryptCode; // 密码
int rndCode; // 随机码
int index;
String decodeString = ""; // 明文
// 获取随机码的10进制数字
rndCode = HexToDecimal(message.substring(length));
for (index = 0; index < length; index += 4) {
// 将4位16进制字符串转换为10进制密码
cryptCode = HexToDecimal(message.substring(index, index + 4));
// 解密为明码
ascCode = Crypt(cryptCode, _PrivateKey);

// 还原随机码偏移
ascCode -= rndCode;
// 还原字位偏移
ascCode += (length / 4 % 128 + 1) * 128 - (index + 1) / 4 - 1; // 因索引值与domino不同（domino起始为1），所以此处加1
// 还原字符串长度偏移
ascCode += (length / 4 % 128 + 1) * 128 - length / 4;
ascCode = ascCode % 128;

// 将ASCII码转换为字符
decodeString += (char) ascCode;
}

return decodeString;
}

// 10进制数字转16进制字符串
private static String DecimalToHex(int decNumber, int hexWidth) {
String hexString = Integer.toHexString(decNumber);
while (hexString.length() < hexWidth)
hexString = "0" + hexString;
return hexString;
}

// 16进制字符串转10进制数字
private static int HexToDecimal(String hexString) {
return Integer.parseInt(hexString, 16);
}

public static void main(String[] args) throws UnsupportedEncodingException {
String str = "测试158228&&2008-10-23_15:39:58";
System.out.println(str);
str = URLEncoder.encode(str, "UTF-8");
System.out.println(str);
for (int i = 0; i < 10; i++) {
String r = RSACrypt.Encode(str);
System.out.println(r);
System.out.println(URLDecoder.decode(RSACrypt.Decode(r), "UTF-8"));
}

}
}

RSA算法非常简单，概述如下：
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e<t并且e与t互素（就是最大公因数为1）
取d*e%t==1

这样最终得到三个数： n d e

设消息为数M (M <n)
设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则 m == M，从而完成对c的解密。
注：**表示次方,上面两式中的d和e可以互换。

在对称加密中：
n d两个数构成公钥，可以告诉别人；
n e两个数构成私钥，e自己保留，不让任何人知道。
给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。
别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。

rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解
从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法
求得d。

RSA简洁幽雅，但计算速度比较慢，通常加密中并不是直接使用RSA 来对所有的信息进行加密，
最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用
RSA对刚才的加密密钥进行加密。

最后需要说明的是，当前小于1024位的N已经被证明是不安全的
自己使用中不要使用小于1024位的RSA，最好使用2048位的。

首先, 找出三个数, p, q, r,
其中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数
p, q, r 这三个数便是 private key

接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1
这个 m 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了
再来, 计算 n = pq
m, n 这两个数便是 public key

编码过程是, 若资料为 a, 将其看成是一个大整数, 假设 a < n
如果 a >= n 的话, 就将 a 表成 s 进位 (s <= n, 通常取 s = 2^t),
则每一位数均小於 n, 然後分段编码
接下来, 计算 b == a^m mod n, (0 <= b < n),
b 就是编码後的资料

解码的过程是, 计算 c == b^r mod pq (0 <= c < pq),
於是乎, 解码完毕.等会会证明 c 和 a 其实是相等的 :)

如果第三者进行窃听时, 他会得到几个数: m, n(=pq), b
他如果要解码的话, 必须想办法得到 r所以, 他必须先对 n 作质因数分解.
要防止他分解, 最有效的方法是找两个非常的大质数 p, q,
使第三者作因数分解时发生困难
<定理>
若 p, q 是相异质数, rm == 1 mod (p-1)(q-1),
a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq,
则 c == a mod pq

证明的过程, 会用到费马小定理, 叙述如下:
m 是任一质数, n 是任一整数, 则 n^m == n mod m
(换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m)
运用一些基本的群论的知识, 就可以很容易地证出费马小定理的
<证明>
因为 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数
因为在 modulo 中是 preserve 乘法的
(x == y mod z and u == v mod z => xu == yv mod z),
所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq

1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时,
则 a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q
所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
即 a^(k(p-1)(q-1)) == 1 mod pq
=> c == a^(k(p-1)(q-1)+1) == a mod pq

2. 如果 a 是 p 的倍数, 但不是 q 的倍数时,
则 a^(q-1) == 1 mod q (费马小定理)
=> a^(k(p-1)(q-1)) == 1 mod q
=> c == a^(k(p-1)(q-1)+1) == a mod q
=> q | c - a
因 p | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod p
=> p | c - a
所以, pq | c - a => c == a mod pq

3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上

4. 如果 a 同时是 p 和 q 的倍数时,
则 pq | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod pq
=> pq | c - a
=> c == a mod pq
Q.E.D.

这个定理说明 a 经过编码为 b 再经过解码为 c 时, a == c mod n (n = pq)
但我们在做编码解码时, 限制 0 <= a < n, 0 <= c < n,
所以这就是说 a 等於 c, 所以这个过程确实能做到编码解码的功能