公鑰密碼一課件

第6章：公鑰密碼一、公鑰密碼的基本概念二、公鑰密碼RSA三、背包公鑰密碼四、公鑰密碼Rabin第6章：公鑰密碼一、公鑰密碼的基本概念1學(xué)習(xí)要點(diǎn)了解非對(duì)稱(chēng)密碼體制的提出背景、基本思想了解非對(duì)稱(chēng)密碼體制的基本應(yīng)用方向了解三種典型的公鑰密碼體制

DH密鑰交換算法RSAECC學(xué)習(xí)要點(diǎn)2§6－1概述問(wèn)題的提出：

密鑰管理困難傳統(tǒng)密鑰管理兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用戶(hù)需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶(hù)量增大時(shí)密鑰空間急劇增大。如:n=100時(shí)C(100,2)=4,995n=5000時(shí)C(5000,2)=12,497,500陌生人間的保密通信問(wèn)題

數(shù)字簽名的問(wèn)題傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴(lài)的需求§6－1概述問(wèn)題的提出：3公鑰密碼一課件4公鑰密碼的基本概念雙鑰密碼體制(公鑰密碼體制)于1976年由W.Diffie和M.Hellman[1976]提出，同時(shí)R.Merkle[1978]也獨(dú)立提出了這一體制。可用于保密通信，也可用于數(shù)字簽字。這一體制的出現(xiàn)在密碼學(xué)史上是劃時(shí)代的事件，它為解決計(jì)算機(jī)信息網(wǎng)中的安全提供了新的理論和技術(shù)基礎(chǔ)。公鑰體制的基本原理是陷門(mén)單向函數(shù)。公鑰密碼的基本概念雙鑰密碼體制(公鑰密碼體制)于1976年5公鑰密碼一課件6注：1*.僅滿(mǎn)足(1)、(2)兩條的稱(chēng)為單向函數(shù)；第(3)條稱(chēng)為陷門(mén)性，δ稱(chēng)為陷門(mén)信息。

2*.當(dāng)用陷門(mén)函數(shù)f作為加密函數(shù)時(shí)，可將f公開(kāi)，這相當(dāng)于公開(kāi)加密密鑰。此時(shí)加密密鑰便稱(chēng)為公開(kāi)密鑰，記為Pk。f函數(shù)的設(shè)計(jì)者將δ保密，用作解密密鑰，此時(shí)δ稱(chēng)為秘密密鑰，記為Sk。由于加密函數(shù)是公開(kāi)的，任何人都可以將信息x加密成y=f(x)，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全信道傳送）；由于設(shè)計(jì)者擁有Sk，他自然可以解出x=f-1(y)。

3*.單向陷門(mén)函數(shù)的第(2)條性質(zhì)表明竊聽(tīng)者由截獲的密文y=f(x)推測(cè)x是不可行的。是滿(mǎn)足下列條件的函數(shù)f：(1)給定x，計(jì)算y=f(x)是容易的(2)給定y,計(jì)算x使y=f(x)是困難的(3)存在δ，已知δ時(shí),對(duì)給定的任何y，若相應(yīng)的x存在，則計(jì)算x使y=f(x)是容易的陷門(mén)單向函數(shù)注：1*.僅滿(mǎn)足(1)、(2)兩條的稱(chēng)為單向函數(shù)；第(3)7公鑰密碼一課件8對(duì)公鑰密碼體制的要求（1）參與方B容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰（公開(kāi)密鑰KUb和私有密鑰KRb）。（2）在知道公開(kāi)密鑰和待加密報(bào)文M的情況下，對(duì)于發(fā)送方A，很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)的密文：C＝EKUb（M）（3）接收方B使用私有密鑰容易通過(guò)計(jì)算解密所得的密文以便恢復(fù)原來(lái)的報(bào)文：M＝DKRb（C）＝DKRb（EKUb（M））（4）敵對(duì)方即使知道公開(kāi)密鑰KUb，要確定私有密鑰KRb在計(jì)算上是不可行的。（5）敵對(duì)方即使知道公開(kāi)密鑰KUb和密文C，要想恢復(fù)原來(lái)的報(bào)文M在計(jì)算上也是不可行的。（6）加密和解密函數(shù)可以以?xún)蓚€(gè)次序中的任何一個(gè)來(lái)使用:

M＝DKRb（EKUb（M））M=EKUb(DKRb(M))對(duì)公鑰密碼體制的要求（1）參與方B容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰（9單向函數(shù)舉例離散對(duì)數(shù)DL。給定一大素?cái)?shù)p（比如，p在21024數(shù)量級(jí)），p－1含另一大素?cái)?shù)因子。稱(chēng)log2p為素?cái)?shù)p的長(zhǎng)度。{1,

2,…,p-1}關(guān)于modp乘法構(gòu)成了一乘群Zp*，它是一個(gè)p－1階循環(huán)群。該循環(huán)群的生成元一共有φ(p-1)個(gè)。設(shè)一個(gè)生成元為整數(shù)g，1<g<p－1。設(shè)一個(gè)整數(shù)x，1<x<p－1。設(shè)y滿(mǎn)足y=gxmodp。單向函數(shù)舉例離散對(duì)數(shù)DL。給定一大素?cái)?shù)p（比如，p在21010單向函數(shù)舉例已知x，g，p，求y=gxmodp容易。這是因?yàn)椋捎谜郯胂喑?，只需要不超過(guò)2log2p次的modp乘法運(yùn)算。（實(shí)際上只需要不超過(guò)2log2x次的modp乘法運(yùn)算。如x=15=11112，g15modp=(((g)2g)2g)2gmodp，要用6次modp乘法）單向函數(shù)舉例已知x，g，p，求y=gxmodp容易。11單向函數(shù)舉例若已知y，g，p，求x滿(mǎn)足y=gxmodp，稱(chēng)為求解離散對(duì)數(shù)問(wèn)題。記為x=loggymodp。求解離散對(duì)數(shù)問(wèn)題的“最笨的方法”當(dāng)然就是窮舉，對(duì)每一個(gè)x∈{0,1,2,…,p－1}檢驗(yàn)是否y=gxmodp。窮舉求解法的運(yùn)算次數(shù)約為(p－1)/2。許多求解離散對(duì)數(shù)問(wèn)題的算法比窮舉快得多，比如Shanks算法，Pohlig-Hellman算法等。最快求解法的運(yùn)算次數(shù)約為數(shù)量級(jí)單向函數(shù)舉例若已知y，g，p，求x滿(mǎn)足y=gxmodp，稱(chēng)為12單向函數(shù)舉例這個(gè)計(jì)算量稱(chēng)為亞指數(shù)計(jì)算量。這是什么概念呢？我們知道p的長(zhǎng)度是log2p。看以下的不等式。當(dāng)log2p≈1024時(shí)，亞指數(shù)計(jì)算量不小于2100數(shù)量級(jí)。至少在在當(dāng)前的計(jì)算水平之下是不能實(shí)現(xiàn)的。單向函數(shù)舉例這個(gè)計(jì)算量稱(chēng)為亞指數(shù)計(jì)算量。這是什么概念呢？我們13單向函數(shù)舉例大整數(shù)分解FAC。設(shè)有二大素?cái)?shù)p和q。設(shè)n=pq。若已知p和q，求n=pq只需一次乘法。但若已知n，求p和q滿(mǎn)足n=pq，則稱(chēng)為大整數(shù)分解問(wèn)題。迄今為止，已知的各種算法的漸近運(yùn)行時(shí)間約為：試除法：n/2。二次篩(QS)：橢圓曲線(EC)：數(shù)域篩(NFS)：?jiǎn)蜗蚝瘮?shù)舉例大整數(shù)分解FAC。設(shè)有二大素?cái)?shù)p和q。設(shè)n=pq14單向函數(shù)舉例背包問(wèn)題。已知向量A=(a1,a2,…,aN)，ai為正整數(shù)，稱(chēng)其為背包向量，稱(chēng)每個(gè)ai為物品重量。給定向量x=(x1,x2,…,xN)，xi{0,1}，求和式（稱(chēng)為背包重量）S=a1x1+a2x2+…+aNxN容易，只需要不超過(guò)N－1次加法。但已知A和S，求x則非常困難，稱(chēng)其為背包問(wèn)題，又稱(chēng)作子集和(Subset-Sum)問(wèn)題。一般只能用窮舉搜索法，有2N種可能。N大時(shí)，相當(dāng)困難。單向函數(shù)舉例背包問(wèn)題。已知向量15單向函數(shù)舉例背包問(wèn)題的特例：超遞增背包問(wèn)題。將物品重量從小到大排列：a1，a2，a3，…，aN。稱(chēng)該背包問(wèn)題為超遞增背包問(wèn)題，如果：a1<a2；a1+a2<a3；a1+a2+a3<a4；…a1+a2+a3+…+aN-1<aN。（超遞增背包問(wèn)題是容易解決的。）單向函數(shù)舉例背包問(wèn)題的特例：超遞增背包問(wèn)題。將物品重量從小到16（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。執(zhí)行概率素?cái)?shù)判定測(cè)試,如果n未測(cè)試通過(guò),則拒絕數(shù)值n,轉(zhuǎn)向步驟1Alice用Bob的公鑰n，計(jì)算：（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。格的維數(shù)總是不超過(guò)N。務(wù)必要先簽名后加密!x=15=11112，(3)K為有限密鑰空間，是一些可能密鑰的有限集合；Ua2>Ua1>M>Ua2(modM)=b2，了解三種典型的公鑰密碼體制C=18191223(mod2867)那么，4個(gè)不同的根怎樣計(jì)算呢？如果僅僅知道n，而不知道分解式n=pq，則無(wú)法計(jì)算mp和mq，因而無(wú)法計(jì)算這4個(gè)不同的根。第(3)條稱(chēng)為陷門(mén)性，δ稱(chēng)為陷門(mén)信息。隨機(jī)選一個(gè)奇數(shù)n(偽隨機(jī)數(shù)發(fā)生器)四、公鑰密碼Rabin（因?yàn)閑d是(p-1)(q-1)的倍數(shù)加1，所以med(modn)=m。（2）c=c1/c2(modn)，則c所對(duì)應(yīng)的明文一定是m=m1/m2(modn)；如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？分析者沒(méi)有辦法在有效時(shí)間內(nèi)將n分解出來(lái)?；綬SA的加密過(guò)程：Alice欲發(fā)送明文m給Bob，其中0<m<n。單向函數(shù)舉例定理設(shè)超遞增背包重量為S。如果k滿(mǎn)足ak<S<ak+1，則ak是背包中的最大物品重量。定理的證明

首先，背包中沒(méi)有大于ak的物品重量。其次，背包中確有等于ak的物品重量。證明完畢。注意到，尋找k滿(mǎn)足ak<S<ak+1只需要對(duì)比N次。（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。單向函數(shù)舉例定理17單向函數(shù)舉例超遞增背包問(wèn)題的解決方法解決方法是可行的。設(shè)背包重量S，步驟如下。（1）窮舉：找k滿(mǎn)足ak<S<ak+1。（這說(shuō)明背包中的最大物品重量是ak）（2）記憶：存儲(chǔ)這個(gè)k。（3）卸載：如果S>0，則令S:=S-ak，返回（1）。如果w=0，則到（4）。（4）輸出前面存儲(chǔ)的所有的k，停止。單向函數(shù)舉例超遞增背包問(wèn)題的解決方法18單向函數(shù)舉例格的最小向量問(wèn)題(SVP)。若干個(gè)N維向量組成的集合，如果滿(mǎn)足“集合中任何若干個(gè)向量的整數(shù)線性組合仍是集合中的一個(gè)向量?！眲t該結(jié)合稱(chēng)為一個(gè)格。關(guān)于格有以下的性質(zhì)和概念。如果格中存在這樣的幾個(gè)向量，滿(mǎn)足①它們（實(shí)數(shù)）線性無(wú)關(guān)；②格中的任何其它向量都能唯一地表示為這幾個(gè)向量的整數(shù)線性組合。則這幾個(gè)向量構(gòu)成的向量組稱(chēng)為基?；械南蛄康膫€(gè)數(shù)稱(chēng)為格的維數(shù)。格的維數(shù)總是不超過(guò)N。單向函數(shù)舉例格的最小向量問(wèn)題(SVP)。19單向函數(shù)舉例給定一個(gè)格的一組基。尋找格中的“尺寸最小”的向量（即模最小的向量），稱(chēng)為格的最小向量問(wèn)題（shortestvectorproblem；SVP）。又稱(chēng)為格歸約。實(shí)際上，格歸約的傳統(tǒng)算法為L(zhǎng)LL算法，以后又有各種改進(jìn)的算法。當(dāng)格的維數(shù)比較大時(shí)（比如，維數(shù)大于200），當(dāng)前的所有格歸約算法都不是有效算法。單向函數(shù)舉例給定一個(gè)格的一組基。尋找格中的“尺寸最小”的向量20公開(kāi)密鑰密碼系統(tǒng)的分析方法強(qiáng)行攻擊(對(duì)密鑰)。公開(kāi)密鑰算法本身可能被攻破?？赡軋?bào)文攻擊(對(duì)報(bào)文本身的強(qiáng)行攻擊)。公開(kāi)密鑰密碼系統(tǒng)的分析方法強(qiáng)行攻擊(對(duì)密鑰)。21公鑰密碼系統(tǒng)的應(yīng)用類(lèi)型加密/解密數(shù)字簽名會(huì)話(huà)密鑰交換公鑰密碼系統(tǒng)的應(yīng)用類(lèi)型加密/解密22例子：簡(jiǎn)單數(shù)字簽名例子：簡(jiǎn)單數(shù)字簽名23例子續(xù)：安全數(shù)字簽名例子續(xù)：安全數(shù)字簽名24公鑰密碼一課件25公鑰密碼一課件26容易，只需要不超過(guò)N－1次加法。隨機(jī)選擇a<n,計(jì)算s次，n=5000時(shí)C(5000,2)=12,497,500陌生人間的保密通信問(wèn)題d(d×a)modn找到一個(gè)e滿(mǎn)足e×d＝1(modz)。TRUE:n一定不是素?cái)?shù)n=5000時(shí)C(5000,2)=12,497,500基本RSA的這個(gè)安全性漏洞稱(chēng)為可傳遞性。如果每次都返回FALSE，doc2×c(2)給定y,計(jì)算x使y=f(x)是困難的單向陷門(mén)函數(shù)的第(2)條性質(zhì)表明竊聽(tīng)者由截獲的密文y=f(x)推測(cè)x是不可行的。格歸約的傳統(tǒng)算法為L(zhǎng)LL算法，以后又有各種改進(jìn)的算法。在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。(3)K為有限密鑰空間，是一些可能密鑰的有限集合；格的維數(shù)總是不超過(guò)N。m(2,1)(modp)=p-mp；格歸約的傳統(tǒng)算法為L(zhǎng)LL算法，以后又有各種改進(jìn)的算法。執(zhí)行概率素?cái)?shù)判定測(cè)試,如果n未測(cè)試通過(guò),則拒絕數(shù)值n,轉(zhuǎn)向步驟1二、公鑰密碼RSA公鑰密碼RSA1977年由美國(guó)麻省理工學(xué)院的三位教授

RonaldRivestAdiShamirLeonardAdleman聯(lián)合發(fā)明容易，只需要不超過(guò)N－1次加法。二、公鑰密碼RSA公鑰密碼R27二、公鑰密碼RSARSA的密鑰生成選擇兩個(gè)大的素?cái)?shù)p和q。選擇兩個(gè)正整數(shù)e和d，滿(mǎn)足：ed是(p-1)(q-1)的倍數(shù)加1。計(jì)算n=pq。Bob的公鑰是（n，e），對(duì)外公布。Bob的私鑰是d，自己私藏。至于（p，q

），可以是Bob的另一部分私鑰，也可以是對(duì)所有人（包括Bob）都保密的。二、公鑰密碼RSARSA的密鑰生成28二、公鑰密碼RSA基本RSA的加密過(guò)程：Alice欲發(fā)送明文m給Bob，其中0<m<n

。Alice用Bob的公鑰（n，e），計(jì)算密文c為c=me(modn)。基本RSA的解密過(guò)程：Bob收到密文c后，用自己的公鑰（n，e）和私鑰d，計(jì)算cd(modn)=med(modn)=m。（因?yàn)閑d是(p-1)(q-1)的倍數(shù)加1，所以med(modn)=m。這是數(shù)論中的一個(gè)基本結(jié)論）二、公鑰密碼RSA基本RSA的加密過(guò)程：Alice欲發(fā)送明文29二、公鑰密碼RSA基本RSA的安全性攻擊者Eve已經(jīng)知道了Bob的公鑰是（n，e）。如果Eve還知道（p，q），則他容易知道Bob的私鑰d。此時(shí)Eve只需要用推廣的輾轉(zhuǎn)相除法尋找d，滿(mǎn)足ed=1(mod(p-1)(q-1))。由n的值求解（p，q）的值，即求解n的大整數(shù)分解n=pq，是一個(gè)公認(rèn)的數(shù)學(xué)難題（雖然至今并沒(méi)有證明），暫時(shí)還沒(méi)有有效的算法。二、公鑰密碼RSA基本RSA的安全性30二、公鑰密碼RSA目前普遍使用的參數(shù)范圍是2511<p<2512，2511<q<2512。如果Eve欲窮舉p的所有可能值，則窮舉的次數(shù)約為(2512-2511)/2=2510（次）。（因此，基本RSA似乎是足夠安全的）二、公鑰密碼RSA目前普遍使用的參數(shù)范圍是31二、公鑰密碼RSA基本RSA的一個(gè)安全性漏洞設(shè)攻擊者Eve獲得了兩組明文/密文對(duì)(m1，c1)，(m2，c2)。如果Bob新截獲了一個(gè)密文c，并發(fā)現(xiàn)：（1）c=c1c2(modn)，則c所對(duì)應(yīng)的明文一定是m=m1m2(modn)；（2）c=c1/c2(modn)，則c所對(duì)應(yīng)的明文一定是m=m1/m2(modn)；（3）c=c2/c1(modn)，則c所對(duì)應(yīng)的明文一定是m=m2/m1(modn)。（模除運(yùn)算·/·

(modn)是一個(gè)數(shù)論運(yùn)算）二、公鑰密碼RSA基本RSA的一個(gè)安全性漏洞32二、公鑰密碼RSA基本RSA的這個(gè)安全性漏洞稱(chēng)為可傳遞性。這個(gè)漏洞使得攻擊者Eve對(duì)某些新的密文能夠輕而易舉地找到其對(duì)應(yīng)明文。這個(gè)漏洞還有更深刻的隱患，比如在消息認(rèn)證過(guò)程中容易產(chǎn)生偽造。（將在后面介紹）為了克服基本RSA的這個(gè)安全性漏洞，人們將基本RSA進(jìn)行改造，引入Hash函數(shù)。（將在后面介紹）二、公鑰密碼RSA基本RSA的這個(gè)安全性漏洞稱(chēng)為可傳遞性。33要求：若使RSA安全，p與q必為足夠大的素?cái)?shù)，使分析者沒(méi)有辦法在有效時(shí)間內(nèi)將n分解出來(lái)。建議選擇p和q大約是100位的十進(jìn)制素?cái)?shù)。模n的長(zhǎng)度要求至少是512比特。為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)RSA模n的素因子p和q還有如下要求：(1)|p-q|很大，通常p和q的長(zhǎng)度相同；(2)p-1和q-1分別含有大素因子p1和q1(3)gcd(p1-1,q1-1)應(yīng)該很小。為了提高加密速度，通常取e為特定的小整數(shù)，如EDI國(guó)際標(biāo)準(zhǔn)中規(guī)定e＝216＋1，ISO/IEC9796中甚至允許取e＝3。這時(shí)加密速度一般比解密速度快10倍以上。要求：若使RSA安全，p與q必為足夠大的素?cái)?shù)，使34RSA密鑰的生成RSA密鑰的生成35公鑰密碼一課件36=[a(2i)modn]n=5000時(shí)C(5000,2)=12,497,500這是因?yàn)?，采用折半相乘，只需要不超過(guò)2log2p次的modp乘法運(yùn)算。(2)給定y,計(jì)算x使y=f(x)是困難的Bob的公鑰是（n，e），對(duì)外公布。Ua1>M>Ua1(modM)=b1，設(shè)y滿(mǎn)足y=gxmodp。定理設(shè)超遞增背包重量為S。當(dāng)log2p≈1024時(shí)，亞指數(shù)計(jì)算量不小于2100數(shù)量級(jí)。在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。務(wù)必要先簽名后加密!如果n已通過(guò)足夠的測(cè)試,則接受n,否則轉(zhuǎn)向步驟2;WITNESS(a,n)判定n是否為素?cái)?shù)，a是某個(gè)小于n的整數(shù)m(2,2)(modq)=q-mq。至于（p，q），可以是Bob的另一部分私鑰，也可以是對(duì)所有人（包括Bob）都保密的。例：明文=“RSAALGORITHM”一個(gè)根的(modp)、(modq)值是p-mp、q-mq。m的二進(jìn)制表示為bkbk-1…b0,則=18191024·1819128·181964·18194·18192·18191(mod2867)傳統(tǒng)密鑰管理兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用戶(hù)需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶(hù)量增大時(shí)密鑰空間急劇增大。例：p=47,q=61,(n)=(47-1)(61-1)=2760時(shí)，SK=167是否為秘密密鑰的候選者？

用歐氏算法計(jì)算：gcd(2760,167)=1即可證明。QX1X2X3Y1Y2Y3－1027600116716011671－168811－1688－117791－117792－33982－339－1728171－17281719－3142319－3142－7412231=[a(2i)modn]例：p=47,q=637用RSA算法加密與解密的過(guò)程：例：明文=“RSAALGORITHM”(1)明文用數(shù)字表示空白=00，A=01,B=02,…,Z=26(兩位十進(jìn)制數(shù)表示)

1819010001120715180920081300(2)利用加密變換公式C=mPKmodr,即C=18191223mod2867=2756 PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223(mod2867) =18191024·1819128·181964·18194·18192·18191(mod2867) =27562756200105420669234704081815用RSA算法加密與解密的過(guò)程：2756200105438選擇兩個(gè)大素?cái)?shù)p和q，通常要求每個(gè)均大于10100。計(jì)算n＝pｘq和z＝(p－1)(q－1)。選擇一與z互素的數(shù)、令其為d。找到一個(gè)e滿(mǎn)足e×d＝1(modz)。選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文P長(zhǎng)度m滿(mǎn)足0<m<n。加密P時(shí)，計(jì)算C＝Pe(modn)，解密C時(shí)計(jì)算P＝Cd(modn)。由于模運(yùn)算的對(duì)稱(chēng)性，可以證明，在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。為實(shí)現(xiàn)加密，需要公開(kāi)(e,n)，為實(shí)現(xiàn)解密需要(d,n)。RSA算法歸納選擇兩個(gè)大素?cái)?shù)p和q，通常要求每個(gè)均大于10100。RSA算39如何計(jì)算abmodn？如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？如何找到足夠大的素?cái)?shù)p和q?問(wèn)題……如何計(jì)算abmodn？問(wèn)題……40要點(diǎn)1：(axb)modn=[(amodn)x(bmodn)]modn]

要點(diǎn)2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的問(wèn)題：am m的二進(jìn)制表示為bkbk-1…b0,

則計(jì)算ammodnammodn=[

a(2i)]modn =[a(2i)modn]bi0bi0如何計(jì)算abmodn？要點(diǎn)1：(axb)modn=[(amod41快速取模指數(shù)算法計(jì)算abmodn

c0;d1forikdownto0doc2×cd(d×d)modnifbi=1thencc+1d(d×a)modnreturnd快速取模指數(shù)算法計(jì)算abmodnc0;d42快速取模指數(shù)算法：例子i9876543210bi1000110000c=01248173570140280560d=17491575261602412981666717560mod561=1快速取模指數(shù)算法：例子i9876543210bi10001143MillerandRabin,WITNESS算法

WITNESS(a,n)判定n是否為素?cái)?shù)，a是某個(gè)小于n的整數(shù)1.令bkbk-1…b0

為(n-1)的二進(jìn)制表示，2.d13.forikdownto04. doxd5. d(dd)modn6. ifd=1andx1andxn-17. thenreturnTRUE8. ifbi=19. thend(da)modn10.ifd111.thenreturnTRUE12.returnFALSE

返回值：TRUE:n一定不是素?cái)?shù)FALSE:n可能是素?cái)?shù)應(yīng)用：隨機(jī)選擇a<n,計(jì)算s次，如果每次都返回FALSE，則這時(shí)n是素?cái)?shù)的概率為

(1-1/2s)如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？MillerandRabin,WITNESS算法1.441.隨機(jī)選一個(gè)奇數(shù)n(偽隨機(jī)數(shù)發(fā)生器)2.隨機(jī)選擇一個(gè)整數(shù)a<n3.執(zhí)行概率素?cái)?shù)判定測(cè)試,如果n未測(cè)試通過(guò),則拒絕數(shù)值n,轉(zhuǎn)向步驟14.如果n已通過(guò)足夠的測(cè)試,則接受n,否則轉(zhuǎn)向步驟2;說(shuō)明：①隨機(jī)選取大約用

ln(N)/2的次數(shù)，如ln(2200)/2=70②好在生成密鑰對(duì)時(shí)才用到，慢一點(diǎn)還可忍受。

③確定素?cái)?shù)p和q以后，只需選取e,滿(mǎn)足gcd(e,(n))=1,計(jì)算d=e-1mod(n)（擴(kuò)展的歐拉算法）如何找到足夠大的素?cái)?shù)p和q?如何找到足夠大的素?cái)?shù)p和q?45p和q在長(zhǎng)度上應(yīng)僅差幾個(gè)數(shù)位，即p和q應(yīng)是1075

到10100（p-1）和（q-1）都應(yīng)包含一個(gè)較大的素?cái)?shù)因子gcd(p-1,q-1)應(yīng)比較小如果e<n且d<n1/4,則d可以很容易確定建議－p和q在長(zhǎng)度上應(yīng)僅差幾個(gè)數(shù)位，即p和q應(yīng)是1075到10146（3）c=c2/c1(modn)，則c所對(duì)應(yīng)的明文一定是m=m2/m1(modn)。如果n已通過(guò)足夠的測(cè)試,則接受n,否則轉(zhuǎn)向步驟2;f函數(shù)的設(shè)計(jì)者將δ保密，用作解密密鑰，此時(shí)δ稱(chēng)為秘密密鑰，記為Sk。至少在在當(dāng)前的計(jì)算水平之下是不能實(shí)現(xiàn)的。至于（p，q），可以是Bob的另一部分私鑰，也可以是對(duì)所有人（包括Bob）都保密的。這個(gè)漏洞還有更深刻的隱患，比如在消息認(rèn)證過(guò)程中容易產(chǎn)生偽造。p,q,d為保密的（私鑰）d(d×a)modn（3）c=c2/c1(modn)，則c所對(duì)應(yīng)的明文一定是m=m2/m1(modn)。③確定素?cái)?shù)p和q以后，只需選取e,滿(mǎn)足gcd(e,(n))=1,計(jì)算d=e-1mod(n)（擴(kuò)展的歐拉算法）找到一個(gè)e滿(mǎn)足e×d＝1(modz)。例：p=47,q=61,(n)=(47-1)(61-1)=2760時(shí)，SK=167是否為秘密密鑰的候選者？

用歐氏算法計(jì)算：gcd(2760,167)=1即可證明。由于加密函數(shù)是公開(kāi)的，任何人都可以將信息x加密成y=f(x)，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全信道傳送）；使用公鑰{b1，b2，b3，…，bn}計(jì)算密文c：c=m1b1+m2b2+m3b3+…+mnbn。0<m(2,1)<n；分析者沒(méi)有辦法在有效時(shí)間內(nèi)將n分解出來(lái)。(2)給定y,計(jì)算x使y=f(x)是困難的a1+a2+a3+…+aN-1<aN。計(jì)算n＝pｘq和z＝(p－1)(q－1)。四、公鑰密碼Rabin數(shù)字簽名方案：一個(gè)簽名方案是由簽署算法與驗(yàn)證算法兩部分構(gòu)成?？捎晌逶P(guān)系組（M,A,K,S,V）來(lái)描述：(1)M是由一切可能消息所構(gòu)成的有限集合；(2)A是一切可能的簽名的有限集合；(3)K為有限密鑰空間，是一些可能密鑰的有限集合；(4)任意k∈K，有簽署算法Sigk∈S且有對(duì)應(yīng)的驗(yàn)證算法Verk∈V,對(duì)每一個(gè)Sigk和Verk滿(mǎn)足條件：任意一個(gè)簽名：Ver(x,y)=｛

RSA的數(shù)字簽名應(yīng)用真若y=sig(x)假若ySig(x)（3）c=c2/c1(modn)，則c所對(duì)應(yīng)的明文一定是47選取整數(shù)n=pq,

M=A=Zn定義密鑰集合K={(n,e,p,q,d)}|n=pq,d*e1(mod(n))}n和e為公鑰；p,q,d為保密的（私鑰）對(duì)x∈M,Bob要對(duì)x簽名，取k∈K：Sigk(x)xd(modn)y(modn)

Verk(x,y)=真xye(modn)RSA的數(shù)字簽名方案選取整數(shù)n=pq,M=A=ZnRSA的數(shù)字簽名方案48假設(shè)Alice想把簽了名的消息加密送給Bob：對(duì)明文x，Alice計(jì)算對(duì)x的簽名y=SigAlice(x)，然后用Bob的公鑰加密函數(shù)eBob,算出z=eBob(x,y),Alice將z傳給BobBob收到z后，先解密：dBob(z)=dBobeBob(x,y)=(x,y)后檢驗(yàn)：

VerAlice(x,y)=真？問(wèn)題：若Alice首先對(duì)消息x進(jìn)行加密,z=eBob(x),然后再簽名，y=SigAlice(eBob(x)),結(jié)果如何呢？Alice將（z,y)傳給Bob，Bob先將z解密，獲取x;然后用VerAlice檢驗(yàn)關(guān)于x的加密簽名y一個(gè)潛在問(wèn)題：如果Oscar獲得了這對(duì)（z,y)，他能用自己的簽名來(lái)替代Alice的簽名

y=SigOscar(eBob(x))簽名消息的加密傳遞問(wèn)題務(wù)必要先簽名后加密!

假設(shè)Alice想把簽了名的消息加密送給Bob：對(duì)明文x，Al49公鑰密碼一課件50公鑰密碼一課件51公鑰密碼一課件52公鑰密碼一課件53DES和RSA性能比較（同等強(qiáng)度）DES和RSA性能比較（同等強(qiáng)度）54三、背包公鑰密碼背包公鑰密碼早已經(jīng)被攻破，然而背包公鑰密碼的設(shè)計(jì)思想是公認(rèn)的人類(lèi)設(shè)計(jì)思想精華，其設(shè)計(jì)和攻擊已成為公鑰密碼攻防的一個(gè)樣板。三、背包公鑰密碼背包公鑰密碼早已經(jīng)被攻破，然而背包公鑰密碼的55三、背包公鑰密碼背包公鑰密碼的密鑰生成取n個(gè)具有超遞增性的物品重量：a1，a2，a3，…，an。取正整數(shù)M，U，滿(mǎn)足M>a1+a2+a3+…+an；M>U；Ua1>M；M與U互素，因此可以用輾轉(zhuǎn)相除法計(jì)算出U關(guān)于(modM)的逆元U-1。三、背包公鑰密碼背包公鑰密碼的密鑰生成56計(jì)算n＝pｘq和z＝(p－1)(q－1)。C=18191223(mod2867)7560mod561=1C=18191223(mod2867)選擇兩個(gè)大的素?cái)?shù)p和q，要求p和q都是4的倍數(shù)加3。由n的值求解（p，q）的值，即求解n的大整數(shù)分解n=pq，是一個(gè)公認(rèn)的數(shù)學(xué)難題（雖然至今并沒(méi)有證明），暫時(shí)還沒(méi)有有效的算法。定義密鑰集合K={(n,e,p,q,d)}|n=pq,d*e1(mod(n))}一個(gè)根的(modp)、(modq)值是p-mp、q-mq。了解非對(duì)稱(chēng)密碼體制的基本應(yīng)用方向數(shù)字簽名方案：一個(gè)簽名方案是由簽署算法與驗(yàn)證算法兩部分構(gòu)成。a1+a2+a3+…+aN-1<aN。當(dāng)格的維數(shù)比較大時(shí)（比如，維數(shù)大于200），當(dāng)前的所有格歸約算法都不是有效算法。如果每次都返回FALSE，最快求解法的運(yùn)算次數(shù)約為數(shù)量級(jí)計(jì)算n＝pｘq和z＝(p－1)(q－1)。=U-1(m1b1+m2b2+m3b3+…+mnbn)(modM)（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。傳統(tǒng)密鑰管理兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用戶(hù)需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶(hù)量增大時(shí)密鑰空間急劇增大。其次，背包中確有等于ak的物品重量。這個(gè)漏洞還有更深刻的隱患，比如在消息認(rèn)證過(guò)程中容易產(chǎn)生偽造。三、背包公鑰密碼計(jì)算：b1=Ua1(modM)，b2=Ua2(modM)

，b3=Ua3(modM)

，…，bn=Uan(modM)

。（此時(shí)a1=U-1b1(modM)，a2=U-1b2(modM)，a3=U-1b3(modM)，…，an=U-1bn(modM)

。）計(jì)算n＝pｘq和z＝(p－1)(q－1)。三、背包公鑰密碼計(jì)57三、背包公鑰密碼b1，b2，b3，…，bn是n個(gè)物品重量。因?yàn)閁a1>M>Ua1(modM)=b1，Ua2>Ua1>M>Ua2(modM)=b2，Ua3>Ua1>M>Ua3(modM)=b3，…，Uan>Ua1>M>Uan(modM)=bn，所以通常b1，b2，b3，…，bn不具有超遞增性。{b1，b2，b3，…，bn}是公鑰。{a1，a2，a3，…，an}

，M，U都是私鑰。三、背包公鑰密碼b1，b2，b3，…，bn是n個(gè)物品重量。因58三、背包公鑰密碼背包公鑰密碼的加密設(shè)明文m=(m1,m2,m3,…,mn)是長(zhǎng)度為n的比特串。使用公鑰{b1，b2，b3，…，bn}計(jì)算密文c

：c=m1b1+m2b2+m3b3+…+mnbn。密文c是一個(gè)正整數(shù)。（密文c是背包重量，由n個(gè)物品重量b1，b2，b3，…，bn中的某些物品重量相加而成。若截獲了密文c，又知道n個(gè)物品重量b1，b2，b3，…，bn，求解明文m就是背包問(wèn)題。）三、背包公鑰密碼背包公鑰密碼的加密59三、背包公鑰密碼背包公鑰密碼的解密使用私鑰{a1，a2，a3，…，an}

，M，U，計(jì)算變換課文C：C=U-1c(modM)=U-1(m1b1+m2b2+m3b3+…+mnbn

)(modM)=m1a1+m2a2+m3a3+…+mnan(modM)=m1a1+m2a2+m3a3+…+mnan。根據(jù)定理中的方法，容易解出明文m。三、背包公鑰密碼背包公鑰密碼的解密60三、背包公鑰密碼變換課文C是背包重量，由n個(gè)物品重量a1，a2，a3，…，an中的某些物品重量相加而成。若已知變換課文C，又知道n個(gè)物品重量a1，a2，a3，…，an，求解明文m就是超遞增背包問(wèn)題。三、背包公鑰密碼變換課文C是背包重量，由n個(gè)物品重量a1，a61四、公鑰密碼RabinRabin的密鑰生成選擇兩個(gè)大的素?cái)?shù)p和q，要求p和q都是4的倍數(shù)加3。計(jì)算n=pq。Bob的公鑰是n，對(duì)外公布。Bob的私鑰是（p，q），自己私藏。四、公鑰密碼RabinRabin的密鑰生成62四、公鑰密碼RabinRabin的加密過(guò)程Alice欲發(fā)送明文m給Bob，其中0<m<n

。Alice用Bob的公鑰n，計(jì)算：c=m2(modn)。c為密文。四、公鑰密碼RabinRabin的加密過(guò)程63四、公鑰密碼RabinRabin的解密過(guò)程Bob收到密文c后，用自己的私鑰（p，q）計(jì)算四、公鑰密碼RabinRabin的解密過(guò)程64四、公鑰密碼Rabin計(jì)算4個(gè)數(shù)m(1,1)，m(1,2)，m(2,1)，m(2,2)，滿(mǎn)足：0<m(1,1)<n；0<m(1,2)<n；0<m(2,1)<n；0<m(2,2)<n；m(1,1)(modp)=mp；m(1,1)(modq)=mq；m(1,2)(modp)=mp；m(1,2)(modq)=q-mq；m(2,1)(modp)=p-mp；m(2,1)(modq)=mq；m(2,2)(modp)=p-mp；m(2,2)(modq)=q-mq。四、公鑰密碼Rabin計(jì)算4個(gè)數(shù)m(1,1)，m(1,2)65四、公鑰密碼Rabin（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。）于是，真正的明文m一定就是4個(gè)數(shù)m(1,1)，m(1,2)，m(2,1)，m(2,2)之中的一個(gè)。觀察4個(gè)數(shù)，排除那些沒(méi)有意義的“亂碼課文”。哪個(gè)是有意義的課文，哪個(gè)就是真正的明文m。解密完畢。四、公鑰密碼Rabin（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定66四、公鑰密碼RabinRabin的解密原理因?yàn)閚=pq是兩個(gè)不同的素?cái)?shù)的乘積，所以，關(guān)于未知數(shù)x的二次方程c=x2(modn)恰好有4個(gè)不同的根x，分別有以下形狀：一個(gè)根的(modp)、(modq)值是mp、mq；一個(gè)根的(modp)、(modq)值是mp、q-mq；一個(gè)根的(modp)、(modq)值是p-mp、mq；一個(gè)根的(modp)、(modq)值是p-mp、q-mq。四、公鑰密碼RabinRabin的解密原理67四、公鑰密碼Rabin4個(gè)根中有一個(gè)是明文m。如果把(modp)、(modq)值為mp、mq的根叫做m’，則(modp)、(modq)值為p-mp、q-mq的根就是n-m’。另外兩個(gè)根的和也等于n。即如果把一個(gè)叫做m’’，則另一個(gè)就是n-m’’。那么，4個(gè)不同的根怎樣計(jì)算呢？如果僅僅知道n，而不知道分解式n=pq，則無(wú)法計(jì)算mp和mq，因而無(wú)法計(jì)算這4個(gè)不同的根。四、公鑰密碼Rabin4個(gè)根中有一個(gè)是明文m。68四、公鑰密碼Rabin如果知道了n的分解式n=pq，則能夠計(jì)算mp和mq。再由mp和mq計(jì)算4個(gè)根，使用的是著名的孫子定理（中國(guó)剩余定理）（略）。最后，要判斷哪一個(gè)根是真正的明文。一般，真正的明文都具有語(yǔ)言含義，而其它的根則是沒(méi)有語(yǔ)言含義的“亂碼課文”。當(dāng)然也有例外，比如當(dāng)明文是一副圖象的編碼時(shí)，明文也是沒(méi)有語(yǔ)言含義的“亂碼課文”。四、公鑰密碼Rabin如果知道了n的分解式n=pq，則能夠計(jì)69四、公鑰密碼RabinRabin的安全性原理攻擊者Eve截獲了密文c。Eve還知道Bob的公鑰n，也知道明文m滿(mǎn)足方程c=m2(modn)。但是他不知道n的分解式n=pq，無(wú)法計(jì)算mp和mq，進(jìn)一步無(wú)法計(jì)算4個(gè)根。求n的分解式n=pq是大數(shù)分解問(wèn)題。四、公鑰密碼RabinRabin的安全性原理70如果每次都返回FALSE，LeonardAdleman(3)K為有限密鑰空間，是一些可能密鑰的有限集合；設(shè)明文m=(m1,m2,m3,…,mn)是長(zhǎng)度為n的比特串。(3)K為有限密鑰空間，是一些可能密鑰的有限集合；a1+a2+a3<a4；容易，只需要不超過(guò)N－1次加法。四、公鑰密碼RabinBob的公鑰是n，對(duì)外公布。p,q,d為保密的（私鑰）使用公鑰{b1，b2，b3，…，bn}計(jì)算密文c：c=m1b1+m2b2+m3b3+…+mnbn。n=100時(shí)C(100,2)=4,995于是，真正的明文m一定就是4個(gè)數(shù)(2)p-1和q-1分別含有大素因子p1和q1背包公鑰密碼的密鑰生成若干個(gè)N維向量組成的集合，如果滿(mǎn)足一般，真正的明文都具有語(yǔ)言含義，而其它的根則是沒(méi)有語(yǔ)言含義的“亂碼課文”。許多求解離散對(duì)數(shù)問(wèn)題的算法比窮舉快得多，比如Shanks算法，Pohlig-Hellman算法等。變換課文C是背包重量，由n個(gè)物品重量a1，a2，a3，…，an中的某些物品重量相加而成。m(1,1)(modq)=mq；四、公鑰密碼RabinRSA與Rabin比較比較項(xiàng)目RSARabin公鑰(n,e)n私鑰d(p,q)加密算法c=me(modn)c=m2(modn)解密算法m=cd(modn)若干步安全基礎(chǔ)大數(shù)分解問(wèn)題的困難性大數(shù)分解問(wèn)題的困難性如果每次都返回FALSE，四、公鑰密碼RabinRSA與Ra71第6章：公鑰密碼一、公鑰密碼的基本概念二、公鑰密碼RSA三、背包公鑰密碼四、公鑰密碼Rabin第6章：公鑰密碼一、公鑰密碼的基本概念72學(xué)習(xí)要點(diǎn)了解非對(duì)稱(chēng)密碼體制的提出背景、基本思想了解非對(duì)稱(chēng)密碼體制的基本應(yīng)用方向了解三種典型的公鑰密碼體制

DH密鑰交換算法RSAECC學(xué)習(xí)要點(diǎn)73§6－1概述問(wèn)題的提出：

密鑰管理困難傳統(tǒng)密鑰管理兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用戶(hù)需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶(hù)量增大時(shí)密鑰空間急劇增大。如:n=100時(shí)C(100,2)=4,995n=5000時(shí)C(5000,2)=12,497,500陌生人間的保密通信問(wèn)題

數(shù)字簽名的問(wèn)題傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴(lài)的需求§6－1概述問(wèn)題的提出：74公鑰密碼一課件75公鑰密碼的基本概念雙鑰密碼體制(公鑰密碼體制)于1976年由W.Diffie和M.Hellman[1976]提出，同時(shí)R.Merkle[1978]也獨(dú)立提出了這一體制?？捎糜诒Ｃ芡ㄐ?，也可用于數(shù)字簽字。這一體制的出現(xiàn)在密碼學(xué)史上是劃時(shí)代的事件，它為解決計(jì)算機(jī)信息網(wǎng)中的安全提供了新的理論和技術(shù)基礎(chǔ)。公鑰體制的基本原理是陷門(mén)單向函數(shù)。公鑰密碼的基本概念雙鑰密碼體制(公鑰密碼體制)于1976年76公鑰密碼一課件77注：1*.僅滿(mǎn)足(1)、(2)兩條的稱(chēng)為單向函數(shù)；第(3)條稱(chēng)為陷門(mén)性，δ稱(chēng)為陷門(mén)信息。

2*.當(dāng)用陷門(mén)函數(shù)f作為加密函數(shù)時(shí)，可將f公開(kāi)，這相當(dāng)于公開(kāi)加密密鑰。此時(shí)加密密鑰便稱(chēng)為公開(kāi)密鑰，記為Pk。f函數(shù)的設(shè)計(jì)者將δ保密，用作解密密鑰，此時(shí)δ稱(chēng)為秘密密鑰，記為Sk。由于加密函數(shù)是公開(kāi)的，任何人都可以將信息x加密成y=f(x)，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全信道傳送）；由于設(shè)計(jì)者擁有Sk，他自然可以解出x=f-1(y)。

3*.單向陷門(mén)函數(shù)的第(2)條性質(zhì)表明竊聽(tīng)者由截獲的密文y=f(x)推測(cè)x是不可行的。是滿(mǎn)足下列條件的函數(shù)f：(1)給定x，計(jì)算y=f(x)是容易的(2)給定y,計(jì)算x使y=f(x)是困難的(3)存在δ，已知δ時(shí),對(duì)給定的任何y，若相應(yīng)的x存在，則計(jì)算x使y=f(x)是容易的陷門(mén)單向函數(shù)注：1*.僅滿(mǎn)足(1)、(2)兩條的稱(chēng)為單向函數(shù)；第(3)78公鑰密碼一課件79對(duì)公鑰密碼體制的要求（1）參與方B容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰（公開(kāi)密鑰KUb和私有密鑰KRb）。（2）在知道公開(kāi)密鑰和待加密報(bào)文M的情況下，對(duì)于發(fā)送方A，很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)的密文：C＝EKUb（M）（3）接收方B使用私有密鑰容易通過(guò)計(jì)算解密所得的密文以便恢復(fù)原來(lái)的報(bào)文：M＝DKRb（C）＝DKRb（EKUb（M））（4）敵對(duì)方即使知道公開(kāi)密鑰KUb，要確定私有密鑰KRb在計(jì)算上是不可行的。（5）敵對(duì)方即使知道公開(kāi)密鑰KUb和密文C，要想恢復(fù)原來(lái)的報(bào)文M在計(jì)算上也是不可行的。（6）加密和解密函數(shù)可以以?xún)蓚€(gè)次序中的任何一個(gè)來(lái)使用:

M＝DKRb（EKUb（M））M=EKUb(DKRb(M))對(duì)公鑰密碼體制的要求（1）參與方B容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰（80單向函數(shù)舉例離散對(duì)數(shù)DL。給定一大素?cái)?shù)p（比如，p在21024數(shù)量級(jí)），p－1含另一大素?cái)?shù)因子。稱(chēng)log2p為素?cái)?shù)p的長(zhǎng)度。{1,

2,…,p-1}關(guān)于modp乘法構(gòu)成了一乘群Zp*，它是一個(gè)p－1階循環(huán)群。該循環(huán)群的生成元一共有φ(p-1)個(gè)。設(shè)一個(gè)生成元為整數(shù)g，1<g<p－1。設(shè)一個(gè)整數(shù)x，1<x<p－1。設(shè)y滿(mǎn)足y=gxmodp。單向函數(shù)舉例離散對(duì)數(shù)DL。給定一大素?cái)?shù)p（比如，p在21081單向函數(shù)舉例已知x，g，p，求y=gxmodp容易。這是因?yàn)?，采用折半相乘，只需要不超過(guò)2log2p次的modp乘法運(yùn)算。（實(shí)際上只需要不超過(guò)2log2x次的modp乘法運(yùn)算。如x=15=11112，g15modp=(((g)2g)2g)2gmodp，要用6次modp乘法）單向函數(shù)舉例已知x，g，p，求y=gxmodp容易。82單向函數(shù)舉例若已知y，g，p，求x滿(mǎn)足y=gxmodp，稱(chēng)為求解離散對(duì)數(shù)問(wèn)題。記為x=loggymodp。求解離散對(duì)數(shù)問(wèn)題的“最笨的方法”當(dāng)然就是窮舉，對(duì)每一個(gè)x∈{0,1,2,…,p－1}檢驗(yàn)是否y=gxmodp。窮舉求解法的運(yùn)算次數(shù)約為(p－1)/2。許多求解離散對(duì)數(shù)問(wèn)題的算法比窮舉快得多，比如Shanks算法，Pohlig-Hellman算法等。最快求解法的運(yùn)算次數(shù)約為數(shù)量級(jí)單向函數(shù)舉例若已知y，g，p，求x滿(mǎn)足y=gxmodp，稱(chēng)為83單向函數(shù)舉例這個(gè)計(jì)算量稱(chēng)為亞指數(shù)計(jì)算量。這是什么概念呢？我們知道p的長(zhǎng)度是log2p?？匆韵碌牟坏仁?。當(dāng)log2p≈1024時(shí)，亞指數(shù)計(jì)算量不小于2100數(shù)量級(jí)。至少在在當(dāng)前的計(jì)算水平之下是不能實(shí)現(xiàn)的。單向函數(shù)舉例這個(gè)計(jì)算量稱(chēng)為亞指數(shù)計(jì)算量。這是什么概念呢？我們84單向函數(shù)舉例大整數(shù)分解FAC。設(shè)有二大素?cái)?shù)p和q。設(shè)n=pq。若已知p和q，求n=pq只需一次乘法。但若已知n，求p和q滿(mǎn)足n=pq，則稱(chēng)為大整數(shù)分解問(wèn)題。迄今為止，已知的各種算法的漸近運(yùn)行時(shí)間約為：試除法：n/2。二次篩(QS)：橢圓曲線(EC)：數(shù)域篩(NFS)：?jiǎn)蜗蚝瘮?shù)舉例大整數(shù)分解FAC。設(shè)有二大素?cái)?shù)p和q。設(shè)n=pq85單向函數(shù)舉例背包問(wèn)題。已知向量A=(a1,a2,…,aN)，ai為正整數(shù)，稱(chēng)其為背包向量，稱(chēng)每個(gè)ai為物品重量。給定向量x=(x1,x2,…,xN)，xi{0,1}，求和式（稱(chēng)為背包重量）S=a1x1+a2x2+…+aNxN容易，只需要不超過(guò)N－1次加法。但已知A和S，求x則非常困難，稱(chēng)其為背包問(wèn)題，又稱(chēng)作子集和(Subset-Sum)問(wèn)題。一般只能用窮舉搜索法，有2N種可能。N大時(shí)，相當(dāng)困難。單向函數(shù)舉例背包問(wèn)題。已知向量86單向函數(shù)舉例背包問(wèn)題的特例：超遞增背包問(wèn)題。將物品重量從小到大排列：a1，a2，a3，…，aN。稱(chēng)該背包問(wèn)題為超遞增背包問(wèn)題，如果：a1<a2；a1+a2<a3；a1+a2+a3<a4；…a1+a2+a3+…+aN-1<aN。（超遞增背包問(wèn)題是容易解決的。）單向函數(shù)舉例背包問(wèn)題的特例：超遞增背包問(wèn)題。將物品重量從小到87（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。執(zhí)行概率素?cái)?shù)判定測(cè)試,如果n未測(cè)試通過(guò),則拒絕數(shù)值n,轉(zhuǎn)向步驟1Alice用Bob的公鑰n，計(jì)算：（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。格的維數(shù)總是不超過(guò)N。務(wù)必要先簽名后加密!x=15=11112，(3)K為有限密鑰空間，是一些可能密鑰的有限集合；Ua2>Ua1>M>Ua2(modM)=b2，了解三種典型的公鑰密碼體制C=18191223(mod2867)那么，4個(gè)不同的根怎樣計(jì)算呢？如果僅僅知道n，而不知道分解式n=pq，則無(wú)法計(jì)算mp和mq，因而無(wú)法計(jì)算這4個(gè)不同的根。第(3)條稱(chēng)為陷門(mén)性，δ稱(chēng)為陷門(mén)信息。隨機(jī)選一個(gè)奇數(shù)n(偽隨機(jī)數(shù)發(fā)生器)四、公鑰密碼Rabin（因?yàn)閑d是(p-1)(q-1)的倍數(shù)加1，所以med(modn)=m。（2）c=c1/c2(modn)，則c所對(duì)應(yīng)的明文一定是m=m1/m2(modn)；如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？分析者沒(méi)有辦法在有效時(shí)間內(nèi)將n分解出來(lái)。基本RSA的加密過(guò)程：Alice欲發(fā)送明文m給Bob，其中0<m<n。單向函數(shù)舉例定理設(shè)超遞增背包重量為S。如果k滿(mǎn)足ak<S<ak+1，則ak是背包中的最大物品重量。定理的證明

首先，背包中沒(méi)有大于ak的物品重量。其次，背包中確有等于ak的物品重量。證明完畢。注意到，尋找k滿(mǎn)足ak<S<ak+1只需要對(duì)比N次。（4個(gè)數(shù)的計(jì)算使用孫子定理（中國(guó)剩余定理）。單向函數(shù)舉例定理88單向函數(shù)舉例超遞增背包問(wèn)題的解決方法解決方法是可行的。設(shè)背包重量S，步驟如下。（1）窮舉：找k滿(mǎn)足ak<S<ak+1。（這說(shuō)明背包中的最大物品重量是ak）（2）記憶：存儲(chǔ)這個(gè)k。（3）卸載：如果S>0，則令S:=S-ak，返回（1）。如果w=0，則到（4）。（4）輸出前面存儲(chǔ)的所有的k，停止。單向函數(shù)舉例超遞增背包問(wèn)題的解決方法89單向函數(shù)舉例格的最小向量問(wèn)題(SVP)。若干個(gè)N維向量組成的集合，如果滿(mǎn)足“集合中任何若干個(gè)向量的整數(shù)線性組合仍是集合中的一個(gè)向量?！眲t該結(jié)合稱(chēng)為一個(gè)格。關(guān)于格有以下的性質(zhì)和概念。如果格中存在這樣的幾個(gè)向量，滿(mǎn)足①它們（實(shí)數(shù)）線性無(wú)關(guān)；②格中的任何其它向量都能唯一地表示為這幾個(gè)向量的整數(shù)線性組合。則這幾個(gè)向量構(gòu)成的向量組稱(chēng)為基?；械南蛄康膫€(gè)數(shù)稱(chēng)為格的維數(shù)。格的維數(shù)總是不超過(guò)N。單向函數(shù)舉例格的最小向量問(wèn)題(SVP)。90單向函數(shù)舉例給定一個(gè)格的一組基。尋找格中的“尺寸最小”的向量（即模最小的向量），稱(chēng)為格的最小向量問(wèn)題（shortestvectorproblem；SVP）。又稱(chēng)為格歸約。實(shí)際上，格歸約的傳統(tǒng)算法為L(zhǎng)LL算法，以后又有各種改進(jìn)的算法。當(dāng)格的維數(shù)比較大時(shí)（比如，維數(shù)大于200），當(dāng)前的所有格歸約算法都不是有效算法。單向函數(shù)舉例給定一個(gè)格的一組基。尋找格中的“尺寸最小”的向量91公開(kāi)密鑰密碼系統(tǒng)的分析方法強(qiáng)行攻擊(對(duì)密鑰)。公開(kāi)密鑰算法本身可能被攻破?？赡軋?bào)文攻擊(對(duì)報(bào)文本身的強(qiáng)行攻擊)。公開(kāi)密鑰密碼系統(tǒng)的分析方法強(qiáng)行攻擊(對(duì)密鑰)。92公鑰密碼系統(tǒng)的應(yīng)用類(lèi)型加密/解密數(shù)字簽名會(huì)話(huà)密鑰交換公鑰密碼系統(tǒng)的應(yīng)用類(lèi)型加密/解密93例子：簡(jiǎn)單數(shù)字簽名例子：簡(jiǎn)單數(shù)字簽名94例子續(xù)：安全數(shù)字簽名例子續(xù)：安全數(shù)字簽名95公鑰密碼一課件96公鑰密碼一課件97容易，只需要不超過(guò)N－1次加法。隨機(jī)選擇a<n,計(jì)算s次，n=5000時(shí)C(5000,2)=12,497,500陌生人間的保密通信問(wèn)題d(d×a)modn找到一個(gè)e滿(mǎn)足e×d＝1(modz)。TRUE:n一定不是素?cái)?shù)n=5000時(shí)C(5000,2)=12,497,500基本RSA的這個(gè)安全性漏洞稱(chēng)為可傳遞性。如果每次都返回FALSE，doc2×c(2)給定y,計(jì)算x使y=f(x)是困難的單向陷門(mén)函數(shù)的第(2)條性質(zhì)表明竊聽(tīng)者由截獲的密文y=f(x)推測(cè)x是不可行的。格歸約的傳統(tǒng)算法為L(zhǎng)LL算法，以后又有各種改進(jìn)的算法。在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。(3)K為有限密鑰空間，是一些可能密鑰的有限集合；格的維數(shù)總是不超過(guò)N。m(2,1)(modp)=p-mp；格歸約的傳統(tǒng)算法為L(zhǎng)LL算法，以后又有各種改進(jìn)的算法。執(zhí)行概率素?cái)?shù)判定測(cè)試,如果n未測(cè)試通過(guò),則拒絕數(shù)值n,轉(zhuǎn)向步驟1二、公鑰密碼RSA公鑰密碼RSA1977年由美國(guó)麻省理工學(xué)院的三位教授

RonaldRivestAdiShamirLeonardAdleman聯(lián)合發(fā)明容易，只需要不超過(guò)N－1次加法。二、公鑰密碼RSA公鑰密碼R98二、公鑰密碼RSARSA的密鑰生成選擇兩個(gè)大的素?cái)?shù)p和q。選擇兩個(gè)正整數(shù)e和d，滿(mǎn)足：ed是(p-1)(q-1)的倍數(shù)加1。計(jì)算n=pq。Bob的公鑰是（n，e），對(duì)外公布。Bob的私鑰是d，自己私藏。至于（p，q

），可以是Bob的另一部分私鑰，也可以是對(duì)所有人（包括Bob）都保密的。二、公鑰密碼RSARSA的密鑰生成99二、公鑰密碼RSA基本RSA的加密過(guò)程：Alice欲發(fā)送明文m給Bob，其中0<m<n

。Alice用Bob的公鑰（n，e），計(jì)算密文c為c=me(modn)?；綬SA的解密過(guò)程：Bob收到密文c后，用自己的公鑰（n，e）和私鑰d，計(jì)算cd(modn)=med(modn)=m。（因?yàn)閑d是(p-1)(q-1)的倍數(shù)加1，所以med(modn)=m。這是數(shù)論中的一個(gè)基本結(jié)論）二、公鑰密碼RSA基本RSA的加密過(guò)程：Alice欲發(fā)送明文100二、公鑰密碼RSA基本RSA的安全性攻擊者Eve已經(jīng)知道了Bob的公鑰是（n，e）。如果Eve還知道（p，q），則他容易知道Bob的私鑰d。此時(shí)Eve只需要用推廣的輾轉(zhuǎn)相除法尋找d，滿(mǎn)足ed=1(mod(p-1)(q-1))。由n的值求解（p，q）的值，即求解n的大整數(shù)分解n=pq，是一個(gè)公認(rèn)的數(shù)學(xué)難題（雖然至今并沒(méi)有證明），暫時(shí)還沒(méi)有有效的算法。二、公鑰密碼RSA基本RSA的安全性101二、公鑰密碼RSA目前普遍使用的參數(shù)范圍是2511<p<2512，2511<q<2512。如果Eve欲窮舉p的所有可能值，則窮舉的次數(shù)約為(2512-2511)/2=2510（次）。（因此，基本RSA似乎是足夠安全的）二、公鑰密碼RSA目前普遍使用的參數(shù)范圍是102二、公鑰密碼RSA基本RSA的一個(gè)安全性漏洞設(shè)攻擊者Eve獲得了兩組明文/密文對(duì)(m1，c1)，(m2，c2)。如果Bob新截獲了一個(gè)密文c，并發(fā)現(xiàn)：（1）c=c1c2(modn)，則c所對(duì)應(yīng)的明文一定是m=m1m2(modn)；（2）c=c1/c2(modn)，則c所對(duì)應(yīng)的明文一定是m=m1/m2(modn)；（3）c=c2/c1(modn)，則c所對(duì)應(yīng)的明文一定是m=m2/m1(modn)。（模除運(yùn)算·/·

(modn)是一個(gè)數(shù)論運(yùn)算）二、公鑰密碼RSA基本RSA的一個(gè)安全性漏洞103二、公鑰密碼RSA基本RSA的這個(gè)安全性漏洞稱(chēng)為可傳遞性。這個(gè)漏洞使得攻擊者Eve對(duì)某些新的密文能夠輕而易舉地找到其對(duì)應(yīng)明文。這個(gè)漏洞還有更深刻的隱患，比如在消息認(rèn)證過(guò)程中容易產(chǎn)生偽造。（將在后面介紹）為了克服基本RSA的這個(gè)安全性漏洞，人們將基本RSA進(jìn)行改造，引入Hash函數(shù)。（將在后面介紹）二、公鑰密碼RSA基本RSA的這個(gè)安全性漏洞稱(chēng)為可傳遞性。104要求：若使RSA安全，p與q必為足夠大的素?cái)?shù)，使分析者沒(méi)有辦法在有效時(shí)間內(nèi)將n分解出來(lái)。建議選擇p和q大約是100位的十進(jìn)制素?cái)?shù)。模n的長(zhǎng)度要求至少是512比特。為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)RSA模n的素因子p和q還有如下要求：(1)|p-q|很大，通常p和q的長(zhǎng)度相同；(2)p-1和q-1分別含有大素因子p1和q1(3)gcd(p1-1,q1-1)應(yīng)該很小。為了提高加密速度，通常取e為特定的小整數(shù)，如EDI國(guó)際標(biāo)準(zhǔn)中規(guī)定e＝216＋1，ISO/IEC9796中甚至允許取e＝3。這時(shí)加密速度一般比解密速度快10倍以上。要求：若使RSA安全，p與q必為足夠大的素?cái)?shù)，使105RSA密鑰的生成RSA密鑰的生成106公鑰密碼一課件107=[a(2i)modn]n=5000時(shí)C(5000,2)=12,497,500這是因?yàn)?，采用折半相乘，只需要不超過(guò)2log2p次的modp乘法運(yùn)算。(2)給定y,計(jì)算x使y=f(x)是困難的Bob的公鑰是（n，e），對(duì)外公布。Ua1>M>Ua1(modM)=b1，設(shè)y滿(mǎn)足y=gxmodp。定理設(shè)超遞增背包重量為S。當(dāng)log2p≈1024時(shí)，亞指數(shù)計(jì)算量不小于2100數(shù)量級(jí)。在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。務(wù)必要先簽名后加密!如果n已通過(guò)足夠的測(cè)試,則接受n,否則轉(zhuǎn)向步驟2;WITNESS(a,n)判定n是否為素?cái)?shù)，a是某個(gè)小于n的整數(shù)m(2,2)(modq)=q-mq。至于（p，q），可以是Bob的另一部分私鑰，也可以是對(duì)所有人（包括Bob）都保密的。例：明文=“RSAALGORITHM”一個(gè)根的(modp)、(modq)值是p-mp、q-mq。m的二進(jìn)制表示為bkbk-1…b0,則=18191024·1819128·181964·18194·18192·18191(mod2867)傳統(tǒng)密鑰管理兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用戶(hù)需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶(hù)量增大時(shí)密鑰空間急劇增大。例：p=47,q=61,(n)=(47-1)(61-1)=2760時(shí)，SK=167是否為秘密密鑰的候選者？

用歐氏算法計(jì)算：gcd(2760,167)=1即可證明。QX1X2X3Y1Y2Y3－1027600116716011671－168811－1688－117791－117792－33982－339－1728171－17281719－3142319－3142－7412231=[a(2i)modn]例：p=47,q=6108用RSA算法加密與解密的過(guò)程：例：明文=“RSAALGORITHM”(1)明文用數(shù)字表示空白=00，A=01,B=02,…,Z=26(兩位十進(jìn)制數(shù)表示)

1819010001120715180920081300(2)利用加密變換公式C=mPKmodr,即C=18191223mod2867=2756 PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223(mod2867) =18191024·1819128·181964·18194·18192·18191(mod2867) =27562756200105420669234704081815用RSA算法加密與解密的過(guò)程：27562001054109選擇兩個(gè)大素?cái)?shù)p和q，通常要求每個(gè)均大于10100。計(jì)算n＝pｘq和z＝(p－1)(q－1)。選擇一與z互素的數(shù)、令其為d。找到一個(gè)e滿(mǎn)足e×d＝1(modz)。選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文P長(zhǎng)度m滿(mǎn)足0<m<n。加密P時(shí)，計(jì)算C＝Pe(modn)，解密C時(shí)計(jì)算P＝Cd(modn)。由于模運(yùn)算的對(duì)稱(chēng)性，可以證明，在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。為實(shí)現(xiàn)加密，需要公開(kāi)(e,n)，為實(shí)現(xiàn)解密需要(d,n)。RSA算法歸納選擇兩個(gè)大素?cái)?shù)p和q，通常要求每個(gè)均大于10100。RSA算110如何計(jì)算abmodn？如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？如何找到足夠大的素?cái)?shù)p和q?問(wèn)題……如何計(jì)算abmodn？問(wèn)題……111要點(diǎn)1：(axb)modn=[(amodn)x(bmodn)]modn]

要點(diǎn)2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的問(wèn)題：am m的二進(jìn)制表示為bkbk-1…b0,

則計(jì)算ammodnammodn=[

a(2i)]modn =[a(2i)modn]bi0bi0