哈工大信息安全密碼學(xué)基礎(chǔ)課件

1、計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心1密碼學(xué)密碼學(xué)基礎(chǔ)基礎(chǔ) Email: 辦公室辦公室:新技術(shù)樓新技術(shù)樓509Tel:3計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心2內(nèi)容內(nèi)容密碼體系概述密碼體系概述古典密碼古典密碼對(duì)稱(chēng)密鑰密碼對(duì)稱(chēng)密鑰密碼公開(kāi)密鑰密碼公開(kāi)密鑰密碼數(shù)字簽名與摘要函數(shù)數(shù)字簽名與摘要函數(shù)計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心3數(shù)據(jù)加密基本概念數(shù)據(jù)加密基本概念 密碼：是一組含有參數(shù)的變換密碼：是一組含有參數(shù)的變換 明文（明文（plain text) ：作為加密輸入的原始信息：作為加密輸入的原始信息 加密算法：變換

2、函數(shù)加密算法：變換函數(shù) 密文（密文（ciphertext)：:明文變換結(jié)果明文變換結(jié)果 密鑰（密鑰（key)：:參與變換的參數(shù)參與變換的參數(shù)計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心4加密通信的模型加密通信的模型 密碼學(xué)的目的：密碼學(xué)的目的：Alice和和Bob兩個(gè)人在不安全的信道上進(jìn)兩個(gè)人在不安全的信道上進(jìn)行通信，而破譯者行通信，而破譯者Oscar不能理解他們通信的內(nèi)容。不能理解他們通信的內(nèi)容。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心5密碼體制密碼體制 通常一個(gè)完整密碼體制要包括如下五個(gè)要素通常一個(gè)完整密碼體制要包括如下五個(gè)要素M,C,K,E,D

3、 M是可能明文的有限集稱(chēng)為明文空間是可能明文的有限集稱(chēng)為明文空間 C是可能密文的有限集稱(chēng)為密文空間是可能密文的有限集稱(chēng)為密文空間 K是一切可能密鑰構(gòu)成的有限集稱(chēng)為密鑰空間是一切可能密鑰構(gòu)成的有限集稱(chēng)為密鑰空間 對(duì)于密鑰空間的任一密鑰，有一個(gè)加密算法和相應(yīng)的解密對(duì)于密鑰空間的任一密鑰，有一個(gè)加密算法和相應(yīng)的解密算法使得算法使得ek:MC 和和dk:CM（分別為加密解密函數(shù)），（分別為加密解密函數(shù)），滿足滿足 , 這里這里 。M xx(x)(edkk計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心6一個(gè)密碼體制必須滿足如下特性一個(gè)密碼體制必須滿足如下特性每一個(gè)加密函數(shù)每一個(gè)加密函數(shù)

4、Ek和每一個(gè)解密函數(shù)和每一個(gè)解密函數(shù)Dk都能有效都能有效地計(jì)算地計(jì)算破譯者取得密文破譯者取得密文y后后,將不能在有效的時(shí)間內(nèi)破解出將不能在有效的時(shí)間內(nèi)破解出密鑰密鑰k或明文或明文x一個(gè)密碼系統(tǒng)是安全的必要條件：一個(gè)密碼系統(tǒng)是安全的必要條件：窮舉密鑰搜索將是不可行的，即密鑰空間非常大窮舉密鑰搜索將是不可行的，即密鑰空間非常大計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心7密碼分類(lèi)密碼分類(lèi)按發(fā)展進(jìn)程分：按發(fā)展進(jìn)程分：l古典密碼古典密碼l對(duì)稱(chēng)密鑰密碼對(duì)稱(chēng)密鑰密碼l公開(kāi)密鑰密碼公開(kāi)密鑰密碼 按密鑰管理的方式分為按密鑰管理的方式分為l秘密密鑰算法秘密密鑰算法l公開(kāi)密鑰算法公開(kāi)密鑰算法按

5、加密模式分：按加密模式分：l序列密碼序列密碼l分組密碼分組密碼 計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心8密碼體系概述密碼體系概述古典密碼古典密碼對(duì)稱(chēng)密鑰密碼對(duì)稱(chēng)密鑰密碼公開(kāi)密鑰密碼公開(kāi)密鑰密碼數(shù)字簽名與摘要函數(shù)數(shù)字簽名與摘要函數(shù)計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心9經(jīng)典密碼經(jīng)典密碼 代替密碼代替密碼: 簡(jiǎn)單代替、多名或同音代替、多表代替、多字母或多簡(jiǎn)單代替、多名或同音代替、多表代替、多字母或多碼代替碼代替. 簡(jiǎn)單代替密碼簡(jiǎn)單代替密碼 將明文字母表將明文字母表M中的每個(gè)字母用密文字母表中的每個(gè)字母用密文字母表C中的相應(yīng)中的相應(yīng)字母來(lái)代替。字母

6、來(lái)代替。 這一類(lèi)密碼包括移位密碼、替換密碼、仿射密碼、乘這一類(lèi)密碼包括移位密碼、替換密碼、仿射密碼、乘數(shù)密碼等。數(shù)密碼等。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心10移位密碼移位密碼 移位密碼：移位密碼： 是最簡(jiǎn)單的一類(lèi)代替密碼，將字母表的字母右移是最簡(jiǎn)單的一類(lèi)代替密碼，將字母表的字母右移k個(gè)位置，并對(duì)字母表長(zhǎng)度作模運(yùn)算。個(gè)位置，并對(duì)字母表長(zhǎng)度作模運(yùn)算。 加密變換：加密變換：ek(m)=(k+m)(mod q)； 解密變換：解密變換：dk (c)=(m-k)( mod q)計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心11凱撒凱撒Caesar 密碼密碼

7、 Caesar 密碼是對(duì)英文密碼是對(duì)英文26個(gè)字母進(jìn)行移位代個(gè)字母進(jìn)行移位代替的密碼，其替的密碼，其M=C；q=26, k=3 。 使用凱撒密碼將明文使用凱撒密碼將明文M= meet me after the toga party加密為加密為C= phhw ph diwho wkh wrjd sduwb 計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心12乘數(shù)密碼乘數(shù)密碼 乘數(shù)密碼： 是一種替換密碼，它將每個(gè)字母乘以一個(gè)密鑰k，即Ek(m)=km mod q； 其中k和q為互素的，這樣字母表中的字母會(huì)產(chǎn)生一個(gè)復(fù)雜的剩余集合。 若k和q不互素，則會(huì)有一些明文字母被加密成相同的密文

8、字母，而且，不是所有的字母都會(huì)出現(xiàn)在密文字母表中。 算法描述 設(shè)M=C=Z/(26)， K=aZ/(26) |gcd(a,26)=1, x、yZ/(26)； 對(duì)k=aK, Ek(x)=ax(mod 26)；Dk(y)=a-1(y)(mod 26)，aa-1 mod q =1a=5, a-1 =21a=7, a-1 =15 計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心13 例子例子: a=9， Ek(x)=9x(mod 26)ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR 明文=密文cipher = SUFLKX 對(duì)于

9、乘數(shù)密碼，當(dāng)且僅當(dāng)a與互素時(shí)，加密變換才是一一映射的，因此a的選擇有11種：a=3,5,7,9,11,15,17,19,21,23,25。 可能?chē)L試的密鑰只有11個(gè)。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心14仿射密碼仿射密碼 仿射密碼是替換密碼的另一個(gè)特例，形式為仿射密碼是替換密碼的另一個(gè)特例，形式為 ek(m)=(k1m+k2) mod q =c mod q； 其中其中k1和和q是互素的。是互素的。k1=1,3,5,7,9,11,15,17,19,21,23,25 定義：定義：ek(x)=ax+b (mod 26)dk(y)=a-1(y -b)(mod 26)；x,

10、y Z/(26) ，q=26時(shí)，可能的密鑰是時(shí)，可能的密鑰是26*12=312個(gè)。個(gè)。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心15仿射密碼仿射密碼 例例 例子，設(shè)例子，設(shè)k（7，3），注意到），注意到7-1(mod 26)=15,加密函數(shù)是加密函數(shù)是ek(x)=7x+3 (mod 26),相應(yīng)的解密函數(shù)是相應(yīng)的解密函數(shù)是dk(y)=15(y -3)=15y 19 (mod 26) , 易見(jiàn)易見(jiàn) dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19 =x(mod 26) 若加密明文：若加密明文：hot ，首先轉(zhuǎn)換字母，首先轉(zhuǎn)換字母hot成為數(shù)字成為數(shù)

11、字7,14,19,加密：加密： 解密：解密： 計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心16單表替換密碼的破譯 通過(guò)字母的使用頻率破譯計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心17多表代替密碼多表代替密碼 單字母出現(xiàn)頻率分布與密文中相同，安全性受到威脅。單字母出現(xiàn)頻率分布與密文中相同，安全性受到威脅。 多表代替密碼思想：多表代替密碼思想： 使用從明文字母到密文字母的多個(gè)映射，來(lái)隱藏單字母出現(xiàn)的頻率分使用從明文字母到密文字母的多個(gè)映射，來(lái)隱藏單字母出現(xiàn)的頻率分布，每個(gè)映射是簡(jiǎn)單代替密碼中的一對(duì)一映射。布，每個(gè)映射是簡(jiǎn)單代替密碼中的一對(duì)一映射。 維吉尼亞

12、維吉尼亞Vigenere 密碼、博福特密碼、博福特Beaufort 密碼均是多表代替密碼。密碼均是多表代替密碼。 維吉尼亞維吉尼亞Vigenere 密碼算法如下：密碼算法如下： 設(shè)密鑰明文加密變換設(shè)密鑰明文加密變換ek(m)=c1c2cn； 其中：其中： Ci=（mi+ki ）mod 26；密鑰；密鑰k可以通過(guò)周期性地延長(zhǎng)，反復(fù)可以通過(guò)周期性地延長(zhǎng)，反復(fù)進(jìn)行以至無(wú)窮。進(jìn)行以至無(wú)窮。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心18密碼體系概述密碼體系概述古典密碼古典密碼對(duì)稱(chēng)密鑰密碼對(duì)稱(chēng)密鑰密碼公開(kāi)密鑰密碼公開(kāi)密鑰密碼數(shù)字簽名與摘要函數(shù)數(shù)字簽名與摘要函數(shù)計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)

13、絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心19對(duì)稱(chēng)密鑰密碼模型對(duì)稱(chēng)密鑰密碼模型計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心20數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DES的產(chǎn)生的產(chǎn)生 1973年年5月月15日日, NBS開(kāi)始公開(kāi)征集標(biāo)準(zhǔn)加密算法開(kāi)始公開(kāi)征集標(biāo)準(zhǔn)加密算法,并公布了它的設(shè)計(jì)要求并公布了它的設(shè)計(jì)要求:(1)算法必須提供高度的安全性算法必須提供高度的安全性(2)算法必須有詳細(xì)的說(shuō)明算法必須有詳細(xì)的說(shuō)明,并易于理解并易于理解(3)算法的安全性取決于密鑰算法的安全性取決于密鑰,不依賴(lài)于算法不依賴(lài)于算法(4)算法適用于所有用戶(hù)算法適用于所有用戶(hù)(5)算法適用于不同應(yīng)用場(chǎng)合算法適用于不同應(yīng)

14、用場(chǎng)合(6)算法必須高效、經(jīng)濟(jì)算法必須高效、經(jīng)濟(jì)(7)算法必須能被證實(shí)有效算法必須能被證實(shí)有效(8)算法必須是可出口的算法必須是可出口的1974年年8月月27日日, NBS開(kāi)始第二次征集開(kāi)始第二次征集,IBM提交了算法提交了算法LUCIFER，該算法由，該算法由IBM的工程師在的工程師在19711972年研制年研制最近的一次評(píng)估是在最近的一次評(píng)估是在1994年年1月，已決定月，已決定1998年年12月以后，月以后，DES將不再作將不再作為聯(lián)邦加密標(biāo)準(zhǔn)。為聯(lián)邦加密標(biāo)準(zhǔn)。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心21簡(jiǎn)化的簡(jiǎn)化的DES Simplified DES方案，簡(jiǎn)稱(chēng)方

15、案，簡(jiǎn)稱(chēng)S-DES方案。加密算法涉及方案。加密算法涉及五個(gè)函數(shù)：五個(gè)函數(shù)：(1)初始置換初始置換IP(initial permutation) (2)復(fù)合函數(shù)復(fù)合函數(shù)fk1，它是由密鑰，它是由密鑰K確定的，具有置換和替代的運(yùn)算。確定的，具有置換和替代的運(yùn)算。(3)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)SW (4)復(fù)合函數(shù)復(fù)合函數(shù)fk2 (5)初始置換初始置換IP的逆置換的逆置換IP-1(6)置換函數(shù)置換函數(shù)P8、P10計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心22S-DES的流程的流程計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心23（1）S-DES的密鑰生成的密鑰生成 設(shè)1

16、0bit的密鑰為 (k1,k2,k3,k4,k5,k6,k7, k8,k9,k10) 置換P10是這樣定義的 P10(k1,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) 相當(dāng)于P10=（3 5 2 7 4 10 1 9 8 6） LS-1為循環(huán)左移一次， 置換P8=(6 3 7 4 8 5 10 9)計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心24 算法如下圖算法如下圖 若若K選為選為(1010000010), 產(chǎn)生的兩個(gè)子密鑰分別為產(chǎn)生的兩個(gè)子密鑰分別為 K1=(1 0 1 0 0 1 0 0)；K2=(0 1 0 0 0 0 1 1)計(jì)算機(jī)

17、網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心25（2） S-DES的加密運(yùn)算的加密運(yùn)算: 初始置換用初始置換用IP函數(shù)函數(shù): IP= 末端算法的置換為末端算法的置換為IP的逆置換的逆置換: IP-1= 易見(jiàn)易見(jiàn)IP-1(IP(X)=X。 計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心26簡(jiǎn)化的得DES方案加密細(xì)節(jié)如右圖計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心27 函數(shù)函數(shù)fk fk(L,R)=(L F(R,SK),R)是加密方案中的最重要部分，是加密方案中的最重要部分， 其中，其中，L、R為為8位輸入的左右各位輸入的左右各4位位,， F為

18、從為從4位集到位集到4位集的一個(gè)映射。位集的一個(gè)映射。 SK為子密鑰。為子密鑰。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心28 對(duì)映射對(duì)映射F來(lái)說(shuō)：來(lái)說(shuō)： 首先輸入是一個(gè)首先輸入是一個(gè)4位數(shù)（位數(shù)（n1,n2,n3,n4），第一步運(yùn)算），第一步運(yùn)算是擴(kuò)張是擴(kuò)張/置換（置換（E/P）運(yùn)算：）運(yùn)算： E/P=( 4 1 2 3 2 3 4 1) 計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心29 然后然后, E/P的結(jié)果與子密鑰作異或運(yùn)算得：的結(jié)果與子密鑰作異或運(yùn)算得： 8-bit子密鑰：子密鑰：K1=(k11,k12,k13,k14,k15,k16,k17

19、,k18),計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心30 把它們重記為把它們重記為8位：位：計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心31 上述第一行的上述第一行的4位輸入進(jìn)位輸入進(jìn)S盒盒S0，產(chǎn)，產(chǎn)生生2-位的輸出；位的輸出； 第二行的第二行的4位輸入進(jìn)位輸入進(jìn)S盒盒S1，產(chǎn)生，產(chǎn)生2-位的輸出。位的輸出。 兩個(gè)兩個(gè)S盒按如下定義：盒按如下定義：計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心32 S盒按下述規(guī)則運(yùn)算：盒按下述規(guī)則運(yùn)算： 將第將第1和第和第4的輸入比特做為的輸入比特做為2 bit數(shù)，指示為數(shù)，指示為S盒的一盒的一個(gè)

20、行；將第個(gè)行；將第2和第和第3的輸入比特做為的輸入比特做為S盒的一個(gè)列。如此盒的一個(gè)列。如此確定為確定為S盒矩陣的（盒矩陣的（i,j）數(shù)。）數(shù)。 例如：（例如：（P0,0, P0,3）=(0 0)，并且，并且(P0,1,P0,2)=(1 0)，確定了確定了S0中的第中的第0行行2列（列（0，2）的系數(shù)為）的系數(shù)為3，記為（，記為（1 1）輸出。）輸出。 由由S0, S1輸出輸出4 bit經(jīng)置換經(jīng)置換 P4=(2 4 3 1)；即；即F的輸出。的輸出。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心33回顧：回顧：計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心3

21、4 DES是一種對(duì)二元數(shù)據(jù)進(jìn)行加密的算法是一種對(duì)二元數(shù)據(jù)進(jìn)行加密的算法, 數(shù)據(jù)分組長(zhǎng)度為數(shù)據(jù)分組長(zhǎng)度為64位位,密文分組長(zhǎng)度也是密文分組長(zhǎng)度也是64位位,使用的密使用的密鑰為鑰為64位位,有效密鑰長(zhǎng)度為有效密鑰長(zhǎng)度為56位位,有有8位用于奇偶校驗(yàn)；位用于奇偶校驗(yàn)； 解密時(shí)的過(guò)程和加密時(shí)相似解密時(shí)的過(guò)程和加密時(shí)相似,但密鑰的順序正好相反；但密鑰的順序正好相反； DES的整個(gè)體制是公開(kāi)的的整個(gè)體制是公開(kāi)的,系統(tǒng)的安全性完全靠密鑰的系統(tǒng)的安全性完全靠密鑰的保密保密.計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心35計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心36

22、其它分組加密算法其它分組加密算法 三重三重DES、IDEA、 RC5、 RC6、 Blowfish 、CAST、RC2 AES算法算法: 為為AES開(kāi)發(fā)開(kāi)發(fā)Rijndael算法的是兩位來(lái)自比利時(shí)的密碼算法的是兩位來(lái)自比利時(shí)的密碼專(zhuān)家專(zhuān)家Joan daemen博士、博士、Vincent Rijmen計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心37密碼體系概述密碼體系概述古典密碼古典密碼對(duì)稱(chēng)密鑰密碼對(duì)稱(chēng)密鑰密碼公開(kāi)密鑰密碼公開(kāi)密鑰密碼數(shù)字簽名與摘要函數(shù)數(shù)字簽名與摘要函數(shù)計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心38公鑰加密模型公鑰加密模型計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)

23、算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心39公鑰密碼體制公鑰密碼體制 公鑰密碼又稱(chēng)為雙鑰密碼和非對(duì)稱(chēng)密碼公鑰密碼又稱(chēng)為雙鑰密碼和非對(duì)稱(chēng)密碼 1976年由年由Diffie和和Hellman在其在其“密碼學(xué)新方向密碼學(xué)新方向”一文中一文中提出的。提出的。見(jiàn)劃時(shí)代的文獻(xiàn)見(jiàn)劃時(shí)代的文獻(xiàn)W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 單向陷門(mén)函數(shù)是滿足下列條件的函數(shù)單向陷門(mén)函數(shù)是滿

24、足下列條件的函數(shù)f 給定給定x 計(jì)算計(jì)算y=f(x)是容易的；是容易的； 給定給定y, 計(jì)算計(jì)算x使使y=f(x)是困難的是困難的(所謂計(jì)算所謂計(jì)算x=f-1(Y)困難是指困難是指計(jì)算上相當(dāng)復(fù)雜已無(wú)實(shí)際意義計(jì)算上相當(dāng)復(fù)雜已無(wú)實(shí)際意義)； 存在存在，已知，已知時(shí)時(shí),對(duì)給定的任何對(duì)給定的任何y，若相應(yīng)的，若相應(yīng)的x存在，則計(jì)存在，則計(jì)算算x使使y=f(x)是容易的。是容易的。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心40基于公開(kāi)密鑰的加密過(guò)程基于公開(kāi)密鑰的加密過(guò)程計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心41基于公開(kāi)密鑰的鑒別過(guò)程基于公開(kāi)密鑰的鑒別過(guò)程計(jì)

25、算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心42公鑰密碼實(shí)現(xiàn)保密、鑒別公鑰密碼實(shí)現(xiàn)保密、鑒別 用戶(hù)擁有自己的密鑰對(duì)用戶(hù)擁有自己的密鑰對(duì)(KU,KR) 保密：保密：A -B：Y=EKUb(X)B：DKRb(Y)= DKRb(EKUb(X)=X 鑒別：鑒別： 條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密A ALL：Y=DKRa(X)ALL：EKUa(Y)=EKUa(DKRa(X)=X 鑒別鑒別+保密：保密： A- B：Z= EKUb(DKRa(X) B：EKUa(DKRb(Z)=X計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全

26、技術(shù)研究中心安全技術(shù)研究中心43數(shù)論問(wèn)題數(shù)論問(wèn)題 離散對(duì)數(shù)離散對(duì)數(shù): ygx mod p 已知已知g,x,p,計(jì)算計(jì)算y是容易的；是容易的； 已知已知y,g,p,計(jì)算計(jì)算x是困難的。是困難的。 表示表示 a mod p = b mod p ，稱(chēng)，稱(chēng)“模模P同余同余”。 素?cái)?shù)素?cái)?shù)p的原根的原根(primitive root) 如果如果a是素?cái)?shù)是素?cái)?shù)p的原根，則數(shù)的原根，則數(shù)a mod p, a2 mod p, , ap-1 mod p 是不同的并且包含是不同的并且包含1到到p-1的整數(shù)的某種排列。的整數(shù)的某種排列。 對(duì)任意的整數(shù)對(duì)任意的整數(shù)b，我們可以找到唯一的冪，我們可以找到唯一的冪 I I

27、滿足滿足 b ai mod p ， 0=i=(p-1)。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心44Diffie-Hellman密鑰交換密鑰交換 對(duì)對(duì)Diffie-Hellman密鑰交換協(xié)議描述密鑰交換協(xié)議描述 Alice和和Bob協(xié)商好一個(gè)大素?cái)?shù)協(xié)商好一個(gè)大素?cái)?shù)p，和大的整數(shù)，和大的整數(shù)g，1gp，g是是p的原根。的原根。p和和g無(wú)須保密，可為網(wǎng)絡(luò)上的所有用戶(hù)共無(wú)須保密，可為網(wǎng)絡(luò)上的所有用戶(hù)共享。享。 當(dāng)當(dāng)Alice和和Bob要進(jìn)行保密通信時(shí)，他們可以按如下步驟要進(jìn)行保密通信時(shí)，他們可以按如下步驟來(lái)做：來(lái)做：(1)Alice送取大的隨機(jī)數(shù)送取大的隨機(jī)數(shù)x，并計(jì)算，并計(jì)

28、算Y = gx (mod P)(2)Bob選取大的隨機(jī)數(shù)選取大的隨機(jī)數(shù)x ，并計(jì)算，并計(jì)算Y = gx (mod P)(3)Alice將將Y傳送給傳送給Bob；Bob將將Y 傳送給傳送給Alice。(4)Alice計(jì)算計(jì)算K = (Y ) x(mod P);(5)Bob計(jì)算計(jì)算K = (Y)x (mod P)， 易見(jiàn)，易見(jiàn)，K=K =gxx (mod P)。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心45RSA密碼體制密碼體制 歐拉定理歐拉定理 若整數(shù)若整數(shù)g和和n互素，則互素，則g (n) 1(mod n)；其中；其中 (n)為比為比n小，但與小，但與n互素的正整數(shù)個(gè)數(shù)互

29、素的正整數(shù)個(gè)數(shù), 稱(chēng)為稱(chēng)為 (n)為歐拉函數(shù)。為歐拉函數(shù)。 n=pq ， (n)=(p-1)(q-1) 。 RSA密碼體制密碼體制 明文空間明文空間P密文空間密文空間C=Zn. 密鑰的生成密鑰的生成 選擇選擇p,q，p,q為互異素?cái)?shù)，計(jì)算為互異素?cái)?shù)，計(jì)算n=p*q, (n)=(p-1)(q-1), 選擇整數(shù)選擇整數(shù)e使使gcd( (n),e)=1 ,1e (n), 計(jì)算計(jì)算d,使使d=e-1(mod (n), 公鑰公鑰Pk=e,n;私鑰私鑰Sk=d,p,q。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心46 RSA密碼加密和解密函數(shù)密碼加密和解密函數(shù) 加密加密 (用用e,n)

30、明文：明文：M=2|Z|，記，記|X|=m和和|Z|=n，易見(jiàn)，易見(jiàn)，至少有至少有n個(gè)碰撞個(gè)碰撞， 那么，如何找到它們？那么，如何找到它們？ 這個(gè)過(guò)程類(lèi)似于隨機(jī)拋這個(gè)過(guò)程類(lèi)似于隨機(jī)拋k個(gè)球進(jìn)入個(gè)球進(jìn)入n個(gè)箱子，然后，檢個(gè)箱子，然后，檢查一下是否有一些箱子包含了至少兩個(gè)球。查一下是否有一些箱子包含了至少兩個(gè)球。(這這k個(gè)球個(gè)球?qū)?yīng)于對(duì)應(yīng)于k個(gè)隨機(jī)值個(gè)隨機(jī)值xi，且，且n個(gè)箱子對(duì)應(yīng)于個(gè)箱子對(duì)應(yīng)于Z中中n個(gè)元素個(gè)元素)計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心59 若要分析這若要分析這k個(gè)隨機(jī)元素個(gè)隨機(jī)元素z1,z2,.,zkZ兩兩不同兩兩不同(無(wú)碰無(wú)碰撞時(shí)撞時(shí))的可能性的可能

31、性 則對(duì)應(yīng)于一個(gè)初始問(wèn)題則對(duì)應(yīng)于一個(gè)初始問(wèn)題-無(wú)碰撞的概率。無(wú)碰撞的概率。 考慮一下有序考慮一下有序z1、z2、zk中的中的zi的選擇可能的選擇可能 第一個(gè)選擇第一個(gè)選擇z1是隨機(jī)的，無(wú)碰撞的概率是隨機(jī)的，無(wú)碰撞的概率100% z2z1的概率為的概率為1-1/n； z3不同于不同于z1和和z2的概率為的概率為1-2/n，以此類(lèi)推。，以此類(lèi)推。 則無(wú)碰撞的概率：則無(wú)碰撞的概率： 隨機(jī)拋隨機(jī)拋k個(gè)球進(jìn)入個(gè)球進(jìn)入n個(gè)箱子，沒(méi)有箱子被拋進(jìn)兩個(gè)以上的球個(gè)箱子，沒(méi)有箱子被拋進(jìn)兩個(gè)以上的球的概率的概率計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心60 若設(shè)若設(shè)E = ,可解出可解出k的關(guān)于

32、的關(guān)于 n和和E的函數(shù)，如下的函數(shù)，如下:12)1ln(2 EnkkEenkk 1)2/()1()1ln()2/()1(Enkk )2/()1(1nkke 計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心61結(jié)論結(jié)論 若略去若略去-k項(xiàng)，有項(xiàng)，有k(n(ln(1/(1-E)2)0.5； 若取若取E=0.5,我們估計(jì)我們估計(jì)k1.17 n0.5 n0.5 ; 說(shuō)明在集合說(shuō)明在集合X中，中，n0.5個(gè)隨機(jī)元素散列的結(jié)果產(chǎn)生一個(gè)碰撞個(gè)隨機(jī)元素散列的結(jié)果產(chǎn)生一個(gè)碰撞的概率為的概率為50%! 所謂生日攻擊就是：如果所謂生日攻擊就是：如果X為一些人的集合，為一些人的集合，Y是一個(gè)非閏是一個(gè)

33、非閏年的年的365天集合，天集合，h(x)表示表示x的生日的生日(xX)。在上述估計(jì)式。在上述估計(jì)式中取中取n=365, 得得k=22.3 即隨機(jī)的即隨機(jī)的23人中至少有一個(gè)重復(fù)生人中至少有一個(gè)重復(fù)生日的概率至少為日的概率至少為50%。生日攻擊給出消息尺寸的下界。一個(gè)生日攻擊給出消息尺寸的下界。一個(gè)40bit的的消息摘要將是不安全的。消息摘要將是不安全的。因?yàn)橐驗(yàn)閗1.17*(240)0.5, 也就是也就是220(大約大約100萬(wàn)萬(wàn)), 即在即在100萬(wàn)個(gè)隨機(jī)散列值中將找到一個(gè)碰撞萬(wàn)個(gè)隨機(jī)散列值中將找到一個(gè)碰撞的概率為的概率為1/2。通常建議消息摘要的尺寸為通常建議消息摘要的尺寸為128bit

34、s。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心62MD4散列算法散列算法(或稱(chēng)信息摘要算法或稱(chēng)信息摘要算法) Rivest(RSA公司首度科學(xué)家公司首度科學(xué)家)，MIT博士，博士，1990年提出年提出MD4，1991年提出增強(qiáng)版年提出增強(qiáng)版MD5，1992年提出年提出SHA公布于公布于1992年年1月月31日的聯(lián)幫記錄上，并于日的聯(lián)幫記錄上，并于1993年年5月月11日采納日采納作為標(biāo)準(zhǔn)。作為標(biāo)準(zhǔn)。計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心63MD4： 給定一個(gè)消息比特串給定一個(gè)消息比特串x，使用如下算法來(lái)構(gòu)造，使用如下算法來(lái)構(gòu)造M； 設(shè)設(shè)d= (

35、447-|x|)(mod 512) ；l 表示表示|x|(mod 264)的二進(jìn)制的二進(jìn)制表示，表示，|l|=64 ；M=X10dl。 在在M的構(gòu)造中，在的構(gòu)造中，在x后面附上一個(gè)后面附上一個(gè)1， 然后，并上足夠多然后，并上足夠多的的0，使得長(zhǎng)度變成模，使得長(zhǎng)度變成模512（=29 ）與）與448同余的數(shù)，最后同余的數(shù)，最后并上并上64bit的的l ，它是，它是x的長(zhǎng)度的二進(jìn)制表示。（注意：若的長(zhǎng)度的二進(jìn)制表示。（注意：若必要的話，用模必要的話，用模264約簡(jiǎn)）。約簡(jiǎn)）。 |M|=512*n計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心64計(jì)算機(jī)網(wǎng)絡(luò)與信息計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心65 將將M表示成陣列形式：表示成陣列形式： M=M0M1MN-1； 其中每一個(gè)其中每一個(gè)Mi是一個(gè)長(zhǎng)度為是一個(gè)長(zhǎng)度為3