本科生必修課《現代密碼學》第四章公鑰密碼內容提要4.1公鑰密碼常用知識和算法4.2公鑰密碼體制的基本概念4.3RSA算法4.4Rabin體制4.5背包體制4.6NTRU公鑰密碼系統4.7ElGamal密碼體制與DH密鑰交換4.8橢圓曲線密碼體制4.9基于身份的密碼體制4.10公鑰密碼體制的可證明安全性2/第四章公鑰密碼4.1公鑰密碼常用知識和算法一、基本數學知識群、環、域、素數模運算費爾馬定理ap-1=1modp

，p是素數歐拉函數

(n)：小于n的且與n互素的正整數個數a

(n)=1modn

素性檢驗1.愛拉托斯散篩法(Eratosthenes)依次刪去小于素數的倍數2.Miller-Rabin概率檢測法3.AKS3/第四章公鑰密碼：4.1公鑰密碼常用知識和算法歐幾里得算法、擴展歐幾里德算法求最大公約數和乘法的逆元中國剩余定理求一次同余方程組的解離散對數，本原根平方剩余計算復雜性4.1公鑰密碼常用知識和算法二、擴展歐幾里得算法，有限域上求逆元計算dmodf的逆元1.(X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);2.ifY3=0,thenreturnX3=gcd(f,d)//此時無逆元3.ifY3=1,thenreturnY3=gcd(f,d);Y2=d-1modf4.Q=

X3/Y3

5.(T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1,X2,X3)

(Y1,Y2,Y3)7.(Y1,Y2,Y3)

(T1,T2,T3)8.goto24/第四章公鑰密碼：4.1公鑰密碼常用知識和算法4.1公鑰密碼常用知識和算法三、Miller-Rabin概率檢測法，找大素數原理：若p是大于2的素數，則x2=1modp只有1和-1兩個解，所以如果方程x2=1modp有一解x0{-1,1}，那么p不為素數算法：(a<n是隨機選擇的一個數，n是待檢驗的數，返回False則一定不是素數，返回True則不一定是素數）令d=1；n-1的二進制表示為bkbk-1…b0fori=kdownto0do{

x

d;d(d

d)modn;(此時d剛好是x的平方)ifd=1andx1andxn-1thenreturnFalse;ifbi=1thend(d

a)modn;}ifd1thenreturnFalse;ReturnTrue;循環結束后有d=an-1modn，若d1，則n不是素數。x1andxn-1意指x2=1modp有不在{-1,1}中的根該測試如果進行s次，如果都是真T，則n是素數的概率最小為1-2-s5/第四章公鑰密碼：4.1公鑰密碼常用知識和算法4.1公鑰密碼常用知識和算法四、蒙哥馬利算法，避免求模運算中的除法避免求模過程中復雜耗時的除法（P.L.Montgomery,1985年提出)計算TR-1modN(1)T=(T+MN)/R(2)IFT

NreturnT-N;ELSEreturnT其中M=(TmodR)×(N-1modR)modR，且0<T<NR而且顯然有R(R-1modN)+N(N-1modR)=1+RN(R-1modN)以及(N-1modR）可預計算，R常取2的冪一般先計算TR-1modN，若R=2w，再不斷左移模N共w次可得結果6/第四章公鑰密碼：4.1公鑰密碼常用知識和算法4.1公鑰密碼常用知識和算法蒙哥馬利模乘算法計算Z=XYR-1modM輸入：X=(XNw-1,…,X0)r，Y=(YNw-1,…,Y0)r，M=(MNw-1,…,M0)r，M

=-(M0)-1modr，其中0

X,Y

M，2N-1

M2N，r=2w，gcd(M,r)=1，Nw=N/w

7/第四章公鑰密碼：4.1公鑰密碼常用知識和算法4.2公鑰密碼體制的基本概念公鑰密碼體制的出現在密碼學史上是一個最大的而且是惟一真正的革命。為密碼學發展提供了新的理論和技術基礎公鑰密碼算法基本工具不再是代換和置換，而是數學函數以非對稱的形式使用兩個密鑰，兩個密鑰的使用對保密性、密鑰分配、認證等都有著深刻的意義。公鑰密碼體制的概念是在解決單鑰密碼體制中最難解決的兩個問題時提出的，即密鑰分配和數字簽字8/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2公鑰密碼體制的基本概念對稱密碼算法的缺陷密鑰分配問題：通信雙方加密通信前要通過秘密的安全信道協商加密密鑰，這種安全信道可能很難實現；對這個信道安全性的要求比正常傳送消息信道的安全性要高密鑰管理問題：在多用戶網絡中，任何兩個用戶之間都需要有共享的秘密鑰，n個用戶需要Cn2=n(n-1)/2個密鑰，n=5000時，Cn2=12,497,500，系統開銷非常大沒有簽名功能：當主體A收到主體B的電子文擋時，無法向第三方證明此電子文檔確實來源于B，傳統單鑰加密算法無法實現抗抵賴的需求9/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2公鑰密碼體制的基本概念公鑰密碼的主要作用公鑰加密用于加密任何消息，象分組密碼一樣使用任何人可以用公鑰加密消息，私鑰的擁有者可以解密消息數字簽名(DigitalSignature)用于生成對某消息的數字簽名私鑰的擁有者生成數字簽名，任何人可以用公鑰驗證簽名簽名時可將公鑰加密算法逆用來實現，也可單獨設計公鑰簽名算法基于公鑰的密鑰分配(KeyDistribution)用于交換秘密信息，常用于協商對稱加密算法的密鑰可采用公鑰加密的算法實現密鑰分配也可使用單獨設計的密鑰交換算法，如DH密鑰交換協議實現密鑰分配參考資料：ArtoSalomaa《公鑰密碼學》芬蘭，等10/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2公鑰密碼體制的基本概念公鑰密碼算法的最大特點是采用兩個相關密鑰將加密和解密能力分開一個密鑰是公開的，稱為公開密鑰，簡稱公開鑰，用于加密、驗證簽名，可以被任何人知道另一個密鑰是為用戶專用，因而是保密的，只能被消息的接收者或簽名者知道，稱為秘密密鑰，簡稱秘密鑰，用于解密、產生簽名因此公鑰密碼體制也稱為雙鑰密碼體制算法有以下重要特性：已知密碼算法和加密密鑰，求解密密鑰在計算上是不可行的因此加密和簽名的驗證者不能解密和生成簽名11/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.1公鑰密碼體制的原理公鑰體制的加密過程①密鑰的產生：要求接收消息的端系統，產生一對用來加密和解密的密鑰PKB和SKB，如圖中的接收者B，其中PKB是公開鑰，SKB是秘密鑰。因此，公鑰可以發布給其他人②公開鑰的分發：B將加密密鑰(PKB)予以公開。另一密鑰則被保密(SKB)③加密：A要想向B發送消息m，則使用B的公開鑰加密m，表示為c=EPKB[m]其中c是密文，E是加密算法④解密：B收到密文c后，用自己的秘密鑰SKB解密，即m=DSKB[c]，其中D是解密算法。因為只有B知道SKB，所以其他人都無法對c解密。12/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.1公鑰密碼體制的原理公鑰體制的認證過程公鑰加密不僅能用于加、解密，還能用于對發方A發送的消息m提供認證用戶A用自己的秘密鑰SKA對m加密，表示為c=ESKA[m]將c發往B。B用A的公開鑰PKA對c解密，表示為m=DPKA[c]因為從m得到c是經過A的秘密鑰SKA加密，只有A才能做到。因此c可當做A對m的數字簽字。任何人只要得不到A的秘密鑰SKA就不能篡改m，所以以上過程獲得了對消息來源和消息完整性的認證，也實現了對身份的認證。13/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.1公鑰密碼體制的原理認證符：通過單向壓縮函數(hash)解決長文件的簽字公鑰密碼算法實質上是一種分組密碼算法，但公鑰密碼算法運算復雜、速度很慢，而且對明文的加密和簽名的結果存在很大的數據擴展，因此這對于長文件來說直接使用不可行改進的方法是減小文件的數字簽字的大小，即先將文件經過一個函數壓縮成長度較小的比特串，得到的比特串稱為認證符，然后對認證符進行處理認證符具有這樣一個性質：如果保持認證符的值不變而修改文件，在計算上是不可行的簽名過程中，往往用發送者的秘密鑰對認證符加密，加密后的結果為原文件的數字簽字。(詳見第7章)14/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.1公鑰密碼體制的原理公鑰體制同時提供加密和認證的過程為了同時提供認證功能和保密性，可使用雙重加、解密先簽名后加密：發方首先用自己的秘密鑰SKA對消息m加密，用于提供數字簽字。再用收方的公開鑰PKB第2次加密，表示為c=EPKB[ESKA[m]]先解密再驗證：收方的解密過程為m=DPKA[DSKB[c]]先加密后簽名是不安全的，別人可以先將簽名去掉，再簽上自己的簽名，從而實現了篡改，謊稱是自己產生了該密文消息。單純的先簽名再加密有時也不安全，收方解密出簽名的消息后，再用其他人公鑰加密發給其他人，從而實現冒充簽名者發送消息給其它任何人，因此簽字中還應該有收方的ID15/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.2公鑰密碼算法應滿足的要求公鑰密碼算法應滿足以下要求①收方B產生密鑰對（公開鑰PKB和秘密鑰SKB）在計算上是容易的。由私鑰及其他密碼信息容易計算出公開密鑰(P問題)②發方A用收方的公開鑰對消息m加密以產生密文c，即c=EPKB[m]在計算上是容易的③收方B用自己的秘密鑰對c解密，即m=DSKB[c]在計算上是容易的④敵手由B的公開鑰PKB求秘密鑰SKB在計算上是不可行的⑤敵手由密文c和B的公開鑰PKB恢復明文m在計算上是不可行的⑥加、解密次序可換，即EPKB[DSKB(m)]=DSKB[EPKB(m)]其中最后一條雖然非常有用，但不是對所有的算法都作要求。在構建盲簽字等算法時需要類似要求以上要求的本質之處在于要求一個陷門單向函數。16/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.2公鑰密碼算法應滿足的要求單向函數兩個集合X、Y之間的一個映射，使得Y中每一元素y都有惟一的一個原像x∈X，且由x易于計算它的像y，由y計算它的原像x是不可行的“易于計算”是指函數值能在其輸入長度n的多項式時間內求出，即求函數值的計算時間復雜度O(na),其中a是一固定的常數這時稱求函數值的算法屬于多項式類P，否則就是不可行的，例如，函數的輸入是n比特，如果求函數值所用的時間是2n的某個倍數，則認為求函數值是不可行的。易于計算和不可行兩個概念與計算復雜性理論中復雜度的概念極為相似，然而又存在著本質的區別在復雜性理論中，算法的復雜度是以算法在最壞情況或平均情況時的復雜度來度量的。這時可能對某些情況很容易求解，復雜度很低而在此所說的兩個概念是指算法在幾乎所有情況下的情形17/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.2公鑰密碼算法應滿足的要求陷門單向函數稱一個函數是陷門單向函數，是指該函數是易于計算的，但求它的逆是不可行的，除非再已知某些附加信息。當附加信息給定后，求逆可在多項式時間完成總結為：陷門單向函數是一族可逆函數fk，滿足①當k和X已知時，Y=fk(X)易于計算②當k和Y已知時，X=fk-1(Y)易于計算③當Y已知但k未知時，X=fk-1(Y)計算上是不可行的研究公鑰密碼算法就是要找出合適的陷門單向函數18/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.2公鑰密碼算法應滿足的要求用于構造單向陷門函數的典型困難問題及算法RSA(基于大數分解困難問題)RSA系列算法，Rabin體制DLP(基于求解有限域上離散對數困難問題)ElGamal加密體制，DH密鑰交換ECC(橢圓曲線離散對數問題)ECC上雙線性對，ECC上基于身份的密碼體制基于格的概率加密體制(基于求解格上最短向量等問題)NTRU…基于糾錯碼的體制McElice…背包體制19/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.2公鑰密碼算法應滿足的要求量子公鑰密碼基于量子編碼、量子不可克隆定理、子集和問題等困難性的公鑰密碼算法，但是目前這些問題的困難性也受到質疑后量子密碼學post-quantumcryptography量子計算具有內在并行性，能攻破RSA、離散對數、ECC等體制06年在比利時魯汶天主教大學召開了第一次后量子密碼學國際會議DanielJ.Bernstein,JohannesBuchmann,ErikDahmen,“Post-QuantumCryptography,”Springer-Verlag,pp.245,2009.幾種量子計算尚不能征服的密碼體制基于Hash的密碼（Hash-basedcryptography）如Merkle于1979年提出的hash樹公鑰簽名體制，按Lamport和Diffie的單消息簽名概念構建的20/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.2公鑰密碼算法應滿足的要求基于編碼（糾錯碼）的密碼（Code-basedcryptography）如McEliece1978年提出的隱Goppa碼公鑰加密體制。王新梅教授提出的新梅算法基于格的密碼（Lattice-basedcryptography）Hoffstein-Pipher-Silverman于1998年提出的“NTRU”公鑰加密體制，雖不是第一個，但為最引人注目的一個多變量二次方程密碼（Multivariate-quadratic-equationscryptography)如Patarin于1996年提出的“HFEv-”公鑰簽名體制就是幾個重要例子中的一個，此例后為Matsumoto和Imai所推廣秘密（單）鑰密碼（Secret-keycryptography）如高級數據加密標準AES21/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.3對公鑰密碼體制的攻擊以下討論的攻擊是指對所有公鑰密碼體制都有效的平凡的攻擊涉及到公鑰算法所基于的困難問題的安全性和參數空間大小的安全性第一種平凡的攻擊：（窮搜索攻擊與密鑰長度）如果密鑰太短，公鑰密碼體制也易受到窮搜索攻擊然而又由于公鑰密碼體制所使用的可逆函數的計算復雜性與密鑰長度常常不是呈線性關系，而是增大得更快。所以密鑰長度太大又會使得加解密運算太慢而不實用因此公鑰密碼體制目前主要用于密鑰管理和數字簽字。即處理短消息如密鑰和hash值22/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.2.3對公鑰密碼體制的攻擊第二種平凡的攻擊是尋找從公開鑰計算秘密鑰的方法目前為止，對常用公鑰算法還都未能夠證明這種攻擊是不可行的第三種平凡的攻擊：(可能字攻擊)僅適用于對公鑰密碼算法的攻擊例如對56比特的DES密鑰用公鑰密碼算法加密后發送，敵手用算法的公開鑰對所有可能的密鑰加密后與截獲的密文相比較如果一樣，則相應的明文即DES密鑰就被找出。因此不管公鑰算法的密鑰多長，攻擊的本質是對56比特DES密鑰的窮搜索攻擊抵抗方法是在欲發送的明文消息后添加一些隨機比特不同的公鑰密碼算法在設計和實現中的密碼協議是影響安全性的主要方面，不同算法的攻擊不同。公鑰的安全性是指計算上的安全性23/第四章公鑰密碼：4.2公鑰密碼體制的基本概念4.3RSA算法從本節開始，我們介紹分別介紹基于不同困難問題的公鑰密碼體制，這些體制在實際中都是不安全的，實用的體制都是在這些基本原型基礎上進行了較大的修改而設計的。但這些體制會啟發我們如何根據不同的數學困難問題構造陷門單向函數，并進而構造公鑰密碼算法1978年由R.Rivest,A.Shamir和L.Adleman提出的一種用數論構造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制，已得到廣泛的應用RLRivest,AShamir,LAdleman,"OnDigitalSignaturesandPublicKeyCryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb.1978它既可用于加密、又可用于數字簽字。RSA算法的安全性是基于數論中大整數分解的困難性(但可能達不到大數分解的困難強度)IEEEP1363公鑰密碼標準24/第四章公鑰密碼：4.3RSA算法4.3.1算法描述1．密鑰的產生①選兩個保密的大素數p和q②計算n=p×q，

(n)=(p-1)(q-1)，其中

(n)是n的歐拉函數值③選一整數e，滿足1<e<

(n)，且gcd(

(n),e)=1④計算d，滿足d·e≡1mod

(n)，即d是e在模

(n)下的乘法逆元，因e與

(n)互素，模

(n)的乘法逆元一定存在⑤以{e,n}為公開鑰,{d,p,q}為秘密鑰秘密鑰也可記為d，或{d,n}，如果是系統負責產生密鑰，則用戶可能不知道p,q25/第四章公鑰密碼：4.3RSA算法4.3.1算法描述2．加密加密時首先將明文比特串分組，使得每個分組對應的十進制數小于n，即分組長度小于log2n。然后對每個明文分組m，作加密運算：

c≡memodn3．解密對密文分組的解密運算為：

m≡cdmodnRSA的模很長，如模n為1024比特的RSA一次加密約1024比特明文，相當于16次DES加密，但一次RSA比16次DES要慢很多，不在一個數量級上），所以公鑰密碼算法不適合加密長消息26/第四章公鑰密碼：4.3RSA算法4.3.1算法描述RSA算法中解密過程的正確性證明證明：由c≡memodn，可知cd

modn≡medmodn≡mk

(n)+1modn下面分兩種情況：①

m與n互素，則由Euler定理得m

(n)≡1modn，mk

(n)≡1modn，mk

(n)+1≡mmodn,即cdmodn≡m②gcd(m,n)≠1，因n=pq，所以m是p的倍數或q的倍數，不妨設m=cp，其中c為一正整數。此時必有gcd(m,q)=1，否則m也是q的倍數，從而是pq的倍數，與m<n=pq矛盾。由gcd(m,q)=1及Euler定理得m

(q)≡1modq，所以mk

(q)≡1modq，(mk

(q))

(p)≡1modq，即mk

(n)≡1modq因此存在一整數r，使得mk

(n)＝1+rq，兩邊同乘以m=cp得mk

(n)＋1＝m+rcpq＝m+rcn即mk

(n)＋1＝mmodn，所以cdmodn≡m。(證畢)27/第四章公鑰密碼：4.3RSA算法4.3.2RSA算法中的計算問題1.RSA的加密與解密過程①模運算的累次乘法RSA的加密、解密過程都為求一個整數的整數次冪，再取模如果按其含義直接計算，則中間結果非常大，有可能超出計算機所允許的整數取值范圍。如計算6677mod119，先求6677再取模，則中間結果就已遠遠超出了計算機允許的整數取值范圍。用模運算的性質：即采用累次乘法，可減小中間結果(a×b)modn=[(amodn)×(bmodn)]modn28/第四章公鑰密碼：4.3RSA算法4.3.2RSA算法中的計算問題③快速指數算法考慮如何提高加、解密運算中模指數運算的有效性。例如求x16，直接計算需做15次乘法。若重復對每個部分結果做平方運算即求x，x2，x4，x8，x16則只需4次乘法求am可如下進行，其中a，m是正整數：將m表示為二進制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此am＝例如：19=1×24+0×23+0×22+1×21+1×20，所以a19=((((a1)2a0)2a0)2a1)2a129/第四章公鑰密碼：4.3RSA算法4.3.2RSA算法中的計算問題快速指數算法：計算am

modnc=0;

d=1；fori=kdownto0do{

c=2×c;//僅為驗證以上過程，而在具體算法中可刪去

d=(d×d)modn;//計算平方

ifbi=1then{

c=c+1;//僅為驗證以上過程，而在具體算法中可刪去

d=(d×a)modn//bi=1時與a相乘

}}returnd.其中d是中間結果，d的終值即為所求結果。c的終值為指數m30/第四章公鑰密碼：4.3RSA算法4.3.2RSA算法中的計算問題計算復雜度:l＋W(m)-2次模乘（m為模指數）l為指數的bit長，W(m)為指數m的重量(二進制比特1的個數)T進制快速模指數算法：求am可如下進行：將m表示為T進制形式bkbk-1…b0，即m=bkTk+bk-1Tk-1+…+b1T+b0取T=2wam=首先預計算出aimodn，其中i=1,2，…，2w-1再用快速模指數運算w的選擇與預計算需要的存儲空間有關31/第四章公鑰密碼：4.3RSA算法32/④一種改進的RSA實現方法(即4.3.3節）

RSA的加密很快，因為加密指數e一般選擇得很小解密指數d很大，需要計算模300digits(or1024bits)的乘法，計算機不能直接處理這么大的數，計算速度很慢，需要考慮其它技術，加速RSA的實現如果知道p和q，可采用中國剩余定理CRT：CRT對RSA解密算法生成兩個解密方程（利用M=CdmodN，N=pq）即：M1=Mmodp=(Cmodp)d

mod(p-1)modp

M2=Mmodq=(Cmodq)dmod(q-1)modq解方程M=M1modp

M=M2modq

具有唯一解（利用CRT）：

M=M1×q×(q－1modp)+M2×p×(p－1modq)modN不考慮CRT的計算代價，改進的算法的解密速度是原來的4倍若考慮CRT的計算代價，改進后的算法解密速度是原來的3倍多4.3.2RSA算法中的計算問題2.RSA密鑰的產生需考慮兩個大素數p、q的選取，以及e的選取和d的計算n(=pq)是公開的，為了防止敵手通過窮搜索發現p、q，這兩個素數應足夠大，且具有好的隨機性(1)如何有效地尋找大素數一般是先隨機選取一個大的奇數（例如用偽隨機數產生器），然后用素性檢驗算法檢驗這一奇數是否為素數，如果不是則選取另一大奇數，重復這一過程，直到找到素數為止素性檢驗算法通常都是概率性的，常用Miller-Rabin概率檢測算法實現，只有在產生新密鑰時才需執行這一工作(2)如何選取滿足gcd(

(n),e)=1的e，并計算滿足d·e≡1mod

(n)的d這一問題可由推廣的Euclid算法完成33/第四章公鑰密碼：4.3RSA算法4.3.3RSA的安全性一.平凡攻擊下的安全性(1)大整數分解問題RSA的安全性是基于大整數分解的困難性假定，至今還未能證明分解大整數就是NP問題，也許有尚未發現的多項式時間分解算法隨著計算能力不斷提高，被分解的大數越來越大例如RSA-129（即n為129位十進制數，大約428個比特）已在網絡上通過分布式計算歷時8個月于1994年4月被成功分解，RSA-155（512bit）已于1999年8月被成功分解，RSA-158，2002年被成功分解，現在768比特的模值已經不安全對于大整數的威脅除了人類的計算能力外，還來自分解算法的進一步改進，已知的各種算法的漸近運行時間約為：試除法：n/2；二次篩(QS)：橢圓曲線(EC)：

，數域篩(NFS)：34/第四章公鑰密碼：4.3RSA算法512bitRSA只能提供60比特的安全性4.3.3RSA的安全性將來也可能還有更好的分解算法量子計算如果成功的話，可解決大整數分解問題估計在未來一段比較長的時期，密鑰長度介于1024比特至2048比特之間的RSA是安全的(2)用于產生大素數的隨機數必須是不可預測的，即密碼上是安全的特別的如果要生成多個大素數，這一要求尤為重要，因為敵手可能會猜測隨機數，進而獲得可能的素數要求產生大素數的隨機數采用安全性能良好的偽隨機數產生器，在引入一些真隨機因素，如時間、鍵盤敲擊記錄等(3)由n直接確定φ(n)等價于對n的分解由RSA密鑰產生容易推出p+q=n－

(n)+1；以及35/第四章公鑰密碼：4.3RSA算法由此可見，由p、q確定

(n)和由

(n)確定p、q是等價的4.3.3RSA的安全性(4)研究表明，如果e<n且d<n1/4，則d能被容易地確定D.Boneh證明了RSA中私有密鑰長度小于ｎ0.292時方案容易被攻破(5)對p和q提出以下要求1)|p-q|要大由(p+q)2/4－n=(p+q)2/4－pq=(p－q)2/4，如果|p-q|小，則(p－q)2/4也小，因此(p+q)2/4稍大于n，(p+q)/2稍大于n1/2。可得n的如下分解步驟：①順序檢查大于n1/2的每一整數x，直到找到一個x使得x2-n是某一整數（記為y）的平方。②由x2-n=y2，得n=(x+y)(x-y)。2)p-1和q-1都應有大素因子(強素數)這是因為RSA算法存在著可能的重復加密攻擊法36/第四章公鑰密碼：4.3RSA算法4.3.3RSA的安全性(6)重復加密攻擊設攻擊者截獲密文c，可如下進行重復加密：

，…,若，則有，即，所以重復加密的倒數第2步就已恢復出明文m

t較小時攻擊是可行的。為抵抗這種攻擊，p、q的選取應保證使t很大。設m在模n下階為k，由得，所以k|(et-1)，即et≡1(modk)，t取為滿足前式的最小值（為e在模k下的階）。又當e與k互素時t|

(k)。為使t大，k就應大且

(k)應有大的素因子。又由k|

(n)，所以為使k大，p-1和q-1都應有大的素因子37/第四章公鑰密碼：4.3RSA算法4.3.3RSA的安全性二、

參數選擇不當引起的兩類攻擊，并非算法本身缺陷(1)共模攻擊在實現RSA時，為方便起見，可能給每一用戶相同的模數n，雖然加解密密鑰不同，然而這樣做是不行的設兩個用戶的公開鑰分別為e1和e2，且e1和e2互素（一般情況都成立），明文消息是m，密文分別是

c1≡me1(modn)

c2≡me2(modn)敵手截獲c1和c2后，可如下恢復m。用推廣的Euclid算法求出滿足re1+se2=1的兩個整數r和s，其中一個為負，設為r。再次用推廣的Euclid算法求出c1-1，由此得(c1-1)-rc2s≡m(modn)。38/第四章公鑰密碼：4.3RSA算法4.3.3RSA的安全性(2)低指數攻擊假定將RSA算法同時用于多個用戶（以下假定3個），然而每個用戶的加密指數（即公開鑰）都很小。設3個用戶的模數分別為ni(i=1,2,3)，當i≠j時，gcd(ni,nj)=1，否則通過gcd(ni,nj)有可能得出ni和nj的分解。設明文消息是m，加密指數e＝3，密文分別是:c1≡m3(modn1)c2≡m3(modn2)c3≡m3(modn3)由中國剩余定理可求出m3(modn1n2n3)。由于m3<n1n2n3，可直接由m3開立方根得到m。最初建議使用e=3，不安全，e是有下限的39/第四章公鑰密碼：4.3RSA算法4.3.3RSA的安全性三、RSA體制的同態攻擊根據RSA加密算法，如果c1=m1emodn；c2=m2emodn那么我們構造密文c1

c2其對應的明文剛好是m1

m2這種性質就稱為同態特性。攻擊者在不知道兩個明文的情況下，完成了兩個明文乘積的加密然而這種攻擊對于今天的云計算而言，確是一個很好的性質，計算方在不知道明文的情況下仍舊可以對明文進行處理抵抗這種攻擊的方法是對加密的明文再填加一個驗證符，從而抵消同態特性，在實際的加密中為了有效增大明文空間，并消除明文泄露，還要填充一定長度的隨機數。這既是概率加密40/第四章公鑰密碼：4.3RSA算法4.3.3RSA的安全性三、RSA體制的同態攻擊根據RSA加密算法，如果c1=m1emodn；c2=m2emodn那么我們構造密文c1

c2其對應的明文剛好是m1

m2這種性質就稱為同態特性。攻擊者在不知道兩個明文的情況下，完成了兩個明文乘積的加密然而這種攻擊對于今天的云計算而言，確是一個很好的性質，計算方在不知道明文的情況下仍舊可以對明文進行處理抵抗這種攻擊的方法是對加密的明文再填加一個驗證符，從而抵消同態特性，在實際的加密中為了有效增大明文空間，并消除明文泄露，還要填充一定長度的隨機數。這既是概率加密41/第四章公鑰密碼：4.3RSA算法4.3.3RSA的安全性概率加密體制1982年，ShafiGoldwasser和SilvioMicali提出了概率加密(ProbabilisticEncryption)的概念,基本思想是使公鑰體制的信息泄露為0,其相應的密碼體制稱作概率加密公鑰體制(ProbabilisticEncryptionCryptosystem)，簡稱PEC。概率加密公鑰體制具有多項式安全性。一個明文在加密后得到的密文是一個隨機變量42/第四章公鑰密碼：4.3RSA算法4.3.4RSA-OAEP算法隨機預言機模型下安全的RSA算法最佳非對稱加密填充（OAEP）是一個通常和RSA一起使用的填充方案。OAEP由Bellare和Rogaway

提出的43/第四章公鑰密碼：4.3RSA算法4.4Rabin密碼體制RSA密碼體制破譯RSA的難度不超過大整數的分解。但還不能證明破譯RSA和分解大整數是等價的，雖然這一結論已得到普遍共識Rabin密碼體制已被證明對該體制的破譯等價于對大整數的分解RSA中選取的公開鑰e滿足1<e<

(n)，且gcd(e,

(n))=1。Rabin密碼體制則取e=21.密鑰的產生隨機選擇兩個大素數p、q，滿足p≡q≡3mod4，Blum數，即這兩個素數形式為4k+3；計算n=p×q。以n作為公開鑰，p、q作為秘密鑰。2.加密：c≡m2modn

其中m是明文分組，c是對應的密文分組。3.解密解密就是求c模n的平方根，即解x2≡cmodn，因此，Rabin體制也被稱為基于環上二次剩余困難性構造，由中國剩余定理知解該方程等價于解方程組44/第四章公鑰密碼：4.4Rabin密碼體制4.4Rabin密碼體制由于p≡q≡3mod4，方程組的解可容易地求出，其中每個方程都有兩個解，即x≡

m1modp，

x≡

m2modq，經過組合可得4個同余方程組，，，由中國剩余定理可解出每一方程組的解，共有4個，即每一密文對應的明文不惟一。為了有效地確定明文,可在m中加入某些信息,如發送者的身份號、接收者的身份號、日期、時間等。當p≡q≡3mod4時，兩個方程的平方根

m1

、

m2易于求出因c是模p的平方剩余，故≡c(p-1)/2≡1modp，易于驗證

即為方程x2≡cmodp的兩個根，同理

即為方程x2≡cmodq的兩個平方根45/第四章公鑰密碼：4.4Rabin密碼體制4.4Rabin密碼體制由以前知識知，求解方程x2≡amodn與分解n是等價的，所以破譯Rabin密碼體制的困難程度等價于大整數n的分解。Rabin密碼在選擇密文攻擊CCA下是不安全的。二次剩余有四個根分成兩組

m1

和

m2，如果每組中分別獲得一個，則可分解模n，這是因為m12=m22modn，即m12-m22=kn，從而gcd(m1-m2,n)應該恢復p和q其中的一個如果敵手控制解密機，那么隨機選一個x加密后給解密機，解密機解密出x

返回，若x

x則完成了攻擊和RSA一樣，安全的Rabin算法也必須對消息進行padding明文消息空間太小時，消息需要填充46/第四章公鑰密碼：4.4Rabin密碼體制4.5背包密碼體制設A=(a1,a2,…,an)是由n個不同的正整數構成的n元組，s是另一已知的正整數。背包問題就是從A中求出所有的ai，使其和等于s。其中A稱為背包向量，s是背包的容積。例如,A=(43,129,215,473,903,302,561,1165,697,1523)，s=3231。由于3231=129+473+903+561+1165所以從A中找出的滿足要求的數有129、473、903、561、1165原則上講，通過檢查A的所有子集，總可找出問題的解（若有解的話）本例A的子集共有210=1024個（包括空集）。然而如果A中元素個數n很大，子集個數2n將非常大。如A中有300個元素，A的子集有2300。尋找滿足要求的A的子集沒有比窮搜索更好的算法，因此背包問題(

Knapsack)是NPC問題。47/第四章公鑰密碼：4.5背包密碼體制4.5背包密碼體制由背包問題構造公鑰密碼體制同樣是要構造一個(陷門)單向函數f將x(1≤x≤2n-1)寫成長為n的二元表示,f(x)定義為A中所有ai的和，其中x的二元表示的第i位為1，即f(1)=f(0…001)=an;f(2)=f(0…010)=an-1;f(3)=f(0…011)=an-1+an…f(2n-1)=f(1…111)=a1+a2+…+an使用向量乘(內積)，有f(x)=A·Bx，其中Bx是x二元表示的列向量。上例中f(364)=f(0101101100)=129+473+903+561+1165=3231顯然，已知x很容易求f(x)，但已知f(x)求x就是要解背包問題。為使接收方能夠解密，就需找出單向函數f(x)的陷門。為此需引入一種特殊類型的背包向量。48/第四章公鑰密碼：4.5背包密碼體制4.5背包密碼體制定義背包向量A=(a1,a2,…,an)稱為超遞增的，如果，j＝1,2,…,n超遞增背包向量對應的背包問題很容易通過以下算法求解。已知s為背包容積，對A從右向左檢查每一元素，以確定是否在解中。若s≥an，則an在解中，令xn=1；若s<an，則an不在解中，令xn=0。下面令s＝對an-1重復上述過程，一直下去，直到檢查出a1是否在解中。檢查結束后得x=(x1x2…xn)，Bx=(x1x2…xn)T49/第四章公鑰密碼：4.5背包密碼體制4.5背包密碼體制基于背包問題構造公鑰密碼體制1.密鑰產生選一個超遞增背包向量A=(a1,a2,…,an)用模乘對A進行偽裝，模乘的模數k和乘數t皆取為常量，滿足，gcd(t,k)=1，即t在模k下有乘法逆元。設bi≡t·aimodk,i=1,2,…,n，得一新的背包向量B=(b1,b2,…,bn)，記為B≡t·Amodk用戶以B作為自己的公開鑰，A,t,k為私鑰2.加密對明文分組x=(x1x2…xn)的加密運算為c=f(x)=B·Bxmodk50/第四章公鑰密碼：4.5背包密碼體制4.5背包密碼體制3.解密首先由s≡t-1cmodk，求出s作為超遞增背包向量A的容積，再由超遞增背包向量A解背包問題即得x=(x1x2…xn)。這是因為t-1cmodk≡t-1tABxmodk≡ABxmodk，而由，知ABx<k，所以t-1cmodk=ABx是惟一的。背包密碼體制是Diffie和Hellman1976年提出公鑰密碼體制的設想后的第一個公鑰密碼體制，由Merkle和Hellman1978年提出。它表示了如何將NP完全問題用于公開密鑰算法。然而又過了兩年該體制即被破譯破譯的基本思想是不必找出正確的模數k和乘數t（即陷門信息），只須找出任意模數k′和乘數t′，使得用k′和t′去乘公開的背包向量B時，能夠產生超遞增的背包向量即可51/第四章公鑰密碼：4.5背包密碼體制4.6.1NTRU密碼體制NTRU是一種環上基于格的公鑰密碼系統，由JeffreyHoffstein等人在1998年提出密鑰短且容易產生，算法的運算速度快，所需存儲空間小。系統建立在整系數多項式環上（＋Abel群，×半群，可分配）。設R表示最高次數不超過N－1的所有整系數多項式集合設a＝a0+a1x+…+aN－1xN－1,b＝a0+b1x+…+bN－1xN－1是R上兩個元素R上的加法定義為a+b＝(a0+b0)+(a1+b1)x+…+(aN-1+bN-1)xN－1,R上的乘法定義為a*b＝c0+c1x+…+cN-1xN－1其中k階系數ck＝a0bk+a1bk-1+…+akb0+ak+1bN-1+ak+2bN-2+…+aN-1bk+1

＝算法的參數參數包括3個整數(N,p,q)和4個次數為N-1的整系數多項式集合Lf,Lg,L

,Lm，其中p是小的奇素數，但滿足gcd(p,q)=1，且q>2p(modq)和(modp)運算的結果分別限制在區間(-q/2,q/2]和(-p/2,p/2]內52/第四章公鑰密碼：4.6NTRU公鑰密碼系統4.6.1NTRU密碼體制1.密鑰的產生隨機選取兩個多項式f,g

Lg，它們的系數均屬于{0,±1}，其中多項式f在(modq,modxN-1)和(modp,modxN-1)均可逆，其逆元分別表示為Fq和Fp，即：Fq*f=1modq

和Fp*f=1modp。計算h＝Fq*gmodq，以h為公鑰，f和g作為秘密鑰，接收方同時還需保存Fp2.加密設發送方欲將消息m

Lm發送給接收方，可對m作如下加密：隨機選取多項式

L

，用公鑰h對消息進行加密e＝p*h+m(modq,modxN-1)將e發送給接收方。53/第四章公鑰密碼：4.6NTRU公鑰密碼系統4.6.1NTRU密碼體制4.解密接收方收到e后，使用秘密鑰f對其作如下解密。①首先計算a=f*e(modq),a的系數選在-q/2到q/2之間.②將a作為一個整系數多項式，計算Fp*a(modp)即可恢復明文m解密原理：a=f*e＝f*p*h+f*m(modq)

＝f*p*Fq*g

+f*m(modq)

＝p*g

+f*m(modq)

＝p*g

+f*m

最后一步是由于若選擇的參數合適，可保證多項式p*g

+f*m的系數在-q/2到q/2之間，而無modq，所以對p*g

+f*m模q運算后結果不變而Fp*a＝Fp*p*g

+Fp*f*m(modp)＝m(modp)當然也可能因為系數沒控制在-q/2到q/2之間而解密失敗54/第四章公鑰密碼：4.6NTRU公鑰密碼系統4.6.2NTRU的安全性一、若f和pg的系數絕對值之和不超過(q-1)/p，則對任何明文m(x)都保證：pgr(x)+f(x)m(x)(modxN-1)的每個系數都不超出區間(-q/2,q/2]二、一般，f(x)和pg(x)的系數恰當地設計，可以對絕大多數明文m(x)都保證：p*g

+f*m

(modxN-1)的每個系數都不超出區間(-q/2,q/2]。對于公鑰h，如果s

L

滿足t=h*s(modq,modxN-1)，且多項式pt*+s*m(modxN-1)的每個系數都在區間(-q/2,q/2]內，則此{t,s}就是能夠將此{

,m}進行解密的一個局部有效私鑰。這是因為h=t*s-1(modq,modxN-1)，因此，e=p*h+m(modq,modxN-1)；a=s*e=pt*+s*m(modq,modxN-1)；=pt*+s*m(modxN-1)；//上式系數都在(-q/2,q/2]內，所以無modq進而有s-1*a(modp,modxN-1)=s-1*s*m(modp,modxN-1)=m55/第四章公鑰密碼：4.6NTRU公鑰密碼系統4.6.2NTRU的安全性當{t,s}的尺寸比較小時，就可能有{

,m}使pt*+s*m(modxN-1)的每個系數都在區間(-q/2,q/2]內，因而{t,s}能作為有效私鑰對{

,m}成功解密{t,s}的尺寸越較小，{t,s}能夠成功解密的{

,m}越多。尋找滿足方程t=h*s(modq,modxN-1)、且尺寸足夠小的{t,s}是攻破NTRU的關鍵。方程t=h*s(modq,modxN-1)的全部解{t,s}構成了一個格，稱為CS格。真正的私鑰{g,f}屬于此CS格。CS格歸約被用來尋找“尺寸”足夠小的{t,s}，來作為NTRU的有效私鑰或局部有效私鑰。CS格歸約的方法主要是LLL算法和各種改進算法只要N足夠大（N≥251），在當前CS格歸約還不能成功。格的定義若干個N維向量組成的集合，如果滿足“集合中任何若干個向量的整數線性組合仍是集合中的一個向量。”則該結合稱為一個格。56/第四章公鑰密碼：4.6NTRU公鑰密碼系統4.6.2NTRU的安全性格的最小向量問題(SVP)關于格有以下的性質和概念。如果格中存在這樣的幾個向量，滿足①它們（實數）線性無關；②格中的任何其它向量都能唯一地表示為這幾個向量的整數線性組合。則這幾個向量構成的向量組稱為基。基中的向量的個數稱為格的維數。格的維數總是不超過N。給定一個格的一組基。尋找格中的“尺寸最小”的向量（即模最小的向量），稱為格的最小向量問題（shortestvectorproblem；SVP）。又稱為格歸約實際上，格歸約的傳統算法為LLL算法，以后又有各種改進的算法。當格的維數比較大時（比如，維數大于200），當前的所有格歸約算法都不是有效算法。57/第四章公鑰密碼：4.6NTRU公鑰密碼系統4.7.1離散對數問題及其困難性有限域GF(p)上的離散對數問題若已知y，g，p，求x滿足y=gxmodp，稱為求解離散對數問題。記為x=loggymodp。求解離散對數問題的“最笨的方法”當然就是窮舉，運算次數約為(p－1)/2。許多求解離散對數問題的算法比窮舉快得多，比如Shanks算法，Pohlig-Hellman算法等。最快求解法的運算次數約為數量級這個計算量稱為亞指數計算量，當log2p≈1024時，亞指數計算量不小于2100數量級，因此是安全的如果p-1不含大素因子，很多情況下也是容易計算的，這時x=xmodp-1,如果都是小因子，則可分別求出模小因子，再用CRT定理。58/第四章公鑰密碼：4.7ElGamal密碼體制與DH密鑰交換4.7.2ElGamal密碼體制1.密鑰產生選擇一個大的素數p；選擇g，1<g<p；選擇x，1<x<p-1；計算y=gxmodp，公鑰是(p,g,y)，私鑰是x2.加密設欲加密明文消息M，0<M<p隨機選一整數k,滿足gcd(k,p－1)=1計算對C1≡gkmodp,C2≡ykMmodp，密文為C=C1||C2(級聯)3.解密M=C2/C1xmodp

這是因為C2/C1xmodp＝ykM/gkxmodp＝ykM/ykmodp＝Mmodp

特點：密文由明文和所選隨機數k來定，因而是一種概率加密體制，代價是使數據擴展一倍59/第四章公鑰密碼：4.7ElGamal密碼體制與DH密鑰交換4.7.3Diffie-Hellman密鑰交換ElGamal加密體制的本質是使用了DH密鑰交換技術DH密鑰交換是W.Diffie和M.Hellman于1976年提出的第一個公鑰密碼算法，已在很多商業產品中得以應用算法的唯一目的是使得兩個用戶能夠安全地交換密鑰，得到一個共享地會話密鑰，算法本身不能用于加、解密算法的安全性基于求離散對數的困難性假設p是大素數，g是p的本原根，p和g作為公開元素，協議如下：①用戶Alice選擇隨機數x，計算a=gxmodp，保密x，發送a給Bob②用戶Bob選擇隨機數y，計算b=gymodp，保密y，發送b給Alice③Bob和Alice各自計算k=bxmodp和k=aymodp,從而得到共享密鑰k這是因為k=bxmodp=(gy)xmodp=(gx)ymodp=aymodp60/第四章公鑰密碼：4.7ElGamal密碼體制與DH密鑰交換4.8橢圓曲線密碼體制為保證RSA算法的安全性，它的密鑰長度需一再增大，使得它的運算負擔越來越大。相比之下，橢圓曲線密碼體制ECC（ellipticcurvecryptography）可用短得多的密鑰獲得同樣的安全性，因此具有廣泛的應用前景，軟硬件實現都有優勢ECC已被IEEE公鑰密碼標準P1363采用1985年，N.Koblitz和V.Miller獨立將其引入密碼學中，成為構造雙鑰密碼體制的一個有力工具其安全性主要基于ECDLP橢圓曲線離散對數問題有限域上的方案都可以用橢圓曲線實現61/第四章公鑰密碼：4.8橢圓曲線密碼體制4.8.1橢圓曲線橢圓曲線并非橢圓，之所以稱為橢圓曲線是因為它的曲線方程與計算橢圓周長的方程類似。一般來講，橢圓曲線的曲線方程是以下形式的三次方程：

y2+axy+by=x3+cx2+dx+e(4-1)其中a，b，c，d，e是滿足某些簡單條件的實數。定義中包括一個稱為無窮點的元素，記為O。下圖是橢圓曲線的兩個例子。從圖可見，橢圓曲線關于x軸對稱。62/第四章公鑰密碼：4.8橢圓曲線密碼體制4.8.1橢圓曲線橢圓曲線上的加法運算定義如下：

如果其上的3個點位于同一直線上，那么它們的和為O。進一步可如下定義橢圓曲線上的加法律（加法法則）：①O為加法單位元，即對橢圓曲線上任一點P，有

P+O=P(這是因為P與-P在曲線的第三個交點是O)②設P1=(x,y)是橢圓曲線上的一點（如圖所示），它的加法逆元定義為P2=－P1=(x,-y)這是因為P1、P2的連線延長到無窮遠時，得到橢圓曲線上的另一點O，即橢圓曲線上的3點P1、P2，O共線，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，還可得O=-O63/第四章公鑰密碼：4.8橢圓曲線密碼體制4.8.1橢圓曲線③設Q和R是橢圓曲線上x坐標不同的兩點，Q+R的定義如下：畫一條通過Q、R的直線與橢圓曲線交于P1這一交點是惟一的，除非所做的直線是Q點或R點的切線，此時分別取P1=Q或P1=R

由Q+R+P1=O得Q+R=-P1④點Q的倍數定義如下：在Q點做橢圓曲線的一條切線，設切線與橢圓曲線交于點S，定義2Q=Q+Q=-S。類似地可定義3Q=Q+Q+Q+，…，以上定義的加法具有加法運算的一般性質，如交換律、結合律等64/第四章公鑰密碼：4.8橢圓曲線密碼體制4.8.2有限域上的橢圓曲線密碼中普遍采用的是有限域上的橢圓曲線，有限域上的橢圓曲線是指曲線方程定義式(4-1)中，所有系數都是某一有限域GF(p)中的元素（其中p為一大素數）其中最為常用的是由方程(4-2)定義的曲線y2≡x3+ax+b(modp)(4-2)(a,b

GF(p),4a3+27b2(modp)≠0)因為＝(a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b＝0的判別式，當4a3+27b2

＝0時方程有重根，設為x0，則點Q0＝(x0,0)是方程(4-2)的重根即x3+ax+b＝(x-x0)3或者＝(x-x0)2(x-x1)，重根將使得一階導數3x2＋a在該Q0點為0令F(x,y)=y2－x3－ax－b，則

F/x|Q0=F/y|Q0=0所以dy/dx=－(F/x)/(F/y)＝(3x2＋a)/2y在Q0點無定義，即曲線y2≡x3+ax+b在Q0點的切線無定義，因此點Q0的倍點運算無定義65/第四章公鑰密碼：4.8橢圓曲線密碼體制4.8.2有限域上的橢圓曲線有限域上的橢圓曲線群定義如下：設Ep(a,b)表示方程(4-2)所定義的橢圓曲線上的點集{(x,y)|0

x<p,0

y<p，且x,y均為整數}并上無窮遠點O一般來說，Ep(a,b)由以下方式產生：

①對每一x(0

x<p且x為整數），計算x3+ax+b(modp)。②決定①中求得的值在模p下是否有平方根，如果沒有，則曲線上沒有與這一x相對應的點；如果有，則求出兩個平方根(y=0時只有一個平方根)。即判斷是否是模p的平方剩余例：橢圓曲線E23(1,1)，4a3+27b2(mod23)≡8≠0，方程為y2≡x3+x+1(mod23)，那么曲線在GF(23)中的整數點，注意點和其逆元，表中未給出O66/第四章公鑰密碼：4.8橢圓曲線密碼體制(0，1)(0，22)(1，7)(1，16)(3，10)(3，13)(4，0)(5，4)(5，19)(6，4)(6，19)(7，11)(7，12)(9，7)(9，16)(11，3)(11，20)(12，4)(12，19)(13，7)(13，