1、信息安全數(shù)學(xué)基礎(chǔ),信息科學(xué)與工程學(xué)院,網(wǎng)絡(luò)信息的安全威脅 網(wǎng)上犯罪形勢(shì)不容樂(lè)觀； 有害信息污染嚴(yán)重； 網(wǎng)絡(luò)病毒的蔓延和破壞； 網(wǎng)上黑客無(wú)孔不入； 機(jī)要信息流失與信息間諜潛入； 網(wǎng)絡(luò)安全產(chǎn)品的自控權(quán)； 信息戰(zhàn)的陰影不可忽視。,引 言,網(wǎng)絡(luò)通信的困境,引 言,我們要保護(hù)什么呢？,引 言,網(wǎng)絡(luò)安全體系的五類服務(wù),引 言,網(wǎng)絡(luò)安全體系的五類服務(wù),訪問(wèn)控制服務(wù)：根據(jù)實(shí)體身份決定其訪問(wèn)權(quán)限； 身份鑒別服務(wù)：消息來(lái)源確認(rèn)、防假冒、證明你 是否就是你所聲明的你； 保密性服務(wù)：利用加密技術(shù)將消息加密，非授權(quán) 人無(wú)法識(shí)別信息； 數(shù)據(jù)完整性服務(wù)：防止消息被篡改，證明消息與 過(guò)程的正確性； 防抵賴服務(wù)：阻止你或其他主

2、體對(duì)所作所為的進(jìn) 行否認(rèn)的服務(wù)，可確認(rèn)、無(wú)法抵賴。,引 言,引 言,解決方法：加密,如何實(shí)現(xiàn)保密性？,密碼分析,Alice,Bob,加密 密鑰,解密 密鑰,Eve,引 言,解決方法：數(shù)字摘要,如何實(shí)現(xiàn)完整性？,消息篡改,公共網(wǎng)絡(luò),Alice,Bob,m,z,m,z,z=hk(m),y=hk(m),Eve,引 言,解決方法：數(shù)字簽名,如何實(shí)現(xiàn)不可否認(rèn)性？,否認(rèn),公共網(wǎng)絡(luò),Alice,Bob,Trent,誰(shuí)是正確的？,舉報(bào),引 言,解決方法：密碼技術(shù),身份鑒別：就是確認(rèn)實(shí)體是它所聲明的，身份鑒別服務(wù)提供關(guān)于某個(gè)實(shí)體身份的保證，以對(duì)抗假冒攻擊。,如何鑒別通信對(duì)象的身份？,本課程的相關(guān)知識(shí)點(diǎn),簡(jiǎn)單的密

3、碼學(xué)基礎(chǔ)： 密碼技術(shù)是信息安全的核心技術(shù)； 需要掌握一些密碼學(xué)基礎(chǔ)知識(shí)。 相關(guān)的數(shù)學(xué)知識(shí)： 密碼技術(shù)的實(shí)現(xiàn)依賴于數(shù)學(xué)知識(shí)； 掌握密碼技術(shù)涉及的相應(yīng)數(shù)學(xué)基礎(chǔ)知識(shí)點(diǎn)。 參考教材： (1) 密碼學(xué)導(dǎo)引,機(jī)械工業(yè)出版社,Paul Garrett 著,吳世忠等譯； (2) 信息安全數(shù)學(xué)基礎(chǔ),武漢大學(xué)出版社,李繼國(guó)等 主編。,引 言,什么是密碼技術(shù)？,竊聽(tīng),公共網(wǎng)絡(luò),Alice,Bob,Eve,篡改,偽造,加密 密鑰,解密 密鑰,密文,密碼學(xué)是一門古老而深?yuàn)W的學(xué)科,包括密碼編碼學(xué)和密碼分析學(xué); 通信雙方按照某種約定將消息的原形隱藏。 密碼系統(tǒng):明文,密文,加解密算法,密鑰。,引 言,密碼學(xué)的起源與發(fā)展 三

4、個(gè)階段： 1949年之前：密碼學(xué)是一門藝術(shù)； 19491975年：密碼學(xué)成為科學(xué)； 1976年以后：密碼學(xué)的新方向公鑰密碼學(xué)。 1949年之前(手工階段的初級(jí)形式) 隱寫(xiě)術(shù)：隱形墨水、字符格式的變化、圖像；,舉例： 蘆花叢中一扁舟，俊杰俄從此地游； 義士若能知此理，反躬難逃可無(wú)憂。 258 71539 258 314697 314697 15358 24862 17893,引 言,19491975年(機(jī)械階段)：現(xiàn)代密碼出現(xiàn) 1949年香農(nóng)Shannon提出“保密系統(tǒng)信息理論”； 提出：數(shù)據(jù)的安全基于密鑰而不是密碼算法。 1976年以后(計(jì)算機(jī)階段)：公鑰密碼誕生 1976年Diffie vo

5、id seed_LFSR(unsigned long seed) if(seed=0) seed=1; else ShiftRegister=seed; int modified_LFSR(void) if(ShiftRegister ,第四章 現(xiàn)代對(duì)稱密碼,作業(yè)： (1)計(jì)算線性同余發(fā)生器的壞種子： xn+1=6xn+9 mod 11 (2)求LFSR xn+1=xn+xn-1+xn-2+xn-3的周期， 其初態(tài)為: (x0,x1,x2,x3)=(0,1,0,0),5.1 整除性 1.定義 d|n：d整除n，即存在整數(shù)k，使得n=kd。 真因子d：d整除n，但d不是n，1。 素?cái)?shù)：一個(gè)沒(méi)有真

6、因子的正整數(shù)。,2.命題 (1)正整數(shù)n是素?cái)?shù)當(dāng)且僅當(dāng)它不能被任何整數(shù)d整除，其中： (2)互素：如果同時(shí)整除m和n的整數(shù)只有1，則稱m和n互素。記作gcd(m,n)=1。,第五章 整除和同余,(3)如果a|b并且b|c，則a|c； 如果d|x并且d|y，則對(duì)于任意整數(shù)a和b有： d|(ax+by),(4)n和N是兩個(gè)整數(shù)，且n|N，則對(duì)任意整數(shù)x有： (x%N)%n=x%n,3.定理 m和n為不同時(shí)為0的整數(shù)，則m和n的最大公因子 gcd(m,n)是以xm+yn表示的最小正整數(shù)。 例如：gcd(3,5)=23-15=1 gcd(9,15)=29-115=3,第五章 整除和同余,4.素?cái)?shù)的產(chǎn)生

7、 (1)采用素性檢測(cè)法對(duì)隨機(jī)產(chǎn)生的數(shù)進(jìn)行檢測(cè)。 (2)迄今為止沒(méi)有發(fā)現(xiàn)素?cái)?shù)的模型或產(chǎn)生素?cái)?shù)的 有效公式。例如：中國(guó)古代數(shù)學(xué)家提出：若n|2n-2，則n為素?cái)?shù)。但是當(dāng)n=341時(shí)不成立。,第五章 整除和同余,(3)一些特殊意義的素?cái)?shù)： 梅森(Mersenne)素?cái)?shù)： 形如Mn=2n-1的素?cái)?shù)(n為素?cái)?shù)) 如3,7,127,8191,131071。至今發(fā)現(xiàn)27個(gè): n=2,3,5,7,13,17,19,31,61,89,107,127,521, 607,1279,2203,2281,3217,4253,4423,9689, 9941,11213,21701,23209,44497。 M11=204

8、7=2389不是素?cái)?shù)。 費(fèi)馬(Fermat)素?cái)?shù)： 形如Fm=2m+1的素?cái)?shù)(m為自然數(shù)) 至今只發(fā)現(xiàn)5個(gè):3,5,17,257,65537 F5=4294967297=6416700417,5.2 整數(shù)模m 1.xy mod m x模m同余y 這種關(guān)系叫模m的同余。 等價(jià)的說(shuō)法有xy mod m當(dāng)且僅當(dāng)m|x-y。 2.同余的性質(zhì) 對(duì)于固定的整數(shù)m，模m同余是一個(gè)等價(jià)關(guān)系。 自反性：對(duì)于任意的x，總有xx mod m； 對(duì)稱性：xy mod m yx mod m； 傳遞性：xy mod m,yz mod mxz mod m。 其他性質(zhì)： (1) xy mod m axay mod m,xay

9、a mod m； (2) xy mod m axay mod am, a0； (3) (ab) mod m(a mod mb mod m) mod m。,第五章 整除和同余,3.命題 兩個(gè)整數(shù)x和x，x=qm+r,x=qm+r,0r,r |m|，則xx mod m當(dāng)且僅當(dāng)rr mod m。 對(duì)于固定的模數(shù)m，如果xx，那么對(duì)于y有 x+y=x+y mod m xy=xy mod m,推論：同余直接繼承了普通算術(shù)運(yùn)算的一些性質(zhì)。 分配律：x(y+z)xy+xz mod m 加法結(jié)合律：(x+y)+zx+(y+z) mod m 乘法結(jié)合律：(xy)zx(yz) mod m 1的性質(zhì)：1xx1x m

10、od m 0的性質(zhì)：0+xx+0x mod m,第五章 整除和同余,4.Z/m或者Zm 整數(shù)模m等價(jià)類的集合 給定整數(shù)x和模數(shù)m，x模m等價(jià)類： yZ: yx mod m 通常記為x或x，稱為x模m的同余類或者剩余類。,第五章 整除和同余,例：對(duì)于模數(shù)12，有,模m等價(jià)類的集合表示形式：,模m等價(jià)類的集合,模m約簡(jiǎn)的集合,Z/m中的結(jié)論： m0 mod m x+(-x)0 mod m xkmx mod m (x+y)%m=(x%m)+(y%m)%m (xy)%m=(x%m)(y%m)%m,5.Z/mX或ZmX,ZmX= yZm|gcd(y,m)=1 即：Zm中與m互素的元素的集合。 例如：Z1

11、5X=1,2,4,7,8,11,13,14 Z11X=1,2,3,4,5,6,7,8,9,10,第五章 整除和同余,6.定理,定理1：設(shè)m,n是兩個(gè)互素的正整數(shù)，如果x,y 分別遍歷模m,n的完全(簡(jiǎn)化)剩余系， 則nx+my遍歷模mn的完全(簡(jiǎn)化)剩余系。 舉例：分別用模4和模5的完全剩余系和簡(jiǎn)化剩系 來(lái)表示模20的完全剩余系和簡(jiǎn)化剩余系。 Z4=0,1,2,3 Z4X=1,3 Z5=0,1,2,3,4 Z5X=1,2,3,4 所以：Z20=0,4,8,12,16,5,9,13,17,21,10, 14,18,22,26,15,19,23,27,31 Z20X=9,13,17,21,19,2

12、3,27,31,第五章 整除和同余,定理2：若正整數(shù)m,n，滿足gcd(m,n)=1，則有： (mn)=(m)(n)= 1 mod n,第五章 整除和同余,5.3 兩個(gè)著名的定理 1.歐拉定理,對(duì)n1,如果gcd(x,n)=1，則有：x(n)=1 mod n,2.費(fèi)馬小定理 對(duì)任意的整數(shù)x和素?cái)?shù)p，有 xp-11 mod p,3. 歐拉函數(shù)(n)的定義 對(duì)于正整數(shù)n，與其互素的小于等于n的正整數(shù)的個(gè)數(shù)表示為(n)，稱為歐拉函數(shù)。 也可以理解為ZmX中的元素個(gè)數(shù)。,第五章 整除和同余,4. 歐拉函數(shù)(n)的計(jì)算,舉例：計(jì)算(7)，(10)，(35),Z7X=1,2,3,4,5,6,所以(7)=6

13、,Z10X=1,3,7,9,所以(10)=4,Z35X=1,2,3,4,6,8,9,11,12,13,16,17,18, 19,22,23,24,26,27,29,31,32,33,34 ,所以：(35)=24,那么：(10000)=？,第五章 整除和同余,因式惟一分解定理：正整數(shù)N可以因子分解為：,舉例：N=30=235 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30,問(wèn)題：如何求歐拉函數(shù)？,其中：p1,p2,pm為素?cái)?shù),所有指數(shù)為正整數(shù)。,那么：,證明：,第五章 整除和同余,那

14、么(10000)=？,10000=2454,所以(10000)=(2-1)23(5-1)53,=84125,=4000,驗(yàn)證(35)=24,35=57,所以(35)=(5-1)51-1(7-1)71-1,=46,=24,第五章 整除和同余,小結(jié)：,(1)歐拉函數(shù)的定義,(2)歐拉函數(shù)(n)的計(jì)算方法,對(duì)于正整數(shù)n，與其互素的小于等于n的正整數(shù)的個(gè)數(shù)表示為(n)，稱為歐拉函數(shù)。,作業(yè)：,計(jì)算(28)，(1234) 。,第五章 整除和同余,傳統(tǒng)的指數(shù)運(yùn)算效率低，需改進(jìn)。 1.思想 在計(jì)算xe時(shí)，將e表示為一個(gè)二元整數(shù) e=e0+e121+e222+en2n 那么：,因此，若ek=0，可以忽略 項(xiàng)；

15、 若ek=1，則包含 項(xiàng)。,2.實(shí)現(xiàn)算法 為了計(jì)算xe，利用三元組(X,E,Y)，其初始值為： (X,E,Y)=(x,e,1),6.1指數(shù)運(yùn)算,第六章 離散對(duì)數(shù)和原根,為了計(jì)算xe，利用三元組(X,E,Y)，其初始值為： (X,E,Y)=(x,e,1) (1)若E是奇數(shù)，則Y=X*Y，E=E-1； (2)若E為偶數(shù)，則X=X*X，E=E/2； (3)當(dāng)E=0時(shí)，Y的值xe。 舉例1：計(jì)算x5 X E Y x 5 1 x 4 x x*1 x*x x2 2 x x2*x2 x4 1 x x4 0 x5 x4*x x5=x1(x4)1 (5=101,e0=1,e1=0,e2=1) 課內(nèi)作業(yè)：計(jì)算21

16、000 mod 89,第六章 離散對(duì)數(shù)和原根,第六章 離散對(duì)數(shù)和原根,6.2 相關(guān)定義 1.離散對(duì)數(shù)： 對(duì)正整數(shù)n，若gl=x mod n，則l稱為x的以g為 底模n的離散對(duì)數(shù)，記為loggx。 2.原根(本原根,生成元,本原元)： 對(duì)正整數(shù)n，如果g是模n的一個(gè)原根，那么對(duì)于 任意的xZnX，都存在d，使得gd=x mod n。 例：n=7時(shí)，3是否為其原根？ 可以驗(yàn)證，8沒(méi)有原根，2是11的原根。,舉例2：計(jì)算257%59,考慮歐拉定理，即258%59=1，所以： 257%59=2-1%59=30,第六章 離散對(duì)數(shù)和原根,3.階(指數(shù))： 對(duì)于n1，ZnX是一個(gè)有限集。若g是模n的原根，

17、則ZnX的元素列表可表示為：g,g2,g3, 對(duì)于任意的aZnX，即gcd(a,n)=1，會(huì)存在一個(gè) 正整數(shù)t滿足：at=1 mod n，而滿足該條件的最小正 整數(shù)t是a模n的指數(shù)或階。 例如：Z7X=1,2,3,4,5,6 a=2,t=3；a=3,t=6 Z10X=1,3,7,9 a=3,t=4 4.定理： (1)一個(gè)模n的原根g具有最大的階(n) (2)若g是模n的原根，l滿足gl=1 mod n，則(n)|l (3)若g不是模n的原根，t滿足gt=1 mod n，則t|(n),第六章 離散對(duì)數(shù)和原根,2.原根存在的條件 對(duì)于那些原根的整數(shù)n，它們具有如下形式： (1) n=pe ,p為奇

18、素?cái)?shù),e1； (如9) (2) n=2pe ,p為奇素?cái)?shù),e1； (如6) (3) n=2,4； 特別地，存在模素?cái)?shù)的原根。,1.定理： (1)一個(gè)模n的原根g具有最大的階(n) (2)若g是模n的原根，l滿足gl=1 mod n，則(n)|l (3)若g不是模n的原根，t滿足gt=1 mod n，則t|(n),6.3 原根的特性,第六章 離散對(duì)數(shù)和原根,1.定理： 設(shè)n1, (n)=q1q2qk，則g是模n的一個(gè) 原根的充要條件是：,6.4 原根的測(cè)試,2.對(duì)于素?cái)?shù)p，令p-1=q1q2qk，計(jì)算：,第六章 離散對(duì)數(shù)和原根,舉例：p=11, p-1=10=25 (1)當(dāng)g=2時(shí)，2(11-1

19、)/2 mod 11=32 mod 11=10 2(11-1)/5 mod 11=4 mod 11=4 所以：2是原根。 (2)當(dāng)g=3時(shí)，3(11-1)/2 mod 11=243 mod 11=1 3(11-1)/5 mod 11=9 mod 11=9 所以：3不是原根。,作業(yè)：,(1)用快速指數(shù)算法計(jì)算256%1001。 (2)用快速指數(shù)算法計(jì)算23519%521。 (2)求以2為底模25的3的離散對(duì)數(shù)。 (3)證明2不是模23的原根。,第七章 公鑰密碼算法,所有的傳統(tǒng)密碼以及DES、AES等現(xiàn)代密碼 都是一種對(duì)稱算法，即解密密鑰等價(jià)于加密密鑰； 非對(duì)稱密碼算法中，加密密鑰和解密密鑰是不相

20、 同的，因而可以將加密密鑰公開(kāi)，將解密密鑰保密。 公鑰密碼的思想1976年被提出； 典型的有：RSA,ElGamal,Knapsnack,ECC等。,對(duì)稱密碼與公鑰密碼的特點(diǎn)： (1)對(duì)稱密碼算法速度快； (2)非對(duì)稱密碼密鑰管理簡(jiǎn)單。 實(shí)際網(wǎng)絡(luò)應(yīng)用中，采用非對(duì)稱密碼來(lái)交換對(duì)稱密 碼算法的密鑰。,7.1 概述,第七章 公鑰密碼算法,對(duì)稱密碼算法,公鑰密碼算法,加密,第七章 公鑰密碼算法,公鑰密碼算法,簽名,混合加密通信,第七章 公鑰密碼算法,7.2 陷門,每個(gè)非對(duì)稱密碼算大都依賴于數(shù)論中某些處理 過(guò)程的不可逆性，稱為陷門。 RSA密碼：因子分解難題；,ECC：橢圓曲線上的離散對(duì)數(shù)難題，aP=Q

21、；,易：a,PQ,難：P,Qa,第七章 公鑰密碼算法,7.3 RSA算法,由Rivest、Shamir和Adlemar開(kāi)發(fā)，既能加密 又可簽名，易理解和實(shí)現(xiàn)，因而最流行。,密鑰的生成： (1)選擇兩個(gè)大素?cái)?shù)p和q，計(jì)算： n=pq以及(n)=(p-1)(q-1)； 例如：p=11,q=17; n=187, (n)=1016=160 (2)選擇隨機(jī)數(shù)1e10150，一個(gè)模p的原根g以及隨機(jī) 整數(shù)x(1xp)，計(jì)算y=gx mod p，則 公鑰為(y,g,p)，私鑰為x,7.4 ElGamal算法,2.ElGamal加密消息m 選擇隨機(jī)數(shù)k，得到密文對(duì)(a,b)為： (a=gk mod p, b=

22、myk mod p) 解密消息：ba-x mod p=myk(gk)-x mod p=m,第七章 公鑰密碼算法,(1)Bob選擇隨機(jī)數(shù)k=4，計(jì)算得到的密文： a=gk mod p=24 mod 11=5 b=myk mod p=354 mod 11=5 (2)Alice對(duì)收到的密文(5,5)解密： ba-x mod p=55-4 mod 11=3,選p=11,g=2,私鑰x=4,則公鑰y=gx mod p=5 Bob要將消息m=3傳送給Alice。,3.舉例,第七章 公鑰密碼算法,第一個(gè)公鑰算法，由Ralph Merkle和Martin Hellman開(kāi)發(fā)，只能用于加密。 1.描述 b=a1

23、x1+a2x2+anxn 明文分組長(zhǎng)度為n，消息為x1xn，密文為b。 舉例1：明文：1 1 1 0 0 1 背包：1 5 6 11 14 20 密文：b=1+5+6+20=32 解密：32=1x1+5x2+6x3+11x4+14x5 +20 x6 奧妙在于背包問(wèn)題有兩種： 普通背包：難解；超遞增背包：易解。,7.5 Knapsnack算法,26次測(cè)試,第七章 公鑰密碼算法,超遞增背包： a1+a2+ai3)上的橢圓曲線群 Ep(a,b): y2=x3+ax+b (mod p),a,bGF(p) 4a3+27b20,第七章 公鑰密碼算法,2.橢圓曲線的基本性質(zhì),設(shè)P,QEp(a,b),則 P+

24、O=P, P+Q=Q+P。 若P+Q=O,則Q=-P為P的加法逆元。 設(shè)P=(x1,y1),Q=(x2,y2),P-Q,則P+Q=(x3,y3) 由以下規(guī)則確定： x3=2-x1-x2 (mod p) y3=(x1-x3)-y1 (mod p),點(diǎn)Q的倍數(shù)定義如下： 在Q點(diǎn)做一條切線，與橢圓曲線相交于點(diǎn)S，則 2Q=Q+Q=-S 在Ep(a,b)中有P,Q,Q=kP,kp,則有,第七章 公鑰密碼算法,3.Diffie-Hellman密鑰交換協(xié)議,通信雙方事先不需要保密信道交換密鑰，可以 協(xié)商共享密鑰； 安全性基于離散對(duì)數(shù)難題。 Alice和Bob協(xié)商好一個(gè)大素?cái)?shù)p和一個(gè)模p的原根g。,選x,g

25、x mod p,gy mod p,選y,竊聽(tīng),公共網(wǎng)絡(luò),Alice,Bob,Eve,第七章 公鑰密碼算法,4.橢圓曲線上的密碼算法,(1) Diffie-Hellman密鑰交換： 先取素?cái)?shù)p2180和兩個(gè)參數(shù)a,b，得到滿足方程 y2=x3+ax+b (mod p),4a3+27b20的橢圓曲線以及其 上面的點(diǎn)構(gòu)成的Abel群EP(a,b)。G是EP(a,b)的生成元。,(2)橢圓曲線上的加密算法ECC： 選取橢圓曲線得到Abel群EP(a,b)，G是EP(a,b) 的生成元，公開(kāi)。 將明文消息m通過(guò)編碼嵌入到曲線上的點(diǎn)Pm，再對(duì) 點(diǎn)Pm做加密變換。,第七章 公鑰密碼算法,設(shè)用戶Bob的私鑰n

26、B,公鑰為PB=nBG; Alice將消息m發(fā)送給Bob。,舉例： 選E:y2=x3+x+6 (mod 11)，生成元G=(2,7) 首先計(jì)算2G： 因?yàn)椋?(3x12+1)/2y1=(322+1)/(27) (mod 11) =8 于是：x3=2-x1-x2 (mod 11)=5 y3=(x1-x3)-y1 (mod 11)=2 所以：2G=(5,2),第七章 公鑰密碼算法,同理，經(jīng)計(jì)算后可知G的階為13: G=(2,7),2G=(5,2),3G=(8,3),4G=(10,2) 5G=(3,6),6G=(7,9),7G=(7,2),8G=(3,5) 9G=(10,9),10G=(8,8),1

27、1G=(5,9),12G=(2,4) 將明文對(duì)應(yīng)于橢圓曲線上的點(diǎn)Pm。 加解密過(guò)程為： 1)設(shè)Bob的私鑰nB=7，則公鑰PB=7G=(7,2) 2)Alice加密消息Pm=(10,9)，首先選取隨機(jī)數(shù)k=3， 計(jì)算： Cm=kG,Pm+kPB=(8,3),(10,2) 3)Bob用私鑰nB解密： Pm=(10,2)-7(8,3)=(10,9),第七章 公鑰密碼算法,(3)橢圓曲線密碼ECC與RSA相比： 安全性高；密鑰量??；靈活性好。,第七章 公鑰密碼算法,7.7雙線性映射(Weil pairing),1.雙線性映射的性質(zhì),設(shè)(G1,+)和(G2,)為兩個(gè)q階循環(huán)群。 雙線性對(duì)： G1G1G

28、2 滿足如下的屬性： 雙線性：對(duì)于任意P,Q,RG1和a,bZqx (1) (P,P)=1; (2) (P+Q,R)=(P,R)(Q,P); (3) (R,P+Q)=(R,P)(P,Q); (4) (aP,bQ)=(abP,Q) =(P,abQ)=(P,Q)ab; 非退化性：存在P,QG1，使得(P,Q)1 可計(jì)算性：對(duì)于任意的P,QG1，存在一個(gè)高效的 算法計(jì)算(P,Q)。,第七章 公鑰密碼算法,(1) PKG選擇s,公開(kāi)G,sG;給用戶分配私鑰： Alice公鑰為QA,私鑰為sQA; Bob公鑰為QB,私鑰為sQB.,2.雙線性對(duì)用于密鑰分配,(2) 通信方在沒(méi)有對(duì)話的情況下得到共享密鑰：

29、 PKG公開(kāi)G,網(wǎng)絡(luò)中用戶的私鑰分別為a,b,c； 公鑰為PA=aP,PB=bP,PC=cP。 三方的共享密鑰為： kABC=(PB,PC)a=(PA,PC)b=(PA,PB)c,第八章 同余方程,1.費(fèi)馬小定理,8.1梅森數(shù)的分解,定理：p是一個(gè)素?cái)?shù)，對(duì)任意的整數(shù)x有 xp=x mod p 證明：首先，根據(jù)二項(xiàng)式定理：,當(dāng)0i1，對(duì)任意兩個(gè)整數(shù)m,n，有： gcd(bm-1,bn-1)=bgcd(m,n)-1,證明： 首先證明：如果d|n，則有： (bd-1)|(bn-1)和(ad-bd)|an-bn) 這是因?yàn)椋?xN-1=(x-1)(xN-1+xN-2+x2+x+1),N=n/d,第八章

30、 同余方程,用歸納法證明： 1)如果m=n，則命題為真； 2)假設(shè)mn 如果m=n=1,gcd(b-1,b-1)=b-1為真； 因?yàn)閙n，則有 bn-m-1=(bn-1)-bn-m(bm-1) gcd(bm-1,bn-1)=gcd(bm-1,bn-m-1) 這是因?yàn)椋?如果d|bn-1且d|bm-1，則d|(bn-1)-bn-m(bm-1) 根據(jù)歸納法假設(shè)： gcd(bm-1,bn-1)=gcd(bm-1,bn-m-1) =bgcd(m,n)-1 接下來(lái)只要證明 gcd(m,n)=gcd(m,n-m)即可,第八章 同余方程,(2)推論 對(duì)給定的正整數(shù)b,n，如果素?cái)?shù)p|bn-1，那么對(duì) n的因

31、子d，有： p|bd-1 或者p=1 mod n 證明： 根據(jù)費(fèi)馬小定理有 bp = b mod p bp-1 = 1 mod p p|bp-1-1 根據(jù)引理，有p|bgcd(n,p-1)-1 (因?yàn)閜|bn-1) 設(shè) d=gcd(n,p-1) 若 d2，對(duì)整數(shù)b有：,第九章 二次符號(hào),9.3 二次符號(hào)的性質(zhì),第九章 二次符號(hào),設(shè)p為奇素?cái)?shù)，n為奇整數(shù) (1) 若a=b mod p，則(a/p)=(b/p)； 若a=b mod n，則(a/n)=(b/n) (2) (ab/p)=(a/p)(b/p)； 若a,b與n互素，則(ab/n)=(a/n)(b/n) (3) (a2/p)=1； 若gcd

32、(a,n)=1，則(a2/n)= (a/n2)=1 (4) (a+p/p)=(a/p)； (a+n/n)=(a/n) (5) (1/p)=1； (1/n)=1 (-1/p)=(-1)(p-1)/2；(-1/n)=(-1)(n-1)/2 (2/p)=(-1)(p2-1)/8；(2/n)=(-1)(n2-1)/8,第九章 二次符號(hào),(6)二次互反定理,如果p,q是不同的奇素?cái)?shù)，那么 (p/q)=(-1)(p-1)(q-1)/4 (q/p),如果m,n是大于2的奇數(shù)，那么 (m/n)=(-1)(m-1)(n-1)/4 (n/m),9.4 使用二次符號(hào)判定平方剩余,Jacobi符號(hào)=1不能判定方程是否

33、有解； Jacobi符號(hào)=-1可以判定方程無(wú)解。 Legendre符號(hào)=1可以判定方程有解； Legendre符號(hào)=-1可以判定方程無(wú)解。,第九章 二次符號(hào),舉例1：測(cè)試x2=19 mod 101是否有解？ 解：(19/101) =(-1)(19-1)(101-1)/4(101/19) =(6/19) =(2/19)(3/19) (2/19) = (-1)(192-1)/8 =-1 (3/19) =(-1)(3-1)(19-1)/4(19/3) =-(1/3) =-1 所以， (19/101) =(2/19)(3/19)=1 因此，方程有解。,第九章 二次符號(hào),舉例2：測(cè)試x2=1237 mo

34、d 4327是否有解？ 解：(1237/4327) =(-1)12364326/4(4327/1237) =(616/1237) =(8/1237)(7/1237)(11/1237) =1 (8/1237)=(2/1237)=(-1)(12372-1)/8 = (7/1237)=(-1)61236/4(1237/7) =(5/7)=(-1)46/4(2/5)=-1 (11/1237)=(-1)101236/4(1237/11) =(5/11)=(-1)410/4(1/5)=1 所以， (1237/4327)=-1(-1)1=1 因此，方程有解。,第九章 二次符號(hào),舉例3：測(cè)試x2=2 mod

35、3599是否有解？ 由于3599=5961，所以方程等價(jià)于 x2=2 mod 59 x2=2 mod 61 (2/59)= (-1)(592-1)/8 =-1 無(wú)解 (2/61)= (-1)(612-1)/8 =-1 無(wú)解 所以方程x2=2 mod 3599無(wú)解 而根據(jù)Jacobi符號(hào)有 (2/3599)= (2/59)(2/61) =1 因此：Jacobi符號(hào)=1不能判定方程是否有解,作業(yè)： (1)判斷2是否為模1033的一個(gè)平方？ (2)判斷方程x2=119 mod 1009是否有解？ (3)判定3是不是模2009的一個(gè)平方？,第十章 素性測(cè)試,10.1 Miller-Rabin素性檢測(cè)算

36、法,許多密碼算法和協(xié)議需要“隨機(jī)”的大素?cái)?shù)， 而大素?cái)?shù)的生成，常用的方法是隨機(jī)生成一個(gè)整 數(shù)n，然后對(duì)其進(jìn)行素性測(cè)試。 方法：(1)窮舉法； (2)概率素性測(cè)試。-概率素?cái)?shù)(偽素?cái)?shù)),1.強(qiáng)偽素?cái)?shù) 如果p是一個(gè)素?cái)?shù)，則Z/p中應(yīng)該只有1的兩個(gè) 平方根，即1和p-1。 設(shè)n是奇整數(shù)，因式分解為： n-1=2rm m為奇數(shù) 如果bm=1 mod n，或?qū)δ承?sr，滿足 b2sm=-1 mod n，則n是基數(shù)為b的強(qiáng)偽素?cái)?shù)。,第十章 素性測(cè)試,2.檢測(cè)算法： 可以證明合數(shù)的確定性，但只能以一定的概 率說(shuō)明素性性。步驟為： 首先，因式分解n-1=2rm m為奇數(shù)； 隨機(jī)選1bn-1； 設(shè)s=0，計(jì)算

37、z=bm mod n,如果z=1，則停止，n以3/4的概率是素?cái)?shù)， b是n是素?cái)?shù)的證據(jù)。 否則繼續(xù)：s=s+1，計(jì)算z=z2 mod n。 若sr且z=-1，停止，p以3/4的概率為素?cái)?shù)； 若z=1，p為合數(shù)，終止測(cè)試。 若s=r，且沒(méi)有一個(gè)z等于-1，則p為合數(shù)； 以上步驟重復(fù)k次，若每個(gè)b都說(shuō)明n以3/4的概 率是素?cái)?shù)，則n是素?cái)?shù)的概率為1-(1/4)k。,第十章 素性測(cè)試,舉例：證明合數(shù)1281對(duì)基數(shù)41是強(qiáng)偽素?cái)?shù)。 解：1281-1=528 r=8,m=5 首先驗(yàn)證b0=415 mod 1281=？ 41 5 1 41 4 41 400 2 41 1156 1 41 0 115641=

38、47396 mod 1281=-1 所以1281對(duì)基數(shù)41是強(qiáng)偽素?cái)?shù)。,第十章 素性測(cè)試,第十章 素性測(cè)試,10.2 Lehmann素性檢測(cè)算法,(1)隨機(jī)選a1 1 若n為素?cái)?shù)，可判定x2=b mod n有解 -1 若x2=b mod n無(wú)解,(b/n)=,(3)歐拉證明了，對(duì)素?cái)?shù)p有： (b/p)=b(p-1)/2 mod p 相反，如果n不是素?cái)?shù)，則b(n-1)/2 mod n對(duì)于不 同的b就是隨機(jī)。 同樣，如果(b/n)=b(n-1)/2 mod n，則整數(shù)n是基 數(shù)為b的歐拉偽素?cái)?shù)，b稱為歐拉證據(jù)。,第十章 素性測(cè)試,2.算法描述 (1)隨機(jī)選an; (2)若gcd(a,n) 1，則

39、n為合數(shù)，終止。 (3)計(jì)算j=a(n-1)/2 mod n和J=(a/n): 若jJ，則n為合數(shù)，終止。 若jJ，n以50%概率為素?cái)?shù)，繼續(xù)； (4)對(duì)a選t次重復(fù)，n以(1-1/2t)概率為素?cái)?shù)。,3.費(fèi)馬偽素?cái)?shù) (1)設(shè)gcd(n,b)=1，如果bn-1 =1 mod n ，則整 數(shù)n對(duì)于基數(shù)b是費(fèi)馬偽素?cái)?shù)。 (2)一個(gè)非素?cái)?shù)對(duì)于不同的基數(shù)有不同的表現(xiàn)。 舉例：整數(shù)n為91=713，基數(shù)b分別2和3。,第十一章 因式分解,11.1 Pollards Rho算法,大整數(shù)分解是許多密碼學(xué)算法和協(xié)議的安全 依據(jù)，如RSA密碼體制。 方法：(1)窮舉法； (2)分解算法。,可以較快地找到合數(shù)的較

40、小因子。 1.算法描述 給定整數(shù)n，設(shè)初始值x=2，y=x2+1； (1)計(jì)算g=gcd(x-y,n)； (2)若1n1/2不滿足，則還需考慮b0，使得： b0n-1=1 mod n 且 gcd(b0k-1,n)=1,舉例驗(yàn)證： (1) n=31 (2) n=103,3.推論 設(shè)n=u2m+1，n為奇數(shù)且u2m。 若存在一個(gè)b，使得b(n-1)/2=-1 mod n，則n為素?cái)?shù)。 舉例驗(yàn)證：n=13=322+1； n=41=523+1,第十一章 因式分解,11.4 二次篩法 因子基：前t個(gè)素?cái)?shù)的集合S=2,3,5,7, S平滑：整數(shù)n的所有因子都小于等于S。 算法：試圖分解整數(shù)n。 (1)選擇

41、一個(gè)因子基S=2,3,5,7, ; (2)選取 ，取b=ai2%n; (3)若b是S平滑的，且為一個(gè)平方，則可通過(guò) 計(jì)算n的因子。 舉例：n=143,第十二章 離散對(duì)數(shù),12.1 離散對(duì)數(shù)問(wèn)題,很多秘密技術(shù)的安全性都建立在離散對(duì)數(shù) 問(wèn)題的困難上，如ECC密碼體制。,1.離散對(duì)數(shù) 對(duì)正整數(shù)n，若bl=a mod n，則l稱為a的以b為 底模n的離散對(duì)數(shù)，記為logba。 2.離散對(duì)數(shù)問(wèn)題DLP 給定素?cái)?shù)p，Zpx的生成元b和元素aZpx ，求解 x滿足：bx=a mod p 3.廣義離散對(duì)數(shù)問(wèn)題GDLP 給定階為n的有限循環(huán)群G，G的生成元b和元素 aG，求解x滿足：bx=a mod n,第十二

42、章 離散對(duì)數(shù),12.1 Baby-step Giant-step算法 p為素?cái)?shù)，b是模p的一個(gè)本原根，m是不超過(guò) 的最大正整數(shù)，計(jì)算步驟如下：,(1)計(jì)算(0,b0%p),(1,b1%p), (m-1,bm-1%p) (2)按照第二分量的大小排序； (3)計(jì)算c=b-m%p; 初始化x=a; 對(duì)0im，若x是表b0,b1,bm-1中的bj， 則logba =mi+j; 否則，x=xc mod p,i=i+1 舉例：計(jì)算log211 mod 227 作業(yè)：利用Baby-step算法求log25 mod 29。,第十二章 離散對(duì)數(shù),12.2Pollard的Pho方法 定義函數(shù)F： (ax,m+1,

43、n) 若xis1 F(x,m,n)= (x2,2m,2n) 若xis2 (bx,m,n+1) 若xis3 計(jì)算步驟如下： (1)選取子集s1,s2,s3； (2)初始化(x,mx,nx,y,my,ny)=(1,0,0,1,0,0)；,(3)重復(fù)步驟：(x,mx,nx)=F(x,mx,nx) (y,my,ny)=F(F(y,my,ny) 直到x=y，則logba=(my-mx)-1(nx-ny) mod |G| G為Zpx的一個(gè)子群，且包含模p的平方(循環(huán)子群) 如p=59時(shí)，2為其本原根，4=22為其循環(huán)子群， 則G由b=4生成，其階|G|=29。求log49 mod 59。,第十二章 離散對(duì)數(shù),12.3指數(shù)演算 原理：利用已知的因子基德離散對(duì)數(shù)進(jìn)行運(yùn)算 設(shè)b是循環(huán)群G的生成元，n=|G| (1)對(duì)于b，取因子基S=p1,p2,=2,3,5,； (2)考慮b的隨機(jī)方冪，開(kāi)始生成關(guān)系： logbp1,logbp2,(3)對(duì)給定的aG，選擇隨機(jī)整數(shù)k，并嘗試： abk=p1k1ptkt mod n 如果成功，則可求解： logba=k1logbp1+ktlogbptk mod |G| 舉例：設(shè)G=Z/X29，n=|G|=28，選原根b=11， 因子基S=2,3,5，求log117。,第十三章 協(xié)議經(jīng)典算法,13.1 秘密共