RSA详解（Java实现）
rsa密码
rsa密码是1978年美国麻省理工学院三位密码学者r.l.rivest、a.shamir和l.adleman提出的一种基于大合数因子分解困难性的公开密钥密码。由于rsa密码既可用于加密，又可用于数字签名，通俗易懂，因此rsa密码已成为目前应用最广泛的公开密钥密码。
rsa加解密算法
1.随机地选择两个大素数p和q，而且保密；
2.计算n=pq，将n公开；
3.计算φ(n)=(p-1)(q-1)，对φ(n)保密；
4.随机地选取一个正整数e，1<e<φ(n)且(e,φ(n))=1，将e公开；
5.根据ed=1(mod φ(n))，求出d，并对d保密；
6.加密运算：c=me(mod n)；
7.解密运算：m=cd(mod n)。
注意：在加密运算和解密运算中，m和c的值都必须小于n，也就是说，如果明文（或密文）太大，必须进行分组加密（或解密）。
rsa密码的安全性
密码分析者攻击rsa密码的一种可能途径是截获密文c，通过m=cd(mod n)求出m。其中，n是公开的，而d是保密的。因为e是公开的，所以可以通过ed=1(mod φ(n))求出d，而φ(n)是保密的。虽然n是公开的，但是φ(n)=(p-1)(q-1)=pq-p-q+1=n-p-q+1，其中p和q是保密的，也就是说欲求得φ(n)必须知道p和q，即必须将n进行因式分解。
小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。由此可以得出，破译rsa密码的困难性约为对n进行因子分解的困难性。
rsa密码的安全性除了与因子分解密切相关之外，还与其参数p、q、e、d的选取有密切关系。只要合理地选取参数，并正确使用，rsa密码就是安全的。这就是目前rsa密码仍然广泛使用的重要原因。
java实现
编码实现rsa算法，主要需要实现以下几个部分：
1.对大数的素数判定（素数的概率性检验算法）；
2.模逆运算（扩展欧几里德算法）；
3.模指运算（反复平方乘快速模指算法）。
rsa
java提供了biginteger类，其中几个方法可以用于实现rsa。后续会提供上述三部分的相关代码。
1 p = biginteger.probableprime(new random().nextint(100) + 100, new random());
2 q = biginteger.probableprime(new random().nextint(100) + 100, new random());
3 n = p.multiply(q);
4 phi_n = p.subtract(biginteger.one).multiply(q.subtract(biginteger.one));
5 do {
6 e = new biginteger(new random().nextint(phi_n.bitlength() - 1) + 1, new random());
7 } while (e.compareto(phi_n) != -1 || e.gcd(phi_n).intvalue() != 1);
8 d = e.modpow(new biginteger("-1"), phi_n);
1 /**
2 * 加密
3 * <p> c=m^e(mod n)
4 * @param m
5 * @param n
6 * @param e
7 * @return
8 */
9 public static biginteger encrypt(biginteger m, biginteger n, biginteger e) {
10 return m.modpow(e, n);
11 }
1 /**
2 * 解密
3 * <p> m=c^d(mod n)
4 * @param c
5 * @param n
6 * @param d
7 * @return
8 */
9 public static biginteger decrypt(biginteger c, biginteger n, biginteger d) {
10 return c.modpow(d, n);
11 }
素数的概率性检验算法
执行该概率性算法所判断的正整数n不是素数的概率≤4-k。
1 /**
2 * 素数的概率性检验算法
3 * @param k
4 * @param n
5 * @return
6 */
7 static boolean isprime(int k, long n) {
8 list<long> a = new arraylist<long>();
9 int t = n - 2 > integer.max_value ? integer.max_value : (int) (n - 2);
10 do {
11 long l = (long) (new random().nextint(t - 2) + 2);
12 if (-1 == a.indexof(l))
13 a.add(l);
14 } while (a.size() < k);
15 for (int i = 0; i < k; i++)
16 if (! miller(n, a.get(i)))
17 return false;
18 return true;
19 }
20 static boolean miller(long n, long a) {
21 long m = n - 1;
22 int t = 0;
23 while (m % 2 == 0) {
24 m /= 2;
25 t++;
26 }
27 long b = modexp(a, m, n);
28 if (b == 1 || b == n - 1)
29 return true;
30 for (int j = 1; j < t; j++) {
31 b = b * b % n;
32 if (b == n - 1)
33 return true;
34 }
35 return false;
36 }
模逆算法
1 /**
2 * 模逆运算
3 * @param b
4 * @param m
5 * @return b^-1(mod m)
6 */
7 static long modinv(long b, long m) {
8 if (b >= m) b %= m;
9 return exgcd(b, m)[1] < 0 ? exgcd(b, m)[1] + m : exgcd(b, m)[1];
10 }
11 /**
12 * 扩展欧几里德算法
13 * <p>(a,b)=ax+by
14 * @param a
15 * @param b
16 * @return 返回一个long数组result，result[0]=x，result[1]=y，result[2]=(a,b)
17 */
18 static long[] exgcd(long a, long b) {
19 if (a < b) {
20 long temp = a;
21 a = b;
22 b = temp;
23 }
24 long[] result = new long[3];
25 if (b == 0) {
26 result[0] = 1;
27 result[1] = 0;
28 result[2] = a;
29 return result;
30 }
31 long[] temp = exgcd(b, a % b);
32 result[0] = temp[1];
33 result[1] = temp[0] - a / b * temp[1];
34 result[2] = temp[2];
35 return result;
36 }
模指算法
1 /**
2 * 模指运算
3 * @param b
4 * @param n
5 * @param m
6 * @return b^n(mod m)
7 */
8 static long modexp(long b, long n, long m) {
9 long result = 1;
10 b = b % m;
11 do {
12 if ((n & 1) == 1)
13 result=result*b%m;
14 b = b * b % m;
15 n = n >> 1;
16 } while (n != 0);
17 return result;
18 }
测试
测试数据
p=e86c7f16fd24818ffc502409d33a83c2a2a07fdfe971eb52de97a3de092980279ea29e32f378f5e6b7ab1049bb9e8c5eae84dbf2847eb94ff14c1e84cf568415
q=d7d9d94071fcc67ede82084bbedeae1aaf765917b6877f3193bbaeb5f9f36007127c9aa98d436a80b3cce3fcd56d57c4103fb18f1819d5c238a49b0985fe7b49
e=10001
m=b503be7137293906649e0ae436e29819ea2d06abf31e10091a7383349de84c5b
测试结果
参考文献
张焕国，唐明.密码学引论（第三版）.武汉大学出版社，2015年