经典非对称加密算法:RSA算法原理、实现详解(C++、Java)
目录
- 零、写在最前
- 参数说明
- 一、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算法的可靠性。推导过程涉及较多数学定理,在这里仅关注算法的具体实现。该算法的实现过程为:
- 取两个随机大素数p和q(保密)。
- 计算公开的模数n=pq(公开)。
- 计算秘密的欧拉函数fi(n)=(p-1)(q-1)(保密),两个素数p和q不再需要,应该丢弃,不要让任何人知道。
- 随机选取整数e,满足gcd(e, fi(n))=1(公开e,加密密钥)。 计算d,满足de≡1(mod fi(n))(保密d,解密密钥,陷门信息)。
- 将明文x(其值的范围在0到n-1之间)按模为n自乘e次幂以完成加密操作,从而产生密文y(其值也在0到r-1范围内)。
- 将密文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();
}
三、总结
- 基于面向对象的程序设计思想,设计了加密器类、解密器类,体现了RSA算法的真实流程,保证了私钥的安全性;
- 保证了大素数p、q生成的随机性;
- 实现了文件读写,程序从文件中读取明文/密文,将加密/解密的结果写入文件中,而不是控制台输入明文;
- 明文文件支持任意字符(包括但不限于中文字符、英文字符),而不仅是数字。
- 支持由用户输入预期的密钥二进制长度,程序将生成该长度的密钥;
- 支持大数运算;
- 使用了欧几里得拓展算法,可以快速求解同余方程,从而快速确定d的值;
- 使用了蒙哥马利算法与快速幂,可以快速进行模幂运算。
四、代码下载
其实前面已经把代码介绍地很详细了,强烈推荐大家按照博客中的步骤自己写一下代码,弄清楚每一个模块是做什么的。知其然,更要知其所以然!
为了方便,我也上传了RSA算法的Java实现与C++实现。
如果本文对你有帮助,请给博主点个赞鼓励下吧~