CHD7公開密鑰密碼系統(tǒng)

公開密鑰密碼系統(tǒng)

(Public-KeyCryptosystems)2本章內(nèi)容7.1 公開密鑰的基本概念7.2 RSA公開密鑰密碼機制7.3 ElGamal的公開密鑰密碼系統(tǒng)7.4 橢圓曲線密碼系統(tǒng)7.5 混合式的加密機制7.6 機密分享7.7 量子密碼學(xué)7.8 密碼系統(tǒng)的評估37.1公開密鑰的基本概念對稱式密碼系統(tǒng)有密鑰的管理問題，例如要與N個人做秘密通訊，那么就必須握有N把秘密密鑰為了改善對稱式密碼系統(tǒng)問題，于是便有公開密鑰密碼系統(tǒng)(Public-KeyCryptosystems)的產(chǎn)生4秘密密鑰密碼系統(tǒng)5秘密密鑰密碼系統(tǒng)秘密密鑰密碼系統(tǒng)(Secret-KeyCryptosystems)又稱單密鑰密碼系統(tǒng)(One-KeyCryptosystems)也稱對稱密碼系統(tǒng)(SymmetricCryptosystems)優(yōu)點：加解密速度快缺點：有密鑰管理的問題每位使用者需儲存n-1把Keys

U1U2U5U3U467.1.1公開密鑰加解密基本概念公開密鑰密碼系統(tǒng)(Public-KeyCryptosystems)又稱雙密鑰密碼系統(tǒng)(Two-KeyCryptosystems)也稱非對稱式密碼系統(tǒng)(AsymmetricCryptosystems)7公開密鑰加解密系統(tǒng)87.1.2數(shù)字簽章的基本概念一般數(shù)字簽章具有下列功能：驗證性(Authentication)：可驗證文件來源的合法性，而非經(jīng)他人偽造。完整性(Integrity)：可確保文件內(nèi)容不會被新增或篡改。不可否認(rèn)性(Non-repudiation)：簽章者事后無法否認(rèn)曾簽署過此文件。9數(shù)字簽章的基本概念107.2

RSA公開密鑰密碼機制非對稱式密碼系統(tǒng)的一種。1978年美國麻省理工學(xué)院三位教授Rivest、Shamir及Adleman(RSA)所發(fā)展出來的。利用公開密鑰密碼系統(tǒng)作為數(shù)據(jù)加密的方式，可達到數(shù)據(jù)加密及數(shù)字簽署的功能。Encryption:RSA加密算法，明文加密使用區(qū)塊為每次加密的范圍，使用對方公開密鑰(PublicKey)將明文加密。Decryption:RSA解密算法，必須使用自己的私有金鑰(PrivateKey)才能將密文解出。11RSA算法1.選兩個大質(zhì)數(shù)p和q

(至少100位數(shù))，令N=p?q2.再計算?(N)=(p-1)(q-1)，并選一個與?(N)互質(zhì)數(shù)e?(N)為Euler’sTotient函數(shù)，其意為與N互質(zhì)之個數(shù)3.(e,N)即為公開密鑰

加密法為C=MemodN4.選一個數(shù)d，滿足e?dmod?(N)=15.d即為解密密鑰(亦稱私有密鑰或秘密密鑰)

解密法為M=CdmodNRSA之安全性取決于質(zhì)因子分解之困難度要將很大的N因子分解成P跟Q之相乘，是很困難的12RSA算法例子1.接收方選p=3，q=11;此時N=p?q=332.找出1個與(p-1)x(q-1)=(3-1)(11-1)=2x10=20

互質(zhì)數(shù)e=33. (e,N)=(3,33)即為接收方的公開密鑰4.接收方選一個數(shù)d=7當(dāng)作解密密鑰， 滿足e?d1mod20(7x31mod20)

令明文M=19

加密:C=MemodN=193mod33=28

解密:M=CdmodN=287mod33=1913相關(guān)的數(shù)學(xué)理論Ifpisaprime,andaisnotamultipleofp,thenFermat’slittletheoremsaysap-1modp=1

Ex.26mod7=1

費瑪(Fermat)定理:若p為質(zhì)數(shù)且(a,p)互質(zhì)，則ap-1modp=1Fermat’sLittleTheorem14尤拉定理Ifgcd(a,n)=1,then

where()calledEulerphifunction.Euler定理:若a，n互質(zhì)，則a?(n)modn=1尤拉函數(shù):?(P)=P-1若P為質(zhì)數(shù)?(N)=?(PQ)=?(P)?(Q)=(P-1)(Q-1)Itisthenumberofpositiveintegerslessthannthatarerelativelyprimeton.

Ifnisaprime,(n)=n-1.Ifn=pq,wherepandqareprime,then(n)=(p-1)(q-1)Euler’sTheorem15模數(shù)系下的乘法反元素問題

找到一數(shù)x使得

(a×x)=1

x的解為x=a-1

一般的乘法反元素問題

找到一數(shù)x使得

1=(a×x)modN

x的解為x=a-1modN模數(shù)系的乘法反元素問題16若a與N互質(zhì)，則x=a-1modn有唯一解若a與N不互質(zhì)，則x=a-1modn無解例如：

5模14的乘法反元素為3，但2模14的乘法反元素就不存在。這也就是為何在RSA密碼系統(tǒng)中，使用者所選擇的公開密鑰e必須與?(N)互質(zhì)的原因。一般來說有兩種方法可以用來解乘法反元素的問題-利用尤拉定理-利用擴展歐幾理德算法ModularInverseProblem模數(shù)系下的乘法反元素問題(續(xù))17如何找到模數(shù)系下的乘法反元素方法一：利用尤拉定理(Euler’sTheorem)

x=a-1modna×xmodn=1

x=a(n)-1modn理由是依據(jù)尤拉定理：Ifgcd(a,n)=1,thena(n)

modn=1例如：5模7的乘法反元素如何求得?56-1

mod7=55

mod7=3where(n)=6Note:若n為質(zhì)數(shù)，則(n)可以很輕易求得；但若n為一很大的非質(zhì)數(shù)，則要求的(n)相當(dāng)于解質(zhì)因子分解的困難度

18方法2：擴展歐幾理德算法(ExtendedEuclideanAlgorithm)歐幾理德算法(EuclideanAlgorithm)常被用在解最大公因子的問題上Findgcd(a,n)Letr0=n,r1=a,wegetr0=r1g1+r2

,r1=r2g2+r3,...,rj-2=rj-1gj-1+rj,...,rm-4=rm-3gm-3+rm-2,rm-3=rm-2gm-2+rm-1,rm-2=rm-1gm-1+rm,rm-1=rmgm

如何找到模數(shù)系下的乘法反元素(續(xù))19根據(jù)擴展歐幾理德算法，若a與n兩數(shù)互質(zhì)，一定可以找到兩個整數(shù)s與t，使得

gcd(a,n)=sa+tn=1.其作法如下：Ifgcd(a,n)=1,wegetsa+tn=1.Wecanfindsandtbyusing

rm=gcd(a,n)=rm-2-rm-1gm-1becauserm-1=rm-3–rm-2gm-2sogcd(a,n)=rm-2-(rm-3–rm-2gm-2)gm-1=(1+gm-1gm-2)rm-2–gm-1rm-3

andsoon.sa+tn=1sa+tnmodn=1samodn=1

s=a-1modn如何找到模數(shù)系下的乘法反元素(續(xù))20RSA密碼系統(tǒng)的正確性C=E(M)=MemodnM=D(C)=CdmodnCd=(Me)d=Medmodnsinceed=1mod(p-1)(q-1)soMed=Ma(p-1)(q-1)+1=MMa(p-1)(q-1)=MMa(n)

modn根據(jù)尤拉定理(Euler’sTheorem)，得到M

×

1=M

21因式分解的問題FactoringProblem

FactoringanumbermeansfindingitsprimenumberEx:10=2×5;60=2

×2×3×5但是解一個大數(shù)的值因子分解問題是很困難的。請試著分解:

3337RSA的安全性便是植基于解因式分解的難題上22RSA算法指數(shù)運算：計算x=ABmodN?a1:=A;b1:=B;x:=1;whileb1

0dobeginwhileb1mod2=0dobeginb1:=b1div2;a1:=(a1

×a1)modN;end

b1:=b1-1;x:=(x×a1)modNend

計算x

=A17modN=A10001modN=A?(((A2)2)2)2

計算x=A13modN=A1101modN=A?((A2)2)?((A2)2)2

計算x=A7modN=A111modN=A?(A2)?(A2)2

23Public-KeyCryptosystems之特性1.D(d,E(e,M))=M，可還原性2.d和e很容易求得3.若公開(e,n)，別人很難從(e,n)求得d，即只有自己知道如何解密(以e加密)4.E(e,D(d,M))=MPublic-keyCryptosystems一定要能忍受Chosen-PlaintextAttack24Public-KeyCryptosystems之特性(續(xù))．滿足1~3項稱之為trap-doorone-wayfunction．“one-way”因易加密而不易解密．“trap-door”若知一些特別信息即可解密．滿足1~4項稱之為trap-doorone-waypermutation．1~3項為public-keycryptosystems之要求．若同時滿足第4項要求，則該保密法可用來制作數(shù)字簽章。25RSA數(shù)位簽章S=Md張modN張

M=?Se張modN張張豐使用自己的秘密密鑰對文件M

做數(shù)位簽章S張豐李良李良使用張豐的公開密鑰確認(rèn)數(shù)字簽章及文件傳送M及S一般使用時會先將文件M作HASH函數(shù)處理，使得HASH(M)比N小26數(shù)位簽章法MHE||MHD比較是否相等SKaPKaESKa[H(M)]為M之簽章DPKa[ESKa[H(M)]]=H(M)512位27RSA數(shù)位簽章+加密C=(Md張modN張)e李modN李M=(Cd李modN李)e張modN張

張豐對文件M做數(shù)位簽章后用李良的公用密鑰將簽章加密張豐李良李良使用私有密鑰解開密文C再用張豐的公開密鑰確認(rèn)數(shù)字簽章傳送密文C28非對稱式密碼系統(tǒng)的一種。1985年由ElGamal所發(fā)展出來的。安全性導(dǎo)因于離散對數(shù)(DiscreteLogarithm)之困難度。相同明文可得到不相同的密文。RSA密碼系統(tǒng)則是相同明文得到相同密文。

7.3ElGamal的公開密鑰密碼系統(tǒng)離散對數(shù)(DiscreteLogarithm)的問題：若p為很大之質(zhì)數(shù)；g為p之原根(primitiveroot)y=gxmodp雖已知y,g,p，但要導(dǎo)出x值是很困難的29

什么是原根？原根generators:ifpisaprime,andgislessthanp,thengisageneratormodpifforeachbfrom1top-1,thereexistssomeawherega

b(modp).galsocalledprimitiverootofmodp

21mod11=222mod11=423mod11=824mod11=525mod11=1026mod11=927mod11=728mod11=329mod11=6210mod11=12isageneratormodulo11Ex:3不是模11下的一個原根，因為3amod11=2中，a為無解30解離散對數(shù)的問題已知a、b與n三數(shù)，要找到一個數(shù)x，使得x滿足

axmodn=b是一個很難解的問題。Ex.If3xmod17=15,thenx=6

Note:并非所有離散對數(shù)的問題均有解Ex.3xmod13=7,nosolution!!31張豐將明文M以李良之公開密鑰加密：1.張豐選一個隨機數(shù)r2.計算b=grModPc=M?yrmodP張豐送(b,c)給李良4.李良收到(b,c)后計算c?(bx)-1modP=M7.3.1ElGamal的加解密機制李良之密鑰產(chǎn)生：y=gxmodPy為李良之公開密鑰x為李良之秘密密鑰P為很大之質(zhì)數(shù)g為與P互質(zhì)之原根32李良將明文M以李良之秘密密鑰制作簽章：1.李良選一個隨機數(shù)k使得gcd(k,p-1)=12.計算r=gkmodp3.李良計算s使得M=(xr+ks)mod(p-1)4.李良送(M,r,s)給驗證者(張豐)5.M,r,s)后驗證gM=yrrsmodP上式若相等表示M確定為李良所簽署7.3.2ElGamal的數(shù)位簽章機制李良之密鑰產(chǎn)生：

y=gxmodPy為李良之公開密鑰x為李良之秘密密鑰P為很大之質(zhì)數(shù)g為與P互質(zhì)之原根33

7.4橢圓曲線密碼系統(tǒng)RSA或ElGamal密碼系統(tǒng)最為人詬病的問題就是在加解密或是簽章的時候需要龐大的運算量，所以需要較長的運算時間。為了改善其效率（較少之運算量），因此提出橢圓曲線的密碼系統(tǒng)(EllipticCurveCryptosystem,ECC)，它的安全性必須相當(dāng)于RSA或ElGamal的密碼系統(tǒng)。34

橢圓曲線上的有限加法群所使用的橢圓曲線方程式為y2=x3+ax+b此曲線剛好對稱于y=0這條直線參數(shù)a及b必需滿足4a3+27b2≠0，才能確保沒有重根，具有唯一解加法單位元素O為一無窮遠的點，并滿足O=-O此加法單位元素亦需滿足：橢圓曲線上某三點共線其合為O35

橢圓曲線上不同坐標(biāo)點相加36作法先找出A與B這兩點所構(gòu)成的直線。接著找出這個直線與橢圓曲線的交點R。由于A、B及R這三點共線，根據(jù)橢圓曲線加法的定義可知A+B+R=0，因此可求得A+B=-R，這里的-R表示坐標(biāo)點R對y=0這條直線鏡射，也就是R對稱于y軸的坐標(biāo)點。

橢圓曲線上不同坐標(biāo)點相加(續(xù))37范例：假設(shè)一橢圓曲線為y2=x3+73，求A坐標(biāo)點(-4,3)與B坐標(biāo)點為(2,9)相加的結(jié)果。求出A與B兩點所構(gòu)成的直線方程式（二個坐標(biāo)點可以畫一直線）為y=x+7。將此直線方程式y(tǒng)=x+7代入橢圓曲線方程式y(tǒng)2=x3+73中，得知此直線與橢圓曲線的交點坐標(biāo)R為(3,0)。把R坐標(biāo)對y軸做鏡射，可得到-R的坐標(biāo)為(3,-10)，因此可得知A與B兩點做相加，其值等于(-4,3)+(2,9)=(3,-10)。

橢圓曲線上不同坐標(biāo)點相加(續(xù))38

橢圓曲線上相同坐標(biāo)點相加39作法：先找出A點在橢圓曲線上的切線。接著找出這條切線與橢圓曲線的交點R。同樣地，我們可以看成A、A'、R這三點共線，根據(jù)橢圓曲線加法的定義可得知A+A'+R=O，因此可求得A+A=-R。

橢圓曲線上不同坐標(biāo)點相加(續(xù))40

橢圓曲線上一坐標(biāo)點與一無窮遠點相加41

橢圓曲線上兩對稱點相加A＋B=A+(-A)=O

B42

7.4.2在有限體內(nèi)的橢圓曲線運算

在此橢圓曲線上可能出現(xiàn)的點有(0,1)、(0,4)、(2,1)、(2,4)、(3,1)、(3,4)、(4,2)、(4,3)、(∞,∞)任取橢圓曲線上兩點，無論作加法、減法或乘法，其結(jié)果永遠為上述坐標(biāo)點中的一點橢圓曲線中的離散對數(shù)難題：給訂一參數(shù)K及一點A，要求得另一點B，使得B=KA是很容易的。例如：5A=A+A+A+A+A但若給定A及B要求得K則很困難437.4.3橢圓曲線的公開密鑰加密機制447.4.4橢圓曲線的數(shù)字簽章45

7.5混合式的加密機制混合式加密機制顧名思義就是同時采用對稱式密碼機制及公開密鑰密碼機制的加密系統(tǒng)，截長補短，使它可以同時擁有這兩種密碼機制的優(yōu)點。46

7.5.1數(shù)位信封Sender:AliceReceiver:BobC=ESK(M)密文V=EPU(SK)信封SK:SessionKey(交談密鑰)ESK:秘密密鑰密碼系統(tǒng)(Key:SK)PU:Bob之公開密鑰EPU:公開密鑰密碼系統(tǒng)(Key:PU)PR:Bob之秘密密鑰M=DSK(C)明文SK=DPR(V)交談密鑰密文及信封477.5.2Diffie-Hellman的密鑰協(xié)議與交換機制Diffie和Hellman在1976年最早提出公開密鑰密碼系統(tǒng)的概念。沒有真正地利用公開密鑰去對訊息做加解密，而是利用公開密鑰的概念來幫助通訊雙方可以安全地協(xié)議出一把共同的交談密鑰(SessionKey)。真正的加解密工作是利用所協(xié)議出來的這把交談密鑰，透過DES或AES等對稱式的密碼系統(tǒng)來完成。48Diffie-Hellman的密鑰協(xié)議方法注:

p為很大之質(zhì)數(shù)

g為與p互質(zhì)之原根(primitive)49Diffie-Hellman的密鑰交換方法子機密密鑰Ki產(chǎn)生方法如下：分派者決定主機密密鑰K任選K1、K2、…、Kn-1等n-1把子機密密鑰由下列方程式求出第n把子機密密鑰Kn

Kn=K1⊕K2⊕…⊕Kn-1⊕Kn當(dāng)n個成員均拿出其子機密密鑰Ki，即可推導(dǎo)出煮機密密鑰K： K=K1⊕K2⊕…⊕Kn507.6機密分享(t,n)門坎機密分享技術(shù)Shamir在1979年提出(t,n)門坎機密分享技術(shù)(ThresholdSecretSharing)門坎機密分享技術(shù)之兩重要參數(shù)： t：門坎值 n：機密分享數(shù)目機密分派者將機密信息K打造成n份不同的子機密(Shadow)，每位成員都可得到一子機密訊息Ki51(t,n)門坎機密分享技術(shù)(續(xù))(t,n)門坎機制的兩個主要法則：當(dāng)子機密訊息的數(shù)目等于或大于門坎值t時，便可以導(dǎo)出主機密信息。當(dāng)子機密訊息的數(shù)目小于門坎值t時，就無法導(dǎo)出主機密信息。52分派者任選t-1次多項式 F(X)=K+a1X+a2X2+…+at-1Xt-1

modP K：主機密信息

P：為大值數(shù)并滿足P≧K a1,a2,…,at-1：值介于0~P-1間分派者給每位成員唯一的公開識別碼IDi，及依IDi產(chǎn)生不同的子機密信息Ki=F(IDi)

i=1,2,…,n (IDi,Si)：可視為多項式F(X)上的一個坐標(biāo)點53(t,n)門坎機密分享技術(shù)(續(xù))假設(shè)有大于等于t個成員拿出所持有的子機密信息(IDi,Ki)，可得到下列t條方程式：

Ki=K+a1IDi+a2IDi2+…+at-1IDit-1modP,i=1,2,…,t上式t個未知數(shù)(K,a1,a2,…,at-1)可用下列方法解出：解聯(lián)立方程式利用下列Lagrange插值多項式解出機密值K：54(t,n)門坎機密分享技術(shù)(續(xù))范例：(t,n)=(3,4)門坎機密分享技術(shù)如下分派者任選2次多項式：F(X)=6+3X+4X2mod11分派者給每位成員識別碼IDi，并計算出各成員的機密信息Ki假設(shè)三成員(ID1,ID2,ID3)拿出所持有的子機密信息(IDi,Ki)，可得到下列三條方程式： 2=K+a1(1)+a2(12)mod11 6=K+a1(2)+a2(22)mod11 7=K+a1(3)+a2(32)mod1155(t,n)門坎機密分享技術(shù)(續(xù))可用Lagrange插值多項式解出機密值K：代入公式得：

56(t,n)門坎機密分享技術(shù)(續(xù))577.7量子密碼學(xué)前使用的密碼系統(tǒng)中，不論DES、RSA、ElGamal或橢圓曲線密碼系統(tǒng)，其安全程度都僅屬于計算安全(ComputationalSecure)。量子計算機的出現(xiàn)，使得現(xiàn)存的密碼系統(tǒng)都將不再安全。有機會利用量子計算機來發(fā)展出無條件安全的密碼系統(tǒng)587.7.1量子計算機的基本概念量子計算機(QuantumComputer)是利用量子物理的法則所設(shè)計的一種計算機。與傳統(tǒng)計算機最大的差別在于量子計算機可以同步地處理同一件工作，因此可大幅縮減在運算上所需花費的時間。量子計算機的基本元素稱之為量子位(QuantumBits)，簡稱為qubits。59迭加性(Superposition)假設(shè)每一個量子位都可能會有兩種狀態(tài)，不是順時針旋轉(zhuǎn)就是逆時針旋轉(zhuǎn)，若我們把一個粒子放到一個暗箱里，然后打進一個微弱的脈沖，此時箱子內(nèi)的粒子可能是順時針，也可能是逆時針，若不打開箱子看，我們無法得知這個粒子旋轉(zhuǎn)的方向。這種所有狀態(tài)都可能出現(xiàn)的情況就稱為迭加性。測量性(Measurement)在箱子打開之前，量子是以迭加的狀態(tài)存在，也就是順時針旋轉(zhuǎn)或逆時針旋轉(zhuǎn)都有可能。一旦箱子被打開后，答案就公布了，量子的迭加性也隨之消失。量子計算機的特性量子計算機的特性(續(xù))可逆性(Reversing)在量子運算中，所有運算在未經(jīng)測量前都是可逆的。不可復(fù)制性(No-cloning)無法對處于迭加狀態(tài)中的量子進行復(fù)制。糾纏性(Entanglement)無法分解成任意兩個量子態(tài)的乘積。617.7.2量子計算機對傳統(tǒng)密碼學(xué)的威脅以猜數(shù)字游戲為例，一方從0到9的數(shù)字中任選四個不同的數(shù)字，由另一方來猜，總共有10×9×8×7=5040種可能的答案。若把這個猜謎游戲交給傳統(tǒng)計算機來執(zhí)行，就算計算機依序測試各種可能的答案，例如，先猜0123，若不對，接著就猜0124，如此不斷地猜下去，徹底嘗試過5040種可能的答案，也只需要幾秒鐘的時間就可以找到正確的答案。62由于量子計算機可以對同一個問題的不同狀態(tài)進行同步的處理，所以量子計算機可以更有效率地來執(zhí)行這個猜謎游戲。其作法如下：我們可以用14個位來表示任何由4個數(shù)字所組成的十進制數(shù)，例如「00000001111011」就相當(dāng)于十進制的「0123」，「00000001111100」相當(dāng)于十進制的「0124」。然后將每一個位用一個量子位來表示，再將這14個量子位同時放到一個箱子中。7.7.2量子計算機對傳統(tǒng)密碼學(xué)的威脅(續(xù))7.7.2量子計算機對傳統(tǒng)密碼學(xué)的威脅(續(xù))打入弱脈沖，使之旋轉(zhuǎn)方線產(chǎn)生變化，此時這14個量子就進入迭加狀態(tài)了，它同時代表214種可能發(fā)生的狀態(tài)，然后把這些處于迭加狀態(tài)的粒子放入量子計算機中執(zhí)行。由于量子計算機可以同時嘗試所有可能的答案，一個單位時間后，量子計算機就會告訴我們正確的謎底為何，而傳統(tǒng)計算機可能需要5040個單位時間，才能完成所有可能答案的搜查。647.7.3量子密碼學(xué)概念是利用光子的偏震方向來代表「0」或「1」。偏震方向的定義有兩種，分別是直線方案(Rectilinear)與斜線方案(Diagonal)。直線方案中偏振方向「|」代表「1」，偏振方向「－」代表「0」。斜線方案中偏振方向「\」代表「1」，偏振方向「/」代表「0」。而用來測量偏振方向的偵測器也可分為兩種，分別為直線型「＋」，與斜線型「×」，「＋」型偵測器可用來判定「|」及「－」偏振的光子；同理，「×」型偵測器可用來判定「\」及「/」偏振的光子。65利用量子密碼進行秘密通訊春嬌隨意用直線或斜線方案來傳送一連串可代表0或1位的光子給志明。由于志明不知道春嬌依序用了哪些方案來傳送這些光