RSA加密算法原理及其Java实现

简单介绍了RSA加密算法的原理及其Java实现：原文过长时，进行了分段加密。

RSA加密算法的基本原理

主要步骤

本文所有的字母都为正整数。

其主要步骤如下：

1、取两个不相等的质数p、q，一般都比较大。例如：p=67，q=79。

2、n=p×q，其中n所对应的二进制长度即为密钥的长度，一般为1024位或2048位。n=67×79=5293，转化为二进制数为1 0100 1010 1101，共13位。

3、计算n的欧拉函数f(n):

欧拉函数f(n)定义为：小于n的正整数中和n组成互斥关系的正整数的个数。由欧拉函数的性质：（1）如果正整数可以分解为两个互斥整数之积，则有该正整数的欧拉函数等于两个互斥整数的欧拉函数之积；（2）如果整数为质数，其欧拉函数为该整数减一。则有：

f(n)=f(p)∗f(q)=(p−1)∗(q−1)(1)f(n)=f(p)*f(q)=(p-1)*(q-1)\tag{1}f(n)=f(p)∗f(q)=(p−1)∗(q−1)(1)

f(n)=66×78=5148

4、任选一整数x满足1<x<f(n)，且x与f(n)互斥。选x=19

5、计算x关于f(n)的模反元素y，即满足：

(x∗y)%f(n)=1xy=hf(n)+1(2)(x*y)\%f(n)=1\tag{2}\\ xy=hf(n)+1(x∗y)%f(n)=1xy=hf(n)+1(2)

%为取余。

通过扩展欧几里得算法求解19y=5148h+1：

求得y=271，h=-1。

则(n,x)为公钥，(n,y)为私钥，假设原文为a（这里的原文是要转换为ascii码或者其他编码方式，用数字表示），且a小于n，则获取密文b的加密过程为：

b=ax%n(3)b=a^{x}\%n\tag{3}b=ax%n(3)

解密过程为：

a=by%n(4)a=b^{y}\%n\tag{4}a=by%n(4)

假设传递字符A，其ascii码值为65，则通过(3)式计算得到b=1863，通过(4)式解密得到a=65。注意这里数字足够大，以至于使用普通整数计算得到的结果是错误的。

BigInteger num1 = new BigInteger("65");BigInteger num2 = new BigInteger("5293");BigInteger b = num1.pow(19).mod(num2);System.out.println(b); System.out.println("普通的整数运算是错误的："+Math.pow(65, 19)%5293); BigInteger a = b.pow(271).mod(num2);System.out.println(a);// 输出为：1863普通的整数运算是错误的：4055.065

可靠性说明：因为公钥是公开的，所以破解的方法就是获取y，那么在已知n和x的情况下能否求解出y呢？

（1）通过步骤5可知，只有知道x和f(n)才能求解y；

（2）要计算f(n)需要得到p和q；

（3）n=pq，只有将n进行因式分解才能算出p和q。

大整数的因式分解是很难的，所以RSA加密算法可靠。

解密过程证明

下面给出解密公式正确性的证明，即证明(4)式成立：

通过(3)式得：

b=ax−kn(5)b=a^{x}-kn\tag{5}b=ax−kn(5)

将(5)式代入到(4)式等号右边得：

by%n=(ax−kn)y%n=(axy+nK(n))%n=axy%n(6)b^{y}\%n=(a^{x}-kn)^{y}\%n=(a^{xy}+nK(n))\%n=a^{xy}\%n\tag{6}by%n=(ax−kn)y%n=(axy+nK(n))%n=axy%n(6)

这里用到了多项式的因式分解：

(x+y)n=xn+(n1)xyn−1+...+(nn−1)xn−1y+yn(7)(x+y)^n=x^n+\binom{n}{1}xy^{n-1}+...+\binom{n}{n-1}x^{n-1}y+y^{n}\tag{7}(x+y)n=xn+(1n​)xyn−1+...+(n−1n​)xn−1y+yn(7)

其中只有第一项不包含y。

将(2)式代入到(6)式，则只需要证明：

ahf(n)+1%n=a(8)a^{hf(n)+1}\%n=a\tag{8}ahf(n)+1%n=a(8)

下面分情况进行讨论：

情况1、a和n互斥。

这里引入欧拉定理：如果a和n互斥，n的欧拉函数为f(n)，则

af(n)%n=1(9)a^{f(n)}\%n=1\tag{9}af(n)%n=1(9)

根据欧拉定理：

af(n)=1+gn→ahf(n)=(1+gn)hahf(n)+1=af(n)∗a=(1+gn)h∗a=(1+hgn+...+hgh−1nh−1+ghnh)a(10)a^{f(n)}=1+gn→a^{hf(n)}=(1+gn)^{h}\\ a^{hf(n)+1}=a^{f(n)}*a=(1+gn)^{h}*a=(1+hgn+...+hg^{h-1}n^{h-1}+g^{h}n^{h})a\tag{10}af(n)=1+gn→ahf(n)=(1+gn)hahf(n)+1=af(n)∗a=(1+gn)h∗a=(1+hgn+...+hgh−1nh−1+ghnh)a(10)

将(10)式代入到(8)式，则可证明(8)式成立。

情况2、a和n不互斥。

由于n为两个质数的乘积，a<n，所以必有a=kp或a=kq，不妨假设a=kp，此时a与q互斥。根据欧拉定理：

af(q)%q=1→af(q)=1+gq(11)a^{f(q)}\%q=1→a^{f(q)}=1+gq\tag{11} af(q)%q=1→af(q)=1+gq(11)

ahf(n)+1%q=(af(q))f(p)∗a%q=(1+gq)f(p)∗a%q=aahf(n)+1=a+tq(12)a^{hf(n)+1}\%q=(a^{f(q)})^{f(p)}*a\%q=(1+gq)^{f(p)}*a\%q=a\tag{12}\\ a^{hf(n)+1}=a+tqahf(n)+1%q=(af(q))f(p)∗a%q=(1+gq)f(p)∗a%q=aahf(n)+1=a+tq(12)

因为a=kp，所以必然有：

ahf(n)+1%p=0(13)a^{hf(n)+1}\%p=0\tag{13}ahf(n)+1%p=0(13)

即

(a+tq)%p=tq%p=0(14)(a+tq)\%p=tq\%p=0\tag{14}(a+tq)%p=tq%p=0(14)

又因为pq互斥，则由t=rp，代入到式(12)得：

ahf(n)+1=a+rpq=a+rn(a+rn)%n=a→ahf(n)+1%n=aa^{hf(n)+1}=a+rpq=a+rn\\ (a+rn)\%n=a→a^{hf(n)+1}\%n=aahf(n)+1=a+rpq=a+rn(a+rn)%n=a→ahf(n)+1%n=a

得证(8)式。

结合情况1、2，则可证明解密公式得正确性。

java实现

package mytest;import java.security.KeyFactory;import java.security.KeyPair;import java.security.KeyPairGenerator;import java.security.NoSuchAlgorithmException;import java.security.SecureRandom;import java.security.interfaces.RSAPrivateCrtKey;import java.security.interfaces.RSAPrivateKey;import java.security.interfaces.RSAPublicKey;import java.security.spec.PKCS8EncodedKeySpec;import java.security.spec.X509EncodedKeySpec;import java.util.Arrays;import java.util.Base64;import java.util.HashMap;import java.util.Map;import java.util.Scanner;import javax.crypto.Cipher;public class RSAUtil {// 密钥长度,可调public static int keyLength = 1025;// 注意这里1024对应128byte，其中11byte用来存储相关信息，所以1024最多加密117Byte数据// 若超过117Byte需要分段，计算公式为keyLength/8并向上取整再减去11// 解密时候长度为keyLength/8向上取整// 存储密钥public static Map<String, String> keyMap = new HashMap<String, String>();public static void main(String[] args) throws Exception {//生成公钥和私钥geneKeyPair();// 输入原文System.out.print("输入原文：");Scanner in = new Scanner(System.in);String message = in.nextLine();//String message = "1aa";System.out.println("随机生成的公钥为:" + keyMap.get("publicKey"));System.out.println("随机生成的私钥为:" + keyMap.get("privateKey"));//加密字符串String messageEnctypt = encrypt(message, keyMap.get("publicKey"));System.out.println("原文:"+message + "\n加密后的字符串为:" + messageEnctypt);String messageDecrypt = decrypt(messageEnctypt, keyMap.get("privateKey"));System.out.println("还原后的字符串为:" + messageDecrypt);in.close();}/*** function:随机生成密钥对并存放在keyMap中* 也可以直接保存RSAPublicKey对象和RSAPrivateCrtKey对象* 一般情况下密钥可能会保存在本地或者其他地方，然后直接读取密钥，这时候存储的一般是密钥字符串* @throws NoSuchAlgorithmException */public static void geneKeyPair() throws NoSuchAlgorithmException {// RSA密钥生成器KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");// 初始化密钥生成器keyPairGenerator.initialize(keyLength, new SecureRandom());// 生成密钥对并保存KeyPair keyPair = keyPairGenerator.generateKeyPair();RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic(); // 公钥RSAPrivateCrtKey privateKey = (RSAPrivateCrtKey) keyPair.getPrivate(); // 私钥String publicKeyString = Base64.getEncoder().encodeToString(publicKey.getEncoded()); // 公钥字符串String privateKeyString = Base64.getEncoder().encodeToString(privateKey.getEncoded()); // 私钥字符串// 存放keyMap.put("publicKey", publicKeyString);keyMap.put("privateKey", privateKeyString);}/** function:加密* @param 明文* @param 公钥字符串,十六进制字符串* @return 密文* @throws Exception*/public static String encrypt(String input, String publicKeyString) throws Exception {// 从字符串获取公钥byte[] decoded = Base64.getDecoder().decode(publicKeyString.getBytes());RSAPublicKey publicKey = (RSAPublicKey) KeyFactory.getInstance("RSA").generatePublic(new X509EncodedKeySpec(decoded)); // 加密Cipher cipher = Cipher.getInstance("RSA");cipher.init(Cipher.ENCRYPT_MODE, publicKey);byte[] inputArr = input.getBytes();StringBuilder output = new StringBuilder();int splitLength = (int) Math.ceil((float)keyLength/8) - 11; // 分段长度for(int i = 0; i < inputArr.length; i += splitLength) {// 分段加密int len = inputArr.length-i >= splitLength ? splitLength : inputArr.length-i;output.append(byteArray2HexString(cipher.doFinal(Arrays.copyOfRange(inputArr, i, i+len))));}return output.toString();}/** function:私钥解密* @param 密文* @param 私钥字符串* @return 明文* @throws Exception*/public static String decrypt(String input, String privateKeyString) throws Exception {// 从字符串获取私钥byte[] decoded = Base64.getDecoder().decode(privateKeyString.getBytes());RSAPrivateKey privateKey = (RSAPrivateKey) KeyFactory.getInstance("RSA").generatePrivate(new PKCS8EncodedKeySpec(decoded)); // 解密Cipher cipher = Cipher.getInstance("RSA");cipher.init(Cipher.DECRYPT_MODE, privateKey);int splitLength = (int) Math.ceil((float)privateKey.getModulus().bitLength()/8); // 分段长度byte[] inputArr = hexString2byteArray(input);StringBuilder output = new StringBuilder();for(int i = 0; i < inputArr.length; i += splitLength) {// 分段解密int len = inputArr.length-i >= splitLength ? splitLength : inputArr.length-i;output.append(new String(cipher.doFinal(Arrays.copyOfRange(inputArr, i, i+len))));}return output.toString();}public static int getKeyLength() {return keyLength;}/** function：设置密钥长度*/public static void setKeyLength(int keyLength) {// RSA keys must be at least 512 bits longif(keyLength < 512) {keyLength = 512;}RSAUtil.keyLength = keyLength;}/** function:byte[]转换为十六进制字符串* byte占8位，可以用两位16进制数表示* @param byte[]* @return String*/public static String byteArray2HexString(byte[] bytes) {StringBuilder output = new StringBuilder();String temp;for(byte b : bytes) {temp = Integer.toHexString(0xff & b);if(temp.length() == 1) {output.append(0);}output.append(temp);}return output.toString();}/** function:十六进制字符串转换位byte[]* @param String* @return byte[]*/public static byte[] hexString2byteArray(String hexString) {int len = hexString.length() / 2;byte[] output = new byte[len];for(int i = 0; i < len; i++) {int pos = i * 2;output[i] = (byte) (char2Byte(hexString.charAt(pos)) << 4 | char2Byte(hexString.charAt(pos+1)));}return output;}/** function: char转换位byte,这里的char只包含0123456789abcdef* @param char* @return byte*/private static byte char2Byte(char c) {byte b = (byte)"0123456789abcdef".indexOf(c);return b;}}

测试结果：

输入原文：sadjhfkkjasdghjkhadkjsdhgksdhgjkshgdweuosyhjkhfsdg5sd4g5s4dg1564h56d4as1gd521f56a1sa3f54a654g5s6d41fg56ha456sd41f23g1h5a6s4dg1gf2asd5g45随机生成的公钥为:MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCo+UfWVK/CQVayLR5DRy9ydyahLUjr0Eq4xD6pXmMouNWgSjWkiEiQ2eWE3RfAVI89qGYwvD76VvBd+uO9lMLZmh3aVk+Iu0ajTwEt4UxI3T3oGpirYYHWIBHNmcKrRyuGPpQZd+klNzzJeiS+/4Ee5mOPEKun5kJs33D61o4kKwIDAQAB随机生成的私钥为:MIICdQIBADANBgkqhkiG9w0BAQEFAASCAl8wggJbAgEAAoGBAKj5R9ZUr8JBVrItHkNHL3J3JqEtSOvQSrjEPqleYyi41aBKNaSISJDZ5YTdF8BUjz2oZjC8PvpW8F36472UwtmaHdpWT4i7RqNPAS3hTEjdPegamKthgdYgEc2ZwqtHK4Y+lBl36SU3PMl6JL7/gR7mY48Qq6fmQmzfcPrWjiQrAgMBAAECgYBZKkodMM0abc4o8aQRjoPcHEH3NWVQgrabb3s9dsBOodKg5egOrZfVUBZMmTrKVBTOTYm3V+7HvY7TmOwKg3CZ9UzxYrhhIbh7p42gAIlpnyiq7YCz3X0hz+FrRKEOJJ5eLINKxl6w3jOG1ZeY9FIHUrGIb0KJe/a5m1gkG8zFoQJBAN0zS/DPpDNJKCrnxRs1TijtLdL9JgOle7ecPKp2kbJQB6RLmJ5/675JrlR1SD5N9E4KUdgEsyF4uUr3cew6XlsCQQDDjpcTHn3wgjZOGU8WAuNHV132TSfT1YiCttFjRuXNtGVrmYdbyZh77g6qbk+DxjJ1Zw0dNh1WhsGyLOTCI9pxAkAJxW1SWunG9jFXC9vyIr2sIyYGDvax7Ip1hupLIWe4N77OrCQ2xDHWuwx/YJrrXagwFladMz/yd5G/1QRsSfvHAkB50wuEapt0R/oCnzuob7YczG2Jsbkc+0pme/NnUFR62GXSKTusz6LBmaTjQYMhiUgH4WHHD94o+BwUnmkIFIPRAkAr5ToL9zeevlwYvIxqd4++Vdcfm+1uDbxa0Rjm00ay5S3fS/3jXHs0j+CB2faxakVUYueMKmdUoYpWKfgOOk7A原文:sadjhfkkjasdghjkhadkjsdhgksdhgjkshgdweuosyhjkhfsdg5sd4g5s4dg1564h56d4as1gd521f56a1sa3f54a654g5s6d41fg56ha456sd41f23g1h5a6s4dg1gf2asd5g45加密后的字符串为:9186b953a69941d47b35e0abff66356c03b29e3b0be1b1187f845fd212f2bf14e9fe56484fd5b15b23782d960545bb6cb1a992142315857a6f2854e81f89c6b5e15cf9b5496350c17224f1820fe4445044ce0adf10eba16d130dd63885b6ede13a3670009e2493f1eeaaee35e67fdcd8373692449dab4382196d85ee84861680fc1613ce132c731d6be0d34e00c7ed04a6a0c8b695a0f91983931de47ec2221575d60023cf223ac5b70c047c9c6b155e20723770cbdb13f45014656244f1894205cb8a2a4d029b3cdd2de9b1cbf1729e5ddcdf3314145c6db93a593b8e1f38c70dc064147a3d6ffaf9a21d338fa5d9a676a9449e37c8d9446abea15f1dfc还原后的字符串为:sadjhfkkjasdghjkhadkjsdhgksdhgjkshgdweuosyhjkhfsdg5sd4g5s4dg1564h56d4as1gd521f56a1sa3f54a654g5s6d41fg56ha456sd41f23g1h5a6s4dg1gf2asd5g45