@[TOC]
一、生成公钥和私钥
1、随机生成两个随机素数P，Q
2、将P、Q两个素数相乘得到一个数N，即N=P*Q（需要公开）
3、将P、Q分别减1再相乘得到一个数T，即T=(P-1)*(Q-1)
4、选择一个数E，E满足和T互质且E小于T
5、根据DE mod T = 1计算出密钥D
6、通过以上步骤可以得到N，E，D这3个数字，其中（N、E）作为公钥，（N、D）作为私钥（公钥和私钥可以互换）
二、加密和解密
接受方将生成的公钥（N，E）对外发布
1、用公钥加密
发送方用接受到的公钥（N，E）对密文M加密
密文：M
加密：ME <font size=3>mod</font> N = C
明文：C
2、用私钥解密
接受方用持有私钥（N，D）对明文C解密
明文：C
解密：CD <font size=3>mod</font> N = M
密文：M
三、java实现
public class RSA {
private int N; // 和公钥E一起分发出去
private int E; // E是公钥，随机选取（必须和T互质）
private int D; // D是密钥（D和E可以互换）
public RSA() {
createKey();
}
// 产生密钥
private void createKey() {
// 产生两个随机的素数
int p=61,q=53;
// 计算N和T
N = p*q;
int t = (p-1)*(q-1);
// 选择E（和T互质就行）
E = 17;
// 计算D
int[] r = new int[2];
Gcd.extendGcd(E, t, r); // 调用扩充欧几里得算法计算D
D = r[0];
// 调整d（d为正数）
while(D < 0) D +=t;
}
/**
* 利用公钥对密文m加密
* @param m 必须是整数，且m必须小于N
* @return c=pow(m,E)%N
*/
public int encrypt(int m) { // 注意，这里很容易溢出（虽然此算法已经极度简化了）
BigInteger bm = BigInteger.valueOf(m);
return bm.pow(E).mod(BigInteger.valueOf(N)).intValue();
}
/**
* 利用密钥对明文c解密
* @param c
* @return m1=pow(c, D)%N
*/
public int decrypt(int c) { // 同样考虑溢出情况
BigInteger bc = BigInteger.valueOf(c);
return bc.pow(D).mod(BigInteger.valueOf(N)).intValue();
}
public int getPublicKey() {
return E;
}
public void setPublicKey(int E) {
this.E = E;
}
public int getN() {
return N;
}
public void setN(int N) {
this.N = N;
}
public static void main(String[] args) {
RSA rsa = new RSA();
System.out.println("公钥：E="+rsa.getPublicKey()+",N="+rsa.getN()); // 打印公钥
int m = 65; // 明文
System.out.println("密文："+m);
int c = rsa.encrypt(m); // 对明文m加密，得到密文c
System.out.println("明文："+c);
int m1 = rsa.decrypt(c); // 对密文c解密，得到明文m1
System.out.println("解密出来的密文："+m1);
}
}
参考
阮一峰的博客RSA算法原理
周颖的《程序员的数学思维修炼》
