RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。 对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。
密文=明文^E mod N
RSA加密,是明文的E次方,然后除以N的余数。 公式中的{E,N}的组合是RSA的公钥 。E,N 不是随便的数就可以的,需要经过严密的计算。
明文=密文^D mod N
RSA解密,是对密文的D次方,然后除以N的余数。公式中的 {D,N}的组合是RSA的私钥匙 ,同样 N 是加密过程中的N,D也不是任意一个数字就可以的,也是需要经过严密的计算的。
我们知道了RSA加密和解密的过程,运算过程中,需要使用的 E、D、N 这些数字需要严密的计算,那E、D、N 到底是应该如何计算呢? 计算分为如下几个步骤: (1)求N 首先准备两个很大的质数,p和q ,p 和q 太小的话,密钥很拥有被破解。
N = P*Q
(2)求L L 是 P-1 和 Q-1 的最小公倍数。lcm(X,Y)表示 “X和Y的最小公倍数”。
L = lcm(P-1,Q-1)
(3)求E E是一个比 1 大,比L小的数,此外 E 和 L的最大公约数必须是1,gcd(X,Y)表示"X和Y的最小公约数", E和L的关系需满足如下等式。
第一等式: 1 < E <L 第二等式: gcd(E,L)=1
要找出满足 gcd(E,L) =1 的数据,需要使用伪随机数生成器,通过伪随机数生成器,在1<E<L 的范围内生成E的候选数,然后判断是否满足 gcd(E,L) =1这个条件,求最大公约数可以使用 欧几里得的辗转相处法。 这么复杂的过程,找出N,目的是为了保证一定存在解密的时候需要的D。 (4)求D 数字 D 是由 E 计算出来的,D ,E ,L 满足如下关系。
第一等式 : 1<D < L 第二等式 : E * D mod L = 1
(1)求 N 我们首先准备两个质数,
P = 13 Q = 17 N = P *Q = 221
(2) 求 L
L = lcm(p-1,q-1) L=lcm(12,16) L=48
(3) 求 E
第一等式: 1 < E <48 第二等式: gcd(E,48)=1 E 和L 的最大公约数是1 。
满足 E 的数据 5、7、11、13、17、19、23、25、29、31、35、37、41、43 我们这些选择 7 作为 E。 公钥 E = 13 ,N = 221 (4) 求 D
第一等式 : 1<D < L , 1 < D < 48 第二等式 : E * D mod L = 1 , 5 * D mod 48 = 1
D=37 满足上述条件。 (5) 公钥与私有
E = 13 D = 37 N = 221
(6) 加密
密文 = (m明文=10)^E(13)% N(221) =62
(7)解密
明文 = (密文=62)^(D)37 % N (221) = 62 ^37%221 = ( 62^10%221 ) * ( 62^10%221 ) * ( 62^7%221 ) % 221 = (62^5%221 * 62^5%221 %221)* (62^5%221 * 62^5%221 %221) * (62^5%221 * 62^5%221 %221) * (62^5%221 * 62^2%221 %221) %221 = (95 * 95 % 221) * (95 * 95 %221)(95 * 95 %221)* (95 * 62 * 62 %221) % 221 = 10
package lzf.cipher.jdk;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.NoSuchAlgorithmException;
import java.security.interfaces.RSAPrivateCrtKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import javax.crypto.Cipher;
/**
* @author Java小工匠
*/
public class JdkRsaUtils {
// 初始化密钥对
public static KeyPair initKey() {
try {
KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA");
// 512 -65536 && 64 的倍数
generator.initialize(1024);
return generator.generateKeyPair();
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
}
// 获取公钥
public static byte[] getPublicKey(KeyPair keyPair) {
byte[] bytes = keyPair.getPublic().getEncoded();
return bytes;
}
// 获取公钥
public static String getPublicKeyStr(KeyPair keyPair) {
byte[] bytes = keyPair.getPublic().getEncoded();
return encodeHex(bytes);
}
// 获取私钥
public static byte[] getPrivateKey(KeyPair keyPair) {
byte[] bytes = keyPair.getPrivate().getEncoded();
return bytes;
}
// 获取私钥
public static String getPrivateKeyStr(KeyPair keyPair) {
byte[] bytes = keyPair.getPrivate().getEncoded();
return encodeHex(bytes);
}
// 加密数据
public static byte[] encryptRsa(byte[] data, byte[] key) {
try {
KeyFactory keyFactory = KeyFactory.getInstance("RSA");
X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(key);
RSAPublicKey secretKey = (RSAPublicKey) keyFactory.generatePublic(x509KeySpec);
Cipher cipher = Cipher.getInstance("RSA");
cipher.init(Cipher.PUBLIC_KEY, secretKey);
byte[] rs = cipher.doFinal(data);
return rs;
} catch (Exception e) {
throw new RuntimeException(e);
}
}
// 解密数据
public static byte[] decryptRsa(byte[] data, byte[] key) {
try {
KeyFactory keyFactory = KeyFactory.getInstance("RSA");
PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(key);
RSAPrivateCrtKey secretKey = (RSAPrivateCrtKey) keyFactory.generatePrivate(keySpec);
Cipher cipher = Cipher.getInstance("RSA");
cipher.init(Cipher.PRIVATE_KEY, secretKey);
byte[] rs = cipher.doFinal(data);
return rs;
} catch (Exception e) {
throw new RuntimeException(e);
}
}
// 数据准16进制编码
public static String encodeHex(final byte[] data) {
return encodeHex(data, true);
}
// 数据转16进制编码
public static String encodeHex(final byte[] data, final boolean toLowerCase) {
final char[] DIGITS_LOWER = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
final char[] DIGITS_UPPER = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
final char[] toDigits = toLowerCase ? DIGITS_LOWER : DIGITS_UPPER;
final int l = data.length;
final char[] out = new char[l << 1];
// two characters form the hex value.
for (int i = 0, j = 0; i < l; i++) {
out[j++] = toDigits[(0xF0 & data[i]) >>> 4];
out[j++] = toDigits[0x0F & data[i]];
}
return new String(out);
}
public static void main(String[] args) throws Exception {
String str = "java小工匠";
KeyPair keyPair = initKey();
byte[] publicKey = getPublicKey(keyPair);
byte[] privateKey = getPrivateKey(keyPair);
byte[] secretData = encryptRsa(str.getBytes(), publicKey);
System.out.println("RSA加密:" + encodeHex(secretData));
byte[] data = decryptRsa(secretData, privateKey);
System.out.println("RSA解密:" + new String(data));
}
}