《現(xiàn)代密碼學(xué)原理與實(shí)踐》課件第5章

第5章簽名與認(rèn)證5.1數(shù)字簽名

5.2單向散列(Hash)函數(shù)

5.3身份識別

5.4消息認(rèn)證碼(MAC)

習(xí)題5

實(shí)踐練習(xí)5

信息技術(shù)帶來現(xiàn)代社會變革的一個重大方面是電子商務(wù)，它極大地促進(jìn)了傳統(tǒng)商務(wù)模式的改變和結(jié)構(gòu)的更新。而電子商務(wù)的發(fā)展，對信息安全技術(shù)又提出了多方位的新要求，主要表現(xiàn)在形形色色的簽名與認(rèn)證需求方面。密碼技術(shù)近年來的巨大發(fā)展，也正集中體現(xiàn)在這些方面。5.1數(shù)字簽名

A收到B以明文方式送來的信息后，A如何鑒別是B所發(fā)而非別人偽造或篡改的呢？又如公鑰密碼系統(tǒng)中，各用戶從網(wǎng)絡(luò)上獲取對方的公開密鑰，如何保證它沒有被篡改或替代呢？倘若C用自己的公鑰替換了B的公鑰，那么它就可以用自己的私鑰解讀所有人發(fā)給B的密文。再如，單鑰體系中，A、B兩方均掌握密鑰K，如果沒有簽名，一旦發(fā)生爭議就說不清楚，因?yàn)锽可以修改A發(fā)來的密文，A也可以自己修改原文以賴賬，法律上缺乏判定誰是誰非的憑證。傳統(tǒng)的(手寫)簽名借助紙張將文件的內(nèi)容與簽發(fā)人的筆跡(認(rèn)可憑證)有效地結(jié)合在一起，使文件具有了可認(rèn)證性。然而，由于電子文檔的易拷貝性和可粘貼性，使機(jī)械地照搬手寫簽名到電子文檔上的做法失效，必須引入功能相似，但方式不同的有效認(rèn)證方式。數(shù)字簽名是含有發(fā)送方身份的一段數(shù)字或代碼串。它應(yīng)有以下特征：

(1)簽名是可以驗(yàn)證的，收到簽名的人容易由簽名確定來信人。

(2)簽名是不可偽造的，除了簽名者之外的任何人無法實(shí)現(xiàn)這個簽名。

(3)簽名是不可重用的，一個簽名只對一個文件生效，無法用于其他文件。

(4)簽名是不可改變的，一旦簽名發(fā)出便不能再作修改。(5)簽名是不可抵賴的，存在某種方法充分證明該簽名確為發(fā)信人所為。用發(fā)信人私鑰加密所發(fā)信件得到的密文，就是具有上述特征的一種數(shù)字簽名。為了適應(yīng)多種不同的用途，為了使用起來更方便更安全，滋生出了一系列不同形式的數(shù)字簽名，下文將陸續(xù)介紹。它們在電子商務(wù)和信息網(wǎng)絡(luò)中發(fā)揮著不可替代的作用。數(shù)字簽名的主要功能有：

(1)識別來信(函)的正確信源。

(2)驗(yàn)證發(fā)信人的合法身份。

(3)檢查信函內(nèi)容的完整性。

(4)獲得行為不可否認(rèn)的證據(jù)。

(5)標(biāo)示知識產(chǎn)權(quán)的印記。5.1.1RSA簽名體系

RSA簽名體系與RSA加密算法相同，但用法不同。

系統(tǒng)參數(shù)

取兩個大素?cái)?shù)p和q，計(jì)算n=p·q和(n)=(p-1)(q-1)，隨機(jī)選擇整數(shù)d使gcd(d,(n))=1，求出模(n)的逆元e，使它滿足ed=1mod(n)。取公開密鑰為k1=(n,e)；私有密鑰為k2=(p,q,d)。簽名算法

用私鑰“加密”明文x，得到的結(jié)果y叫做x的簽名，即

Sig(x)=xd

modn=y(5-1)驗(yàn)證算法

Ver(y)=yemodn≡x(5-2)

首先y只能是x的簽名(是x的加密結(jié)果)，它不能用于其他文檔；其次，y是用發(fā)信人的私鑰“加密”所得，別人做不出這樣的簽名。任何人都可以用發(fā)信人的公鑰解出x，與原來的x對照，即可證明以上兩點(diǎn)。通常不僅要認(rèn)證簽名，還要加密明文，不讓合法收信人以外的其他人看到明文x，這就要進(jìn)行雙重“加密”。如A給B發(fā)信，有兩種方案：

(1)先加密再簽名：A做z=EB(x)，y=SigA(z)的運(yùn)算，把(z,y)傳輸給B；B收到(z,y)后，用自己的私鑰解讀密文,即做x=DB(z)的運(yùn)算，再用A的公鑰驗(yàn)證簽名VerA(z,y)，看是否滿足=z。

這樣做的不安全之處在于如果竊聽者C收到(z,y)，它可以用自己的密文z′=EB(x′)替代z，并對z′作自己的簽名：SigC(z′)=y′，再用y′代替y。而B收到(z′,y′)后，可能會做出發(fā)信人是C的誤解，因?yàn)橛肅的公鑰(eC,n′)能夠證明簽名VerC(z′,y′),即

=z′modn′，從而相信了C發(fā)來的密文x′，結(jié)果受了騙。

(2)先簽名再加密：A先做SigA(x)=y的運(yùn)算，再做連明文帶簽名一起加密EB(x,y)=z的運(yùn)算，發(fā)送z給B；B收到z后先解密得到簽名，再進(jìn)行驗(yàn)證。這種方案中，竊聽者C即使收到z，也因無A的私鑰而不能解譯，所以比較安全。5.1.2ElGamal簽名方案

1985年，ElGamal基于離散對數(shù)提出了一種簽名方案。

系統(tǒng)參數(shù)

p是大素?cái)?shù)，g是的一個生成元(即本原根)。定義密鑰為

K={(p,g,y,x)：y=gxmodp}，x∈

其中，公開密鑰k1為y、p、g；私有密鑰k2為x。

簽名算法

簽名者擁有(k1k2)=(p，g，y，x)，隨機(jī)數(shù)k∈和待簽消息m。生成的簽名為

Sig(m,k)=(r,s)(5-3)

這里,對r和s有

r=gkmodp,s=(m-xr)k-1mod(p-1)(5-4)

隨機(jī)數(shù)k用以生成簽名中的r部分，而明文用以生成簽名中的s部分。

驗(yàn)證算法

驗(yàn)證者有公鑰k1=(p，g，y)，收到的明文m和簽名(r,s)，從而驗(yàn)證算法為

Ver(r,s)=yrrs≡gm

modp(5-5)實(shí)際上，因?yàn)?/p>

ks=(m-xr)mod(p-1)即

ks=λ(p-1)+(m-xr)于是有

gks=gλ(p-1)+(m-xr)=gλ(p-1)g(m-xr)

利用歐拉定理gp-1modp=1，就有

gλ(p-1)=(gp-1)λmodp=1modp

所以

gks=g(m-xr)modp

因此有

yrrs=gxrgks=gxrg(m-xr)modp=gmmodp

使用ElGamal方案應(yīng)注意三方面的情況：

(1)隨機(jī)數(shù)k不能泄露，否則用x=(m-sk)r-1modp就可以在已知明文的情況下竊取私鑰。

(2)k應(yīng)當(dāng)每次都不同，否則，若

m1=xr+ks1mod(p-1),m2=xr+ks2mod(p-1)兩式相減得

m1-m2=k(s1-s2)mod(p-1)

設(shè)d=gcd{s1-s2,p-1}，因?yàn)閐|(p-1)且d|(s1-s2),于是d|(m1-m2)。再定義則有，且，那么：從而通過驗(yàn)證r=gkmodp就可以確定k。(3)由于驗(yàn)證只是核實(shí)等式y(tǒng)rrs=gmmodp是否成立，因此可考慮通過偽造能使上式成立的(r,s)來攻擊。然而它的作用只不過對給定明文m又作了一個能通過認(rèn)可的簽名，既沒有破譯系統(tǒng)，又不能為其他明文生成簽名，僅此而已。所以，它并不能對ElGamal構(gòu)成威脅。為了把明文與簽名結(jié)合起來，可以有多種方式，前面所講的方式是：

ks=(m-xr)mod(p-1)其驗(yàn)證方程是

yrrs=gmmodp

其他方式及其驗(yàn)證方程列舉如下：

mx=(rk+s)mod(p-1)ym=rrgsmodp

mx=(sk+r)mod(p-1)ym=rsgrmodp

rx=(mk+s)mod(p-1)yr=rmgsmodp

rx=(sk+m)mod(p-1)yr=rsgmmodp

sx=(rk+m)mod(p-1)ys=rrgmmodp

sx=(mk+r)mod(p-1)ys=rmgrmodp

sx=(k+mr)mod(p-1)ys=rgmrmodp

mrx=(k+s)mod(p-1)ymr=rgsmodp

x=(mrk+s)mod(p-1)y=rmrgsmodp

x=(sk+rm)mod(p-1)y=rsgmrmodp

rmx=(sk+1)mod(p-1)ymr=rsgmodp

sx=(mrk+1)mod(p-1)ys=rmrgmodp

(r+m)x=(k+s)mod(p-1)y(m+r)=rgsmodp

x=［(m+r)k+s］mod(p-1)y=r(m+r)gsmodp

sx=［k+(m+r)］mod(p-1)ys=rg(m+r)modp

x=［sk+(r+m)］mod(p-1)y=rsg(m+r)modp

(r+m)x=(sk+1)mod(p-1)y(m+r)=rsgmodp

sx=［(r+m)k+1］mod(p-1)ys=r(m+r)gmodp通式是：

Ax=Bk+Cmod(p-1)yA=rBgCmodp(5-6)5.1.3DSS

數(shù)字簽名標(biāo)準(zhǔn)(DSS)是美國國家標(biāo)準(zhǔn)和技術(shù)研究所(NIST)于1991年8月公布的標(biāo)準(zhǔn)。它所采用的算法叫DSA，實(shí)際上是ElGamal的變形，簽名中用的是明文的信息摘要。系統(tǒng)參數(shù)

p是一個512~1024位的大素?cái)?shù)，它滿足離散對數(shù)難解問題；q是160位的素?cái)?shù),且q|p-1;g∈是Zp域中q次單位元根。定義K={(p,q,g,y,x}:y=gxmodp},h(·)為公開的Hash函數(shù)。取公開密鑰k1=(p,q,g,y);私有密鑰k2=(x)。

簽名算法簽名者擁有私鑰x，對于隨機(jī)數(shù)k∈和待簽消息m∈，生成的簽名為

(m,k)=(r,s)(5-7)這里:r=(gkmodp)modq(必然小于160位)(5-8)s={h(m)+xr}k-1modq(必然小于160位)(5-9)驗(yàn)證算法

驗(yàn)證者有公鑰k1=(p，g，y)，收到的明文m和簽名(r,s)，驗(yàn)證算法為

(5-10)其中：

e1=h(m)s-1modq,e2=rs-1modq(5-11)實(shí)際上，由k={h(m)+xr}s-1modq知：

DSS的公布引起了學(xué)術(shù)界和商業(yè)界的激烈反應(yīng)：贊成的人認(rèn)為它長度小、速度快、成本低，對金融業(yè)特別有用；反對的人則認(rèn)為它不與國際標(biāo)準(zhǔn)(以RSA為標(biāo)準(zhǔn)的ISO、CCITT、SWIFT等)兼容。從技術(shù)上講，s不能等于零，要加以排除，否則危及安全性。5.1.4不可否認(rèn)簽名方案不可否認(rèn)簽名方案與一般的簽名方案相比較，最根本的特點(diǎn)是如果沒有簽名者的合作，簽名就無法得到驗(yàn)證。這就防止了未經(jīng)簽名者同意就隨意復(fù)制他的簽名文件進(jìn)行電子分發(fā)的可能性。有了這樣的前提，一旦驗(yàn)證通過，簽名者也就沒有理由否認(rèn)。一個不可否認(rèn)簽名由簽名算法、驗(yàn)證算法和否認(rèn)協(xié)議三部分組成。系統(tǒng)參數(shù)

設(shè)p=2q+1是一個大素?cái)?shù)，這里q是素?cái)?shù)且符合離散對數(shù)復(fù)雜性要求；α∈是域中q次單位元根，1≤α≤q-1。設(shè)G表示階為q的的乘法子群，且定義：

K={(p,α,β,a):β=αamodp}其中，私有密鑰為a；公開密鑰為p、α、β。

簽名算法

B掌握私鑰a，欲對x簽名，x∈G，則可計(jì)算：

y=Siga(x)=xamodpy∈G(5-12)y就是B對x的簽名。驗(yàn)證協(xié)議

(1)A欲驗(yàn)證簽名，可任意選取e1,e2∈。計(jì)算c=modp，把它傳給B。

(2)B計(jì)算，并傳回A。

(3)A接收d并驗(yàn)證modp。(5-13)

如果成立，便有充分必要的理由認(rèn)為y是B對x的一條有效的簽名。因?yàn)锽用自己的私鑰參與了驗(yàn)證過程，使A任意地選取e1和e2都能自恰。證明如下：

因?yàn)樗圆豢煞裾J(rèn)簽名方案的安全性分析

首先，A是驗(yàn)證了后，才同意接收y作為x的簽名的，理論上可以推知y≠xamodp情況下的概率只有，因此一個偽造的簽名能使A相信的概率只有。

其次，若y=xamodp且A遵守否認(rèn)協(xié)議，但存在d和d′使：則理論上可以推知成立的概率為

它表明，如果B想用其他d值來否認(rèn)y是他的簽名，其結(jié)果就很難使等式成立(立刻會被發(fā)現(xiàn))。因此，B能愚弄A的概率只有。只要q充分大，B就沒有理由否認(rèn)自己的簽名。5.1.5群簽名

1991年，Chaum和VanHeyst基于以下問題提出群簽名(GroupSignature)方案：一個公司所屬各部門的計(jì)算機(jī)聯(lián)網(wǎng)工作，各部門的打印機(jī)也聯(lián)在網(wǎng)上。打印時，應(yīng)先確定是本公司的人才可以使用，然而又要求不暴露用戶的姓名。另一方面，如果打印機(jī)使用太頻繁時，主管者應(yīng)能夠查出是誰打印了這么多東西。一般來說，群簽名系統(tǒng)由組、組成員(簽名者)、簽名接受者(簽名驗(yàn)證者)和權(quán)威(Authority)組成，它具有以下特點(diǎn)：

(1)用戶組中每位合法用戶都能獨(dú)立對消息產(chǎn)生簽名。

(2)簽名的接受者能驗(yàn)證簽名的有效性。(3)簽名的接受者不能辨認(rèn)是誰的簽名。

(4)一旦發(fā)生爭執(zhí)，權(quán)威或組中所有成員的聯(lián)合可以辨認(rèn)簽名者。這里介紹一種K—P—W可變?nèi)汉灻桨浮Ｏ到y(tǒng)參數(shù)

選擇n=pq=(2fp′+1)(2fq′+1)，這里p、q、p′、q′為相異的大素?cái)?shù)；g的階為f；γ與d為整數(shù)且滿足γd=1modΦ(n)，gcd{γ,Φ(n)}=1；h為安全的Hash函數(shù)；IDG為用戶組身份，由權(quán)威掌握。簽名組的公鑰為(n,γ,g,f,h,IDG)；簽名組的私鑰為(d，p′，q′)。

設(shè)IDA為組員A的身份消息，A隨機(jī)選取sA∈(0,f)，并將消息發(fā)送給權(quán)威。權(quán)威計(jì)算，并將xA秘密地傳送給成員A，使A掌握私有密鑰(xA,sA)。同樣的交換過程在權(quán)威與各個成員之間都要進(jìn)行。

簽名算法

對于待簽消息m，組中任意成員都有權(quán)進(jìn)行簽名。比如A要簽名，他可以隨機(jī)選取整數(shù)(r1,r2)∈［0,f),計(jì)算

(5-14)則簽名為

(e,z1,z2)(5-15)其中:(5-16)

在簽名過程中，雖然簽名者用的是自己隨機(jī)選擇的r1、r2和sA，但是他還必須使用來自權(quán)威的，由于掌握在權(quán)威手里，這就留下了能被權(quán)威辨認(rèn)的把柄。

簽名驗(yàn)證算法

計(jì)算(5-17)驗(yàn)證是否成立。顯然在這個驗(yàn)證算法中，僅使用了用戶組身份IDG和公鑰g和γ，并沒有涉及A的身份問題，所以不會暴露是誰簽的名。

驗(yàn)證簽名時，只需驗(yàn)證e是否等于即可。但為了說明該驗(yàn)證方法是合理的，則應(yīng)當(dāng)在此證明。實(shí)際上：因?yàn)樗?/p>

身份驗(yàn)證算法在發(fā)生爭議需驗(yàn)證是不是A簽的名時，權(quán)威部門可用A發(fā)給他的來驗(yàn)證：(5-18)

計(jì)算中所需要的r2可以由得到(因?yàn)?/p>

)，并不需要A提供任何信息(正因?yàn)锳不愿暴露身份才需要權(quán)威部門出來驗(yàn)證)，僅由簽名(e,z1,z2)和用戶組權(quán)威部門掌握的和xA，就可以驗(yàn)證A的身份。實(shí)際上，不難證明：5.1.6多重?cái)?shù)字簽名多重?cái)?shù)字簽名(DigitalMultisignature)是一種要求多人對同一消息進(jìn)行簽名的數(shù)字簽名方案，只有所有成員都正確完成了簽名，簽名才有效。根據(jù)簽名過程的不同，可分為廣播式(Broadcasting)和順序式(Sequential)兩種。

1．ElGamal順序式多重?cái)?shù)字簽名方案

順序式多重?cái)?shù)字簽名方案的流程如圖5.1所示。圖5.1中,U1…Un是n個簽名者，順序進(jìn)行簽名，并且每人簽名時要驗(yàn)證上一簽名者的簽名的有效性，否則終止簽名過程。圖5.1順序式多重?cái)?shù)字簽名方案流程(1)系統(tǒng)初始化。選擇大素?cái)?shù)p，它滿足Zp中離散對數(shù)復(fù)雜性。g是GF(p)的本原元素。函數(shù)h是GF(p)→GF(p)的單向Hash函數(shù)。每一簽名者Ui(i=1,2,…,n)的私鑰是xi∈［1,p-1］，公鑰是yi=modp,其中，p、g、yi和h(·)公開，xi由Ui密管。

(2)簽名算法。簽名者Ui收到前一人的簽名消息后(m1,(si-1,ri-1))后(第一個簽名者取s0=0)，先驗(yàn)證，然后隨機(jī)選取ki∈［1,p-1］，計(jì)算：和(5-19)這里,m′=h(m)。之后，將(m1,(si,ri))發(fā)送給下一簽名者Ui+1，并將ri發(fā)給Ui以后的所有人。(3)驗(yàn)證算法。①Ui對U1,U2,…,Ui-1簽名有效性的驗(yàn)證是看等式：(5-20)是否成立。實(shí)際上，由就有注意,若s0=0就有：因此，對任意i有下列等式恒成立：即②驗(yàn)證者Ur對最后的結(jié)果進(jìn)行驗(yàn)證時，只需在上式中取i-1=n即可：(5-21)2．Harn廣播多重?cái)?shù)字簽名方案

Harn廣播多重?cái)?shù)字簽名方案如圖5.2所示。

(1)系統(tǒng)初始化。選擇大素?cái)?shù)p,它滿足Zp中離散對數(shù)復(fù)雜性。g是GF(p)的本原元素。函數(shù)h是GF(p)→GF(p)的單向Hash函數(shù)。每一簽名者Ui(i=1,2,…,n)的私鑰是xi∈［1,p-1］，公鑰是,其中p、g、yi和h()公開。圖5.2廣播多重?cái)?shù)字簽名方案流程(2)單用戶簽名的產(chǎn)生。用戶Ui收到消息后，計(jì)算

m′=h(m)(5-22)然后隨機(jī)選取ki∈［1,p-1］，計(jì)算

(5-23)將ri發(fā)給其他各個簽名者Uj(j≠i)。等收到各個用戶發(fā)來的rj后，計(jì)算：(5-24)和(5-25)最后將簽名消息(m′,(si,ri))發(fā)給簽名收集者Uc。(3)單用戶簽名的驗(yàn)證。Uc收到Ui的簽名消息后，計(jì)算:(5-26)通過驗(yàn)證方程:(5-27)來驗(yàn)證Ui簽名的有效性。實(shí)際上，因?yàn)樗?/p>

只有各Ui的簽名均有效，才能計(jì)算多重簽名：

S=s1+s2+…+snmodp-1否則就終止簽名。(R,S)即為多重簽名。

(4)多重簽名的驗(yàn)證。驗(yàn)證者UV驗(yàn)證Ver(m,r,s)=TURE的方法是：(5-28)理由是：5.1.7代理數(shù)字簽名設(shè)A、B是兩用戶，他們的私鑰和公鑰分別為(xA,yA)和(xB,yB)。如果滿足以下條件：

(1)A利用他的秘密密鑰xA計(jì)算出一個數(shù)σ,并將σ秘密交給B。

(2)任何人，包括B試圖求出xA時，σ不會對他有任何幫助。(3)B可以用σ和xB生成一個新的簽名密鑰σA→B，并做簽名s=Sig(σA→B,m)。

(4)存在一個公開的驗(yàn)證算法VerA→B，使其對任何s∈S和m∈M,都有：

VerA→B(yA,s,m)=TURESig(σA→B,m)

式中：S是所有簽名的集合；M是所有明文的集合。

也就是說，對任何消息m及它的簽名s，均可用A的公鑰來驗(yàn)證。

(5)任何人在試圖求出xA、xB、σ或σA→B時，Sig(σA→B,m)都不會對他產(chǎn)生幫助。那么就說，用戶A將他的簽名權(quán)力委托給了用戶B，稱A為B的原始簽名人，B為A的代理簽名人，σ為托管密鑰，σA→B為代理托管密鑰，Sig(σA→B,m)是對消息m做的A的代理簽名。能夠產(chǎn)生代理簽名的體制則稱為代理簽名系統(tǒng)。下面介紹一種基于離散對數(shù)的代理簽名體制。

系統(tǒng)參數(shù)

(M,A,K,S,V)是基于離散對數(shù)的數(shù)字簽名體制，其參數(shù)p、q、g滿足：p是大素?cái)?shù)，在Zp中離散對數(shù)是難解的;q是大素?cái)?shù),且q|p-1;g∈是Zp域中q次單位元根。用戶A和B的私鑰分別是(xA,yA)和(xB,yB)，其中：

(5-29)

委托過程

A隨機(jī)選擇一整數(shù)k∈，計(jì)算：

r=gkmodp,σ=xA+krmodg(5-30)

將(σ,r)秘密傳給B,B收到后驗(yàn)證等式gσ=yArrmodp是否成立。

代理簽名的生成算法

對于待簽消息m，B生成普通的數(shù)字簽名：

s=Sig(σ,m)比如

s=(xB+σm)modg(5-31)將(s,r)作為他代表A對消息m的數(shù)字簽名，此即代理簽名。

代理簽名的驗(yàn)證算法

當(dāng)代理簽名的接收者收到消息m和代理簽名(s,r)后，計(jì)算：

v=yArrmodp(5-32)驗(yàn)證：

Ver(yA,(s,r))=TUREVer(v,s,m)=TURE比如驗(yàn)證：

gs=yBvmmodp(5-33)證明表明v可作為密鑰σ的驗(yàn)證公鑰。由σ對m所作數(shù)字簽名s=Sig(σ,m)就可由Ver(v,s)=m來校驗(yàn)。證明：

代理數(shù)字簽名的安全性如下：

(1)基本不可偽造性：B不能根據(jù)(σ,r)求出xA，就無法偽造A的普通簽名。

(2)代理簽名的不可偽造性：除A、B以外的人無法偽造有意義的代理簽名。(3)代理簽名的可區(qū)分性：代理簽名由普通簽名s和另一部分r組成，很容易與普通簽名區(qū)分開來。如果同一人委托有兩個代理人簽名A的(s,r)和C的(s′,r2)，則由r≠r2也很容易加以區(qū)分。

(4)不可抵賴性：A自然不能抵賴他傳給B的(σ,r)，而B卻可以說是A代理B而不是B代理A，所以B必須是A的充分信任者。(5)身份證實(shí)性：A見到一個代理簽名(s,r)時，可以由r知道是B代理的。

(6)可注銷性：A可以注銷B的代理權(quán)，只需向大家聲明r作廢就可以。5.2單向散列(Hash)函數(shù)

5.2.1概述

單向散列函數(shù)(Hash函數(shù))也叫雜湊函數(shù)，在上段所講的數(shù)字簽名中已多次出現(xiàn)過。它實(shí)際上是一種特殊的壓縮算法，它把任意長度的消息m壓縮成一定長度(如128bit、160bit)的代碼串(稱之為消息摘要)。這種算法h(m)應(yīng)當(dāng)保證原消息的每一符號與壓縮結(jié)果相關(guān)聯(lián)，以至于任意改變原消息的一個符號時將導(dǎo)致其信息摘要一半以上的bit變化。它還要求：

(1)h(m)應(yīng)能對任意長度的消息m做計(jì)算。

(2)計(jì)算h(m)的值h是容易的，而由h計(jì)算m是不可行的(單向性)。(3)對于算法h(m)，要找出兩個不同消息m1和m2有相同的摘要值：

h(m1)=h(m2)(5-34)是非常困難的(或者說是不可行的)。因此，h(m)可作為m的“指紋”或“縮影”方便地保存。當(dāng)原文檔m被傳輸或轉(zhuǎn)存后，可再次計(jì)算其摘要值，比較是否變化(因?yàn)檎怠胺糯蟆绷宋臋n的差別)，以判斷原文檔是否被有意或無意改動過?？梢姡瑔蜗蛏⒘泻瘮?shù)最基本的功能是對文件做“完整性”檢驗(yàn)。其次，如果在計(jì)算摘要值的時候，必須利用發(fā)信人(作者)的私鑰，則這個摘要值也就有了數(shù)字簽名的功效。這樣的簽名短小方便，便于附于文后傳輸。因此摘要算法常常以多種方式與數(shù)字簽名相結(jié)合使用。下面介紹單向散列函數(shù)的常用構(gòu)造方法。

5.2.2用分組加密函數(shù)構(gòu)造散列函數(shù)第2章講的分組加密算法,如DES，它將明文m分成長為64bit的許多小段m1m2…mn，使用64bit的密鑰，一段一段地加密，聯(lián)結(jié)起來就是密文。現(xiàn)在可以把m1加密得到的64bit的密文段c1作為密鑰，去對m2加密，用得到的結(jié)果c2作為密鑰，再對m3加密，如此下去，直到最后得到mn的密文cn，則cn就是所求得的64bit的信息摘要。1.Rabin方案

Rabin方法加密產(chǎn)生信息摘要的方案如圖5.3所示。圖5.3Rabin方法加密產(chǎn)生信息摘要的方案

這種反復(fù)迭代計(jì)算，還可有多種不同方式，如利用分組鏈接方案、密文鏈接方案和密鑰鏈接方案加密產(chǎn)生信息摘要，分別如圖5.4~5.6所示。分組鏈接方案中，每次ci與mi+1按位模2加后，送入加密器進(jìn)行加密。圖5.4分組鏈接產(chǎn)生信息摘要的方案圖5.5密文鏈接產(chǎn)生信息摘要的方案圖5.6密鑰鏈接產(chǎn)生信息摘要的方案5.2.3用候選單向函數(shù)構(gòu)造散列函數(shù)

(1)若f=f(n,e)為RSA函數(shù)令h0=IV(初始值)(5-35)則hi=(mi+hi-1)emodni=1,2,3,…,t(5-36)(2)若f=f(p,g)為離散對數(shù)函數(shù)令h0=IV(初始值)(5-37)則i=1,2,3,…,t(5-38)總之，任何一種單向函數(shù)，迭代使用時都可構(gòu)造h(m)函數(shù)。5.2.4軟件算法MD4

MD4算法是一種通過計(jì)算機(jī)程序?qū)⑷我忾L消息壓縮為128bit消息摘要的算法。首先將明文x按512bit分段，最后不足512bit的部分，扣除末尾64bit后添一個1和d個0，湊成448bit，再把這64bit加在末尾，使之也成為512bit的一段，共有N段。軟件依次處理各個段落，每次把512bit的一個段落分組成32bit的16小段，裝入數(shù)組：

M=M［0］,M［1］,…,M［15］(5-39)(1)給四個寄存器A、B、C、D賦初值，初值的十六進(jìn)制表達(dá)為

A=67452301，B=efcdab89，C=98badcfe，D=10325476(5-40)

每符號4bit，A、B、C、D都是32bit的寄存器，正好可存數(shù)組的一個單元。(2)將A、B、C、D的數(shù)據(jù)拷貝到另外四個寄存器AA、BB、CC、DD中備用，而A、B、C、D作為計(jì)算過程中的變量使用。所用到的運(yùn)算符號說明如下：

x∧y表示按位邏輯與運(yùn)算；x∨y表示按位邏輯或運(yùn)算

x

y表示按位邏輯異或運(yùn)算；表示按位邏輯非運(yùn)算

x+y表示整數(shù)的模232加法；x<<s表示x循環(huán)左移s位(0<s<31)(3)fori=0to(N-1)do(循環(huán)處理各個512bit的段落)(4)forj=0to15do(循環(huán)處理16個32bit數(shù)組單元)X［j］=M［j］(一次將一個32bit裝入數(shù)組X［j］中)(5)執(zhí)行第一輪：fork=0to3do

A={A+f(B,C,D)+X［4k］}<<3

D={D+f(A,B,C)+X［4k+1］}<<7

C={C+f(D,A,B)+X［4k+2］}<<11

B={B+f(C,D,A)+X［4k+3］}<<19其中：f(x,y,z)=(x∧y)∨(∧z) (5-41)(6)執(zhí)行第二輪：fork=0to3do

A={A+g(B,C,D)+X［k］+5a827999}<<3

D={D+g(A,B,C)+X［4+k］+5a827999}<<5

C={C+g(D,A,B)+X［8+k］+5a827999}<<9

B={B+g(C,D,A)+X［12+k］+5a827999}<<13其中：g(x,y,z)=(x∧y)∨(x∧z)∨(y∧z) (5-42)(7)執(zhí)行第三輪：fork=0to3do

A={A+h(B,C,D)+X［0］+6ed9eba1}<<3

D={D+h(A,B,C)+X［8］+6ed9eba1}<<9

C={C+h(D,A,B)+X［4］+6ed9eba1}<<11

B={B+h(C,D,A)+X［12］+6ed9eba1}<<15

A={A+h(B,C,D)+X［2］+6ed9eba1}<<3

D={D+h(A,B,C)+X［10］+6ed9eba1}<<9

C={C+h(D,A,B)+X［6］+6ed9eba1}<<11

B={B+h(C,D,A)+X［14］+6ed9eba1}<<15

A={A+h(B,C,D)+X［1］+6ed9eba1}<<3

D={D+h(A,B,C)+X［9］+6ed9eba1}<<9

C={C+h(D,A,B)+X［5］+6ed9eba1}<<11

B={B+h(C,D,A)+X［13］+6ed9eba1}<<15

A={A+h(B,C,D)+X［3］+6ed9eba1}<<3

D={D+h(A,B,C)+X［11］+6ed9eba1}<<9

C={C+h(D,A,B)+X［7］+6ed9eba1}<<11

B={B+h(C,D,A)+X［15］+6ed9eba1}<<15其中：h(x,y,z)=x

y

z(5-43)(8)再令

AA=A+AA，BB=B+BB，CC=C+CC，DD=D+DD(5-44)回到(3)，處理下一個512bit段落，直至全部。

(9)最后將四個寄存器AA、BB、CC、DD中的4×32bit鏈接,即得到128bit的消息摘要。5.2.5MD5算法

MD5是對MD4的改進(jìn)，消息分組方式不變。但初始值變?yōu)?/p>

A=0x01234567,B=0x89abcdef

C=0xfedcba98,D=0x76543210(5-45)它用到的四個非線性函數(shù)是：(5-46)并且引入以下四個符號表示四種運(yùn)算過程，各自引用不同的非線性函數(shù)：

FF(a,b,c,d,Mj,s,ti)表示a=b+{［a+F(b,c,d)］+Mj+ti}<<s

GG(a,b,c,d,Mj,s,ti)表示a=b+{［a+G(b,c,d)］+Mj+ti}<<s

HH(a,b,c,d,Mj,s,ti)表示a=b+{［a+H(b,c,d)］+Mj+ti}<<s

II(a,b,c,d,Mj,s,ti)表示a=b+{［a+I(b,c,d)］+Mj+ti}<<s(5-47)512bit的信息段被放入16個數(shù)組單元Mj中，各32bit，進(jìn)行4輪加密，每輪循環(huán)16次，每次分別對一個數(shù)組單元進(jìn)行，共64次。各次處理過程的程序全都相同，都是在4個變量中進(jìn)行運(yùn)算，先把其中3個變量進(jìn)行非線性運(yùn)算，然后加上第4個變量，再與一個數(shù)組單元內(nèi)的被處理信息和一個常數(shù)ti相加，之后循環(huán)左移s位，最后加上3個變量中的第一個，將結(jié)果賦予第4個變量。而64次處理過程的區(qū)別在于：A、B、C、D四個變量與a、b、c、d四個形參的對應(yīng)關(guān)系不同，每次引用的信息數(shù)組單元Mj不同，所加常數(shù)ti不同，循環(huán)左移位數(shù)s不同，4大輪所用的非線性運(yùn)算函數(shù)也不同。第一輪是：FF(A,B,C,D,X0,7,0xd76aa478)

FF(D,A,B,C,X1,12,0xe8c7b756)

FF(C,D,A,B,X2,17,0x242070db)

FF(B,C,D,A,X3,22,0xc1bdceee)

FF(A,B,C,D,X4,7,0xf57c0faf)

FF(D,A,B,C,X5,12,0x4787c62a)

FF(C,D,A,B,X6,17,0x48304613)

FF(B,C,D,A,X7,22,0xfd469501)

FF(A,B,C,D,X8,7,0x698098d8)

FF(D,A,B,C,X9,12,0x8b44f7af)

FF(C,D,A,B,X10,17,0xffff5bb1)

FF(B,C,D,A,X11,22,0x895cd7be)

FF(A,B,C,D,X12,7,0x6b901122)

FF(D,A,B,C,X13,12,0xfd987193)

FF(C,D,A,B,X14,17,0xa679438e)

FF(B,C,D,A,X15,22,0x49b40821)

第二輪是：GG(A,B,C,D,X1,5,0x561e2562)

GG(D,A,B,C,X6,9,0xc040b340)

GG(C,D,A,B,X11,14,0x265e5a51)

GG(B,C,D,A,X0,20,0xe96607aa)

GG(A,B,C,D,X5,5,0xd62f105d)

GG(D,A,B,C,X10,9,0x02441053)

GG(C,D,A,B,X15,14,0xd8a1e681)

GG(B,C,D,A,X4,20,0xe7d3fbc8)

GG(A,B,C,D,X9,5,0x21e1cde6)

GG(D,A,B,C,X14,9,0xc33707d6)

GG(C,D,A,B,X3,14,0xf4d50d87)

GG(B,C,D,A,X8,20,0x455a14ed)

GG(A,B,C,D,X13,5,0xa9e3e905)

GG(D,A,B,C,X2,9,0xfcefa3f8)

GG(C,D,A,B,X7,14,0x676f02d9)

GG(B,C,D,A,X12,20,0x8d2a4c8a)

第三輪是：HH(A,B,C,D,X5,4,0xfffa3942)

HH(D,A,B,C,X8,11,0x87715681)

HH(C,D,A,B,X11,16,0x6d9d6112)

HH(B,C,D,A,X14,23,0xfde5380c)HH(A,B,C,D,X1,4,0xa4beea44)HH(D,A,B,C,X4,11,0x4bdecfa9)HH(C,D,A,B,X7,16,0xf6bb4b60)HH(B,C,D,A,X10,23,0xbebf6c70)HH(A,B,C,D,X13,4,0x289b7ec6)HH(D,A,B,C,X0,11,0xeaa107fa)HH(C,D,A,B,X3,16,0xd4ef3085)HH(B,C,D,A,X6,23,0x04881d05)HH(A,B,C,D,X9,4,0xd9d4d039)HH(D,A,B,C,X12,11,0xe6db99e5)HH(C,D,A,B,X15,16,0x1fa27cf8)HH(B,C,D,A,X2,23,0xc4ac5665)

第四輪是:II(A,B,C,D,X0,6,0xf4292244)

II(D,A,B,C,X7,10,0x432aff97)

II(C,D,A,B,X14,15,0xab9423a7)

II(B,C,D,A,X5,21,0xfc93a039)

II(A,B,C,D,X12,6,0x655b59c3)

II(D,A,B,C,X3,10,0x8f0ccc92)

II(C,D,A,B,X10,15,0xffeff47d)

II(B,C,D,A,X1,21,0x85845dd1)

II(A,B,C,D,X8,6,0x6fa87e4f)

II(D,A,B,C,X15,10,0xfe2ce6e0)

II(C,D,A,B,X6,15,0xa3014314)

II(B,C,D,A,X13,21,0x4e0811a1)

II(A,B,C,D,X4,6,0xf7537e82)

II(D,A,B,C,X11,10,0xbd3af235)

II(C,D,A,B,X2,15,0x2ad7d2bb)

II(B,C,D,A,X9,21,0xeb868391)

在第i步中，ti是232×abs［sin(i)］的整數(shù)部分，i的單位是弧度。每512bit處理完后與上一輪結(jié)果相加(同MD4)，最后是A、B、C、D的級聯(lián)。5.2.6對散列函數(shù)的攻擊和安全性

1.生日攻擊

生日攻擊指攻擊者找到了與明文m有相同散列值的另一個不同的明文m′。之所以叫這樣一個名稱，是因?yàn)樗淄谒^生日問題：問一個班級至少有多少個學(xué)生，才能使兩個學(xué)生同一天生日的概率不小于1/2？首先任意指定一位學(xué)生報(bào)出自己的生日，在其余的學(xué)生中，第1位學(xué)生的生日不在這一天的概率是364/365=1-1/365，第2位學(xué)生的生日不在這兩天的概率是363/365=1-2/365……第j位學(xué)生的生日不在已被前面學(xué)生占用的j天的概率是1-j/365，因此，除了所有生日不相同的情況之外，就是出現(xiàn)兩個或更多學(xué)生生日在同一天的概率：(5-48)式中，N=365是一年的天數(shù)，J是班級里學(xué)生總數(shù)，p是出現(xiàn)兩人或多人生日相同的概率。由于：(5-49)當(dāng)x較小時有1-x≈e-x，因此，當(dāng)J<<N時，有解得：J-J2≈2Nln(1-p)忽略一次項(xiàng)J，得到：(5-49)當(dāng)p=0.5時，J≈22.49。這個答案是出乎意料的，僅僅23人就會有50%的概率出現(xiàn)兩人生日在同一天！類似的情況也會發(fā)生在電話號碼問題上。設(shè)某城市采用7位號碼，共有N=107個號碼可選擇，如果每個用戶都能不受限制地隨機(jī)選擇號碼，不難算出，只需J=3723部電話，出現(xiàn)重號的概率就會達(dá)到50%。

現(xiàn)在回到散列函數(shù)。nbit長的散列函數(shù)共有N=2n個不同的組合，兩個人生日相同在這里就是兩個不同明文m和m′有相同的摘要值，求學(xué)生數(shù)目J就是求明文數(shù)目J，問J多大時就有概率為p的可能出現(xiàn)兩摘要值相同的情況？由式(5-49)知明文數(shù)J正比于，即正比于。顯然，對于n=64的散列函數(shù)(比如用DES構(gòu)造),安全性是差了一些。安全的Hash函數(shù)規(guī)定n=160bit就是為了抵抗生日攻擊。

2.中間相迂攻擊中間相迂攻擊是針對分組鏈接結(jié)構(gòu)的散列函數(shù)進(jìn)行的。攻擊者隨意選出若干消息分組，將它們分為兩部分，一部分以初值IV開始迭代到中間某一步為止，得到J1個輸出；第二部分以摘要值h(x)出發(fā)，用逆函數(shù)反向迭代到中間某一步為止，得到J2個輸出；然后比較這兩部分輸出，若能找到一對輸出相等，則可得到一對“碰撞消息”。第一部分按進(jìn)行迭代(不妨假設(shè)t為偶數(shù))。第二部分按進(jìn)行迭代，其中E為加密函數(shù)，D為解密函數(shù)。即是的逆函數(shù)。因此兩部分中若有一對相等，即ht/2=

,則可將對應(yīng)的消息鏈成一個消息：,使。

由于x′是攻擊者隨機(jī)選的，因此可選x′=x。這樣就得到一對碰撞消息。為了找到這對碰撞消息，所需要選出的消息總數(shù)J=J1+J2。這時J不僅與分組加密函數(shù)的分組長度有關(guān)，也與函數(shù)的性質(zhì)有關(guān)。

實(shí)際上，攻擊的第一部分是選擇明文攻擊，第二部分是選擇密文攻擊，為了抵抗選擇明/密文攻擊，分組加密的分組長度至少應(yīng)128bit。防止中間相迂攻擊的另一方法是避免采用可逆的加解密函數(shù)。

3.修正分組攻擊

修正分組攻擊即偽造消息的一個分組，通常是最后那個分組，目的是要修正雜湊值，企圖使它等于某個期望的值，以達(dá)到偽造簽名的目的。5.3身份識別［4］

5.3.1概述

識別(identification)和驗(yàn)證(authentication)是不同的。數(shù)字簽名屬于身份驗(yàn)證，當(dāng)通信雙方或一方需要被驗(yàn)證時，通常存在一些承載信息在通信雙方之間交換。而識別是對一個用戶身份的實(shí)時證明，它不需要交換承載信息。身份識別廣泛地應(yīng)用在訪問控制中，根據(jù)身份識別決定允許或拒絕某用戶訪問相應(yīng)的資源，如出納機(jī)、登錄計(jì)算機(jī)、識別入網(wǎng)的移動電話等。

識別是基于非時變的口令或密碼的。這樣的系統(tǒng)，用戶和識別者都知道口令或密碼，識別者就有可能冒充用戶。實(shí)際上，無需讓識別者知道秘密口令，只要讓它有能力區(qū)別有效口令和無效口令即可。一種改進(jìn)的方法是通過單向函數(shù)將用戶輸入的口令加密，識別者的數(shù)據(jù)庫里只存儲著每個用戶的口令加密值。這樣改進(jìn)的系統(tǒng)也未必能十分安全，因?yàn)樗鼰o法抵制字典式攻擊。其次，當(dāng)用戶輸入口令時也難免被人窺視到。一個安全的識別協(xié)議至少應(yīng)該在證明自己身份時不泄露秘密。這可能嗎？完全可能！下面所舉的GSM身份識別就是這樣的強(qiáng)識別方案。(1)A通過密碼和用戶名向B登記(A為移動手機(jī)用戶，B為服務(wù)商網(wǎng)絡(luò))。

(2)B發(fā)給A一個隨機(jī)號碼(詢問)。

(3)A用自己的私鑰對這個隨機(jī)號碼加密后回答B(yǎng)。

(4)B驗(yàn)證回答正確，表明A確實(shí)擁有密鑰。竊聽者不能重發(fā)這個響應(yīng)，因?yàn)楫?dāng)他聯(lián)系B時，詢問已經(jīng)不同了。而密鑰在整個過程中并未泄露，竊聽者無法得到。當(dāng)然，這個方案是建立在A、B雙方互相信任的基礎(chǔ)之上的。然而很多情況下，雙方未必能互相信任，甚至還可能是敵對的,所以更加安全的識別方案應(yīng)該是不需要雙方共享秘密的方案。其識別協(xié)議至少應(yīng)包含以下兩條：(1)證明者A能向驗(yàn)證者B