信息安全原理與技術(shù) 課件全套 郭亞軍 第1-11章 引言、數(shù)學(xué)基礎(chǔ) -惡意代碼

信息安全原理與技術(shù)第3版第1章引言主要知識點(diǎn)：

--安全攻擊

--安全機(jī)制

--安全目標(biāo)與安全需求

--安全服務(wù)模型

--安全目標(biāo)、需求、服務(wù)和機(jī)制之間的關(guān)系

--信息安全模型

--網(wǎng)絡(luò)安全協(xié)議2024/4/5Ch1-引言2安全的本質(zhì)用兵之法：無恃其不來，恃吾有以待也；無恃其不攻，恃吾有所不可攻也。

Theartofwarteachesustorelynotonthelikelihoodoftheenemy'snotcoming,butonourownreadinesstoreceivehim;notonthechanceofhisnotattacking,butratheronthefactthatwehavemadeourpositionunassailable.

—孫子兵法2024/4/5Ch1-引言3“如果把一封信鎖在保險(xiǎn)柜中，把保險(xiǎn)柜藏在紐約的某個(gè)地方，然后告訴你去看這封信，這并不是安全，而是隱藏；相反，如果把一封信鎖在保險(xiǎn)柜中，然后把保險(xiǎn)柜及其設(shè)計(jì)規(guī)范和許多同樣的保險(xiǎn)柜給你，以便你和世界上最好的開保險(xiǎn)柜的專家能夠研究鎖的裝置，而你還是無法打開保險(xiǎn)柜去讀這封信，這才是安全…”-BruceSchneier2024/4/5Ch1-引言4安全攻擊信息在存儲、共享和傳輸中，可能會被非法竊聽、截取、篡改和破壞，這些危及信息系統(tǒng)安全的活動稱為安全攻擊

安全攻擊分為主動攻擊和被動攻擊

被動攻擊的特征是對傳輸進(jìn)行竊聽和監(jiān)測。被動攻擊的目的是獲得傳輸?shù)男畔?，不對信息作任何改動被動攻擊主要威脅信息的保密性

常見的被動攻擊包括消息內(nèi)容的泄漏和流量分析等2024/4/5Ch1-引言5主動攻擊則意在篡改或者偽造信息、也可以是改變系統(tǒng)的狀態(tài)和操作主動攻擊主要威脅信息的完整性、可用性和真實(shí)性常見的主動攻擊包括：偽裝、篡改、重放和拒絕服務(wù)2024/4/5Ch1-引言6常見的安全攻擊消息內(nèi)容的泄漏：消息的內(nèi)容被泄露或透露給某個(gè)非授權(quán)的實(shí)體流量分析（TrafficAnalysis）：通過分析通信雙方的標(biāo)識、通信頻度、消息格式等信息來達(dá)到自己的目的篡改：指對合法用戶之間的通信消息進(jìn)行修改或者改變消息的順序偽裝：指一個(gè)實(shí)體冒充另一個(gè)實(shí)體重放：將獲得的信息再次發(fā)送以期望獲得合法用戶的利益

拒絕服務(wù)（denialofservice）：指阻止對信息或其他資源的合法訪問。2024/4/5Ch1-引言7安全機(jī)制阻止安全攻擊及恢復(fù)系統(tǒng)的機(jī)制稱為安全機(jī)制

OSI安全框架將安全機(jī)制分為特定的安全機(jī)制和普遍的安全機(jī)制一個(gè)特定的安全機(jī)制是在同一時(shí)間只針對一種安全服務(wù)實(shí)施一種技術(shù)或軟件一般安全機(jī)制和特定安全機(jī)制不同的一個(gè)要素是，一般安全機(jī)制不能應(yīng)用到OSI參考模型的任一層上2024/4/5Ch1-引言8特定的安全機(jī)制包括：加密、數(shù)字簽名、訪問控制、數(shù)據(jù)完整性、認(rèn)證交換、流量填充、路由控制和公證普遍的安全機(jī)制包括：可信功能機(jī)制、安全標(biāo)簽機(jī)制、事件檢測機(jī)制、審計(jì)跟蹤機(jī)制、安全恢復(fù)機(jī)制與安全服務(wù)有關(guān)的機(jī)制是加密、數(shù)字簽名、訪問控制、數(shù)據(jù)完整性、認(rèn)證交換、流量填充、路由控制和公證。與管理相關(guān)的機(jī)制是可信功能機(jī)制，安全標(biāo)簽機(jī)制，事件檢測機(jī)制，審計(jì)跟蹤機(jī)制和安全恢復(fù)機(jī)制

2024/4/5Ch1-引言9安全目標(biāo)信息安全的目標(biāo)是指能夠滿足一個(gè)組織或者個(gè)人的所有安全需求通常強(qiáng)調(diào)CIA三元組的目標(biāo)，即保密性(Confidentiality)、完整性(Integrity)和可用性(Availability)由于這些目標(biāo)常常是互相矛盾的，因此需要在這些目標(biāo)中找到一個(gè)合適的平衡點(diǎn)。例如，簡單地阻止所有人訪問一個(gè)資源，就可以實(shí)現(xiàn)該資源的保密性，但這樣做就不滿足可用性。2024/4/5Ch1-引言10安全需求可用性(Availability)：確保授權(quán)的用戶在需要時(shí)可以訪問信息完整性(Integrity)：保護(hù)信息和信息處理方法的準(zhǔn)確性和原始性保密性(Confidentiality)：確保信息只被授權(quán)人訪問可追溯性(Accountability)：確保實(shí)體的行動可被跟蹤保障(Assurance)：是對安全措施信任的基礎(chǔ)，保障是指系統(tǒng)具有足夠的能力保護(hù)無意的錯(cuò)誤以及能夠抵抗故意滲透2024/4/5Ch1-引言11安全需求之間的關(guān)系2024/4/5Ch1-引言12安全需求之間的關(guān)系

保密性依賴于完整性，如果系統(tǒng)沒有完整性，保密性就失去意義同樣完整性也依賴于保密性，如果不能保證保密性，完整性也將不能成立可用性和可追溯性都由保密性和完整性支持上面提到的這些安全需求都依賴于保障2024/4/5Ch1-引言13安全服務(wù)模型安全服務(wù)是加強(qiáng)數(shù)據(jù)處理系統(tǒng)和信息傳輸?shù)陌踩缘囊环N服務(wù)，是指信息系統(tǒng)為其應(yīng)用提供的某些功能或者輔助業(yè)務(wù)安全機(jī)制是安全服務(wù)的基礎(chǔ)安全服務(wù)是利用一種或多種安全機(jī)制阻止安全攻擊，保證系統(tǒng)或者數(shù)據(jù)傳輸有足夠的安全性圖1.3是一個(gè)綜合安全服務(wù)模型，該模型揭示了主要安全服務(wù)和支撐安全服務(wù)之間的關(guān)系模型主要由三個(gè)部分組成：支撐服務(wù)，預(yù)防服務(wù)和恢復(fù)相關(guān)的服務(wù)

2024/4/5Ch1-引言142024/4/5Ch1-引言15支撐服務(wù)是其他服務(wù)的基礎(chǔ)，主要包括：

--鑒別（Identification）：它表示能夠獨(dú)特地識別系統(tǒng)中所有實(shí)體

--密鑰管理：該服務(wù)表示以安全的方式管理密鑰。密鑰常常用于鑒別一個(gè)實(shí)體

--安全性管理（Securityadministration）：系統(tǒng)的所有安全屬性必須進(jìn)行管理。如安裝新的服務(wù)，更新已有的服務(wù)，監(jiān)控以保證所提供的服務(wù)是可操作的

--系統(tǒng)保護(hù)：系統(tǒng)保護(hù)通常表示對技術(shù)執(zhí)行的全面信任2024/4/5Ch1-引言16預(yù)防服務(wù)能夠阻止安全漏洞的發(fā)生，包括：

--受保護(hù)的通信：該服務(wù)是保護(hù)實(shí)體之間的通信

--認(rèn)證（Authentication）：保證通信的實(shí)體是它所聲稱的實(shí)體，也就是驗(yàn)證實(shí)體身份

--授權(quán)（Authorization）：授權(quán)表示允許一個(gè)實(shí)體對一個(gè)給定系統(tǒng)作一些行動，如訪問一個(gè)資源。

--訪問控制(AccessControl)：防止非授權(quán)使用資源，即控制誰訪問資源，在什么條件下訪問，能夠訪問什么等

--不可否認(rèn)（Non-repudiation）：它是與責(zé)任相關(guān)的服務(wù)，指發(fā)送方和接受方都不能否認(rèn)發(fā)送和接收到的信息。

--交易隱私（Transactionprivacy）：該服務(wù)保護(hù)任何數(shù)字交易的隱私2024/4/5Ch1-引言17檢測與恢復(fù)服務(wù)主要是關(guān)于安全漏洞的檢測，以及采取行動恢復(fù)或者降低這些安全漏洞產(chǎn)生的影響，主要包括：

--審計(jì)(Audit)：當(dāng)安全漏洞被檢測到時(shí)，審計(jì)安全相關(guān)的事件是非常重要的。它是在系統(tǒng)發(fā)現(xiàn)錯(cuò)誤或受到攻擊時(shí)能定位錯(cuò)誤和找到攻擊成功的原因，以便對系統(tǒng)進(jìn)行恢復(fù)

--入侵檢測(Intrusiondetection):

該服務(wù)主要監(jiān)控危害系統(tǒng)安全的可疑行為，以便盡早地采用額外的安全機(jī)制來使系統(tǒng)更安全

--整體檢驗(yàn)(Proofofwholeness)：整體檢驗(yàn)服務(wù)主要是檢驗(yàn)系統(tǒng)或者數(shù)據(jù)仍然是否是完整的

--恢復(fù)安全狀態(tài)(Restoresecurestate)：該服務(wù)指當(dāng)安全漏洞發(fā)生時(shí)，系統(tǒng)必須能夠恢復(fù)到安全的狀態(tài)2024/4/5Ch1-引言18安全目標(biāo)、需求、服務(wù)和機(jī)制之間的關(guān)系

安全機(jī)制安全機(jī)制安全機(jī)制安全服務(wù)安全服務(wù)安全服務(wù)安全服務(wù)安全需求安全需求安全目標(biāo)2024/4/5Ch1-引言19安全目標(biāo)、需求、服務(wù)和機(jī)制之間的關(guān)系全部安全需求的實(shí)現(xiàn)才能達(dá)到安全目標(biāo)不同的安全服務(wù)的聯(lián)合能夠?qū)崿F(xiàn)不同的安全需求一個(gè)安全服務(wù)可能是多個(gè)安全需求的組成要素同樣，不同的安全機(jī)制聯(lián)合能夠完成不同的安全服務(wù)一個(gè)安全機(jī)制也可能是多個(gè)安全服務(wù)的構(gòu)成要素表1.1表示了一些安全服務(wù)和安全需求之間的關(guān)系2024/4/5Ch1-引言202024/4/5Ch1-引言21表1.1說明了不是所有的安全需求都強(qiáng)制性地要求所有安全服務(wù)但是這些安全服務(wù)并不是完全可以忽略因?yàn)檫@些安全服務(wù)可能間接地使用如上表中的鑒別和密鑰管理兩個(gè)安全服務(wù)僅僅是完整性、保密性和可追溯性所要求的，不是可用性和保障必須的，但可用性是依賴于完整性和保密性。保障則與可用性、完整性、保密性和可追溯性相關(guān)所以一個(gè)密鑰管理服務(wù)將影響所有的安全需求2024/4/5Ch1-引言22信息安全模型-網(wǎng)絡(luò)安全模型

大多數(shù)信息安全涉及通信雙方在網(wǎng)絡(luò)傳輸過程中的數(shù)據(jù)安全和計(jì)算機(jī)系統(tǒng)中數(shù)據(jù)安全。圖1.5是一個(gè)典型的網(wǎng)絡(luò)安全模型。2024/4/5Ch1-引言23從網(wǎng)絡(luò)安全模型可以看到，設(shè)計(jì)安全服務(wù)應(yīng)包括下面的四個(gè)方面的內(nèi)容：

--設(shè)計(jì)一個(gè)恰當(dāng)?shù)陌踩儞Q算法，該算法應(yīng)有足夠強(qiáng)安全性，不會被攻擊者有效地攻破。

--產(chǎn)生安全變換中所需要的秘密信息，如密鑰。

--設(shè)計(jì)分配和共享秘密信息的方法。

--指明通信雙方使用的協(xié)議，該協(xié)議利用安全算法和秘密信息實(shí)現(xiàn)系統(tǒng)所需要安全服務(wù)2024/4/5Ch1-引言24信息安全模型-計(jì)算機(jī)系統(tǒng)安全模型該模型顯示了計(jì)算機(jī)系統(tǒng)的安全，主要存在兩類攻擊：一類是外部入侵系統(tǒng)，一類是內(nèi)部對計(jì)算機(jī)系統(tǒng)的攻擊。本書介紹的信息安全原理與技術(shù)是針對網(wǎng)絡(luò)安全模型和計(jì)算機(jī)系統(tǒng)安全模型。2024/4/5Ch1-引言25網(wǎng)絡(luò)安全協(xié)議通過對TCP/IP參考模型各層增加一些安全協(xié)議來保證安全。這些安全協(xié)議主要分布在最高三層，主要有：

網(wǎng)絡(luò)層的安全協(xié)議：IPSec

傳輸層的安全協(xié)議：SSL/TLS

應(yīng)用層的安全協(xié)議：SHTTP（Web安全協(xié)議）、PGP(電子郵件安全協(xié)議)、S/MIME(電子郵件安全協(xié)議)、MOSS(電子郵件安全協(xié)議)、PEM(電子郵件安全協(xié)議)、SSH（遠(yuǎn)程登錄安全協(xié)議）、Kerberos(網(wǎng)絡(luò)認(rèn)證協(xié)議)等上面提到的一些協(xié)議將在本書的后面章節(jié)進(jìn)行詳細(xì)介紹2024/4/5Ch1-引言26信息安全原理與技術(shù)第3版第2章數(shù)學(xué)基礎(chǔ)主要知識點(diǎn)：

--數(shù)論

--代數(shù)基礎(chǔ)

--計(jì)算復(fù)雜性理論

--單向函數(shù)

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)28因子設(shè)Z表示全體整數(shù)所構(gòu)成的集合。定義2.1

設(shè)a,b∈Z，a≠0，c∈Z，使得b=ac，則稱a整除b，并稱a是b的因子或者約數(shù)，b是a的倍數(shù)，記為a|b。定理2.1

（帶余除法）設(shè)a,b∈Z，b≥1，則存在唯一的整數(shù)q和r，使得a=qb+r，0≤r<b。q稱a除以b所得的商，r稱為a除以b所得的最小非負(fù)剩余。定義2.2

設(shè)a,b∈Z，a，b不全為0，如果c|a且c|b，則稱c為a和b的公因子。特別地，我們把a(bǔ)和b的所有公因子中最大的，稱為a和b的最大公因子，記為gcd(a,b)或者(a,b)。2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)29計(jì)算兩個(gè)數(shù)的最大公因子的最容易的方法是用歐幾里德(Euclid)算法定理2.3（歐幾里德算法）給定整數(shù)a和b，且b>0，重復(fù)使用帶余除法，即每次的余數(shù)為除數(shù)去除上一次的除數(shù)，直到余數(shù)為0，這樣可以得到下面一組方程：

a=bq1+r1,0<r1<b,b=r1q2+r2,0<r2<r1,r1

=r2q3+r3,0<r3<r2,……rj-1

=rjqj+1最后一個(gè)不為0的余數(shù)rj就是a和b的最大公因子2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)30例2.1

求gcd(1970，1066)用歐幾里德算法的計(jì)算過程如下：1970＝1×1066+9041066＝1×904+162904＝5×162+94162=1×94+6894＝1×68+2668＝2×26+1626＝1×16+1016＝1×10+610＝1×6+46=1×4+24＝2×2+0因此gcd(1970，1066)=22024/4/5Ch2-數(shù)學(xué)基礎(chǔ)31素?cái)?shù)定義2.4

設(shè)p∈Z，p≥2，如果p的正因子只有1和p，則稱p

為素?cái)?shù)，否則為合數(shù)

若正整數(shù)a有一因子b，而b又是素?cái)?shù)，則稱b為a的素因子如果整數(shù)a與整數(shù)b的最大公因子是1，即gcd(a,b)=1，則稱a與b互為素?cái)?shù)，簡稱互素設(shè)

(m)為小于或等于m且與m互素的正整數(shù)個(gè)數(shù)，則稱其為歐拉(Euler)函數(shù)

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)32同余定義2.8

兩個(gè)整數(shù)a,b分別被m除，如果所得的余數(shù)相同，則稱a與b對模m是同余的，記為a≡b(modm)，正整數(shù)m稱為模數(shù)

同余具有下面的性質(zhì)：(1)若a≡b(modm)，則則m|(b-a)。反過來，若m|(b-a)，則a≡b(modm)(2)如果a=km+b(k為整數(shù))，則a≡b(modm)(3)每個(gè)整數(shù)恰與0,1,…，m-1這m個(gè)整數(shù)中的某一個(gè)對模m同余(4)同余關(guān)系是一種等價(jià)關(guān)系(5)a≡b(modm)當(dāng)且僅當(dāng)amodm=bmodm2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)33定理2.8(乘法消去律)對于ab

≡ac（modm）來說，若gcd(a,m)＝1則b≡c(mod

m)。

定理2.9(加法消去律)如果a+b

≡a+c（modm），則b≡c(mod

m)加法消去律是沒有條件，但乘法消去律的條件是gcd(a,m)＝1，即a和m互素例如6×3≡6×7≡2mod8，但3≡7mod8不成立2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)34模運(yùn)算

求余運(yùn)算稱為模運(yùn)算,下面是模運(yùn)算的一些性質(zhì)。

(1)(a+b)modm=((amodm)+(bmodm))modm(2)(a-b)modm=((amodm)-(bmodm))modm(3)(a×b)modm=((amodm)×(bmodm))modm(4)(a×(b+c))modm=((a×b)modm)+((a×c)modm))modm例如11mod8=3;15mod8=7,那么(11mod8)+(15mod8)mod8=(3+7)mod8=2(11+15)mod8=26mod8=2

在模運(yùn)算中，加法單位元是0，(0+a)modm=amodm乘法單位元是1，(1×a)modm=amodm2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)35定義2.13

對a∈Zm，存在b∈Zm，使得a+b≡0(modm)，則b是a的加法逆元，記b=-a。定義2.14對a∈Zm，存在b∈Zm，使得a×b≡1(modm)，則稱b為a的乘法逆元。加法一定存在逆元，乘法不一定存在逆元。在密碼學(xué)特別是非對稱密碼體制中，常常需要求模逆元，求模逆元就是求乘法逆元。即尋找一個(gè)x，使得a×x

≡1modm成立求模逆元問題很困難，有時(shí)有結(jié)果，有時(shí)沒有結(jié)果利用擴(kuò)展歐幾里德算法能夠計(jì)算出模逆元2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)36模8運(yùn)算的例子

模8的加法和乘法運(yùn)算與普通運(yùn)算一樣,只是將所得的值是去模8后的余數(shù)

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)372024/4/5Ch2-數(shù)學(xué)基礎(chǔ)38模8的加法逆元和乘法逆元

對每一個(gè)x都有一個(gè)對應(yīng)的y，使得x+y≡0mod8，則y是x的加法逆元。如對2，有6，使得2+6≡0mod8，那么6是2的加法逆元如果對x，存在y，使得x×y≡1mod8，則y為x的乘法逆元。如3×3≡1mod8，因此3的乘法逆元是3。2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)39快速指數(shù)模運(yùn)算

在非對稱密碼體制（公鑰密碼體制）中常常涉及指數(shù)模運(yùn)算，如計(jì)算73327mod37一種方法是利用前面介紹的模運(yùn)算性質(zhì)(a×b)modm=((amodm)×(bmodm))modm，將指數(shù)模運(yùn)算可以看做是多次重復(fù)乘法，并且在計(jì)算中間結(jié)果時(shí)就取模例如：計(jì)算117mod13，可以按照下面的思路：112=121≡4mod13114=(112)2≡42mod13≡3mod13117=11×112×114≡11×4×3mod13≡132mod13≡2mod132024/4/5Ch2-數(shù)學(xué)基礎(chǔ)40快速求memodn算法一

(1)a

e,b

m,c

1,其中a,b,c為三大整數(shù)寄存器。

(2)如果a=0，則輸出結(jié)果c即為所求的模n的大整數(shù)次冪。(3)如果a是奇數(shù)，轉(zhuǎn)第(5)步。(4)a

(a÷2),b

(b×b)modn,轉(zhuǎn)第(3)步。(5)a

(a-1),c

(c×b)modn,轉(zhuǎn)第(2)步。2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)41計(jì)算3037mod772024/4/5Ch2-數(shù)學(xué)基礎(chǔ)42費(fèi)馬定理和歐拉定理費(fèi)馬定理和歐拉定理在公鑰密碼體制中占非常重要的地位定理2.13(費(fèi)馬定理Format)若p是素?cái)?shù),且a是正整數(shù)，且gcd(a,p)=1，則：ap-1

1(modp)定理2.14(歐拉定理)

對于任何互素的兩個(gè)整數(shù)a和n，有

aφ(n)≡1modn2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)43素性測試很多密碼算法需要隨機(jī)選擇一個(gè)或者多個(gè)非常大的素?cái)?shù)一般做法是先生成大的隨機(jī)整數(shù)，然后確定該大數(shù)是否是素?cái)?shù)目前沒有還沒有簡單有效的方法確定一個(gè)大數(shù)是否是素?cái)?shù)定理2.15:如果p為大于2的素?cái)?shù)，則方程x2≡1(modp)的解只有x=1和x=-1。定理2.15的逆否命題是：如果方程x

2≡1(modp)有一解，那么p不是素?cái)?shù)2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)44Miller-Rabin素性概率檢驗(yàn)算法WITNESS(a,n)

(1)將(n-1)表示為二進(jìn)制形式bkbk-1…b0(2)d

1fori=k

downto0do{x

d；

d

(d

d)modn；

if(d=1&x

1&x

n-1)thenreturnTRUE；

ifbi=1thend

(d

a)modn}ifd

1thenreturnTRUE；

elsereturnFALSE.2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)45算法有兩個(gè)輸入，n是待檢驗(yàn)的數(shù)，a是小于n的整數(shù)。如果算法的返回值為TRUE，則n肯定不是素?cái)?shù)，如果返回值為FALSE，則n有可能是素?cái)?shù)。

for循環(huán)后，有d=an-1modn，由費(fèi)馬定理可知，若n為素?cái)?shù)，則d為1，因此若d

1，則n不是素?cái)?shù)，所以返回TRUE。因?yàn)閚-1≡-1modn，所以x

1，x

n-1，表示x

2≡1(modp)有不在{-1，1}中的根，因此n不為素?cái)?shù)，返回TRUE2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)46離散對數(shù)離散對數(shù)是許多公鑰算法的基礎(chǔ)本原根這一個(gè)重要概念假設(shè)gcd(a,n)=1,如果m是使am

≡1modn成立的最小正整數(shù)，則稱它是a對模n的指數(shù)，記為Ordna

若Ordna=φ(n)，則稱a是模n的本原根(primitiveroot)，也稱生成元2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)47求模7和模15的本原根對于模7而言，滿足gcd(a,n)=1的a是{1,2,3,4,5,6}，將它們的指數(shù)列表如下

a123456Ord7a136362從上表可以看到，當(dāng)a是3和5時(shí)，Ord7a=φ(7)，因此，3和5是模7的本原根。2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)48對于模15而言，滿足gcd(a,n)=1的a是{1,2,4,7,8,11,13,14}，將它們的指數(shù)列表如下：上表中不存在一個(gè)a，使Ord15a=φ(15)，所以模15沒有本原根定理2.18

模m的本原根存在的必要條件是m=2,4,pa,或者2pa，此處p是奇素?cái)?shù)a12478111314Ord7a142442422024/4/5Ch2-數(shù)學(xué)基礎(chǔ)49本原根的測試

通常找出一個(gè)本原根不是一件容易的問題如果知道p-1的因子，它就變得容易測試方法:令q1,q2,…,qn是p-1的素因子，對于所有的q1,q2,…,qn,計(jì)算a(p-1)/q(modp)，如果對某個(gè)q的某個(gè)值其結(jié)果為1，那么a

不是一個(gè)本原根。如果對某個(gè)q的所有值其結(jié)果都不為1，那么a

是一個(gè)本原根。2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)50例2.9

假設(shè)p=11,檢驗(yàn)2和3是否是一個(gè)本原根。解：當(dāng)p=11時(shí),p-1=10，p-1有兩個(gè)素因子2和5，現(xiàn)測試2是否是一個(gè)本原根。

2(10-1)/5(mod11)=42(10-1)/2(mod11)=10計(jì)算結(jié)果沒有1，所以2是本根原。測試3是否是本根原

3(10-1)/5(mod11)=93(10-1)/2(mod11)=1所以3不是本根原2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)51離散對數(shù)模運(yùn)算用于指數(shù)計(jì)算可以表示為axmodn，我們稱為模指數(shù)運(yùn)算

模指數(shù)運(yùn)算的逆問題就是找出一個(gè)數(shù)的離散對數(shù)，即求解x，使得

ax

≡bmodn定義2.17（離散對數(shù)）對于一個(gè)整數(shù)b和素?cái)?shù)n的一個(gè)本原根a，可以找到唯一的指數(shù)x，使得b≡ax

modn，其中0≤x≤n-1，指數(shù)x稱為b的以a為基數(shù)的模n的離散對數(shù)2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)52代數(shù)基礎(chǔ)有限域在現(xiàn)代密碼學(xué)中的地位越來越重要本節(jié)先簡單介紹群、環(huán)和域等概念，然后詳細(xì)介紹有限域中的運(yùn)算

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)53群

群G有時(shí)記做{G，·}，是定義了一個(gè)二元運(yùn)算的集合，這個(gè)二元運(yùn)算可以表示為·(它具有一般性，可以指加法，乘法或者其他的數(shù)學(xué)運(yùn)算)，G中每一個(gè)序偶(a，b)通過運(yùn)算生成G中的元素(a·b)，并滿足以下公理：(Al)封閉性：如果a和b都屬于G，則a·b也屬于G。(A2)結(jié)合律；對于G中任意元素a,b,c，都有a·(b·c)=(a·b)·c成立(A3)單位元：G中存在一個(gè)元素e，對于G中任意元素a，都有a·e=e·a=a成立(A4)逆元：對于G中任意元素a，G中都存在一個(gè)元素a’，使得式a·a’=a’·a=e成立。如果一個(gè)群的元素個(gè)數(shù)是有限的，則該群稱為有限群。并且群的階等于群中元素的個(gè)數(shù)。否則，稱該群為無限群。一個(gè)群如果還滿足以下條件，則稱為交換群（或稱Able群）(A5)交換律:對于G中任意的元素a,b，都有.a·b=b·a成立2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)54環(huán)

環(huán)R有時(shí)記為{R，+，×}，是一個(gè)有兩個(gè)二元運(yùn)算的集合，這兩個(gè)二元運(yùn)算分別稱為加法和乘法，且對于R中的任意元素a,b,c，滿足以下公理：

(Al-A5)R關(guān)于加法是一個(gè)交換群；對于此種情況下的加法群，我們用0表示其單位元，-a表示a的逆元。

(M1)乘法的封閉性：如果a和b都屬于R，則ab也屬于R。(M2)乘法的結(jié)合律：對于R中任意元素a,b,c，有a(bc)=(ab)c成立。(M3)分配律：對于R中任意元素a,b,c，式a(b+c)=ab+ac和式(a+b)c=ac+bc總成立。環(huán)如果還滿足一下條件則成為交換環(huán)：(M4)乘法的交換律：對于R中的任意元素a,b，有ab=ba成立。在交換環(huán)的基礎(chǔ)上，滿足以下公理的環(huán)叫做整環(huán)：(M5)乘法單位元：在R中存在元素1，使得對于R中的任意元素a，有al=1a=a成立。(M6)無零因子：如果有R中元素a,b，且ab=0，則必有a=0或b=0

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)55域

域F有時(shí)記為{F，+，×}，是有兩個(gè)二元運(yùn)算的集合，這兩個(gè)二元運(yùn)算分別稱為加法和乘法，且對于F中的任意元素a,b,c，滿足以下公理：(Al-M6)F是一個(gè)整環(huán)；也就是說F滿足從Al到A5以及從M1到M6的所有原則。(M7)乘法逆元:對于F中的任意元素a(除0以外),F中都存在一個(gè)元素a-1,使得式aa-1=(a-1)a=1成立2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)56根據(jù)域中元素的個(gè)數(shù)是不是有限，把域劃分成有限域和無限域無限域在密碼學(xué)中沒有特別的意義，然而有限域卻在許多密碼編碼學(xué)中扮演著重要的角色。定義2.19:有限域中元素的個(gè)數(shù)稱為有限域的階。定理2.19:有限域的階必為素?cái)?shù)p的冪pn，n為正整數(shù)定理2.20:

對任意素?cái)?shù)p和正整數(shù)n，存在pn階的有限域，記為GF(pn)。當(dāng)時(shí)n=1，有限域GF(p)也稱素域。在密碼學(xué)中，最常用的域一般是素域GF(p)或者階為2m的GF(2m)域2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)57有限域GF(p)

給定一個(gè)素?cái)?shù)p，元素個(gè)數(shù)為p的有限域GF(p)定義為整數(shù){0,1,…,p-1}的集合Zp，其運(yùn)算為模p的算術(shù)運(yùn)算最簡單的有限域是GF(2)，該域元素的個(gè)數(shù)是2，它們分別是0和1，在GF(2)上的加運(yùn)算等價(jià)于異或運(yùn)算，乘等價(jià)于邏輯與運(yùn)算表2.5是在有限域GF(7)中的算術(shù)運(yùn)算，這是一個(gè)階為7，采用模7運(yùn)算，它滿足域的所有性質(zhì)。需要注意的是，前面介紹的表2.1只是表示集合Z8中模8運(yùn)算，其中的非零整數(shù)不一定有乘法逆元，因此不是域2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)58模7加法2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)59模7乘法2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)60模7的加法逆元和乘法逆元2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)61域上多項(xiàng)式

若ai≠0，稱n為該多項(xiàng)式的次數(shù)，并稱an為首項(xiàng)系數(shù)。首項(xiàng)系數(shù)為1的多項(xiàng)式稱為首1多項(xiàng)式。域F上x多項(xiàng)式全體集合記為F[x]多項(xiàng)式運(yùn)算包括加法、減法、乘法和除法

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)62在域F上的多項(xiàng)式加法運(yùn)算定義為乘法運(yùn)算定義為：2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)63定理2.21設(shè)a(x)和b(x)是域F上的多項(xiàng)式，且b(x)≠0，則存在唯一的一對多項(xiàng)式，使

其中q(x)為商式，r(x)為余式，r(x)的次數(shù)小于b(x)的次數(shù)多項(xiàng)式除法具有與普通除法一樣的長除法如整數(shù)運(yùn)算類似，我們可以將余式r(x)寫成a(x)modb(x)，稱為a(x)模b(x)，b(x)稱為模多項(xiàng)式

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)64定義2.21設(shè)a(x)和b(x)是域F上的多項(xiàng)式(1)設(shè)b(x)≠0，若存在q(x)使，則稱b(x)是a(x)的因式或者除式。b(x)整除a(x)，記為b(x)|a(x)。

(2)設(shè)a(x)和b(x)不全為0，a(x)和b(x)的次數(shù)最高的首1公因式稱為它們的最高公因式，記為gcd(a(x),b(x))。若gcd(a(x),b(x))=1，稱a(x)和b(x)互素。

(3)若存在次數(shù)大于或者等于1的q(x)和b(x)，使a(x)=q(x)b(x)，則稱a(x)為可約多項(xiàng)式，否則稱a(x)為不可約多項(xiàng)式（也稱既約多項(xiàng)式）2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)65例如，GF(2)上的多項(xiàng)式是可約多項(xiàng)式，因?yàn)?。而多?xiàng)式則是不可約多項(xiàng)式，因?yàn)樗鼪]有一個(gè)因式2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)66有限域GF(2n)

為pn模的模運(yùn)算不一定能產(chǎn)生域用不可約多項(xiàng)式可以構(gòu)造一個(gè)域

對于F[x]中的每個(gè)不可約多項(xiàng)式p(x)，可以構(gòu)造一個(gè)域F[x]

p(x)

設(shè)p(x)是F[x]中n次不可約多項(xiàng)式，令F[x]

p(x)為F[x]中所有次數(shù)小于n的多項(xiàng)式集合

其中ai

∈F，即在集合{0,1,…,p-1}上取值

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)67定義F[x]

p(x)上的二元運(yùn)算加法和乘法運(yùn)算如下：域F[x]

p(x)中的單位元和零元分別是F中的單位元和零元上面的運(yùn)算定義可以看到：

(1)該運(yùn)算遵循基本代數(shù)規(guī)則中的普通多項(xiàng)式運(yùn)算規(guī)則

(2)系數(shù)運(yùn)算以p模，即遵循有限域上Zp的運(yùn)算規(guī)則(3)乘法運(yùn)算是兩個(gè)多項(xiàng)式相乘結(jié)果再模一個(gè)不可約多項(xiàng)式p(x)，如果兩個(gè)多項(xiàng)式相乘結(jié)果是次數(shù)大于n-1的多項(xiàng)式，它將除以次數(shù)為n的不可約多項(xiàng)式p(x)并取余2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)68定理2.22是域,當(dāng)且僅當(dāng)p(x)是F上的不可約多項(xiàng)式，其中F是有限域。特別地，在GF(2n)中，F(xiàn)[x]

p(x)中所有次數(shù)小于n的多項(xiàng)式表示為：系數(shù)ai是二進(jìn)制數(shù)，該多項(xiàng)式可以由它的n個(gè)二進(jìn)制系數(shù)唯一地表示。因此GF(2n)中的每個(gè)多項(xiàng)式都可以表示成一個(gè)n位的二進(jìn)制整數(shù)。2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)69高級加密標(biāo)準(zhǔn)中的有限域GF(28)上運(yùn)算不可約多項(xiàng)式為假設(shè)多項(xiàng)式加法運(yùn)算過程為=乘法運(yùn)算過程為：2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)70由于a(x)和b(x)相乘的多項(xiàng)式次數(shù)大于n，將它們相乘結(jié)果再除不可約多項(xiàng)式p(x)，可得商為x5+x3，余數(shù)為x7+x6+1，因此用十六進(jìn)制表示為{57}{83}={C1}用二進(jìn)制表示為=(11000001)說明：在上面的十六進(jìn)制表示中，是用一個(gè)十六進(jìn)制字符表示4位二進(jìn)制數(shù)，一個(gè)字節(jié)的二進(jìn)制數(shù)用括號括起來的兩個(gè)十六進(jìn)制字符表示2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)71從上面的例子我們也可以發(fā)現(xiàn)，多項(xiàng)式加法是將對應(yīng)的系數(shù)分別相加GF(2n)中兩個(gè)多項(xiàng)式加法和減法等同于按位異或，需要注意的是加法不進(jìn)位，減法不借位2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)72計(jì)算復(fù)雜性理論計(jì)算復(fù)雜性理論提供了一種分析不同密碼技術(shù)和算法的計(jì)算復(fù)雜性方法計(jì)算復(fù)雜性理論給出了求解一個(gè)問題的計(jì)算是“容易”還是“困難”的確切定義，這有助于確定一個(gè)密碼算法的安全強(qiáng)度破譯一個(gè)密碼算法所花費(fèi)的時(shí)間或者空間代價(jià)超出了密碼本身所保密內(nèi)容的價(jià)值，破譯就沒有意義計(jì)算機(jī)復(fù)雜性理論涉及算法的復(fù)雜性和問題的復(fù)雜性

2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)73問題的復(fù)雜性一個(gè)問題的復(fù)雜性是由可解這個(gè)問題的算法的計(jì)算復(fù)雜性所決定可解一個(gè)問題的算法可能有多個(gè)，在理論上定義一個(gè)問題的計(jì)算復(fù)雜性為可解該問題的最有效算法的計(jì)算復(fù)雜性

計(jì)算復(fù)雜性粗分為三類，即P類(確定性多項(xiàng)式時(shí)間可解類)、NP類(不確定性多項(xiàng)式時(shí)間可解類)和NP完全類(記為NPC，不確定性多項(xiàng)式時(shí)間可解完全類)P類問題稱為易解問題，NP類問題稱為難解問題，NPC問題稱為困難問題。由于NPC問題不存在有效的算法，現(xiàn)在的密碼算法的安全性都是基于NPC問題的2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)74算法的復(fù)雜性算法的復(fù)雜性表示算法在實(shí)際執(zhí)行時(shí)所需計(jì)算能力方面的信息，通常它由該算法所要求的最大時(shí)間與儲存空間來確定算法所需的時(shí)間和空間往往取決于問題實(shí)例的規(guī)模n

算法在用于相同規(guī)模n的不同實(shí)例時(shí)，其時(shí)間和空間需求也可能會有很大差異，因此，實(shí)際中我們常常研究的是算法關(guān)于輸入規(guī)模n的所有實(shí)例的時(shí)間與空間需求的平均值

表2.6顯示:如果一個(gè)密碼算法具有指數(shù)級的時(shí)間復(fù)雜性，那么可以認(rèn)為它是計(jì)算上不可行的2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)752024/4/5Ch2-數(shù)學(xué)基礎(chǔ)76單向函數(shù)單向函數(shù)是密碼學(xué)中哈希算法的設(shè)計(jì)基礎(chǔ)，單向陷門函數(shù)則是公鑰密碼學(xué)的核心。定義2.23

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

B，若它滿足：

(1)對所有x

A，易于計(jì)算f(x)。

(2)對幾乎所有x

A，由f(x)求x極為困難，以至于實(shí)際上不可能做到，則稱f為單向函數(shù)(One-wayFunction)2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)77定義2.24(單向陷門函數(shù))一“可逆”函數(shù)F若滿足下列二條件，則稱F為單向陷門函數(shù)(One-wayTrapdoorFunction)：(1)對于所有屬于域F中的的任一x，容易計(jì)算F(x)=y；(2)對于幾乎所有屬于域F中的任一y，除非獲得陷門信息(trapdoor)，否則求出x，使得x=F-1(y)在計(jì)算上不可行，F(xiàn)-1為F的逆函數(shù)單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù)是在不知陷門信息下求逆困難的函數(shù)，當(dāng)知道陷門信息后，求逆是易于實(shí)現(xiàn)的2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)78目前，還不能從理論上證明單向函數(shù)是存在的現(xiàn)實(shí)中卻存在幾個(gè)候選單向函數(shù).說他們是“候選”，是因?yàn)樗麄儽憩F(xiàn)出了單向函數(shù)的性質(zhì)，但還沒有辦法從理論上證明它們一定是單向函數(shù)常見的候選單向函數(shù):

--離散對數(shù)

--因數(shù)分解問題

--背包問題2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)79密碼學(xué)中哈希算法和公鑰算法中單向函數(shù)區(qū)別如下：哈希算法中的單向函數(shù)完全單向，不存在可逆性。公鑰算法中的單向函數(shù)在知道陷門信息時(shí)具有可逆性。哈希算法中單向函數(shù)設(shè)計(jì)是基壓縮函數(shù)的迭代結(jié)構(gòu)，公鑰算法中的單向函數(shù)是基于數(shù)學(xué)上難題，因此，哈希算法運(yùn)算速度遠(yuǎn)高于公鑰算法。2024/4/5Ch2-數(shù)學(xué)基礎(chǔ)80信息安全原理與技術(shù)第3版第3章對稱加密技術(shù)(1)主要知識點(diǎn)：

--對稱密碼模型

--密碼攻擊

--古典加密技術(shù)

--數(shù)據(jù)加密標(biāo)準(zhǔn)

--高級加密標(biāo)準(zhǔn)

--中國商用密碼算法-SM4

--RC6

--流密碼

--分組密碼工作模式

--隨機(jī)數(shù)的產(chǎn)生

--對稱密碼的密鑰分配

2024/4/5Ch3(1)-對稱加密技術(shù)82密碼技術(shù)主要分為對稱密碼技術(shù)和非對稱密碼技術(shù)對稱密碼技術(shù)中，加密密鑰和解密密鑰相同，或者一個(gè)密鑰可以從另一個(gè)導(dǎo)出非對稱密碼技術(shù)則使用兩個(gè)密鑰,加密密鑰和解密密鑰不同,非對稱密碼技術(shù)則產(chǎn)生于20世紀(jì)70年代20世紀(jì)70年代以前的加密技術(shù)都是對稱加密技術(shù)，這個(gè)時(shí)期的加密技術(shù)也稱為古典加密技術(shù)。古典加密技術(shù)一般將加密算法保密，而現(xiàn)代的對稱加密技術(shù)則公開加密算法，加密算法的安全性只取決于密鑰，不依賴于算法2024/4/5Ch3(1)-對稱加密技術(shù)83密碼學(xué)的基本概念密碼學(xué)（Cryptology）包括密碼編碼學(xué)（Cryptography）,和密碼分析學(xué)（Cryptanalysis）密碼編碼學(xué)是研究加密原理與方法，使消息保密的技術(shù)和科學(xué)，它的目的是掩蓋消息內(nèi)容密碼分析學(xué)則是研究破解密文的原理與方法密碼分析者（Cryptanalyst）是從事密碼分析的專業(yè)人員被偽裝的原始的消息(Message)稱為明文（Plaintext）將明文轉(zhuǎn)換為密文過程稱為加密（Encryption）

2024/4/5Ch3(1)-對稱加密技術(shù)84加了密的消息稱為密文（Ciphertext）把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密（Decryption）從明文到密文轉(zhuǎn)換的算法稱為密碼(Cipher)一個(gè)加密系統(tǒng)采用的基本工作方式叫做密碼體制(Cryptosystem)在密碼學(xué)中見到“系統(tǒng)或體制”(System)、“方案”(Scheme)和“算法”(Algorithm)等術(shù)語本質(zhì)上是一回事加密和解密算法通常是在一組密鑰（Key）控制下進(jìn)行的,分別稱為加密密鑰和解密密鑰如果加密密鑰和解密密鑰相同，則密碼系統(tǒng)為對稱密碼系統(tǒng)

2024/4/5Ch3(1)-對稱加密技術(shù)85對稱密碼模型對稱密碼也稱傳統(tǒng)密碼，它的特點(diǎn)是發(fā)送方和接收方共享一個(gè)密鑰對稱密碼分為兩類：分組密碼(BlockCiphers)和流密碼(StreamCiphers)分組密碼也稱為塊密碼，它是將信息分成一塊(組)，每次操作(如加密和解密)是針對一組而言流密碼也稱序列密碼，它是每次加密(或者解密)一位或者一個(gè)字節(jié)2024/4/5Ch3(1)-對稱加密技術(shù)86一個(gè)對稱密碼系統(tǒng)(也稱密碼體制)有五個(gè)組成部分組成。用數(shù)學(xué)符號來描述為S＝{M,C,K,E,D}，如圖3.2所示。(1)明文空間M，是全體明文的集合。(2)密文空間C，表示全體密文的集合。(3)密鑰空間K，表示全體密鑰的集合，包括加密密鑰和解密密鑰。(4)加密算法E，表示由明文到密文的變換。(5)解密算法D，表示由密文到文明的變換。2024/4/5Ch3(1)-對稱加密技術(shù)87明文加密算法解密算法明文傳輸通道MMCC攻擊者接收方發(fā)送方密鑰源安全通道KK圖3.2對稱密碼系統(tǒng)模型2024/4/5Ch3(1)-對稱加密技術(shù)88對明文M用密鑰K，使用加密算法E進(jìn)行加密常常表示為Ek(M)，同樣用密鑰K使用解密算法D對密文C進(jìn)行解密表示為Dk(C)在對稱加密體制中，密解密密鑰相同,有：C＝Ek(M)M＝Dk(C)＝Dk(Ek(M))2024/4/5Ch3(1)-對稱加密技術(shù)89密碼體制至少滿足的條件

(1)已知明文M和加密密鑰K時(shí)，計(jì)算C＝Ek(M)容易(2)加密算法必須足夠強(qiáng)大，使破譯者不能僅根據(jù)密文破譯消息，即在不知道解密密鑰K時(shí)，由密文C計(jì)算出明文M是不可行的(3)由于對稱密碼系統(tǒng)雙方使用相同的密鑰，因此還必須保證能夠安全地產(chǎn)生密鑰，并且能夠以安全的形式將密鑰分發(fā)給雙方(4)對稱密碼系統(tǒng)的安全只依賴于密鑰的保密，不依賴于加密和解密算法的保密2024/4/5Ch3(1)-對稱加密技術(shù)90密碼攻擊

分析一個(gè)密碼系統(tǒng)是否是安全，一般是在假定攻擊者知道所使用的密碼系統(tǒng)情況下進(jìn)行分析的如:密碼分析者可以得到密文，知道明文的統(tǒng)計(jì)特性，加密體制，密鑰空間及其統(tǒng)計(jì)特性這個(gè)假設(shè)稱為Kerckhoff（克爾克霍夫）假設(shè)分析一個(gè)密碼系統(tǒng)的安全性一般是建立在這個(gè)假設(shè)的基礎(chǔ)上對稱密碼體制的攻擊有兩種方法：密碼分析和窮舉攻擊(BruteForceSearch)2024/4/5Ch3(1)-對稱加密技術(shù)91密碼分析是依賴加密算法的性質(zhì)和明文的一般特征等試圖破譯密文得到明文或試圖獲得密鑰的過程窮舉攻擊則是試遍所有可能的密鑰對所獲密文進(jìn)行解密，直至得到正確的明文；或者用一個(gè)確定的密鑰對所有可能的明文進(jìn)行加密，直至得到所獲得的密文2024/4/5Ch3(1)-對稱加密技術(shù)92窮舉攻擊窮舉攻擊是最基本也是比較有效的一種攻擊方法從理論上講，可以嘗試所有的密鑰窮舉攻擊的代價(jià)與密鑰大小成正比密碼算法可以通過增大密鑰位數(shù)或加大解密（加密）算法的復(fù)雜性來對抗窮舉攻擊表3.1是窮盡密鑰空間所需的時(shí)間。從表中我們可以發(fā)現(xiàn)，當(dāng)密鑰長度達(dá)到128位以上時(shí)，以目前的資源來說，窮舉攻擊將不成功2024/4/5Ch3(1)-對稱加密技術(shù)932024/4/5Ch3(1)-對稱加密技術(shù)94密碼攻擊類型密碼分析是基于Kerckhoff假設(shè)密碼分析者所使用的策略取決于加密方案的性質(zhì)以及可供密碼分析者使用的信息根據(jù)密碼分析者所知的信息量,把對密碼的攻擊分為:唯密文攻擊,已知明文攻擊,選擇明文攻擊,選擇密文攻擊,選擇文本攻擊

2024/4/5Ch3(1)-對稱加密技術(shù)95唯密文攻擊（Ciphertext-OnlyAttack）:密碼分析者知道：加密算法和待破譯的密文.已知明文攻擊（Known-PlaintextAttack）:密碼分析者除知道加密算法和待破譯的密文外，而且也知道，有一些明文和同一個(gè)密鑰加密的這些明文所對應(yīng)的密文即知道一定數(shù)量的明文和對應(yīng)的密文選擇明文攻擊（Chosen-PlaintextAttack）:密碼分析者知道加密算法和待破譯的密文，并且可以得到所需要的任何明文所對應(yīng)的密文，這些明文和待破譯的密文是用同一密鑰加密得來的，即知道選擇的明文和對應(yīng)的密文。如在公鑰密碼體制中，攻擊者可以利用公鑰加密他任意選定的明文2024/4/5Ch3(1)-對稱加密技術(shù)96選擇密文攻擊（Chosen-CiphertextAttack）:密碼分析者知道加密算法和待破譯的密文，密碼分析者能選擇不同的被加密的密文，并可得到對應(yīng)的解密的明文，即知道選擇的密文和對應(yīng)的明文。解密這些密文所使用的密鑰與解密待破解的密文的密鑰是一樣的。這種攻擊主要用于公鑰密碼算法。選擇文本攻擊（ChosenTextAttack）：選擇文本攻擊是選擇明文攻擊和選擇密文攻擊的結(jié)合。密碼分析者知道加密算法和待破譯的密文，并且知道任意選擇的明文和它對應(yīng)的密文，這些明文和待破譯的密文是用同一密鑰加密得來的，以及有目的選擇的密文和它對應(yīng)的明文，解密這些密文所使用的密鑰與解密待破解的密文的密鑰是一樣的。2024/4/5Ch3(1)-對稱加密技術(shù)97如果一個(gè)密碼系統(tǒng)能夠抵抗選擇明文攻擊，那么它也能抵抗唯密文攻擊和已知明文攻擊在這幾種攻擊類型中，唯密文攻擊難度最大，因?yàn)楣粽呖衫玫男畔⒆钌賹γ艽a設(shè)計(jì)者而言，被設(shè)計(jì)的加密算法一般要能經(jīng)受得住已知明文的攻擊如果無論攻擊者有多少密文，由一個(gè)加密算法產(chǎn)生的這些密文中包含的信息不足以唯一決定對應(yīng)的明文，也無論用什么技術(shù)方法進(jìn)行攻擊都不能被攻破，這種加密算法是絕對安全(UnconditionalSecurity)除一次一密（One-TimePad）外，沒有絕對安全的加密算法2024/4/5Ch3(1)-對稱加密技術(shù)98一般來說,加密算法的使用者應(yīng)該挑選滿足下列標(biāo)準(zhǔn)中的一個(gè)或兩個(gè)的算法：(1)破譯該密碼的成本超過被加密信息的價(jià)值。(2)破譯該密碼的時(shí)間超過該信息有用的生命周期。如果滿足上述的兩個(gè)準(zhǔn)則，一個(gè)加密算法就可認(rèn)為是在計(jì)算上安全（ComputationalSecurity）的計(jì)算上安全是指在計(jì)算能力有限的的情況下(如計(jì)算所需時(shí)間比宇宙生存時(shí)間還長)，無法破解此密文目前的加密算法一般是計(jì)算上安全的2024/4/5Ch3(1)-對稱加密技術(shù)99密碼分析方法當(dāng)密鑰長度增加到一定的大小時(shí)，窮舉攻擊變得不實(shí)際比較流行的密碼分析方法是線性密碼分析和差分密碼分析

線性分析是一種已知明文攻擊線性分析是一種統(tǒng)計(jì)攻擊，它以求線性近似為基礎(chǔ)。通過尋找現(xiàn)代密碼算法變換的線性近似來攻擊用這種方法只需要知道243個(gè)已知明文的情況下就可以找到DES的密鑰

2024/4/5Ch3(1)-對稱加密技術(shù)100差分密碼分析在許多方面與線性密碼分析相似它與線性密碼分析的主要區(qū)別在于差分密碼分析包含了將兩個(gè)輸入的異或與其相對應(yīng)的兩個(gè)輸出的異或相比較差分密碼分析也是一個(gè)選擇明文攻擊差分密碼分析出現(xiàn)于20世紀(jì)70年代，但在1990年才公開發(fā)表它的基本思想是：通過分析明文對的差值與密文對的差值的影響來恢復(fù)某些密鑰位差分分析可用來攻擊任何由迭代一個(gè)固定的輪函數(shù)的結(jié)構(gòu)的密碼

2024/4/5Ch3(1)-對稱加密技術(shù)101古典加密技術(shù)古典加密技術(shù)主要使用代換或者置換技術(shù)代換是將明文字母替換成其他字母、數(shù)字或者符號置換則保持明文的所有字母不變，只是打亂明文字母的位置和次序古典代換加密技術(shù)分為兩類:單字母代換密碼，它將明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符代替。多字母代換密碼,它是對多于一個(gè)字母進(jìn)行代換單字母代換密碼中又分為單表代換密碼和多表代換密碼2024/4/5Ch3(1)-對稱加密技術(shù)102單表代換密碼只使用一個(gè)密文字母表，并且用密文字母表中的一個(gè)字母來代替一個(gè)明文字母表中的一個(gè)字母多表代換密碼是將明文消息中出現(xiàn)的同一個(gè)字母，在加密時(shí)不是完全被同一個(gè)固定的字母代換，而是根據(jù)其出現(xiàn)的位置次序，用不同的字母代換2024/4/5Ch3(1)-對稱加密技術(shù)103單表代換密碼設(shè)M和C分別表示為含n個(gè)字母的明文字母表和密文字母表。

M={m0,m1,…,mn-1}

C={c0,c1,…,cn-1}如果f為一種代換方法，那么密文為C=Ek(m)=c0c1…cn-1=f(m0)f(m1)…

f(mn-1)單表代換密碼常見的方法有加法密碼，乘法密碼和仿射密碼

2024/4/5Ch3(1)-對稱加密技術(shù)104加法密碼

對每個(gè)c,m∈Zn，加法密碼的加密和解密算法是：

C=Ek(m)=(m+k)modn

M=Dk(c)=(c-k)modnk是滿足0<k<n

的正整數(shù)。若n是26個(gè)字母，加密方法是用明文字母后面第k個(gè)字母代替明文字母Caesar密碼是典型的加法密碼,由JuliusCaesar發(fā)明，最早用在軍方。將字母表中的每個(gè)字母，用它后面的第3個(gè)字母代替2024/4/5Ch3(1)-對稱加密技術(shù)105Caesar密碼舉例明文：meetmeafterthetogaparty密文：PHHWPHDIWHUWKHWRJDSDUWB對每個(gè)明文字母m，用密文字母c代換，那么Caesar密碼算法如下：加密：C=E(m)=(m+3)mod26解密：

M=D(c)=(c–3)mod26移位可以是任意的，如果用k（1≤k≤25）表示移位數(shù)，則通用的Caesar密碼算法表示為：加密：

C=Ek(m)=(m+k)mod26解密：

M=Dk(c)=(c–k)mod262024/4/5Ch3(1)-對稱加密技術(shù)106Caesar密碼安全性對密碼的分析是基于Kerckhoff假設(shè)假設(shè)攻擊者知道使用Caesar密碼加密。如果攻擊者只知道密文，即唯密文攻擊，只要窮舉測試所有可能字母移位的距離，最多嘗試25次如果攻擊者知道一個(gè)字符以及它對應(yīng)的密文，即已知明文攻擊，那么攻擊者很快就通過明文字符和對應(yīng)的密文字符之間的距離推出密鑰這個(gè)例子說明一個(gè)密碼體制安全至少要能夠抵抗窮舉密鑰搜索攻擊，普通的做法是將密鑰空間變得足夠大。但是，很大的密鑰空間并不是保證密碼體制安全的充分條件，下面的例子可以說明這一點(diǎn)2024/4/5Ch3(1)-對稱加密技術(shù)107對Caesar密碼進(jìn)行改進(jìn)，假設(shè)密文是26個(gè)字母的任意代換，密鑰是明文字母到密文字母的一個(gè)字母表，密鑰長度是26字長下面用一個(gè)密鑰句子構(gòu)造一個(gè)字母代換表密鑰句子為themessagewastransmittedanhourago，按照密鑰句子中的字母依次填入字母表（重復(fù)的字母只用一次），未用的字母按自然順序排列

原字母表abcdefghijklmnopqrstuvwxyz代換字母表THEMSAGWRNIDOUBCFJKLPQVXYZ2024/4/5Ch3(1)-對稱加密技術(shù)108若明文為pleaseconfirmreceipt

使用上面的代換字母表，則密文為CDSTKSEBUARJOJSESRCL使用上面的方法代換，總共有26!=4x1026

種密鑰從表3.1可以看到窮舉搜索這么多的密鑰很困難但這并不表示該密碼不容易破解破解這類密碼的突破點(diǎn)是由于語言本身的特點(diǎn)是充滿冗余的，每個(gè)字母使用的頻率不相等單表代換密碼沒有改變字母相對出現(xiàn)的頻率明文字母的統(tǒng)計(jì)特性在密文中能夠反映出來,當(dāng)通過統(tǒng)計(jì)密文字母的出現(xiàn)頻率，可以確定明文字母和密文字母之間的對應(yīng)關(guān)系2024/4/5Ch3(1)-對稱加密技術(shù)109英文字母中單字母出現(xiàn)的頻率

2024/4/5Ch3(1)-對稱加密技術(shù)110單字母按照出現(xiàn)頻率的大小可以分為下面5類：

(1)e：出現(xiàn)的頻率大約為0.127(2)t,a,o,I,n,s,h,r：出現(xiàn)的頻率大約在0.06-0.09之間

(3)d,l：出現(xiàn)的頻率約為0.04(4)c,u,m,w,f,g,y,p,b：出現(xiàn)的頻率大約在0.015-0.028之間

(5)v,k,j,x,q,z：出現(xiàn)的頻率小于0.01雙字母和三字母組合都有現(xiàn)成的統(tǒng)計(jì)數(shù)據(jù)，常見的雙字母組合和三字母組合統(tǒng)計(jì)表能夠幫助破解密文。頻率最高的30個(gè)雙字母（按照頻率從大到小排列）：

thheineranreedones

stenattonthand

oueangasortiisetitar

tesehiof

頻率最高的20個(gè)3字母（按照頻率從大到小排列）：

theingandherereent

thanthwasethfordthhatsheioninthissth

ers

ver2024/4/5Ch3(1)-對稱加密技術(shù)111破解舉例例3.1

已知下面的密文式由單表代換生產(chǎn)的：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ，試破譯該密文首先統(tǒng)計(jì)密文中字母出現(xiàn)的頻率，然后與英文字母出現(xiàn)頻率比較。密文中字母的相對頻率統(tǒng)計(jì)如下：2024/4/5Ch3(1)-對稱加密技術(shù)1122024/4/5Ch3(1)-對稱加密技術(shù)113將統(tǒng)計(jì)結(jié)果與圖3.3進(jìn)行比較，可以猜測密文中P與Z可能是e和t，密文中的S,U,O,M出現(xiàn)頻率比較高，可能與明文字母中出現(xiàn)頻率相對較高的a,o,I,n,s,h,r這些字母對應(yīng)密文中出現(xiàn)頻率很低的幾個(gè)字母C,K,L,N,R,I,J可能與明文字母中出現(xiàn)頻率較低的字母v,k,j,x,q,z對應(yīng)。就這樣邊試邊改，最后得到明文如下：itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow

在嘗試過程中，如果同時(shí)使用雙字母和三字母的統(tǒng)計(jì)規(guī)律，那么更容易破譯密文。如上面的密文中出現(xiàn)最多的雙字母是ZW，它可能對應(yīng)明文雙字母出現(xiàn)頻率較大的th，那么ZWP就可能是the，這樣就更容易試出明文。2024/4/5Ch3(1)-對稱加密技術(shù)114乘法密碼

對每個(gè)c,m∈Zn，乘法密碼的加密和解密算法是：

C=Ek(m)=(mk)modn

M=Dk(c)=(ck-1)modn其中k和n互素，即gcd(k,n)=1，否則不存在模逆元，不能正確解密乘法密碼的密碼空間大小是φ(n)，φ(n)是歐拉函數(shù)。乘法密碼的密鑰空間很小，當(dāng)n為26字母，則與26互素的數(shù)是1、3、5、7、9、11、15、17、19、21、23、25，即φ(n)=12因此乘法密碼的密鑰空間為12。乘法密碼也稱采樣密碼，因?yàn)槊芪淖帜副硎菍⒚魑淖帜赴凑障聵?biāo)每隔k位取出一個(gè)字母排列而成。2024/4/5Ch3(1)-對稱加密技術(shù)115乘法密碼舉例例3.2

假設(shè)選取密鑰為9，使用乘法密碼的加密算法，那么明文字母和密文字母的代換表構(gòu)造如下

若明文為amanliberalinhisviews那么密文為AENVUJKXUNLUGHUKQG2024/4/5Ch3(1)-對稱加密技術(shù)116仿射密碼

加法密碼和乘法密碼結(jié)合就構(gòu)成仿射密碼，仿射密碼的加密和解密算法是：C=Ek(m)=(k1m+k2)modn

M=Dk(c)=k1-1(c-k2)modn仿射密碼具有可逆性的條件是gcd(k,n)=1。當(dāng)k1=0時(shí)，仿射密碼變?yōu)榧臃艽a，當(dāng)k2=0時(shí)，仿射密碼變?yōu)槌朔艽a。仿射密碼中的密鑰空間的大小為nφ(n)，當(dāng)n為26字母，φ(n)=12，因此仿射密碼的密鑰空間為12×26=312。2024/4/5Ch3(1)-對稱加密技術(shù)117仿射密碼舉例例3.3設(shè)密鑰K=(7,3),用仿射密碼加密明文hot。三個(gè)字母對應(yīng)的數(shù)值是7、14和19。分別加密如下：

(7×7+3)mod26=52mod26=0(7×14+3)mod26=101mod26=23(7×19+3)mod26=136mod26=6三個(gè)密文數(shù)值為0、23和6，對應(yīng)的密文是AXG。2024/4/5Ch3(1)-對稱加密技術(shù)118多表代換密碼

用單表代換密碼加密后的密文具有明文的特征，通過統(tǒng)計(jì)密文中字母出現(xiàn)的頻率能夠比較方便地破解密文要提高密碼的強(qiáng)度，應(yīng)該讓明文結(jié)構(gòu)在密文中盡量少出現(xiàn)多表代換密碼和多字母代換密碼能夠減少這種密文字母和明文字母之間的對應(yīng)關(guān)系多表代換密碼是對每個(gè)明文字母信息采用不同的單表代換

2024/4/5Ch3(1)-對稱加密技術(shù)119如果明文字母序列為m=m1m2…，令f=f1,f2,…為代換序列，則對應(yīng)的密文字母序列為：

C=Ek(m)=f1(m1)f2(m2)

…

若代換系列為非周期無限序列,則相應(yīng)的密碼為非周期多表代換密碼這類密碼對每個(gè)明文字母都采用不同的代換表或密鑰進(jìn)行加密，稱作是一次一密密碼(one-timepadcipher),這是一種在理論上唯一不可破的密碼實(shí)際中經(jīng)常采用周期多表代換密碼，它通常只使用有限的代換表，代換表被重復(fù)使用以完成對消息的加密2024/4/5Ch3(1)-對稱加密技術(shù)120周期多表代換密碼此時(shí)代換表系列為：

f=f1,f2,…,fd,f1,f2,…,f