大家好，又见面了，我是你们的朋友全栈君。
RSA加密算法是目前应用最广泛的公钥加密算法，特别适用于通过Internet传送的数据，常用于数字签名和密钥交换。那么我今天就给大家介绍一下如何利用Java编程来实现RSA加密算法。
一、RSA加密算法描述
RSA加密算法是1978年提出的。经过多年的分析和研究，在众多的公开密钥加密算法中，RSA加密算法最受推崇，它也被推荐为公开密钥数据加密标准。
由数论知识可知，若将一个具有大素数因子的合数进行分解是很困难的，或者说这个问题的计算量是令人望而生畏的，而RSA加密算法正是建立在这个基础上的。
在RSA加密算法中，—个用户A可根据以下步骤来选择密钥和进行密码转换：
(1)随机的选取两个不同的大素数p和q(一般为100位以上的十进制数)，予以保密；
(2)计算n=p*q，作为用户A的模数，予以公开；
(3)计算欧拉(Euler)函数z=(p-1)*(q-1)，予以保密；
(4)随机的选取d与z互质，作为A的公开密钥；
(5)利用Euclid算法计算满足同余方程e*d≡1modz的解d，作为用户A的保密密钥；
(6)任何向用户A发送信息M的用户，可以用A的公开模数D和公开密钥e根据C=Me mod n得到密文C；
RSA加密算法的安全性是基于大素数分解的困难性。攻击者可以分解已知的n，得到p和q，然后可得到z；最后用Euclid算法，由e和z得到d。然而要分解200位的数，需要大约40亿年。
二、用Java语言描述RSA加密算法的原理
假设我们需要将信息从机器A传到机器B，首先由机器B随机确定一个private_kcy(我们称之为密钥)，可将这个private_key始终保存在机器B中而不发出来。然后，由这个private_key计算出public_key(我们称之为公钥)。这个public_key的特性是：几乎不可能通过该public_key计算生成它的priyate_key。接下来通过网络把这个public_key传给机器A，机器A收到public_key后，利用public_key将信息加密，并把加密后的信息通过网络发送到机器B，最后机器B利用已知的pri.rate_key，就可以解开加密信息。
步骤：
(1)首先选择两个大素数p和q，计算n=p*q；m=(p-1)(q一1)；
(2)而后随机选择加密密钥public_key，要求和m互质(比如public_key=m-1)；
(3)利用Euclid算法计算解密密钥priyate_key，使private_key满足public_key*private_key—1(mod m)，其中public_key，n是作为公钥已知，priVate_key是密钥；
(4)加密信息text时，利用公式secretWord=texI^Public_key (mod n)得到密文8ecretword；
(5)解密时利用公式word=text^priVate_key(mod n)得到原文word=text。
三、用java编程实现RSA加密算法过程
1、产生大素数
实现RSA加密算法的第一个步骤是产生大素数p和q，采用的方法是产生随机数而后对其进行素性判断，故实现RSA加密算法的一个重要技术是随机数的产生。RSA加密算法中的大素数的随机性直接影响算法的安全性，如果素数产生时随机性差，就很容易被重复，因而也就是不安全的。然而，要人工产生真正的随机数是不可能的，一般情况下计算机产生的随机数都足伪随机数，但是，用一些算法产生的伪随机数的随机性非常接近真正的随机数，可以满足密码学的要求。
JAVA的标准包java .security中的SecureRandom类提供了一个基于SHA-1散列算法的强伪随机数生成器，该生成算法生成的随机序列具有比较理想的随机性。使用该方法生成随机序列后，利用Biglnteger类中的intcertainty方法对产生的随机序列进行多次素性测试，则通过该测试的随机序列为素数的概率为1-(1／2)m(设素性判断的次数是m次)。不难看出，当m取一个比较大的整数时，该序列为素数的概率近似为1。
生成N位的大素数p和q的主要代码如下：
SecureRandom rnd=new SecureRandom();//生成随机序列
Biglnteger p=new Biglnteger(m.200, md);//生成p
Biglnteger q=new Biglnteger(m, 200, md);//生成q
2、计算乘积n和模数Φ(n)
Biglnteger类中已经预先定义了基本的数学运算方法，如multiply、subtract等，利用这些方法可以非常快捷地计算n=p*q和Φ(n)=(p—1)(q—1)。具体实现代码如下：
Biglnteger u=(p.subtract(new Biglnteger(“1”)
multiply(q．subtract(new Biglnteger(“1”)))；//计算模数Φ(n)
n=p．multiply(q)；//计算乘积n
3、生成密钥对e和d
适当选择RSA加密算法的公钥e，可以大大加快算法的实现速度。例如，可以选e为3、17或65537，它们的二进制表示式中都只有两个1，可以大大减少运算量。但是e太小时可能会导致低加密指数攻击，本程序选取e为65537，这样可以在提高算法速度的同时保证安全性。
得到e后，需要根据：d=e-1modΦ(n)计算私钥d，即d是e的乘法逆元，Biglnteger类中的modlnverse方法可以直接用来计算乘法逆元d，选取e以及根据e计算d的部分代码为：
e=new Biglnteger(”65537i”);//选择公钥e为65537
d=PK．modlnverse(u);//根据e求私钥d
4、加密和解密
RSA加密算法的加密和解密过程中均需要计算大整数的幂之后模n，在程序实现上可以利用Biglnteger类中的modPow方法，该方法是计算一个大整数的幂与另外一个大整数的模。分别在程序中的RSA类中定义加密方法encrypt和解密方法decrypt：
Biglnteger encrypt(Biglnteger message)
{
return message.modPow(e,n),)//加密
Biglnteger decrypt(Biglnteger encrypted)
{
retum encrypted. modPow(d,n);
}
//解密
在加密和解密中分别调用RSA类中对应的加密方法enaypt和解密方法decrypt，即可获得对应的密文和明文。
四、程序执行结果
此RSA加密程序的开发环境为eclipse-SDK-3.0.1，在Pentium(R) Dual T2310 (1.4G)，1G内存， 在Windows XP系统计算机上调试成功。在操作系统的命令提示符下进入程序所在路径，键入“java rsa”，根据提示输入加密密钥位数以及明文，程序执行结果如图所示。
程序根据设定的公钥65537计算出私钥，并对明文进行了加密和解密操作，执行结果验证了程序的正确性。
RSA加密体制既可用于关键数据文件加密，也可用于数字签名，目前已被广泛应用于各种安全和认证领域，如Web服务器和浏览器信息安全，Email的安全和认证。对远程登录的安全保证和网上银行的身份验证等。运用JAVA语言实现的RSA密码算法，结合了JAVA语言良好的跨平台性和安全性，具有广阔的应用前景。
小知识之公开密钥
公开密钥也称为非对称密钥，每个人都有一对唯一对应的密钥：公开密钥(简称公钥)和私人密钥(简称私钥)，公钥对外公开，私钥由个人秘密保存；用其中一把密钥加密，就只能用另一把密钥解密。非对称密钥加密算法的典型代表是RSA。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/140992.html原文链接：https://javaforall.cn
