密碼學公鑰如何用符號表示

① 公鑰演算法原理

這是一種不對稱加密演算法。公鑰演算法包括快速公鑰演算法與傳統公鑰演算法。快速公鑰演算法與傳統公鑰演算法相比具有更廣泛地應用前景,對快速公鑰系統的研究是當前公鑰系統研究的一個熱點。

定義
不對稱加密演算法使用兩把完全不同但又是完全匹配的一對鑰匙—公鑰和私鑰。在使用不對稱加密演算法加密文件時，只有使用匹配的一對公鑰和私鑰，才能完成對明文的加密和解密過程。加密明文時採用公鑰加密，解密密文時使用私鑰才能完成，而且發信方（加密者）知道收信方的公鑰，只有收信方（解密者）才是唯一知道自己私鑰的人。不對稱加密演算法的基本原理是，如果發信方想發送只有收信方才能解讀的加密信息，發信者使用收信者的公鑰加密信件，收信者使用自己的私鑰鑰解密信件。顯然，採用不對稱加密演算法，收發信雙方在通信之前，收信方必須將自己早已隨機生成的公鑰送給發信方，而自己保留私鑰。由於不對稱演算法擁有兩個密鑰，因而特別適用於分布式系統中的數據加密。廣泛應用的不對稱加密演算法有RSA演算法和美國國家標准局提出的DSA。以不對稱加密演算法為基礎的加密技術應用非常廣泛。

工作原理
1976 年，Whitfield Diffe 和 Martin Hellman 創建了公鑰加密。公鑰加密是重大的創新，因為它從根本上改變了加密和解密的過程。

Diffe 和 Hellman 提議使用兩個密鑰，而不是使用一個共享的密鑰。一個密鑰（稱為「私鑰」）是保密的。它只能由一方保存，而不能各方共享。第二個密鑰（稱為「公鑰」）不是保密的，可以廣泛共享。這兩個密鑰（稱為「密鑰對」）在加密和解密操作中配合使用。密鑰對具有特殊的互補關系，從而使每個密鑰都只能與密鑰對中的另一個密鑰配合使用。這一關系將密鑰對中的密鑰彼此唯一地聯系在一起：公鑰與其對應的私鑰組成一對，並且與其他任何密鑰都不關聯。

由於公鑰和私鑰的演算法之間存在特殊的數學關系，從而使得這種配對成為可能。密鑰對在數學上彼此相關，例如，配合使用密鑰對可以實現兩次使用對稱密鑰的效果。密鑰必須配合使用：不能使用每個單獨的密鑰來撤消它自己的操作。這意味著每個單獨密鑰的操作都是單向操作：不能使用一個密鑰來撤消它的操作。此外，設計兩個密鑰使用的演算法時，特意設計無法使用一個密鑰確定密鑰對中的另一個密鑰。因此，不能根據公鑰確定出私鑰。但是，使得密鑰對成為可能的數學原理也使得密鑰對具有對稱密鑰所不具有的一個缺點。這就是，所使用的演算法必須足夠強大，才能使人們無法通過強行嘗試，使用已知的公鑰來解密通過它加密的信息。公鑰利用數學復雜性以及它的單向特性來彌補它是眾所周知的這樣一個事實，以防止人們成功地破解使用它編碼的信息。

如果將此概念應用於前面的示例，則發件人將使用公鑰將純文本加密成密碼。然後，收件人將使用私鑰將密碼重新解密成純文本。

由於密鑰對中的私鑰和公鑰之間所存在的特殊關系，因此一個人可以在與許多人交往時使用相同的密鑰對，而不必與每個人分別使用不同的密鑰。只要私鑰是保密的，就可以隨意分發公鑰，並讓人們放心地使用它。使許多人使用同一個密鑰對代表著密碼學上的一個重大突破，因為它顯著降低了密鑰管理的需求，大大提高了密碼學的可用性。用戶可以與任意數目的人員共享一個密鑰對，而不必為每個人單獨設立一個密鑰。

公鑰加密是郵件安全中的一個基本要素。如果沒有公鑰加密，那麼是否存在實用的郵件安全解決方案是值得懷疑的，因為在公鑰加密出現之前，密鑰管理是一件很麻煩的事情。在了解了公鑰加密的基本概念之後，接下來便是了解如何藉助這些概念來實現郵件安全性。

② 公鑰密碼→RSA詳解

在對稱密碼中，由於加密和解密的密鑰是相同的，因此必須向接收者配送密鑰。用於解密的密鑰必須被配送給接收者，這一問題稱為 密鑰配送問題 ，如果使用公鑰密碼，則無需向接收者配送用於解密的密鑰，這樣就解決了密鑰配送問題。可以說公鑰密碼是密碼學歷史上最偉大的發明。

解決密鑰配送問題的方法

在人數很多的情況下，通信所需要的密鑰數量會增大，例如：1000名員工中每一個人都可以和另外999個進行通信，則每個人需要999個通信密鑰，整個密鑰數量：
1000 x 999 ÷ 2 = 499500
很不現實，因此此方法有一定的局限性

在Diffic-Hellman密鑰交換中，進行加密通信的雙方需要交換一些信息，而這些信息即便被竊聽者竊聽到也沒有問題（後續文章會進行詳解）。

在對稱密碼中，加密密鑰和解密密鑰是相同的，但公鑰密碼中，加密密鑰和解密密鑰卻是不同的。只要擁有加密密鑰，任何人都可以加密，但沒有解密密鑰是無法解密的。

公鑰密碼中，密鑰分為加密密鑰（公鑰）和解密密鑰（私鑰）兩種。

公鑰和私鑰是一一對應的，一對公鑰和私鑰統稱為密鑰對，由公鑰進行加密的密文，必須使用與該公鑰配對的私鑰才能夠解密。密鑰對中的兩個密鑰之間具有非常密切的關系——數學上的關系——因此公鑰和私鑰是不能分別單獨生成的。

發送者：Alice      接收者：Bob      竊聽者：Eve
通信過程是由接收者Bob來啟動的

公鑰密碼解決了密鑰配送的問題，但依然面臨著下面的問題

RSA是目前使用最廣泛的公鑰密碼演算法，名字是由它的三位開發者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母組成的（Rivest-Shamir-Adleman）。RSA可以被使用公鑰密碼和數字簽名（此文只針對公鑰密碼進行探討，數字簽名後續文章敬請期待）1983年在美國取得了專利，但現在該專利已經過期。

在RSA中，明文、密鑰和密文都是數字，RSA加密過程可以用下列公式來表達

密文 = 明文 ^E mod N

簡單的來說，RSA的密文是對代表明文的數字的 E 次方求mod N 的結果，換句話說：將明文和自己做 E 次乘法，然後將結果除以 N 求余數，這個余數就是密文。

RSA解密過程可以用下列公式來表達

明文 = 密文 ^D mod N
對表示密文的數字的 D 次方求mod N 就可以得到明文，換句話說：將密文和自己做 D 次乘法，在對其結果除以 N 求余數，就可以得到明文
此時使用的數字 N 和加密時使用的數字 N 是相同的，數 D 和數 N 組合起來就是RSA的解密密鑰，因此 D 和 N 的組合就是私鑰 。只要知道 D 和 N 兩個數的人才能夠完成解密的運算

根據加密和解密的公式可以看出，需要用到三個數—— E 、 D 和 N 求這三個數就是 生成密鑰對 ，RSA密鑰對的生成步驟如下：

准備兩個很大的質數 p 和 q ，將這兩個數相乘，結果就是 N
N = p x q

L 是 p-1 和 q-1 的最小公倍數，如果用lcm( X , Y )來表示 「 X 和 Y 的最小公倍數」 則L可以寫成下列形式
L = lcm ( p - 1， q - 1)

E 是一個比1大、比 L 小的數。 E 和 L 的最大公約數必須為1，如果用gcd( X , Y )來表示 X 和 Y 的最大公約數，則 E 和 L 之間存在下列關系：
1 < E < L
gcd( E , L ) = 1 （是為了保證一定存在解密時需要使用的數 D ）

1 < D < L
E x D mod L = 1

p = 17
q = 19
N = p x q = 17 x 19 = 323

L = lcm ( p - 1， q - 1) = lcm (16,18) = 144

gcd( E , L ) = 1
滿足條件的 E 有很多：5，7，11，13，17，19，23，25，29，31...
這里選擇5來作為 E ,到這里我們已經知道 E = 5    N = 323 這就是公鑰

E x D mod L = 1
D = 29 可以滿足上面的條件，因此：
公鑰： E = 5     N = 323
私鑰： D = 29    N = 323

要加密的明文必須是小於 N 的數，這是因為在加密運算中需要求 mod N 假設加密的明文是123
明文 ^E mod N = 123 ⁵ mod 323 = 225（密文）

對密文225進行解密
密文 ^D mod N = 225 ²⁹ mod 323 = 225 ¹⁰ x 225 ¹⁰ x 225 ⁹ mod 323 = (225 ¹⁰ mod 323) x (225 ¹⁰ mod 323) x (225 ⁹ mod 323) = 16 x 16 x 191 mod 323 = 48896 mod 323 = 123（明文）

如果沒有mod N 的話，即：

明文 = 密文 ^D mod N

通過密文求明文的難度不大，因為這可以看作是一個求對數的問題。
但是，加上mod N 之後，求明文就變成了求離散對數的問題，這是非常困難的，因為人類還沒有發現求離散對數的高效演算法。

只要知道 D ，就能夠對密文進行解密，逐一嘗試 D 來暴力破譯RSA，暴力破解的難度會隨著D的長度增加而加大，當 D 足夠長時，就不能再現實的時間內通過暴力破解找出數 D

目前，RSA中所使用的 p 和 q 的長度都是1024比特以上， N 的長度為2048比特以上，由於 E 和 D 的長度可以和N差不多，因此要找出 D ，就需要進行2048比特以上的暴力破解。這樣的長度下暴力破解找出 D 是極其困難的

E x D mod L = 1           L = lcm ( p - 1， q - 1)
由 E 計算 D 需要使用 p 和 q ，但是密碼破譯者並不知道 p 和 q

對於RSA來說，有一點非常重要，那就是 質數 p 和 q 不能被密碼破譯這知道 。把 p 和 q 交給密碼破譯者與把私鑰交給密碼破譯者是等價的。

p 和 q 不能被密碼破譯者知道，但是 N = p x q 而且 N 是公開的， p 和 q 都是質數，因此由 N 求 p 和 q 只能通過 將 N 進行質因數分解 ，所以說：
一旦發現了對大整數進行質因數分解的高效演算法，RSA就能夠被破譯

這種方法雖然不能破譯RSA，但卻是一種針對機密性的有效攻擊。

所謂中間人攻擊，就是主動攻擊者Mallory混入發送者和接收者的中間，對發送者偽裝成接收者，對接收者偽裝成發送者的攻擊，在這里，Mallory就是「中間人」

這種攻擊不僅針對RSA，而是可以針對任何公鑰密碼。在這個過程中，公鑰密碼並沒有被破譯，所有的密碼演算法也都正常工作並確保了機密性。然而，所謂的機密性並非在Alice和Bob之間，而是在Alice和Mallory之間，以及Mallory和Bob之間成立的。 僅靠公鑰密碼本身，是無法防禦中間人攻擊的。

要防禦中間人攻擊，還需要一種手段來確認所收到的公鑰是否真的屬於Bob，這種手段稱為認證。在這種情況下，我們可以使用公鑰的 證書 (後面會陸續更新文章來進行探討)

網路上很多伺服器在收到格式不正確的數據時都會向通信對象返回錯誤消息，並提示「這里的數據有問題」，然而，這種看似很貼心的設計卻會讓攻擊者有機可乘。 攻擊者可以向伺服器反復發送自己生成的偽造密文，然後分析返回的錯誤消息和響應時間獲得一些關於密鑰和明文的信息。

為了抵禦這種攻擊，可以對密文進行「認證」，RSA-OAEP(最優非對稱加密填充)正是基於這種思路設計的一種RSA改良演算法。

RSA-OAEP在加密時會在明文前面填充一些認證信息，包括明文的散列值以及一定數量的0，然後用RSA進行加密，在解密的過程中，如果解密後的數據的開頭沒有找到正確的認證信息，則可以判定有問題，並返回固定的錯誤消息（重點是，不能將具體的錯誤內容告知開發者）
RSA-OAEP在實際應用中，還會通過隨機數使得每次生成的密文呈現不同的排列方式，從而進一步提高安全性。

隨著計算機技術的進步等，以前被認為是安全的密碼會被破譯，這一現象稱為 密碼劣化 ，針對這一點：

③ 1.密碼學之RSA

計算56的歐拉函數

 φ(56) =  φ(8)*  φ(7) = 4 * 6 = 24

一、當n是質數的時候，φ(n)=n-1。

二、如果n可以分解成兩個互質磨仿的整數之積，如n=A*B則：

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

根據以上兩點得到：

如果N是兩個質數P1 和 P2的乘積則

φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)

如果兩個正整數m和n互質，那麼m的φ(n)次方減去1，可以被n整除。

 歐拉定理的特殊情況：如果兩個正整數m和n互質，而且n為質數！那麼φ(n)結果就是n-1。

公式轉換

3 φ(5) mod 5  --->  3 **4 mod 5 = 81 mod 5 = 1

3 φ(5) mod 5  --->  3 **(4 * 2) mod 5 = 6561 mod 5 = 1

3 φ(5) mod 5  --->  3 **(4  + 1) mod 5 = 243 mod 5 = 3

如果兩個正整數e和x互質，那麼一定可以找到整首卜數d，使得 ed-1

被x整除。  那麼d就是e對於x的「模反元素」

e = 3 , x = 5

e*d mod x  = 1  -->  3*d mod 5 = 1 , d 可以為 2、7 ， 2、7 就是3相對於5的模反元素

e*d = k *x + 1   --> 瞎芹纖 3*7 = k*5 + 1, k 可以為 4

m = 4, n = 15 , φ(n) = φ(3) * φ(5) = 8,  e = 3,  d 可以為 11 、19 （d 是求出來的， e*d mod φ(n) = 1 --> 3*d mod 8 = 1 ,  --->  3*d - 1 = 8*k ---> d = 3, 11, 19）  e和φ(n)互質

4**33 mod 15 = 4   ,   5**33 mod 15 = 5  ,   6**33 mod 15 = 6

結論 m<n 都滿足條件 ， m **(e*d) mod n = m

3 ** 15 mod 17 = 6   ,  6 **13 mod 17  = 10  ----> (3 ** 15) ** 13 mod 17 = 10

3 ** 13 mod 17 = 12  ,  12 **15 mod 17  = 10  ----> (3 ** 13) ** 15 mod 17 = 10

所以 ：  (3 ** 15)** 13 mod 17 = (3 ** 13) ** 15 mod 17  --->

m **e mod n = c ,  c ** d mod n = m **(e *d) mod n，  m ** (e *d) mod n = m  ( d和φ(n)的模反元素 )

m **e mod n = c 加密

c **d mod n = m 解密

m = 3 , n = 15, φ(n) = 8, e = 3 (與φ(n) 互質)，d = 11、19

3 ** 3 mod 15 = 12  , 12 ** 11 mod 15 = 3

12 * 3 mod 15 = 3 ,  3 ** 11 mod 15 = 12

m 小於 n, d 是 e 相對於φ(n)的模反元素

公鑰： n 和 e

私鑰： n 和 d

明文:   m

密文:   c

n 長度 1024 以上，所以 n 是由 p1 和 p2 兩個質數相乘得到的，為了好算。

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

除了公鑰用到了n和e 其餘的4個數字是不公開的。

目前破解RSA得到d的方式如下：

1、要想求出私鑰d  。由於e*d = φ(n)*k + 1。要知道e和φ(n);

2、e是知道的，但是要得到 φ(n)，必須知道p1 和 p2。

3、由於 n=p1*p2。只有將n因數分解才能算出。

1. 相對來說比較安全（非對稱加密的，私鑰不用傳遞）

2. 效率不高

3. 加密數據小

由於Mac系統內置OpenSSL(開源加密庫),所以我們可以直接在終端上使用命令來玩RSA.

OpenSSL中RSA演算法常用指令主要有三個：

$ openssl genrsa -out private.pem 1024

$ cat private.pem  （查看顯示出來的是 base64的編碼）

$ openssl rsa -in private.pem -pubout -out public.pem

$ openssl rsa -in private.pem -text -out private.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   解密

$ openssl req -new -key private.pem -out rsacert.csr   生成csr文件

$ openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt   簽名

$ openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt 生成p12

  base64 可以將任意的二進制數據進行編碼。 編碼成為65個字元組成的文本文件。

  0~9a ~ z， A ~ Z + / =

 $base64 源文件 -o 目標文件    編碼

 $base64 源文件 -o 目標文件 -D 解碼

  101001 010101 010100 010101

  A 位元組  =  =

  010000 010000 000000 000000  (將二進制數據以每6個二進制為一組進行編碼， 6位正好是64個二進制)

例如 ： A 的ASCII 碼為65， 佔1個位元組，8個二進制位 01000001 ，---> 010000 010000 000000 000000 （補兩組0是為了位元組對齊）

$ openssl x509 -outform der -in rsacert.crt -out rsacert.der  （在ios中不能直接使用，需將crt 文件生成一個der文件）

將der 和 p12文件拖入項目中，導入 RSACryptor

- (void)viewDidLoad {

    [super viewDidLoad];

    //1.載入公鑰

    [[RSACryptor sharedRSACryptor] loadPublicKey: [[NSBundle mainBundle] pathForResource:@"rsacert.der" ofType:nil]];

    //2.載入私鑰

    [[RSACryptor sharedRSACryptor] loadPrivateKey:[[NSBundle mainBundle] pathForResource:@"p.p12" ofType:nil] password:@"123456"];

}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent*)event{

    //1.加密

    NSData * result = [[RSACryptor sharedRSACryptor] encryptData:[@"hello" dataUsingEncoding:NSUTF8StringEncoding]];

    NSLog(@"加密的結果是:%@",[result :0]);

    //2.解密

    NSData * jiemi = [[RSACryptor sharedRSACryptor] decryptData:result];

    NSLog(@"解密的結果：%@",[[NSString alloc] initWithData:jiemi encoding:NSUTF8StringEncoding]);

}

// 填充模式  kSecPaddingNone 每次解密結果是固定的

// kSecPaddingPKCS1 是隨機變化的。

#define kTypeOfWrapPadding        kSecPaddingNone