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

}

}

總結

以上是生活随笔為你收集整理的java实现rsa欧几里得算法求d_RSA 加密算法的 java 实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。