第3章 密碼技術(shù)概述

復(fù)習(xí)與回顧信息安全涉及范疇、安全屬性需求以及信息安全保障體系結(jié)構(gòu)動(dòng)態(tài)和可適應(yīng)的信息安全防御模型風(fēng)險(xiǎn)評估、等級保護(hù)、安全測評的內(nèi)容與方法2024/3/202第3章密碼技術(shù)概述2024/3/203學(xué)習(xí)目標(biāo)數(shù)據(jù)保密通信模型及基本術(shù)語對稱密碼體制及其分類與工作原理公鑰密碼體制及其工作原理數(shù)字簽名技術(shù)及其特性消息完整性保護(hù)及認(rèn)證如何定義和衡量密碼體制的安全性本章介紹密碼技術(shù)的基本概念、分類、實(shí)現(xiàn)和應(yīng)用原理。內(nèi)容包括：2024/3/2043.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析目錄2024/3/205什么是密碼術(shù)？Cryptography?3.1密碼術(shù)及發(fā)展2024/3/2063.1密碼術(shù)及發(fā)展保密性要求即使非授權(quán)者獲取了數(shù)據(jù)副本，他也無法從副本中獲得有用的信息。

2024/3/2073.1密碼術(shù)及發(fā)展古典密碼北宋曾公亮、丁度等編撰《武經(jīng)總要》“字驗(yàn)”；公元前405年，斯巴達(dá)將領(lǐng)來山得使用了原始的錯(cuò)亂密碼；公元前一世紀(jì)，古羅馬皇帝凱撒曾使用有序單表代替密碼；古典密碼使用的基本方法置換加密法：將字母的順序重新排列。替換加密法：將一組字母用其它字母或符號代替。古典密碼原理簡單，容易遭受統(tǒng)計(jì)分析攻擊。2024/3/2083.1密碼術(shù)及發(fā)展現(xiàn)代密碼1863年普魯士人卡西斯基著《密碼和破譯技術(shù)》,

1883年法國人克爾克霍夫所著《軍事密碼學(xué)》；20世紀(jì)初，產(chǎn)生了最初的可以實(shí)用的機(jī)械式和電動(dòng)式密碼機(jī)，同時(shí)出現(xiàn)了商業(yè)密碼機(jī)公司和市場；第二次世界大戰(zhàn)德國的Enigma轉(zhuǎn)輪密碼機(jī)，堪稱機(jī)械式古典密碼的巔峰之作。1949年美國人香農(nóng)(C.Shannon)發(fā)表論文《保密系統(tǒng)的通信理論》標(biāo)志現(xiàn)代密碼學(xué)的誕生。2024/3/2093.1密碼術(shù)及發(fā)展密碼學(xué)已經(jīng)發(fā)展成一門跨學(xué)科的學(xué)問，它以信息理論為基礎(chǔ)，同時(shí)使用大量數(shù)學(xué)和其它領(lǐng)域的工具，而計(jì)算機(jī)技術(shù)和計(jì)算理論又支撐和推動(dòng)了現(xiàn)代密碼學(xué)的應(yīng)用和發(fā)展。密碼學(xué)包括密碼編碼學(xué)和密碼分析學(xué)兩大分支。密碼編碼學(xué)研究如何對信息進(jìn)行加解密。密碼分析學(xué)研究如何在不知道密鑰的情況對密碼進(jìn)行破譯。2024/3/20103.1密碼術(shù)及發(fā)展現(xiàn)代密碼學(xué)發(fā)展過程中的重大事件1976年，美國政府頒布數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）。1976年，Diffie和Hellman發(fā)表論文《密碼學(xué)的新動(dòng)向》，開創(chuàng)了公鑰密碼的新思想。1978年，Rivest，Shamir和Adleman實(shí)現(xiàn)了RSA公鑰密碼體制。1969年，哥倫比亞大學(xué)的StephenWiesner首次提出“共軛編碼”概念。1984年Bennett和Brassard在此思想啟發(fā)下，提出量子理論BB84協(xié)議。2024/3/20113.1密碼術(shù)及發(fā)展現(xiàn)代密碼學(xué)發(fā)展過程中的重大事件1985年，Miller和Koblitz首次將有限域上的橢圓曲線用到了公鑰密碼系統(tǒng)中。1989年，Mathews,Wheeler,Pecora和Carroll等人首次把混沌理論使用到序列密碼及保密通信理論。2001年，NIST發(fā)布高級加密標(biāo)準(zhǔn)AES，替代DES作為商用密碼標(biāo)準(zhǔn)。2024/3/20123.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析目錄2024/3/20133.2數(shù)據(jù)保密通信模型如何在開放網(wǎng)絡(luò)中保密傳輸數(shù)據(jù)？SecretTransmission?2024/3/20143.2數(shù)據(jù)保密通信模型2024/3/20153.2數(shù)據(jù)保密通信模型保密通信系統(tǒng)相關(guān)術(shù)語明文(Plaintext)：需要安全保護(hù)的原始信息/數(shù)據(jù)，常記為m。所有明文構(gòu)成明文空間，常記為M。密文(Ciphertext)：原始數(shù)據(jù)經(jīng)加密變換得到的數(shù)據(jù)，常記為c。所有密文構(gòu)成密文空間，常記為C。加密(Encryption)：c＝Ek1(m)解密(Decryption)：m＝Dk2(c)。密鑰(Key)：用于加解密的秘密信息。所有密鑰構(gòu)成密鑰空間，常記為K。公眾信道：數(shù)據(jù)公開傳遞的信道，也稱公共信道。秘密信道：代指安全信道，用于傳遞密鑰。2024/3/20163.2數(shù)據(jù)保密通信模型密碼體制(CipherSystem)對于m∈M，k1,k2∈K，有

，五元組（M,C,K,E,D）稱為一個(gè)密碼體制，其中E和D代表具體的密碼算法——具體的變換過程或數(shù)學(xué)方法?？梢钥闯?，加密可以看做是將密鑰與明文混合變換的過程，而解密是從密文中剝離密鑰的過程，因此也稱脫密過程。Kerchhoff假設(shè)一個(gè)密碼體制，對于所有密鑰，加密和解密算法迅速有效；密碼體制的安全性不應(yīng)該依賴于算法的保密，而僅依賴密鑰的保密。2024/3/20173.2數(shù)據(jù)保密通信模型密碼技術(shù)、密碼體制與密碼算法密碼技術(shù)是利用密碼體制實(shí)現(xiàn)信息安全保護(hù)的技術(shù)；密碼體制是使用特定密碼算法實(shí)現(xiàn)信息安全保護(hù)的具體方法；密碼算法是使用密鑰實(shí)現(xiàn)數(shù)據(jù)加解密變換的數(shù)學(xué)處理過程密碼體制分類（根據(jù)密鑰情況分類）對稱密鑰密碼體制：加密與解密使用相同密鑰(單鑰)公鑰密碼體制：加密與解密使用不同密鑰(雙鑰)2024/3/20183.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析目錄2024/3/20193.3對稱密碼體制如何使用相同的密鑰加/解密數(shù)據(jù)？SymmetricCryptography?2024/3/20203.3對稱密碼體制對稱密碼體制加密密鑰與解密密鑰存在明顯的依賴關(guān)系，由其中一個(gè)可以很容易推導(dǎo)出另一個(gè)。實(shí)踐中，對稱密碼體制多使用同一個(gè)密鑰加密和解密，稱為加解密雙方共享密鑰。對稱密碼體制也稱為單鑰密碼體制。2024/3/20213.3對稱密碼體制對稱密碼體制2024/3/20223.3對稱密碼體制對稱密碼體制分類分組密碼(Blockcipher)先將明文劃分成若干等長的塊——分組，如每個(gè)分組長64比特、128比特，然后再分別對每個(gè)分組進(jìn)行加密，得到等長的密文分組；解密過程也類似。有些密碼體制解密算法與加密算法完全一樣，如DES。序列密碼(Sequentialcipher)是把明文以位或字節(jié)為單位進(jìn)行加密，一般是與密鑰（由密鑰種子產(chǎn)生的任意長度的字節(jié)流）進(jìn)行混合（如異或）獲得密文序列。也稱流密碼(Streamcipher)。2024/3/20233.3對稱密碼體制分組密碼設(shè)計(jì)的兩個(gè)思想擴(kuò)散（Diffusion）：即將明文及密鑰的影響盡可能迅速地散布到較多的輸出密文中，典型操作就是“置換”（Permutation）（如重排字符順序）?；煜–onfusion）：目的在于使作用于明文的密鑰和密文之間的關(guān)系復(fù)雜化，使得明文和密文、密文和密鑰之間的統(tǒng)計(jì)相關(guān)性極小化，從而使統(tǒng)計(jì)分析攻擊不能奏效。混淆通常采用“代換”（Substitution）操作。2024/3/20243.3對稱密碼體制Feistel網(wǎng)絡(luò)結(jié)構(gòu)分組密碼一般采用多次相同的迭代操作（輪操作），實(shí)現(xiàn)明文與密鑰充分地混淆和擴(kuò)散。許多分組密碼體制采用了Feistel網(wǎng)絡(luò)結(jié)構(gòu)。Feistel結(jié)構(gòu)保證了無論輪函數(shù)F是一個(gè)如何復(fù)雜的變換過程，都不影響加密與解密過程的一致性，實(shí)現(xiàn)加密過程的可逆性。F具有良好的非線性性，增加密碼分析的難度。分組密碼通過多輪處理增加了混淆效果，每一輪使用不同的輪密鑰（由初始密鑰擴(kuò)展得到）。2024/3/2025Feistel網(wǎng)絡(luò)結(jié)構(gòu)3.3對稱密碼體制2024/3/20263.3對稱密碼體制序列密碼(流密碼)將明文流和密鑰流混合(一般為簡單的按字節(jié)或比特位異或)產(chǎn)生密文流。流密碼使用一個(gè)“種子密鑰”產(chǎn)生密鑰流(理論上可以無限長度)，通信雙方共享這個(gè)“種子密鑰”，按相同方式產(chǎn)生密鑰流。2024/3/20273.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析目錄2024/3/20283.4公鑰密碼體制如何方便地管理和使用密鑰？AsymmetricCryptography?2024/3/20293.4公鑰密碼體制公鑰密碼體制有兩個(gè)完全不同的密鑰，而且其中一個(gè)可以公開（常用于加密），另一個(gè)需要保密（常用于解密）。因此，也稱為雙鑰密碼體制。公鑰密碼就是一種陷門單向函數(shù)f。即：對f定義域中的任意x都易于計(jì)算f(x)，而對f值域中幾乎所有的y，即使f為已知時(shí)要計(jì)算f-1(y)在計(jì)算上也是不可行的。當(dāng)給定某些輔助信息（陷門）時(shí)則易于計(jì)算f-1(y)。此時(shí)稱f是一個(gè)陷門單向函數(shù)，輔助信息（陷門信息）作為秘密密鑰。2024/3/20303.4公鑰密碼體制公鑰加密體制2024/3/20313.4公鑰密碼體制公鑰密碼體制一般要借助某個(gè)特殊的數(shù)學(xué)問題，如數(shù)論中的大數(shù)分解、離散對數(shù)等數(shù)學(xué)難解問題，構(gòu)造單向函數(shù)，因此，這類密碼的安全強(qiáng)度取決于它所依據(jù)的問題的計(jì)算復(fù)雜度。目前的公鑰密碼體制主要有兩類：基于大整數(shù)因子分解問題的公鑰密碼體制，如RSA體制基于離散對數(shù)問題的公鑰密碼體制，如ElGmal密碼體制、橢圓曲線密碼體制。2024/3/20323.4公鑰密碼體制一個(gè)公鑰密碼體制是一個(gè)七元組(M,C,SK,PK,Gen,Enc,Dec)，其中明文空間M(Message消息，或Plaintext)，需要加密的消息表示為m，m∈M。密文空間C(Ciphertext)，明文m經(jīng)過加密變換為密文c，c∈C。私鑰空間SK(SecretKey)與公鑰空間PK(PublicKey)。2024/3/20333.4公鑰密碼體制一個(gè)公鑰密碼體制是一個(gè)七元組(M,C,SK,PK,Gen,Enc,Dec)，其中密鑰生成算法Gen(KeyGenerationAlgorithm)，從私鑰空間中隨機(jī)選取一個(gè)私鑰kpri(PrivateKey)，kpri∈SK，算法Gen輸出私鑰kpri和對應(yīng)的公鑰kpub(PubklicKey)，kpub∈PK。加密算法Enc(EncryptionAlgorithm)，給定明文m，m∈M，輸出密文c，c=Enc(m,

kpub)，c∈C。解密算法Dec(DecryptionAlgorithm)，給定密文c，c∈C，輸出明文m，m=Dec(c,kpri)，m∈M。2024/3/20343.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析目錄2024/3/20353.5數(shù)字簽名如何在電子世界中實(shí)現(xiàn)簽名？Digital

Signature?2024/3/20363.5數(shù)字簽名一個(gè)假想的例子：路人甲要通過網(wǎng)絡(luò)傳輸一份文檔給路人乙，乙接收到這份文檔，乙能確認(rèn)這份文檔的真實(shí)性嗎（確實(shí)來自于甲，而不是其他人冒充甲發(fā)送的）？乙能確定這份文檔的正確性碼（在傳輸過程中沒有被篡改）？甲如果否認(rèn)曾經(jīng)發(fā)送過該文檔（實(shí)際上確實(shí)是甲發(fā)送的）怎么辦？2024/3/20373.5數(shù)字簽名數(shù)字簽名必須使用某些對于簽名者來講具有唯一性的信息，以防止簽名和偽造和否認(rèn)。數(shù)字簽名的生成與驗(yàn)證都必須是相對容易的，而且在出現(xiàn)糾紛時(shí)可以通過可信的第三方TTP仲裁。公鑰密碼技術(shù)為數(shù)字簽名提供了理論依據(jù)：公鑰密碼體制中的私鑰是私有的、保密的，其他人無法獲得，可以作為持有者的唯一性信息，作為持有者身份的唯一性表示。2024/3/20383.5數(shù)字簽名數(shù)字簽名機(jī)制使用公鑰密碼技術(shù)，使得消息接收者相信接收的消息來自聲稱的消息發(fā)送者（消息主體的識(shí)別與鑒別），并信任該消息（消息被正確地傳遞，沒有被篡改——完整性保護(hù)），同時(shí)消息簽名者不能否認(rèn)簽發(fā)了該消息（不可否認(rèn)性保護(hù)）。2024/3/20393.5數(shù)字簽名數(shù)字簽名機(jī)制2024/3/20403.5數(shù)字簽名一個(gè)數(shù)字簽名體制是一個(gè)七元組(M,S,SK,PK,Gen,Sig,Ver)，其中明文空間M(Message消息，或Plantext)，對應(yīng)需要簽名的消息表示為m，m∈M。密文空間S(Signature)，明文m經(jīng)過密碼變換輸出密文s，s∈S。私鑰空間SK(SecretKey)，所有可能的私鑰構(gòu)成。公鑰空間PK(PublicKey)，所有可能的公鑰構(gòu)成。2024/3/20413.5數(shù)字簽名一個(gè)數(shù)字簽名體制是一個(gè)七元組(M,S,SK,PK,Gen,Sig,Ver)，其中密鑰生成算法Gen(KeyGenerationAlgorithm)，從可能的私鑰空間中隨機(jī)選取一個(gè)私鑰kpri(PrivateKey)，kpri∈SK，算法Gen輸出私鑰kpri和對應(yīng)的公鑰kpub(PublicKey)，kpub∈PK。簽名算法Sig(SigningAlgorithm)，給定明文m，m∈M，輸出簽名s，s=Sig(m,kpri)，

s∈S。驗(yàn)證算法Ver(VerifyingAlgorithm)，給定簽名s，s∈S，驗(yàn)證簽名v=Ver(s,kpuk)，輸出正確或錯(cuò)誤的結(jié)果，v∈{True,False}。2024/3/20423.5數(shù)字簽名數(shù)字簽名機(jī)制的工作過程2024/3/20433.5數(shù)字簽名密碼學(xué)哈希(Hash)函數(shù)：密碼學(xué)哈希函數(shù)將任意長度輸入轉(zhuǎn)換為特定長度輸出，典型的算法如MD5、SHA、SHA-256等。一個(gè)密碼學(xué)哈希函數(shù)H應(yīng)具備以下特性單向性：給定一個(gè)輸入m，容易計(jì)算哈希值h=H(m)；但反過來，給定一個(gè)哈希值h，計(jì)算原像m是困難的?？古鲎残裕阂阎粋€(gè)哈希值h=H(m)，找出另一個(gè)m’，使得H(m’)等于h是困難的；同時(shí)任意找到兩個(gè)值c1、c2，使得這兩個(gè)數(shù)的哈希值相同，即H(c1)=H(c2)，是困難的。2024/3/20443.5數(shù)字簽名數(shù)字簽名可以實(shí)現(xiàn)3個(gè)安全屬性鑒別性：實(shí)體和消息的真實(shí)性認(rèn)證完整性不可否認(rèn)性2024/3/20453.5數(shù)字簽名數(shù)字簽名與消息加密組合方案2024/3/20463.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析目錄2024/3/20473.6消息完整性保護(hù)如何保護(hù)通信數(shù)據(jù)的完整性？Digital

Signature?2024/3/20483.6消息完整性保護(hù)消息完整性的含義影響消息完整性的因素偶發(fā)因素人為破壞（惡意攻擊）消息完整性保護(hù)循環(huán)冗余校驗(yàn)碼(CRC:CyclicRedundancyCheck)?數(shù)字簽名?消息認(rèn)證碼(MAC:MessageAuthenticationCode)2024/3/20493.6消息完整性保護(hù)消息認(rèn)證碼MAC——帶密碼的摘要2024/3/20503.6消息完整性保護(hù)IETFRFC2104HMAC:Keyed-HashingforMessageAuthentication帶密鑰的哈希函數(shù)消息認(rèn)證：一種MAC構(gòu)造標(biāo)準(zhǔn)HMAC＝H((KXORopad)||H((KXORipad)||m)消息認(rèn)證碼的安全問題MAC的計(jì)算可以直接使用對稱密碼算法或公鑰密碼算法，MAC的安全性完全依賴于所采用密碼算法的安全性。HMAC通信雙方需要事先共享密鑰K或口令，HMAC的安全性依賴于Hash函數(shù)的安全性。2024/3/20513.6消息完整性保護(hù)一個(gè)基于HMAC的應(yīng)用實(shí)例，使用HMAC完成一個(gè)典型的“質(zhì)詢/響應(yīng)（Challenge/Response）”身份認(rèn)證過程：客戶端向服務(wù)器發(fā)出認(rèn)證請求，如一個(gè)登錄請求（假設(shè)是瀏覽器的GET請求）。服務(wù)器返回一個(gè)質(zhì)詢(Challenge)，一般為一個(gè)隨機(jī)值，并在會(huì)話中記錄這個(gè)隨機(jī)值?？蛻舳藢⒃撾S機(jī)值作為輸入字符串，與用戶口令一起進(jìn)行HMAC運(yùn)算，然后提交計(jì)算結(jié)果給服務(wù)器——響應(yīng)(Response)。服務(wù)器讀取用戶數(shù)據(jù)庫中的用戶口令，并使用步驟2中發(fā)送的隨機(jī)值做與客戶端一樣的HMAC運(yùn)算，然后與用戶返回的響應(yīng)比較，如果結(jié)果一致則驗(yàn)證了用戶是合法的。2024/3/20523.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析目錄2024/3/20533.7認(rèn)證如何驗(yàn)證主體的身份或消息地真實(shí)性？Digital

Signature?2024/3/20543.7認(rèn)證認(rèn)證的含義認(rèn)證也稱鑒別(Authentication)，是證明某種真實(shí)性、合法性、有效性或正確性的過程。也就是驗(yàn)證者(Verifier，一般為接收者)對認(rèn)證者(Authenticator，也稱證明者、示證者，一般為發(fā)送方)聲稱的某種真實(shí)性、合法性、有效性或正確性的確認(rèn)方法和過程。認(rèn)證的對象包括兩類實(shí)體身份的真實(shí)性消息的真實(shí)性2024/3/20553.7認(rèn)證實(shí)體身份真實(shí)性認(rèn)證實(shí)體包括人和設(shè)備，即回答“是某人嗎？”、“是某臺(tái)設(shè)備嗎？”、“是某個(gè)軟件嗎？”。對實(shí)體認(rèn)證的目的往往是為了決定將什么樣的特權(quán)(Privilege)授權(quán)(Authorizing)給該實(shí)體。消息真實(shí)性認(rèn)證消息自身（來源、內(nèi)容）的認(rèn)證，即回答“這個(gè)消息真實(shí)嗎？”、“這個(gè)消息正確嗎？”，確認(rèn)這個(gè)消息是合法用戶生成的且在傳遞過程中沒有被篡改。消息的順序性和時(shí)間性認(rèn)證。2024/3/20563.7認(rèn)證認(rèn)證機(jī)制與技術(shù)認(rèn)證機(jī)制知道的東西：口令、密鑰擁有的東西：生物特征、令牌認(rèn)證技術(shù)數(shù)字簽名消息認(rèn)證碼認(rèn)證與完整性保護(hù)使用許多共同的技術(shù)和方法，但安全目標(biāo)不一樣。2024/3/20573.7認(rèn)證零知識(shí)證明：一種有趣的“魔咒”認(rèn)證方法洞穴問題：如圖有一個(gè)洞穴，在洞穴深處C點(diǎn)與D點(diǎn)間有一道門，設(shè)P知道打開該門的咒語，其他人不知道咒語無法打開此門。那么現(xiàn)在P如何向驗(yàn)證者V證明他知道咒語但又不告訴V咒語是什么呢？2024/3/20583.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析目錄2024/3/20593.8計(jì)算復(fù)雜理論如何定義一個(gè)密碼系統(tǒng)是安全的？Digital

Signature?2024/3/20603.8計(jì)算復(fù)雜理論1.安全的定義只有相對的安全，沒有絕對的安全。安全的意義在于保護(hù)信息安全所需的代價(jià)與信息本身價(jià)值的對比，因此信息安全保護(hù)是一種效能的折衷。安全的三個(gè)層次理論安全性（也稱無條件安全）：如果具有無限計(jì)算資源的密碼分析者也無法破譯一個(gè)密碼系統(tǒng)則稱該密碼系統(tǒng)是理論安全的。2024/3/20613.8計(jì)算復(fù)雜理論1.安全的定義安全的三個(gè)層次可證明安全性：如果從理論上可以證明破譯一個(gè)密碼系統(tǒng)的代價(jià)/困難性不低于求解某個(gè)已知的數(shù)學(xué)難題，則稱該密碼系統(tǒng)是可證安全的。計(jì)算安全性：如果使用已知的最好算法和利用現(xiàn)有的（或密碼系統(tǒng)生命周期內(nèi)）最大的計(jì)算資源仍然不可能在合理的時(shí)間完成破譯一個(gè)密碼系統(tǒng)，則稱該密碼系統(tǒng)是計(jì)算安全的。注：可證明安全性與計(jì)算安全性也稱為實(shí)際安全性。2024/3/20623.8計(jì)算復(fù)雜理論2.安全的度量密碼分析所需的計(jì)算量是密碼體制安全性的衡量指標(biāo)。計(jì)算復(fù)雜度理論用n表示問題的大小或系統(tǒng)輸入的長度，則運(yùn)算所需的時(shí)間T和存儲(chǔ)所需的空間S都是n的函數(shù)，記為T(n)和S(n)，稱為時(shí)間復(fù)雜度和空間復(fù)雜度。

時(shí)間復(fù)雜度與空間復(fù)雜度可以互相轉(zhuǎn)化，即可以“空間”換“時(shí)間”。2024/3/20633.8計(jì)算復(fù)雜理論2.安全的度量計(jì)算復(fù)雜度理論如果T(n)＝O(nc

)，且c>0，則稱該算法的運(yùn)算時(shí)間是多項(xiàng)式階的。一般認(rèn)為多項(xiàng)式階時(shí)間復(fù)雜度是計(jì)算上可行的。如果T(n)＝O(n

p(n))，p(n)是關(guān)于n的一個(gè)多項(xiàng)式，則稱該算法運(yùn)算時(shí)間是指數(shù)階的。一般認(rèn)為指數(shù)階時(shí)間復(fù)雜度是計(jì)算上不可行的。如果破譯一個(gè)密碼體制所需的時(shí)間是指數(shù)階的，則該密碼體制在計(jì)算上是安全的，因而也是實(shí)際安全的。2024/3/20643.8計(jì)算復(fù)雜理論3.計(jì)算理論確定性算法與非確定性算法確定性算法的每一步操作結(jié)果都是確定的，計(jì)算時(shí)間也是確定的。非確定性算法的某些步驟操作結(jié)果是不確定的，在所有使算法成功操作的序列中，運(yùn)行時(shí)間最短的序列所需時(shí)間就是該非確定性算法的計(jì)算時(shí)間。用確定算法可以在多項(xiàng)式時(shí)間內(nèi)求解的問題稱為P問題。多項(xiàng)式時(shí)間內(nèi)可用非確定性算法求解的問題稱為NP問題。P＝NP？或者P≠NP？2024/3/20653.8計(jì)算復(fù)雜理論3.計(jì)算理論如果一個(gè)問題X可以在多項(xiàng)式時(shí)間內(nèi)用確定性算法轉(zhuǎn)化為問題Y，而Y的解可以在多項(xiàng)式時(shí)間內(nèi)用確定性算法轉(zhuǎn)化為X的解，則稱問題X可以規(guī)約化為問題Y。因此，如果某類NP問題中任何一個(gè)問題可以規(guī)約為問題Y，而且Y本身就是NP問題，則稱Y是一個(gè)NP完全問題，記為NPC。如果能夠找到一個(gè)計(jì)算序列作為解密算法，那么密碼分析者在不知道計(jì)算序列的情況下求解問題（稱為客觀求解）在計(jì)算上是不可行的。因此，可以基于NP問題構(gòu)造密碼體制。2024/3/2066目錄3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字簽名3.6消息完整性保護(hù)3.7認(rèn)證3.8計(jì)算復(fù)雜理論3.9密碼分析2024/3/20673.9密碼分析如何攻擊密碼系統(tǒng)？