信息安全原理與技術 課件 第1、2章 引言、-數學基礎

信息安全原理與技術第3版第1章引言主要知識點：

--安全攻擊

--安全機制

--安全目標與安全需求

--安全服務模型

--安全目標、需求、服務和機制之間的關系

--信息安全模型

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

Theartofwarteachesustorelynotonthelikelihoodoftheenemy'snotcoming,butonourownreadinesstoreceivehim;notonthechanceofhisnotattacking,butratheronthefactthatwehavemadeourpositionunassailable.

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

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

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

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

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

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

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

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

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

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

--密鑰管理：該服務表示以安全的方式管理密鑰。密鑰常常用于鑒別一個實體

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

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

--受保護的通信：該服務是保護實體之間的通信

--認證（Authentication）：保證通信的實體是它所聲稱的實體，也就是驗證實體身份

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

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

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

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

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

--入侵檢測(Intrusiondetection):

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

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

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

安全機制安全機制安全機制安全服務安全服務安全服務安全服務安全需求安全需求安全目標2024/4/5Ch1-引言19安全目標、需求、服務和機制之間的關系全部安全需求的實現才能達到安全目標不同的安全服務的聯合能夠實現不同的安全需求一個安全服務可能是多個安全需求的組成要素同樣，不同的安全機制聯合能夠完成不同的安全服務一個安全機制也可能是多個安全服務的構成要素表1.1表示了一些安全服務和安全需求之間的關系2024/4/5Ch1-引言202024/4/5Ch1-引言21表1.1說明了不是所有的安全需求都強制性地要求所有安全服務但是這些安全服務并不是完全可以忽略因為這些安全服務可能間接地使用如上表中的鑒別和密鑰管理兩個安全服務僅僅是完整性、保密性和可追溯性所要求的，不是可用性和保障必須的，但可用性是依賴于完整性和保密性。保障則與可用性、完整性、保密性和可追溯性相關所以一個密鑰管理服務將影響所有的安全需求2024/4/5Ch1-引言22信息安全模型-網絡安全模型

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

--設計一個恰當的安全變換算法，該算法應有足夠強安全性，不會被攻擊者有效地攻破。

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

--設計分配和共享秘密信息的方法。

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

網絡層的安全協(xié)議：IPSec

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

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

--數論

--代數基礎

--計算復雜性理論

--單向函數

2024/4/5Ch2-數學基礎28因子設Z表示全體整數所構成的集合。定義2.1

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

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

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

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

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

=rjqj+1最后一個不為0的余數rj就是a和b的最大公因子2024/4/5Ch2-數學基礎30例2.1

求gcd(1970，1066)用歐幾里德算法的計算過程如下：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-數學基礎31素數定義2.4

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

為素數，否則為合數

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

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

2024/4/5Ch2-數學基礎32同余定義2.8

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

同余具有下面的性質：(1)若a≡b(modm)，則則m|(b-a)。反過來，若m|(b-a)，則a≡b(modm)(2)如果a=km+b(k為整數)，則a≡b(modm)(3)每個整數恰與0,1,…，m-1這m個整數中的某一個對模m同余(4)同余關系是一種等價關系(5)a≡b(modm)當且僅當amodm=bmodm2024/4/5Ch2-數學基礎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-數學基礎34模運算

求余運算稱為模運算,下面是模運算的一些性質。

(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

在模運算中，加法單位元是0，(0+a)modm=amodm乘法單位元是1，(1×a)modm=amodm2024/4/5Ch2-數學基礎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的乘法逆元。加法一定存在逆元，乘法不一定存在逆元。在密碼學特別是非對稱密碼體制中，常常需要求模逆元，求模逆元就是求乘法逆元。即尋找一個x，使得a×x

≡1modm成立求模逆元問題很困難，有時有結果，有時沒有結果利用擴展歐幾里德算法能夠計算出模逆元2024/4/5Ch2-數學基礎36模8運算的例子

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

2024/4/5Ch2-數學基礎372024/4/5Ch2-數學基礎38模8的加法逆元和乘法逆元

對每一個x都有一個對應的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-數學基礎39快速指數模運算

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

(1)a

e,b

m,c

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

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

(a÷2),b

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

(a-1),c

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

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

對于任何互素的兩個整數a和n，有

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

2≡1(modp)有一解，那么p不是素數2024/4/5Ch2-數學基礎44Miller-Rabin素性概率檢驗算法WITNESS(a,n)

(1)將(n-1)表示為二進制形式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-數學基礎45算法有兩個輸入，n是待檢驗的數，a是小于n的整數。如果算法的返回值為TRUE，則n肯定不是素數，如果返回值為FALSE，則n有可能是素數。

for循環(huán)后，有d=an-1modn，由費馬定理可知，若n為素數，則d為1，因此若d

1，則n不是素數，所以返回TRUE。因為n-1≡-1modn，所以x

1，x

n-1，表示x

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

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

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

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

模m的本原根存在的必要條件是m=2,4,pa,或者2pa，此處p是奇素數a12478111314Ord7a142442422024/4/5Ch2-數學基礎49本原根的測試

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

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

是一個本原根。2024/4/5Ch2-數學基礎50例2.9

假設p=11,檢驗2和3是否是一個本原根。解：當p=11時,p-1=10，p-1有兩個素因子2和5，現測試2是否是一個本原根。

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

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

模指數運算的逆問題就是找出一個數的離散對數，即求解x，使得

ax

≡bmodn定義2.17（離散對數）對于一個整數b和素數n的一個本原根a，可以找到唯一的指數x，使得b≡ax

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

2024/4/5Ch2-數學基礎53群

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

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

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

(M1)乘法的封閉性：如果a和b都屬于R，則ab也屬于R。(M2)乘法的結合律：對于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)的基礎上，滿足以下公理的環(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-數學基礎55域

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

對任意素數p和正整數n，存在pn階的有限域，記為GF(pn)。當時n=1，有限域GF(p)也稱素域。在密碼學中，最常用的域一般是素域GF(p)或者階為2m的GF(2m)域2024/4/5Ch2-數學基礎57有限域GF(p)

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

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

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

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

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

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

(3)若存在次數大于或者等于1的q(x)和b(x)，使a(x)=q(x)b(x)，則稱a(x)為可約多項式，否則稱a(x)為不可約多項式（也稱既約多項式）2024/4/5Ch2-數學基礎65例如，GF(2)上的多項式是可約多項式，因為。而多項式則是不可約多項式，因為它沒有一個因式2024/4/5Ch2-數學基礎66有限域GF(2n)

為pn模的模運算不一定能產生域用不可約多項式可以構造一個域

對于F[x]中的每個不可約多項式p(x)，可以構造一個域F[x]

p(x)

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

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

其中ai

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

2024/4/5Ch2-數學基礎67定義F[x]

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

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

(1)該運算遵循基本代數規(guī)則中的普通多項式運算規(guī)則

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

p(x)中所有次數小于n的多項式表示為：系數ai是二進制數，該多項式可以由它的n個二進制系數唯一地表示。因此GF(2n)中的每個多項式都可以表示成一個n位的二進制整數。2024/4/5Ch2-數學基礎69高級加密標準中的有限域GF(28)上運算不可約多項式為假設多項式加法運算過程為=乘法運算過程為：2024/4/5Ch2-數學基礎70由于a(x)和b(x)相乘的多項式次數大于n，將它們相乘結果再除不可約多項式p(x)，可得商為x5+x3，余數為x7+x6+1，因此用十六進制表示為{57}{83}={C1}用二進制表示為=(11000001)說明：在上面的十六進制表示中，是用一個十六進制字符表示4位二進制數，一個字節(jié)的二進制數用括號括起來的兩個十六進制字符表示2024/4/5Ch2-數學基礎71從上面的