現(xiàn)代密碼學(xué)第1章

1、現(xiàn)代密碼學(xué),高等院校信息安全專業(yè)系列教材,楊波 主編,第1章 引言,1.1 信息安全面臨的威脅1.2 信息安全的模型1.3 密碼學(xué)基本概念,1.1 信息的安全威脅 1.1.1 安全威脅,自然威脅人為威脅,圖1.1 攻擊類型分類,1.被動攻擊被動攻擊即竊聽，是對系統(tǒng)的保密性進行攻擊，如搭線竊聽、對文件或程序的非法拷貝等，以獲取他人的信息。被動攻擊又分為兩類，一類是獲取消息的內(nèi)容，很容易理解；第二類是進行業(yè)務(wù)流分

2、析，假如我們通過某種手段，比如加密，使得敵手從截獲的消息無法得到消息的真實內(nèi)容，然而敵手卻有可能獲得消息的格式、確定通信雙方的位置和身份以及通信的次數(shù)和消息的長度，這些信息可能對通信雙方來說是敏感的。被動攻擊因不對消息做任何修改，因而是難以檢測的，所以抗擊這種攻擊的重點在于預(yù)防而非檢測。,2.主動攻擊這種攻擊包括對數(shù)據(jù)流的某些篡改或產(chǎn)生某些假的數(shù)據(jù)流。主動攻擊又可分為以下三個子類：①中斷：是對系統(tǒng)的可用性進行攻擊，如破壞計算機硬

3、件、網(wǎng)絡(luò)或文件管理系統(tǒng)。②篡改：是對系統(tǒng)的完整性進行攻擊，如修改數(shù)據(jù)文件中的數(shù)據(jù)、替換某一程序使其執(zhí)行不同的功能、修改網(wǎng)絡(luò)中傳送的消息內(nèi)容等。③偽造：是對系統(tǒng)的真實性進行攻擊。如在網(wǎng)絡(luò)中插入偽造的消息或在文件中插入偽造的記錄。,絕對防止主動攻擊是十分困難的，因為需要隨時隨地對通信設(shè)備和通信線路進行物理保護，因此抗擊主動攻擊的主要途徑是檢測，以及對此攻擊造成的破壞進行恢復(fù)。,信息安全的人為威脅主要來自用戶（惡意的或無惡意的）和惡意軟件

4、的非法侵入。入侵信息系統(tǒng)的用戶也稱為黑客，黑客可能是某個無惡意的人，其目的僅僅是破譯和進入一個計算機系統(tǒng)；或者是某個心懷不滿的雇員，其目的是對計算機系統(tǒng)實施破壞；也可能是一個犯罪分子，其目的是非法竊取系統(tǒng)資源（如竊取信用卡號或非法資金傳送），對數(shù)據(jù)進行未授權(quán)的修改或破壞計算機系統(tǒng)。,1.1.2 入侵者和病毒,惡意軟件指病毒、蠕蟲等惡意程序，可分為兩類，如圖1.2所示，一類需要主程序，另一類不需要。前者是某個程序中的一段，不能獨立于實際

5、的應(yīng)用程序或系統(tǒng)程序；后者是能被操作系統(tǒng)調(diào)度和運行的獨立程序。,圖1.2 惡意程序分類,對惡意軟件也可根據(jù)其能否自我復(fù)制來進行分類。不能自我復(fù)制的一般是程序段，這種程序段在主程序被調(diào)用執(zhí)行時就可激活。能夠自我復(fù)制的或者是程序段（病毒）或者是獨立的程序（蠕蟲、細菌等），當(dāng)這種程序段或獨立的程序被執(zhí)行時，可能復(fù)制一個或多個自己的副本，以后這些副本可在這一系統(tǒng)或其他系統(tǒng)中被激活。以上僅是大致分類，因為邏輯炸彈或特洛伊木馬可能是病毒或蠕蟲的一部

6、分。,安全業(yè)務(wù)指安全防護措施，有以下5種。1. 保密業(yè)務(wù)保護數(shù)據(jù)以防被動攻擊。保護方式可根據(jù)保護范圍的大小分為若干級，其中最高級保護可在一定時間范圍內(nèi)保護兩個用戶之間傳輸?shù)乃袛?shù)據(jù)，低級保護包括對單個消息的保護或?qū)σ粋€消息中某個特定域的保護。保密業(yè)務(wù)還包括對業(yè)務(wù)流實施的保密，防止敵手進行業(yè)務(wù)流分析以獲得通信的信源、信宿、次數(shù)、消息長度和其他信息。,1.1.3 安全業(yè)務(wù),2. 認證業(yè)務(wù)用于保證通信的真實性。在單向通信的情況下，認證

7、業(yè)務(wù)的功能是使接收者相信消息確實是由它自己所聲稱的那個信源發(fā)出的。在雙向通信的情況下，例如計算機終端和主機的連接，在連接開始時，認證服務(wù)則使通信雙方都相信對方是真實的（即的確是它所聲稱的實體）；其次，認證業(yè)務(wù)還保證通信雙方的通信連接不能被第三方介入，以假冒其中的一方而進行非授權(quán)的傳輸或接收。,3. 完整性業(yè)務(wù)和保密業(yè)務(wù)一樣，完整性業(yè)務(wù)也能應(yīng)用于消息流、單個消息或一個消息的某一選定域。用于消息流的完整性業(yè)務(wù)目的在于保證所接收的消息未經(jīng)復(fù)

8、制、插入、篡改、重排或重放，即保證接收的消息和所發(fā)出的消息完全一樣；這種服務(wù)還能對已毀壞的數(shù)據(jù)進行恢復(fù)，所以這種業(yè)務(wù)主要是針對對消息流的篡改和業(yè)務(wù)拒絕的。應(yīng)用于單個消息或一個消息某一選定域的完整性業(yè)務(wù)僅用來防止對消息的篡改。,4. 不可否認業(yè)務(wù)用于防止通信雙方中的某一方對所傳輸消息的否認，因此，一個消息發(fā)出后，接收者能夠證明這一消息的確是由通信的另一方發(fā)出的。類似地，當(dāng)一個消息被接收后，發(fā)出者能夠證明這一消息的確已被通信的另一方接收了

9、。,5. 訪問控制訪問控制的目標(biāo)是防止對網(wǎng)絡(luò)資源的非授權(quán)訪問，控制的實現(xiàn)方式是認證，即檢查欲訪問某一資源的用戶是否具有訪問權(quán)。,信息安全的基本模型可以用圖1.3來表示。,1.2 信息安全的模型,圖1.3 信息安全的基本模型,通信雙方欲傳遞某個消息，需通過以下方式建立一個邏輯上的信息通道： 首先在網(wǎng)絡(luò)中定義從發(fā)送方到接收方的一個路由，然后在該路由上共同執(zhí)行通信協(xié)議。如果需要保護所傳信息以防敵手對其保密性、認證性等構(gòu)成的威脅，則需要考

10、慮通信的安全性。安全傳輸技術(shù)有以下兩個基本成分：,① 消息的安全傳輸， 包括對消息的加密和認證。加密的目的是將消息搞亂以使敵手無法讀懂，認證的目的是檢查發(fā)送者的身份。② 通信雙方共享的某些秘密信息，如加密密鑰。為獲得消息的安全傳輸，可能還需要一個可信的第三方，其作用可能是負責(zé)向通信雙方發(fā)布秘密信息或者在通信雙方有爭議時進行仲裁。,安全的網(wǎng)絡(luò)通信必須考慮以下4個方面： ① 加密算法。② 用于加密算法的秘密信息。③ 秘密信息的分布

11、和共享。④ 使用加密算法和秘密信息以獲得安全服務(wù)所需的協(xié)議。,以上考慮的是信息安全的一般模型，然而還有其他一些情況。圖1.4表示保護信息系統(tǒng)以防未授權(quán)訪問的一個模型。,圖1.4 信息系統(tǒng)的保護模型,對付未授權(quán)訪問的安全機制可分為兩道防線： 第一道稱為守衛(wèi)者，它包括基于通行字的登錄程序和屏蔽邏輯程序，分別用于拒絕非授權(quán)用戶的訪問、檢測和拒絕病毒；第二道防線由一些內(nèi)部控制部件構(gòu)成，用于管理系統(tǒng)內(nèi)部的各項操作和分析所存有的信息，以檢查是否有

12、未授權(quán)的入侵者。,上面介紹了信息安全面臨的威脅以及信息安全的一般模型。信息安全可分為系統(tǒng)安全（包括操作系統(tǒng)安全、數(shù)據(jù)庫系統(tǒng)安全等）、數(shù)據(jù)安全（包括數(shù)據(jù)的安全存儲、安全傳輸）和內(nèi)容安全（包括病毒的防護、不良內(nèi)容的過濾等）3個層次，是一個綜合、交叉的學(xué)科領(lǐng)域，要利用數(shù)學(xué)、電子、信息、通信、計算機等諸多學(xué)科的長期知識積累和最新發(fā)展成果。信息安全研究的內(nèi)容很多，它涉及安全體系結(jié)構(gòu)、安全協(xié)議、密碼理論、信息分析、安全監(jiān)控、應(yīng)急處理等，其中密碼技術(shù)

13、是保障數(shù)據(jù)安全的關(guān)鍵技術(shù)。,通信雙方采用保密通信系統(tǒng)可以隱蔽和保護需要發(fā)送的消息，使未授權(quán)者不能提取信息。發(fā)送方將要發(fā)送的消息稱為明文，明文被變換成看似無意義的隨機消息，稱為密文，這種變換過程稱為加密；其逆過程，即由密文恢復(fù)出原明文的過程稱為解密。對明文進行加密操作的人員稱為加密員或密碼員。密碼員對明文進行加密時所采用的一組規(guī)則稱為加密算法。,1.3 密碼學(xué)基本概念 1.3.1 保密通信系統(tǒng),傳送消息的預(yù)定對象稱為接收者，接收者對

14、密文進行解密時所采用的一組規(guī)則稱為解密算法。加密和解密算法的操作通常都是在一組密鑰控制下進行的，分別稱為加密密鑰和解密密鑰。傳統(tǒng)密碼體制所用的加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個易于得出另一個，稱其為單鑰或?qū)ΨQ密碼體制。若加密密鑰和解密密鑰不相同，從一個難于推出另一個，則稱為雙鑰或非對稱密碼體制。密鑰是密碼體制安全保密的關(guān)鍵，它的產(chǎn)生和管理是密碼學(xué)中的重要研究課題。,在信息傳輸和處理系統(tǒng)中，除了預(yù)定的接收者外，還有非授權(quán)者，他

15、們通過各種辦法（如搭線竊聽、電磁竊聽、聲音竊聽等）來竊取機密信息，稱其為截收者。截收者雖然不知道系統(tǒng)所用的密鑰，但通過分析可能從截獲的密文推斷出原來的明文或密鑰，這一過程稱為密碼分析，從事這一工作的人稱為密碼分析員，研究如何從密文推演出明文、密鑰或解密算法的學(xué)問稱為密碼分析學(xué)。對一個保密通信系統(tǒng)采取截獲密文進行分析的這類攻擊稱為被動攻擊?，F(xiàn)代信息系統(tǒng)還可能遭受的另一類攻擊是主動攻擊，非法入侵者、攻擊者或黑客主動向系統(tǒng)竄擾，采用刪除、增添

16、、重放、偽造等竄改手段向系統(tǒng)注入假消息，達到利己害人的目的。這是現(xiàn)代信息系統(tǒng)中更為棘手的問題。,保密通信系統(tǒng)可用圖1.5表示，它由以下幾部分組成： 明文消息空間M，密文消息空間C，密鑰空間K1和K2，在單鑰體制下K1=K2=K，此時密鑰K需經(jīng)安全的密鑰信道由發(fā)送方傳給接收方；加密變換Ek1：M→C，其中k1∈K1，由加密器完成；解密變換Dk2：C→M，其中k2∈K2，由解密器實現(xiàn)。稱總體(M,C,K1,K2,EK1,DK2)為保密通信系

17、統(tǒng)。對于給定明文消息m∈M，密鑰k1∈K1，加密變換將明文m變換為密文c，即c=f(m,k1)=Ek1(m)m∈M,k1∈K1,接收方利用通過安全信道送來的密鑰k（k∈K，單鑰體制下）或用本地密鑰發(fā)生器產(chǎn)生的解密密鑰k2（k2∈K2，雙鑰體制下）控制解密操作D，對收到的密文進行變換得到恢復(fù)的明文消息，即：m=Dk2(c)m∈M,k2∈K2而密碼分析者，則用其選定的變換函數(shù)h，對截獲的密文c進行變換，得到的明文是明文空間中的某

18、個元素,即m′=h(c)一般m′≠m。如果m′=m，則分析成功。,圖1.5 保密通信系統(tǒng)模型,為了保護信息的保密性，抗擊密碼分析，保密系統(tǒng)應(yīng)當(dāng)滿足下述要求： ① 系統(tǒng)即使達不到理論上是不可破的，即pr{m′=m}=0，也應(yīng)當(dāng)為實際上不可破的。就是說，從截獲的密文或某些已知的明文密文對，要決定密鑰或任意明文在計算上是不可行的。② 系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。③ 加密

19、和解密算法適用于所有密鑰空間中的元素。④ 系統(tǒng)便于實現(xiàn)和使用。,1.3.2 密碼技術(shù)的發(fā)展歷史,第一階段（1949年前）古典密碼發(fā)展階段 1、隱寫術(shù)，暗語、隱語、藏頭詩等 2、采用手工或機械變換的方式實現(xiàn) 單表代換密碼：Caesar密碼、仿射密碼 多表代換密碼：Vigenere、Hill密碼等 轉(zhuǎn)輪密碼：Enigma、Red密碼等,第二階段

20、：近代密碼學(xué)階段（1949~1976) 1、1949年，Shannon發(fā)表了《保密系統(tǒng)的通信理論》，用信息論的觀點分析了密碼學(xué)的基本原理，奠定了密碼學(xué)的理論基礎(chǔ)。 2、1967年David Kahn出版了《破譯者》一書。,現(xiàn)代密碼學(xué)階段(1976~至今）1、1976年，Diffie、Hellman發(fā)表《密碼學(xué)新方向》，開辟了公鑰密碼學(xué)的新領(lǐng)域；2、1976年，美國建立DES為聯(lián)邦標(biāo)準(zhǔn),現(xiàn)代密碼學(xué)的主要發(fā)展方向

21、 1、混沌密碼學(xué) 2、量子密碼學(xué) 3、橢圓曲線密碼學(xué),密碼體制從原理上可分為兩大類，即單鑰體制和雙鑰體制。,1.3.3 密碼體制分類,單鑰體制的加密密鑰和解密密鑰相同。采用單鑰體制的系統(tǒng)的保密性主要取決于密鑰的保密性，與算法的保密性無關(guān)，即由密文和加解密算法不可能得到明文。換句話說，算法無需保密，需保密的僅是密鑰。根據(jù)單鑰密碼體制的這種特性，單鑰加解密算法可通過低費用的芯片來實現(xiàn)。密鑰可由發(fā)送方產(chǎn)生然后再經(jīng)一個

22、安全可靠的途徑（如信使遞送）送至接收方，或由第三方產(chǎn)生后安全可靠地分配給通信雙方。如何產(chǎn)生滿足保密要求的密鑰以及如何將密鑰安全可靠地分配給通信雙方是這類體制設(shè)計和實現(xiàn)的主要課題。密鑰產(chǎn)生、分配、存儲、銷毀等問題，統(tǒng)稱為密鑰管理。這是影響系統(tǒng)安全的關(guān)鍵因素，即使密碼算法再好，若密鑰管理問題處理不好，就很難保證系統(tǒng)的安全保密。,單鑰體制對明文消息的加密有兩種方式： 一是明文消息按字符（如二元數(shù)字）逐位地加密，稱之為流密碼；另一種是將明文消息

23、分組（含有多個字符），逐組地進行加密，稱之為分組密碼。單鑰體制不僅可用于數(shù)據(jù)加密，也可用于消息的認證。,雙鑰體制是由Diffie和Hellman于1976年首先引入的。采用雙鑰體制的每個用戶都有一對選定的密鑰：一個是可以公開的，可以像電話號碼一樣進行注冊公布；另一個則是秘密的。因此雙鑰體制又稱為公鑰體制。雙鑰密碼體制的主要特點是將加密和解密能力分開，因而可以實現(xiàn)多個用戶加密的消息只能由一個用戶解讀，或由一個用戶加密的消息而使多個用戶可

24、以解讀。前者可用于公共網(wǎng)絡(luò)中實現(xiàn)保密通信，而后者可用于實現(xiàn)對用戶的認證。詳細介紹在第3章。,表1.1是攻擊者對密碼系統(tǒng)的4種攻擊類型，類型的劃分由攻擊者可獲取的信息量決定。其中，最困難的攻擊類型是惟密文攻擊，這種攻擊的手段一般是窮搜索法，即對截獲的密文依次用所有可能的密鑰試譯，直到得到有意義的明文。只要有足夠多的計算時間和存儲容量，原則上窮搜索法總是可以成功的。但實際中，任何一種能保障安全要求的實用密碼都會設(shè)計得使這一方法在實際上是不可

25、行的。敵手因此還需對密文進行統(tǒng)計測試分析，為此需要知道被加密的明文的類型，比如英文文本、法文文本、MD-DOS執(zhí)行文件、Java源列表等。（見9頁表1.1）,1.3.4 密碼攻擊概述,惟密文攻擊時，敵手知道的信息量最少，因此最易抵抗。然而，很多情況下，敵手可能有更多的信息，也許能截獲一個或多個明文及其對應(yīng)的密文，也許知道消息中將出現(xiàn)的某種明文格式。例如JPG格式文件開始位置的兩字節(jié)總為“FFD8”，電子資金傳送消息總有一個標(biāo)準(zhǔn)的報頭或

26、標(biāo)題。這時的攻擊稱為已知明文攻擊，敵手也許能夠從已知的明文被變換成密文的方式得到密鑰。,與已知明文攻擊密切相關(guān)的一種攻擊法稱為可能字攻擊。例如對一篇散文加密，敵手可能對消息含義知之甚少。然而，如果對非常特別的信息加密，敵手也許能知道消息中的某一部分。例如，發(fā)送一個加密的賬目文件，敵手可能知道某些關(guān)鍵字在文件報頭的位置。又如，一個公司開發(fā)的程序的源代碼中，可能在某個標(biāo)準(zhǔn)位置上有該公司的版權(quán)聲明。,如果攻擊者能在加密系統(tǒng)中插入自己選擇的明文

27、消息，則通過該明文消息對應(yīng)的密文，有可能確定出密鑰的結(jié)構(gòu)，這種攻擊稱為選擇明文攻擊。選擇密文攻擊是指攻擊者利用解密算法，對自己所選的密文解密出相應(yīng)的明文。,還有兩個概念值得注意。第一，一個加密算法是無條件安全的，如果算法產(chǎn)生的密文不能給出惟一決定相應(yīng)明文的足夠信息。此時無論敵手截獲多少密文、花費多少時間，都不能解密密文。第二，Shannon指出，僅當(dāng)密鑰至少和明文一樣長時，才能達到無條件安全。也就是說除了一次一密方案外，再無其他加密方

28、案是無條件安全的。因此，加密算法只要滿足以下兩條準(zhǔn)則之一就行： ① 破譯密文的代價超過被加密信息的價值。② 破譯密文所花的時間超過信息的有用期。滿足以上兩個準(zhǔn)則的加密算法稱為計算上安全的。,1.3.5 計算復(fù)雜性理論,計算復(fù)雜性理論分析問題的有效解法，提供求解問題所需的運算次數(shù)。從而給出問題求解困難性的數(shù)據(jù)指標(biāo)。加密、解密算法設(shè)計中，經(jīng)常需要考慮算法的效率問題；而在密碼分析中，破譯一個算法所付出的代價（時間、存儲容量）也通常是

29、以運算次數(shù)為依據(jù)的。因此，運算量是密碼體制安全性的生命指標(biāo)。,計算復(fù)雜度的表示方法： 如果用n表示問題的大小，則計算復(fù)雜度可用兩個參數(shù)來表示，記為： T（n）； S（n）； 這種方法的最大優(yōu)點是獨立于所用的系統(tǒng)并且使人們看到時間和空間的需求隨輸入的規(guī)模n而增長。,若T（n）＝

30、O（nc）（c>0），則稱該算法的時間是多項式的；若T（n）＝O（ap（n)) (a>0），其中p（n）是一個多項式，則稱算法時間是指數(shù)階的。對于指數(shù)階的算法，適當(dāng)增大n，計算將變成不可能的。,n＝106,,,,,,,,確定性算法：確定性算法的每一步的操作結(jié)果都是確定的，其計算時間就是完成這些步驟所需的時間； 非確定性算法：非確定性算法的某些操作結(jié)果是不確定的，使算法成功完成的操作序列中，所需時間最少的序列就是該非不確定

31、算法的計算時間,P問題：用確定性算法可以在多項式時間內(nèi)求解的問題； NP問題：在多項式時間內(nèi)可以用非確定性算法求解的問題顯然：但不能確定：,,,,,,NP完全問題： 如果某類NP問題中的任何一個問題都可以歸約為問題L，且L本身也是NP問題，則稱L是一個NP完全問題，稱為NPC問題 NP問題在密碼學(xué)中的應(yīng)用：對于一個NP問題，若能找到一個計算序列，作為解密算法，那么密碼分析者在不知道計算序列的情形下求解問題（稱為客觀求解）成為