第7講 公鑰密碼體制

密碼學(xué)

韋寶典副教授

第7講：公鑰密碼體制1 一：公鑰密碼原理 二：RSA密碼體制 三：Rabin密碼體制 四：離散對數(shù)

五：ElGamal密碼體制

六：Diffie-Hellman密鑰協(xié)商

七：公鑰密碼總結(jié)2一、公鑰密碼原理雙(公)鑰密碼體制1976年W.Diffie和M.Hellman;R.Merkle[1978]可用于保密通信，也可用于數(shù)字簽字密碼學(xué)史上劃時代的事件為解決計算機信息網(wǎng)中的安全提供了新的理論和技術(shù)基礎(chǔ)加密變換(公鑰)公開解密變換(私鑰)保密3一、公鑰密碼原理4公鑰密碼方案RSAscheme(‘78):R.L.Rivest,A.Shamir,L.Adleman,“AMethodforObtainingDigitalSignaturesandPublicKeyCryptosystems”,CACM,Vol.21,No.2,pp.120-126,Feb,1978McEliecescheme(‘78)Rabinscheme(‘79)Knapsackscheme(‘79-):Merkle-Hellman,Chor-RivestWilliamsscheme(‘80)ElGamalscheme(‘85)EllipticCurvebasedscheme(‘85):Koblitz,MillerHiddenFieldEquations(’95):C*,PatarinLatticeCryptography(’97-):Ajtai(AD,DDH,NTRU)NonabeliangroupCryptography(2000):Braid一、公鑰密碼原理5二、RSA密碼體制1978年

MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman用數(shù)論構(gòu)造雙鑰密碼的方法，稱作MIT體制，后被廣泛稱為RSA體制它既可用于加密、又可用于數(shù)字簽名易懂且易于實現(xiàn)，是目前仍然安全并且逐步被廣泛應(yīng)用的一種體制國際上一些標(biāo)準(zhǔn)化組織ISO、ITU、及SWIFT等均已接受RSA體制作為標(biāo)準(zhǔn)Internet采用的PGP(PrettyGoodPrivacy)也將RSA作為

傳送會話密鑰和數(shù)字簽名的標(biāo)準(zhǔn)算法RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性67參數(shù)選擇：獨立地選取兩大素數(shù)p1和p2(各512bit的數(shù))，計算n=p1×p2

其歐拉函數(shù)值

(n)=(p1－1)(p2－1)隨機選一整數(shù)e，1

e<

(n)，(

(n),e)=1(因而在模

(n)下e有逆元)

d=e-1mod

(n)公鑰為n，e;私鑰為d

(p1,p2不再需要，可以銷毀)二、RSA密碼體制8加密、解密：

將明文分組，各組長1024比特

明文集

Az={x：1

x<n,(x,n)=1}

注意，(x,n)

1是很危險的

x

Az的概率：

加密 y=xemodn 解密 x=yd

modn

證明：yd=(xe)d=xde，因為de

1mod

(n)即de=q

(n)＋1由歐拉定理，(x,n)=1意味x

(n)

1modn，故有yd=xde=xq

(n)+1

x

xq

(n)=x

1=xmodn

陷門函數(shù)：Z=(p1,p2,d)二、RSA密碼體制9例子：p1=47，p2=71，n=47×71=3337，

(n)=46×70=3220e=79，d=e-1(mod3220)=1019公開n=3337和e=79保密私鑰d=1019銷毀p1,p2

令x=6882326879666683，分組x1=688，x2=232，x3=687，x4=966，x5=668，x6=3x1的加密為(688)79(mod3337)=1570=C1，類似計算出其他各組密文，y=15702756209122762423158第一組密文解密為(1570)1019

mod3337=688=x類似解出其他各組密文二、RSA密碼體制10RSA加密實質(zhì)上是一種Zn*

Zn*上的單表代換！給定n=p1p2和合法明文x

Zn*，密文y=xe

modn

Zn*

對于x

x’，必有y

y’Zn*中的元素是一個明文，也是與某個明文相對應(yīng)的一個密文因此，RSA是Zn

Zn的一種單表代換密碼

關(guān)鍵在于：n極大時，若不知陷門信息，則極難確定這種對應(yīng)關(guān)系

由于這種一一對應(yīng)性，RSA不僅可以用于加密也可用于數(shù)字簽名二、RSA密碼體制11安全性:分解模數(shù)n

理論上，RSA的安全性取決于模n分解的困難性，但數(shù)學(xué)上至今還未證明分解模就是攻擊RSA的最佳方法，也未證明分解大整數(shù)就是NP問題，可能有尚未發(fā)現(xiàn)的多項式時間分解算法。人們完全可以設(shè)想有另外的途徑破譯RSA，如求出解密指數(shù)d或找到(p1－1)(p2－1)等。但這些途徑都不比分解n來得容易。甚至Alexi等[1988]曾揭示，從RSA加密的密文恢復(fù)某些比特的困難性也和恢復(fù)整組明文一樣困難。這一視在困難性問題是個NP問題，但還沒人證明它為NPC問題。二、RSA密碼體制12采用廣義數(shù)域篩分解不同長度RSA公鑰模所需的計算機資源二、RSA密碼體制

密鑰長(bit)所需的MIPS-年*

116 4001295,00051230,000768200,000,0001024300,000,000,0002048300,000,000,000,000,000,000

*MIPS-年指以每秒執(zhí)行1,000,000條指令的計算機運行一年

安全性:分解模數(shù)n13技術(shù)進展使分解算法和計算能力在不斷提高，計算所需的硬件費用在不斷下降

RSA-129：110位十進制數(shù)字早已能分解。Rivest等最初懸賞$100的RSA-129，已經(jīng)由包括五大洲43個國家600多人參加，用1600臺機子同時產(chǎn)生820條指令數(shù)據(jù)，通過Internet網(wǎng)，耗時8個月，于1994年4月2日利用二次篩法分解出為64位和65位的兩個因子，所給密文的譯文為“這些魔文是容易受驚的魚鷹”。這是有史以來最大規(guī)模的數(shù)學(xué)運算。原來估計要用4億億年。RSA-130于1996年4月10日利用數(shù)域篩法分解出來。RSA-140于1999年2月分解出來。

RSA-154(512bit)于1999年8月分解出來。

RSA-160,2003.01()

RSA-174(576bit),2003.12二、RSA密碼體制安全性:分解模數(shù)n1415從n若能求出

(n)，則可求得p1,p2。

n－

(n)＋1=p1p2－(p1－1)(p2－1)＋1=p1＋p2((p1+p2)2-4n)1/2=p1-p2但已證明：求

(n)等價于分解n的困難從n求d亦等價于分解n目前尚不知是否存在一種無需籍助于分解n的攻擊法也未能證明破譯RSA的任何方法都等價于大整數(shù)分解問題二、RSA密碼體制安全性:其它途徑16Simmons和Norris提出迭代/循環(huán)攻擊法：給定一RSA的參數(shù)為(n,e,y)=(35,17,3)，由y0=y=3計算y1=317=33mod35再由y1計算y2=y117=3mod35從而得到明文x=y1=33mod35。一般對明文x加密多次，直到再現(xiàn)x為止。Rivest證明：當(dāng)p1－1和p2－1中含有大素數(shù)因子，且n足夠大時，這種攻擊法成功的概率趨于0。二、RSA密碼體制安全性:迭代攻擊法17消息破譯

0）收集用戶A以公鑰e加密的密文y=xemodn，目標(biāo)分析出消息x1）選隨機數(shù)r<n，計算y1=remodn，這意味r=y1dmodn2）計算y2=y1×ymodn3）令t=r-1modn=y1-dmodn4）請A對消息y2進行簽字(用私鑰，但不能用Hash函數(shù))得到s=y2dmodn5）攻擊者計算tsmodn=y1-d×y2dmodn

=y1-d×(y1d×yd)modn=ydmodn=x

得到了明文。二、RSA密碼體制安全性:選擇明文攻擊18消息破譯

y=xemodn，目標(biāo)分析出消息x=ydmodn=yd

y1d

y1-dmodn=(y

y1)d

y1-dmodn=(yre)d(re)-dmodn=

y2dr-1modn=

y2dtmodn

y1=remodn y2=yy1=

yremodn t=r-1modn二、RSA密碼體制安全性:選擇明文攻擊19多人共用同一模數(shù)n，各自選擇不同e和d，實現(xiàn)簡單但不安全若消息以兩個互素(一般如此)的密鑰加密，在共用同一個模下，則可用任一密鑰恢復(fù)明文e1和e2是兩個互素的不同密鑰，共用模為n，對同一消息x加密得y1=xe1modn,y2=xe2modn分析者知道n,e1,e2,y1和y2

因為(e1,e2,)=1，所以由Euclidean算法有r

e1+s

e2=1計算(y1-1)-r

y2s=xmodn(假設(shè)r是負數(shù))二、RSA密碼體制安全性:公用模攻擊20小的e可加快加密和驗證簽字速度，且所需的存儲密鑰空間小但若加密鑰e選擇得太小，則容易受到攻擊網(wǎng)中三用戶的加密鑰e均選3，分別模n1,n2,n3

(互素，否則可求出公因子，而降低安全性)

一用戶將消息x傳給三個用戶的密文分別為

y1=x3modn1

x<n1利用中國余定理， y2=x3modn2

x<n2可從y1,y2,y3求出

y3=x3modn3

x<n3y=x3mod(n1

n2

n3)由x<n1,x<n2,x<n3，可得x3<n1

n2,

n3，故有x=y1/3擴展為k個用戶：將相同的消息x傳給k個人，只要k>e(e+1)/2，采用低指數(shù)亦可有效攻擊為抗擊這種攻擊e必須選得足夠大

e選為16位素數(shù)，既可兼顧快速加密，又可防止這類攻擊二、RSA密碼體制安全性:低加密指數(shù)攻擊21

在x后加時戳

y1=(2tx+t1)3modn1

y2=(2tx+t2)3modn2y3=(2tx+t3)3modn3t是t1,t2,t3的二元表示位數(shù)可防止這類攻擊對短的消息，可用隨機數(shù)字填充以防止低加密指數(shù)攻擊d小也不行：對e<n，d<n1/4，也可以攻破這類RSA體制二、RSA密碼體制安全性:低加密指數(shù)攻擊構(gòu)造y=xemodn，猜測d值，做ydmodn，直到試湊出ydxmodn

Wiener給出對小d的系統(tǒng)攻擊法，證明了當(dāng)d長度小于n的1/4時，由連分式算法，可在多項式時間內(nèi)求出d值22利用測定RSA解密所進行的模指數(shù)運算的時間來估計解密指數(shù)d，而后再精確定出d的取值?？赏ㄟ^將解密運算量與參數(shù)d無關(guān)化來挫敗此攻擊(R.Rivest)還可采用盲化技術(shù)：將數(shù)據(jù)盲化后再密，而后做去盲運算這樣做雖然不能使解密運算時間保持不變，但 計算時間被隨機化而難于推測解密進行的指數(shù)運算的時間

二、RSA密碼體制安全性:定時攻擊法(Timing:P.Kocher)23對明文x，0

x

n－1，采用RSA體制加密，可能出現(xiàn)xe=xmodn，致使消息暴露這是明文在RSA加密下的不動點總有一些不動點，如x=0，1和n－1一般有[1+gcd(e－1,p－1)]

[1+gcd(e－1,q－1)]個不動點由于e－1，p－1和q－1都是偶數(shù)所以不動點至少為9個一般來說，不動點個數(shù)相當(dāng)少而可忽略二、RSA密碼體制安全性:消息隱匿問題24D.Boneh.

TwentyYearsofAttacksontheRSACryptosystem.

NoticesoftheAmericanMathematicalSociety,46(2):203-213,1999.二、RSA密碼體制安全性25(1)n=p×q的確定：p與q必須為強素數(shù)強素數(shù)p的條件：(a)存在兩個大素數(shù)p1和p2，p1|(p－1)，p2|(p＋1)(b)存在4個大素數(shù)r1,s1,r2及s2，使r1|(p1－1),r2|(p2－1),s1|(p1＋1),s2|(p2＋1)。p1和p2為二級素數(shù)；r1,r2,s1和s2為三級素數(shù)二、RSA密碼體制RSA參數(shù)的選擇26采用強素數(shù)的理由如下：若，pi為素數(shù)，ai為正整數(shù)分解式中pi<B，B為已知一個小整數(shù)則存在一種p－1的分解法，使我們易于分解n令n=pq，且p－1滿足上述條件，pi<B令a

ai，i=1,2,…,t可構(gòu)造

顯然(p－1)

R，由費爾馬定理2R

1modp

令2R=xmodn，若x=1則選3代2，直到出現(xiàn)x

1此時，kR=1modp有解的充要條件是 kR=xmodn(p,n)=p|x-1由GCD(x－1,n)=p，就得到n的分解因子p和q二、RSA密碼體制RSA參數(shù)的選擇27p與q之差要大若p與q之差很小，則可由n=pq估計(p＋q)/2=n1/2，

由((p＋q)/2)2－n=((p－q)/2)2，等式右邊為小的平方數(shù)，可以試驗給出p,q的值例：n=164009，估計(p＋q)/2

405，由4052－n=16=42，可得(p＋q)/2=405，(p－q)/2=4，

p=409，q=401二、RSA密碼體制RSA參數(shù)的選擇28p－1與q－1的最大公因子要小惟密文攻擊下，設(shè)破譯者截獲密文y=x

emodn破譯者做下述遞推計算：

xi=xi-1emodn=(xe)imodn若ei=1mod

(n)，則有xi=xmodn，且ei+1=emod

(n)，即xi+1=x若i小，則由此攻擊法易得明文x。由Euler定理知，i=

((p－1)(q－1))，若p－1和q－1的最大公因子小，則i值大，如i=(p－1)(q－1)/2，此攻擊法難于奏效。二、RSA密碼體制RSA參數(shù)的選擇29p，q要足夠大，以使n分解在計算上不可行二、RSA密碼體制RSA參數(shù)的選擇30e的選取原則

(e,

(n))=1條件易于滿足，因為兩個隨機數(shù)互素的概率約為3/5e不可過小：若e小，x小，y=xe

modn，當(dāng)xe<n，則未取模， 由y直接開e次方可求x，易遭低指數(shù)攻擊e小時，加密速度快，Knuth和Shamir曾建議采用e=3但e太小存在一些問題

選e在mod

(n)中的階數(shù)i(ei

1mod

(n))達到(p－1)(q－1)/2二、RSA密碼體制RSA參數(shù)的選擇p，q要足夠大，以使n分解在計算上不可行31d的選擇

e選定后可用Euclidean算法在多項式時間內(nèi)求出dd小，簽字和解密快，在IC卡中尤為重要(復(fù)雜的加密和驗證簽字可由主機來做)d要大于n1/4：類似于加密下的情況，d不能太小否則由已知明文攻擊，構(gòu)造y=xemodn，猜測d的值： 做ydmodn，直到試湊出ydxmodn

Wiener給出對小d的系統(tǒng)攻擊法，證明了當(dāng)d長度小于n的1/4時，由連分式算法，可在多項式時間內(nèi)求出d值二、RSA密碼體制RSA參數(shù)的選擇32不可用公共模由一密鑰產(chǎn)生中心(KGC)采用一公共模，分發(fā)多對密鑰，公布相應(yīng)公鑰ei這當(dāng)然使密鑰管理簡化，存儲空間小，且無重新分組問題但如前所述，它在安全上會帶來問題。明文熵要盡可能地大

明文熵要盡可能地大，以使在已知密文下，要猜測明文無異于完全隨機等概情況。用于簽字時，要采用Hash函數(shù)

二、RSA密碼體制RSA體制實用中的其它問題33

Set-upoftheRabinSystem

Choosetwodistinctprimesp,qs.t.

andputn=pq.

Encryptionfunction三、Rabin密碼體制34Encryptionalgorithm:

Decryptionalgorithm:

step1:Finda,bs.t.ap+bq=1usingtheEuclideanalgorithm.

step2:put

step3:Compute三、Rabin密碼體制Claim:arefourrootsofandmisoneofthesefour.Choseonewhichmakessense!35Theorem.Letn=pqbetheproductoftwodistinctoddprimesp,q.If,thenhasnosolutionsorexactlyfoursolutions(ii)Letr,sbeasolutionof,respectively,thenthefoursolutionsofare(aps+bqr);-(aps+bqr);(aps-bqr);-(aps-bqr),wherea,bsatisfyap+bq=1.(iii)If,thenisasolutionof三、Rabin密碼體制36c=x2modpcp-1=1modpc(p-1)/2=xp-1=1modpc=x2modnc=x2modqcq-1=1modqc(q-1)/2=xq-1=1modqc(p-1)/2c=x2modpx=±c(p+1)/4modpCRT:c(q-1)/2c=x2modqx=±c(q+1)/4modqx=±c(p+1)/4bq±c(q+1)/4apmodn37Theorem:Solvingforallisequivalenttofactoringn.

Cryptanalysis

三、Rabin密碼體制38四、離散對數(shù)Thediscretelogarithmproblemappliestomathematicalstructurescalledgroups.GivenanelementginafinitegroupGandanotherelementhinG,findanintegerxsuchthatgx=h.Likethefactoringproblem,thediscretelogarithmproblemisbelievedtobedifficultandalsotobetheharddirectionofaone-wayfunction.Forthisreason,ithasbeenthebasisofseveralpublic-keycryptosystems,includingtheElGamalsystemandDSS.ThediscretelogarithmproblembearsthesamerelationtothesesystemsasfactoringdoestotheRSAsystem:thesecurityofthesesystemsrestsontheassumptionthatdiscretelogarithmsaredifficulttocompute.39Thediscretelogarithmproblemhasreceivedmuchattentioninrecentyears;descriptionsofsomeofthemostefficientalgorithmsfordiscretelogarithmsoverfinitefieldscanbefound.Thebestdiscretelogarithmalgorithmshaveexpectedrunningtimessimilartothoseofthebestfactoringalgorithms.Rivesthasanalyzedtheexpectedtimetosolvethediscretelogarithmproblembothintermsofcomputingpowerandcost.Ingeneral,thediscretelogarithminanarbitrarygroupofsizencanbecomputedinrunningtimeO(n1/2),thoughinmanygroupsitcanbedonefaster.四、離散對數(shù)40四、離散對數(shù)41ElGamal[1984,1985]提出、基于離散對數(shù)問題的雙鑰密碼體制既可用于加密，又可用于簽字方案：Zp是一個有p個元素的有限域，p是一個素數(shù)，

g是Zp＊的一個生成元明文集M為Zp＊，密文集C為Zp＊×Zp＊。

公鑰：

y

gxmodp

秘密鑰：x<p(2)加密：選擇隨機數(shù)k

Zp-1，且(k,p－1)=1，對明文組M計算：

c1=g

kmodp

(隨機數(shù)k被加密)c2=Mykmodp

(明文被隨機數(shù)k和公鑰

加密)密文由y1、y2級連構(gòu)成，即密文C=c1||c2。(3)解密：收到密文組C后，計算{c2=Myk=M(gx)k=M(gk)x=M(c1)x}M=c2/c1x=Myk/gkx=Mgxk/gk

modp五、ElGamal密碼體制42c1=g

kc2=Myk=M(gx)

k=M(gk)x=

M(c1)xM=c2/c1x=Myk/gkx=Mgxk/gkx

modp特點：密文由明文和所選隨機數(shù)k來定，因而是非確定性加密，一般稱之為隨機化加密，對同一明文不同時刻的隨機數(shù)k不同會給出不同的密文代價是數(shù)據(jù)擴展一倍例p=2579，g=2，x=765，y=g765mod2579=949

明文為M=1299，選隨機數(shù)k=853c1

2853mod2579=435c2

1299×949853mod2579=2396密文C=(435,2396)解密：C算出消息組M

2396/(435)765mod2579=1299。安全性：本體制基于Zp＊中有限群上的離散對數(shù)的困難性。五、ElGamal密碼體制43算法雙方選擇素數(shù)p以及p的一個本原根g用戶A選擇一個隨機數(shù)Xa<p，計算Ya=gXamodp用戶B選擇一個隨機數(shù)Xb<p，計算Yb=gXbmodp每一方保密X值，而將Y值交換給對方用戶A計算出K=YbXamodp用戶B計算出K=YgXbmodp雙方獲得一個共享密鑰(gXaXbmodp)

素數(shù)p以及p的本原根g可由一方選擇后發(fā)給對方六、Diffie-Hellman密鑰交換44GeneraterandomXa<pCalculateYa=gXamodpGeneraterandomXb<pCalculateYb=gXbmodpUserAUserBYaYbCalculateK=(Yb)XamodpCalculateK=(Ya)XbmodpDiffie-HellmanKeyExchange六、Diffie-Hellman密鑰交換45Diffie-Hellman密鑰交換的攻擊replay攻擊中間人攻擊圖示ABK=gXaXbOABK=gXaXoOK=gXbXo六、Diffie-Hellman密鑰交換46中間人攻擊1雙方選擇素數(shù)p以及p的一個原根g(假定O知道)2A選擇Xa<p,計算Ya=gXamodp,AB:Ya3O截獲Ya,選Xo,計算Yo=gXomodp,冒充AB:Yo4B選擇Xb<p,計算Yb=gXbmodp,BA:Yb5O截獲Yb,冒充BA:Yo6A計算:(Yo)Xa(gXo)XagXoXamodp7B計算:(Yo)Xb(gXo)XbgXoXbmodp8O計算:(Ya)XogXaXomodp,(Yb)XogXbXomodpO無法計算出gXaXbmodp雖然不需要計算出這個數(shù)，但O必須實時截獲每一數(shù)值，并冒充轉(zhuǎn)發(fā),否則會被發(fā)現(xiàn)Diffie-Hellman密鑰交換的攻擊六、Diffie-Hellman密鑰交換47雙鑰體制的加密變換是公開的，任何人都可以采用選擇明文來攻擊雙鑰體制，明文空間必須足夠大才能防止窮盡搜索明文空間攻擊。 這在雙鑰體制應(yīng)用中特別重要 (如用雙鑰體制加密會話密鑰時，會話密鑰要足夠長)。一種更強有力的攻擊法是選擇密文攻擊：攻擊者選擇密文，而后通過某種途徑得到相應(yīng)的明文。多數(shù)雙鑰體制對于選擇密文攻擊特別敏感。通常采用兩類選擇密文攻擊：(1)冷漠(Indifferent)選擇明文攻擊。在接收到待攻擊的密文之前，可以向攻擊者提供他們所選擇的密文的解密結(jié)果。(2)自適應(yīng)選擇密文攻擊，攻擊者可能利用(或接入)被攻擊者的解密機(但不知其秘密鑰)，而可以對他所選擇的、與密文有關(guān)的待攻擊的密文，以及以前詢問得到的密文進行解密。七、公鑰密碼總結(jié)48雙鑰密碼體制的設(shè)計雙鑰密鑰保密、認證系統(tǒng)的的安全性主要取決于

構(gòu)造雙鑰算法所依賴的數(shù)學(xué)問題。要求加密函數(shù)具有單向性，即求逆的困難性。因此，設(shè)計雙鑰體制的關(guān)鍵是先要尋求一個合適的單向函數(shù)。七、公鑰密碼總結(jié)49單向函數(shù)令函數(shù)f是集A到集B的映射，以f：A

B表示。若對任意x1

x2，x1,x2

A，有f(x1)

f(x2)，則稱f為單射，或1—1映射，或可逆的函數(shù)。f為可逆的充要條件是，存在函數(shù)g：B

A，使對所有x

A有g(shù)[f(x)]=x。一個可逆函數(shù)f：A

B，若它滿足：1、

對所有x

A，易于計算f(x)。2、對“幾乎所有x

A”由f(x)求x“極為困難”，以至于實際上不可能做到則稱f為一單向(One-way)函數(shù)?！皹O為困難”是對現(xiàn)有的計算資源和算法而言。Massey稱此為視在困難性(apparentdifficulty)，相應(yīng)函數(shù)稱之為視在單向函數(shù)。以此來和本質(zhì)上(Essentially)的困難性相區(qū)分[Massey1985]。七、公鑰密碼總結(jié)50

例

令f是在有限域GF(p)中的指數(shù)函數(shù)，其中p是大素數(shù)，即

y=f(x)=

x,式中，x

GF(p)，x為滿足0

x<p－1的整數(shù)，其逆運算是GF(p)中定義的對數(shù)運算，即

x=log

x

0

x<p－1

顯然，由x求y是容易的，即使當(dāng)p很大，例如p

2100時也不難實現(xiàn)。為方便計算以下令

=2。所需的計算量為ln2p次乘法，存儲量為(ln2p)2比特例如p=2100時，需作100次乘法。利用計算機由x計算

x可在0.1毫秒內(nèi)完成。但是，相對于當(dāng)前計算GF(p)中對數(shù)最好的算法，要從

x計算x所需存儲量大約為(2/3)*(p)1/2*logp比特、運算量大約為(1/2)*(p)1/2*logp

例如p=2100時，所需的計算量為(1/2)*250*100次，以計算指數(shù)一樣快的計算機進行計算需時約1010.7秒(1年=107.5秒，約為1600年！其中假定存儲量的要求能夠滿足)?？梢?，當(dāng)p很大時，GF(p)中的f(x)=

x，x<p－1是個單向函數(shù)。七、公鑰密碼總結(jié)51Pohlig和Hellman對(p－1)無大素因子時給出一種快速求對數(shù)的算法[Pohlig等1978]。特別是，當(dāng)p=2n＋1時，從

x求x的計算量僅需(logp)2次乘法。對于p=2160，在高速計算機上大約僅需時10毫秒。因此，在這種情況下，f(x)=

x就不能被認為是單向函數(shù)。

當(dāng)對素數(shù)p，且p－1有大的素因子時，GF(p)上的函數(shù)f(x)=

x是一個視在單向函數(shù)。尋求在GF(p)上求對數(shù)的一般快速算法是當(dāng)前密碼學(xué)研究中的一個重要課題。七、公鑰密碼總結(jié)52陷門單向函數(shù)

單向函數(shù)是求逆困難的函數(shù)，而

單向陷門函數(shù)(Trapdoorone-wayfunction)是在不知陷門信息下求逆困難的函數(shù)，當(dāng)知道陷門信息后求逆是易于實現(xiàn)的。Diffie和Hellmam[1976]引入的有用概念。例：號碼鎖、太平門。但如何給陷門單向函數(shù)下定義則很棘手，因為(1)陷門函數(shù)其實不是單向函數(shù)，因為單向函數(shù)在任何條件下求逆都是困難的；(2)陷門可能不止一個，通過試驗,一個個陷門就可容易地找到逆。如果陷門信息的保密性不強，求逆也就不難。七、公鑰密碼總結(jié)53公鑰系統(tǒng)一個公鑰系統(tǒng)中，所有用戶共同選定一個陷門單向函數(shù)、加密運算E及可用消息集鑒別函數(shù)F。用戶i從陷門集中選定zi，并公開Ezi和Fzi。任一要向用戶i送機密消息者，可用Fzi檢驗消息x是否在許用明文之中，而后送y=Ezi(x)給用戶x即可。在僅知y，Ezi和Fzi下，任一用戶不能得到x。但用戶i利用陷門信息zi，易于得到Dzi(y)=x。定義對z

Z和任意x

X，F(xiàn)i(x)

y

Y=X。若Fj(Fi(x))=Fi(Fj(x))

成立，則稱F為可換單向函數(shù)?？蓳Q單向函數(shù)在密碼學(xué)中更有用。七、公鑰密碼總結(jié)54用于構(gòu)造雙鑰密碼的單向函數(shù)1976年Diffie和Hellman發(fā)表的文章中雖未給出陷門單向函數(shù)，但大大推動了這方面的研究工作。雙鑰密碼體制的研究在于給出這種函數(shù)的構(gòu)造方法以及它們的安全性。陷門單向函數(shù)的定義并沒有給出這類函數(shù)是否存在。

目前多數(shù)雙鑰體制所用的單向函數(shù)的例子 多項式求根 離散對數(shù) 大整數(shù)分解/RSA問題 背包問題 Diffie-Hellman問題(DHP) 二次剩余問題 模n的平方根問題七、公鑰密碼總結(jié)55

多項式求根