【1】第二章 密碼學(xué)基礎(chǔ)1

1、目錄v2.1 密碼學(xué)的基本知識(shí)密碼學(xué)的基本知識(shí)v2.2 對(duì)稱密碼體制對(duì)稱密碼體制v2.3 密碼學(xué)的數(shù)學(xué)基礎(chǔ)密碼學(xué)的數(shù)學(xué)基礎(chǔ)v2.4 公鑰密碼體制公鑰密碼體制密碼學(xué)的基本概念是經(jīng)過偽裝后的明文是經(jīng)過偽裝后的明文c。全體可能。全體可能出現(xiàn)的密文集合稱為出現(xiàn)的密文集合稱為密文空間密文空間C密文密文未經(jīng)過加密的原始信息稱為明文未經(jīng)過加密的原始信息稱為明文m，明文的全體稱為，明文的全體稱為明文空間明文空間 M明文明文由明文空間、密文空間、密碼方由明文空間、密文空間、密碼方案和密鑰空間組成案和密鑰空間組成密碼密碼系統(tǒng)系統(tǒng)密碼學(xué)的基本概念密碼學(xué)的基本概念密碼學(xué)的基本概念(2)加密和解密算法的操作在稱為密加密

2、和解密算法的操作在稱為密鑰（鑰（k）的元素控制下進(jìn)行。密）的元素控制下進(jìn)行。密鑰的全體稱為鑰的全體稱為密鑰空間（密鑰空間（K）密鑰密鑰確切地描述了加密變換和解密變確切地描述了加密變換和解密變換的具體規(guī)則換的具體規(guī)則密碼密碼方案方案加密算法加密算法對(duì)明文進(jìn)行加密時(shí)對(duì)明文進(jìn)行加密時(shí)所使用的規(guī)則的描所使用的規(guī)則的描述述(m)解密算法解密算法對(duì)密文進(jìn)行還原時(shí)對(duì)密文進(jìn)行還原時(shí)所使用的規(guī)則所使用的規(guī)則D(c)保密通信系統(tǒng)的基本模型加密算法解密算法密碼分析者加密密鑰Ke解密密鑰Kd竊聽干擾明文明文m明文明文m密文密文c有了密鑰的概念后，加密的過程：有了密鑰的概念后，加密的過程：c=EKe(m)，解密的過程，

3、解密的過程:m=DKd(c)，其中，其中mM，cC被動(dòng)攻擊和主動(dòng)攻擊v密碼分析者（密碼分析者（Cryptanalyst）又稱攻擊者，可）又稱攻擊者，可采用搭線竊聽等方式直接獲得未經(jīng)加密的明文采用搭線竊聽等方式直接獲得未經(jīng)加密的明文或加密后的密文，并分析得知明文。這種對(duì)密或加密后的密文，并分析得知明文。這種對(duì)密碼系統(tǒng)的攻擊手段稱為碼系統(tǒng)的攻擊手段稱為被動(dòng)攻擊被動(dòng)攻擊（Passive attack），），特點(diǎn)：不破壞原始信息特點(diǎn)：不破壞原始信息 v攻擊者還可以采用刪除、更改、增添、重放、攻擊者還可以采用刪除、更改、增添、重放、偽造等手段主動(dòng)向系統(tǒng)注入假信息，這種對(duì)密偽造等手段主動(dòng)向系統(tǒng)注入假信息，

4、這種對(duì)密碼系統(tǒng)的攻擊手段稱為碼系統(tǒng)的攻擊手段稱為主動(dòng)攻擊主動(dòng)攻擊（Active attack） 被動(dòng)攻擊和主動(dòng)攻擊形式形式威脅威脅特點(diǎn)特點(diǎn)被動(dòng)攻擊被動(dòng)攻擊竊聽竊聽流量分析流量分析機(jī)密性機(jī)密性不破壞原始不破壞原始信息信息難于發(fā)現(xiàn)難于發(fā)現(xiàn)主動(dòng)攻擊主動(dòng)攻擊篡改、偽造篡改、偽造重放、否認(rèn)重放、否認(rèn)完整性完整性易于探測(cè)但易于探測(cè)但卻難于防范卻難于防范 拒絕服務(wù)拒絕服務(wù)可用性可用性密碼體制的分類 v1. 按照密碼的發(fā)展歷史分類按照密碼的發(fā)展歷史分類密碼可分為密碼可分為古典密碼古典密碼和和近現(xiàn)代密碼近現(xiàn)代密碼 v2.按照需要保密的內(nèi)容分類按照需要保密的內(nèi)容分類 根據(jù)密碼體制的密碼算法是否需要保密，可分根據(jù)密

5、碼體制的密碼算法是否需要保密，可分為為受限制的算法受限制的算法和和基于密鑰的算法基于密鑰的算法v1883年年Kerchoffs第一次明確提出了編碼的原則，第一次明確提出了編碼的原則，即加密算法應(yīng)建立在即加密算法應(yīng)建立在算法的公開算法的公開不影響明文和不影響明文和密鑰的安全的基礎(chǔ)上密鑰的安全的基礎(chǔ)上 密碼體制的分類v3. 根據(jù)加密和解密所使用的密鑰是否相同根據(jù)加密和解密所使用的密鑰是否相同對(duì)稱密碼體制對(duì)稱密碼體制 公鑰密碼體制公鑰密碼體制：也稱為非對(duì)稱密碼體制：也稱為非對(duì)稱密碼體制對(duì)稱密碼體制對(duì)稱密碼體制 對(duì)稱密碼體制對(duì)稱密碼體制Symmetric Key Cryptosystem加密密鑰加密密

6、鑰=解密密鑰解密密鑰密鑰必須保密密鑰必須保密公鑰密碼體制公鑰密碼體制公鑰密碼體制公鑰密碼體制Public Key Cryptosystem加密密鑰加密密鑰解密密鑰解密密鑰 加密密鑰為公鑰（加密密鑰為公鑰（Public Key），公鑰無需保密），公鑰無需保密 解密密鑰為私鑰（解密密鑰為私鑰（Private Key）密碼體制的分類v4. 根據(jù)對(duì)明文的處理方式根據(jù)對(duì)明文的處理方式 分組密碼分組密碼算法和算法和流密碼流密碼算法算法 v5. 根據(jù)是否能進(jìn)行可逆的加密變換根據(jù)是否能進(jìn)行可逆的加密變換分為單向函數(shù)密碼體制和雙向變換密碼體分為單向函數(shù)密碼體制和雙向變換密碼體制制 密碼學(xué)的發(fā)展歷程密碼學(xué)的發(fā)展歷

7、程密碼學(xué)的發(fā)展歷程古典密碼古典密碼體制體制近現(xiàn)代密近現(xiàn)代密碼體制碼體制Shannon的保密的保密通信的信通信的信息理論息理論 密碼學(xué)的密碼學(xué)的新方向新方向Diffie和和Hellman密碼學(xué)密碼學(xué)的新方向的新方向 密碼分析與密碼系統(tǒng)的安全性密碼系統(tǒng)的安全性取決于密碼系統(tǒng)的安全性取決于(1) 所使用的密碼算法的保密強(qiáng)度所使用的密碼算法的保密強(qiáng)度(2) 密碼算法以外不安全的因素密碼算法以外不安全的因素因此必須同時(shí)完善技術(shù)與管理上的要因此必須同時(shí)完善技術(shù)與管理上的要求，才能保證整個(gè)密碼系統(tǒng)的安全求，才能保證整個(gè)密碼系統(tǒng)的安全密碼分析研究如何分析和破解密碼密碼分析的方法密碼分析密碼分析的方法的方法數(shù)學(xué)

8、分析攻擊（數(shù)學(xué)分析攻擊（Mathe-matical analysis attack）統(tǒng)計(jì)分析攻擊（統(tǒng)計(jì)分析攻擊（Statistical analysis attack）窮舉分析攻擊（窮舉分析攻擊（Exhaustive attack）密碼分析攻擊的類型v假設(shè)密碼分析者已經(jīng)知道加密算法，根據(jù)密碼假設(shè)密碼分析者已經(jīng)知道加密算法，根據(jù)密碼分析者對(duì)明文、密文等資源的掌握程度：分析者對(duì)明文、密文等資源的掌握程度：v1）唯密文攻擊（）唯密文攻擊（Ciphtext-only attack）v2）已知明文攻擊（）已知明文攻擊（Plaintext-known attack） v3）選擇明文攻擊（）選擇明文攻擊（C

9、hosen-plaintext attack）v4）選擇密文攻擊（）選擇密文攻擊（ChosenCiphtext attack） 現(xiàn)代加密算法的設(shè)計(jì)目標(biāo)是要能抵抗現(xiàn)代加密算法的設(shè)計(jì)目標(biāo)是要能抵抗住選擇明文攻擊住選擇明文攻擊 密碼系統(tǒng)安全性的層次v無條件安全（無條件安全（Unconditionally Secure）v計(jì)算上安全（計(jì)算上安全（Computationally Secure）v可證明安全（可證明安全（Provable Secure） 一般認(rèn)為，密碼系統(tǒng)只要能達(dá)到計(jì)算上安一般認(rèn)為，密碼系統(tǒng)只要能達(dá)到計(jì)算上安全就是安全的全就是安全的 目錄v2.1 密碼學(xué)的基本知識(shí)密碼學(xué)的基本知識(shí)v2.2

10、對(duì)稱密碼體制對(duì)稱密碼體制v2.3 密碼學(xué)的數(shù)學(xué)基礎(chǔ)密碼學(xué)的數(shù)學(xué)基礎(chǔ)v2.4 公鑰密碼體制公鑰密碼體制對(duì)稱密碼體制v對(duì)稱密碼體制，即對(duì)稱密碼體制，即加密密鑰與解密密鑰相同加密密鑰與解密密鑰相同的的密碼體制，這種體制只要知道加（解）密算法，密碼體制，這種體制只要知道加（解）密算法，就可以反推解（加）密算法就可以反推解（加）密算法 v在在1976年公鑰密碼算法提出以前的所有加密算年公鑰密碼算法提出以前的所有加密算法都是對(duì)稱密碼體制法都是對(duì)稱密碼體制 v對(duì)稱密碼體制可分為分組密碼和流密碼對(duì)稱密碼體制可分為分組密碼和流密碼 v本節(jié)將介紹的古典密碼、分組密碼和流密碼本節(jié)將介紹的古典密碼、分組密碼和流密碼古

11、典密碼置換（換位）是對(duì)明文中的元素進(jìn)行置換（換位）是對(duì)明文中的元素進(jìn)行換位排列，可以證明置換是替代的一換位排列，可以證明置換是替代的一種特殊形式種特殊形式置換置換替代是將明文中的每個(gè)元素映射為另替代是將明文中的每個(gè)元素映射為另一個(gè)元素，明文元素被其他元素所替一個(gè)元素，明文元素被其他元素所替代而形成密文代而形成密文替代替代采用的加密思想：采用的加密思想：替代替代和和置換置換對(duì)于明文“dog”，使用替代技術(shù)加密：結(jié)果可能是“eph”，使用置換技術(shù)加密：結(jié)果可能是“ogd” 討論下面密碼算法的加密思想vScytale 密碼密碼v棋盤密碼棋盤密碼123451abcde2fghijk3lmnop4qrs

12、tu5vwxyz弗納姆密碼弗納姆密碼例：例： Aice欲將明文欲將明文m=OK，借由弗納姆密碼加密，借由弗納姆密碼加密成密文成密文c，傳遞給，傳遞給Bob。假設(shè)密鑰為。假設(shè)密鑰為k=DA。ASCIImOK(79,75)10011111001011ASCIIkDA(68,65)10001001000001c00010110001010c00010110001010k10001001000001DAm10011111001011OK10011,00110 ci=(mi+ki) mod 2幾種典型的古典密碼v移位密碼（又稱凱撒密碼）移位密碼（又稱凱撒密碼）v一般單表替代密碼一般單表替代密碼v仿射密碼

13、仿射密碼v密鑰短語密碼密鑰短語密碼v維吉尼亞（維吉尼亞（Vigenere）密碼）密碼v希爾（希爾（Hill）密碼）密碼v置換密碼置換密碼移位密碼 v加密變換：加密變換：Ek(m)=m+k(mod 26) mM, kKv解密變換：解密變換：Dk(c)=c-k(mod 26) cC, kKv很容易利用窮舉法將密文解密，最多嘗試很容易利用窮舉法將密文解密，最多嘗試25次，次，就能找到密文對(duì)應(yīng)的明文信息就能找到密文對(duì)應(yīng)的明文信息 明文明文：youth密文：密文：brxwk將明文每個(gè)字母前移三位將明文每個(gè)字母前移三位 移位密碼加密示例移位密碼加密示例密鑰產(chǎn)生）Alice與Bob協(xié)定編碼方式為明文字母后移

14、4位，即加密密鑰及解密密鑰同為K=4。Alice將明文將明文“gaul is divided into three part”轉(zhuǎn)為數(shù)字代碼：轉(zhuǎn)為數(shù)字代碼：（6，0，20，11，8，18，3，8，21，8，3，4，3，8，13，19，14，19，7，17，4，4，15，0，17，19）。）。使用使用加密函數(shù)加密函數(shù)E（m） m+k=m+4（mod 26）計(jì)算得：（計(jì)算得：（10，4，24，15，12，22，7，12，25，12，7，8，7，12，17，23，17，23，11，21，8，8，19，4，21，23）即即密文密文“K，E，Y，P，M，Z，M，H，I，H，M，R，X，R，X，L，V，I，

15、I，T，E，V，X”。 2.一般單表替代密碼v明文消息中的每個(gè)字母不是同時(shí)移動(dòng)相同的位明文消息中的每個(gè)字母不是同時(shí)移動(dòng)相同的位數(shù)，而是根據(jù)一張?zhí)娲硎褂秒S機(jī)替換數(shù)，而是根據(jù)一張?zhí)娲硎褂秒S機(jī)替換 一張一般單表替代密碼的映射一張一般單表替代密碼的映射表表明文 abcdefghijklm密文 qwertyuiopasd明文 nopqrstuvwxyz密文 fghjklzxcvbnmc=Ek(m)=(m)m=Dk(c)=-1(c)3. 仿射密碼v加密變換為：加密變換為：vc=Ek(m)= (k1m+k2) mod 26v相應(yīng)的解密變換為：相應(yīng)的解密變換為：vm=Dk(c)=k1-1(c-k2) mo

16、d 26v注意：注意：k1必須和必須和26互素互素，如果不互素，例如取，如果不互素，例如取k1=2，則明文，則明文m=mi和和m=mi+13兩個(gè)字符都將被兩個(gè)字符都將被映射成同一個(gè)密文字符映射成同一個(gè)密文字符仿射密碼示例Alice與Bob事先協(xié)定一把密鑰K=(3,8)其中g(shù)cd(3,26)=1E(.)maffine(0,5,5,8,13,4)(8,23,23,6,21,20)IXXGVUc E(m)3m8 (mod26)1D(c)3 (c8)9(c8) (mod26)D(.)cIXXGVU(8,23,23,6,21,20)(0,5,5,8,13,4)affinem 密鑰短語密碼v密鑰短語密碼選

17、用一個(gè)英文短語或單詞作密鑰短語密碼選用一個(gè)英文短語或單詞作為密鑰，如密鑰為為密鑰，如密鑰為university時(shí)，先去掉時(shí)，先去掉重復(fù)字母重復(fù)字母i，成為，成為universty明文字母a b c d e f g h i j k l m n o p q r s t u v w x y z密鑰字母u n i v e r s t y a b c d f g h j k l m o p q w x z總結(jié)：?jiǎn)伪硖娲艽a的特點(diǎn)v以上幾種密碼都是單表替代密碼，特點(diǎn)如下：以上幾種密碼都是單表替代密碼，特點(diǎn)如下：這個(gè)特點(diǎn)使其密文中單字母出現(xiàn)的頻率分布這個(gè)特點(diǎn)使其密文中單字母出現(xiàn)的頻率分布與明文中的相同，因此

18、任何單表替代密碼都與明文中的相同，因此任何單表替代密碼都經(jīng)不起統(tǒng)計(jì)分析。經(jīng)不起統(tǒng)計(jì)分析。明文和密文是明文和密文是一對(duì)一的映射關(guān)系一對(duì)一的映射關(guān)系。Ef (x0,x1,x2,)=(f(x0),f(x1),f(x2),) 對(duì)單表加密算法的統(tǒng)計(jì)分析字母百分比字母百分比a8.2n6.8b1.5o7.5c2.8p1.9d4.2q0.1e12.7r6.0f2.2s6.3g2.0t9.0h6.1u2.8i7.0v1.0j0.1w2.4k0.8x2.0l4.0y0.1m2.4z0.1另外最常出現(xiàn)的雙字母組合為：另外最常出現(xiàn)的雙字母組合為： th(3.15%)，he(2.51%)，an(1.72)，in(1.6

19、9%)，er(1.54%)，re(1.48%)，es(1.45%)，on(1.45%)，ea(1.31%)，ti(1.28)，at(1.24%)，st(a.21%)，en(1.20%)，nd(1.18%)等。等。最常出現(xiàn)的三字母組合最常出現(xiàn)的三字母組合（Trigram）為：）為：the，ing，and，her，ere ，ent，tha，。多表替代密碼v多表替代密碼使用從明文字母到密文字母的多多表替代密碼使用從明文字母到密文字母的多個(gè)映射來隱藏單字母出現(xiàn)的頻率分布個(gè)映射來隱藏單字母出現(xiàn)的頻率分布 v同一個(gè)明文字母將對(duì)應(yīng)不同的密文字母同一個(gè)明文字母將對(duì)應(yīng)不同的密文字母 Ef (x0,x1,x2,)

20、=(f0(x0),f1(x1),f2(x2),) 維吉尼亞（Vigenere）密碼v維吉尼亞密碼：一種典型的維吉尼亞密碼：一種典型的多表替代密碼多表替代密碼，該，該密碼體制有一個(gè)參數(shù)密碼體制有一個(gè)參數(shù)n，表示采用，表示采用n位長(zhǎng)度的字位長(zhǎng)度的字符串（例如一個(gè)英文單詞）作為密鑰。符串（例如一個(gè)英文單詞）作為密鑰。 v設(shè)密鑰設(shè)密鑰k=k1k2kn，明文，明文M=m1m2mn，則加密，則加密變換為：變換為：vEk(m1,m2,mn)=(m1+k1mod 26, m2+k2mod 26 ,mn+knmod 26 ) 維吉尼亞密碼舉例v例例2.2 設(shè)明文為設(shè)明文為“killthem”密鑰為密鑰為“gun

21、”，試，試用維吉尼亞密碼對(duì)明文進(jìn)行加密。用維吉尼亞密碼對(duì)明文進(jìn)行加密。v加密密鑰：加密密鑰：k=gun=(6,20,13)明文對(duì)應(yīng)的數(shù)字為明文對(duì)應(yīng)的數(shù)字為 1081111197412密鑰對(duì)應(yīng)的數(shù)字密鑰對(duì)應(yīng)的數(shù)字6201362013620相加取余變換后：相加取余變換后： 16224171320106對(duì)應(yīng)的密文是：對(duì)應(yīng)的密文是：hcyrnvwg因 密文為：密文為：hcyrnvwg破解維吉尼亞密碼v密文為：密文為：hcyrnvwgcxgtu h n c u c v x y w g r g t關(guān)鍵是如何確定密鑰長(zhǎng)度關(guān)鍵是如何確定密鑰長(zhǎng)度n希爾密碼v希爾密碼：利用矩陣變換來對(duì)信息實(shí)現(xiàn)加密。希爾密碼：利用

22、矩陣變換來對(duì)信息實(shí)現(xiàn)加密。v數(shù)學(xué)定義：設(shè)數(shù)學(xué)定義：設(shè)m是一個(gè)正整數(shù)，令是一個(gè)正整數(shù)，令M=E=(Z26)m，密鑰密鑰Kmm=定義在定義在Z26上的上的mm矩陣矩陣，其中，其中K的行列式值必須和的行列式值必須和26互素互素，否則不存在，否則不存在K的逆矩的逆矩陣陣K-1。v對(duì)任意的密鑰對(duì)任意的密鑰Kmm，定義加密，定義加密/解密變換為解密變換為Ek(x)= Kmmx mod 26Dk(y)= K-1mmy mod 26希爾（希爾（HillHill）密碼舉例）密碼舉例首先決定所用矩陣的大小，譬如是2211E34其中E的行列式值detE必須與26互素，否則不存在E的反矩陣。m=Hillhl711Mi

23、l81111711EM3 481115 2253 7715 22(mod 26)12515 22pwC125bzc=pbwz如何求矩陣的逆矩陣vA*為為A的伴隨矩陣。的伴隨矩陣。*|11AAA代數(shù)余子式代數(shù)余子式Hill密碼解密過程密碼解密過程計(jì)算加密矩陣的逆矩陣，再進(jìn)行模運(yùn)算（計(jì)算加密矩陣的逆矩陣，再進(jìn)行模運(yùn)算（mod 26），），得解密矩陣得解密矩陣41D(mod 26)314115 22EM3112559534441711(mod 26)811hlil Hill密碼的特點(diǎn)：vHill密碼完全隱藏了單字母的頻率密碼完全隱藏了單字母的頻率v能比較好地抵抗頻率法的分析，對(duì)抗僅有能比較好地抵抗頻

24、率法的分析，對(duì)抗僅有密文的攻擊強(qiáng)度較高密文的攻擊強(qiáng)度較高v易受選擇明文攻擊易受選擇明文攻擊威脅替代密碼的因素威脅替代密碼的因素v頻率分析頻率分析v考慮最可能出現(xiàn)的字母及單詞考慮最可能出現(xiàn)的字母及單詞v重復(fù)結(jié)構(gòu)分析（針對(duì)多表替代密碼）重復(fù)結(jié)構(gòu)分析（針對(duì)多表替代密碼）va a a a a a a a a avg u n g u n g u n g置換密碼v置換（置換（Permutation）密碼通過改變明文消息中密碼通過改變明文消息中各字符出現(xiàn)的相對(duì)位置，但明文消息字符本身各字符出現(xiàn)的相對(duì)位置，但明文消息字符本身的取值不變。置換密碼的一個(gè)顯著特點(diǎn)是它的的取值不變。置換密碼的一個(gè)顯著特點(diǎn)是它的明文集

25、合和密文集合完全相同明文集合和密文集合完全相同 列置換密碼列置換密碼 螺旋置換密碼螺旋置換密碼ScytalePermutation of characters400 BCSPARTA【例例】明文為明文為cryptography is an applied science。密鑰是密鑰是creny密鑰中字母在字母表中的出現(xiàn)次序密鑰中字母在字母表中的出現(xiàn)次序14235密文為：密文為： cohnii yripdn paspsc rgyaee tpalce。密鑰 14235cryptographyisanappliedscience列置換密碼實(shí)例列置換密碼實(shí)例螺旋置換密碼v明文：明文：This is a

26、n examplev密文：密文：xxxeasilnthpexamxxxeAsilnthpexam置換密碼v置換密碼：置換密碼：Ek(dog)=ogd可用如下希爾密碼實(shí)現(xiàn)可用如下希爾密碼實(shí)現(xiàn) dgogodxKxEmmk001100010這證明了置換密碼可轉(zhuǎn)換為替代密碼這證明了置換密碼可轉(zhuǎn)換為替代密碼古典密碼分類匯總圖 替代密碼替代密碼單表替代密碼單表替代密碼多表替代密碼多表替代密碼移位密碼仿射密碼密鑰短語密碼一般單表替代密碼維吉尼亞密碼希爾密碼置換密碼置換密碼2.2.2 分組密碼v分組密碼體制是目前商業(yè)領(lǐng)域中比較重要而流分組密碼體制是目前商業(yè)領(lǐng)域中比較重要而流行的一種加密體制，它廣泛地應(yīng)用于數(shù)據(jù)

27、的保行的一種加密體制，它廣泛地應(yīng)用于數(shù)據(jù)的保密傳輸、加密存儲(chǔ)等應(yīng)用場(chǎng)合。密傳輸、加密存儲(chǔ)等應(yīng)用場(chǎng)合。 v加密時(shí)，先對(duì)明文分組，每組長(zhǎng)度都相同，然加密時(shí)，先對(duì)明文分組，每組長(zhǎng)度都相同，然后對(duì)分組加密得到等長(zhǎng)的密文，分組密碼的特后對(duì)分組加密得到等長(zhǎng)的密文，分組密碼的特點(diǎn)是加密密鑰與解密密鑰相同。點(diǎn)是加密密鑰與解密密鑰相同。 v如果明文不是分組長(zhǎng)的倍數(shù)，則要填充如果明文不是分組長(zhǎng)的倍數(shù)，則要填充分組密碼算法的要求將將大的明文分組再分成幾個(gè)小段大的明文分組再分成幾個(gè)小段，分別完，分別完成各個(gè)小段的加密置換，最后進(jìn)行并行操作成各個(gè)小段的加密置換，最后進(jìn)行并行操作強(qiáng)化密碼算法的措施強(qiáng)化密碼算法的措施采用采

28、用乘積密碼乘積密碼技術(shù)。乘積密碼就是以某種技術(shù)。乘積密碼就是以某種方式連續(xù)執(zhí)行兩個(gè)或多個(gè)密碼變換方式連續(xù)執(zhí)行兩個(gè)或多個(gè)密碼變換分組長(zhǎng)度分組長(zhǎng)度m足夠大足夠大 密鑰空間足夠大密鑰空間足夠大密碼變換必須足夠復(fù)雜密碼變換必須足夠復(fù)雜Feistel網(wǎng)絡(luò)示意圖網(wǎng)絡(luò)示意圖111,iiiiiiLRRLF RKvDES的歷史的歷史v1971 IBM，由由Horst Feistel 領(lǐng)導(dǎo)的密碼研領(lǐng)導(dǎo)的密碼研究項(xiàng)目組研究出究項(xiàng)目組研究出LUCIFER算法。并應(yīng)用于算法。并應(yīng)用于商業(yè)領(lǐng)域。商業(yè)領(lǐng)域。v1973美國(guó)標(biāo)準(zhǔn)局征求標(biāo)準(zhǔn)，美國(guó)標(biāo)準(zhǔn)局征求標(biāo)準(zhǔn)，IBM提交結(jié)果，提交結(jié)果，v在在1977年，被選為數(shù)據(jù)加密標(biāo)準(zhǔn)。年，

29、被選為數(shù)據(jù)加密標(biāo)準(zhǔn)。v1994年，美國(guó)決定年，美國(guó)決定1998年年12月以后不再使月以后不再使用用DES算法算法 數(shù)據(jù)加密標(biāo)準(zhǔn)（數(shù)據(jù)加密標(biāo)準(zhǔn)（DES)DES)數(shù)據(jù)加密標(biāo)準(zhǔn)DES vDES是一種分組密碼算法，它將明文從算法的是一種分組密碼算法，它將明文從算法的一端輸入，將密文從另一端輸出。一端輸入，將密文從另一端輸出。v由于采用的是對(duì)稱密鑰，因此加密和解密使用由于采用的是對(duì)稱密鑰，因此加密和解密使用相同的算法和密鑰相同的算法和密鑰v并且加密和解密算法是公開的，系統(tǒng)的安全性并且加密和解密算法是公開的，系統(tǒng)的安全性完全依賴于密鑰的保密完全依賴于密鑰的保密 DES分組的原理vDES對(duì)數(shù)據(jù)進(jìn)行加密時(shí)，首

30、先將數(shù)據(jù)切分成對(duì)數(shù)據(jù)進(jìn)行加密時(shí)，首先將數(shù)據(jù)切分成64位的明文分組位的明文分組v它使用的密鑰為它使用的密鑰為64位，但有效密鑰長(zhǎng)度為位，但有效密鑰長(zhǎng)度為56位位（另有（另有8位用于奇偶校驗(yàn)）。輸出的密鑰分組也位用于奇偶校驗(yàn)）。輸出的密鑰分組也是是64位位v解密時(shí)的過程和加密時(shí)的類似，但密鑰的順序解密時(shí)的過程和加密時(shí)的類似，但密鑰的順序正好相反正好相反 DES的加密過程v（1）明文初始置換）明文初始置換 v（2）密鑰初始置換）密鑰初始置換 v（3）生成）生成16個(gè)個(gè)48位的子密鑰位的子密鑰 v（4）明文擴(kuò)展置換）明文擴(kuò)展置換 v（5）S盒替代盒替代 v（6）P盒置換盒置換 v（7）末置換）末置換

31、v（8）DES的解密的解密 vDES加密過程加密過程64位明文IP初始置換L0R0fK1L1R1fK2L15R15fK16左右交換R16L16逆初始置換IP164位密文LiRi1，RiLi1 f(Ri1，Ki)明文初始置換初始置換初始置換M=m1m2,m62m63,m64M=m58m50,m23m15,m7IP(M)由于由于M(64位位) =0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 對(duì)對(duì)M運(yùn)用運(yùn)用IP，故有，故有IP(64位位) = 1100 1100 0000 0000 1100 1100 1111 1111 11

32、11 0000 1010 1010將明文分成左右兩半vIP(64位位) = L0(32位位) + R0(32位位)v故故vL0 (32位位) = 1100 1100 0000 0000 1100 1100 1111 1111 R0 (32位位) = 1111 0000 1010 1010 1111 0000 1010 1010 密鑰初始置換 k1 （56 位） (48 位) ki （56 位） （48 位） 64 位密鑰置換選擇 1 C0（28 位） D0（28 位） 循環(huán)左移循環(huán)左移 C1（28 位） D1（28 位） 循環(huán)左移循環(huán)左移 Ci（28 位） Di（28 位）置換選擇 2置換選擇

33、 2密鑰表的計(jì)算邏輯循環(huán)左移：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 116輪輪子密鑰的生成子密鑰的生成第一步：生成16個(gè)子鑰(48位)v從而得到C1D1 C16D16：v C1 = 1110000110011001010101011111D1 = 1010101011001100111100011110 v C2 = 1100001100110010101010111111D2 = 0101010110011001111000111101 v C3 = 0000110011001010101011111111

34、D3 = 0101011001100111100011110101 v C4 = 0011001100101010101111111100D4 = 0101100110011110001111010101 v v C15 = 1111100001100110010101010111D15 = 1010101010110011001111000111 v C16 = 1111000011001100101010101111D16 = 0101010101100110011110001111 明文擴(kuò)展置換Li-1（32位位）Ri-1（32位位）Li（32位位）48位位擴(kuò)展置換擴(kuò)展置換E48位位子密

35、鑰子密鑰Ki（48位位）32位位S盒替代盒替代P盒置換盒置換Ri（32位位）Li=Ri-1對(duì)Ri-1進(jìn)行擴(kuò)展置換與密鑰Ki進(jìn)行異或運(yùn)算進(jìn)行S盒替代8個(gè)個(gè)S 盒的表盒的表 S1盒14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 70 15 7 4 14 2 13 1 10 6 12 11 9 5 3 84 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13S2盒15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 103 13 4 7 15 2 8 14 12 0

36、1 10 6 9 11 50 14 7 11 10 4 13 1 5 8 12 6 9 3 2 1513 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9S3盒10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 813 7 0 9 3 4 6 10 2 8 5 14 12 11 15 113 6 4 9 8 15 3 0 11 1 2 12 5 10 14 71 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12S4盒7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 1513 8 11 5 6 15 0 3 4 7

37、 2 12 1 10 14 910 6 9 0 12 11 7 13 15 1 3 14 5 2 8 43 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14S5盒2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 914 11 2 12 4 7 13 1 5 0 15 10 3 9 8 64 2 1 11 10 13 7 8 15 9 12 5 6 3 0 1411 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3S6盒12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 1110 15 4 2 7 12 9 5 6

38、 1 13 14 0 11 3 89 14 15 5 2 8 12 3 7 0 4 10 1 13 11 64 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13S7盒4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 113 0 11 7 4 9 1 10 14 3 5 12 2 15 8 61 4 11 13 12 3 7 14 10 15 6 8 0 5 9 26 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12S8盒13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 71 15 13 8 10 3 7 4

39、 12 5 6 11 0 14 9 27 11 4 1 9 12 14 2 0 6 10 13 15 3 5 82 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11P盒置換vLi = Ri-1 i=1,2,16vRi = Li-1 f ( Ri-1 , Ki )16 7 20 21 29 12 28 171 15 23 26 5 18 31 102 8 24 14 32 27 3 919 13 30 6 22 11 4 25對(duì)R16L16作末置換40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62

40、3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25DES加密的特點(diǎn)v綜合運(yùn)用了許多次置換和替代技術(shù)綜合運(yùn)用了許多次置換和替代技術(shù),從而達(dá)到了從而達(dá)到了混淆混淆和和擴(kuò)散擴(kuò)散的特點(diǎn)的特點(diǎn) v擴(kuò)散擴(kuò)散：將明文的統(tǒng)計(jì)特性散布到密文中。目的：將明文的統(tǒng)計(jì)特性散布到密文中。目的是使明文的每一位影響密文中多位的值是使明文的每一位影響密文中多位的值v混淆混淆：應(yīng)使得密鑰和明文以及密文之間的依賴：應(yīng)使得密鑰和明文以及密文之間的依賴關(guān)系相當(dāng)復(fù)雜

41、，以至于這種依賴性對(duì)密碼分析關(guān)系相當(dāng)復(fù)雜，以至于這種依賴性對(duì)密碼分析者來說是無法利用的。者來說是無法利用的。v采用了乘積密碼技術(shù)，將采用了乘積密碼技術(shù)，將R0加密后的所得結(jié)果加密后的所得結(jié)果R1再作為再作為L(zhǎng)2的輸入進(jìn)行加密的輸入進(jìn)行加密 DES算法的變形v利用兩個(gè)密鑰的三重利用兩個(gè)密鑰的三重DESv若若K1=K2，將可兼容單，將可兼容單DES算法算法K1K2K1原始明文密文1密文2最終密文加密加密解密其他分組密碼其他分組密碼 vAES高級(jí)加密標(biāo)準(zhǔn)高級(jí)加密標(biāo)準(zhǔn)（Advanced Encryption Standard）明文分組的長(zhǎng)度為明文分組的長(zhǎng)度為128比特，而密鑰長(zhǎng)度可以為比特，而密鑰長(zhǎng)度

42、可以為128、192、256比特比特vIDEA國(guó)際數(shù)據(jù)加密標(biāo)準(zhǔn)國(guó)際數(shù)據(jù)加密標(biāo)準(zhǔn)（International Data Encryption Algorithm）是最強(qiáng)大的數(shù)據(jù)）是最強(qiáng)大的數(shù)據(jù)加密標(biāo)準(zhǔn)之一加密標(biāo)準(zhǔn)之一 流密碼 v流密碼采用密鑰流生成器，從種子密鑰生成一流密碼采用密鑰流生成器，從種子密鑰生成一系列密鑰流來加密信息，每個(gè)明文字母被密鑰系列密鑰流來加密信息，每個(gè)明文字母被密鑰流中不同的密鑰字母加密流中不同的密鑰字母加密 安全信道安全信道種子密鑰種子密鑰z密鑰流產(chǎn)生器密鑰流產(chǎn)生器KGEki(mi)Dki(mi)密鑰流產(chǎn)生器密鑰流產(chǎn)生器KG種子密鑰種子密鑰z密文流密文流ci明文流明文流mi

43、明文流明文流mi密鑰密鑰ki密鑰密鑰ki流密碼的類型v流密碼的思想：模擬一次一密流密碼的思想：模擬一次一密v同步流密碼同步流密碼 ：密鑰流和明文流相互獨(dú)立；：密鑰流和明文流相互獨(dú)立； (如密鑰流是固定的，明文每次是變化的如密鑰流是固定的，明文每次是變化的)v異步流密碼異步流密碼： 密鑰流和明文流不相互獨(dú)立，密密鑰流和明文流不相互獨(dú)立，密鑰流的產(chǎn)生有密文或者明文的參與，會(huì)發(fā)生錯(cuò)鑰流的產(chǎn)生有密文或者明文的參與，會(huì)發(fā)生錯(cuò)誤傳播現(xiàn)象誤傳播現(xiàn)象同步流密碼v設(shè)維吉尼亞密碼的密鑰為設(shè)維吉尼亞密碼的密鑰為cipher，則密鑰長(zhǎng)度，則密鑰長(zhǎng)度d=6，將該密鑰作為流密碼的種子密鑰，將該密鑰作為流密碼的種子密鑰，v

44、密鑰流產(chǎn)生器產(chǎn)生密鑰流的規(guī)則為：第一次用密鑰流產(chǎn)生器產(chǎn)生密鑰流的規(guī)則為：第一次用該密鑰加密明文，然后將該密鑰每位循環(huán)右移該密鑰加密明文，然后將該密鑰每位循環(huán)右移一位。例如一位。例如v設(shè)種子密鑰設(shè)種子密鑰 z=cipher（2, 8, 15, 7, 4, 17），則），則在種子密鑰控制下產(chǎn)生的密鑰流在種子密鑰控制下產(chǎn)生的密鑰流Ki=（2,8,15,7,4,17,8,15,7,4,17,2,15,7,4,17,2,8,7,4,17,2,8,15）異步流密碼 v明文明文： t h i s i s a s a m p l ev密鑰：密鑰： c i p h e rv密鑰流：密鑰流：c i p h e r

45、 t h i s i s av密鑰與明文有關(guān)，若明文在傳輸中發(fā)生錯(cuò)誤，密鑰與明文有關(guān)，若明文在傳輸中發(fā)生錯(cuò)誤，則會(huì)導(dǎo)致密鑰也發(fā)生錯(cuò)誤，即錯(cuò)誤傳播現(xiàn)象則會(huì)導(dǎo)致密鑰也發(fā)生錯(cuò)誤，即錯(cuò)誤傳播現(xiàn)象目錄v2.1 密碼學(xué)的基本知識(shí)密碼學(xué)的基本知識(shí)v2.2 對(duì)稱密碼體制對(duì)稱密碼體制v2.3 密碼學(xué)的數(shù)學(xué)基礎(chǔ)密碼學(xué)的數(shù)學(xué)基礎(chǔ)v2.4 公鑰密碼體制公鑰密碼體制數(shù)論的基本概念 整除1. 整除整除v 設(shè)設(shè)a, b是兩個(gè)整數(shù)，其中是兩個(gè)整數(shù)，其中b0，如果存在另一整數(shù)，如果存在另一整數(shù)m使得等式使得等式a=mb成立，則稱成立，則稱b整除整除a，記為，記為b | a，并稱并稱b是是a的除數(shù)（或因子），的除數(shù)（或因子），a

46、為為b的倍數(shù)。的倍數(shù)。v 整除具有以下性質(zhì)：整除具有以下性質(zhì)：（1）若）若b | a，c | b，則，則c | a；（2）若）若a | 1，則，則a=1；若；若a | b且且b | a，則，則a=b；（3）對(duì)任一）對(duì)任一b(b0)，則，則b | 0；（4）若）若b | g，b | h，則對(duì)任意整數(shù)，則對(duì)任意整數(shù)m，n有有b | (mg+nh) 整除實(shí)例Q: 下面哪個(gè)是對(duì)的下面哪個(gè)是對(duì)的?1.77 | 72.7 | 773.24 | 244.0 | 245.24 | 0對(duì)對(duì)對(duì)數(shù)論的基本概念素?cái)?shù)v2. 素?cái)?shù)和合數(shù)素?cái)?shù)和合數(shù)v一個(gè)大于一個(gè)大于1且只能被且只能被1和它本身整除的整數(shù)，稱和它本身整除的整

47、數(shù)，稱為為素?cái)?shù)素?cái)?shù)(prime number)；否則，稱為；否則，稱為合數(shù)合數(shù)(composite)。例如：。例如：2、3、5、7、11就是素就是素?cái)?shù)。除數(shù)。除2之外所有的素?cái)?shù)必定都是奇數(shù)。之外所有的素?cái)?shù)必定都是奇數(shù)。 v對(duì)于素?cái)?shù)，有以下定理：對(duì)于素?cái)?shù)，有以下定理：v定理定理1.1 任一正整數(shù)任一正整數(shù)a都能分解成素?cái)?shù)乘積的形都能分解成素?cái)?shù)乘積的形式，并且此表示是唯一的。式，并且此表示是唯一的。ttpppa2121gcdv定理定理1.2 若若p是素?cái)?shù)，是素?cái)?shù)，p | ab，則，則p | a或或p | b。v如果整數(shù)如果整數(shù)a能整除整數(shù)能整除整數(shù)a1, a2, a3, , an，則稱，則稱a為為

48、這幾個(gè)整數(shù)的公因子。這幾個(gè)整數(shù)可能有多個(gè)這幾個(gè)整數(shù)的公因子。這幾個(gè)整數(shù)可能有多個(gè)公因子，其中最大的公因子叫公因子，其中最大的公因子叫最大公因子最大公因子（GCD，Greatest Common Divisor），記做），記做gcd(a1, a2, a3, , an)或或(a1, a2, a3, , an) v 若若p是素?cái)?shù)，是素?cái)?shù)，a是任意整數(shù)，則有是任意整數(shù)，則有p | a或或gcd(p, a)=1，即素?cái)?shù)與任意數(shù)之間只可能是整除或互，即素?cái)?shù)與任意數(shù)之間只可能是整除或互素的關(guān)系素的關(guān)系 gcd的性質(zhì)和求法v定理定理1.4 設(shè)設(shè)a，b，c是任意不全為是任意不全為0的整數(shù)，且的整數(shù)，且a=qb+

49、c，其中，其中q是整數(shù)，則有：是整數(shù)，則有：gcd(a, b)= gcd(b, c)或?qū)懗苫驅(qū)懗蒰cd (a, b)=gcd (b, a mod b)。v即被除數(shù)和除數(shù)的最大公因子與除數(shù)和余數(shù)的即被除數(shù)和除數(shù)的最大公因子與除數(shù)和余數(shù)的最大公因子相同。例如：最大公因子相同。例如：gcd(18, 12)= gcd(12, 6) = gcd(6, 0)=6gcd(11, 10)= gcd(10, 1) = gcd(1, 0)=1素?cái)?shù)的相關(guān)定理v定理定理1.5 任給整數(shù)任給整數(shù)ab0，則存在兩個(gè)整數(shù)，則存在兩個(gè)整數(shù)m, n，使得：使得：ma+nb=gcd(a, b)gcd(a,b)記為記為c，則有，則

50、有c|a,且且c|b,從而從而c|ma+nb 若若 a | b且且a|c,則對(duì)任意的則對(duì)任意的 m,n,有有 a|(bm+cn).證明證明 因?yàn)橐驗(yàn)閍|b且且a|c, 故故b=aq1和和c=aq2. 于是于是, bm+cn=a(q1m+q2n), 所以所以, a|(bm+cn).例如：若例如：若a=3，b=2，則，則gcd(a, b)=1，存在，存在m=1，n=-1合數(shù)的定理v定理定理1.6 若若a是合數(shù)，則是合數(shù)，則a有一因數(shù)有一因數(shù)d滿足：滿足：1d=a1/2。v定理定理1.7 若若a是合數(shù)，則是合數(shù)，則a必有一素因數(shù)小于或等必有一素因數(shù)小于或等于于a1/2。3. 模運(yùn)算與同余v設(shè)設(shè)n是一

51、正整數(shù)，是一正整數(shù)，a是整數(shù)，如果用是整數(shù)，如果用n除除a，得商，得商為為q，余數(shù)為，余數(shù)為r，即，即a=qn+r，0rn，則余數(shù)，則余數(shù)r可可以用以用“a mod n”表示，即表示，即r=a mod n；商；商q可表示可表示為為q= ，其中，其中， 表示小于或等于表示小于或等于x的最大的最大整數(shù)。整數(shù)。 v同余同余：如果：如果a mod n=b mod n，則稱兩整數(shù)則稱兩整數(shù)a和和b模模n同余，記為同余，記為ab mod nna/ x注意：同余符注意：同余符“”和等號(hào)和等號(hào)“=”的區(qū)別的區(qū)別ab (mod m) m|(a-b)同余的性質(zhì)v同余的性質(zhì)：同余的性質(zhì)：v 自反性：如自反性：如aa

52、 mod n；v 對(duì)稱性：若對(duì)稱性：若a b(mod m)，則，則b a(mod m)；v 傳遞性：若傳遞性：若a b(mod m)，b c(mod m)，則，則a c(mod m)。模運(yùn)算與同余v求余運(yùn)算求余運(yùn)算a mod n將整數(shù)映射到非負(fù)整數(shù)的集合將整數(shù)映射到非負(fù)整數(shù)的集合Zn=0,1, , n-1，稱為求余運(yùn)算，在這個(gè)集合上，稱為求余運(yùn)算，在這個(gè)集合上的運(yùn)算稱為的運(yùn)算稱為模運(yùn)算模運(yùn)算。稱稱Zn為模為模n的的同余類集合同余類集合。其。其上的模運(yùn)算有以下性質(zhì)：上的模運(yùn)算有以下性質(zhì)： (a mod n)+(b mod n) mod n=(a+b) mod n。 (a mod n)-(b mo

53、d n) mod n=(a-b) mod n。 (a mod n)(b mod n) mod n=(ab) mod n。 同余式的運(yùn)算規(guī)則v定理定理1.8 若若ab(mod m)，cd(mod m)，則有：，則有： ax+cybx+dy(mod m), 其中其中x和和y為任給整數(shù)；為任給整數(shù)；證明：證明：因?yàn)橐驗(yàn)閙|(a-b), m|(c-d), 故有故有m|x(a-b)+y(c-d) = (ax+cy)-(bx+dy). acbd(mod m)；證明：由證明：由 m|c(a-b)+b(c-d)=ac-bd立即可得立即可得.同余式的運(yùn)算規(guī)則 anbn(mod m), 其中其中 n0。例如。例如

54、25 mod 3，則則2*25*2 mod 3。 anbn(mod m), 其中其中 n0。例如。例如25 mod 3，則則2252 mod 3。 f(a)f(b)(mod m), 其中其中f(x)為任給的一個(gè)整為任給的一個(gè)整系數(shù)多項(xiàng)式。系數(shù)多項(xiàng)式。同余式的運(yùn)算規(guī)則v1）如果）如果acbd(mod m)，ab(mod m)，gcd(a, m)=1，則，則cd(mod m)v2）存在）存在c，使得，使得ac1(mod m)，當(dāng)且僅，當(dāng)且僅當(dāng)當(dāng)gcd(a, m)=1v3）ab(mod m)，如果，如果d是是m的因子，則的因子，則ab(mod d)。 逆變換v1）加法逆元加法逆元：對(duì)每一個(gè)：對(duì)每一個(gè)

55、a，存在一個(gè)，存在一個(gè)b，使得，使得a+b=0 mod n，則稱，則稱b為為a對(duì)模對(duì)模n的加法逆元，例的加法逆元，例如如5+3 mod 4=0，我們就稱，我們就稱5是是3對(duì)模對(duì)模4的加法逆的加法逆元。元。v2）乘法逆元乘法逆元：若若m1，gcd(a,m)=1，則存在，則存在c使使得得ca1(mod m)，我們把滿足這樣條件的，我們把滿足這樣條件的c稱為稱為a對(duì)模對(duì)模m的乘法逆元，記作的乘法逆元，記作a-1 (mod m)。若。若aZm，則則a對(duì)模對(duì)模m的逆記作：的逆記作：a-1。例如例如5*3 mod 7=1。 歐拉函數(shù) v定義：設(shè)定義：設(shè)n是一正整數(shù)，是一正整數(shù)，小于小于n且與且與n互素互素

56、的正整數(shù)的個(gè)數(shù)的正整數(shù)的個(gè)數(shù)稱為稱為n的歐拉函數(shù)，記為的歐拉函數(shù)，記為(n)。v歐拉函數(shù)的性質(zhì)（求法）：歐拉函數(shù)的性質(zhì)（求法）：1）若）若n是素?cái)?shù)，則是素?cái)?shù)，則(n)=n-1；2）若）若n=p*q，p、q是素?cái)?shù)且是素?cái)?shù)且pq，則，則(n)=(p-1)*(q-1)；歐拉函數(shù)（2）v3）若）若np1a1p2a2psas，其中，其中p1, p2, , ps為素?cái)?shù)，為素?cái)?shù)，a1, a2, as為正整數(shù)，則有：為正整數(shù)，則有：v例如：例如：(6)= (3-1)*(2-1)=2；(7)=7-1=6；(8)=8*(1-1/2) =4；(20)=20*(1-1/5) *(1-1/2)=8；(49)=49*(1

57、-1/7) =42。 spppnn111111)(21v歐拉（歐拉（Euler）定理：若）定理：若a和和n都是正整數(shù)，且都是正整數(shù)，且gcd (a, n) =1，則有，則有a(n) mod n =1。v歐拉定理的應(yīng)用：求解歐拉定理的應(yīng)用：求解3102 mod 11v解：因?yàn)榻猓阂驗(yàn)間cd (3, 11) =1，則有，則有310 mod 11=1 （因?yàn)椋ㄒ驗(yàn)?11)=10）v所以所以310*10 mod 11=110=1，3100+2 mod 11=32 mod 11=9v推論：若推論：若a與與n互素，則互素，則a與與a (n)-1 互為乘法逆互為乘法逆元。元。 歐拉定理例題eg: 求求780

58、3的后三位數(shù)字的后三位數(shù)字 解：解： 7803（mod 1000）的結(jié)果）的結(jié)果 ?(1000) = 1000(1-1/2)(1-1/5) = 400， 有有7803 (7400)273 343 (mod 1000)例如：例如： 求求 253 (mod 11) = ? 由由Fermat小定理小定理: 210 = 1024 1 (mod 11) 253 = (210)523 1523 8 (mod 11) 費(fèi)馬定理v費(fèi)馬（費(fèi)馬（Fermat）定理：設(shè)）定理：設(shè)a和和p都為正整數(shù)，且都為正整數(shù)，且p是素?cái)?shù)，若是素?cái)?shù)，若gcd (a, p) =1，則，則ap-1 1 mod p。也可。也可寫成設(shè)寫成

59、設(shè)p是素?cái)?shù)，是素?cái)?shù)，a是任一正整數(shù)，則是任一正整數(shù)，則apa mod p。當(dāng)當(dāng)n為素?cái)?shù)時(shí)，歐拉定理即轉(zhuǎn)化為費(fèi)馬定為素?cái)?shù)時(shí)，歐拉定理即轉(zhuǎn)化為費(fèi)馬定理，該費(fèi)馬定理又叫做費(fèi)馬小定理理，該費(fèi)馬定理又叫做費(fèi)馬小定理（1）通常情況下，如果）通常情況下，如果2n-1 1 (mod n),n為素?cái)?shù)為素?cái)?shù),然而然而,也有例外也有例外: 561 = 3 11 17是合數(shù)是合數(shù),但但2560 1 (mod 561)。因此，如果。因此，如果2n-1 1 (mod n),那么那么n可可能為素?cái)?shù)。能為素?cái)?shù)。 （2）但）但2n-1 模模n 不等于不等于 1,那么那么n不可能為素?cái)?shù)不可能為素?cái)?shù) 這為我們提供一種尋找素?cái)?shù)的方法

60、，給定一個(gè)這為我們提供一種尋找素?cái)?shù)的方法，給定一個(gè)n, 計(jì)算計(jì)算2n-1 模模n 是否等于是否等于 1，如果不等于，如果不等于1， n為非為非素?cái)?shù)，如果等于素?cái)?shù)，如果等于1，還需用更復(fù)雜的方法來判斷，還需用更復(fù)雜的方法來判斷是否為素?cái)?shù)，是否為素?cái)?shù)，數(shù)論的其他重要定理v3. 威爾遜定理：若威爾遜定理：若p為素?cái)?shù)，則為素?cái)?shù)，則p可整除可整除(p-1)!+1，該定理給出了判定自然數(shù)為素?cái)?shù)的充要條件。該定理給出了判定自然數(shù)為素?cái)?shù)的充要條件。v4. 中國(guó)剩余定理：已知某個(gè)數(shù)關(guān)于一些兩兩互中國(guó)剩余定理：已知某個(gè)數(shù)關(guān)于一些兩兩互素的數(shù)的同余類集，就可重構(gòu)這個(gè)數(shù)。如某個(gè)素的數(shù)的同余類集，就可重構(gòu)這個(gè)數(shù)。如某個(gè)