经典非对称加密算法：RSA算法原理、实现详解（C++、Java）

痛定思痛。 2023-07-15 11:21 39阅读 0赞

### 目录 ###

*   *  零、写在最前
     *   *  参数说明
     *  一、RSA算法原理介绍
     *  二、实验步骤（含实验方法与关键代码)
     *   *   *  1. 创建项目
             *  2. 设计加密、解密的总体流程
             *  3. 设计素数类PrimeNum，包括两个静态方法
             *  4. 设计解密器类Decryption。
             *  5. 设计加密器类Encryption
     *  三、总结
 *  四、代码下载

## 零、写在最前 ##

本文利用C++或Java实现RSA算法，使用面向对象的方法，分别实现文件的加密和解密方法。

加密方法格式为：  
void encrypt（String file,String destFile）\{…\}

解密方法格式为：  
void decode（ String file,String destFile）\{…\}

密钥生成方法格式为：  
String genKey(int length) \{…\}

### 参数说明 ###

file 待加密(解密)的文件路径

destFile 加密(解密)后文件的存放路径

length 密钥的二进制长度

我基于Eclipse Java开发环境，通过编程实现RSA算法。通过本实验，可以理解非对称密码算法和公钥密码体制的基本原理，掌握RSA算法的计算过程和安全性约束。

## 一、RSA算法原理介绍 ##

RSA加密算法是一种非对称加密算法，是一种分组密码体制算法。对极大整数做因数分解的难度决定了RSA算法的可靠性。推导过程涉及较多数学定理，在这里仅关注算法的具体实现。该算法的实现过程为：

1.  取两个随机大素数p和q（保密）。
2.  计算公开的模数n=pq（公开）。
3.  计算秘密的欧拉函数fi（n）=（p-1）（q-1）（保密），两个素数p和q不再需要，应该丢弃，不要让任何人知道。
4.  随机选取整数e，满足gcd（e, fi（n））=1（公开e，加密密钥）。 计算d，满足de≡1（mod fi（n））（保密d，解密密钥，陷门信息）。
5.  将明文x（其值的范围在0到n-1之间）按模为n自乘e次幂以完成加密操作，从而产生密文y（其值也在0到r-1范围内）。
6.  将密文y按模为n自乘d次幂，完成解密操作。

## 二、实验步骤（含实验方法与关键代码) ##

#### 1. 创建项目 ####

在Eclipse Java中新建一个名为“RsaAlogrithm”的项目，基于面向对象的程序设计思想，在源程序src目录下创建Main.java。

#### 2. 设计加密、解密的总体流程 ####

RSA算法实现了数字的加密与解密过程，为了实现对一般字符的加密，我们设计三个文件，并作如下处理：

(1) 明文.txt  
该明文应不受限制，可以是任意一篇文献，可以包括中文、字母、各类标点符号、数字等字符。我们取其中的每一个字符ch，将int(ch)，即该字符对应的ASCII码作为明文输入x。

(2) 密文.txt  
我们可以得到明文数字x对应的密文数字y。考虑到y的范围远超ASCII码可以表示的范围，我们在密文文件中直接存储数字y。

(3) 密文解密.txt  
读取密文文件，得到密文数字y，通过解密方法得到明文数字x。但x并不是原本的明文文件中的字符，而是明文字符对应的ASCII码。因此，我们需要将解密得到的x转换为其在ASCII表中对应的字符，即char(x)。

将第三个文件与第一个文件进行比对，即可检验程序设计的正确性与健壮性。经过如上处理，程序可以对任一篇明文进行加密与解密，对明文中的字母、数字、标点等均起作用。基于该思想，我们开始进行类的设计。

#### 3. 设计素数类PrimeNum，包括两个静态方法 ####

（1) 判断一个数是否为素数

private static boolean isPrimeNum(long num) { 
    		if(num<2) return false;
    		for(int i=2; i<=num/2; i++)
    			if(num%i==0)
    				return false;
    		return true;
    	}

（2) 随机生成素数

public static long getRandomPrimeNum() { 
    		long num=0;
    		while(true) { 
    			num=Math.abs(new Random().nextLong());
    			if(isPrimeNum(num))
    				return num;
    		}	
    	}

#### 4. 设计解密器类Decryption。 ####

（1) 私有数据成员

private long fi,d,p,q;

各变量的具体含义见上面介绍的RSA原理，  
其中的p与q将在使用后销毁。

（2) 公有数据成员

public long n=0,e;

各变量的具体含义见上面介绍的RSA原理。

（3) 求最大公约数函数：基于欧几里得算法，生成密钥时调用

public long gcd(long a,long b) { 
            if(b==0)
                return a;
            else
                return gcd(b,a%b);
    	}

（4) 密钥生成函数：生成指定长度的密钥

public void genKey(int length) { 
    		while(n==0||Long.toBinaryString(n).length()!=length) { 
    			p=PrimeNum.getRandomPrimeNum();
    			q=PrimeNum.getRandomPrimeNum();
    			n=p*q;
    			if(Long.toBinaryString(n).length()!=length)
    				continue;
    			fi=(p-1)*(q-1);
    			e=Math.abs(new Random().nextLong()+1)%fi;
    			while(gcd(e,fi)!=1) { 
    				e=Math.abs(new Random().nextLong()+1)%fi;
    			}		
    			d=euclid(e,fi);
    		}
    		System.out.println("取随机素数p="+p+",q="+q+",生成"+length+"位密钥");
    		p=0;
    		q=0;
    	}

下面有几个关键问题：

（a) 如何保证密钥的二进制长度为length？  
为保证密钥长度为length，每生成一对大素数p、q，若n=pq的长度不符合要求，则循环生成p与q，直至n的二进制长度为length。最坏情况下，该算法的时间复杂度为O(length)；最优情况下，该算法的时间复杂度为O(1)。

（b) 如何随机获取大素数？  
调用PrimeNum.getRandomPrimeNum()方法，该方法将返回一个长度不超过32位的随机素数。在length（取32）的制约下，p、q的值较大，达到预期。

（c) 如何求解同余方程 XY % M = 1？  
在求解d时，调用euclid(e,fi)。euclid()方法基于欧几里得拓展算法实现，核心代码为：

long a=e,b=fi;
    	long x=0,y=1,x0=1,y0=0,q=0,t=0;
    	while(b!=0) { 
    	    q=a/b; t=a%b; a=b; b=t;
    		t=x; x=x0-q*x; x0=t;
    		t=y; y=y0-q*y; y0=t;
    	}
    	if(x0<0) x0+=fi;
    	return x0;

（f) 如何模拟p、q的丢弃？  
将p、q清零，实现两个大素数的销毁。

（5) 解密方法：将密文翻译成明文

BigInteger yy=new BigInteger(line);
    	BigInteger rs=new BigInteger("1");
    	BigInteger nn=new BigInteger(n+"");
    	long dd=d;
    	while(dd>0) { 
    		if(dd%2==1) { 
    			rs=rs.multiply(yy);
    			rs=rs.remainder(nn);
    		}
    		dd=dd/2;
    		yy=yy.multiply(yy);
    		yy=yy.remainder(nn);
    	}
    	out.write((char)rs.intValue());
    	out.flush();

下面有几个关键问题：

（a) 如何实现文件的读写？  
创建文件读写对象BufferedReader br与BufferedWriter out。String line=br.readLine()实现file文件按行读入。

（b) 如何处理大数运算  
在这里我选择一种较为简单的做法：BigInteger大数类。该类在理论上可以处理任意长度的数值。核心代码为：

BigInteger yy=new BigInteger(line);
    BigInteger rs=new BigInteger("1");
    …
    rs=rs.multiply(yy);

BigInteger运算速度慢于Integer，那么如何解决这个问题呢？这也就是下一个问题。

（c) 如何快速进行模幂运算  
对于幂模运算 `A**B%N`，若按照一般算法，首先A\*\*B将执行B次运算，时间复杂度为O(B)，运算结果将是一个非常大的数，再把运算结果取模N，无论是时间复杂度还是空间复杂度均不理想。因此，使用快速幂算法、蒙哥马利算法，实现快速进行模幂运算。核心代码为：

while(dd>0) { 
    		if(dd%2==1) { 
    			rs=rs.multiply(yy);
    			rs=rs.remainder(nn);
    		}
    		dd=dd/2;
    		yy=yy.multiply(yy);
    		yy=yy.remainder(nn);
    	}

实验结果表明，对于32位长度密钥，该算法可以在较短时间内得到预期结果。

#### 5. 设计加密器类Encryption ####

(1) 公有数据成员

public long n,e;

即公钥，由加密器类生成后公开。

(2) 设计加密方法  
加密方法的具体实现过程与解密方法类似。核心代码为：

for(int i=0; i<line.length(); i++) { 
    	char ch=line.charAt(i);
    	long x=(int) ch, ee=e;
    	BigInteger rs=new BigInteger("1");
    	BigInteger nn=new BigInteger(n+"");
    	BigInteger xx=new BigInteger(x+"");
    	while(ee>0) { 
    		if(ee%2==1) { 
    			rs=rs.multiply(xx);
    			rs=rs.remainder(nn);
    		}
    		ee/=2;
    		xx=xx.multiply(xx);
    		xx=xx.remainder(nn);
    	}
    	out.write(rs.toString()+"\n");
    	out.flush();
    }

## 三、总结 ##

1.  基于面向对象的程序设计思想，设计了加密器类、解密器类，体现了RSA算法的真实流程，保证了私钥的安全性；
2.  保证了大素数p、q生成的随机性；
3.  实现了文件读写，程序从文件中读取明文/密文，将加密/解密的结果写入文件中，而不是控制台输入明文；
4.  明文文件支持任意字符（包括但不限于中文字符、英文字符），而不仅是数字。
5.  支持由用户输入预期的密钥二进制长度，程序将生成该长度的密钥；
6.  支持大数运算；
7.  使用了欧几里得拓展算法，可以快速求解同余方程，从而快速确定d的值；
8.  使用了蒙哥马利算法与快速幂，可以快速进行模幂运算。

# 四、代码下载 #

其实前面已经把代码介绍地很详细了，强烈推荐大家按照博客中的步骤自己写一下代码，弄清楚每一个模块是做什么的。知其然，更要知其所以然！

为了方便，我也上传了[RSA算法的Java实现与C++实现][RSA_Java_C]。

如果本文对你有帮助，请给博主点个赞鼓励下吧~

[RSA_Java_C]: https://download.csdn.net/download/qq_41112170/17236948