RSA加密與解密

數據信息安全對我們每個人都有很重要的意義，特別是一些敏感信息，可能一些類似於收貨地址、手機號還沒引起大家的注意。但是最直白的，銀行卡、姓名、手機號、身份證號，如果這些信息被黑客攔截到，他就可以偽裝成你，把你的錢都取走。那我們該怎麼防止這樣的事情發生？報文加密解密，加簽驗籤。

我害怕什麼

我害怕卡里的錢被別人取走

我害怕轉賬的時候，報文被黑客攔截到，篡改信息轉到別人的賬戶。

我害怕我的敏感信息被有心人獲取

做一筆遊戲充值，半個小時就收到各種遊戲廣告，我並不能抵擋誘惑

我要做什麼

1. 交易報文不被篡改防止報文被篡改，需要對報文進行驗籤操作。
2. 敏感信息不被讀取防止報文被讀取，則需要將敏感信息加密。

公鑰和私鑰

公鑰和私鑰，加密解密和加簽驗籤。加解密用來保證數據安全，加簽驗籤用來證明身份。

商戶生成一對公私鑰(商公，商私)，商戶會把公鑰給銀行；銀行也會生成一對公私鑰(銀公，銀私)，銀行會把公鑰給商戶。也就是說：商戶有銀行的公鑰，自己的公鑰和私鑰。銀行有商戶的公鑰，自己的公鑰和私鑰

• 加密解密保證數據安全：商戶使用自己公鑰加密，銀行沒有商戶私鑰解不開報文，排除商戶使用自己的私鑰加密，銀行使用商戶公鑰解密。理論上可行，然而會出現這種情況，商戶和銀行1，2，3都使用相同的公私鑰，那麼自己私鑰加密後發送給銀行1的報文，被銀行2截取到也可以被解密開，違背了我們加密的目的--保證數據安全，排除。商戶使用銀行的公鑰加密，讓銀行用自己的私鑰解密。理論上可行，然而會出現這種情況，銀行會和商戶A，B，C都使用相同的公私鑰，那麼商戶A和商戶B發送過去的報文，銀行都能解開，而且只有此銀行的私鑰可以解開，達成了我們的目的。但是新的問題出現了，這種情況假如商戶A模擬商戶B的報文把商戶B的錢轉移走該怎麼辦？所以除了加密解密，還需要加簽驗籤。
• 加簽驗簽證明身份：加密已經完成，現在的問題只有怎麼讓銀行區分這筆請求是商戶A發的，還是商戶B發的。想讓銀行區分出各個商戶，拿出各個商戶最獨特的私鑰加簽即可，銀行拿出對應的商戶公鑰驗籤即可。
• 到此，報文交互形成了一個穩定且安全的循環

帶上代碼設計一套加解密

結構

兩對SHA1withRSA公私鑰+DES會話密鑰。結構如下：

加密加簽步驟：

1. 使用KeyGenerator隨機生成一個會話密鑰desKey
2. 報文明文+會話密鑰明文desKey對稱加密得到加密後的密文message。
3. 銀行的公鑰+會話密鑰desKey非對稱加密得到加密後的會話密鑰key。
4. 報文明文+商戶的私鑰非對稱加密得到報文數字簽名sign。
5. 將sign和key和message傳遞給銀行。

解密驗籤步驟：

1. 加密後的會話密鑰key+銀行的私鑰解密得到會話密鑰明文desKey
2. 對稱加密得到的密文message+會話密鑰明文desKey解密得到報文明文
3. 得到的明文+商戶的公鑰驗籤，得到報文是否被中途篡改過

代碼

1. 使用KeyGenerator隨機生成一個會話密鑰desKeyKeyGenerator keyGenerator = KeyGenerator.getInstance("DES"); SecretKey secretKey = keyGenerator.generateKey(); return secretKey.getEncoded();
2. 報文明文+會話密鑰明文desKey對稱加密得到加密後的密文message。public static String encryptContext(String context, byte[] desKey) throws Exception { byte[] encryptResult = des(context.getBytes("UTF-8"), desKey, 1); return Hex.encodeHexString(encryptResult); } private static byte[] des(byte[] inputBytes, byte[] keyBytes, int mode) throws Exception { DESKeySpec desKeySpec = new DESKeySpec(keyBytes); SecretKeyFactory keyFactory = SecretKeyFactory.getInstance("DES"); SecretKey secretKey = keyFactory.generateSecret(desKeySpec); IvParameterSpec iv = new IvParameterSpec(keyBytes); Cipher cipher = Cipher.getInstance("DES/CBC/PKCS5Padding"); cipher.init(mode, secretKey, iv); return cipher.doFinal(inputBytes); }
3. 銀行的公鑰+會話密鑰desKey非對稱加密得到加密後的會話密鑰key/** * RAS加密 * * @return byte[]

*/

public byte[] encryptRSA(byte[] plainBytes, boolean useBase64Code, String charset)

throws Exception {
 String CIPHER_ALGORITHM = "RSA/ECB/PKCS1Padding"; // 加密block需要預留11字節
 int KEYBIT = 2048;
 int RESERVEBYTES = 11;
 Cipher cipher = Cipher.getInstance(CIPHER_ALGORITHM);
 int decryptBlock = KEYBIT / 8; // 256 bytes
 int encryptBlock = decryptBlock - RESERVEBYTES; // 245 bytes
 // 計算分段加密的block數 (向上取整)
 int nBlock = (plainBytes.length / encryptBlock);
 if ((plainBytes.length % encryptBlock) != 0) { // 餘數非0，block數再加1
 nBlock += 1;
 }
 // 輸出buffer, 大小為nBlock個decryptBlock
 ByteArrayOutputStream outbuf = new ByteArrayOutputStream(nBlock * decryptBlock);
 cipher.init(Cipher.ENCRYPT_MODE, peerPubKey);
 // 分段加密
 for (int offset = 0; offset < plainBytes.length; offset += encryptBlock) {
 // block大小: encryptBlock 或 剩餘字節數
 int inputLen = (plainBytes.length - offset);
 if (inputLen > encryptBlock) {
 inputLen = encryptBlock;
 }
 // 得到分段加密結果
 byte[] encryptedBlock = cipher.doFinal(plainBytes, offset, inputLen);
 // 追加結果到輸出buffer中
 outbuf.write(encryptedBlock);
 } 

 // 如果是Base64編碼，則返回Base64編碼後的數組
 if (useBase64Code) {
 return Base64.encodeBase64String(outbuf.toByteArray()).getBytes(
 charset);
 } else {
 return outbuf.toByteArray(); // ciphertext
 }

}

4. 報文明文+商戶的私鑰非對稱加密得到報文數字簽名sign。

/**

* RSA簽名
* 
* @return byte[]
* @throws Exception
*/

public byte[] signRSA(byte[] plainBytes, boolean useBase64Code, String charset) throws Exception {

Signature signature = Signature.getInstance("SHA1withRSA");
 signature.initSign(localPrivKey);
 signature.update(plainBytes);
 // 如果是Base64編碼的話，需要對簽名後的數組以Base64編碼
 if (useBase64Code) {
 return Base64.encodeBase64String(signature.sign()).getBytes(charset);
 } else {
 return signature.sign();
 }

}

5. 加密後的會話密鑰key+銀行的私鑰解密得到會話密鑰明文desKey；對稱加密得到的密文message+會話密鑰明文desKey解密得到報文明文

/**

* RSA解密
*  

* @param cryptedBytes
* 待解密信息
* @return byte[]
* @throws Exception
*/

public byte[] decryptRSA(byte[] cryptedBytes, boolean useBase64Code,

String charset) throws Exception {
 String CIPHER_ALGORITHM = "RSA/ECB/PKCS1Padding"; // 加密block需要預留11字節
 byte[] data = null;
 // 如果是Base64編碼的話，則要Base64解碼
 if (useBase64Code) {
 data = Base64.decodeBase64(new String(cryptedBytes, charset));
 } else {
 data = cryptedBytes;
 }
 int KEYBIT = 2048;
 int RESERVEBYTES = 11;
 Cipher cipher = Cipher.getInstance(CIPHER_ALGORITHM);
 int decryptBlock = KEYBIT / 8; // 256 bytes
 int encryptBlock = decryptBlock - RESERVEBYTES; // 245 bytes
 // 計算分段解密的block數 (理論上應該能整除)
 int nBlock = (data.length / decryptBlock);
 // 輸出buffer, , 大小為nBlock個encryptBlock
 ByteArrayOutputStream outbuf = new ByteArrayOutputStream(nBlock * encryptBlock);
 cipher.init(Cipher.DECRYPT_MODE, localPrivKey);
 // 分段解密
 for (int offset = 0; offset < data.length; offset += decryptBlock) {
 // block大小: decryptBlock 或 剩餘字節數
 int inputLen = (data.length - offset);
 if (inputLen > decryptBlock) {
 inputLen = decryptBlock;
 }
 // 得到分段解密結果
 byte[] decryptedBlock = cipher.doFinal(data, offset, inputLen);
 // 追加結果到輸出buffer中
 outbuf.write(decryptedBlock);
 }
 outbuf.flush();
 outbuf.close();
 return outbuf.toByteArray();

}

6. 得到的明文+商戶的公鑰驗籤，得到報文是否被中途篡改過

public boolean verifyRSA(byte[] plainBytes, byte[] signBytes,

boolean useBase64Code, String charset) throws Exception {
 Signature signature = Signature.getInstance("SHA1withRSA");
 signature.initVerify(peerPubKey);
 signature.update(plainBytes);
 // 如果是Base64編碼的話，需要對驗籤的數組以Base64解碼
 if (useBase64Code) {
 return signature.verify(Base64.decodeBase64(new String(signBytes, charset)));
 } else {
 return signature.verify(signBytes);
 }

}

代碼只給出了一部分重要的加解密，加驗籤邏輯。還有一些邏輯都貼出來有點亂，就放在倉庫裡了，具體用法查看README即可，[更詳細的參考放在demo裡](https://gitee.com/metabolism/decry_eencrypt_mock)

### 思考：為什麼RSA公鑰加密的值一定只有私鑰才能解開，不能暴力破解？？

其實RSA的原理很簡單，運用了數學的一個難題：兩個大的質數相乘，難以在短時間內將其因式分解。原理很簡單，但實際上操作真的很難。

##### 時間複雜度--O

我們都知道計算機的計算速度非常快，計算幾十位數的加減法都是秒出。 


然而，雖然計算機很快，但再快也是有上限的。

比如我電腦的CPU主頻是2.30GHz，也就是說我的電腦每秒可以進行2300000000次最基本的運行。

![](https://image-static.segmentfault.com/121/362/1213624279-5dd4d4d083d21_articlex)

計算機的計算能力有限，就算是超級計算機“天河二號”，每秒也只能算3.39億億(這裡多了個億 ，給大佬跪了orz)次。

對應的，我們有一個參數來衡量一個程序的耗時，叫做時間複雜度：

| 多項式量級 | 不嚴格的通俗例子(輸入規模![[公式]](https://www.zhihu.com/equation?tex=n%3D10%5E9)) |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| 常量階 ![O(1)](https://math.jianshu.com/math?formula=O(1)) | 只用1次運算,普通電腦 ![[公式]](https://www.zhihu.com/equation?tex=10%5E%7B-9%7D) 秒就能算完。 |
| 對數階 ![O(\\log{n})](https://math.jianshu.com/math?formula=O(%5Clog%7Bn%7D)) | 大約會用30次計算，普通電腦 ![[公式]](https://www.zhihu.com/equation?tex=10%5E%7B-8%7D) 秒算完 |
| 線性階 ![O(n)](https://math.jianshu.com/math?formula=O(n)) | ![[公式]](https://www.zhihu.com/equation?tex=10%5E9) 次計算，普通電腦需要一秒左右 |
| 線性對數階 ![O(n log n)](https://math.jianshu.com/math?formula=O(n%20log%20n)) | |
| 平方階 ![O(n^{2})](https://math.jianshu.com/math?formula=O(n%5E%7B2%7D)),立方階 ![O(n^{3})](https://math.jianshu.com/math?formula=O(n%5E%7B3%7D)) | 大約是 ![[公式]](https://www.zhihu.com/equation?tex=10%5E%7B18%7D) 次計算，普通電腦大概要30年。 |

| 非多項式量級 | 不嚴格的通俗例子(輸入規模![[公式]](https://www.zhihu.com/equation?tex=n%3D10%5E9)) |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| 指數階 ![2^{n}](https://math.jianshu.com/math?formula=2%5E%7Bn%7D) | 大約2^1000000000次計算，心態崩了 |
| 階乘階 n！ | 人類所有電腦加在一起，等太陽炸了都算不完 | 


算法複雜度有各種各樣的，有 ![[公式]](https://www.zhihu.com/equation?tex=O%281%29) ， ![[公式]](https://www.zhihu.com/equation?tex=O%28logn%29), ![[公式]](https://www.zhihu.com/equation?tex=O%28n%29), ![[公式]](https://www.zhihu.com/equation?tex=O%28n%5E2%29), ![[公式]](https://www.zhihu.com/equation?tex=O%282%5En%29)……上述幾個複雜度的算法一個比一個慢。通俗的講，大O後面括號裡面**函數的增長速度越快，算法越耗時**。

總的來說，RSA之所以理論上非常安全，是因為破解RSA所要付出地計算成本遠遠高於使用RSA進行加密的計算成本。

* 使用RSA的私鑰進行解密，耗用的時間複雜度是**多項式級**。

* 不使用RSA私鑰，暴力破解，需要分解質因數，他的時間複雜度是**非多項式級**的**指數級**。

* 也就是有私鑰解密只要一秒，暴力破解出結果時，人類可能已經毀滅了(不嚴格)。

##### RSA生成公私鑰數學計算流程：

1. 商戶隨機生成了一些非常非常大的整數，並用Miller-Rabin算法檢測它們是不是質數，直到找到兩個大質數——![[公式]](https://www.zhihu.com/equation?tex=p_1) 和 ![[公式]](https://www.zhihu.com/equation?tex=p_2) 。（隨機數生成：多項式時間；Miller-Rabin: 多項式時間）

2. 商戶計算兩個質數的乘積 ![[公式]](https://www.zhihu.com/equation?tex=n%3Dp_1p_2) （乘法: 多項式時間）

3. 商戶計算 φ(n) = (p1 - 1)(p2 - 1) （乘法: 多項式時間），這一步難以被破解，因為n太大了，分解質因數需要指數級時間複雜度。人類毀滅前是根據n推算出φ(n)可能性極小。 


* **歐拉函數：φ(n)表示：小於n的正整數中與n互質的數的數目。**（互質表示公因數為1）

 比如想要知道φ(10)的話，我們就可以看[1, 10)中和10互質的整數，也就是1、3、7、9這四個數。（2、4、6、8和10有公因數2，而5和10有公因數10）。所以φ(10)=4。

 比如想要知道φ(21)的話，我們就可以看[1, 21)中和21互質的整數，也就是1、2、4、5、8、10、11、13、16、17、19、20這12個數。（3、6、9、12、15、18和21有公因數3，而7、14和21有公因數7）。所以φ(21)=12。

4. 商戶構造了一個比1大、比φ(n)小、不等於 ![[公式]](https://www.zhihu.com/equation?tex=p_1) 或 ![[公式]](https://www.zhihu.com/equation?tex=p_2) 的整數e。（隨機數：多項式時間）

5. 商戶求出了e對於φ(n)的乘法逆元d，也就是說**ed ≡ 1（mod φ(n)）**，也就是說ed=kφ(n)+1 (擴展歐幾里得，多項式時間)

6. **請注意！現在神奇的事情發生了！對於一個與n互質的數a：**

因為 ![[公式]](https://www.zhihu.com/equation?tex=a%5E%7B%CF%86%28n%29%7D%E2%89%A11+) (mod n)

所以 ![[公式]](https://www.zhihu.com/equation?tex=a%5E%7Bk%CF%86%28n%29%7D%E2%89%A11) (mod n)

所以 ![[公式]](https://www.zhihu.com/equation?tex=a%5E%7Bk%CF%86%28n%29%2B1%7D%E2%89%A1a) (mod n)

所以 ![[公式]](https://www.zhihu.com/equation?tex=a%5E%7Bed%7D%E2%89%A1a) (mod n)

所以，若 ![[公式]](https://www.zhihu.com/equation?tex=c%5Cequiv+a%5Ee) (mod n), 則![[公式]](https://www.zhihu.com/equation?tex=c%5Ed%5Cequiv+a%5E%7Bed%7D+%5Cequiv+a)（mod n）
 

**到這裡，兩把鑰匙構造完成！ㄟ(≧◇≦)ㄏ**

**公鑰：（n, e）**

**密鑰：（n, d）**

##### RSA公私鑰加密解密

商戶想要生成一對公私鑰的時候：

* 首先隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。
* 根據歐拉函數，求得r = (p-1)(q-1)
* 選擇一個小於 r 的整數 e，求得 e 關於模 r 的模反元素，命名為d。（模反元素存在，當且僅當e與r互質）
* 將 p 和 q 的記錄銷燬。
* (N,e)是公鑰，(N,d)是私鑰。商戶將她的公鑰(N,e)傳給銀行，而將自己的私鑰(N,d)藏起來。

商戶進行加密的時候：

* 假設商戶想給銀行送一個消息m，他知道銀行的公鑰，換句話說是銀行公鑰的N和e。他使用起先與銀行約好的格式將m轉換為一個小於N的整數n，比如他可以將每一個字轉換為這個字的Unicode碼，然後將這些數字連在一起組成一個數字。假如他的信息非常長的話，他可以將這個信息分為幾段，然後將每一段轉換為n。用下面這個公式他可以將n加密為c： 


 ​ ne ≡ c (mod N)
 計算c並不複雜。商戶算出c後就可以將它傳遞給銀行，也就是密文啦。

銀行想要解密的時候：

* 銀行得到商戶的密文消息c(商戶使用銀行公鑰加密後的密文)後就可以利用他的私鑰d來解碼。他可以用以下這個公式來將c轉換為n：
 cd ≡ n (mod N)
 得到n後，他可以將原來的信息m重新復原。

### 其他的概念

##### 素數

素數又稱質數，指在一個大於1的自然數中，除了1和此整數自身外，不能被其他自然數整除的數

##### 互質數

互質，又稱互素。若N個整數的最大公因子是1，則稱這N個整數互質。

##### 指數運算

指數運算又稱乘方計算，計算結果稱為冪。nm指將n自乘m次。把nm看作乘方的結果，叫做”n的m次冪”或”n的m次方”。其中，n稱為“底數”，m稱為“指數”。
 

##### 模運算

模運算即求餘運算。

##### 同餘

當兩個整數除以同一個正整數，若得相同餘數，則二整數同餘。

##### 會話密鑰

前提：對稱加密速度要比非對稱加密快速。會話密鑰是一個隨機生成的對稱式加密密鑰，舉個例子：A和B交互，A隨機挑了一個字符串，用B的公鑰加密發給了B，告訴B這個隨機字符串就是他們之間用來交流的密鑰了，之後A和B的報文就可以不用公私鑰非對稱加密，直接用這個密鑰對稱加密即可。對稱式加密算法有很多：AES/DES等。SSH通信的數據就是用AES之類的對稱式加密算法加密的。(在SSH協商密鑰的過程中，還會使用專門的**密鑰協商算法（Key Exchange Algorithm）**，確保竊聽者無法偷聽到密鑰的內容)

##### 中間人攻擊

即當商戶發送公鑰給銀行的時候，黑客截取了商戶的公鑰，同時把自己公鑰發給銀行，這樣一直在與銀行通信的並不是商戶。

##### CA認證中心

專門提供網絡身份認證服務的機構或團體 


### 總結

數學的魅力在於將這個世界變得井井有條，試想當計算機的運行速度越來越快，RSA會被破解嗎？不見得，1999年N(兩個大質數的乘積)位數是512，後面發展成了位數是1024和2048位，計算機速度變快之後，每臺電腦能處理的位數也會越來越大，我相信我們會見到更長位數的N，十萬，甚至百萬....

浩瀚世界，自己真渺小

閱讀更多 sandag 的文章

關鍵字: 信息安全 加密 黑客