第章公鑰密碼體制

第2.3章公鑰密碼體制公鑰密碼學(xué)RSA算法傳統(tǒng)密碼體制的不足對稱密碼體制的問題加密能力與解密能力是捆綁在一起的密鑰更換、傳遞和交換需要可靠信道如有n用戶，則需要C=n(n-1)/2個(gè)密鑰，n=1000時(shí)，C(1000,2)≈500000，管理困難無法滿足不相識的人之間通信的保密要求不能實(shí)現(xiàn)數(shù)字簽名公鑰密碼學(xué)解決的基本問題密鑰交換對稱密碼進(jìn)行密鑰交換的要求：已經(jīng)共享一個(gè)密鑰利用密鑰分配中心數(shù)字簽名如果密碼編碼學(xué)要獲得廣泛的應(yīng)用，不僅用在軍事場合而且用于商業(yè)或私人目的，那么電子報(bào)文和文件就需要一種與書面材料中使用的簽名等效的認(rèn)證手段。也就是說，我們能不能設(shè)計(jì)一種方法可以讓參與各方都信服地確認(rèn)一個(gè)數(shù)字報(bào)文是由某個(gè)人發(fā)送的？這是一個(gè)比鑒別更高一些的要求公鑰密碼學(xué)公鑰密碼學(xué)是密碼學(xué)一次偉大的革命1976年，Diffie和Hellman在“密碼學(xué)新方向”一文中提出使用兩個(gè)密鑰：公密鑰、私密鑰加解密的非對稱性利用數(shù)論的方法是對對稱密碼的重要補(bǔ)充(/)公鑰密碼體制重要特點(diǎn)僅根據(jù)密碼算法和加密密鑰來確定解密密鑰在計(jì)算上不可行。兩個(gè)密鑰中的任何一個(gè)都可用來加密，另一個(gè)用來解密。六個(gè)組成部分：明文、密文；公鑰、私鑰；加密、解密算法(/)對公鑰密碼的要求1.B產(chǎn)生一對密鑰(公鑰KUb，私鑰KRb)在計(jì)算上是容易的。2.已知公鑰和要加密的消息m，發(fā)送方A產(chǎn)生相應(yīng)的密文在計(jì)算上是容易的：c=EKUb(m)3.接收方B使用其私鑰對接收的密文解密以恢復(fù)明文在計(jì)算上是容易的：m=DKRb(c)=DKRb

[EKUb(m)]4.已知公鑰KUb時(shí)，攻擊者要確定私鑰KRb在計(jì)算上是不可行的。5.已知公鑰KUb和密文c，攻擊者要恢復(fù)明文m在計(jì)算上是不可行的。6.加密和解密函數(shù)的順序可以交換順序：m=EKUb

[DKRb(m)]=DKUb

[EKRb(m)]單向函數(shù)單向函數(shù)將一個(gè)定義域映射到一個(gè)值域，使得每個(gè)函數(shù)值有一個(gè)惟一的原像；函數(shù)值計(jì)算很容易，而逆計(jì)算是不可行的

y=f(x) 容易

x=f-1(y) 不容易例子打碎/拼接平方/開方乘法/分解單向陷門函數(shù)對公鑰密碼的要求，相當(dāng)于尋找一個(gè)單向陷門函數(shù)除非知道某種附加的信息，否則這樣的函數(shù)在一個(gè)方向上容易計(jì)算，而在另外的方向上要計(jì)算是不可行的。有了附加信息，函數(shù)的逆就可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出來。即：

y=fk(x)容易，如果知道了k和x

x=fk-1(y)容易，如果知道了k和y

x=fk-1(y)不可行，如果知道y而不知道k例子魔方的置亂/恢復(fù) 如果有口訣，就能很快恢復(fù)公鑰密碼體制(/)公鑰密碼體制的加密功能A向B發(fā)消息XB的公鑰為KUb,私鑰為KRb加密Y=EKUb(X)解密X=DKRb(Y)(/)公鑰密碼體制的加密功能(/)公鑰密碼體制的認(rèn)證A向B發(fā)送消息XA的公鑰為KUa，私鑰為KRa“加密”：Y=EKRa(X)（數(shù)字簽名）“解密”：X=DKUa(Y)注意：不能保證消息的保密性(/)公鑰密碼體制的認(rèn)證(/)具有保密與認(rèn)證的公鑰體制(/)對稱密鑰和公鑰密鑰(/)關(guān)于公鑰密碼的幾種誤解公鑰密碼比傳統(tǒng)密碼安全？公鑰密碼是通用方法，所以傳統(tǒng)密碼已經(jīng)過時(shí)？公鑰密碼實(shí)現(xiàn)密鑰分配非常簡單？(/)公鑰密碼體制的應(yīng)用加密/解密：發(fā)送方用接收方的公開密鑰加密報(bào)文數(shù)字簽名：發(fā)送方用它自己的私有密鑰“簽署”報(bào)文。簽署功能是通過對于報(bào)文，或者作為報(bào)文的一個(gè)函數(shù)的一小塊數(shù)據(jù)應(yīng)用密碼算法完成的密鑰交換：兩方合作以便交換會話密鑰。這有幾種可能的方法，其中涉及到一方或兩方的私有密鑰RSA算法簡介RSA是基于Diffie和Hellman所提出的單向陷門函數(shù)的定義而給出的第一個(gè)公鑰密碼的實(shí)際實(shí)現(xiàn)RSA算法的名字以發(fā)明者的名字命名：RonRivest，AdiShamir和LeonardAdlemanRSA算法于1977年12月申請專利(U.S.Patent4,405,829)，2000年9月到期明文、密文是0到n-1之間的整數(shù)，通常n的大小為1024位或309位十進(jìn)制數(shù)RSA的安全性一直未能得到理論上的證明，它經(jīng)歷了各種攻擊，至今未被完全攻破國際上一些標(biāo)準(zhǔn)化組織ISO、ITU、SWIFT等均已接受RSA體制作為標(biāo)準(zhǔn)。在Internet中所采用的PGP(PrettyGoodPrivacy)中也將RSA作為傳送會話密鑰和數(shù)字簽名的標(biāo)準(zhǔn)算法RSA算法描述加密：c=memodn,其中0≤m<n解密：m=cdmodn =(memodn)dmodn =(me)dmodn公鑰為(e,n)，私鑰為(d,n)必須滿足以下條件：med

≡mmodn計(jì)算me和cd是比較容易的由e和n確定d是不可行的(/)為什么RSA可以加解密(/)因?yàn)镋uler定理的一個(gè)推論，對于給定素?cái)?shù)p和q，整數(shù)n和m，k，其中n=p

×

q，0<m<n，則下列等式成立：mk·?(n)＋1≡mmodnRSA中:n=p

×

q?(n)=(p-1)(q-1)選擇e&d

使得e·d≡1mod

?(n)因此存在k使得e·d=1+k·?(n)因此

cd=(me)d=m1+k.?(N)≡mmodn

相關(guān)參數(shù)(n)：指小于n并且與n互素的正整數(shù)的個(gè)數(shù) [參考書第8.2.2章Euler函數(shù)]對于素?cái)?shù)p有：(p)=p-1

如：(37)=36對于n=pq，p，q均為素?cái)?shù)，有(pq)=(p-1)(q-1)

(21)=(3–1)×(7–1)=2×6=12gcd(a,b)=1[參考書第4.3章Euclid算法]a,b

最大公因子為1，也即a,b互素a

≡b

modn[參考書第4.2章模運(yùn)算](amodn)=(bmodn)，則稱a，b對于模n同余，記為a

≡b

modn如73≡4mod23 21≡-9mod10RSA密鑰的產(chǎn)生(/)隨機(jī)選擇兩個(gè)大素?cái)?shù)p,q

計(jì)算n=p×q注意?(n)=(p-1)(q-1)

選擇e使得1<e<?(n),且gcd(e,?(n))=1解下列方程求出de

×

d≡1mod?(n)且0≤d≤n

公布公鑰：KU={e,n}保存私鑰：KR={d,n}銷毀：p,qRSA的使用(/)發(fā)送方要加密明文m:獲得接收方的公鑰KU={e,n}計(jì)算:c=memodn,where0≤m<n接收方解密密文c:

使用自己的私鑰KR={d,n}計(jì)算:m=cdmodn

注意：m必須比n小模冪運(yùn)算模冪運(yùn)算是RSA中的主要運(yùn)算[(amodn)×(bmodn)]modn=(a×b)modn利用中間結(jié)果對n取模，實(shí)現(xiàn)高效算法對于RSA的模運(yùn)算mamodn

假設(shè)a二進(jìn)制表示為bibi-1…b0，則模運(yùn)算可變化如下：RSA實(shí)例(/)選擇兩個(gè)素?cái)?shù):p=17和q=11計(jì)算n=pq=17×11=187機(jī)算?(n)=(p–1)(q-1)=16×10=160選擇e，使其與?(n)互素且小于?(n)。在此選擇e=7確定d：de≡1mod160并且d<?(n)。

因?yàn)?3×7=161=10×160+1，符合要求。所以選擇d=23。公布公鑰KU={7,187}保護(hù)私鑰KR={23,17,11}RSA實(shí)例對于明文信息m=88(88<187)加密：C=887

mod187 =[(884

mod187)×(882

mod187)×(881

mod187)]mod187 =(88×77×132)

mod187=11 881

mod187=88 882

mod187=(88×88)mod187=77 884

mod187=[(882

mod187)×(882

mod187)]mod187 =(77×77)mod187=132解密：M=1123

mod187=88

(/)問題1p=3，q=11，n=33，(n)=20，d=77e=1mod20，e=3加解密如下明文：(/)問題2c=10,e=5,n=35,m能夠求出嗎？如果：e=31,n=3599,d=?你看出什么問題了嗎解答c=10,e=5,n=35,m能夠求出嗎？n=35=5×7=>p=5,q=7=>(n)=(5-1)(7-1)=24e=5,可以找到d=5

m=cdmodn=105mod35=5

RSA密鑰生成必須做確定兩個(gè)大素?cái)?shù)：p,q

p,q

都應(yīng)該在1075，10100之間選擇e或者d，并計(jì)算d或者e素?cái)?shù)測試是重要的算法[參考書p1778.3素?cái)?shù)測試]由e求d要使用到擴(kuò)展Euclid算法[參考書p97EXTENDEDEUCLID](/)RSA