RSA算法Java的简单实现

浏览数：23 / 时间：2015年06月08日

RSA简介

RSA算法据说是目前地球上最重要的加密算法。维基百科是这么介绍的：“对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。”

看上去很神奇是吧，其实在学习网络安全和密码学这门课的时候，都接触过。毕业近一年了，数论方面的知识忘的差不多了。如果大家对RSA算法原理很感兴趣，推荐下面这两篇文章：

http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

本文描述下，我自己实现的一个简单的RSA算法。

RSA密钥生成和加密解密过程

技术分享

RSA的具体实现

RSA具体实现的难点在于质数的生成。好在Java提供了一个强大的工具类BigInteger。具体的实现如下

（不过百行）：

public class RSA {
	private BigInteger p = null;
	private BigInteger q = null;
	private BigInteger n = null;
	private BigInteger totient = null;
	private BigInteger e = null;
	private BigInteger d = null;
	public RSA(BigInteger p, BigInteger q) {
		this.p = p;
		this.q = q;
		n = p.multiply(q); // n = p * q;//totient =(p-1)*(q-1)即 (n)
		totient = (p.subtract(BigInteger.valueOf(1)).multiply((q
				.subtract(BigInteger.valueOf(1)))));

                e = getE();//选择公钥
		BigInteger y = egcd(totient, e)[1];
                d = y.mod(totient); //产生私钥
	}
	public BigInteger getE() {
		// 这里以totient/4为种子，选取一个素数作为公钥
		return totient.divide(BigInteger.valueOf(4)).nextProbablePrime();
	}
        // 扩展的Euclid算法，目的：算出e-1 mod n
	public static BigInteger[] egcd(BigInteger d1, BigInteger d2) {
		BigInteger[] ret = new BigInteger[3];
		BigInteger u = BigInteger.valueOf(1), u1 = BigInteger.valueOf(0);
		BigInteger v = BigInteger.valueOf(0), v1 = BigInteger.valueOf(1);
		if (d2.compareTo(d1) > 0) {
			BigInteger tem = d1;
			d1 = d2;
			d2 = tem;
		}
		while (d2.compareTo(BigInteger.valueOf(0)) != 0) {
			BigInteger tq = d1.divide(d2); // tq = d1 / d2
			BigInteger tu = u;
			u = u1;
			u1 = tu.subtract(tq.multiply(u1)); // u1 =tu - tq * u1
			BigInteger tv = v;
			v = v1;
			v1 = tv.subtract(tq.multiply(v1)); // v1 = tv - tq * v1
			BigInteger td1 = d1;
			d1 = d2;
			d2 = td1.subtract(tq.multiply(d2)); // d2 = td1 - tq * d2
			ret[0] = u;
			ret[1] = v;
			ret[2] = d1;
		}
		return ret;
	}
        // 加密
	public BigInteger encode(BigInteger d) {
		return d.modPow(this.e, this.n);
	}
        // 解密
	public BigInteger decode(BigInteger c) {
		return c.modPow(this.d, this.n);
	}
}

RSA的缺点

RSA算法使用乘方运算，明文以分组为单位进行加密，每个分组的二进制值均小于n也就是说分组的大

小必须小于或等于log2(n)+1位。如果明文分组大于此长度，则需要进一步细分，或者借助另外一种对

称的加密算法来进行加密。此外，RSA加密解密效率不高，特别是密钥长度很长的时候，不适合对大

量信息进行加密。所以一般RSA会和其他对称的加密算法配合使用。

下面是我本科毕设中设计的一个简单的加密方案，以及前几天根据这个方案写的一个demo。

技术分享