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

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

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

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

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

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

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

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

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

9、乘數(shù)密碼，當(dāng)且僅當(dāng)a與互素時，加密變換才是一一映射的，因此a的選擇有11種：a=3,5,7,9,11,15,17,19,21,23,25。 可能嘗試的密鑰只有11個。計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心14仿射密碼仿射密碼 仿射密碼是替換密碼的另一個特例，形式為仿射密碼是替換密碼的另一個特例，形式為 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時，可能的密鑰是時，可能的密鑰是26*12=312個。個。計算機網(wǎng)絡(luò)與信息計算機網(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) , 易見易見 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,加密：加密： 解密：解密： 計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心16單表替換密碼的破譯 通過字母的使用頻率破譯計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心17多表代替密碼多表代替密碼 單字母出現(xiàn)頻率分布與密文中相同，安全性受到威脅。單字母出現(xiàn)頻率分布與密文中相同，安全性受到威脅。 多表代替密碼思想：多表代替密碼思想： 使用從明文字母到密文字母的多個映射，來隱藏單字母出現(xiàn)的頻率分使用從明文字母到密文字母的多個映射，來隱藏單字母出現(xiàn)的頻率分布，每個映射是簡單代替密碼中的一對一映射。布，每個映射是簡單代替密碼中的一對一映射。 維吉尼亞

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

13、絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心19對稱密鑰密碼模型對稱密鑰密碼模型計算機網(wǎng)絡(luò)與信息計算機網(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開始公開征集標(biāo)準(zhǔn)加密算法開始公開征集標(biāo)準(zhǔn)加密算法,并公布了它的設(shè)計要求并公布了它的設(shè)計要求:(1)算法必須提供高度的安全性算法必須提供高度的安全性(2)算法必須有詳細(xì)的說明算法必須有詳細(xì)的說明,并易于理解并易于理解(3)算法的安全性取決于密鑰算法的安全性取決于密鑰,不依賴于算法不依賴于算法(4)算法適用于所有用戶算法適用于所有用戶(5)算法適用于不同應(yīng)用場合算法適用于不同應(yīng)

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

15、案，簡稱S-DES方案。加密算法涉及方案。加密算法涉及五個函數(shù)：五個函數(shù)：(1)初始置換初始置換IP(initial permutation) (2)復(fù)合函數(shù)復(fù)合函數(shù)fk1，它是由密鑰，它是由密鑰K確定的，具有置換和替代的運算。確定的，具有置換和替代的運算。(3)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)SW (4)復(fù)合函數(shù)復(fù)合函數(shù)fk2 (5)初始置換初始置換IP的逆置換的逆置換IP-1(6)置換函數(shù)置換函數(shù)P8、P10計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心22S-DES的流程的流程計算機網(wǎng)絡(luò)與信息計算機網(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)計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心24 算法如下圖算法如下圖 若若K選為選為(1010000010), 產(chǎn)生的兩個子密鑰分別為產(chǎn)生的兩個子密鑰分別為 K1=(1 0 1 0 0 1 0 0)；K2=(0 1 0 0 0 0 1 1)計算機

17、網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心25（2） S-DES的加密運算的加密運算: 初始置換用初始置換用IP函數(shù)函數(shù): IP= 末端算法的置換為末端算法的置換為IP的逆置換的逆置換: IP-1= 易見易見IP-1(IP(X)=X。 計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心26簡化的得DES方案加密細(xì)節(jié)如右圖計算機網(wǎng)絡(luò)與信息計算機網(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位集的一個映射。位集的一個映射。 SK為子密鑰。為子密鑰。計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心28 對映射對映射F來說：來說： 首先輸入是一個首先輸入是一個4位數(shù)（位數(shù)（n1,n2,n3,n4），第一步運算），第一步運算是擴張是擴張/置換（置換（E/P）運算：）運算： E/P=( 4 1 2 3 2 3 4 1) 計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心29 然后然后, E/P的結(jié)果與子密鑰作異或運算得：的結(jié)果與子密鑰作異或運算得： 8-bit子密鑰：子密鑰：K1=(k11,k12,k13,k14,k15,k16,k17

19、,k18),計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心30 把它們重記為把它們重記為8位：位：計算機網(wǎng)絡(luò)與信息計算機網(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-位的輸出。位的輸出。 兩個兩個S盒按如下定義：盒按如下定義：計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心32 S盒按下述規(guī)則運算：盒按下述規(guī)則運算： 將第將第1和第和第4的輸入比特做為的輸入比特做為2 bit數(shù)，指示為數(shù)，指示為S盒的一盒的一個

20、行；將第個行；將第2和第和第3的輸入比特做為的輸入比特做為S盒的一個列。如此盒的一個列。如此確定為確定為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的輸出。的輸出。計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心33回顧：回顧：計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心3

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

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

23、算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心39公鑰密碼體制公鑰密碼體制 公鑰密碼又稱為雙鑰密碼和非對稱密碼公鑰密碼又稱為雙鑰密碼和非對稱密碼 1976年由年由Diffie和和Hellman在其在其“密碼學(xué)新方向密碼學(xué)新方向”一文中一文中提出的。提出的。見劃時代的文獻(xiàn)見劃時代的文獻(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 單向陷門函數(shù)是滿足下列條件的函數(shù)單向陷門函數(shù)是滿

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

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

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

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

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

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

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

31、性 則對應(yīng)于一個初始問題則對應(yīng)于一個初始問題-無碰撞的概率。無碰撞的概率。 考慮一下有序考慮一下有序z1、z2、zk中的中的zi的選擇可能的選擇可能 第一個選擇第一個選擇z1是隨機的，無碰撞的概率是隨機的，無碰撞的概率100% z2z1的概率為的概率為1-1/n； z3不同于不同于z1和和z2的概率為的概率為1-2/n，以此類推。，以此類推。 則無碰撞的概率：則無碰撞的概率： 隨機拋隨機拋k個球進(jìn)入個球進(jìn)入n個箱子，沒有箱子被拋進(jìn)兩個以上的球個箱子，沒有箱子被拋進(jìn)兩個以上的球的概率的概率計算機網(wǎng)絡(luò)與信息計算機網(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 計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心61結(jié)論結(jié)論 若略去若略去-k項，有項，有k(n(ln(1/(1-E)2)0.5； 若取若取E=0.5,我們估計我們估計k1.17 n0.5 n0.5 ; 說明在集合說明在集合X中，中，n0.5個隨機元素散列的結(jié)果產(chǎn)生一個碰撞個隨機元素散列的結(jié)果產(chǎn)生一個碰撞的概率為的概率為50%! 所謂生日攻擊就是：如果所謂生日攻擊就是：如果X為一些人的集合，為一些人的集合，Y是一個非閏是一個

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

34、s。計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心62MD4散列算法散列算法(或稱信息摘要算法或稱信息摘要算法) Rivest(RSA公司首度科學(xué)家公司首度科學(xué)家)，MIT博士，博士，1990年提出年提出MD4，1991年提出增強版年提出增強版MD5，1992年提出年提出SHA公布于公布于1992年年1月月31日的聯(lián)幫記錄上，并于日的聯(lián)幫記錄上，并于1993年年5月月11日采納日采納作為標(biāo)準(zhǔn)。作為標(biāo)準(zhǔn)。計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心63MD4： 給定一個消息比特串給定一個消息比特串x，使用如下算法來構(gòu)造，使用如下算法來構(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后面附上一個后面附上一個1， 然后，并上足夠多然后，并上足夠多的的0，使得長度變成模，使得長度變成模512（=29 ）與）與448同余的數(shù)，最后同余的數(shù)，最后并上并上64bit的的l ，它是，它是x的長度的二進(jìn)制表示。（注意：若的長度的二進(jìn)制表示。（注意：若必要的話，用模必要的話，用模264約簡）。約簡）。 |M|=512*n計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心64計算機網(wǎng)絡(luò)與信息計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心安全技術(shù)研究中心65 將將M表示成陣列形式：表示成陣列形式： M=M0M1MN-1； 其中每一個其中每一個Mi是一個長度為是一個長度為3