公鑰密碼-信息安全概論課件

信息安全與保密概論

第五章

公鑰密碼學(xué)信息安全與保密概論

第五章

1起源公鑰密碼又稱為雙鑰密碼和非對稱密碼，是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出的，見劃時(shí)代的文獻(xiàn)：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公鑰算法是由Rivest,Shamir和Adleman在1978年提出來的,見CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126起源公鑰密碼又稱為雙鑰密碼和非對稱密碼，是1976年由Dif2公開密鑰密碼的重要特性加密與解密由不同的密鑰完成 加密:XY:Y=EKU(X) 解密:YX:X=DKR(Y)=DKR(EKU(X))知道加密算法,從加密密鑰得到解密密鑰在計(jì)算上是不可行的兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密 X=DKR(EKU(X))=EKU(DKR(X))公開密鑰密碼的重要特性加密與解密由不同的密鑰完成3基于公開密鑰的加密過程基于公開密鑰的加密過程4基于公開密鑰的鑒別過程基于公開密鑰的鑒別過程5

用公鑰密碼實(shí)現(xiàn)保密用戶擁有自己的密鑰對(KU,KR)公鑰KU公開,私鑰KR保密AB:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X用公鑰密碼實(shí)現(xiàn)保密用戶擁有自己的密鑰對(KU,KR)6

用公鑰密碼實(shí)現(xiàn)鑒別條件:兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密鑒別: AALL:Y=DKRa(X) ALL:EKUa(Y)=EKUa(DKRa(X))=X鑒別+保密: AB:Z=EKUb(DKRa(X)) B:EKUa(DKRb(Z))=X用公鑰密碼實(shí)現(xiàn)鑒別條件:兩個(gè)密鑰中任何一個(gè)都可以用作加7

公鑰密鑰的應(yīng)用范圍加密/解密數(shù)字簽名(身份鑒別)密鑰交換算法加/解密數(shù)字簽名密鑰交換RSA是是是Dieffie-Hellman否否是DSS否是否公鑰密鑰的應(yīng)用范圍加密/解密算法加/解密數(shù)字簽名密鑰交換8基本思想和要求涉及到各方：發(fā)送方、接收方、攻擊者涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文公鑰算法的條件：產(chǎn)生一對密鑰是計(jì)算可行的已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的接收方利用私鑰來解密密文是計(jì)算可行的對于攻擊者，利用公鑰來推斷私鑰是計(jì)算不可行的已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的(可選)加密和解密的順序可交換基本思想和要求涉及到各方：發(fā)送方、接收方、攻擊者9陷門單向函數(shù)單向陷門函數(shù)是滿足下列條件的函數(shù)f：(1)給定x，計(jì)算y=fk(x)是容易的；(2)給定y,計(jì)算x使x=fk-1(y)是不可行的。(3)存在k’，已知k’時(shí),對給定的任何y，若相應(yīng)的x存在，則計(jì)算x使x=fk’-1(y)是容易的。陷門單向函數(shù)單向陷門函數(shù)是滿足下列條件的函數(shù)f：10

公鑰密碼基于的數(shù)學(xué)難題

背包問題大整數(shù)分解問題（TheIntegerFactorizationProblem,RSA體制）有限域的乘法群上的離散對數(shù)問題(TheDiscreteLogarithmProblem,ElGamal體制）橢圓曲線上的離散對數(shù)問題（TheEllipticCurveDiscreteLogarithmProblem,類比的ElGamal體制）公鑰密碼基于的數(shù)學(xué)難題

背包問題11數(shù)學(xué)基礎(chǔ)同余：給定任意整數(shù)a和m，以q除a，余數(shù)是r，則可以表示為a=sm+r,0r<m，其中s=[a/m],表示小于a/m的最大整數(shù)。定義r為amodm的剩余，記為ramodq.若整數(shù)a和b有(amodm)=(bmodm)，則稱a與b在modm下同余。同余關(guān)系的性質(zhì)：（1）為等價(jià)關(guān)系，即具有自反性，對稱性和可傳遞性自反性：aamodm對稱性：若abmodm，則bamodm傳遞性：若abmodm且bcmodm，則acmodm數(shù)學(xué)基礎(chǔ)同余：12同余（2）同余式可以進(jìn)行運(yùn)算若abmodm，cdmodm，則a+cb+dmodm，acbdmodm，anbnmodm（3）若acbcmodm，且（c，m）＝d，則abmodm/d；特別的，若(c,m)=1，則abmodm（4）若m≥1，(a,m)=1，則存在c使得ac1modm，稱c是a對模m的逆，記做a-1同余（2）同余式可以進(jìn)行運(yùn)算13同余（5）設(shè)a1和a2為任意整數(shù)，op為操作符，如＋、－等，則：

(a1opa2)modm=((a1modm)op(a2modm))modmeg.a1=23，a2=8，m=323＋8mod3＝31mod3＝1（23mod3＋8mod3）＝2＋2mod3＝123×8mod3＝184mod3＝1（23mod3×8mod3）＝2×2mod3＝1同余（5）設(shè)a1和a2為任意整數(shù)，op為操作符，如＋、－等，14同余（剩余）類假定m為正整數(shù)，任一整數(shù)除m得到的最小非負(fù)剩余必定為0，1，......，m-1中的一個(gè)，即任一整數(shù)對于模m必定與0，1，......，m-1中的某一個(gè)同余。因此，我們把全體整數(shù)分成若干兩兩不相交的集合，使得在同一個(gè)集合中的任意兩個(gè)數(shù)對模m同余，而屬于不同集合的兩個(gè)數(shù)對模m一定不同余。每一個(gè)這樣的集合稱作關(guān)于模m的同余類。完全剩余系從模m的每一個(gè)同余類中任取一數(shù)就得到m個(gè)數(shù)，這m個(gè)數(shù)稱作m的完全剩余系。如模4的一個(gè)完全剩余系{0，5，2，11}。通常選取的不大于m的m個(gè)非負(fù)整數(shù)集合{0，1，2，......，m-1}。同余類同余（剩余）類同余類15既約（互素）同余類和既約剩余系對于模m的同余類rmodm，如果(r,m)=1，則稱該同余類是模m的既約同余類。在模m的一個(gè)完全剩余系中，所有與m互素的數(shù)的集合構(gòu)成模m的既約剩余系。eg.m=5{0,1,2,3,4}{1,2,3,4}m=10{0,1,2,...9}{1,3,7,9}歐拉函數(shù)模m的所有既約同余類的個(gè)數(shù)記為φ(m)，通常稱作Euler函數(shù)。eg.φ(5)＝4，φ(10)＝4歐拉函數(shù)既約（互素）同余類和既約剩余系歐拉函數(shù)16Euler函數(shù)和Euler定理p是素?cái)?shù)，φ(p)=p-1若gcd(m,n)=1,則φ(mn)=φ(m)φ(n),特別地,若pq且都是素?cái)?shù),φ(pq)=(p-1)(q-1)

eg.φ(10)＝φ(2)φ(5)＝1×4＝4Euler定理：若(a,m)=1，則aφ(m)

≡1modm

eg.a＝7，m＝5，則74=72×72=4×4mod5＝1通過歐拉定理，可以求得a的逆a-1＝aφ(m)-1

modmEuler函數(shù)和Euler定理p是素?cái)?shù)，φ(p)=p-117Euler定理若(a,m)=1，則aφ(m)

1modm證明:R={x1，x2，…，xφ(m)}為所有小于m且與m互素的正整數(shù)，即為一個(gè)既約剩余系，考慮集合S={ax1modm,ax2modm

，…，axφ(m)modm}

aximodm與m互素

aximodm與axjmodm不同余，其中i≠j:

axi=axjmodmxi=xjmodn

故S也是一個(gè)剩余系，那么ximodm=(aximodm)((axi))modm

(aφ(m)xi)modm

aφ(m)1modmEuler定理若(a,m)=1，則aφ(m)1mod18

Fermat小定理Fermat小定理:p素?cái)?shù),(a,p)=1,則:ap-1

1modp推論:p素?cái)?shù),a是任意整數(shù),則:ap

amodp定理若(a,m)=1，則同余方程ax1modm有唯一的解eg.7x1mod5x=3,8,13,...證明：一定有解，因?yàn)閍aφ(m)-11modm若有不同的解x1,x2，則ax1ax2modm由于(a,m)=1，則x1x2modm用于在RSA中計(jì)算密鑰Fermat小定理Fermat小定理:p素?cái)?shù),(a,p)19

Euler定理推論推論:若m=pq,pq都是素?cái)?shù),k是任意整數(shù),則 ak(p-1)(q-1)+1

amodm,對任意0a<m證明:若(a,m)＝1，φ(m)=(p-1)(q-1),由Euler定理有aφ(m)

1modm，所以有結(jié)論成立；

否則a必定是p或者q的倍數(shù),不妨設(shè)a=sp,則0<s<q為正整數(shù),a與q互素,由Euler定理得到:aφ(q)

1modq(aφ(q))kφ(p)

1modq

ak(p-1)(q-1)

=tq+1t是整數(shù)等式兩邊乘以a=sp,得到:ak(p-1)(q-1)+1=(tq+1)sp=tspq+spamodmEuler定理推論推論:若m=pq,pq都是素?cái)?shù),20

原根(primitiveroot)Euler定理表明,對兩個(gè)互素的整數(shù)a,n, aφ(n)

1modn定義：素?cái)?shù)p的原根定義：如果a是素?cái)?shù)p的原根，則數(shù) amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整數(shù)的某種排列。對任意的整數(shù)b且(b,p)=1，我們可以找到唯一的冪i滿足b=aimodp0≦i≦(p-1)原根(primitiveroot)Euler定理表明21

離散對數(shù)若a是素?cái)?shù)p的一個(gè)原根,則對任意整數(shù)b,

(b,p)=1,存在唯一的整數(shù)i,1i(p-1),使得:

baimodp

i稱為b以a為基模p的指數(shù)(離散對數(shù)),記作inda,p(b).容易知道:

inda,p(xy)=[inda,p(x)+inda,p(y)]modφ(p)

inda,p(xr)=[rinda,p(x)]modφ(p)離散對數(shù)的計(jì)算:

ygxmodp已知g,x,p,計(jì)算y是容易的已知y,g,p,計(jì)算x是困難的離散對數(shù)若a是素?cái)?shù)p的一個(gè)原根,則對任意整數(shù)b,

(b,22經(jīng)典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經(jīng)典例子Diffie-Hellman密鑰交換算法23

Diffie-Hellman密鑰交換允許兩個(gè)用戶可以安全地交換一個(gè)秘密信息，用于后續(xù)的通訊過程算法的安全性依賴于計(jì)算離散對數(shù)的難度素?cái)?shù)p的原根定義：如果a是素?cái)?shù)p的原根，則數(shù) amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整數(shù)的某種排列。對任意的整數(shù)b，(b,p)=1,我們可以找到唯一的冪i滿足 b=aimodp0<=i<=(p-1)i在離散對數(shù)算法中稱為以a為基的指數(shù)modp。記為inda,p(b)Diffie-Hellman密鑰交換允許兩個(gè)用戶可以安全24Diffie-Hellman密鑰交換算法：雙方選擇素?cái)?shù)p以及p的一個(gè)原根a用戶A選擇一個(gè)隨機(jī)數(shù)Xa<p，計(jì)算Ya=aXamodp用戶B選擇一個(gè)隨機(jī)數(shù)Xb<p，計(jì)算Yb=aXbmodp每一方保密X值，而將Y值交換給對方用戶A計(jì)算出K=YbXamodp用戶B計(jì)算出K=YaXbmodp雙方獲得一個(gè)共享密鑰(aXaXbmodp)素?cái)?shù)p以及p的原根a可由一方選擇后發(fā)給對方Diffie-Hellman密鑰交換算法：25

GeneraterandomXa<pCalculateYa=aXamodpGeneraterandomXb<pCalculateYb=aXbmodpUserAUserBYaYbCalculateK=(Yb)XamodpCalculateK=(Ya)XbmodpDiffie-HellmanKeyExchangeGeneraterandomGeneraterand26

Diffie-Hellman密鑰交換的攻擊中間人攻擊圖示ABK=aXaXoOK=aXbXoDiffie-Hellman密鑰交換的攻擊中間人攻擊圖示27

Diffie-Hellman密鑰交換的攻擊中間人攻擊1雙方選擇素?cái)?shù)p以及p的一個(gè)原根a(假定O知道)2A選擇Xa<p,計(jì)算Ya=aXamodp,AB:Ya3O截獲Ya,選Xo,計(jì)算Yo=aXomodp,冒充AB:Yo4B選擇Xb<p,計(jì)算Yb=aXbmodp,BA:Yb5O截獲Yb,冒充BA:Yo6A計(jì)算:(Xo)Xa(aXo)XaaXoXamodp7B計(jì)算:(Xo)Xb(aXo)XXbaXoXbmodp8O計(jì)算:(Ya)XoaXaXomodp,(Yb)XoaXbXomodpO無法計(jì)算出aXaXbmodpO永遠(yuǎn)必須實(shí)時(shí)截獲并冒充轉(zhuǎn)發(fā),否則會(huì)被發(fā)現(xiàn)Diffie-Hellman密鑰交換的攻擊中間人攻擊28

經(jīng)典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經(jīng)典例子Diffie-Hellman密鑰交換算法29背包問題

背包問題描述：給定重量分別為a1,a2,…an的n個(gè)物品,裝入一個(gè)背包中,要求重量等于一個(gè)給定值，那么，究竟是那些物品？0-1背包問題：給定一個(gè)正整數(shù)S和一個(gè)背包向量A=(a1,…,an)，其中ai是正整數(shù)，求滿足方程

S=∑aixi的二進(jìn)制向量X=(x1,…,xn)。這是一個(gè)NP完全問題，解決這個(gè)問題所需要的時(shí)間與n呈指數(shù)增長背包問題

背包問題描述：給定重量分別為a1,a2,…an的n30背包問題用于公鑰密碼學(xué)做法：明文為X，S為密文奧妙在于有兩類背包，一類可以在線性時(shí)間內(nèi)求解，另一類則不能把易解的背包問題修改成難解的背包問題公開密鑰使用難解的背包問題私鑰使用易解的背包問題背包問題用于公鑰密碼學(xué)做法：明文為X，S為密文31

易解的背包問題——超遞增背包滿足下列條件的背包 ai>∑aj(j=1,…,i-1)這樣的背包也被稱為超遞增背包求解從最大的ai開始，如果S大于這個(gè)數(shù)，則減去ai,記xi為1，否則記xi為0如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包結(jié)果為{2,3,13,52}所以，密文70對應(yīng)的明文為110101易解的背包問題——超遞增背包滿足下列條件的背包32

轉(zhuǎn)換背包簡單背包用作私鑰如何產(chǎn)生相應(yīng)的公鑰——轉(zhuǎn)換做法：選擇一個(gè)整數(shù)m>∑ai(i=1,…,n)然后選擇一個(gè)與m互素的整數(shù)w，然后

ai'=wai(modm)(i=1,…,n)這里的ai'是偽隨機(jī)分布的這樣得到的背包是非超遞增背包轉(zhuǎn)換背包簡單背包用作私鑰33

基于背包問題的公鑰密碼系統(tǒng)

——MH公鑰算法加密將明文分為長度為n的塊X=(x1,…,xn)然后用公鑰A'=(a1',…,an')，將明文變?yōu)槊芪腟=E(X)=∑ai'

xi解密先計(jì)算S'=w-1Smodm再求解簡單背包問題S'=∑aixi基于背包問題的公鑰密碼系統(tǒng)

——MH公鑰算法加密34Eaxmple-從私鑰計(jì)算公鑰私鑰{2,3,6,13,27,52}w=31,m=1052*31mod105=623*31mod105=936*31mod105=8113*31mod105=8827*31mod105=10252*31mod105=37公鑰{62,93,81,88,102,37}Eaxmple-從私鑰計(jì)算公鑰私鑰{2,3,6,13,27,35Eaxmple-加密消息=011000110101101110明文:011000背包:6293818810237密文:93+81=174011000對應(yīng)于93+81=174110101對應(yīng)于62+93+88+37=280101110對應(yīng)于62+81+88+102=333Eaxmple-加密消息=01100011010110136Eaxmple-解密解密者知道{2,3,6,13,27,52},w,m計(jì)算w(w-1)=1mod(m)w-1=61密文為174,280,333174*61mod105=9=3+6,對應(yīng)于011000280*61mod105=70=2+3=13+52,對應(yīng)于110101333*61mod105=48=2+6+13+27,對應(yīng)于101110因此,消息=011000110101101110Eaxmple-解密解密者知道{2,3,6,13,27,5237

背包密碼系統(tǒng)的意義是第一個(gè)公鑰密碼系統(tǒng)有較好的理論價(jià)值在實(shí)踐過程中，大多數(shù)的背包方案都已被破解，或者證明存在缺陷背包密碼系統(tǒng)的意義是第一個(gè)公鑰密碼系統(tǒng)38

經(jīng)典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經(jīng)典例子Diffie-Hellman密鑰交換算法39

RSA算法1977年由RonRivest、AdiShamir和LenAdleman發(fā)明，1978年公布是一種分組加密算法。明文和密文在0~n-1之間,n是一個(gè)正整數(shù)應(yīng)用最廣泛的公鑰密碼算法只在美國申請專利，且已于2000年9月到期RSA算法1977年由RonRivest、AdiSh40

RSA算法描述

RSA加、解密算法(1978Rivest,Shamir,Adelman)

分組大小為k,2k<n2k+1公開密鑰n(兩素?cái)?shù)p和q的乘積)（推薦p,q等長）e，滿足（e，φ(n)）＝1（其中φ(n)=(p-1)(q-1)－保密）ed1(modφ(n))私人密鑰d（e-1mod(p-1)(q-1))

加密c=memodn解密m=cdmodnRSA算法描述

RSA加、解密算法(1978Riv41

42

RSA密鑰生成原理令n=pq,pq都是素?cái)?shù),(n)=(p-1)(q-1)是n的Euler數(shù)Euler定理推論:若n=pq,pq都是素?cái)?shù),k是任意整數(shù),則

mk(p-1)(q-1)+1

mmodn,對任意0mn只要選擇e,d,滿足ed=k(n)+1,即

ed1mod(n)de-1mod(n)公鑰:KU={e,n},私鑰:KR={d,n}RSA密鑰生成原理令n=pq,pq都是素?cái)?shù),(n)43

example（1）若Bob選擇了p=7和q＝5（2）那么，n=35,(n)=6×4＝24；（3）然而24＝23×3，一個(gè)正整數(shù)e能用作加密指數(shù)，當(dāng)且僅當(dāng)e不能被2，3所整除。假設(shè)Bob選擇了e=11，（4）那么用Euclidean算法將求得：d=e-1

11(mod24),于是Bob的解密密鑰d=11.（5）Bob在一個(gè)目錄中公開n=35和e=11（6）現(xiàn)假設(shè)Alice想發(fā)送明文2給Bob，她計(jì)算：211(mod35)=2526(mod35)=32*64=32*29=928(mod35)=18，且在一個(gè)信道上發(fā)送密文18。（7）當(dāng)Bob接收到密文18時(shí)，他用他的秘密解密指數(shù)（私鑰）d＝11進(jìn)行解密：1811（mod35)=(18)2*5+1=182*182*182*182*182*18=9*9*9*9*9*18=11*11*162=16*22=352=2mod35example（1）若Bob選擇了p=7和q＝544RSA安全性依據(jù)

RSA的安全性是基于加密函數(shù)ek(x)=xe(modn)是一個(gè)單向函數(shù)，所以對攻擊的人來說求逆計(jì)算不可行。而Bob能解密的陷門是分解n=pq，知(n)=(p-1)(q-1)。從而用歐氏算法解出解密私鑰d.（猜想：攻破RSA與分解n是多項(xiàng)式等價(jià)的。然而，這個(gè)猜想至今沒有給出可信的證明！?。。㏑SA安全性依據(jù)RSA的安全性是基于45

每個(gè)合數(shù)都可以唯一地分解出素?cái)?shù)因子 6=2·3 999999=3·3·3·7·11·13·37 27641=131·121 從2開始試驗(yàn)每一個(gè)小于等于√27641的素?cái)?shù)。素?cái)?shù)：只能被1和它本身整除的自然數(shù)；否則為合數(shù)。整數(shù)n的十進(jìn)制位數(shù)因子分解的運(yùn)算次數(shù)所需計(jì)算時(shí)間（每微秒一次） 50 1.4x1010 3.9小時(shí) 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年每個(gè)合數(shù)都可以唯一地分解出素?cái)?shù)因子素?cái)?shù)：只能被1和它本身46對RSA的攻擊方法

1、強(qiáng)力攻擊（窮舉法）：嘗試所有可能的私有密鑰2、數(shù)學(xué)分析攻擊：各種數(shù)學(xué)方法，等價(jià)與兩個(gè)素?cái)?shù)乘積的因子分解3、對RSA實(shí)現(xiàn)的攻擊對RSA的攻擊方法

1、強(qiáng)力攻擊（窮舉法）：嘗試所有可能的私47對RSA的攻擊對RSA的具體實(shí)現(xiàn)存在一些攻擊方法，但不是針對基本算法的，而是針對協(xié)議的。對RSA的選擇密文攻擊對RSA的公共模攻擊對RSA的小加密指數(shù)攻擊對RSA的小解密指數(shù)攻擊時(shí)間性攻擊：取決于解密算法的運(yùn)算時(shí)間對RSA的攻擊對RSA的具體實(shí)現(xiàn)存在一些攻擊方法，但不是針對48對RSA的選擇密文攻擊例1：E監(jiān)聽A的通信，收集由A的公開密鑰加密的密文c，E想知道消息的明文m,使m=cdmodn他首先選擇隨機(jī)數(shù)r,使r<n.然后用A的公開密鑰e計(jì)算x=remodny=xcmodnt=r-1modn如果x=remodn，則r=xdmodn現(xiàn)在E讓A對y簽名，即解密y,A向E發(fā)送u=ydmodn而E計(jì)算tumodn=r-1ydmodn=r-1xdcdmodn=cdmodn=m對RSA的選擇密文攻擊例1：E監(jiān)聽A的通信，收集由A的公開密49對RSA的選擇密文攻擊例2：E讓A對m3簽名。他產(chǎn)生兩個(gè)消息m1和m2，滿足m3=m1m2(modn)如果E能讓A分別對m1和m2簽名，則可以計(jì)算m3：m3d=(m1dmodn)(m2dmodn)注意：不要用RSA對陌生人的隨機(jī)文件簽名，簽名前先使用一個(gè)散列函數(shù)對RSA的選擇密文攻擊例2：E讓A對m3簽名。他產(chǎn)生兩個(gè)50對RSA的公共模攻擊一種可能的RSA實(shí)現(xiàn)方法是給每個(gè)人相同的n,但指數(shù)d和e不同。問題：如果相同的消息曾用兩個(gè)不同的指數(shù)加密，而這兩個(gè)指數(shù)是互素的，則明文可以不用任何一個(gè)解密密鑰來恢復(fù)。令m為明文消息，兩個(gè)加密密鑰為e1，e2,兩個(gè)密文消息為c1,c2c1=me1modnc2=me2modn由于e1和e2互素，所以可以用擴(kuò)展的Euclid算法找到r,s使re1+se2=1,假設(shè)r是負(fù)數(shù)，可以用擴(kuò)展的Euclid算法計(jì)算c1-1,而(c1-1)-r*c2s=mmodn注意:不要讓一群用戶共享一個(gè)模n對RSA的公共模攻擊一種可能的RSA實(shí)現(xiàn)方法是給每個(gè)人相同的51

對RSA的小加密指數(shù)攻擊如果使用一個(gè)較小的e值，則進(jìn)行RSA簽名和加密會(huì)很快，但也不安全。如果用相同e值的不同公開密鑰加密e(e+1)/2個(gè)線性相關(guān)的消息，則系統(tǒng)是可破的。如果有少于這些的消息或消息不相關(guān)，則無問題。比如：消息為mj,使用同樣的指數(shù)e,模數(shù)分別為q1,q2,…qs（兩兩互素）,則密文為mjemodq1，mjemodq2，…mjemodqs，根據(jù)中國剩余定理，m'=mjemodq1q2…qs.可以計(jì)算出來，對于較小的e，可以解出mj。解決辦法：加密前將消息與隨機(jī)值混合，并保證m與n有相同的長度。對RSA的小加密指數(shù)攻擊如果使用一個(gè)較小的e值，則進(jìn)行R52對RSA的小解密指數(shù)攻擊使用較小的d會(huì)產(chǎn)生窮盡解密攻擊的可能當(dāng)d為n的1/4長度時(shí)，而e小于n時(shí)，可以恢復(fù)d，當(dāng)e,d是隨機(jī)選擇的時(shí)，這種情況很少發(fā)生，當(dāng)e很小時(shí)不會(huì)發(fā)生。注意：應(yīng)選擇一個(gè)大的d值對RSA的小解密指數(shù)攻擊使用較小的d會(huì)產(chǎn)生窮盡解密攻擊的可能53RSA密碼體制的實(shí)現(xiàn)實(shí)現(xiàn)的步驟如下：Bob為實(shí)現(xiàn)者(1)Bob尋找出兩個(gè)大素?cái)?shù)p和q(2)Bob計(jì)算出n=pq和(n)=(p-1)(q-1).(3)Bob選擇一個(gè)隨機(jī)數(shù)e(0<e<(n))，滿足（e，(n)）＝1(4)Bob使用輾轉(zhuǎn)相除法計(jì)算d=e-1(mod(n))(5)Bob在目錄中公開n和e作為她的公開鑰。選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文P長度m滿足0<m<n。加密P時(shí)，計(jì)算C＝Pe(modn)，解密C時(shí)計(jì)算P＝Cd(modn)。由于模運(yùn)算的對稱性，可以證明，在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。為實(shí)現(xiàn)加密，需要公開(e,n)，為實(shí)現(xiàn)解密需要(d,n)。RSA密碼體制的實(shí)現(xiàn)實(shí)現(xiàn)的步驟如下：Bob為實(shí)現(xiàn)者54實(shí)現(xiàn)要求于是要求：若使RSA安全，p與q必為足夠大的素?cái)?shù)，使分析者沒有辦法在多項(xiàng)式時(shí)間內(nèi)將n分解出來。建議選擇p和q大約是100位的十進(jìn)制素?cái)?shù)。模n的長度要求至少是512比特。EDI攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長度為512至1024比特位之間，但必須是128的倍數(shù)。國際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC9796中規(guī)定n的長度位512比特位.至1996年，建議使用768位的模n。實(shí)現(xiàn)要求于是要求：若使RSA安全，p與q必為足夠大的素?cái)?shù)，使55素?cái)?shù)的選取為了抵抗現(xiàn)有的整數(shù)分解算法，對RSA模n的素因子p和q還有如下要求：(1)|p-q|很大，通常p和q的長度相同；(2)p-1和q-1分別含有大素因子p1和q1(3)P1-1和q1-1分別含有大素因子p2和q2(4)p+1和q+1分別含有大素因子p3和q3素?cái)?shù)的選取為了抵抗現(xiàn)有的整數(shù)分解算法，對RSA模n的素因子56加密指數(shù)e的選取為了提高加密速度，通常取e為特定的小整數(shù)，如EDI國際標(biāo)準(zhǔn)中規(guī)定e＝216＋1，ISO/IEC9796中甚至允許取e＝3。這時(shí)加密速度一般比解密速度快10倍以上。

e＝216＋1優(yōu)于e＝3之處在于它能夠抵抗對RSA的小加密指數(shù)攻擊加密指數(shù)e的選取為了提高加密速度，通常取e為特定的小整數(shù)，如57實(shí)現(xiàn)中的問題

（1）如何計(jì)算abmodn （2）如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？ （3）如何找到足夠大的素?cái)?shù)p和q?實(shí)現(xiàn)中的問題（1）如何計(jì)算abmodn58

(1)要點(diǎn)1：(axb)modn=[(amodn)x(bmodn)]modn]

要點(diǎn)2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的問題：am m的二進(jìn)制表示為bkbk-1…b0,則m=2ii0c0;d1forikdownto0 doc2xc d(dd)modn ifbi=1 thencc+1 d(da)modnreturnd計(jì)算ammodnammodn=[

a(2i)]modn =[a(2i)modn]bi0bi0(1)更一般性的問題：ami0c0;d1計(jì)算a59檢測素?cái)?shù)直接判斷一個(gè)整數(shù)是否為素?cái)?shù)是困難的命題:如果p是素?cái)?shù),則方程 x2

1modp只有平凡解x1modp.證明:x2

1modp p|(x2-1) p|(x+1)(x-1) p|(x+1),或者p|(x-1) x+1=kp,或者x-1=jp,k,j是整數(shù) x=kp-1,或者x=jp+1 x1modp,或者x

-1modp若方程x2

1modp存在的解不是x1，則P不是素?cái)?shù)。檢測素?cái)?shù)直接判斷一個(gè)整數(shù)是否為素?cái)?shù)是困難的60

(2)目前還沒有一個(gè)高效的辦法，實(shí)際中應(yīng)用最多MillerandRabin,WITNESS算法 WITNESS(a,n)判定n是否為素?cái)?shù)，a是某些小于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)(2)目前還沒有一個(gè)高效的辦法，實(shí)際中應(yīng)用最多1.令61

(3)通常的辦法是隨機(jī)選取一個(gè)大的奇數(shù)，然后進(jìn)行素性檢驗(yàn)1.隨機(jī)選一個(gè)奇數(shù)n(如:可使用偽隨機(jī)數(shù)發(fā)生器)2.隨機(jī)選擇一個(gè)整數(shù)a<n3.執(zhí)行概率素?cái)?shù)判定測試(如:用WITNESS(a,n)),如果n未測試通過,則拒絕數(shù)值n,轉(zhuǎn)向步驟14.如果n已通過足夠的測試,則接受n,否則轉(zhuǎn)向步驟2;說明：①隨機(jī)選取大約用ln(N)/2的次數(shù)，如ln(2200)/2=70②好在生成密鑰對時(shí)才用到，慢一點(diǎn)還可忍受。 ③確定素?cái)?shù)p和q以后，只需選取e,滿足gcd(e,(n))=1,計(jì)算 d=e-1mod(n)（sieve擴(kuò)展的歐拉算法）(3)通常的辦法是隨機(jī)選取一個(gè)大的奇數(shù)，然后進(jìn)行素性檢驗(yàn)62

信息安全與保密概論

第五章

公鑰密碼學(xué)信息安全與保密概論

第五章

63起源公鑰密碼又稱為雙鑰密碼和非對稱密碼，是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出的，見劃時(shí)代的文獻(xiàn)：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公鑰算法是由Rivest,Shamir和Adleman在1978年提出來的,見CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126起源公鑰密碼又稱為雙鑰密碼和非對稱密碼，是1976年由Dif64公開密鑰密碼的重要特性加密與解密由不同的密鑰完成 加密:XY:Y=EKU(X) 解密:YX:X=DKR(Y)=DKR(EKU(X))知道加密算法,從加密密鑰得到解密密鑰在計(jì)算上是不可行的兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密 X=DKR(EKU(X))=EKU(DKR(X))公開密鑰密碼的重要特性加密與解密由不同的密鑰完成65基于公開密鑰的加密過程基于公開密鑰的加密過程66基于公開密鑰的鑒別過程基于公開密鑰的鑒別過程67

用公鑰密碼實(shí)現(xiàn)保密用戶擁有自己的密鑰對(KU,KR)公鑰KU公開,私鑰KR保密AB:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X用公鑰密碼實(shí)現(xiàn)保密用戶擁有自己的密鑰對(KU,KR)68

用公鑰密碼實(shí)現(xiàn)鑒別條件:兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密鑒別: AALL:Y=DKRa(X) ALL:EKUa(Y)=EKUa(DKRa(X))=X鑒別+保密: AB:Z=EKUb(DKRa(X)) B:EKUa(DKRb(Z))=X用公鑰密碼實(shí)現(xiàn)鑒別條件:兩個(gè)密鑰中任何一個(gè)都可以用作加69

公鑰密鑰的應(yīng)用范圍加密/解密數(shù)字簽名(身份鑒別)密鑰交換算法加/解密數(shù)字簽名密鑰交換RSA是是是Dieffie-Hellman否否是DSS否是否公鑰密鑰的應(yīng)用范圍加密/解密算法加/解密數(shù)字簽名密鑰交換70基本思想和要求涉及到各方：發(fā)送方、接收方、攻擊者涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文公鑰算法的條件：產(chǎn)生一對密鑰是計(jì)算可行的已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的接收方利用私鑰來解密密文是計(jì)算可行的對于攻擊者，利用公鑰來推斷私鑰是計(jì)算不可行的已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的(可選)加密和解密的順序可交換基本思想和要求涉及到各方：發(fā)送方、接收方、攻擊者71陷門單向函數(shù)單向陷門函數(shù)是滿足下列條件的函數(shù)f：(1)給定x，計(jì)算y=fk(x)是容易的；(2)給定y,計(jì)算x使x=fk-1(y)是不可行的。(3)存在k’，已知k’時(shí),對給定的任何y，若相應(yīng)的x存在，則計(jì)算x使x=fk’-1(y)是容易的。陷門單向函數(shù)單向陷門函數(shù)是滿足下列條件的函數(shù)f：72

公鑰密碼基于的數(shù)學(xué)難題

背包問題大整數(shù)分解問題（TheIntegerFactorizationProblem,RSA體制）有限域的乘法群上的離散對數(shù)問題(TheDiscreteLogarithmProblem,ElGamal體制）橢圓曲線上的離散對數(shù)問題（TheEllipticCurveDiscreteLogarithmProblem,類比的ElGamal體制）公鑰密碼基于的數(shù)學(xué)難題

背包問題73數(shù)學(xué)基礎(chǔ)同余：給定任意整數(shù)a和m，以q除a，余數(shù)是r，則可以表示為a=sm+r,0r<m，其中s=[a/m],表示小于a/m的最大整數(shù)。定義r為amodm的剩余，記為ramodq.若整數(shù)a和b有(amodm)=(bmodm)，則稱a與b在modm下同余。同余關(guān)系的性質(zhì)：（1）為等價(jià)關(guān)系，即具有自反性，對稱性和可傳遞性自反性：aamodm對稱性：若abmodm，則bamodm傳遞性：若abmodm且bcmodm，則acmodm數(shù)學(xué)基礎(chǔ)同余：74同余（2）同余式可以進(jìn)行運(yùn)算若abmodm，cdmodm，則a+cb+dmodm，acbdmodm，anbnmodm（3）若acbcmodm，且（c，m）＝d，則abmodm/d；特別的，若(c,m)=1，則abmodm（4）若m≥1，(a,m)=1，則存在c使得ac1modm，稱c是a對模m的逆，記做a-1同余（2）同余式可以進(jìn)行運(yùn)算75同余（5）設(shè)a1和a2為任意整數(shù)，op為操作符，如＋、－等，則：

(a1opa2)modm=((a1modm)op(a2modm))modmeg.a1=23，a2=8，m=323＋8mod3＝31mod3＝1（23mod3＋8mod3）＝2＋2mod3＝123×8mod3＝184mod3＝1（23mod3×8mod3）＝2×2mod3＝1同余（5）設(shè)a1和a2為任意整數(shù)，op為操作符，如＋、－等，76同余（剩余）類假定m為正整數(shù)，任一整數(shù)除m得到的最小非負(fù)剩余必定為0，1，......，m-1中的一個(gè)，即任一整數(shù)對于模m必定與0，1，......，m-1中的某一個(gè)同余。因此，我們把全體整數(shù)分成若干兩兩不相交的集合，使得在同一個(gè)集合中的任意兩個(gè)數(shù)對模m同余，而屬于不同集合的兩個(gè)數(shù)對模m一定不同余。每一個(gè)這樣的集合稱作關(guān)于模m的同余類。完全剩余系從模m的每一個(gè)同余類中任取一數(shù)就得到m個(gè)數(shù)，這m個(gè)數(shù)稱作m的完全剩余系。如模4的一個(gè)完全剩余系{0，5，2，11}。通常選取的不大于m的m個(gè)非負(fù)整數(shù)集合{0，1，2，......，m-1}。同余類同余（剩余）類同余類77既約（互素）同余類和既約剩余系對于模m的同余類rmodm，如果(r,m)=1，則稱該同余類是模m的既約同余類。在模m的一個(gè)完全剩余系中，所有與m互素的數(shù)的集合構(gòu)成模m的既約剩余系。eg.m=5{0,1,2,3,4}{1,2,3,4}m=10{0,1,2,...9}{1,3,7,9}歐拉函數(shù)模m的所有既約同余類的個(gè)數(shù)記為φ(m)，通常稱作Euler函數(shù)。eg.φ(5)＝4，φ(10)＝4歐拉函數(shù)既約（互素）同余類和既約剩余系歐拉函數(shù)78Euler函數(shù)和Euler定理p是素?cái)?shù)，φ(p)=p-1若gcd(m,n)=1,則φ(mn)=φ(m)φ(n),特別地,若pq且都是素?cái)?shù),φ(pq)=(p-1)(q-1)

eg.φ(10)＝φ(2)φ(5)＝1×4＝4Euler定理：若(a,m)=1，則aφ(m)

≡1modm

eg.a＝7，m＝5，則74=72×72=4×4mod5＝1通過歐拉定理，可以求得a的逆a-1＝aφ(m)-1

modmEuler函數(shù)和Euler定理p是素?cái)?shù)，φ(p)=p-179Euler定理若(a,m)=1，則aφ(m)

1modm證明:R={x1，x2，…，xφ(m)}為所有小于m且與m互素的正整數(shù)，即為一個(gè)既約剩余系，考慮集合S={ax1modm,ax2modm

，…，axφ(m)modm}

aximodm與m互素

aximodm與axjmodm不同余，其中i≠j:

axi=axjmodmxi=xjmodn

故S也是一個(gè)剩余系，那么ximodm=(aximodm)((axi))modm

(aφ(m)xi)modm

aφ(m)1modmEuler定理若(a,m)=1，則aφ(m)1mod80

Fermat小定理Fermat小定理:p素?cái)?shù),(a,p)=1,則:ap-1

1modp推論:p素?cái)?shù),a是任意整數(shù),則:ap

amodp定理若(a,m)=1，則同余方程ax1modm有唯一的解eg.7x1mod5x=3,8,13,...證明：一定有解，因?yàn)閍aφ(m)-11modm若有不同的解x1,x2，則ax1ax2modm由于(a,m)=1，則x1x2modm用于在RSA中計(jì)算密鑰Fermat小定理Fermat小定理:p素?cái)?shù),(a,p)81

Euler定理推論推論:若m=pq,pq都是素?cái)?shù),k是任意整數(shù),則 ak(p-1)(q-1)+1

amodm,對任意0a<m證明:若(a,m)＝1，φ(m)=(p-1)(q-1),由Euler定理有aφ(m)

1modm，所以有結(jié)論成立；

否則a必定是p或者q的倍數(shù),不妨設(shè)a=sp,則0<s<q為正整數(shù),a與q互素,由Euler定理得到:aφ(q)

1modq(aφ(q))kφ(p)

1modq

ak(p-1)(q-1)

=tq+1t是整數(shù)等式兩邊乘以a=sp,得到:ak(p-1)(q-1)+1=(tq+1)sp=tspq+spamodmEuler定理推論推論:若m=pq,pq都是素?cái)?shù),82

原根(primitiveroot)Euler定理表明,對兩個(gè)互素的整數(shù)a,n, aφ(n)

1modn定義：素?cái)?shù)p的原根定義：如果a是素?cái)?shù)p的原根，則數(shù) amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整數(shù)的某種排列。對任意的整數(shù)b且(b,p)=1，我們可以找到唯一的冪i滿足b=aimodp0≦i≦(p-1)原根(primitiveroot)Euler定理表明83

離散對數(shù)若a是素?cái)?shù)p的一個(gè)原根,則對任意整數(shù)b,

(b,p)=1,存在唯一的整數(shù)i,1i(p-1),使得:

baimodp

i稱為b以a為基模p的指數(shù)(離散對數(shù)),記作inda,p(b).容易知道:

inda,p(xy)=[inda,p(x)+inda,p(y)]modφ(p)

inda,p(xr)=[rinda,p(x)]modφ(p)離散對數(shù)的計(jì)算:

ygxmodp已知g,x,p,計(jì)算y是容易的已知y,g,p,計(jì)算x是困難的離散對數(shù)若a是素?cái)?shù)p的一個(gè)原根,則對任意整數(shù)b,

(b,84經(jīng)典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經(jīng)典例子Diffie-Hellman密鑰交換算法85

Diffie-Hellman密鑰交換允許兩個(gè)用戶可以安全地交換一個(gè)秘密信息，用于后續(xù)的通訊過程算法的安全性依賴于計(jì)算離散對數(shù)的難度素?cái)?shù)p的原根定義：如果a是素?cái)?shù)p的原根，則數(shù) amodp,a2modp,…,ap-1modp是不同的并且包含1到p-1的整數(shù)的某種排列。對任意的整數(shù)b，(b,p)=1,我們可以找到唯一的冪i滿足 b=aimodp0<=i<=(p-1)i在離散對數(shù)算法中稱為以a為基的指數(shù)modp。記為inda,p(b)Diffie-Hellman密鑰交換允許兩個(gè)用戶可以安全86Diffie-Hellman密鑰交換算法：雙方選擇素?cái)?shù)p以及p的一個(gè)原根a用戶A選擇一個(gè)隨機(jī)數(shù)Xa<p，計(jì)算Ya=aXamodp用戶B選擇一個(gè)隨機(jī)數(shù)Xb<p，計(jì)算Yb=aXbmodp每一方保密X值，而將Y值交換給對方用戶A計(jì)算出K=YbXamodp用戶B計(jì)算出K=YaXbmodp雙方獲得一個(gè)共享密鑰(aXaXbmodp)素?cái)?shù)p以及p的原根a可由一方選擇后發(fā)給對方Diffie-Hellman密鑰交換算法：87

GeneraterandomXa<pCalculateYa=aXamodpGeneraterandomXb<pCalculateYb=aXbmodpUserAUserBYaYbCalculateK=(Yb)XamodpCalculateK=(Ya)XbmodpDiffie-HellmanKeyExchangeGeneraterandomGeneraterand88

Diffie-Hellman密鑰交換的攻擊中間人攻擊圖示ABK=aXaXoOK=aXbXoDiffie-Hellman密鑰交換的攻擊中間人攻擊圖示89

Diffie-Hellman密鑰交換的攻擊中間人攻擊1雙方選擇素?cái)?shù)p以及p的一個(gè)原根a(假定O知道)2A選擇Xa<p,計(jì)算Ya=aXamodp,AB:Ya3O截獲Ya,選Xo,計(jì)算Yo=aXomodp,冒充AB:Yo4B選擇Xb<p,計(jì)算Yb=aXbmodp,BA:Yb5O截獲Yb,冒充BA:Yo6A計(jì)算:(Xo)Xa(aXo)XaaXoXamodp7B計(jì)算:(Xo)Xb(aXo)XXbaXoXbmodp8O計(jì)算:(Ya)XoaXaXomodp,(Yb)XoaXbXomodpO無法計(jì)算出aXaXbmodpO永遠(yuǎn)必須實(shí)時(shí)截獲并冒充轉(zhuǎn)發(fā),否則會(huì)被發(fā)現(xiàn)Diffie-Hellman密鑰交換的攻擊中間人攻擊90

經(jīng)典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經(jīng)典例子Diffie-Hellman密鑰交換算法91背包問題

背包問題描述：給定重量分別為a1,a2,…an的n個(gè)物品,裝入一個(gè)背包中,要求重量等于一個(gè)給定值，那么，究竟是那些物品？0-1背包問題：給定一個(gè)正整數(shù)S和一個(gè)背包向量A=(a1,…,an)，其中ai是正整數(shù)，求滿足方程

S=∑aixi的二進(jìn)制向量X=(x1,…,xn)。這是一個(gè)NP完全問題，解決這個(gè)問題所需要的時(shí)間與n呈指數(shù)增長背包問題

背包問題描述：給定重量分別為a1,a2,…an的n92背包問題用于公鑰密碼學(xué)做法：明文為X，S為密文奧妙在于有兩類背包，一類可以在線性時(shí)間內(nèi)求解，另一類則不能把易解的背包問題修改成難解的背包問題公開密鑰使用難解的背包問題私鑰使用易解的背包問題背包問題用于公鑰密碼學(xué)做法：明文為X，S為密文93

易解的背包問題——超遞增背包滿足下列條件的背包 ai>∑aj(j=1,…,i-1)這樣的背包也被稱為超遞增背包求解從最大的ai開始，如果S大于這個(gè)數(shù)，則減去ai,記xi為1，否則記xi為0如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包結(jié)果為{2,3,13,52}所以，密文70對應(yīng)的明文為110101易解的背包問題——超遞增背包滿足下列條件的背包94

轉(zhuǎn)換背包簡單背包用作私鑰如何產(chǎn)生相應(yīng)的公鑰——轉(zhuǎn)換做法：選擇一個(gè)整數(shù)m>∑ai(i=1,…,n)然后選擇一個(gè)與m互素的整數(shù)w，然后

ai'=wai(modm)(i=1,…,n)這里的ai'是偽隨機(jī)分布的這樣得到的背包是非超遞增背包轉(zhuǎn)換背包簡單背包用作私鑰95

基于背包問題的公鑰密碼系統(tǒng)

——MH公鑰算法加密將明文分為長度為n的塊X=(x1,…,xn)然后用公鑰A'=(a1',…,an')，將明文變?yōu)槊芪腟=E(X)=∑ai'

xi解密先計(jì)算S'=w-1Smodm再求解簡單背包問題S'=∑aixi基于背包問題的公鑰密碼系統(tǒng)

——MH公鑰算法加密96Eaxmple-從私鑰計(jì)算公鑰私鑰{2,3,6,13,27,52}w=31,m=1052*31mod105=623*31mod105=936*31mod105=8113*31mod105=8827*31mod105=10252*31mod105=37公鑰{62,93,81,88,102,37}Eaxmple-從私鑰計(jì)算公鑰私鑰{2,3,6,13,27,97Eaxmple-加密消息=011000110101101110明文:011000背包:6293818810237密文:93+81=174011000對應(yīng)于93+81=174110101對應(yīng)于62+93+88+37=280101110對應(yīng)于62+81+88+102=333Eaxmple-加密消息=01100011010110198Eaxmple-解密解密者知道{2,3,6,13,27,52},w,m計(jì)算w(w-1)=1mod(m)w-1=61密文為174,280,333174*61mod105=9=3+6,對應(yīng)于011000280*61mod105=70=2+3=13+52,對應(yīng)于110101333*61mod105=48=2+6+13+27,對應(yīng)于101110因此,消息=011000110101101110Eaxmple-解密解密者知道{2,3,6,13,27,5299

背包密碼系統(tǒng)的意義是第一個(gè)公鑰密碼系統(tǒng)有較好的理論價(jià)值在實(shí)踐過程中，大多數(shù)的背包方案都已被破解，或者證明存在缺陷背包密碼系統(tǒng)的意義是第一個(gè)公鑰密碼系統(tǒng)100

經(jīng)典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經(jīng)典例子Diffie-Hellman密鑰交換算法101

RSA算法1977年由RonRivest、AdiShamir和LenAdleman發(fā)明，1978年公布是一種分組加密算法。明文和密文在0~n-1之間,n是一個(gè)正整數(shù)應(yīng)用最廣泛的公鑰密碼算法只在美國申請專利，且已于2000年9月到期RSA算法1977年由RonRivest、AdiSh102

RSA算法描述

RSA加、解密算法(1978Rivest,Shamir,Adelman)

分組大小為k,2k<n2k+1公開密鑰n(兩素?cái)?shù)p和q的乘積)（推薦p,q等長）e，滿足（e，φ(n)）＝1（其中φ(n)=(p-1)(q-1)－保密）ed1(modφ(n))私人密鑰d（e-1mod(p-1)(q-1))

加密c=memodn解密m=cdmodnRSA算法描述

RSA加、解密算法(1978Riv103

104

RSA密鑰生成原理令n=pq,pq都是素?cái)?shù),(n)=(p-1)(q-1)是n的Euler數(shù)Euler定理推論:若n=pq,pq都是素?cái)?shù),k是任意整數(shù),則

mk(p-1)(q-1)+1

mmodn,對任意0mn只要選擇e,d,滿足ed=k(n)+1,即

ed1mod(n)de-1mod(n)公鑰:KU={e,n},私鑰:KR={d,n}RSA密鑰生成原理令n=pq,pq都是素?cái)?shù),(n)105

example（1）若Bob選擇了p=7和q＝5（2）那么，n=35,(n)=6×4＝24；（3）然而24＝23×3，一個(gè)正整數(shù)e能用作加密指數(shù)，當(dāng)且僅當(dāng)e不能被2，3所整除。假設(shè)Bob選擇了e=11，（4）那么用Euclidean算法將求得：d=e-1

11(mod24),于是Bob的解密密鑰d=11.（5）Bob在一個(gè)目錄中公開n=35和e=11（6）現(xiàn)假設(shè)Alice想發(fā)送明文2給Bob，她計(jì)算：211(mod35)=2526(mod35)=32*64=32*29=928(mod35)=18，且在一個(gè)信道上發(fā)送密文18。（7）當(dāng)Bob接收到密文18時(shí)，他用他的秘密解密指數(shù)（私鑰）d＝11進(jìn)行解密：1811（mod35)=(18)2*5+1=182*182*182*182*182*18=9*9*9*9*9*18=11*11*162=16*22=352=2mod35example（1）若Bob選擇了p=7和q＝5106RSA安全性依據(jù)

RSA的安全性是基于加密函數(shù)ek(x)=xe(modn)是一個(gè)單向函數(shù)，所以對攻擊的人來說求逆計(jì)算不可行。而Bob能解密的陷門是分解n=pq，知(n)=(p-1)(q-1)。從而用歐氏算法解出解密私鑰d.（猜想：攻破RSA與分解n是多項(xiàng)式等價(jià)的。然而，這個(gè)猜想至今沒有給出可信的證明！?。。㏑SA安全性依據(jù)RSA的安全性是基于107

每個(gè)合數(shù)都可以唯一地分解出素?cái)?shù)因子 6=2·3 999999=3·3·3·7·11·13·37 27641=131·121 從2開始試驗(yàn)每一個(gè)小于等于√27641的素?cái)?shù)。素?cái)?shù)：只能被1和它本身整除的自然數(shù)；否則為合數(shù)。整數(shù)n的十進(jìn)制位數(shù)因子分解的運(yùn)算次數(shù)所需計(jì)算時(shí)間（每微秒一次） 50 1.4x1010 3.9小時(shí) 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年每個(gè)合數(shù)都可以唯一地分解出素?cái)?shù)因子素?cái)?shù)：只能被1和它本身108對RSA的攻擊方法

1、強(qiáng)力攻擊（窮舉法）：嘗試所有可能的私有密鑰2、數(shù)學(xué)分析攻擊：各種數(shù)學(xué)方法，等價(jià)與兩個(gè)素?cái)?shù)乘積的因子分解3、對RSA實(shí)現(xiàn)的攻擊對RSA的攻擊方法

1、強(qiáng)力攻擊（窮舉法）：嘗試所有可能的私109對RSA的攻擊對RSA的具體實(shí)現(xiàn)存在一些攻擊方法，但不是針對基本算法的，而是針對協(xié)議的。對RSA的選擇密文攻擊對RSA的公共模攻擊對RSA的小加密指數(shù)攻擊對RSA的小解密指數(shù)攻擊時(shí)間性攻擊：取決于解密算法的運(yùn)算時(shí)間對RSA的攻擊對RSA的具體實(shí)現(xiàn)存在一些攻擊方法，但不是針對110對RSA的選擇密文攻擊例1：E監(jiān)聽A的通信，收集由A的公開密鑰加密的密文c，E想知道消息的明文m,使m=cdmodn他首先選擇隨機(jī)數(shù)r,使r<n.然后用A的公開密鑰e計(jì)算x=remodny=xcmodnt=r-1modn如果x=remodn，則r=xdmodn現(xiàn)在E讓A對y簽名，即解密y,A向E發(fā)送u=ydmodn而E計(jì)算tumodn=r-1ydmodn=r-1xdcdmodn=cdmodn=m對RSA的選擇密文攻擊例1：E監(jiān)聽A的通信，收集由A的公開密111對RSA的選擇密文攻擊例2：E讓A對m3簽名。他產(chǎn)生兩個(gè)消息m1和m2，滿足m3=m1m2(modn)如果E能讓A分別對m1和m2簽名，則可以計(jì)算m3：m3d=(m1dmodn)(m2dmodn)注意：不要用RSA對陌生人的隨機(jī)文件簽名，簽名前先使用一個(gè)散列函數(shù)對RSA的選擇密文攻擊例2：E讓A對m3簽名。他產(chǎn)生兩個(gè)112對RSA的公共模攻擊一種可能的RSA實(shí)現(xiàn)方法是給每個(gè)人相同的n,但指數(shù)d和e不同。問題：如果相同的消息曾用兩個(gè)不同的指數(shù)加密，而這兩個(gè)指數(shù)是互素的，則明文可以不用任何一個(gè)解密密鑰來恢復(fù)。令m為明文消息，兩個(gè)加密密鑰為e1，e2,兩個(gè)密文消息為c1,c2c1=me1modnc2=me2modn由于e1和e2互素，所以可以用擴(kuò)展的Euclid算法找到r,s使re1+se2=1,假設(shè)r是負(fù)數(shù)，可以用擴(kuò)展的Euclid算法計(jì)算c1-1,而(c1-1)-r*c2s=mmodn注意:不要讓一群用戶共享一個(gè)模n對RSA的公共模攻擊一種可能的RSA實(shí)現(xiàn)方法是給每個(gè)人相同的113

對RSA的小加密指數(shù)攻擊如果使用一個(gè)較小的e值，則進(jìn)行RSA簽名和加密會(huì)很快，但也不安全。如果用相同e值的不同公開密鑰加密e(e+1)/2個(gè)線性相關(guān)的消息，則系統(tǒng)是可破的。如果有少于這些的消息或消息不相關(guān)，則無問題。