現(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.被動(dòng)攻擊被動(dòng)攻擊即竊聽(tīng)，是對(duì)系統(tǒng)的保密性進(jìn)行攻擊，如搭線竊聽(tīng)、對(duì)文件或程序的非法拷貝等，以獲取他人的信息。被動(dòng)攻擊又分為兩類，一類是獲取消息的內(nèi)容，很容易理解；第二類是進(jìn)行業(yè)務(wù)流分

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

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

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

5、的應(yīng)用程序或系統(tǒng)程序；后者是能被操作系統(tǒng)調(diào)度和運(yùn)行的獨(dú)立程序。,圖1.2 惡意程序分類,對(duì)惡意軟件也可根據(jù)其能否自我復(fù)制來(lái)進(jìn)行分類。不能自我復(fù)制的一般是程序段，這種程序段在主程序被調(diào)用執(zhí)行時(shí)就可激活。能夠自我復(fù)制的或者是程序段（病毒）或者是獨(dú)立的程序（蠕蟲、細(xì)菌等），當(dāng)這種程序段或獨(dú)立的程序被執(zhí)行時(shí)，可能復(fù)制一個(gè)或多個(gè)自己的副本，以后這些副本可在這一系統(tǒng)或其他系統(tǒng)中被激活。以上僅是大致分類，因?yàn)檫壿嬚◤椈蛱芈逡聊抉R可能是病毒或蠕蟲的一部

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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