2025/8/1315.1非對稱密碼體制概述通過前面的學(xué)習，我們對分組密碼和序列密碼都有了一定的了解。分組密碼和序列密碼都屬于對稱密碼體制。兩個用戶在用對稱密碼體制進行保密通信時，必須要有一個雙方共享的加密密鑰。那么，如何才能讓兩個不在同一個地方的用戶安全地擁有共享密鑰呢？我們可能想到的方式包括：（1）派一個人來把密鑰從一方送到另外一方；（2）通過郵件或快遞傳遞密鑰；（3）電子郵件、電話或電報等方式傳遞等等?！狿KI第三種方式傳遞是不安全的。因為在沒有共享密鑰前，雙方只能用明文的方式進行通信。如果是重要的信息，電子郵件、電話和電報等往往都處于被竊聽的狀態(tài)，所以是不安全的。第二種方式的時間需求比較多，曾經(jīng)是商業(yè)用途的密鑰傳遞的重要方式之一。如果信息非常重要的，比如涉及到國家安全的機密信息，也是不安全的。第一種方式從時間和代價上來看，都難以符合需要。在非對稱密碼體制產(chǎn)生前，對于很多不是很重要的信息，用得較多的解決辦法就是第二種方式，但效率是比較低的。2025/8/1332025/8/1345.3.1非對稱密碼體制的原理假設(shè)有一種掛鎖，在沒有鎖上的情況下，任何人都可以輕松鎖上。但鎖上后，只有有該鎖的鑰匙的人，才可以用鑰匙打開。假設(shè)Alice把她的這種掛鎖放到郵局，則任何想與她秘密通信的人都可以把消息放到一個箱子里，然后用掛鎖鎖上箱子，寄給Alice。由于只有Alice有開鎖的鑰匙，故只有Alice能打開箱子。正是基于這種思想，密碼學(xué)家設(shè)計出了非對稱密碼體制。

根據(jù)英國科普作家SimonSingh（西蒙·辛格）的作品《thecodebook》（中文譯為《密碼故事》），二戰(zhàn)時，德國高級指揮部每個月都需要分發(fā)《每日密鑰》月刊給所有的“恩格瑪”機操作員。即使U型潛艇大多數(shù)時間都遠離基地，它也不得不想辦法獲得最新的密鑰(《獵殺U571》)。無論某種對稱密碼算法從理論上講是多么安全，在實際運用中，都不可避免地遇到了“密鑰分發(fā)”的問題，這就大大限制了它的可實施性和安全性。假設(shè)一個公司包含N個距離較遠的機構(gòu)，各個分支機構(gòu)之間能相互進行秘密通訊，他們每一個月要更換一次相互通訊用的加密密鑰。容易計算，每次更換密鑰的數(shù)量是N（N-1）/2。當N較大時，比如N=50，這個事情完成起來代價不菲。從某種程度上講，政府和軍隊可以通過花費大筆的金錢來解決密鑰分發(fā)的問題。美國政府的密鑰是COMSEC(通訊安全局的縮寫)掌管和分發(fā)的。1970年代，COMSEC每天分發(fā)的密鑰數(shù)以噸計。當裝載著COMSEC密鑰的船靠港時，密碼分發(fā)員會接收各種貯存密鑰的介質(zhì)。然后，把它們分發(fā)給客戶。——解決失業(yè)問題？密鑰分發(fā)成了戰(zhàn)后密碼學(xué)家要解決的最重要的問題。如果兩個組織需要安全通訊，卻需要第三方來傳送密鑰，這就成了安全通訊最薄弱的環(huán)節(jié)。那如何才能用較小的代價，較高的效率實現(xiàn)通信雙方的密鑰傳遞呢？正是由于這個需求，促使了非對稱密碼體制的產(chǎn)生。1976年，Diffie和Hellman發(fā)表了非對稱密碼的奠基性的論文“密碼學(xué)的新方向”，建立了公鑰密碼的概念，引起了廣泛關(guān)注，隨后，密碼學(xué)家們很快構(gòu)造出了滿足條件的非對稱密碼體制，包括斯坦福大學(xué)的Merkle和Hellman提出的基于陷門背包的公鑰密碼算法和麻省理工學(xué)院的Rivest、Shamir和Adleman提出的RSA算法。由于基于陷門背包的公鑰密碼系統(tǒng)及其變體大都被后來的研究者破解，故在一些密碼學(xué)書籍中已經(jīng)看不到了；而RSA算法則經(jīng)過深入的研究和廣泛使用，一直都現(xiàn)在為止都認為是計算上安全的。——這一段出現(xiàn)了2屆圖靈獎獲得者圖靈獎（A.M.TuringAward），由美國計算機協(xié)會（ACM）于1966年設(shè)立，又叫“A.M.圖靈獎”，專門獎勵那些對計算機事業(yè)作出重要貢獻的個人。其名稱取自計算機科學(xué)的先驅(qū)、英國科學(xué)家艾倫·麥席森·圖靈（AlanM.Turing，1912-1954）。由于圖靈獎對獲獎條件要求極高，評獎程序又是極嚴，一般每年只獎勵一名計算機科學(xué)家，只有極少數(shù)年度有兩名合作者或在同一方向作出貢獻的科學(xué)家共享此獎。因此它是計算機界最負盛名、最崇高的一個獎項，有“計算機界的諾貝爾獎”之稱。2002年：RonaldL.Rivest，AdiShamir，LeonardM.Adleman公鑰密碼學(xué)（RSA加密算法）2015年：WhitfieldDiffieandMartinHellman 對現(xiàn)代密碼學(xué)做出的重要貢獻***大家比較熟悉的有***1974年：高德納DonaldE.Knuth算法分析、程序設(shè)計語言的設(shè)計、程序設(shè)計2000年：姚期智AndrewChi-ChihYao計算理論，包括偽隨機數(shù)生成，密碼學(xué)與通信復(fù)雜度艾倫·麥席森·圖靈（AlanMathisonTuring，1912年6月23日－1954年6月7日），英國數(shù)學(xué)家、邏輯學(xué)家，被稱為計算機科學(xué)之父，人工智能之父。圖靈對于人工智能的發(fā)展有諸多貢獻，提出了一種用于判定機器是否具有智能的試驗方法，即圖靈試驗，至今，每年都有試驗的比賽。此外，圖靈提出的著名的圖靈機模型為現(xiàn)代計算機的邏輯工作方式奠定了基礎(chǔ)。1954年6月7日，圖靈被發(fā)現(xiàn)死于家中的床上，床頭還放著一個被咬了一口的蘋果。警方調(diào)查后認為是劇毒的氰化物中毒，調(diào)查結(jié)論為自殺。On24December2013,

QueenElizabethII

signedapardon

forTuring'sconvictionforgrossindecency,withimmediateeffect.【2013年12月24日,英國女王伊麗莎白二世簽署對圖靈定性為“嚴重猥褻”的赦免,并立即生效。】《模仿游戲》-改編自安德魯·霍奇斯編著的傳記《艾倫·圖靈傳》，講述了“計算機科學(xué)之父”艾倫·圖靈的傳奇人生。圖靈對于人工智能的發(fā)展有諸多貢獻，提出了一種用于判定機器是否具有智能的試驗方法，即圖靈試驗，至今，每年都有試驗的比賽。此外，圖靈提出的著名的圖靈機模型為現(xiàn)代計算機的邏輯工作方式奠定了基礎(chǔ)。5.1.1非對稱密碼體制的原理在對稱密碼體制中，除了加密及解密算法是公開的，一個重要的特點是加密算法與解密算法的密鑰相同，或者容易從其中一個得到另一個，這要求通信雙方要有共享的加密密鑰。那么，可不可以出現(xiàn)下面的情況呢？假設(shè)有一種掛鎖，在沒有鎖上的情況下，任何人都可以輕松鎖上。但鎖上后，只有有該鎖匹配鑰匙的人，才可以用鑰匙打開。假設(shè)Alice把她的這種掛鎖放到郵局，則任何想與她秘密通信的人都可以把消息放到一個箱子里，然后用掛鎖鎖上箱子，寄給Alice.由于只有Alice有開鎖的鑰匙，故只有Alice能打開箱子。正是基于這種思想，密碼學(xué)家設(shè)計出了非對稱密碼體制。假設(shè)B想給A發(fā)送秘密消息，參考保密通信模型，非對稱密碼體制的模型可以用下圖表示。非對稱密碼體制的模型圖公鑰密碼的基本思想：

將密鑰K一分為二，一個專門加密，一個專門解密：PKB≠SKB由PKB不能計算出SKB，因此可將PKB公開，使密鑰分配簡單由于PKB≠SKB，且由PKB不能計算出SKB，因此可將SKB作為用戶指紋，以方便實現(xiàn)數(shù)字簽名2025/8/1315據(jù)上圖所示的模型，描述利用非對稱密碼體制進行保密通信的過程為：（1）主體A若需要其他主體利用非對稱密碼體制向他發(fā)送秘密消息，先要生成一對密鑰，其中一個用于加密，另一個用于解密。用于加密的密鑰在非對稱密碼體制中稱為公開密鑰，也稱公開鑰或公鑰，是不需要保密的。A的公開密鑰通常表示為PKA(publickeyofA)。用于解密的密鑰稱為秘密密鑰，簡稱秘密鑰或私鑰，需要解密方嚴格保密。B的秘密密鑰通常表示為SKA(secretkeyofA)。在知道密碼算法和公開密鑰的情況下，要得到秘密密鑰在計算上是不可行的。

由于只有接收者A有解密密鑰，故密文c在公共信道的傳輸過程中是安全的。如果這個模型能夠得以實現(xiàn)，假設(shè)傳遞的消息就是通信雙方將要在對稱密碼體制中使用的密鑰，則前面我們提到的密鑰傳遞就容易被解決了。現(xiàn)實中，后面我們要學(xué)到的RSA密碼算法，就是這個模型的一個實現(xiàn)，并且得到了廣泛的應(yīng)用。2025/8/1318-公鑰密碼系統(tǒng)的數(shù)學(xué)描述：滿足如下條件的五元組(M,C,K,E,D)（1）M是可能消息的集合；（2）C是可能密文的集合；（3）K是可能密鑰的有限集（4）對每一個k=(PK,SK)K,有PK

E,SK

D,滿足對所有m

M,DSK(EPK(m))=m

（5）對所有k,PK

SK

是計算上不可能的。2025/8/13195.1.2非對稱密碼體制的設(shè)計準則現(xiàn)在應(yīng)用的非對稱密碼體制，其安全是指的計算上是安全的。以著名的RSA算法所基于的大數(shù)分解難題為例，它假定n是兩個大素數(shù)p和q的乘積?，F(xiàn)在一般認為，p和q的長度都是512比特左右，則n的長度是1024比特左右。以人們現(xiàn)有的計算能力，在知道n的情況下，在短時間內(nèi)是不能分解n的，也就是說，這在計算上是安全的。從理論上講，如果有足夠的計算能力，是可以分解n的。但如果分解n的時間超過了消息的保密期，或者投入的物力超過了消息本身的價值，對消息保密的目的就達到了。假設(shè)Alice是密碼消息的接收方，由他產(chǎn)生公開鑰PKA和秘密鑰SKA，通常認為，一個實用的非對稱密碼體制應(yīng)該滿足如下的性質(zhì)：①接收方Alice產(chǎn)生密鑰對（公開鑰PKA和秘密鑰SKA）在計算上是容易的。②消息發(fā)送方Bob用接收方Alice的公開鑰對消息m加密以產(chǎn)生密文c是容易的。③接收方Alice用自己的秘密鑰SKA對c解密是容易的?！龊侠淼?、允許的事情是容易的④密碼分析者由Alice的公開鑰PKA求秘密鑰SKA在計算上是不可行的。⑤密碼分析者由密文c和Alice的公開鑰PKA恢復(fù)明文m在計算上是不可行的?！霌v騰不允許的事情是困難的！如果還滿足下面的性質(zhì)，則該非對稱密碼體制可以用于數(shù)字簽名。⑥加、解密次序可換，即

在上面的描述中，“在計算上是容易的”可以理解為在物力上的投入少且計算時間短。相反，“在計算上是不可行的”也就是“在計算上是安全的”。一個密碼算法要進入實用階段，除了在理論上是安全的，在使用過程中，比如用到電子商務(wù)中，在投入上應(yīng)該是商家能夠接受的；對用戶來說，接受商家的服務(wù)，無論是由于網(wǎng)絡(luò)的原因，還是算法計算需要時間的原因，所等待的時間是要可以容忍的，密碼算法的使用是透明的，因為不可能每個用戶都去掌握密碼理論。只有這樣，這個算法投入商業(yè)使用才會有市場。-【小結(jié)】公鑰密碼算法應(yīng)滿足的要求：（1）秘密性：D(E(M))=M（保密條件）（2）實用性：（高效）接收方B產(chǎn)生密鑰對在計算上是容易的發(fā)方A用B公鑰對消息M加密成C在計算上是容易的收方B用自己的私鑰對C解密成M在計算上是容易的

（3）安全條件敵人由B的公鑰求B的私鑰計算上不可行敵人由B的公鑰和C求明文M,計算上不可行（4）保真條件：E(D(M))=M(數(shù)字簽名)注：若滿足①②③，則可保密；若滿足②③④，則可保真(數(shù)字簽名)；若4個條件都滿足，則可同時保密保真2025/8/1324PlainTextmENetworkCipherTextCCipherTextDPlainTextAliceBob:PublicKeyDirectory(公鑰簿)SecretKeySKBPKBBob確保數(shù)據(jù)的秘密性（保密）2025/8/1325PlainTextMENetworkCipherTextCCipherTextDPlainTextAliceAlice:PublicKeyDirectory(公鑰簿)SecretKeySKAPKABob確保數(shù)據(jù)的真實性（保真）ESecretKeySKAE2025/8/1326PlainTextMENetworkCipherTextCCipherTextDAliceBob:PublicKeyDirectory(公鑰簿)SecretKeySKBPKBBob確保數(shù)據(jù)的秘密性和真實性（保密保真）SecretKeySKAEDPlainTextAlice:

PKA2025/8/1327公鑰密碼系統(tǒng)的安全性公鑰密鑰保密、認證系統(tǒng)的的安全性主要取決于構(gòu)造雙鑰算法所依賴的數(shù)學(xué)難題要求加密函數(shù)具有單向性，即求逆的困難性。因此，設(shè)計雙鑰體制的關(guān)鍵是先要尋求一個合適的陷門單向函數(shù)。2025/8/1328單向函數(shù)

單向函數(shù)：一個可逆函數(shù)f：A

B，若它滿足：（1）對所有x

A，易于計算f(x)；（2）對“幾乎所有x

A”由f(x)求x“極為困難”，以至于實際上不可能做到。定義中的“易于計算”是指函數(shù)值能在其輸入長度的多項式時間內(nèi)求出，即若輸入長度為n，計算函數(shù)的時間是na的倍數(shù)，a為一固定的常數(shù)。若計算函數(shù)時間是an的倍數(shù)，則為不可能做到的。補充：2025/8/1329陷門單向函數(shù)陷門單向函數(shù)：單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù)，是在不知陷門信息下求逆困難的函數(shù)，當知道陷門信息后，求逆是易于實現(xiàn)的。這是Diffie和Hellmam[1976]引入的概念。如何給陷門單向函數(shù)下定義則很棘手，因為

(1)陷門函數(shù)其實就不是單向函數(shù)，因為單向函數(shù)是在任何條件下求逆都是困難的；(2)陷門可能不止一個，通過試驗,一個個陷門就可容易地找到逆。如果陷門信息的保密性不強，求逆也就不難。2025/8/1330注：1*.僅滿足(1)、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性，δ稱為陷門信息。

2*.當用陷門函數(shù)f作為加密函數(shù)時，可將f公開，這相當于公開加密密鑰。此時加密密鑰便稱為公開密鑰，記為PK。f函數(shù)的設(shè)計者將δ保密，用作解密密鑰，此時δ稱為秘密密鑰，記為SK。由于加密函數(shù)是公開的，任何人都可以將信息x加密成y=f(x)，然后送給函數(shù)的設(shè)計者（當然可以通過不安全信道傳送）；由于設(shè)計者擁有SK，他自然可以解出x=f-1(y)。3*.單向陷門函數(shù)的第(2)條性質(zhì)表明竊聽者由截獲的密文y=f(x)推測x是不可行的。滿足下列條件的函數(shù)f：(1)給定x，計算y=f(x)是容易的(2)給定y,計算x使y=f(x)是困難的(3)存在δ，已知δ時,對給定的任何y，若相應(yīng)的x存在，則計算x使y=f(x)是容易的單向函數(shù)和陷門單向函數(shù)的比較2025/8/1331已經(jīng)出現(xiàn)的并且仍然具有較高安全性的公開密鑰密碼體制所基于的困難問題有：1、大整數(shù)分解問題；2、ZP上的離散對數(shù)問題；3、橢圓曲線上的離散對數(shù)問題；4、線性編碼的解碼問題；5、構(gòu)造非線性弱可逆有限自動機的弱逆問題（基于有限自動機的公開密鑰密碼體制，它是我國學(xué)者陶仁驥等提出的一種公開密鑰密碼體制）公開密鑰密碼體制所基于的困難問題2025/8/13325.1.3非對稱密碼體制的分類

經(jīng)過三十余年的研究和應(yīng)用，非對稱密碼體制的研究取得了很大的進展，研究者們創(chuàng)建了多種不同的密碼算法。通常，對非對稱密碼體制的分類，是根據(jù)其所基于的數(shù)學(xué)基礎(chǔ)的不同，主要分成如下幾類：（1）基于大數(shù)分解難題的，包括