9.1 概述
目前為止汁讼，本書(shū)中只討論到對(duì)稱(chēng)加密嘿架。假設(shè)一個(gè)密碼系統(tǒng)不只有一個(gè)密鑰啸箫，而是有一對(duì)密鑰，其中公鑰可以自由地發(fā)布蝉娜，而私鑰由自己保管扎唾。其他人可以使用你的公鑰來(lái)加密數(shù)據(jù)，這個(gè)信息只有你的私鑰可以解密荧呐，這個(gè)被稱(chēng)為公鑰加密（public-key encryption）
很長(zhǎng)一段時(shí)間纸镊，這都被認(rèn)為是不可能的。然而從1970年開(kāi)始峰搪，這一類(lèi)型的算法開(kāi)始出現(xiàn)概耻。第一個(gè)廣為流傳的是MIT的三位密碼學(xué)家：Ron Rivest，Adi Shamir 和Leonard Adleman提出的RSA咐蚯。
公鑰算法并不僅僅用來(lái)加密春锋，實(shí)際上本書(shū)之前的部分已經(jīng)提到過(guò)公鑰算法而其不是直接用在加密上差凹。有三個(gè)與公鑰算法相關(guān)的主題
- 密鑰交換算法，例如Diffie-Hellman呐萌，在不安全的媒介上共享私密的信息谊娇。
- 加密算法，本章的內(nèi)容赠堵，可以讓用戶(hù)加密一個(gè)東西而不需要提前共享密鑰法褥。
- 簽名算法，在之后章節(jié)會(huì)討論揍愁，用戶(hù)可以使用私鑰對(duì)一些信息進(jìn)行簽名杀饵，而其他人使用公鑰可以對(duì)這些信息進(jìn)行驗(yàn)證。
9.2 為什么不在所有的場(chǎng)景上都是用公鑰加密
從表面來(lái)看烁登，公鑰加密好像可以淘汰之前提到的對(duì)稱(chēng)密鑰算法蔚舀。對(duì)于任何事情都可以使用公鑰加密，也不需要對(duì)稱(chēng)密鑰系統(tǒng)中的密鑰交換過(guò)程狼牺。然而在實(shí)際的密碼學(xué)系統(tǒng)中礼患，可以看到到處都是混合的加密掠归，公鑰加密在其中起著重要作用虏冻，但是大部分的加解密以及認(rèn)證工作還是基于對(duì)成密鑰算法的弹囚。
目前來(lái)看最重要的原因是性能。與流密碼（原生的流密碼或者其他）算法相比蛮穿，公鑰加密機(jī)制實(shí)在是太慢了毁渗。RSA通常情況下需要2048位也就是256個(gè)字節(jié)。其加密需要0.29百萬(wàn)次循環(huán)府适，解密需要11.12百萬(wàn)次循環(huán)细溅。而對(duì)稱(chēng)加密和解密只需要每字節(jié)約10次循環(huán)儡嘶。這也意味著在對(duì)稱(chēng)密鑰算法中，解密256位數(shù)據(jù)誓篱，只需要3000次循環(huán)凯楔，這個(gè)效率是非對(duì)稱(chēng)版本的4000次。而目前的密碼系統(tǒng)使得對(duì)稱(chēng)加密更快了邻遏，在AES-GCM硬件加速或者Salsa20/ChaCha20只需要2或者4次每字節(jié)虐骑，更大程度上提高了性能。
實(shí)際的密碼系統(tǒng)中還有更多其他的問(wèn)題糊饱。例如對(duì)于RSA來(lái)說(shuō)颠黎，它不能加密任何比它大的信息滞项，通常情況是小于或者等于4096位文判，比大部分的需求要小的多室梅。當(dāng)然最重要的問(wèn)題依然是上述的速度的問(wèn)題。
9.3 RSA
加密和解密
本節(jié)簡(jiǎn)單描述RSA背后的數(shù)學(xué)問(wèn)題。其本身并不能產(chǎn)生安全加密機(jī)制灰嫉。之后會(huì)看到在其上構(gòu)造的密碼指導(dǎo)OAEP。
為了產(chǎn)生一個(gè)key浑厚，需要挑選兩個(gè)大素?cái)?shù)p和q根盒，這些數(shù)需要隨機(jī)私密的挑選。將兩者相乘的到N敢艰，這個(gè)是公開(kāi)的册赛。然后選擇一個(gè)加密指數(shù)e，這個(gè)也是公開(kāi)的牡属。通常這個(gè)數(shù)是3或者65537.因?yàn)檫@些數(shù)的二進(jìn)制形式中僅有很少量的1扼睬。計(jì)算指數(shù)會(huì)更有效。（N措伐，e）是公鑰军俊，任何人都可以用公鑰來(lái)加密消息M，得到密文C官硝。
接下來(lái)的問(wèn)題是解密，有一個(gè)解密指數(shù)d氢架，可以將C轉(zhuǎn)化會(huì)M。如果指導(dǎo)p和q卿操，d很容易計(jì)算孙援。可以使用d來(lái)解密消息：
RSA的安全性依賴(lài)于對(duì)于不知道d的人來(lái)說(shuō)解密操作是不可能的窥摄，并且在只知道（N础淤，e）的情況下d的計(jì)算是非常難的。
打破RSA
類(lèi)似于很多密碼系統(tǒng)币砂，RSA依賴(lài)于特定數(shù)學(xué)問(wèn)題的難度玻侥。給定密文C决摧，和公鑰（N蜜徽，e）票摇，反推出明文M。這被稱(chēng)為RSA難題盆色。
最直接的方法是將N分解為p*q祟剔。給定p和q物延，攻擊者只需要重復(fù)密鑰擁有者的過(guò)程來(lái)計(jì)算產(chǎn)生d即可。
幸運(yùn)的是浑吟，沒(méi)有一個(gè)算法可以在合理的時(shí)間內(nèi)分解這么大的數(shù)。不幸的是组力，目前也無(wú)法證明該算法一定不存在。更加糟糕的是腥椒，有一個(gè)理論上的算法候衍，被稱(chēng)為Shor's Algorithm，可以在量子計(jì)算機(jī)上在合理的時(shí)間內(nèi)分解一個(gè)數(shù)滨砍。目前榨为，量子計(jì)算機(jī)還離我們有些遠(yuǎn)随闺，但是未來(lái)某天可能就會(huì)成為現(xiàn)實(shí)蔓腐。到時(shí)候RSA就變得不再有效。
本節(jié)中僅僅提到了分解大數(shù)這個(gè)最直接的方式來(lái)攻擊RSA散罕。在接下來(lái)的部分可以看到一系列針對(duì)RSA的實(shí)際攻擊傀蓉，其主要依賴(lài)于一些具體的實(shí)現(xiàn)。
實(shí)施中的隱患
目前误甚，沒(méi)有已知的實(shí)際的攻破RSA的方法谱净。但這不意味著使用RSA的系統(tǒng)沒(méi)有被攻破過(guò)壕探。和其他被攻破的系統(tǒng)一樣，應(yīng)用中有很多組成部分瞧筛，一旦其中的某部分沒(méi)有恰當(dāng)?shù)氖褂茫蜁?huì)使整個(gè)系統(tǒng)變得不可用驾窟。更多有關(guān)RSA實(shí)施的細(xì)節(jié)的，參考【Bon99】和【AV96】月培，本部分只提及一些有趣的部分恩急。
Salt
Salt是一個(gè)用python寫(xiě)的供應(yīng)系統(tǒng)。它有一個(gè)模塊叫做cypto此叠，它沒(méi)有使用已有的密碼學(xué)系統(tǒng)随珠，而是實(shí)現(xiàn)了一個(gè)自己的，其中使用的RSA和AES由第三方庫(kù)提供茸歧。
很長(zhǎng)一段時(shí)間里显沈，Salt使用的公鑰指數(shù)e是1，這也就意味著Pe=P1=P(mod N)蹲坷。這也就意味著結(jié)果的密文就是明文。目前該問(wèn)題已經(jīng)被修復(fù)贼穆，這里只是為了提醒大家御板，不要實(shí)現(xiàn)自己的加密系統(tǒng)。Salt現(xiàn)在支持了SSH作為傳輸蹭铺呵，但是先前提到的DIY的RSA/AES系統(tǒng)依然存在隧熙，并且還是默認(rèn)的傳輸層。
OAEP（Optimal asymmetric encryption padding）最優(yōu)非對(duì)稱(chēng)加密填充
OAEP是Optimal asymmetric encryption padding的簡(jiǎn)稱(chēng)音念，是RSA填充的一種。它的結(jié)構(gòu)類(lèi)似于下圖（文檔中這個(gè)圖有問(wèn)題整葡，下面是正確的圖）：
最終產(chǎn)生的需要被加密的數(shù)據(jù)是X||Y讥脐，是n位長(zhǎng)，這個(gè)n是N的位數(shù)俱萍。它使用一個(gè)隨機(jī)的塊R它的長(zhǎng)度是k告丢，在這個(gè)標(biāo)準(zhǔn)中，k是一個(gè)定值岖免。消息首先需要用0填充被擴(kuò)充到n-k位颅湘。圖中左邊的長(zhǎng)度為n-k位，右邊的長(zhǎng)度為k掂摔。隨機(jī)塊R和以0擴(kuò)充的M术羔，M||000...使用兩個(gè)陷阱函數(shù)，G和H释移。陷阱函數(shù)都是從一個(gè)方向計(jì)算非常簡(jiǎn)單寥殖，但是逆轉(zhuǎn)非常的難。世紀(jì)中通常為hash函數(shù)熏纯。
G的輸入是k位粤策，輸出是n-k位，H的輸入是n-k位，輸出是k位霹俺。
然后結(jié)果的X和Y被連接在一起丙唧，然后由標(biāo)準(zhǔn)的RSA來(lái)進(jìn)行加密產(chǎn)生密文觅玻。
解密的時(shí)候，要反過(guò)來(lái)操作串塑。接收者收到X||Y，他們是指導(dǎo)k的打瘪，因?yàn)檫@個(gè)是協(xié)議里的定值傻昙。所以前n-k是X，后k位是Y僻爽。
想要得到M贾惦，M||000...,需要去計(jì)算
可以看出，對(duì)于一些H和G來(lái)說(shuō)碰镜，需要所有的X和Y才能找到M习瑰。對(duì)于H和G有很多種基于Hash函數(shù)的選擇。
9.4 橢圓曲線(xiàn)（書(shū)中暫未介紹）
9.5 遺留問(wèn)題：未驗(yàn)證的加密
絕大多數(shù)的公鑰加密只能一次加密一小塊柠横，一般都遠(yuǎn)小于要發(fā)送的信息课兄。另外這些算法還很慢，比對(duì)稱(chēng)加密要慢的多搬俊。通常非對(duì)稱(chēng)加密用來(lái)連接密碼系統(tǒng)悠抹。
有了公鑰密碼和密鑰交換，是密碼學(xué)里面兩個(gè)非常重要的部分楔敌，因?yàn)槿藗兛偸切枰c其他人交換私密的信息。有了這兩個(gè)技術(shù)就可以安全地和其他人交流庆聘。
目前為止討論的加密都沒(méi)有任何形式的身份認(rèn)證勺卢。這也就意味著對(duì)消息進(jìn)行加密和解密，并不能驗(yàn)證得到的消息確實(shí)是發(fā)送者發(fā)送的原本的消息宴抚。
沒(méi)有身份認(rèn)證的加密可以提供隱私性甫煞，但是如之前章節(jié)所言，沒(méi)有身份認(rèn)證常潮，盡管攻擊者不知道任何原文的信息，他任然可以修改加密的信息喊式。接收這些消息會(huì)泄漏一些私密的信息萧朝，這也就意味著私密性不在。例如之前第7章提到的CBC的填充攻擊贸诚。
綜上所言方庭，出了加密私密的信息之外，還需要對(duì)其進(jìn)行身份認(rèn)證头朱。通常身份認(rèn)證都是對(duì)消息增加一些額外的可計(jì)算的信息项钮。類(lèi)似于加密，身份認(rèn)證也分為對(duì)稱(chēng)類(lèi)型的和非對(duì)稱(chēng)類(lèi)型的烁巫。對(duì)稱(chēng)類(lèi)型的通常被稱(chēng)為消息認(rèn)證（message authentication）亚隙，非對(duì)稱(chēng)類(lèi)型的通常被稱(chēng)為數(shù)字簽名。
下一章先介紹一下另一個(gè)密碼學(xué)中的重點(diǎn)：hash函數(shù)诊霹。hash在產(chǎn)生簽名和消息認(rèn)證等過(guò)程中都需要用到渣淳。
[Bon99] Dan Boneh. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46:203–213, 1999. URL: http://crypto.stanford.edu/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.
