RSA详解（Java实现）

　　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);