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í)形式) 隱寫術(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+0 x 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互素的元素的集合。 例如：Z

11、15X=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,

12、23,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)=

13、6,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ì)算2

16、1000 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-

19、1)/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、相 同的，因而可以將加密密鑰公開，將解密密鑰保密。 公鑰密碼的思想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=

21、Q；,易：a,PQ,難：P,Qa,第七章 公鑰密碼算法,7.3 RSA算法,由Rivest、Shamir和Adlemar開發(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ù)1e(n),gcd(e,(n)=1，計(jì)算： d=e-1 mod (n)； 例如：e=7,則d=23,1.RSA算法過(guò)程,第七章 公鑰密碼算法,(3)則公鑰為(e,n)，私鑰(d,n)； 例如：公鑰為(7,187);私鑰為(23,187) 加密m：c

22、=me mod n 解密c：m=cd mod n RSA比較慢，一般選e為3,17,65537等等。 公鑰私鑰的關(guān)系： d=e-1 mod (n)； 已知e和n，要得到d，需要知道(n)，由(n)的 計(jì)算公式(n)=(p-1)(q-1)可知需要知道n的因子 分解。當(dāng)n很大時(shí)，這是一個(gè)難題。,第七章 公鑰密碼算法,Bob的公鑰為(7,187)，私鑰為(23,187)； Alice要將保險(xiǎn)柜密碼88發(fā)送Bob。,密碼分析,公共網(wǎng)絡(luò),Alice,Bob,88,887 mod 187=11,11,1123 mod 187=88,Eve,2.舉例,第七章 公鑰密碼算法,(1)歐拉定理：如果gcd(x,n

23、)=1，則有： x(n)=1 mod n (2)明文x與模數(shù)n要互素，不互素的概率為：,(3)e,d必須與(n)互素； (4)具有形式為n=pq的整數(shù)稱為Blum整數(shù)。 其中p和q都是模4同余3的素?cái)?shù)。,3.可解性分析,第七章 公鑰密碼算法,依賴于將整數(shù)n分解為素因子的難度。 EDI攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長(zhǎng)度為512至1024比特位之間，且為128的倍數(shù)。 國(guó)際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC 9796中規(guī)定n的長(zhǎng)度位512比特位。,從安全性考慮，p與q必為足夠大的素?cái)?shù)，使n的分解無(wú)法在多項(xiàng)式時(shí)間內(nèi)完成。要求n至少要有1024或者2048比特(十進(jìn)制的308位或616位)。,4.安全性分

24、析,第七章 公鑰密碼算法,1985年發(fā)表，既可用于數(shù)字簽名又用于加密。 其安全性依賴于離散對(duì)數(shù)難題。 離散對(duì)數(shù)問(wèn)題DLP：給定素?cái)?shù)p，ZnX的一個(gè)原根 b和一個(gè)元素c。求解x，使得bx=c mod p。 1.描述 選取素?cái)?shù)p10150，一個(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=myk mod p) 解密消息：ba-x mod p=myk(gk)-x mod p=m,第七章 公鑰密碼算法,(1)Bob選擇隨

25、機(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開發(fā)，只能用于加密。 1.描述 b=a1x1+a2x2+anxn 明文分組長(zhǎng)度為n，消息為x1xn，密文為b。 舉例1：明文：1 1 1 0 0 1 背包：1 5 6 1

26、1 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+aiai+1 于是存在一個(gè)較簡(jiǎn)單的方法解決Knapsnack問(wèn)題。 如果ban，則an不可能出現(xiàn)在大小為b的背包中； 如果ban，則an必須出現(xiàn)在大小為b的背包中。 舉例： 70=2x1+3x2+6x3+13x4+27x5+52x6 問(wèn)題：授權(quán)者能解密，非授權(quán)者亦可。 解決：將超增長(zhǎng)背包轉(zhuǎn)換為普通背包。,第七章 公鑰密碼算法

27、,2.Knapsnack算法過(guò)程 (1)密鑰的生成： 選擇一個(gè)超遞增(a1,an)、整數(shù)m(ma1+an, gcd(ai,m)=1)以及t(gcd(t,m)=1)； 計(jì)算： ci=tai mod m 則：背包序列(c1,c2,cn)為公鑰； 私鑰為(a1,an)和t。 (2)加密： 加密n位的消息x=(x1,xn)，得到密文： b=c1x1+c2x2+cnxn (3)解密： t-1b= t-1(c1x1+c2x2+cnxn) =a1x1+a2x2+anxn,第七章 公鑰密碼算法,3.舉例： 選m=105，t=31，則 2,3,6,13,27,52 62,93,81,88,102,37 加密消息

28、110101得到密文b=280 解密消息： 計(jì)算 28031-1%105=70 2x1+3x2+6x3+13x4+27x5+52x6=70 1 1 0 1 0 1,第七章 公鑰密碼算法,7.6橢圓曲線密碼算法,1985年N.Koblitz和V.Miller分別獨(dú)立提出了 橢圓曲線密碼體制(ECC)。其安全性依賴于定義在 橢圓曲線點(diǎn)群上的離散對(duì)數(shù)問(wèn)題(ECDLP)的難解性。 1.橢圓曲線的基本概念 已知有限域GF(p)(p=qn,q3)上的橢圓曲線群 Ep(a,b): y2=x3+ax+b (mod p),a,bGF(p) 4a3+27b20,第七章 公鑰密碼算法,2.橢圓曲線的基本性質(zhì),設(shè)P,

29、QEp(a,b),則 P+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和一

30、個(gè)模p的原根g。,選x,gx 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) 的生成元，公開。 將明文消息m通過(guò)編碼嵌入到曲線上的點(diǎn)Pm，再對(duì) 點(diǎn)Pm做加密變換。,第七章 公鑰密碼

31、算法,設(shè)用戶Bob的私鑰nB,公鑰為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

32、),10G=(8,8),11G=(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)群

33、。 雙線性對(duì)： G1G1G2 滿足如下的屬性： 雙線性：對(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,公開G,sG;給用戶分配私鑰： Alice公鑰為QA,私鑰為sQA; Bob公鑰為QB,私鑰為sQB.,2.雙線性對(duì)用于密鑰分配,(2) 通信方在沒(méi)有

34、對(duì)話的情況下得到共享密鑰： PKG公開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)0ip時(shí)，素?cái)?shù)p整除二項(xiàng)式系數(shù)：,使用歸納法證明費(fèi)馬小定理： (1) 顯然，1p=1 mod p； (2) 假設(shè)對(duì)特定的整數(shù)x，存在: xp=x mod p,第八章 同余方程,然后有：,因此： (x+1)p=xp+0+1=x+1 mod p,2.特

35、殊的因式分解表達(dá)式 (1)引理 如果b1，對(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,第八章 同余方程,用歸納法證明： 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|

36、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的因子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) 若 dn，則d為n的正因子，且滿足p|bd-1

37、； 若 d=n，則n|p-1，即p=1 mod n,第八章 同余方程,(3)結(jié)論 特別地，對(duì)于奇素?cái)?shù)p和奇數(shù)n，有p=1 mod 2n；,找bn-1的素因子p,若n有因子d，先找p|bd-1,然后，找p=1 mod 2n,3.梅森數(shù)的分解 (1)分解127=27-1 解：由于7是素?cái)?shù)，故可能的因子p必須滿足 p= 1 mod 14 可能的因子為：15,29,43, 另一方面，由于 12，所以127為素?cái)?shù)。,X,第八章 同余方程,(2)分解8191=213-1 解：由于13是素?cái)?shù)，故可能的因子p必須滿足 p= 1 mod 26 可能的因子為：27,53,79 故可以測(cè)試53和79，均不被8191

38、整除 所以8191為素?cái)?shù)。,X,(3)分解14348906=315-1 解：由于15=35，故具有因子：2,13,121 有14348906/(213121)=4561 針對(duì)4561，嘗試滿足p=1 mod 30的因子為：31,61 ( ) 測(cè)試4561都不能整除31和61，所以4561為素?cái)?shù)，所以：14348906= 21311114561,第八章 同余方程,8.2 一次同余式 1.定理 設(shè)m不整除a，模m的一次同余式ax=b(mod m) 有解的充要條件是(a,m)|b。有解的解數(shù)是(a,m)， 若x0是它的一個(gè)解，則它的(a,m)個(gè)解為：,2.分析 若ax=b(mod m)有解x=x1(

39、mod m)，則存在某個(gè) 整數(shù)y1，使得ax1=b+my1 (mod m)，則有(a,m)|b。 反之若(a,m)|b，則有：as+mr=(a,m) 從而有：,因此,是方程的解。,第八章 同余方程,3.舉例 (1)6x=2 (mod 9) (2)3x=2 (mod 5) (3)3x=15 (mod 6) (4)19x=38 (mod 57),解:,(1)因?yàn)?6,9)=3不整除2，無(wú)解；,(2)因?yàn)?3,5)=1|2，有解，解為x=4 (mod 5)；,(3)因?yàn)?3,6)=3|15，有解，解為： x=-1,1,3 (mod 6)；,(4)因?yàn)?19,57)=19|38，有解，觀察可得解為：

40、x=2 (mod 57) 所以同余式的所有解為： x=2+3i(mod 57) i=0,1,2,18,第八章 同余方程,8.3 二次同余式與n次剩余 1.二次同余式 二次同余式的一般形式為： ay2+by+c=0 (mod m) m為正整數(shù)且a0 將其化簡(jiǎn)為：(2ay+b)2=b2-4ac (mod m) 等價(jià)于：x2=d (mod m) 其中(d,m)=1,2.平方剩余 m為正整數(shù)，(a,m)=1，若同余式x2=a (mod m) 有解，則a稱為模m的平方剩余(二次剩余)；否則a稱 為模m的平方非剩余(二次非剩余)。,3.n次剩余 設(shè)m1，(a,m)=1，若同余式xn=a (mod m)有解

41、， 則a稱為模m的n次剩余；否則a稱為模m的n次非剩余。,第八章 同余方程,8.4 mod p的二次根 1.定理 p是一個(gè)滿足p=3 mod 4的素?cái)?shù)，那么對(duì)模p的平 方數(shù)y，x=y(p+1)/4 mod p是y模p的一個(gè)二次根。即 x2=y mod p，x稱為y的主二次根 證明：由于y是模p的平方數(shù)，設(shè)y=x2，則有 (y(p+1)/4)2=y(p+1)/2=xp+1=xpx=xx=y 所以x=y(p+1)/4 mod p是y模p的一個(gè)二次根。 2.舉例 (1)求6模19的主二次根 x=y(p+1)/4 mod p=65 mod 19=5 (2)課內(nèi)作業(yè)： 求3模107以及2模19的主二次根

42、,第八章 同余方程,8.5 mod p的高次根 1.定理： (1)對(duì)于素?cái)?shù)p，若gcd(n,p-1)，則每一個(gè)y都有 模p的n次根。若r是n模p-1的乘法逆元，則y模p的 一個(gè)n次根為yr mod p。 證明：驗(yàn)證(yr)n = y mod p。 (2)對(duì)于素?cái)?shù)p，若gcd(n,p-1)=n，即n|p-1，且 gcd(n,(p-1)/n)=1，若y是模p的一個(gè)n次剩余，r是n 模(p-1)/n的乘法逆元，則y模p的n次根為yr mod p。 2.舉例： (1)求2模101的立方根； (2)求58模199的11次根。,第八章 同余方程,總結(jié)： p為素?cái)?shù)，且 或者 存在：,若p3 mod 4，則滿

43、足x2=y mod p的平方根為： x=y(p+1)/4 mod p (不一定存在),若gcd(n,p-1)=1，則滿足xn=y mod p的n次根為： x=yr mod p, r=n-1 mod p-1,若n|p-1,gcd(n,(p-1)/n)=1，則滿足xn=y mod p 的n次根為：(不一定存在) x=yr mod p, r=n-1 mod (p-1)/n,第八章 同余方程,8.6 歐拉判別準(zhǔn)則,并不是任何數(shù)y都存在模p的n次根，因此在求 解之前可以用歐拉判別準(zhǔn)則進(jìn)行判定。 歐拉判別準(zhǔn)則用來(lái)有效判斷當(dāng)p=1 mod n時(shí)， 整數(shù)y是否存在模素?cái)?shù)p的n次根。,判定方法： (1)當(dāng)gcd

44、(n,p-1)=1時(shí)，所有的數(shù)y都有模p的n 次根。 例如：x3=y (mod 101) x7=y (mod 181) (2)定理：設(shè)p為素?cái)?shù)，p=1 mod n，當(dāng)且僅當(dāng) gcd(y,p)=1,y(p-1)/n=1(mod p)時(shí)，y是模p的n次冪。,第八章 同余方程,證明： 必要條件： y是模p的n次冪 y(p-1)/n=1 mod p 設(shè)y=xn mod p，有 y(p-1)/n=1 mod p= x(p-1)=1 mod p 充分條件： y(p-1)/n=1 mod p y是模p的n次冪 設(shè)g是模p的本原根，有y=grmod p y(p-1)/n=1 mod p gr(p-1)/n=1

45、 mod p (p)|r(p-1)/n (p-1)|r(p-1)/n n|r r=kn 所以 y=gr=(gk)n mod p,第八章 同余方程,(3) 推論： 設(shè)p為奇素?cái)?shù)，y和p互素，則有： y(p-1)/2=1 mod p時(shí)，y是模p的平方。 y(p-1)/2=-1 mod p時(shí)，y是模p的非平方。 舉例：14是模101的平方嗎？ 14 50 1 95 25 1 95 24 95 36 12 95 84 6 95 87 3 95 87 2 84 95 1 84 0 9584%101=1 課內(nèi)作業(yè)：68是模109的立方嗎？,第八章 同余方程,8.7 模為合數(shù)n的根,1.孫子定理(中國(guó)剩余定

46、理),設(shè)m1,m2,mk是兩兩互素的正整數(shù)，則同余 方程組 x=b1 mod m1 x=b2 mod m2 x=bk mod mk 有唯一解：x=b1T1M1+bkTkMk mod M 其中，M=m1m2mk Mi=M/mi Ti=Mi-1 mod mi,第八章 同余方程,舉例:,x=2 mod 11 x=7 mod 13 x=3 mod 7,x=2 mod 11 x=7 mod 13,(1),(2),應(yīng)用中國(guó)剩余定理，可以簡(jiǎn)化一些復(fù)雜的運(yùn)算。 如計(jì)算 47317 mod 713 解：因?yàn)?13=2331，令x=47317， 則計(jì)算x mod 713等價(jià)于求解同余方程： x=47317 mod

47、 23=1317 mod 23 x=47317 mod 31=817 mod 23,即： x=6 mod 23 x=2 mod 31 根據(jù)中國(guó)剩余定理可得解x=374(mod 713) 因此：47317 mod 713=374(mod 713),第八章 同余方程,2.模是合數(shù)的根(n=p1p2pk) 當(dāng)方程的模數(shù)為合數(shù)n(p1p2pk)時(shí)，如何求解？ 如方程 x2=a mod p1p2 (p1和p2互素) 解決辦法： 分別求解x2=a mod p1 和x2=a mod p2， 再利用孫子定理求解x2=a mod p1p2。 舉例： x2=-1 mod 131729 解： x2=-1 mod 1

48、3 x=5(mod 13) x2=-1 mod 17 x=4(mod 17) x2=-1 mod 29 x=12(mod 29),第八章 同余方程,3.模是合數(shù)的根(n=pk),亨澤爾定理：,假設(shè)f是一個(gè)多項(xiàng)式，其系數(shù)屬于Z，p為素?cái)?shù)， 如果x=x1 mod p 是同余式 f(x)=0 mod p 的一個(gè)解，且gcd(f(x1),p)=1，則同余式 f(x)=0 mod pk 有解：x=xk mod pk 其中xk由下面關(guān)系式遞歸得到： xi=xi-1-f(xi-1)f(x1)-1 mod pi i=2,k,如解方程 x2=2 mod 73，計(jì)算 mod 54。,第八章 同余方程,作業(yè)：,(1

49、)將242461=49-39寫成因子分解的形式。 (2)求2模103的主二次根。 (3)求97模101的一個(gè)立方根。 (4)求一個(gè)整數(shù)x，滿足3x=2 mod 5 4x=5 mod 7 (5)通過(guò)亨澤爾引理求解： mod 133。 (6)用歐拉判別準(zhǔn)則判定5是模109的立方嗎？,第九章 二次符號(hào),9.1 概述,問(wèn)題：給定整數(shù)n和b，x2=b mod n是否有解？ 方法：窮舉1,2,n-1。不僅可以知道二次根是 否存在，而且能找到；但是當(dāng)n很大時(shí)很難實(shí)現(xiàn)。 對(duì)于奇素?cái)?shù)p：歐拉判別準(zhǔn)則，計(jì)算b(p-1)/2 mod p。 問(wèn)題：(1)當(dāng)p和b比較大時(shí)，計(jì)算是否可以簡(jiǎn)化？ (2)當(dāng)n為合數(shù)時(shí)，如何判

50、定？ 9.2 二次符號(hào)的定義 1.二次符號(hào)或勒讓德符號(hào)(Legendre) 對(duì)奇素?cái)?shù)p，二次符號(hào)(b/p)定義為：,0 若p|b 1 若b是模p的平方剩余 -1 若b是模p的平方非剩余,3.擴(kuò)展的二次符號(hào)或雅克比符號(hào)(Jacobi) 對(duì)任意奇整數(shù)n,擴(kuò)展的二次符號(hào)(b/n)定義為：,2.定理 對(duì)于素?cái)?shù)p2，對(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/

51、n)(b/n) (3) (a2/p)=1； 若gcd(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 使用二次符

52、號(hào)判定平方剩余,Jacobi符號(hào)=1不能判定方程是否有解； 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 因此，方程有解。

53、,第九章 二次符號(hào),舉例2：測(cè)試x2=1237 mod 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 因此，方程有解

54、。,第九章 二次符號(hào),舉例3：測(cè)試x2=2 mod 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è)平方？,第十章 素

55、性測(cè)試,10.1 Miller-Rabin素性檢測(cè)算法,許多密碼算法和協(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=2

56、rm m為奇數(shù)； 隨機(jī)選1bn-1； 設(shè)s=0，計(jì)算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=47396 mod 1281=-1 所以1281對(duì)基數(shù)41是強(qiáng)偽素?cái)?shù)。,第十章 素性測(cè)試,第十章 素性測(cè)試,10.2 Lehmann素性檢測(cè)