iOS 密碼學(RSA)，粗略介紹。 　　

導引

我將從以下四點來講述密碼學相關內容：

1. 什麼是密碼學
2. RSA數學原理
3. RSA終端命令
4. 總結

什麼是密碼學

密碼學的歷史大致可以追溯到兩千年前，相傳古羅馬名將凱撒大帝為了防止敵方截獲情報，用密碼傳送情報。凱撒的做法很簡單，就是對二十幾個羅馬字母建立一張對應表。這樣，如果不知道密碼本，即使截獲一段信息也看不懂。

從凱撒大帝時代到上世紀70年代這段很長的時間裡，密碼學的發展非常的緩慢，因為設計者基本上靠經驗。沒有運用數學原理。
在1976年以前，所有的加密方法都是同一種模式：加密、解密使用同一種算法。在交互數據的時候，彼此通信的雙方就必須將規則告訴對方，否則沒法解密。那麼加密和解密的規則（簡稱密鑰），它保護就顯得尤其重要。傳遞密鑰就成為了最大的隱患。這種加密方式被成為對稱密鑰演算法（英語：Symmetric-key algorithm）。

1976年，兩位美國計算機學家 迪菲（W.Diffie）、赫爾曼（ M.Hellman ） 提出了一種嶄新構思，可以在不直接傳遞密鑰的情況下，完成密鑰交換。這被稱為”迪菲赫爾曼密鑰交換”算法。開創了密碼學研究的新方向。

1977年三位麻省理工學院的數學家羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起設計了一種算法，可以實現非對稱加密。這個算法用他們三個人的名字命名，叫做RSA算法。
也就是說「迪菲-赫爾曼密鑰交換(英語：Diffie–Hellman key exchange，縮寫為D-H)」在密碼學歷史的車輪中成為了一個轉折點。

RSA數學原理

我們先把所有需要用到的公式定理列出來：

1. 取模運算
2. 歐拉函數φ
3. 歐拉定理，費馬小定理
4. 模反元素
5. 迪菲赫爾曼密鑰交換

1. 取模運算

取模運算（“Modulo Operation”）和取餘運算（“Complementation ”）兩個概念有重疊的部分但又不完全一致。主要的區別在於對負整數進行除法運算時操作不同。

在這列出各種負數情況的例子供大家理解：

7 mod 4 = 3（商 = 1 或 2，1<2，取商=1）

-7 mod 4 = 1（商 = -1 或 -2，-2<-1，取商=-2）

7 mod -4 = -1（商 = -1或-2，-2<-1，取商=-2）

-7 mod -4 = -3（商 = 1或2，1<2，取商=1）

函數值符號規律(餘數的符號) mod(負,正)=正 mod(正,負)=負

結論：兩個整數求餘時，其值的符號為除數的符號。

2. 歐拉函數φ

可以簡單理解為：

如果n可以分解為兩個互質(不一定是兩個質數)的數之積A和B，那麼：

φ(n) = φ(A) * φ(B)

如果 A和B 又同時為質數，那麼：

φ(n) = (A-1) * (B-1)

3. 歐拉定理，費馬小定理

首先這裡說一下，定制之所以是定理是被人證明過的，如何證明的不管，當然你也可以增加去證明下，反正我不管（……&%￥%……&%&……&% ），哈哈

如果m、n為正整數，且m、n互質，那麼：


如果n為質數，那麼：


公式轉換：


4. 模反元素

如果兩個正整數e和x互質，那麼一定可以找到整數d，使得 e*d-1 被x整除。那麼d就是e對於x的”模反元素”。


5. 迪菲赫爾曼密鑰交換

如上圖：

客戶端持有一個隨機數13 ，服務端持有隨機數15，再選一對特殊的數，3是17的原根。
兩端交換的都是密文，就算中間被劫持，也不知道最後需要的傳輸的內容是10

那麼這個10就是最後真正的密鑰。

證明過程：

==>		3^(13 * 15) mod 17 = 3^(13 * 15) mod 17 
根據模冪運算 ((m^e mod n)^d) mod n = m^(e*d) mod n
==>		(3^13 mod 17)^13 mod 17 = (3^15 mod 17)^15 mod 17
由於	3^13 mod 17 = 12
		3^15 mod 17 = 6
==>		6^13 mod 17 =  12^15 mod 17 = 10

設

m=3, e=13, d=15, n=17, C=12

那麼

m^e mod n = c
c^d mod n = (m^e mod n)^d mod n = m^(e*d) mod n

又由於上面模反元素，最後得出

m^(e*d) mod n = m

所以得出最終結論：

m^e mod n = c
c^d  mod n = m

這個公式也就是我們最後的RSA加密公式！ ！ ！

其中：

公鑰： n和e
私鑰： n和d
明文: m
密文: c
d是e對於φ(n)的"模反元素"。

>補充： >1. n會非常大，長度一般為1024個二進制位。
>（目前人類已經分解的最大整數，232個十進制位，768個二進制位）
>2. 由於需要求出φ(n)，所以根據歐函數特點，最簡單的方式n 由兩個質數相乘得到: 質數：p1、p2
Φ(n) = (p1 -1) * (p2 - 1)
>3. 最終由φ(n)得到e 和 d 。
總共生成6個數字：p1、p2、n、φ(n)、e、d

關於RSA的安全：
除了公鑰用到了n和e 其餘的4個數字是不公開的。
目前破解RSA得到d的方式如下：

1. 要想求出私鑰 d 。由於ed = φ(n)k + 1。要知道e和φ(n);
   
2. e是知道的，但是要得到 φ(n)，必須知道p1 和 p2。
   
3. 由於 n=p1*p2。只有將n因數分解才能算出。
   
   
   

RSA終端命令

由於Mac系統內的 OpenSSL(開源加密庫)，所以我們可以直接在iTerm上使用命令來玩RSA. OpenSSL中RSA算法常用指令主要有三個：

命令	說明
genrsa	生成並且輸出一串RSA私鑰
rsautl	使用RSA密鑰進行加密、解密、簽名和驗證等運算
rsa	處理RSA密鑰的格式轉換等問題

1. 生成RSA私鑰，密鑰長度為1024bit

// 生成RSA私鑰，密鑰長度為1024bit
openssl genrsa -out private.pem 1024

➜  Downloads openssl genrsa -out private.pem 1024
Generating RSA private key, 1024 bit long modulus
........+++++
................................+++++
e is 65537 (0x10001)

2. 從私鑰中提取公鑰

// 從私鑰中提取公鑰
openssl rsa -in private.pem -pubout -out public.pem

➜  Downloads openssl rsa -in private.pem -pubout -out public.pem
writing RSA key

3. 將私鑰轉換成為明文

// 將私鑰轉換成為明文
openssl rsa -in private.pem -text -out private.txt cat private.txt

➜  Downloads openssl rsa -in private.pem -text -out private.txt
cat private.txt
writing RSA key
Private-Key: (1024 bit)
modulus:
    00:c6:46:ac:0e:4f:3b:01:2f:15:f3:94:23:50:32:

4. 通過公鑰加密數據，私鑰解密數據

// 新建一個文件，在文件中隨意輸入內容，比如輸入字符串”Hello“
vim message.txt
// 查看文件
cat message.txt
// 通過公鑰進行加密
openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
// 通過私鑰進行解密
openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
// 查看加密後的文件
cat enc.txt
// 查看解密後的文件
cat dec.txt

5. 通過私鑰加密數據，公鑰解密數據

// 私鑰加密
openssl rsautl -sign -in message.txt -inkey private.pem -out enc_2.txt
// 公鑰加密
openssl rsautl -verify -in enc_2.txt -inkey public.pem -pubin -out dec_2.txt

## 總結

1. 由於RSA加密解密用的不是一套數據，所以其保證了安全性。
2. 由於私鑰過大，所以效率較低
3. 如果有一天量子計算機被普及(計算速度極快)，那麼1024位已經不足以讓RSA安全。
   
   
   

---