RSA是目前使用最廣泛的公鑰密碼體制之一。它是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_(kāi)頭字母拼在一起組成的。
RSA算法的安全性基于RSA問(wèn)題的困難性，也就是基于大整數(shù)因子分解的困難性上。但是RSA問(wèn)題不會(huì)比因子分解問(wèn)題更加困難，也就是說(shuō)，在沒(méi)有解決因子分解問(wèn)題的情況下可能解決RSA問(wèn)題，因此RSA算法并不是完全基于大整數(shù)因子分解的困難性上的。
1. RSA算法描述
1.1 RSA產(chǎn)生公私鑰對(duì)
具體實(shí)例講解如何生成密鑰對(duì)
1.隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù)p和q。
alice選擇了61和53。（實(shí)際應(yīng)用中，這兩個(gè)質(zhì)數(shù)越大，就越難破解。）2.計(jì)算p和q的乘積n。
n = 61×53 = 3233
n的長(zhǎng)度就是密鑰長(zhǎng)度。3233寫(xiě)成二進(jìn)制是110010100001，一共有12位，所以這個(gè)密鑰就是12位。實(shí)際應(yīng)用中，RSA密鑰一般是1024位，重要場(chǎng)合則為2048位。3.計(jì)算n的歐拉函數(shù)φ(n)。稱作L
根據(jù)公式φ(n) = (p-1)(q-1)
alice算出φ(3233)等于60×52，即3120。4.隨機(jī)選擇一個(gè)整數(shù)e，也就是公鑰當(dāng)中用來(lái)加密的那個(gè)數(shù)字
條件是1< e < φ(n)，且e與φ(n) 互質(zhì)。
alice就在1到3120之間，隨機(jī)選擇了17。（實(shí)際應(yīng)用中，常常選擇65537。）5.計(jì)算e對(duì)于φ(n)的模反元素d。也就是密鑰當(dāng)中用來(lái)解密的那個(gè)數(shù)字
所謂"模反元素"就是指有一個(gè)整數(shù)d，可以使得ed被φ(n)除的余數(shù)為1。ed ≡ 1 (mod φ(n))
alice找到了2753，即17*2753 mode 3120 = 16.將n和e封裝成公鑰，n和d封裝成私鑰。
在alice的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。
1.2 RSA加密
首先對(duì)明文進(jìn)行比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，然后依次對(duì)每個(gè)分組m做一次加密，所有分組的密文構(gòu)成的序列就是原始消息的加密結(jié)果，即m滿足0<=m<n，則加密算法為：
c≡ m^e mod n; c為密文，且0<=c<n。
1.3 RSA解密
對(duì)于密文0<=c<n，解密算法為：
m≡ c^d mod n;
1.4 RSA簽名驗(yàn)證
RSA密碼體制既可以用于加密又可以用于數(shù)字簽名。下面介紹RSA數(shù)字簽名的功能。
已知公鑰（e，n），私鑰d
- 1.對(duì)于消息m簽名為：sign ≡ m ^d mod n
- 2.驗(yàn)證：對(duì)于消息簽名對(duì)（m，sign），如果m ≡ sign ^e mod n，則sign是m的有效簽名
2.RSA公開(kāi)密鑰密碼體制
所謂的公開(kāi)密鑰密碼體制就是使用不同的加密密鑰與解密密鑰，是一種“由已知加密密鑰推導(dǎo)出解密密鑰在計(jì)算上是不可行的”密碼體制。
在公開(kāi)密鑰密碼體制中，加密密鑰（即公開(kāi)密鑰）PK是公開(kāi)信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密算法E和解密算法D也都是公開(kāi)的。雖然解密密鑰SK是由公開(kāi)密鑰PK決定的，但卻不能根據(jù)PK計(jì)算出SK。
根據(jù)密鑰的使用方法，可以將密碼分為對(duì)稱密碼和公鑰密碼
對(duì)稱密碼：加密和解密使用同一種密鑰的方式
公鑰密碼：加密和解密使用不同的密碼的方式，因此公鑰密碼通常也稱為非對(duì)稱密碼。
3. Java實(shí)現(xiàn)RSA生成公私鑰并加解密
3.1代碼如下
package com.tencent.blue.utils;
import org.apache.tomcat.util.codec.binary.Base64;
import org.apache.tomcat.util.http.fileupload.IOUtils;
import javax.crypto.Cipher;
import java.io.ByteArrayOutputStream;
import java.security.*;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.InvalidKeySpecException;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.HashMap;
import java.util.Map;
/**
* Created by cuiran on 19/1/9.
*/
public class RSAUtils {
public static final String CHARSET = "UTF-8";
public static final String RSA_ALGORITHM = "RSA";
public static Map<String, String> createKeys(int keySize){
//為RSA算法創(chuàng)建一個(gè)KeyPairGenerator對(duì)象
KeyPairGenerator kpg;
try{
kpg = KeyPairGenerator.getInstance(RSA_ALGORITHM);
}catch(NoSuchAlgorithmException e){
throw new IllegalArgumentException("No such algorithm-->[" + RSA_ALGORITHM + "]");
}
//初始化KeyPairGenerator對(duì)象,密鑰長(zhǎng)度
kpg.initialize(keySize);
//生成密匙對(duì)
KeyPair keyPair = kpg.generateKeyPair();
//得到公鑰
Key publicKey = keyPair.getPublic();
String publicKeyStr = Base64.encodeBase64URLSafeString(publicKey.getEncoded());
//得到私鑰
Key privateKey = keyPair.getPrivate();
String privateKeyStr = Base64.encodeBase64URLSafeString(privateKey.getEncoded());
Map<String, String> keyPairMap = new HashMap<String, String>();
keyPairMap.put("publicKey", publicKeyStr);
keyPairMap.put("privateKey", privateKeyStr);
return keyPairMap;
}
/**
* 得到公鑰
* @param publicKey 密鑰字符串（經(jīng)過(guò)base64編碼）
* @throws Exception
*/
public static RSAPublicKey getPublicKey(String publicKey) throws NoSuchAlgorithmException, InvalidKeySpecException {
//通過(guò)X509編碼的Key指令獲得公鑰對(duì)象
KeyFactory keyFactory = KeyFactory.getInstance(RSA_ALGORITHM);
X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(Base64.decodeBase64(publicKey));
RSAPublicKey key = (RSAPublicKey) keyFactory.generatePublic(x509KeySpec);
return key;
}
/**
* 得到私鑰
* @param privateKey 密鑰字符串（經(jīng)過(guò)base64編碼）
* @throws Exception
*/
public static RSAPrivateKey getPrivateKey(String privateKey) throws NoSuchAlgorithmException, InvalidKeySpecException {
//通過(guò)PKCS#8編碼的Key指令獲得私鑰對(duì)象
KeyFactory keyFactory = KeyFactory.getInstance(RSA_ALGORITHM);
PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(Base64.decodeBase64(privateKey));
RSAPrivateKey key = (RSAPrivateKey) keyFactory.generatePrivate(pkcs8KeySpec);
return key;
}
/**
* 公鑰加密
* @param data
* @param publicKey
* @return
*/
public static String publicEncrypt(String data, RSAPublicKey publicKey){
try{
Cipher cipher = Cipher.getInstance(RSA_ALGORITHM);
cipher.init(Cipher.ENCRYPT_MODE, publicKey);
return Base64.encodeBase64URLSafeString(rsaSplitCodec(cipher, Cipher.ENCRYPT_MODE, data.getBytes(CHARSET), publicKey.getModulus().bitLength()));
}catch(Exception e){
throw new RuntimeException("加密字符串[" + data + "]時(shí)遇到異常", e);
}
}
/**
* 私鑰解密
* @param data
* @param privateKey
* @return
*/
public static String privateDecrypt(String data, RSAPrivateKey privateKey){
try{
Cipher cipher = Cipher.getInstance(RSA_ALGORITHM);
cipher.init(Cipher.DECRYPT_MODE, privateKey);
return new String(rsaSplitCodec(cipher, Cipher.DECRYPT_MODE, Base64.decodeBase64(data), privateKey.getModulus().bitLength()), CHARSET);
}catch(Exception e){
throw new RuntimeException("解密字符串[" + data + "]時(shí)遇到異常", e);
}
}
/**
* 私鑰加密
* @param data
* @param privateKey
* @return
*/
public static String privateEncrypt(String data, RSAPrivateKey privateKey){
try{
Cipher cipher = Cipher.getInstance(RSA_ALGORITHM);
cipher.init(Cipher.ENCRYPT_MODE, privateKey);
return Base64.encodeBase64URLSafeString(rsaSplitCodec(cipher, Cipher.ENCRYPT_MODE, data.getBytes(CHARSET), privateKey.getModulus().bitLength()));
}catch(Exception e){
throw new RuntimeException("加密字符串[" + data + "]時(shí)遇到異常", e);
}
}
/**
* 公鑰解密
* @param data
* @param publicKey
* @return
*/
public static String publicDecrypt(String data, RSAPublicKey publicKey){
try{
Cipher cipher = Cipher.getInstance(RSA_ALGORITHM);
cipher.init(Cipher.DECRYPT_MODE, publicKey);
return new String(rsaSplitCodec(cipher, Cipher.DECRYPT_MODE, Base64.decodeBase64(data), publicKey.getModulus().bitLength()), CHARSET);
}catch(Exception e){
throw new RuntimeException("解密字符串[" + data + "]時(shí)遇到異常", e);
}
}
private static byte[] rsaSplitCodec(Cipher cipher, int opmode, byte[] datas, int keySize){
int maxBlock = 0;
if(opmode == Cipher.DECRYPT_MODE){
maxBlock = keySize / 8;
}else{
maxBlock = keySize / 8 - 11;
}
ByteArrayOutputStream
out = new ByteArrayOutputStream();
int offSet = 0;
byte[] buff;
int i = 0;
try{
while(datas.length > offSet){
if(datas.length-offSet > maxBlock){
buff = cipher.doFinal(datas, offSet, maxBlock);
}else{
buff = cipher.doFinal(datas, offSet, datas.length-offSet);
}
out.write(buff, 0, buff.length);
i++;
offSet = i * maxBlock;
}
}catch(Exception e){
throw new RuntimeException("加解密閥值為["+maxBlock+"]的數(shù)據(jù)時(shí)發(fā)生異常", e);
}
byte[] resultDatas = out.toByteArray();
IOUtils.closeQuietly(out);
return resultDatas;
}
public static void main (String[] args) throws Exception {
Map<String, String> keyMap = RSAUtils.createKeys(1024);
String publicKey = keyMap.get("publicKey");
String privateKey = keyMap.get("privateKey");
System.out.println("公鑰: \n\r" + publicKey);
System.out.println("私鑰： \n\r" + privateKey);
System.out.println("公鑰加密——私鑰解密");
String str = "code_cayden";
System.out.println("\r明文：\r\n" + str);
System.out.println("\r明文大小：\r\n" + str.getBytes().length);
String encodedData = RSAUtils.publicEncrypt(str, RSAUtils.getPublicKey(publicKey));
System.out.println("密文：\r\n" + encodedData);
String decodedData = RSAUtils.privateDecrypt(encodedData, RSAUtils.getPrivateKey(privateKey));
System.out.println("解密后文字: \r\n" + decodedData);
}
}
3.2 運(yùn)行結(jié)果如下
