Ⅰ 9 非對稱加密
目前為止，本書中只討論到對稱加密。假設一個密碼系統不只有一個密鑰，而是有一對密鑰，其中公鑰可以自由地發布，而私鑰由自己保管。其他人可以使用你的公鑰來加密數據，這個信息只有你的私鑰可以解密，這個被稱為 公鑰加密（public-key encryption）
很長一段時間，這都被認為是不可能的。然而從1970年開始，這一類型的演算法開始出現。第一個廣為流傳的是MIT的三位密碼學家：Ron Rivest，Adi Shamir 和Leonard Adleman提出的RSA。
公鑰演算法並不僅僅用來加密，實際上本書之前的部分已經提到過公鑰演算法而其不是直接用在加密上。有三個與公鑰演算法相關的主題
從表面來看，公鑰加密好像可以淘汰之前提到的對稱密鑰演算法。對於任何事情都可以使用公鑰加密，也不需要對稱密鑰系統中的密鑰交換過程。然而在實際的密碼學系統中，可以看到到處都是混合的加密，公鑰加密在其中起著重要作用，但是大部分的加解密以及認證工作還是基於對成密鑰演算法的。
目前來皮褲看最重要的原因是性能。與流密碼（原生的流密碼或者其他）演算法相比，公鑰加密機制實在是太慢了。RSA通常情況下需要2048位也就是256個位元組。其加密需要0.29百萬次循環，解密需要11.12百萬次循環。而對稱加密和解密只需要每位元組約10次循環。這也意味著在對稱密鑰演算法中，解密256位數據，只需要3000次循環，這個效率是非對稱版本的4000次。而目前塵握猛的密碼系統使得對稱加密更快了，在AES-GCM硬體加速或者Salsa20/ChaCha20隻需要2或者4次每位元組，更大程度上提高了性能。
實際的密碼系統中還有更多其他的問題。例如對於RSA來說，它不能加密任何比它大的信息，通常情況是小於或者等於4096位，比大部分的需求要小的多。當然最重要的問題依然是上述的速度的問題。
本節簡單描述RSA背後的數學問題。其本身並不能產生安全加密機制。之後會看到在其上構造的密碼指導OAEP。
為了產生一個key，需要挑選兩個大素數p和q，這些數需要隨機私密的挑選。將兩者相乘的到N，這個是公開的。然後選擇一個加密指數e，這個也是公開的。通常這個數是3或者65537.因為這些數的二進制形式中僅有很少量的1。計算指數會更有效。（N，e）是公鑰，任何人都可以用公鑰來加密消息M，得到密文C。
接下來的問題是解密，有一個解密指數d，可以將C轉化會M。如果指導p和q，d很容易計算。可以使用d來解密消息：
RSA的安全性依賴於對於不知道d的人來說解密操作是不可能的，並且在只知道（N，e）的情況下d的計算是非常難的。
類似於很多密碼系統，RSA依賴於特定數學問題的難度。給定密文C，和公鑰（N，e），反推出明文M。這被稱為RSA難題。
最直接的方法是將N分解為p*q。給定p和q，攻擊者只需要重復密鑰擁有者的過程來計算產生d即可。
幸運的是，沒有一個演算法可以在合理的時間內分解這么大的數。不幸的是，目前也無法證明該演算法一定不存在。更加糟糕的是，有一個理論上的演算法，被稱為Shor's Algorithm，可以在量子計算機上在合理的時間內分解一個數。目前，量子計算機還離我們有些遠，但是未來某天可能就會成為現實。到時候RSA就變得不再有效。
本節中僅僅提到了分解大數這個最直接的方式來攻擊RSA。在接下來的部分可以看到一系列針對RSA的實際攻擊，其主要依賴於一些具體的實現。
目前，沒有已知的實際的攻破RSA的方法。但這不意味著使用RSA的系統沒有被攻破過。和其他被攻破的系統一樣，應用中有很多組成部分，一旦其中的某部分沒有恰當的使用，就會使整個系統變得不可用。更多有關RSA實施的細節的，參考【Bon99】和【AV96】，本部分只提及一些有趣的部分。
Salt是一個用python寫的供應系統。它有一個模塊叫做 cypto ，它沒有使用已有的密碼學系統，而是實現了一個自己的，其中使用的RSA和AES由第三方庫提供。
很長一段時間里，Salt使派橋用的公鑰指數e是1，這也就意味著P e=P 1=P(mod N)。這也就意味著結果的密文就是明文。目前該問題已經被修復，這里只是為了提醒大家，不要實現自己的加密系統。Salt現在支持了SSH作為傳輸蹭，但是先前提到的DIY的RSA/AES系統依然存在，並且還是默認的傳輸層。
OAEP是Optimal asymmetric encryption padding的簡稱，是RSA填充的一種。它的結構類似於下圖（文檔中這個圖有問題，下面是正確的圖）：
最終產生的需要被加密的數據是X||Y，是n位長，這個n是N的位數。它使用一個隨機的塊R它的長度是k，在這個標准中，k是一個定值。消息首先需要用0填充被擴充到n-k位。圖中左邊的長度為n-k位，右邊的長度為k。隨機塊R和以0擴充的M，M||000...使用兩個陷阱函數，G和H。陷阱函數都是從一個方向計算非常簡單，但是逆轉非常的難。世紀中通常為hash函數。
G的輸入是k位，輸出是n-k位，H的輸入是n-k位，輸出是k位。
然後結果的X和Y被連接在一起，然後由標準的RSA來進行加密產生密文。
解密的時候，要反過來操作。接收者收到X||Y，他們是指導k的，因為這個是協議里的定值。所以前n-k是X，後k位是Y。
想要得到M，M||000...,需要去計算
可以看出，對於一些H和G來說，需要所有的X和Y才能找到M。對於H和G有很多種基於Hash函數的選擇。
絕大多數的公鑰加密只能一次加密一小塊，一般都遠小於要發送的信息。另外這些演算法還很慢，比對稱加密要慢的多。通常非對稱加密用來連接密碼系統。
有了公鑰密碼和密鑰交換，是密碼學裡面兩個非常重要的部分，因為人們總是需要與其他人交換私密的信息。有了這兩個技術就可以安全地和其他人交流。
目前為止討論的加密都沒有任何形式的身份認證。這也就意味著對消息進行加密和解密，並不能驗證得到的消息確實是發送者發送的原本的消息。
沒有身份認證的加密可以提供隱私性，但是如之前章節所言，沒有身份認證，盡管攻擊者不知道任何原文的信息，他任然可以修改加密的信息。接收這些消息會泄漏一些私密的信息，這也就意味著私密性不在。例如之前第7章提到的CBC的填充攻擊。
綜上所言，出了加密私密的信息之外，還需要對其進行身份認證。通常身份認證都是對消息增加一些額外的可計算的信息。類似於加密，身份認證也分為對稱類型的和非對稱類型的。對稱類型的通常被稱為消息認證（message authentication），非對稱類型的通常被稱為數字簽名。
下一章先介紹一下另一個密碼學中的重點：hash函數。hash在產生簽名和消息認證等過程中都需要用到。
[Bon99] Dan Boneh. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS , 46:203–213, 1999. URL: http://crypto.stanford.e/dabo/papers/RSA-survey.pdf .
[AV96] Ross Anderson and Serge Vaudenay. Minding your pʼs and qʼs. In In Advances in Cryptology - ASIACRYPT』96, LNCS 1163 , 26–35. Springer� Verlag, 1996. URL: http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf .