RSA的起源

• 1976年以前所有的加密方法都是同一種模式：加解密雙方使用同一種規(guī)則(簡(jiǎn)稱(chēng)“密鑰”)。這種加密方式被稱(chēng)為對(duì)稱(chēng)加密算法。
• 1976年，兩位美國(guó)計(jì)算機(jī)學(xué)家迪菲(W.Diffie)、赫爾曼(M.Hellman)提出了一種嶄新構(gòu)思，加密和解密使用不同的規(guī)則，但只要兩種規(guī)則(密鑰)之間存在某種對(duì)應(yīng)關(guān)系即可實(shí)現(xiàn)在不直接傳遞密鑰的情況下完成解密。這被稱(chēng)為Diffie-Hellman密鑰交換算法。
• 1977年三位麻省理工學(xué)院的數(shù)學(xué)家羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起設(shè)計(jì)了一種算法，可以實(shí)現(xiàn)非對(duì)稱(chēng)加密。
  image
  
  這個(gè)算法用他們?nèi)齻€(gè)人的名字命名，叫做RSA算法。其加密方式比較特殊，需要兩個(gè)密鑰：公開(kāi)密鑰簡(jiǎn)稱(chēng)公鑰(publickey)和私有密鑰簡(jiǎn)稱(chēng)私鑰(privatekey)。公鑰加密，私鑰解密；私鑰加密，公鑰解密。

RSA算法原理 -- 摘抄自網(wǎng)站

• 互質(zhì)關(guān)系：如果兩個(gè)正整數(shù)，除了1以外，沒(méi)有其他公因子，我們就稱(chēng)這兩個(gè)數(shù)是互質(zhì)關(guān)系。關(guān)于互質(zhì)關(guān)系有幾個(gè)結(jié)論：

    1.任意兩個(gè)質(zhì)數(shù)構(gòu)成互質(zhì)關(guān)系
    2.一個(gè)數(shù)是質(zhì)數(shù)，另一個(gè)數(shù)只要不是前者的倍數(shù)，兩者互質(zhì)
    3.若較大的數(shù)為質(zhì)數(shù)，則兩者互質(zhì)
    4.任意自然數(shù)與1都互質(zhì)
    5.若p大于1，則p與p-1構(gòu)成互質(zhì)
    6.若p為大于1的奇數(shù)，則p與p-2互質(zhì)

• 歐拉函數(shù)：φ(n)表示在小于等于n的正整數(shù)之中有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系(除了1以外沒(méi)有其他公因數(shù))。

    1.如果n=1，則φ(1)=1。因?yàn)?與任何數(shù)都構(gòu)成互質(zhì)關(guān)系。
    2.如果n是質(zhì)數(shù)，則φ(n)=n-1。因?yàn)橘|(zhì)數(shù)與小于它的每一個(gè)數(shù)都構(gòu)成互質(zhì)關(guān)系。
    3.如果n是質(zhì)數(shù)p的k次方，k為正整數(shù)，則φ(n) = p^k - p^(k-1) = p^k(1 - 1/p)
    4.如果n為兩個(gè)互質(zhì)的整數(shù)p1、p2之積，那么φ(n) =φ(p1) * φ(p2)
    5.因?yàn)槿我庖粋€(gè)大于1的正整數(shù)都可以寫(xiě)成一系列質(zhì)數(shù)p1,p2,p3...pn之積
      φ(n) = φ(p1^k1 * p2^k2 *...pn^kn) 
           = φ(p1^k1) * φ(p2^k2) * ... * φ(pn^kn)
           = p1^k1(1 - 1/p1) * p2^k2(1-1/p2)...* pn^kn(1-1/pn)
           = n * (1-1/p1)(1-1/p2)...(1-1/pn)

      φ(72) = φ(8*9) = φ(2^3 * 3^2) = 72*(1-1/2)(1-1/3) = 24
            = φ(8) * φ(9) = 4 * 6 = 24 

歐拉函數(shù)通用計(jì)算公式

• 歐拉定理：如果兩個(gè)正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù)φ(n)可以讓下面的等式成立：a^φ(n) % n = 1，a的φ(n)次方除以n取余等于1；如果兩個(gè)正整數(shù)a與質(zhì)數(shù)p互質(zhì)，a^φ(p) % p = a^(p-1) % p = 1，這就是著名的費(fèi)馬小定理，歐拉定理是RSA算法的核心。
• 模反元素：如果兩個(gè)正整數(shù)a和n互質(zhì)，那么一定可以找到整數(shù)b，使用a * b - 1 被n整除，這時(shí)b就叫做a的模反元素，比如7和9互質(zhì)，7*4 % 9 = 1，那么此時(shí)4就是7的模反元素，另外13、22、31都是，即b + k * n都是a的模反元素。

了解上面的數(shù)論知識(shí)之后，再來(lái)理解RSA算法就比較容易了，假如A和B要進(jìn)行加密通信，那么如何生成公鑰和私鑰？

• 第一步，隨機(jī)選擇兩個(gè)不相等的質(zhì)數(shù)p和q。
• 第二步，計(jì)算p和q的乘積n，n轉(zhuǎn)化為二進(jìn)制的長(zhǎng)度就是密鑰的長(zhǎng)度，實(shí)際應(yīng)用中一般RSA的密鑰長(zhǎng)度是1024位，重要場(chǎng)合則為2048位。
• 第三步，計(jì)算n的歐拉函數(shù)φ(n)，根據(jù)公式φ(n) = (p-1)(q-1)
• 第四步，隨機(jī)選擇一個(gè)整數(shù)e
• 第五步，計(jì)算e對(duì)于φ(n)的模反元素d，即滿(mǎn)足e * d - 1 = k*φ(n)，即對(duì)二元一次方程求解e*x - φ(n)*y = 1，其中e和φ(n)已知，使用擴(kuò)歐幾里得算法求解得出一組(x,y)，即得d = y
• 第六步，將n和e封裝成公鑰，n和d封裝成私鑰。在實(shí)際應(yīng)用中公鑰和私鑰的數(shù)據(jù)都是采用ASN.1格式表達(dá)(感興趣可以查看維基百科ASN.1，需要科學(xué)上網(wǎng))

RSA算法的可靠性

由于n和e是公開(kāi)的，d為推導(dǎo)出來(lái)的，如果d被算出來(lái)，那么就意味著私鑰被破解，我們可以看一下d的推導(dǎo)過(guò)程：

• e * d % φ(n) = 1，只要計(jì)算出φ(n)，那么d就能被算出來(lái)
• 如何計(jì)算φ(n)，φ(n) = (p-1)(q-1)，計(jì)算p和q兩個(gè)質(zhì)數(shù)即可算出φ(n)
• n=p*q，將n進(jìn)行因數(shù)分解，才能算出p和q

總結(jié)：如果n可以被因數(shù)分解，私鑰才能被破解

維基百科對(duì)于RSA有這樣一段描述：

對(duì)極大整數(shù)做因數(shù)分解的難度決定了 RSA 算法的可靠性。換言之，對(duì)一極大整數(shù)做因數(shù)分解愈困難，RSA 算法愈可靠。假如有人找到一種快速因數(shù)分解的算法的話，那么用 RSA 加密的信息的可靠性就會(huì)極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的 RSA 鑰匙才可能被強(qiáng)力方式破解。到目前為止，世界上還沒(méi)有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能被破解的。

目前已公布分解出的最大整數(shù)是232個(gè)十進(jìn)制位，768個(gè)二進(jìn)制位，因此1024位很安全，2048位非常安全。

• 公鑰加密：消息m使用公鑰加密(n,e)，m * e % n = c，m必須是整數(shù)（字符串可以取ascii值或unicode值），且m必須小于n
• 私鑰解密：c * d % n = m
  在這個(gè)過(guò)程中依賴(lài)于迪菲赫爾曼密鑰交換算法 等式m ^ (e * d) % n = m 可拆分為m * e % n = c，c * d % n = m。不難看出我們也可以使用d加密，e解密。論證了上面所提到的公鑰加密，私鑰解密；私鑰加密，公鑰解密。

Mac系統(tǒng)內(nèi)置OpenSSL(開(kāi)源加密庫(kù))，所以我們可以使用終端嘗試使用RSA

• 生成RSA私鑰，指定長(zhǎng)度1024bit，命令為openssl genrsa -out private.pem 1024
  

  終端截圖示例

• 從私鑰中提取公鑰，命令為openssl rsa -in xxx.pem -pubout -out public.pem

• 隨便創(chuàng)建一個(gè)txt文件，并寫(xiě)入一些內(nèi)容，注意不能太長(zhǎng)，比如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

• 私鑰加密公鑰解密：
  openssl rsautl -sign -in message.txt -inkey private.pem -out enc.txt
openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt

OC代碼中使用RSA不能直接使用pem格式文件，需要將私鑰轉(zhuǎn)成p12文件，公鑰轉(zhuǎn)成der格式

• 首先需要請(qǐng)求一個(gè)csr的文件，因?yàn)樽C書(shū)是需要認(rèn)證的，這個(gè)csr文件中包含一些信息如Country Name、Organization Name、Email等。隨便填~
  終端命令為：openssl req -new -key private.pem -out rsacert.csr，過(guò)程中需要填寫(xiě)一些信息以及密碼(空即可)。
• 證書(shū)簽名生成crt文件：openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt，-days 3650有效期十年的自簽名證書(shū)(https協(xié)議就需要這樣的一個(gè)證書(shū)，想省錢(qián)可以使用這種自簽名證書(shū)，將crt文件放在服務(wù)器上，讓別人接受即可~)
• crt生成p12文件：openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt，需要輸入密碼
• 生成der文件：openssl x509 -outform der -in rsacert.crt -out rsacert.der
• 將p.p12和rsacert.der文件添加到工程中使用。主要是使用動(dòng)態(tài)庫(kù)Security中的SecKey類(lèi)中的方法

OSStatus SecKeyEncrypt(
                       SecKeyRef           key,
                       SecPadding          padding,
                       const uint8_t        *plainText,
                       size_t              plainTextLen,
                       uint8_t             *cipherText,
                       size_t              *cipherTextLen)

使用方法github有很多封裝示例，這里就不再列舉。