第二章-同余-信安數(shù)學(xué)課件

學(xué)習(xí)目標(biāo)掌握同余、剩余類（系）、歐拉函數(shù)、費(fèi)馬定理、孫子定理了解同余理論和孫子定理在計(jì)算機(jī)和密碼學(xué)的應(yīng)用課程內(nèi)容的設(shè)置同余的基本概念、性質(zhì)和應(yīng)用剩余類、完全剩余系、簡(jiǎn)化剩余系及應(yīng)用歐拉函數(shù)、費(fèi)馬定理及應(yīng)用孫子定理同余式第二章-同余-信安數(shù)學(xué)課件2.0問題的提出50天后星期幾？234567天后呢？計(jì)算機(jī)中的溢出問題循環(huán)隊(duì)列的的實(shí)現(xiàn)？%2.0問題的提出50天后星期幾？234567天后呢？數(shù)學(xué)中的同余整除中：a=qb+r0≤r<b：同余就是余相等如：19=12*1+77=12*0+72.0問題的解決——同余理論07012)7-127112)19數(shù)學(xué)中的同余2.0問題的解決——同余理論00122.1同余的基本概念與性質(zhì)定義2.1.1,若r1=r2,則稱a，b模m同余：也記為：或2.1同余的基本概念與性質(zhì)定義2.1.12.1同余的基本概念與性質(zhì)例：27≡?(mod7)253天后星期幾？同時(shí)：a≡r(mod7)0≤r<7a->r是一個(gè)滿射因此：可以按不同的余數(shù)對(duì)整數(shù)分類，也就是每一類余數(shù)相同，也就是同余23=8≡1(mod7)所以253≡23*17+2≡4(mod7)2.1同余的基本概念與性質(zhì)例：27≡?(mod7)同時(shí)2.1同余的基本概念與性質(zhì)定理2.1.1同余關(guān)系是一種等價(jià)關(guān)系：自反性：對(duì)稱性：則傳遞性：則2.1同余的基本概念與性質(zhì)定理2.1.12.1同余的基本概念與性質(zhì)例:證明(mn-1,m3)=1證：設(shè)（mn-1,m3）=p所以mn-1≡0(modp),m3≡0(modp)所以m2≡mn.m2=n.m3≡0(modp),所以m≡mn.m=n.m2≡0(modp),所以1≡mn=m.n≡0(modp),所以p=12.1同余的基本概念與性質(zhì)例:證明(mn-1,m3)=1證2.1同余的基本概念與性質(zhì)性質(zhì)2.2設(shè)（1）特別的：（2)特別的：以及：（6）,且則有2.1同余的基本概念與性質(zhì)性質(zhì)2.22.1同余的基本概念與性質(zhì)性質(zhì)2.2（3）特別的：,若（m,n）=1則擴(kuò)大：擴(kuò)大：若，d|(a,b,m)則（4）d|m，則特別的：若2.1同余的基本概念與性質(zhì)性質(zhì)2.22.1同余的基本概念與性質(zhì)性質(zhì)2.2（7）若（8）（補(bǔ)充）若，則(a,m)=(b,m)例作業(yè)(1):p57第1題

2.1同余的基本概念與性質(zhì)性質(zhì)2.22.1同余的基本概念與性質(zhì)

作業(yè)(2):p57第5題2.1同余的基本概念與性質(zhì)作業(yè)(2):p57第5題2.1同余的基本概念與性質(zhì)問題：一個(gè)十進(jìn)制數(shù)，什么時(shí)候能被3整除結(jié)論：當(dāng)各位和為3的倍數(shù)時(shí)如：248901why？2.1同余的基本概念與性質(zhì)問題：一個(gè)十進(jìn)制數(shù)，什么時(shí)候能2.1同余的基本概念與性質(zhì)關(guān)鍵：10=3×3+1，100=33×3+1，……所以：若n=am10m+am-110m-1+…+a110+a0

3|n<=>3|am+am-1+…+a1+a0

2.1同余的基本概念與性質(zhì)關(guān)鍵：10=3×3+1，100=2.1同余的基本概念與性質(zhì)例：快速判斷某個(gè)數(shù)整除7的余數(shù)？10≡3(mod7),100≡30≡2(mod7),1000≡20≡-1(mod7)10002k+1≡-1(mod7),10002k≡1(mod7)若n=am1000m+am-11000m-1+…+a11000+a0對(duì)于637692≡692-637=55=6(mod7)2.1同余的基本概念與性質(zhì)例：快速判斷某個(gè)數(shù)整除7的余數(shù)？2.1同余的基本概念與性質(zhì)擴(kuò)展：怎樣快速判斷一個(gè)數(shù)可以被19整除？提示：湊成19的倍數(shù)2位數(shù)字？多于2位時(shí)？作業(yè)(3)：怎樣快速判斷一個(gè)數(shù)可以被31整除？,p57第3題2.1同余的基本概念與性質(zhì)擴(kuò)展：怎樣快速判斷一個(gè)數(shù)可以被12.1同余的基本概念與性質(zhì)補(bǔ)充，性質(zhì)2.2（7）的特殊情況（1）若P,q不同素?cái)?shù)，2.1同余的基本概念與性質(zhì)補(bǔ)充，性質(zhì)2.2（7）的特殊情況2.1同余的基本概念與性質(zhì)例：p,p+10,p+14均是素?cái)?shù)？求p因?yàn)?0=2*5，14=2*7，所以p≠2,5,7對(duì)于p=3，若p≡1(mod3)，則p+14≡0(mod3)，排除若p≡2(mod3)，則p+10≡0(mod3)，排除所以p≡0(mod3)因?yàn)閜素，所以p=32.1同余的基本概念與性質(zhì)例：p,p+10,p+14均是素2.1同余的基本概念與性質(zhì)（補(bǔ)充），則存在唯一使

因?yàn)榇嬖赼x+my=1即ax-1=my若存在x1和x2兩個(gè)逆元，則x1*a*x2≡x1≡x2(modm)如若(a,m)≠1，則a-1不存在2.1同余的基本概念與性質(zhì)（補(bǔ)充）2.1同余的基本概念與性質(zhì)求5模11的逆元11=5*2+15*2≡-1(mod11)5*(-2)≡1(mod11)5模11的逆元為-2（但更常寫為9）求233模1211的逆元1211=233*5+46233=46*5+346=3*15+11=46-3*15=46-(233-46*5)*15=46*76-233*15=(1211-233*5)*76-233*15=1211*76-233*395所以–395為所求2.1同余的基本概念與性質(zhì)求5模11的逆元11=5*2+12.1同余的基本概念與性質(zhì)求解方程17x≡4(mod19)19=17+217=8*2+1所以17*9-19*8=1所以17*9≡1(mod19)因?yàn)?4,9)=1所以17*36≡4(mod19)，所以x≡36≡-2(mod19)作業(yè)(4):p59第25題(1)(3)2.1同余的基本概念與性質(zhì)求解方程17x≡4(mod2.2同余的應(yīng)用主要應(yīng)用補(bǔ)碼、隨機(jī)數(shù)、文件系統(tǒng)、hash、密碼、檢錯(cuò)碼等編程時(shí)求余的主要實(shí)現(xiàn)modexcel、vb、asp、delphi、vfp等%c、c++、c#、java等2.2同余的應(yīng)用主要應(yīng)用編程時(shí)求余的主要實(shí)現(xiàn)2.2同余的應(yīng)用補(bǔ)碼Two’scomplement為什么會(huì)有補(bǔ)碼如何計(jì)算口訣原理：異或：模2加2.2同余的應(yīng)用補(bǔ)碼Two’scomplement2.2同余的應(yīng)用循環(huán)隊(duì)列數(shù)組queue[max_size]隊(duì)首指針front，指向隊(duì)首元素的前一個(gè)位置隊(duì)尾指針rear，指向隊(duì)尾元素初始化front=rear=0插入元素rear=(rear+1)%max_size刪除元素front=(front+1)%max_size什么時(shí)候?yàn)榭眨渴裁磿r(shí)候?yàn)闈M元素?cái)?shù)量最多為max_size-12.2同余的應(yīng)用循環(huán)隊(duì)列2.2同余的應(yīng)用隨機(jī)數(shù)（RandomNumber）什么是隨機(jī)數(shù)有什么用：仿真、游戲、協(xié)議、密碼……srand(seed)intrand(viod)產(chǎn)生方法：利用隨機(jī)過程事先定制好的隨機(jī)數(shù)表利用數(shù)學(xué)遞推公式模擬偽隨機(jī)數(shù)（Pseudo-RandomNumber)2.2同余的應(yīng)用隨機(jī)數(shù)（RandomNumber）隨機(jī)數(shù)（RandomNumber）偽隨機(jī)數(shù)產(chǎn)生方法迭代取中法：代表性為平方取中乘同余線性乘同余，也叫混合同余改進(jìn)：2.2同余的應(yīng)用1961年由IBM提出隨機(jī)數(shù)（RandomNumber）2.2同余的應(yīng)用1962.2同余的應(yīng)用仿射密碼AffineCiphery≡ax+b(mod26)嘗試解密：casear考慮編程的解法LXWPAJCDUJCRXWBy≡x+3(mod26)凱撒密碼CaesarCipher移位密碼、加法密碼ABCDEFABCDEFXYZWXYZABCZABCDEF2.2同余的應(yīng)用仿射密碼AffineCiphery≡2.2同余的應(yīng)用012345678910111213141504812159132610143711150481259131101426153711循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)helloworldbyebyeholewdbebyloelry2.2同余的應(yīng)用0123456789101112131412.3剩余類（系）Residue同余是一種等價(jià)關(guān)系=〉可以借助同余實(shí)現(xiàn)劃分令Ca={c|}定理2-1(1)任意整數(shù)都包含于一個(gè)Cr中，0≤r≤m-1(2)Ca=Cb<=>(3)要么Ca=Cb，要么Ca∩Cb=?(4)兩兩不同的Cr最多m個(gè)04812159132610143711152.3剩余類（系）Residue同余是一種等價(jià)關(guān)系=2.3剩余類（系）Residue定義2.2.1Ca叫模m的一個(gè)剩余類，Ca中的任一數(shù)叫該類的代表元（），若為m個(gè)整數(shù)，并且其中任兩個(gè)數(shù)都不在同一個(gè)剩余類中，叫模m的一個(gè)完全剩余系，若（r,m）=1,則這樣的剩余類叫做模m的簡(jiǎn)化（緊縮/既約）剩余系,縮系元素的個(gè)數(shù)叫做歐拉函數(shù)(m)04812159132610143711152.3剩余類（系）Residue定義2.2.1048122.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue例:a1,a2，…，an是一個(gè)模n的完系，則∑ak≡0(modn)n=2k+1n/2(modn)n=2k∑ak≡1+2+…+n≡n(1+n)/2（modn）若n=2k+1則，∑ak≡n*(k+1)≡0(modn)若n=2k則，∑ak≡k*(n+1)≡k(modn)2.3剩余類（系）Residue例:a1,a2，…，a2.3剩余類（系）Residue例2-10:a1,a2，…，an，b1,b2，…，bn是兩個(gè)模n的完系，證明：當(dāng)m是偶數(shù)時(shí)，a1+b1,a2+b2，…，an+bn一定不是模n的完系2.3剩余類（系）Residue例2-10:a1,a22.3剩余類（系）Residue例2-11設(shè)m>=3,證明(2)模m的最小正簡(jiǎn)化剩余系的各數(shù)之和等于mψ(m)/2證明：若(m,a)=1,則(m,m-a)=1所以，設(shè)ai是在1~m/2和m互素的整數(shù)所以，ai和m-ai組成了m的最小正簡(jiǎn)化剩余系共ψ(m)/2對(duì)，和為mψ(m)/2思考：為什么沒有考慮m/22.3剩余類（系）Residue例2-11設(shè)m>=3,2.3剩余類（系）Residue例：將1(mod5)寫成模15的剩余類的和例：寫出模9的完系，要求全是奇數(shù)對(duì)于10呢？作業(yè)(5):p58第9題2.3剩余類（系）Residue例：將1(mod5)寫2.3剩余類（系）Residue定理,(m,n)=1,(1)Ca,Cb為2個(gè)不同的剩余類<=>nCa,nCb為2個(gè)不同的剩余類(2)為模m的一個(gè)完系<=>為模m的一個(gè)完系為模m的一個(gè)縮系<=>為模m的一個(gè)縮系(3)為模m的一個(gè)完系<=>為模m的一個(gè)縮系<=>(4)為模m的一個(gè)完系<=>為模m的一個(gè)縮系<=>(5)則x遍歷m的一個(gè)完系，則nx+b也遍歷如m=10,n=7,b=6,則13,20,27,34,41,48,55,62,69,76為一個(gè)完系2.3剩余類（系）Residue定理2.3剩余類（系）Residue定理2-2

有所以2.3剩余類（系）Residue定理2-22.3剩余類（系）Residue定理2-32.3剩余類（系）Residue定理2-32.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue定理2-4若（m,n）=1那么呢？2.3剩余類（系）Residue定理2-4若（m,n）2.3剩余類（系）Residue關(guān)鍵n=pn時(shí)，其縮系的元素？排除與其最大公約數(shù)大于1的,也就是該數(shù)為xp(0,n-1)中，非縮系元素最小為0,最大pn-p,x取值0到pn-1–1，共pn-1個(gè)所以，如=22-2=22.3剩余類（系）Residue關(guān)鍵2.3剩余類（系）Residue作業(yè)(6)：用上面的方法計(jì)算24的歐拉函數(shù)定理2-5歐拉函數(shù)的計(jì)算p素2.3剩余類（系）Residue作業(yè)(6)：用上面的方2.3剩余類（系）Residue定理2-6設(shè)m是1,2,…,n中的任一數(shù)，可以按照(m,n)的不同對(duì)1,2,…,n分類,則n的正因子的個(gè)數(shù)即為類的個(gè)數(shù)（因?yàn)閙≤n）,各類中正整數(shù)個(gè)數(shù)之和為n。設(shè)d’為n的一個(gè)正因子，若(x,n)=d’，則(x/d’,n/d’)=1，由于x/d’≤n/d’,所以1,2,…,n中滿足x的個(gè)數(shù)等于1,2,…,n/d’中，滿足(y,n/d’)=1的y的個(gè)數(shù)，故有(n/d’)個(gè)。因此，記d=n/d’，得證2.3剩余類（系）Residue定理2-62.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue例2-14設(shè)m>=1,m|n,證n-φ(n)>=m-φ(m)等號(hào)當(dāng)且僅當(dāng)m=n時(shí)成立證明：

n-φ(n)表示n個(gè)整數(shù)中與n不互質(zhì)的整數(shù)個(gè)數(shù)m|n,所以m-φ(m)

<=n/m(m-φ(m))=n-nφ(m)/mφ(n)=φ(m).φ(n/m)<=φ(m).n/m所以m-φ(m)

<=n-φ(n)當(dāng)且僅當(dāng)m=n式成立2.3剩余類（系）Residue例2-14設(shè)m>=12.3剩余類（系）Residue2.3剩余類（系）Residue2.3剩余類（系）Residue推論：如果(p-1)!≡-1(modp)，則p是素?cái)?shù)反證：如果p=ab，a,b>=2則(ab-1)!≡-1(modab)，則(ab-1)!≡-1(moda),(ab-1)!≡-1(modb)因?yàn)閍<ab-1,所以a|(ab-1)!所以(ab-1)!≡0(moda)矛盾2.3剩余類（系）Residue推論：如果(p-1)!2.3剩余類（系）Residue例2-17設(shè)p為奇素，求證∏k2≡(-1)(p+1)/2(modp)其中1≤k≤p-2,k≡1(mod2)考慮-1(modp)是與(n-1)!同余，所以湊k≡-(p-k)(modp)而k是奇，p-k就是偶所以∏k2≡∏k∏[-(p-k)]≡(p-1)!*(-1)(p-1)/2作業(yè)(6):p58第17題2.3剩余類（系）Residue例2-17設(shè)p為奇素，2.3剩余類（系）Residue例2-18設(shè)ao,a1,…,ap-1和bo,b1,…,bp-1是模p的兩組完全剩余系，p奇素，證aobo,a1b1,…,ap-1bp-1一定不是模p的完全剩余系反證：設(shè)aobo,a1b1,…,ap-1bp-1是模p的完全剩余系不妨設(shè)p|aobo,

p|aibi,

1<=i<=p-1,因此設(shè)p|ao,

p|bo,

p|ai,

p|bi,

1<=i<=p-1,所以a1,…,ap-1和b1,…,bp-1是模p的兩組簡(jiǎn)化剩余系但a1…ap-1≡-1(modp)b1…bp-1≡-1(modp)

與a1b1…ap-1bp-1≡-1(modp)

矛盾2.3剩余類（系）Residue例2-18設(shè)ao,a2.4剩余類（系）的應(yīng)用Hash(散列)函數(shù)就是把任意長(zhǎng)的輸入字符串（預(yù)映射，Pre-image）變換成固定長(zhǎng)（一般更短）的輸出字符串單向：多到一=〉碰撞（collision）必然存在也叫壓縮函數(shù)、縮短函數(shù)、消息摘要、指紋、密碼校驗(yàn)和、信息完整性檢驗(yàn)（DIC）、操作檢驗(yàn)碼（MDC）著名的：MD5，SHA-1MOD可以實(shí)現(xiàn)2.4剩余類（系）的應(yīng)用Hash(散列)函數(shù)2.4剩余類（系）的應(yīng)用Hash函數(shù)是公開的，對(duì)處理過程不用保密安全性是它的單向性：輸出不依賴于輸入預(yù)映射單個(gè)比特的改變，平均而言，將引起hash值中一半的比特改變。已知一個(gè)hash值，要找到預(yù)映射的值，使它的hash值等于已知的hash值在計(jì)算上是不可行的。優(yōu)良hash函數(shù)的條件：已知輸出，求輸入困難:單向性。已知輸入計(jì)算輸出容易的:快速性。已知x，構(gòu)造y使Hash（x）=hash(y)困難:抗碰撞性。輸出的每一比特都與輸入的每一比特有關(guān)，輸入每改變一比特，都將對(duì)輸出產(chǎn)生明顯影響：雪崩性。

2.4剩余類（系）的應(yīng)用Hash函數(shù)是公開的，對(duì)處理過程不2.4剩余類（系）的應(yīng)用應(yīng)用領(lǐng)域密碼學(xué)：特別是數(shù)字簽名密碼保存下載軟件：emule：校驗(yàn)和標(biāo)示微支付：例如基于沖突的micromint和基于hash鏈的支付payword文件系統(tǒng)：物理組織2.4剩余類（系）的應(yīng)用應(yīng)用領(lǐng)域2.4剩余類（系）的應(yīng)用文件系統(tǒng)：物理組織文件的組織形式：邏輯組織：用戶看到的文件組織形式物理組織：邏輯組織到磁盤塊的映射=〉地址映像物理組織：順序、鏈?zhǔn)?、索引、hash結(jié)構(gòu)Hash結(jié)構(gòu)hash(key)=addr(在磁盤或文件中的存放位置)問題：沖突2.4剩余類（系）的應(yīng)用文件系統(tǒng)：物理組織......文件空間空閑標(biāo)志沖突記數(shù)記錄內(nèi)容記錄內(nèi)容空閑標(biāo)志沖突記數(shù)記錄內(nèi)容記錄內(nèi)容Hash(key)=addr起始位置計(jì)算addr=hash(key)對(duì)應(yīng)沖突記數(shù)加1本記錄空閑順取下一個(gè)標(biāo)記為占用填記錄內(nèi)容保存記錄：TF......文件空間空閑標(biāo)志記錄內(nèi)容空閑標(biāo)志記錄內(nèi)容Hash查找記錄：計(jì)算addr=hash(key)取addr對(duì)應(yīng)記錄的沖突記數(shù)

countcount=0無(wú)此記錄本記錄空閑順取下一記錄key相等找到

hash(key)相等count:=count-1count=0無(wú)此記錄順取下一記錄TFFTTFTFTF查找記錄：計(jì)算addr=hash(key)取addr對(duì)應(yīng)記錄刪除記錄：調(diào)用查找過程(key)找到錯(cuò)誤返回置空閑標(biāo)志(找到記錄)沖突記數(shù)-1對(duì)應(yīng)hash(key)特點(diǎn)：按關(guān)鍵字檢索速度非?？?。用途：常用于目錄檢索。注意：文件可循環(huán)使用，滿時(shí)保存失敗。刪除記錄：調(diào)用查找過程(key)找到錯(cuò)誤返回置空閑標(biāo)志特點(diǎn)：2.5歐拉定理與費(fèi)馬小定理2.5歐拉定理與費(fèi)馬小定理2.5歐拉定理與費(fèi)馬小定理2.5歐拉定理與費(fèi)馬小定理2.5歐拉定理與費(fèi)馬小定理需要指出：26

≡1(mod7)，6并不是滿足條件的最小數(shù),23

≡1(mod7)2.5歐拉定理與費(fèi)馬小定理2.5歐拉定理與費(fèi)馬小定理例：115x15+278x3+12(mod7)，x=10原式≡3x15-2x3-2(mod7)

≡3x3-2x3-2(mod7)≡x3-2(mod7)

≡25(mod7)≡4(mod7)2.5歐拉定理與費(fèi)馬小定理例：115x15+278x3+12.5歐拉定理與費(fèi)馬小定理推論:(a,n)=1,ax≡b(modn)解為x≡baφ(n)-1(modn)例:求解7x≡13(mod19)

x≡13*717(mod19)因?yàn)?2≡(-8)(mod19)x≡13*7*224≡-4*36≡-4*7≡10(mod19)2.5歐拉定理與費(fèi)馬小定理推論:(a,n)=1,ax2.5歐拉定理與費(fèi)馬小定理計(jì)算31000000(mod47)1000000(mod46)≡6原式≡36≡-13*9≡-117≡24(mod47)作業(yè)(7)：計(jì)算245678(mod13),p58第19題(1)2.5歐拉定理與費(fèi)馬小定理計(jì)算31000000(mod42.5歐拉定理與費(fèi)馬小定理2.5歐拉定理與費(fèi)馬小定理2.5歐拉定理與費(fèi)馬小定理求證：3n5+5n3+7n≡0(mod15)3n5≡05n3≡2n7n≡n(mod3)3n5≡3n5n3≡07n≡2n(mod5)2.5歐拉定理與費(fèi)馬小定理求證：3n5+5n3+7n≡02.5歐拉定理與費(fèi)馬小定理例：證97104-1能被105整除就是要證97104≡

1（mod105）因?yàn)?97,105)=1105=3*5*7，所以(105)=2*4*6=4897104≡9748*2+8≡978(mod105)978≡1(mod3)，978≡1(mod5)，978≡972≡(-1)2(mod7)所以978≡1(mod105)成立作業(yè)(8):p58第24(4)題2.5歐拉定理與費(fèi)馬小定理例：證97104-1能被105整2.6RSA公鑰密碼機(jī)制麻省理工學(xué)院的Rivest、Shamir和Adleman三人研究小組于1978年提出機(jī)制：(1)選擇兩個(gè)大素?cái)?shù)p和q；(2)計(jì)算n=p×q,則(n)=(p-1)×(q-1)；(3)隨機(jī)選擇一整數(shù)e，0<e<(n),滿足((n)，e)=1；(4)計(jì)算d，滿足de≡1(mod(n))(5)d保密，(d,n)是私鑰；發(fā)布(e,n)是公鑰；銷毀p,q(6)若m表示明文，用c表示密文(m和c均小于n)，則加密：；解密：2.6RSA公鑰密碼機(jī)制麻省理工學(xué)院的Rivest、Sha2.6RSA公鑰密碼機(jī)制實(shí)現(xiàn)中的問題（1）如何計(jì)算abmodn（2）如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？（3）如何找到足夠大的素?cái)?shù)p和q?2.6RSA公鑰密碼機(jī)制實(shí)現(xiàn)中的問題2.6RSA公鑰密碼機(jī)制如何計(jì)算abmodn1）計(jì)算a*a*a*…*a*a*a，需要計(jì)算n-1次乘法，時(shí)間復(fù)雜度O(n)2）考慮實(shí)例a4，計(jì)算b=a*a，再算c=b*b，則c=a4，但是只用了兩次乘法，效率提高。比如a9=a*(a4)*(a4)，只需用4次乘法，一般的，an時(shí)間復(fù)雜度為O(logn)2.6RSA公鑰密碼機(jī)制如何計(jì)算abmodn2.6RSA公鑰密碼機(jī)制第二種算法與二進(jìn)制的關(guān)系9=(1001)2，a9=(((12*a)2)2)2*a10=(1010)2，a10=((((12)*a)2)2*a)2從二進(jìn)制第一位開始，遇到1就先平方乘以a，遇到0就直接平方2.6RSA公鑰密碼機(jī)制第二種算法與二進(jìn)制的關(guān)系2.6RSA公鑰密碼機(jī)制如何計(jì)算abmodnBR算法BinaryRepresentation中國(guó)剩余定理能提高速度，下節(jié)內(nèi)容作業(yè)(9):p58第20題d1forikdownto0d(d*d)modnifbi=1 thend(d*a)modnreturnd2.6RSA公鑰密碼機(jī)制如何計(jì)算abmodnd12.6RSA公鑰密碼機(jī)制公鑰發(fā)布當(dāng)要通信時(shí)向?qū)Ψ剿饕涔€可能假冒，因此仍需要額外的可信保障擴(kuò)散通過可信的朋友之間的輾轉(zhuǎn)交換，如PGP(PrettyGoodPrivacy)公開的目錄服務(wù)目錄的維護(hù)得由信得過的機(jī)構(gòu)執(zhí)行每個(gè)用戶在目錄里有一項(xiàng){身份信息，其公鑰}證書中心CA(CertificateAuthentication)PKI的核心2.6RSA公鑰密碼機(jī)制公鑰發(fā)布2.6RSA公鑰密碼機(jī)制RSA可能受到的攻擊枚舉枚舉所有可能明文m，用e加密和c比較枚舉所有可能的私鑰d數(shù)學(xué)方法分解n=pq，就可以計(jì)算φ(n)，就可從e求得d不分解n，而直接求φ(n)，再求d不求φ(n)，直接求d2.6RSA公鑰密碼機(jī)制RSA可能受到的攻擊2.6RSA公鑰密碼機(jī)制從攻擊對(duì)象：對(duì)RSA的定點(diǎn)攻擊對(duì)RSA的共模攻擊對(duì)RSA的選擇密文攻擊對(duì)RSA的小加密指數(shù)攻擊對(duì)RSA的小解密指數(shù)攻擊時(shí)間性攻擊：取決于解密算法的運(yùn)算時(shí)間2.6RSA公鑰密碼機(jī)制從攻擊對(duì)象：2.6RSA公鑰密碼機(jī)制定點(diǎn)攻擊第三者截獲密文C后，反復(fù)計(jì)算e次冪ce≡

me^2ce^2≡me^3……（modn）一旦ce^t≡c≡me（modn）=〉m≡ce^t-1（modn）

t不是很大時(shí)這種攻擊可行如何避免？如何讓t很大？今后分解

2.6RSA公鑰密碼機(jī)制定點(diǎn)攻擊2.6RSA公鑰密碼機(jī)制選擇密文攻擊利用同態(tài)：Ek(x1x2)=Ek(x1)Ek(x2)例1：m3≡

m1m2(modn),讓A給其中兩個(gè)簽名就能夠得到其對(duì)第3個(gè)的簽名例2：收集到用A公鑰加密的密文C，想要得到明文M他首先選擇隨機(jī)數(shù)r,使r<n.然后用A的公開密鑰e計(jì)算x≡remodn y≡xc

modn讓A對(duì)y簽名，得到u≡ydmodnr-1ydmodn≡r-1xdcdmodn≡cdmodn≡m不要用RSA對(duì)陌生人的隨機(jī)文件簽名，簽名前先使用一個(gè)散列函數(shù)2.6RSA公鑰密碼機(jī)制選擇密文攻擊2.6RSA公鑰密碼機(jī)制共模攻擊如果相同的消息曾用兩個(gè)不同的指數(shù)加密，而這兩個(gè)指數(shù)是互素、加密的用戶共模，則明文可以不用任何一個(gè)解密密鑰來(lái)恢復(fù)。設(shè)用戶的公開密鑰分別為e1,e2,且e1,e2互素，明文消息為m,密文為C1≡me1modnC2

≡me2modn

因?yàn)椋╡1,e2)=1, r*e1+s*e2=1假定r為負(fù)數(shù)則：(C1-1)r*C2s=mmodn所以：不要共模2.6RSA公鑰密碼機(jī)制共模攻擊2.6RSA公鑰密碼機(jī)制總結(jié)加/解密、密鑰交換、數(shù)字簽名使用最廣泛注：實(shí)際使用時(shí)RSA加密的一般不是直接的明文，而是會(huì)話密鑰，然后用對(duì)稱算法加解密公鑰算法加密解密速度慢誤區(qū):

公開密鑰密碼算法更安全公開密鑰密碼使對(duì)稱密鑰密碼過時(shí)了公鑰的分發(fā)是簡(jiǎn)單和一目了然的2.6RSA公鑰密碼機(jī)制總結(jié)2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論2.5同余方程的一般理論法二：直接刪除x4化為：≡3x2+4x+2x3+x+x2+x3+2x2+x≡3x3+x2+x(mod5)2.5同余方程的一般理論問題的提出代數(shù)的主要問題就是解方程隋朝之前有部《孫子算經(jīng)》提出“物不知數(shù)”問題：今有物不知數(shù)，三三數(shù)之有二，五五數(shù)之有三，七七數(shù)之有二，問物有幾何韓信點(diǎn)兵有兵一隊(duì)，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵數(shù)解決：大衍求一術(shù)，鬼谷算天文、歷法的需要問題的提出代數(shù)的主要問題就是解方程中國(guó)剩余定理ChineseRemainderTheorem

Letnbeapositiveintegersuchthatitleavestheremainders2,3,2whenitisdividedby3,5,7respectively.Findn.最簡(jiǎn)單直接的方法：

Sincen=3k+2willleaveremainder2whenitisdividedby3,n=2,5,8,11,14,17,20…….Wefoundthatn=8cansatisfythefirsttwoconditionsbutnotthethirdone.AstheL.C.M.of3,5is15,weaddthenumber8by15eachtimeuntilwegetoursolutions.n=23Anyothersolutions?GeneralSolutions?2.7孫子定理中國(guó)剩余定理ChineseRemainderTheo2.3孫子定理明朝程大位《算數(shù)統(tǒng)籌》：三人同行七十稀，五樹梅花甘一枝，七子團(tuán)圓整半月，除百零五便得知。

2.3孫子定理明朝程大位《算數(shù)統(tǒng)籌》：2.3孫子定理利用算式表示：２

７０＋３

２１＋２

１５＝２３３再把２３３－１０５－１０５＝２３233+105n均是答案

３除余數(shù)５除余數(shù)７除余數(shù)７０１００２１０１０１５００１

３除余數(shù)５除余數(shù)７除余數(shù)７０

２２００２１

３０３０１５

２００２２３３２＋０＋０＝２０＋３＋０＝３２＋０＋０＝２三人同行七十稀五樹梅花甘一枝七子團(tuán)圓整半月除百零五便得知2.3孫子定理利用算式表示：

３除余數(shù)５除余數(shù)７除余數(shù)７０2.3孫子定理把問題一般化如何找70、21、15

３除余數(shù)５除余數(shù)７除余數(shù)７０１００２１０１０１５００１

３除余數(shù)５

７＝３５除余數(shù)35x=3y+1１０2.3孫子定理把問題一般化

３除余數(shù)５除余數(shù)７除余數(shù)７０１2.3孫子定理找出A,B,C分別滿足以下條件而答案則為2.3孫子定理找出A,B,C分別滿足以下條件2.3孫子定理定理2-11孫子定理

設(shè)兩兩互素，k>=2,，則同余方程組解為2.3孫子定理定理2-11孫子定理2.3孫子定理2.3孫子定理2.3孫子定理第1步：最后的模M=5*6*7*11=2310第2步：各方程模變?yōu)镸需要乘以的數(shù)Mi

M1=2310/5=6*7*11=462;M2=2310/6=5*7*11=385M3=2310/7=5*6*11=330;M4=2310/11=5*6*7=210第3步：求出逆元Mi-1考慮Mi*x≡Mibi(modM)x≡Mi-1Mibi

(modM)但上面Mi-1是不存在的，因?yàn)椋∕,Mi）=M/mi，但（mi,Mi）=1Mi*x≡Mibi(modM)=>Mi*x≡Mibi(modmi)=>x≡MibiMi-1(modmi)所以求出：462*3≡1(mod5)變成x≡462*1*3(mod5)同理：x≡385*5*1(mod6);x≡330*4*1(mod7);x≡210*10*1(mod11)2.3孫子定理第1步：最后的模M=5*6*7*11=2312.3孫子定理第4步：求出解考慮x≡462*3(mod5)：此時(shí)的x≡0(mod6)\(mod7)\(mod11)所以，對(duì)于其他方程組，這個(gè)x同余于0，可以直接加其實(shí)x≡MibiMi-1(modmi)其他mj都|Mi因此下面的解滿足各方程x≡462*3+385*5*1+330*4*1+210*10*1(mod2310)≡6731≡2111(mod2310)2.3孫子定理第4步：求出解2.3孫子定理練習(xí)解方程組：7x≡5(mod18);13x≡2(mod15)首先7x≡5(mod18)化為：7x≡5(mod2)和7x≡5(mod9)即：x≡1(mod2)和7x≡5(mod9)13x≡2(mod15)化為:13x≡2(mod5)和13x≡2(mod3)即：3x≡2(mod5)和x≡2(mod3)對(duì)于7x≡5(mod9)可以推出7x≡5(mod3)即x≡2(mod3)所以只有3個(gè)：3x≡2(mod5)，x≡1(mod2)和7x≡5(mod9)解：x≡4*2*2*9+1*1*5*9+2*1*5*2≡209≡29(mod90)作業(yè)：P59第34題系數(shù)都化為1:x≡4(mod5)，x≡1(mod2)和x≡2(mod9)2.3孫子定理練習(xí)解方程組：首先7x≡5(mod18)化2.3孫子定理2.3孫子定理北大ACM網(wǎng)絡(luò)熱身賽青蛙的約會(huì)兩只青蛙在網(wǎng)上相識(shí)了，覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。青蛙們都是很樂觀的，它們覺得只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方的。但是除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個(gè)程序來(lái)判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。

青蛙A和青蛙B，規(guī)定緯度線上東經(jīng)0度處為原點(diǎn)，由東往西為正方向，單位長(zhǎng)度1米，青蛙A的出發(fā)點(diǎn)坐標(biāo)是x，一次能跳m米;青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。一次能跳n米。兩只青蛙跳一次所花費(fèi)的時(shí)間相同。緯度線總長(zhǎng)L米。北大ACM網(wǎng)絡(luò)熱身賽青蛙的約會(huì)福大ACM網(wǎng)絡(luò)熱身賽豬的安家

Andy和Mary養(yǎng)了很多豬。他們想要給豬安家。但是Andy沒有足夠的豬圈，很多豬只能夠在一個(gè)豬圈安家。舉個(gè)例子，假如有16頭豬，Andy建了3個(gè)豬圈，為了保證公平，剩下1頭豬就沒有地方安家了。Mary生氣了，罵Andy沒有腦子，并讓他重新建立豬圈。這回Andy建造了5個(gè)豬圈，但是仍然有1頭豬沒有地方去，然后Andy又建造了7個(gè)豬圈，但是還有2頭沒有地方去。Andy都快瘋了。你對(duì)這個(gè)事情感興趣起來(lái)，你想通過Andy建造豬圈的過程，知道Andy家至少養(yǎng)了多少頭豬。福大ACM網(wǎng)絡(luò)熱身賽豬的安家

2.5加速RSA的實(shí)現(xiàn)速度p=23,q=47,e=3,加密字母A，并解密首先A的ASCII碼為65，n=pq=1081,(n)=1012，d=675加密：c≡653≡51(mod1081)變成“3”解密：m≡51675(mod1081)m≡51675≡(46+5)22*30+15≡515≡5*257≡5*27≡20*32≡-4(mod23)m≡51675≡(47+4)46*14+31≡262≡216≡212≡18(mod47)直接使用孫子定理m≡-4*47*1+18*23*(-2)≡-1016≡65(mod1081)2.5加速RSA的實(shí)現(xiàn)速度p=23,q=47,e=3,加密2.5加速RSA的實(shí)現(xiàn)速度JavaDocumentC#RSAParameters2.5加速RSA的實(shí)現(xiàn)速度JavaDocument第二章-同余-信安數(shù)學(xué)課件2.5加速RSA的實(shí)現(xiàn)速度分析對(duì)N求模，現(xiàn)在變成了對(duì)P和Q求模,余數(shù)的大小是P和Q的剩余系里的數(shù)了。按位數(shù)來(lái)算，現(xiàn)在的乘數(shù)的二進(jìn)制位數(shù)是原來(lái)乘數(shù)的二進(jìn)制位數(shù)的一半根據(jù)理論分析，用了中國(guó)剩余定理后，RSA的速度又提高了約50%2.5加速RSA的實(shí)現(xiàn)速度分析2.5加速RSA的實(shí)現(xiàn)速度可能受到出錯(cuò)攻擊設(shè)備可能出錯(cuò)此時(shí)如果Cp計(jì)算錯(cuò)誤，而Cq計(jì)算正確，則可以分解n若Cp被計(jì)算成Cp’，最終計(jì)算的C變成C’,=M’(modn)則M-M’≡0(modq)M-M’≡0(modp)所以gcd((M-M’),n)=q其中2.5加速RSA的實(shí)現(xiàn)速度可能受到出錯(cuò)攻擊2.6群簽名方案中國(guó)剩余定理最主要的價(jià)值在于將單個(gè)方程式和一個(gè)方程組等價(jià)起來(lái)若干用戶組成一個(gè)群體，使用相關(guān)的簽名方案群中心負(fù)責(zé)為群管理員和群成員分配秘鑰，群管理員則在必要的時(shí)候打開簽名確定簽名者的身份。可用在電子投票、電子拍賣等領(lǐng)域一個(gè)基本的群簽名應(yīng)具有匿名性即同一個(gè)群中的成員不能識(shí)別其他群成員的簽名;不相關(guān)性即決定兩個(gè)不同的簽名是否來(lái)自于同一個(gè)人計(jì)算上是不可行的;不可偽造性即任何多個(gè)群成員不能偽造其他成員的簽名。2.6群簽名方案中國(guó)剩余定理最主要的價(jià)值在于將單個(gè)方程式和2.6群簽名方案簽名機(jī)制秘鑰生成群中心隨機(jī)地生成兩個(gè)大素?cái)?shù)p，q，計(jì)算n=pq，選擇公開hash函數(shù)h(x)選擇，并求d，使隨機(jī)選擇,使選擇素?cái)?shù),且,將()送給用戶做密鑰驗(yàn)證，以確信消息是群中心送來(lái)的群中心將()送給群管理員，其中是群成員的身份。設(shè)系統(tǒng)有k個(gè)成員，群中心利用中國(guó)剩余定理，可求同余方程組：的解C群中心將（n,e,c）作為公鑰，（d,p,q）為群中心的私鑰2.6群簽名方案簽名機(jī)制2.6群簽名方案簽名機(jī)制成員的加入和撤銷在有成員加入或撤銷時(shí)，群中心只需重新求解c的值并公布出去，而不必改變其他群成員的秘鑰。簽名群成員要對(duì)消息m簽名,首先計(jì)算h(m),再計(jì)算則即為的簽名。驗(yàn)證若Alice要對(duì)

的簽名

進(jìn)行驗(yàn)證，Alice利用群公鑰e計(jì)算：，得到，然后驗(yàn)證：是否成立。若成立，簽名合法，否則不接受簽名。群管理員通過對(duì)應(yīng)的IDi確定簽名者的身份。2.6群簽名方案簽名機(jī)制2.6群簽名方案可能遭受的攻擊群中心偽造群成員的簽名

顯然該方案中群中心知道所有的群成員的簽名秘鑰，因此一個(gè)不誠(chéng)實(shí)的群中心可以偽造其他群成員的合法簽名而不被發(fā)現(xiàn)聯(lián)合攻擊假設(shè)群成員聯(lián)合對(duì)方案攻擊，他們分別掌握可知為和為的公因子聯(lián)合人越多成功的可能越大也可以自己通過多次加入群實(shí)現(xiàn)2.6群簽名方案可能遭受的攻擊總結(jié)同余：余數(shù)相同，關(guān)注余數(shù)，離不開除數(shù)一定是模m的意義下同余a≡b(modm)<=>m|a-b<=>a=b+km≡非常類似于==：左右可以同時(shí)加減乘除同一個(gè)數(shù)，但不能除以0≡:同一個(gè)m，左右可以同時(shí)加減乘除同余的數(shù)但不能除以與0同余的數(shù)如14≡28(mod7)不能=>2≡4(mod7)除了以后仍然得為整數(shù)≡:a,b不變，m變m可以變成其一個(gè)因子，等式仍然成立M可分解成n個(gè)不同的素?cái)?shù)：方程與方程組的互化逆元總結(jié)同余：余數(shù)相同，關(guān)注余數(shù)，離不開除數(shù)練習(xí)一般技巧同時(shí)減去同余于0的數(shù)的倍數(shù)，即模m的倍數(shù)將幾個(gè)乘數(shù)湊成1，約去，一般使用逆元例：115x15+278x3+12(mod7)，x=15原式≡(7*16+3)x15+(7*40-2)x3+14-2(mod7)

≡3x15-2x3-2(mod7)X=15≡3*1515-2*153-2(mod7)≡3*115-2*13-2(mod7)

≡-1(mod7)類似：求解123456789(mod7)練習(xí)一般技巧原式≡(7*16+3)x15+(7*40-2)x練習(xí)例：a,b,c,d4個(gè)整數(shù)，求證12|(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)只需證明3|,4|因?yàn)閍,b,c,d有4個(gè)數(shù)，則至少2個(gè)數(shù)模3同余，不妨設(shè)為a,b，則3|a-b對(duì)于模2，若分別2個(gè)數(shù)模2余1和0，不妨設(shè)為a,b和c,d,則2|a-b,2|c-d,則4|(a-b)(c-d)3個(gè)數(shù)模2同余，不妨設(shè)為a,b,c則4|(a-b)(a-c)練習(xí)例：a,b,c,d4個(gè)整數(shù)，求證只需證明3|,4|練習(xí)7*8*9*10*11*12(mod13)≡(-6)*(-5)*(-4)*(-3)*(-2)*(-1)≡6!擴(kuò)推12!(mod13)≡(6!)2練習(xí)7*8*9*10*11*12(mod13)≡(-6)總結(jié)模m的剩余類：同余的歸一類：2類或者完全一樣，或者完全不同完全不同的最多m個(gè)：完全剩余類模m的剩余系每個(gè)剩余類中找出一個(gè)代表元，組成一個(gè)系完全剩余類<->完系，0，1，…,m-1緊縮剩余類<->縮系,(m)縮系最大的價(jià)值：每個(gè)元素都有逆元m為素的價(jià)值：完系-0就是縮系0481215913261014371115總結(jié)模m的剩余類：048121591326101437111總結(jié)關(guān)于縮系與完系的定理模m都可統(tǒng)一到0到m-1之間，簡(jiǎn)化x遍歷縮（完）系，則ax+b也遍歷，其中（a,m）=1結(jié)合右圖擴(kuò)展：a也是縮系中的一員，若b=0，如對(duì)于72*1≡2

2*2≡42*3≡62*4≡12*5≡32*6≡5(mod7)可形成分離的循環(huán)1*2≡2

2*2≡44*2≡1；

2*3≡62*6≡52*5≡30481215913261014371115總結(jié)關(guān)于縮系與完系的定理模m04812159132610總結(jié)技巧不規(guī)則的數(shù)簡(jiǎn)化為0，1，…，m的形式要證完系，分別證有m個(gè)，兩兩不同余要證縮系，先證完系，在證與m互質(zhì)總結(jié)技巧練習(xí)證明：當(dāng)m>2時(shí)，02,12,…,(m-1)2一定不是模m的完全剩余系。m個(gè),所以只需證存在兩個(gè)同余(m-1)2=m2-2m+1≡1(modm)類似：m個(gè)整數(shù)，都不屬于剩余類0(modm)則其中必有2個(gè)數(shù)屬于同一剩余類練習(xí)證明：當(dāng)m>2時(shí)，02,12,…,(m-1)2一定不是模練習(xí)求證：模m簡(jiǎn)化剩余系每個(gè)元素的和模m與0同余若r為模m的簡(jiǎn)化剩余，則m-r也是所以，可以兩兩湊對(duì)求和，每對(duì)和與0同于練習(xí)求證：模m簡(jiǎn)化剩余系每個(gè)元素的和模m與0同余總結(jié)歐拉函數(shù)的計(jì)算公式：更常用兩個(gè)：(m,n)=1時(shí)和總結(jié)歐拉函數(shù)的計(jì)算總結(jié)Wilson定理(p-1)!≡-1(modp)<=>p是素?cái)?shù)判斷素?cái)?shù)的方法之三之一：用不大于sqrt(n)的質(zhì)數(shù)試除（3,i+=2）之二：愛托拉斯散篩法總結(jié)Wilson定理總結(jié)歐拉定理費(fèi)馬小定理技巧：指數(shù)化簡(jiǎn)，指數(shù)中減去歐拉函數(shù)的倍數(shù)模若為合數(shù)，先分離成多個(gè)?；ベ|(zhì)的方程總結(jié)歐拉定理練習(xí)證明：n整數(shù)，a7≡a(mod63)首先63=7*9，所以分解：先證a7≡a(mod7)，直接根據(jù)費(fèi)馬定理再由于(9)=9-3=6，所以若(a,9)=1或9時(shí)，a7≡a(mod9)

若(a,9)=3，a2k≡0(mod9)

所以(a,9)=3時(shí)是不成立注意：歐拉定理與費(fèi)馬小定理的不同之處練習(xí)證明：n整數(shù)，a7≡a(mod63)首先63=7*9總結(jié)應(yīng)用：判斷素?cái)?shù)的方法之四首先計(jì)算2n，若模n是否同余于2注意：此時(shí)的判斷方法與費(fèi)馬小定理的推理正好相反。如果p質(zhì)數(shù)則成立vs.如果成立，則p是質(zhì)數(shù)所以只能排除合數(shù)，并不能肯定素?cái)?shù)偽素?cái)?shù)總結(jié)應(yīng)用：判斷素?cái)?shù)的方法之四總結(jié)應(yīng)用：RSA(1)選擇兩個(gè)大素?cái)?shù)p和q；(2)計(jì)算n=p×q,則(n)=(p-1)×(