一、RSA 介绍

以下引自百度百科

RSA 是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

需要注意的是，RSA 加密的安全性并不是依赖于大整数分解，而是求解高次同余方程的困难性。因为存在一些方法(例如共模攻击)能够绕过大整数分解来解密。

二、RSA 算法流程

生成两个大素数(现较为安全的大小为 1024bit ) \(p\) 和 \(q\)，令 \(N=p \cdot q, \; \varphi(N) = (p-1) \cdot (q-1)\)

并选取加密指数 \(e\)，使得 \(gcd(e,\varphi(N))=1\)，即 \(e\) 和 \(\varphi(N)\) 互素

将 \(e\) 和 \(N\) 公开

求解同余方程 \(e \cdot x = 1 (mod \; \varphi(N))\)，解为 \(d\)

若 \(d<0\)，则令 \(d=d+\varphi(N)\)

设明文为 \(c\)，加密过程为 \(m=c^e (mod \; N)\)，\(d\) 为加密后的密文

解密过程为 \(c' = m^d (mod \; N)\)，\(c'\) 为解密后的结果，即 \(c'=c\)

三、RSA 算法的 java 实现

1. 核心内容

1.1 Random 类

由于我们需要随机生成素数，故需要调用随机数，该类将配合后续的 BigInteger 类来生成随机大素数

1.2 BigInteger 类

在 RSA 中，我们需要使用长达 1024bit 的素数，显然一般的 int 类型并不能满足我们的要求，所以需要采用 java 中的 BigInteger 类，即高精度整数类

在 BigInteger 类中，并不能像 int 类那样直接使用 + - * / % 进行计算，需要调用 BigInteger 类的方法

在此处需要用到的是 add(加法)，multiply(乘法) ，divide(除法) 和 remainder(取余)

在 BigInteger 类中，也不能直接用 == 判断两个元素是否相等，需要调用 equals 方法

对于常用的值(例如0，1)，可以直接使用 BigInteger.ZERO 和 BigInteger.ONE 调用

对于其他值，可以通过 BigInteger.valueOf 来生成，例如 BigInteger.valueOf(-1) 生成 -1 对应的高精度整数

使用 BigInteger 类中的 probablePrime 方法还能够生成指定长度的随机素数，该方法传入待生成素数的长度 LENGTH 和随机数种子 rnd 作为参数

1.3 解密指数的求解

通过上文的算法流程可以知道，求解解密指数 \(d\) 就是求解同余方程 \(e \cdot x = 1 (mod \varphi(N))\)

由扩展欧几里得算法，可以求出整数 \(u,v\)，使得 \(u \cdot e + v \cdot \varphi(N) = gcd(e,\varphi(N))=1\)

1.4 扩展欧几里得算法

首先，有定理 \(gcd(a,b)=gcd(b,a \; mod \; b)\)

接下来的过程需要一些线性代数中的矩阵相关知识

首先，有 \(\left[ \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right] \cdot \left[ \begin{matrix} a \\ b \end{matrix} \right]= \left[ \begin{matrix} a \\ b \end{matrix} \right]\)

令 \(q=[\frac{a}{b}]\)，即 \(q\) 为 \(a \div b\) 的整数部分，构建矩阵 \(\left[ \begin{matrix} 0 & 1 \\ 1 & -q \end{matrix} \right]\)

将等式两端同时乘以上述矩阵，则有 \(\left[ \begin{matrix} 0 & 1 \\ 1 & -q \end{matrix} \right] \cdot \left[ \begin{matrix} a\\b \end{matrix} \right]= \left[ \begin{matrix} b \\ a-q \cdot b \end{matrix} \right]\)

即 \(\left[ \begin{matrix} 0 & 1 \\ 1 & -q \end{matrix} \right] \cdot \left[ \begin{matrix} a\\b \end{matrix} \right]= \left[ \begin{matrix} b \\ a \; mod \; b \end{matrix} \right]\)

再令 \(q'=[\frac{b}{a \; mod \; b}]\)，重复上述步骤

最终有 \(\left[ \begin{matrix} u & v \\ u' & v' \end{matrix} \right] \cdot \left[ \begin{matrix} a\\b \end{matrix} \right]= \left[ \begin{matrix} gcd(a,b) \\ 0 \end{matrix} \right]\)

即求出 \(u \cdot a + v \cdot b = gcd(a,b)\)

通过上述方法，可以求解出解密指数 \(d\)

1.5 模幂运算

在加密或者解密中，都需要对一个大数进行幂次方后取模的运算

使用 BigInteger 类中的 modPow 方法即可

2. java 代码

/* RSA.java */

import java.math.BigInteger;

import java.util.Random;

public class RSA {

/* 2x2矩阵相乘 */

private static BigInteger[][] MatrixMultiply(BigInteger[][] matrix_1,BigInteger[][] matrix_2){

BigInteger[][] res = new BigInteger[2][2];//结果矩阵

for(int i=0;i<2;i++){

for(int j=0;j<2;j++){

BigInteger temp=BigInteger.ZERO;

/* [i][j]位置的元素=左矩阵第i行 与 右矩阵第j列 依次相乘 */

for(int k=0;k<2;k++){

temp=temp.add(matrix_1[i][k].multiply(matrix_2[k][j]));//求出下标为[i][j]位置的元素值

}

res[i][j]=temp;

}

}

return res;

}

/* 利用扩展欧式算法求出a在模b下的逆 */

static BigInteger InverseElement(BigInteger a,BigInteger b){

/* 初始矩阵 */

BigInteger[][] res = new BigInteger[][]{

{BigInteger.ONE,BigInteger.ZERO},//1 0

{BigInteger.ZERO,BigInteger.ONE} //0 1

};

while(!b.equals(BigInteger.ZERO)){

/* 左乘构建矩阵

* 0 1

* 1 -q

*/

BigInteger q=a.divide(b);

res=MatrixMultiply(new BigInteger[][]{

{BigInteger.ZERO,BigInteger.ONE},

{BigInteger.ONE,q.multiply(BigInteger.valueOf(-1))}

},res);//左乘操作阵

/* 普通的辗转相除法 */

BigInteger temp=a.remainder(b);

a=b;

b=temp;

}

return res[0][0];

}

public static void main(String[] args){

Random rnd=new Random();//创建随机数发生器，默认以当前时间为种子

final int LENGTH=1024;//定义p,q位数

final int e_LENGTH=16;//e的位数

BigInteger p,q,N;

BigInteger e,d,pi_N;

BigInteger c,m,res;

p=BigInteger.probablePrime(LENGTH,rnd);//创建1024位的随机素数p

q=BigInteger.probablePrime(LENGTH,rnd);//创建1024位的随机素数q

N=p.multiply(q);//N=p*q

System.out.println("[创建p,q]");

System.out.println("p:"+p);

System.out.println("q:"+q);

pi_N=p.subtract(BigInteger.ONE).multiply((q.subtract(BigInteger.ONE)));//pi_N=(p-1)*(q-1)

e=BigInteger.probablePrime(e_LENGTH,rnd);//生成指数e

d=InverseElement(e,pi_N);//获取e在模pi_N下的逆d

if(d.compareTo(BigInteger.ZERO)<0) d=d.add(pi_N);//保证d为正数

System.out.println("[创建e，d]");

System.out.println("e:"+e);

System.out.println("d:"+d);

c=BigInteger.probablePrime(LENGTH,rnd);//创建明文c

m=c.modPow(e,N);//加密明文c得密文m

System.out.println("[创建明文c]");

System.out.println("c:"+c);

System.out.println("[加密明文c得密文m]");

System.out.println("m:"+m);

res=m.modPow(d,N);//解密密文m得明文res

System.out.println("[解密密文m得明文res]");

System.out.println("res:"+res);

System.out.print("检验解密正确性:"+c.equals(res));

}

}