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

信息安全與保密概論

第五章

公鑰密碼學信息安全與保密概論

第五章

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

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))知道加密算法,從加密密鑰得到解密密鑰在計算上是不可行的兩個密鑰中任何一個都可以用作加密而另一個用作解密 X=DKR(EKU(X))=EKU(DKR(X))公開密鑰密碼的重要特性加密與解密由不同的密鑰完成3基于公開密鑰的加密過程基于公開密鑰的加密過程4基于公開密鑰的鑒別過程基于公開密鑰的鑒別過程5

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

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

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

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

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

背包問題11數(shù)學基礎同余：給定任意整數(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下同余。同余關系的性質：（1）為等價關系，即具有自反性，對稱性和可傳遞性自反性：aamodm對稱性：若abmodm，則bamodm傳遞性：若abmodm且bcmodm，則acmodm數(shù)學基礎同余：12同余（2）同余式可以進行運算若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）同余式可以進行運算13同余（5）設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）設a1和a2為任意整數(shù)，op為操作符，如＋、－等，14同余（剩余）類假定m為正整數(shù)，任一整數(shù)除m得到的最小非負剩余必定為0，1，......，m-1中的一個，即任一整數(shù)對于模m必定與0，1，......，m-1中的某一個同余。因此，我們把全體整數(shù)分成若干兩兩不相交的集合，使得在同一個集合中的任意兩個數(shù)對模m同余，而屬于不同集合的兩個數(shù)對模m一定不同余。每一個這樣的集合稱作關于模m的同余類。完全剩余系從模m的每一個同余類中任取一數(shù)就得到m個數(shù)，這m個數(shù)稱作m的完全剩余系。如模4的一個完全剩余系{0，5，2，11}。通常選取的不大于m的m個非負整數(shù)集合{0，1，2，......，m-1}。同余類同余（剩余）類同余類15既約（互素）同余類和既約剩余系對于模m的同余類rmodm，如果(r,m)=1，則稱該同余類是模m的既約同余類。在模m的一個完全剩余系中，所有與m互素的數(shù)的集合構成模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的所有既約同余類的個數(shù)記為φ(m)，通常稱作Euler函數(shù)。eg.φ(5)＝4，φ(10)＝4歐拉函數(shù)既約（互素）同余類和既約剩余系歐拉函數(shù)16Euler函數(shù)和Euler定理p是素數(shù)，φ(p)=p-1若gcd(m,n)=1,則φ(mn)=φ(m)φ(n),特別地,若pq且都是素數(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是素數(shù)，φ(p)=p-117Euler定理若(a,m)=1，則aφ(m)

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

，…，axφ(m)modm}

aximodm與m互素

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

axi=axjmodmxi=xjmodn

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

(aφ(m)xi)modm

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

Fermat小定理Fermat小定理:p素數(shù),(a,p)=1,則:ap-1

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

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

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

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

1modm，所以有結論成立；

否則a必定是p或者q的倍數(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都是素數(shù),20

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

1modn定義：素數(shù)p的原根定義：如果a是素數(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是素數(shù)p的一個原根,則對任意整數(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ù)的計算:

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

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

經典例子Diffie-Hellman密鑰交換算法23

Diffie-Hellman密鑰交換允許兩個用戶可以安全地交換一個秘密信息，用于后續(xù)的通訊過程算法的安全性依賴于計算離散對數(shù)的難度素數(shù)p的原根定義：如果a是素數(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密鑰交換允許兩個用戶可以安全24Diffie-Hellman密鑰交換算法：雙方選擇素數(shù)p以及p的一個原根a用戶A選擇一個隨機數(shù)Xa<p，計算Ya=aXamodp用戶B選擇一個隨機數(shù)Xb<p，計算Yb=aXbmodp每一方保密X值，而將Y值交換給對方用戶A計算出K=YbXamodp用戶B計算出K=YaXbmodp雙方獲得一個共享密鑰(aXaXbmodp)素數(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雙方選擇素數(shù)p以及p的一個原根a(假定O知道)2A選擇Xa<p,計算Ya=aXamodp,AB:Ya3O截獲Ya,選Xo,計算Yo=aXomodp,冒充AB:Yo4B選擇Xb<p,計算Yb=aXbmodp,BA:Yb5O截獲Yb,冒充BA:Yo6A計算:(Xo)Xa(aXo)XaaXoXamodp7B計算:(Xo)Xb(aXo)XXbaXoXbmodp8O計算:(Ya)XoaXaXomodp,(Yb)XoaXbXomodpO無法計算出aXaXbmodpO永遠必須實時截獲并冒充轉發(fā),否則會被發(fā)現(xiàn)Diffie-Hellman密鑰交換的攻擊中間人攻擊28

經典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經典例子Diffie-Hellman密鑰交換算法29背包問題

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

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

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

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

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

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

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

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

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

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

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

經典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經典例子Diffie-Hellman密鑰交換算法39

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

RSA算法描述

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

分組大小為k,2k<n2k+1公開密鑰n(兩素數(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都是素數(shù),(n)=(p-1)(q-1)是n的Euler數(shù)Euler定理推論:若n=pq,pq都是素數(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都是素數(shù),(n)43

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

11(mod24),于是Bob的解密密鑰d=11.（5）Bob在一個目錄中公開n=35和e=11（6）現(xiàn)假設Alice想發(fā)送明文2給Bob，她計算：211(mod35)=2526(mod35)=32*64=32*29=928(mod35)=18，且在一個信道上發(fā)送密文18。（7）當Bob接收到密文18時，他用他的秘密解密指數(shù)（私鑰）d＝11進行解密：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)是一個單向函數(shù)，所以對攻擊的人來說求逆計算不可行。而Bob能解密的陷門是分解n=pq，知(n)=(p-1)(q-1)。從而用歐氏算法解出解密私鑰d.（猜想：攻破RSA與分解n是多項式等價的。然而，這個猜想至今沒有給出可信的證明?。。。㏑SA安全性依據(jù)RSA的安全性是基于45

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

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

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

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

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

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

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

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

a(2i)]modn =[a(2i)modn]bi0bi0(1)更一般性的問題：ami0c0;d1計算a59檢測素數(shù)直接判斷一個整數(shù)是否為素數(shù)是困難的命題:如果p是素數(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不是素數(shù)。檢測素數(shù)直接判斷一個整數(shù)是否為素數(shù)是困難的60

(2)目前還沒有一個高效的辦法，實際中應用最多MillerandRabin,WITNESS算法 WITNESS(a,n)判定n是否為素數(shù)，a是某些小于n的整數(shù)1.令bkbk-1…b0為(n-1)的二進制表示，2.d13.forikdownto04. doxd5. d(dd)modn6. ifd=1andx1andxn-17. thenreturnTRUE8. ifbi=19. thend(da)modn10.ifd111.thenreturnTRUE12.returnFALSE

返回值：TRUE:n一定不是素數(shù)FALSE:n可能是素數(shù)應用：隨機選擇a<n,計算s次，如果每次都返回FALSE，則這時n是素數(shù)的概率為 (1-1/2s)(2)目前還沒有一個高效的辦法，實際中應用最多1.令61

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

信息安全與保密概論

第五章

公鑰密碼學信息安全與保密概論

第五章

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

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))知道加密算法,從加密密鑰得到解密密鑰在計算上是不可行的兩個密鑰中任何一個都可以用作加密而另一個用作解密 X=DKR(EKU(X))=EKU(DKR(X))公開密鑰密碼的重要特性加密與解密由不同的密鑰完成65基于公開密鑰的加密過程基于公開密鑰的加密過程66基于公開密鑰的鑒別過程基于公開密鑰的鑒別過程67

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

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

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

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

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

背包問題73數(shù)學基礎同余：給定任意整數(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下同余。同余關系的性質：（1）為等價關系，即具有自反性，對稱性和可傳遞性自反性：aamodm對稱性：若abmodm，則bamodm傳遞性：若abmodm且bcmodm，則acmodm數(shù)學基礎同余：74同余（2）同余式可以進行運算若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）同余式可以進行運算75同余（5）設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）設a1和a2為任意整數(shù)，op為操作符，如＋、－等，76同余（剩余）類假定m為正整數(shù)，任一整數(shù)除m得到的最小非負剩余必定為0，1，......，m-1中的一個，即任一整數(shù)對于模m必定與0，1，......，m-1中的某一個同余。因此，我們把全體整數(shù)分成若干兩兩不相交的集合，使得在同一個集合中的任意兩個數(shù)對模m同余，而屬于不同集合的兩個數(shù)對模m一定不同余。每一個這樣的集合稱作關于模m的同余類。完全剩余系從模m的每一個同余類中任取一數(shù)就得到m個數(shù)，這m個數(shù)稱作m的完全剩余系。如模4的一個完全剩余系{0，5，2，11}。通常選取的不大于m的m個非負整數(shù)集合{0，1，2，......，m-1}。同余類同余（剩余）類同余類77既約（互素）同余類和既約剩余系對于模m的同余類rmodm，如果(r,m)=1，則稱該同余類是模m的既約同余類。在模m的一個完全剩余系中，所有與m互素的數(shù)的集合構成模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的所有既約同余類的個數(shù)記為φ(m)，通常稱作Euler函數(shù)。eg.φ(5)＝4，φ(10)＝4歐拉函數(shù)既約（互素）同余類和既約剩余系歐拉函數(shù)78Euler函數(shù)和Euler定理p是素數(shù)，φ(p)=p-1若gcd(m,n)=1,則φ(mn)=φ(m)φ(n),特別地,若pq且都是素數(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是素數(shù)，φ(p)=p-179Euler定理若(a,m)=1，則aφ(m)

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

，…，axφ(m)modm}

aximodm與m互素

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

axi=axjmodmxi=xjmodn

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

(aφ(m)xi)modm

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

Fermat小定理Fermat小定理:p素數(shù),(a,p)=1,則:ap-1

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

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

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

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

1modm，所以有結論成立；

否則a必定是p或者q的倍數(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都是素數(shù),82

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

1modn定義：素數(shù)p的原根定義：如果a是素數(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是素數(shù)p的一個原根,則對任意整數(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ù)的計算:

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

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

經典例子Diffie-Hellman密鑰交換算法85

Diffie-Hellman密鑰交換允許兩個用戶可以安全地交換一個秘密信息，用于后續(xù)的通訊過程算法的安全性依賴于計算離散對數(shù)的難度素數(shù)p的原根定義：如果a是素數(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密鑰交換允許兩個用戶可以安全86Diffie-Hellman密鑰交換算法：雙方選擇素數(shù)p以及p的一個原根a用戶A選擇一個隨機數(shù)Xa<p，計算Ya=aXamodp用戶B選擇一個隨機數(shù)Xb<p，計算Yb=aXbmodp每一方保密X值，而將Y值交換給對方用戶A計算出K=YbXamodp用戶B計算出K=YaXbmodp雙方獲得一個共享密鑰(aXaXbmodp)素數(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雙方選擇素數(shù)p以及p的一個原根a(假定O知道)2A選擇Xa<p,計算Ya=aXamodp,AB:Ya3O截獲Ya,選Xo,計算Yo=aXomodp,冒充AB:Yo4B選擇Xb<p,計算Yb=aXbmodp,BA:Yb5O截獲Yb,冒充BA:Yo6A計算:(Xo)Xa(aXo)XaaXoXamodp7B計算:(Xo)Xb(aXo)XXbaXoXbmodp8O計算:(Ya)XoaXaXomodp,(Yb)XoaXbXomodpO無法計算出aXaXbmodpO永遠必須實時截獲并冒充轉發(fā),否則會被發(fā)現(xiàn)Diffie-Hellman密鑰交換的攻擊中間人攻擊90

經典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經典例子Diffie-Hellman密鑰交換算法91背包問題

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

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

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

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

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

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

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

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

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

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

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

經典例子Diffie-Hellman密鑰交換算法背包算法RSA算法

經典例子Diffie-Hellman密鑰交換算法101

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

RSA算法描述

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

分組大小為k,2k<n2k+1公開密鑰n(兩素數(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都是素數(shù),(n)=(p-1)(q-1)是n的Euler數(shù)Euler定理推論:若n=pq,pq都是素數(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都是素數(shù),(n)105

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

11(mod24),于是Bob的解密密鑰d=11.（5）Bob在一個目錄中公開n=35和e=11（6）現(xiàn)假設Alice想發(fā)送明文2給Bob，她計算：211(mod35)=2526(mod35)=32*64=32*29=928(mod35)=18，且在一個信道上發(fā)送密文18。（7）當Bob接收到密文18時，他用他的秘密解密指數(shù)（私鑰）d＝11進行解密：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)是一個單向函數(shù)，所以對攻擊的人來說求逆計算不可行。而Bob能解密的陷門是分解n=pq，知(n)=(p-1)(q-1)。從而用歐氏算法解出解密私鑰d.（猜想：攻破RSA與分解n是多項式等價的。然而，這個猜想至今沒有給出可信的證明！?。。㏑SA安全性依據(jù)RSA的安全性是基于107

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

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

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

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