Java RSA 算法基本实现

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止，世界上还没有任何可靠的攻击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基本过程：

(1)选取两个大素数p、q：这里我是用Java BigInteger自带的probablePrime()素数生成函数得到的

(2)根据选取的p、q计算出n和φ(n)

(3)从1—φ(n)之间选取一个随机整数e(e要与φ(n)互质)，

(4)计算e对于φ(n)的模反元素d(关于模反元素可以去看上面那两篇文章)

这样，我们就得到了公钥(n,e)和私钥(n,d)，把公钥公开，这样别人把要发给你的消息用你的公钥加密，加密后的消息只能用你的私钥才能解密得到明文信息，只要你的密匙长度足够长，理论上是不可能被别人破解的

下面贴上简单实现RSA加密解密的代码：

package com.eridani.rsa;

import java.io.UnsupportedEncodingException;
import java.math.BigInteger;
import java.net.URLDecoder;
import java.net.URLEncoder;
import java.security.SecureRandom;
import java.util.Random;

public class a {

 public static void main(String[] args) throws UnsupportedEncodingException {
  // 随机生成两个2048位比特大质数
  Random random = new SecureRandom();
  BigInteger p = BigInteger.probablePrime(2048, random);
  BigInteger q = BigInteger.probablePrime(2048, random);

  BigInteger[][] key = getKey(p, q); // 获取公钥和私钥

  String string = "陈独秀同学，请你坐下！";
  string = URLEncoder.encode(string ,"utf-8");
  
  byte[] bs = string.getBytes();
  BigInteger m = new BigInteger(bs); // 要加密的数据

  BigInteger c = exmode(m, key[0][1], key[0][0]); // 加密
  BigInteger d = exmode(c, key[1][1], key[1][0]); // 解密

  byte[] b = d.toByteArray();

  String string2 = new String(b);
  string2 = URLDecoder.decode(string2, "utf-8");
  String mm = m.toString(), cc = c.toString(), dd = d.toString(), pp = p.toString(), qq = q.toString();

  System.out.println("加密前为：" + URLDecoder.decode(string, "utf-8"));
  System.out.println("加密前mm=：" + mm);
   System.out.println("加密后为：" + cc);
  System.out.println("解密后d=：" + dd);
  System.out.println("解密后为：" + string2);
 }

 public static BigInteger[][] getKey(BigInteger p, BigInteger q) { // 生成公钥和私钥的方法
  BigInteger n = p.multiply(q);
  BigInteger x, y;
  BigInteger fn = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));

  BigInteger e = new BigInteger("65537"); // 一般选取e=65537
  BigInteger a = e;
  BigInteger b = fn;
  BigInteger result[] = gcd(a, b);
  while ((result[0].compareTo(BigInteger.ZERO)) == -1) {
   result[0] = result[0].add(fn); // 求出的d必须要大于0
  }
  BigInteger d = result[0];
  BigInteger[][] key = new BigInteger[2][2];

  key[0][0] = n;
  key[0][1] = e; // 获得公钥
  key[1][0] = n;
  key[1][1] = d; // 获得私钥
  return key;
 }

 private static BigInteger[] gcd(BigInteger a, BigInteger b) { // 拓展欧几里得算法求出d
  if (b.equals(BigInteger.ZERO)) {
   BigInteger[] result = new BigInteger[3];
   result[0] = BigInteger.ONE;
   result[1] = BigInteger.ZERO;
   result[2] = a;
   return result;
  } else {
   BigInteger[] result = new BigInteger[3];
   result = gcd(b, a.mod(b));
   BigInteger x = result[0];
   result[0] = result[1];
   result[1] = x.subtract((a.divide(b)).multiply(result[1]));
   return result;
  }
 }

 public static BigInteger exmode(BigInteger m, BigInteger ex, BigInteger n) { // 加密解密求法
  return m.modPow(ex, n);
 }

}

Java RSA 算法基本实现

浏览过的版块