第三章-數(shù)據(jù)的完整性保護(hù)(last1)

第三章數(shù)據(jù)的完整性愛護(hù)3、1消息摘錄技術(shù)

一、基本原理

消息摘錄（messagedigests）：是單向的散列函數(shù)（即Hash函數(shù)），它以變長的消息為輸入，把其壓縮成一個(gè)定長的值輸出。若輸入的信息被變更了，則輸出的定長值（摘錄）也會相應(yīng)變更。依據(jù)Hash函數(shù)（即消息摘錄函數(shù)）的平安水平，人們將Hash函數(shù)分成兩大類：一類是強(qiáng)碰撞自由的Hash函數(shù)(strongcollision-freehashfunction)；另一類是弱碰撞自由的Hash函數(shù)(weakcollision-freehashfunctions).一個(gè)強(qiáng)碰撞自由的Hash函數(shù)是滿足下列條件的一個(gè)函數(shù)h：

（1）

h的輸入可以是隨意長度的任何消息或文件M；（2）h輸出的長度是固定的（該長度必需足夠長，以反抗所謂的生日攻擊，依據(jù)今日的計(jì)算技術(shù)和實(shí)力，至少應(yīng)為128比特長）；（3）給定h和m，計(jì)算h（M）是簡潔的；

（4）給定h的描述，找兩個(gè)不同的消息（信息）M1和M2，使得h（M1）=h（M2）是計(jì)算上不行行的。（假如這兩個(gè)消息M1，M2，M1≠M(fèi)2，使得h（M1）=h（M2），則稱這兩個(gè)消息是碰撞消息或稱這兩個(gè)消息碰撞。）

一個(gè)弱碰撞自由的Hash函數(shù)與一個(gè)強(qiáng)碰撞自由的Hash函數(shù)的前三個(gè)條件（1）-（3）完全一樣，不同的只是第（4）個(gè)條件。在一個(gè)弱碰撞自由的Hash函數(shù)中。（5）給定h的描述和一個(gè)隨機(jī)選擇的消息M1，找另一個(gè)消息M2，M2≠M(fèi)1，使得h（M1）=h（M2）是計(jì)算上不行行的。實(shí)際受到的附件附件所期望的附件如果兩者一樣，則認(rèn)為消息是完整的產(chǎn)生附件消息附件產(chǎn)生附件消息消息接收者發(fā)送者傳輸?shù)南⒈容^一般的封裝機(jī)制二、消息摘錄技術(shù)的應(yīng)用

1、用于計(jì)算消息完整碼

消息m附件F將F′與收到的附件F進(jìn)行比較假如F′=F則認(rèn)為消息是完整的，否則不是完整的消息m附件FMD（m|KAB）重新依據(jù)m,由m|KAB計(jì)算附件F′消息m密匙KAB消息m發(fā)方A收方B傳輸?shù)南?、運(yùn)用MD進(jìn)行雙向鑒別rArBABMD(KAB│rA)MD(KAB│rA)基于的雙向MD鑒別機(jī)制一、概述MD4的設(shè)計(jì)是面對32比特字的，更適合于32位計(jì)算機(jī)，效率比MD2高。MD4計(jì)算出的消息摘錄長度為128比特，用4個(gè)字表示，分別記為A，B，C，D，在計(jì)算起先時(shí)被分別初始化為常數(shù)。輸入信息被分成512比特的等長塊，逐塊處理。每塊包含16個(gè)字，分別記為m0，m1，……m15。每塊的處理分三遍掃描，每遍對A，B，C，D運(yùn)用不同的擾亂函數(shù)。在處理前需將當(dāng)前的消息摘錄備份，在處理后將這個(gè)備份加到新產(chǎn)生的消息摘錄上，并將其作為下一塊處理時(shí)消息摘錄的當(dāng)前值。最終一塊信息處理之后的消息摘錄當(dāng)前值，即為最終的消息摘錄值。3.1.1、

MD4二、MD4信息填充

給定一個(gè)X，將X進(jìn)行填充，使其成為一個(gè)512比特的倍數(shù)串M=M[0]M[1]……M[N-1]，這里每個(gè)M[i](0≤i≤N-1)是長為32比特的串，N≡0(mod16)（即N是16的倍數(shù)。）我們將每個(gè)M[i]稱為一個(gè)字（32位），由X產(chǎn)生M的算法如下：

⑴d=447-(│x│mod512)（當(dāng)d<0時(shí)，按模512處理）⑵l表示x的長度，即│x│。│l│=64（即用64比特表示x的長度）⑶M=x‖1‖0d‖l初始信息（x）100……0初始信息的比特?cái)?shù)（l）即使原來的信息已是512比特的倍數(shù)，也要進(jìn)行填充。

三、干脆構(gòu)造法現(xiàn)在我們從M起先構(gòu)造一個(gè)128比特長的消息摘錄，其構(gòu)造過程如下：（1）給四個(gè)寄存器A、B、C、D賦初始值（用十六進(jìn)制表示）：A=67452301B=efcdab89C=98badcfeD=10325476（2）fori=0toN/16-1do；（3）forj=0to15dom[j]=M[16i+j]

（4）將四個(gè)寄存器A、B、C、D的值存儲到另外四個(gè)寄存器AA，BB，CC，DD之中，AA=A；BB=B；CC=C；DD=D（5）執(zhí)行第一輪；（6）執(zhí)行其次輪；（7）執(zhí)行第三輪；（8）A=A+AA；B=B+BB；C=C+CC；D=D+DD[X]—取整—二進(jìn)制求補(bǔ)；x∧y—x與y按位邏輯“與（and）”；x∨y—x與y按位邏輯“或（or）”；xy—x與y按位邏輯“異或（xor）”；

x+y—二進(jìn)制加運(yùn)算（即整數(shù)模232加法運(yùn)算）；x<<y—x循環(huán)左移y個(gè)位置（0≤y≤31）。

MD4中的三個(gè)輪是不同的。1、第一輪第一輪運(yùn)用一個(gè)如下定義的函數(shù)f（x，y，z）=（x∧y）∨（x∧z）(1）fork=0to3do；（2）

A=（A+f（B，C，D））+m[4k]<<3（3）

D=（D+f（A，B，C））+m[4k+1]<<7（4）

C=（C+f（D，A，B））+m[4k+2]<<11(5)B=（B+f（C，D，A））+m[4k+3]<<152、其次輪其次輪運(yùn)用一個(gè)如下定義的函數(shù)：g（x，y，z）=（x∧y）∨（x∧z）∨（y∧z）取常數(shù)C2=[2]=5a827999H

留意：在其次輪中m[i]不是依次處理的。1）A=（A+g（B，C，D）+m[0]+5a827999）<<3；2）D=（D+g（A，B，C）+m[4]+5a827999）<<5；3）C=（C+g（D，A，B）+m[8]+5a827999）<<9；4）B=（B+g（C，D，A）+m[12]+5a827999）<<13；5）A=（A+g（B，C，D）+m[1]+5a827999）<<3；

(6)D=（D+g（A，B，C）+m[5]+5a827999）<<5；(7)C=（C+g（D，A，B）+m[9]+5a827999）<<9；(8)B=（B+g（C，D，A）+m[13]+5a827999）<<13；(9)A=（A+g（B，C，D）+m[2]+5a827999）<<3；(10)D=（D+g（A，B，C）+m[6]+5a827999）<<5；(11)C=（C+g（D，A，B）+m[10]+5a827999）<<9；(12)B=（B+g（C，D，A）+m[14]+5a827999）<<13；(13)A=（A+g（B，C，D）+m[3]+5a827999）<<3；(14)D=（D+g（A，B，C）+m[7]+5a827999）<<5;(15)C=（C+g（D，A，B）+m[11]+5a827999）<<9；(16)B=（B+g（C，D，A）+m[15]+5a827999）<<13；

第三輪第三輪定義擾亂函數(shù)如下：h（X，y，Z）=xyz取常數(shù)C3=[2]=6edgebalH

與其次遍掃描類似，第三遍掃描時(shí)對Mi的處理也不是依次的，具體為:(1)A=（A+h（B，C，D）+m[0]+C3）<<3；(2)D=（D+h（A，B，C）+m[8]+C3）<<9；(3)C=（C+h（D，A，B）+m[4]+C3）<<11；(4)B=（B+h（C，D，A）+m[12]+C3）<<15；(5)A=（A+h（B，C，D）+m[2]+C3）<<3；

(6)D=（D+h（A，B，C）+m[10]+C3）<<9；(7)C=（C+h（D，A，B）+m[6]+C3）<<11；(8)B=（B+h（C，D，A）+m[14]+C3）<<15；(9)A=（A+h（B，C，D）+m[1]+C3）<<3；（10）D=（D+h（A，B，C）+m[9]+C3）<<9；（11）C=（C+h（D，A，B）+m[5]+C3）<<11；（12）B=（B+h（C，D，A）+m[13]+C3）<<15；（13）A=（A+h（B，C，D）+m[3]+C3）<<3；（14）D=（D+h（A，B，C）+m[11]+C3）<<9；（15）C=（C+h（D，A，B）+m[7]+C3）<<11；（16）B=（B+h（C，D，A）+m[15]+C3）<<15；MD5第一輪F(x,y,z)=(xΛy)V(Λz)A=B+((A+f(B,C,D)+m[0]+d7aa78)<<7)D=A+((D+f(A,B,C)+m[1]+e8c7b756)<<12)C=D+((C+f(D,A,B)+m[2]+242070db)<<17)B=C+((B+f(C,D,A)+m[3]+c1bdceee)<<22)A=B+((A+f(B,C,D)+m[4]+f57c0faf)<<7)D=A+((D+f(A,B,C)+m[5]+4787c62a)<<12)C=D+((C+f(D,A,B)+m[6]+a8304613)<<17)B=C+((B+f(C,D,A)+m[7]+fd469501)<<22)A=B+((A+f(B,C,D)+m[8]+698098db)<<7)D=A+((D+f(A,B,C)+m[9]+8b44f7af)<<12)C=D+((C+f(D,A,B)+m[10]+ffff5bb1)<<17)B=C+((B+f(C,D,A)+m[11]+895cd7be)<<22)A=B+((A+f(B,C,D)+m[12]+6b901122)<<7)D=A+((D+f(A,B,C)+m[13]+fd987193)<<12)C=D+((C+f(D,A,B)+m[14]+a679438e)<<17)B=C+((B+f(C,D,A)+m[15]+49b40821)<<22)其次輪g(x,y,z)=(xΛz)V(yΛ)A=B+((A+g(B,C,D)+m[1]+f61e2562)<<5)D=A+((D+g(A,B,C)+m[6]+c04ob34o)<<9)C=D+((C+g(D,A,B)+m[11]+265e5a51)<<14)B=C+((B+g(C,D,A)+m[0]+egb6c7aa)<<20)A=B+((A+g(B,C,D)+m[5]+d62f105d)<<5)D=A+((D+g(A,B,C)+m[10]+02441453)<<9)C=D+((C+g(D,A,B)+m[15]+d8a1e681)<<14)B=C+((B+g(C,D,A)+m[4]+e7d3fbc8)<<20)A=B+((A+g(B,C,D)+m[9]+21e1cde6)<<5)D=A+((D+g(A,B,C)+m[14]+c33707d6)<<9)C=D+((C+g(D,A,B)+m[3]+f4d5od87)<<14)B=C+((B+g(C,D,A)+m[8]+455a14ed)<<20)A=B+((A+g(B,C,D)+m[13]+a9e3e9o5)<<5)D=A+((D+g(A,B,C)+m[2]+fcefa3f8)<<9)C=D+((C+g(D,A,B)+m[7]+676fo2d9)<<14)B=C+((B+g(C,D,A)+m[12]+8d2a4c8a)<<20)第三輪h(x,y,z)=x⊕y⊕zA=B+((A+h(B,C,D)+m[5]+fffa3942)<<4)D=A+((D+h(A,B,C)+m[8]+8771f681)<<11)C=D+((C+h(D,A,B)+m[11]+6d9d6122)<<16)B=C+((B+h(C,D,A)+m[14]+fde5380c)<<23)A=B+((A+h(B,C,D)+m[1]+a4beea44)<<4)D=A+((D+h(A,B,C)+m[4]+4dbecfa9)<<11)C=D+((C+h(D,A,B)+m[7]+f6b46bo)<<16)B=C+((B+h(C,D,A)+m[10]+bebfbc70)<<23)A=B+((A+h(B,C,D)+m[13]+289b7ecb)<<4)D=A+((D+h(A,B,C)+m[0]+eaa127fa)<<11)C=D+((C+h(D,A,B)+m[3]+d4ef3085)<<16)B=C+((B+h(C,D,A)+m[6]+04881d05)<<23)A=B+((A+h(B,C,D)+m[9]+d9d4d039)<<4)D=A+((D+h(A,B,C)+m[12]+e6db99e5)<<11)C=D+((C+h(D,A,B)+m[15]+1fa27cf8)<<16)B=C+((B+h(C,D,A)+m[2]+c4ac5665)<<23)第四輪I(x,y,z)=y⊕(xV)A=B+((A+I(B,C,D)+m[0]+f4292244)<<6)D=A+((D+I(A,B,C)+m[7]+432aff97)<<10)C=D+((C+I(D,A,B)+m[14]+ab9423a7)<<15)B=C+((B+I(C,D,A)+m[5]+fc93a039)<<21)A=B+((A+I(B,C,D)+m[12]+655b59c3)<<6)D=A+((D+I(A,B,C)+m[3]+8foccc92)<<10)C=D+((C+I(D,A,B)+m[10]+ffeff47d)<<15)B=C+((B+I(C,D,A)+m[1]+85845dd1)<<21)A=B+((A+I(B,C,D)+m[8]+6fa87e4f)<<6)D=A+((D+I(A,B,C)+m[15]+fe2ce6e0)<<10)C=D+((C+I(D,A,B)+m[6]+a3014314)<<15)B=C+((B+I(C,D,A)+m[13]+4e0811a1)<<21)A=B+((A+I(B,C,D)+m[4]+f7537e82)<<6)D=A+((D+I(A,B,C)+m[11]+bd3af235)<<10)C=D+((C+I(D,A,B)+m[2]+2ad7d2bb)<<15)B=C+((B+I(C,D,A)+m[9]+eb86d391)<<21)

常數(shù)可以如下選擇:在第i步中,是×|sin(i)|的整數(shù)部分，i的單位是弧度。全部這些完成之后，將A,B,C,D分別加上AA,BB,CC,DD，然后用下一組數(shù)據(jù)接著運(yùn)行算法，最終的輸出是A,B,C和D的級聯(lián)，即128位長的字。對單輪的MD5已有攻擊結(jié)果，但對4輪MD5則還沒有有效的方法。即使接受生日攻擊，找尋具有相同Hash值的兩個(gè)信息須要試驗(yàn)個(gè)信息，而差分攻擊也對MD5的平安性步構(gòu)成威逼。MD5與MD4相比較,主要作了以下六點(diǎn)改進(jìn):

(1)增加了第四輪，第四輪所運(yùn)用的函數(shù)為Ⅰ（x，y，z）=（x∨）y；(2)其次輪的函數(shù)g變?yōu)間（x，y，z）=（x∧z）∨（y∧），以減弱它的對稱性；(3)進(jìn)入其次輪和第三輪的輸入字的次序被改變；(4)每一輪中的移位數(shù)已變更，并且各輪中的移位數(shù)互不相同；(5)每一步有一個(gè)唯一的加法常數(shù)；(6)每一步加上了上一步的結(jié)果，這樣會產(chǎn)生更好的“雪崩效應(yīng)”。3.1.2Hash函數(shù)的攻擊方法

生日攻擊生日攻擊這個(gè)術(shù)語來自于所謂的生日問題：在一個(gè)教室中最少應(yīng)有多少學(xué)生,才使得至少有兩個(gè)學(xué)生的生日在同一天的概率不小于？設(shè)h∶x→y是一個(gè)Hash函數(shù)，x和y都是有限的集合，并且│x│=m，│y│=n。明顯至少有個(gè)碰撞，問題是如何去找這些碰撞。一個(gè)很自然的方法是隨機(jī)選擇k個(gè)不同的元素x1，x2，…，xk∈x，計(jì)算yi=h(xi)，1≤i≤k，然后確定是否有一個(gè)碰撞發(fā)生。

這表明，僅雜湊（隨機(jī)拼湊）個(gè)x的隨機(jī)的元素就能以50%的概率產(chǎn)生一個(gè)碰撞。留意:的不同選擇將導(dǎo)致一個(gè)不同的常數(shù)因子，但k與仍成正比例。如前面的例子，x是一個(gè)教室中全部學(xué)生的集合，y是一個(gè)非潤年的365天的集合，h(x)表示學(xué)生x的生日，現(xiàn)在我們類處理生日問題。這時(shí)n=365,=,由k≈1.17,=1.17,≈22.3，知教室中至少要有23名學(xué)生。生日攻擊隱含著消息摘要的長度的一個(gè)下界。3．2數(shù)字簽名技術(shù)一、數(shù)字簽名為了具有通常手書簽名的功效，數(shù)字簽名應(yīng)滿足以下條件：（1）收方能夠鑒別其收到的報(bào)文的確是發(fā)方發(fā)送來的，其內(nèi)容是真實(shí)的；（2）發(fā)方事后不能依據(jù)自己的利益來否認(rèn)他所發(fā)送過的報(bào)文；（3）包括收方在內(nèi)的任何人都不能偽造報(bào)文或簽名。二、利用公鑰密碼體制實(shí)現(xiàn)的數(shù)字簽名1、在公鑰密碼系統(tǒng)的通信中，實(shí)現(xiàn)數(shù)據(jù)的保密性和真實(shí)性。(1)數(shù)據(jù)的保密性設(shè)用戶A要發(fā)送消息M給用戶B，AB,為了使M在傳送過程中不被泄露，A可用B的公開密鑰PKB對M加密，將密文傳送給B。

M→→DSKB（EPKB（M））=M↑↑A方PKBSKBB方ED用公鑰體制實(shí)現(xiàn)數(shù)據(jù)的保密性。

(2)數(shù)據(jù)的真實(shí)性條件：該公鑰密碼體制的公開密鑰既能作加密密鑰，又能作解密密鑰運(yùn)用，即DSK（EPK（M））=EPK（DSK（M））=MM→→M=EPKA（DSKA（M））↑↑A方SKAPKAB方ED公鑰密碼體制實(shí)現(xiàn)真實(shí)性。（丟失了保密性）

(3)既實(shí)現(xiàn)數(shù)據(jù)的保密性又實(shí)現(xiàn)數(shù)據(jù)的真實(shí)性

數(shù)據(jù)M→→→→M↑↑↑↑A方SKAPKBSKBPKAB方

DEDE用公鑰密碼體制實(shí)現(xiàn)數(shù)據(jù)的保密性和真實(shí)性

2、用公鑰密碼體制實(shí)現(xiàn)的數(shù)字簽名

設(shè)A要向B發(fā)送一份報(bào)文M，該報(bào)文由兩部分組成：一部分稱作報(bào)頭H，它包括發(fā)方的身份，收方的身份及發(fā)送序號等。即H=〈發(fā)方的ID〉，〈收方的ID〉，〈發(fā)送序號〉；另一部分是要發(fā)送的報(bào)文數(shù)據(jù)M，若須要可附上時(shí)間T。簽名者用他的隱私密鑰SKA對M或（M，T）進(jìn)行變換（解密運(yùn)算）得S=DSKA（M）或S=DSKA（M，T），實(shí)現(xiàn)對報(bào)文的簽名，然后用收方B的公開密鑰PKB對MS=（H，S）進(jìn)行加密運(yùn)算，并將結(jié)果EPKB（MS）發(fā)送給B，實(shí)現(xiàn)保密通信。M→→→M↑↑↑↑A方SKAPKBSKBPKAB方

DEDDHH簽名保密通信加密脫密

驗(yàn)證簽名

B收到報(bào)文后操作：

（1）B用自己的隱私密鑰SKB先對收到的報(bào)文解密，得MS，依據(jù)H中的信息識別動身送者的身份是A。（2）在公開的簽名信息簿中查出A用于簽名驗(yàn)證的公開密鑰PKA。（3）用PKA對S進(jìn)行變換EPKA（S）=EPKA（DSKA（M′））=M。

（4）檢查M′是否正確。

三、基于對稱密碼體制的數(shù)字簽名L—D方法利用一組密鑰，其個(gè)數(shù)由報(bào)文的長度確定，對報(bào)文進(jìn)行逐位的簽名。L—D方法分為準(zhǔn)備、簽名和驗(yàn)證三部分。準(zhǔn)備的內(nèi)容為：（1）若報(bào)文長度為n，則設(shè)置由發(fā)方A隱私保存的2n個(gè)簽名密鑰，記為λ1，μ1，λ2，μ2，……，λn，μn；（2）A隨機(jī)地選擇2n個(gè)數(shù)：u1，u2，……，un

U1，U2，……，Un

并分別用第一步產(chǎn)生的密鑰對這2n個(gè)數(shù)據(jù)加密，得到2n個(gè)密文：vi=Eλi(ui)i=1,2,……，nvi=Eμi(ui)i=1,2,……，n

A將u1,u2,u3,……,unu1,u2,u3,……,un這2n個(gè)數(shù)據(jù)和2n個(gè)密文v1,v2,v3,……,vnv1,v2,v3,……,vn作密文驗(yàn)證信息公開交給B和仲裁者。(3)若報(bào)文M=m1m2……mn的第i位mi為1，則簽名的第i位取μi，否則取λi，最終構(gòu)成一個(gè)元素個(gè)數(shù)與報(bào)文長度相同的密鑰序列。SA=K1K2……Kn。

Ki=μimi=1λimi=0i=1,2,……n其中A將A將SA留底后，發(fā)送給B.B收B收到簽名數(shù)據(jù)后，驗(yàn)證簽名的方法為：依據(jù)報(bào)文的內(nèi)容確定密鑰的內(nèi)容，然后按報(bào)文的各位依據(jù)預(yù)先計(jì)算好的那兩組數(shù)來驗(yàn)證收到的簽名是否正確；（4）B用Ki分別對vi和Vi解密，若解得明文為ui，則斷定mi=0；若為Ui，則斷定mi=1。否則說明簽名有錯誤或有篡改偽造行為。

0Dki(vi)=ui1Dki(Vi)=UiMi=B將收到的SA留底。

該方法存在兩個(gè)嚴(yán)峻缺陷：

（1）簽名比報(bào)文長的多，例如若運(yùn)用DES作為加密算法，則每個(gè)密鑰有56位，即簽名的長度是報(bào)文長度的56倍。（2）簽名密鑰若不接受一次一密方式，則每次簽名都會把n個(gè)密鑰泄露出去，重復(fù)運(yùn)用相同的簽名密鑰是很擔(dān)憂全的；而一次一密的密鑰管理負(fù)擔(dān)很重。

四、仲裁者簽名

通過第三者介入的傳統(tǒng)密碼數(shù)字簽名（仲裁簽名）

通信的雙方A，B把各自的隱私密鑰交給可信的第三者了，通信過程如圖所示，設(shè)發(fā)方A要將信息M發(fā)送給B。S方仲裁者M(jìn)→A方↑KAEM=DKA(C)C’=EKB(M)C’=EKB(M)D←KBB方3.3數(shù)字簽名標(biāo)準(zhǔn)一.素根離散對數(shù)是很多公開密鑰算法，包括Diffie-Klellman密鑰交換算法及數(shù)字簽名（DSA）的基礎(chǔ)。本節(jié)對離散對數(shù)做一個(gè)簡潔的概述。歐拉定理1modn現(xiàn)在考慮更一般的表達(dá)式：假如（a,n）=1，那么至少有一個(gè)整數(shù)m滿足公式（*），即m=。滿足公式（*）的最小指數(shù)m又稱為以下幾種方式：（1）a(modn)的階。（2）a屬于(modn)的指數(shù)。（3）a的生成周期長度。(*)1modn表7.6一般地，使1modn成立的最小正整數(shù)m，最高可能指數(shù)是，假如是a(modn)的階，則a就是n的一個(gè)素根。這個(gè)概念的重要性是假如a是n的一個(gè)素根，則它的指數(shù)a,是（modn）各不相同的且均與n互素。特殊地，對一個(gè)素?cái)?shù)p，假如a是p的一個(gè)素根，那么a,是（modp）各不相同的。對素?cái)?shù)19，它的素根是2,3,10,13,14和15。指數(shù)及離散對數(shù)對于底數(shù)x和一個(gè)值y，有于是

對數(shù)包括如下性質(zhì)：考慮某個(gè)素?cái)?shù)p（也可運(yùn)用非素?cái)?shù)）的一個(gè)素根a,那么a從1到p-1的冪將產(chǎn)生從表面上1到p-1的一個(gè)置換（排列）。此外，依據(jù)模運(yùn)算的定義，任何整數(shù)均能表示為：br(modp)于是對任何整數(shù)b和素?cái)?shù)p的素根a，總可以找到唯一的指數(shù)使得b其中指數(shù)i稱為數(shù)b以a（modp）為底數(shù)的指數(shù)，記為留意因?yàn)?[]歸納可得[]這說明真正的對數(shù)與指數(shù)很類似。正是由于這個(gè)緣由，后者常被成為離散對數(shù)（discretelegarithms）。表7.7模19的離散對數(shù)（a）以2為底模19的離散對數(shù)A123456789101112131415161718181132161463817121557114109

(b)以3為底模19的離散對數(shù)表A123456789101112131415161718187114486321112151713510169

數(shù)字簽名標(biāo)準(zhǔn)DSS數(shù)據(jù)簽名標(biāo)準(zhǔn)（DigitalSignatureStandard--DSS）是美國NIST（美國國家標(biāo)準(zhǔn)技術(shù)探討所）于己于1991年8月建議的一種基于非對稱加密體制的數(shù)據(jù)簽名實(shí)現(xiàn)方法。DSS的平安性表現(xiàn)在：（1）對報(bào)文的簽名不會引起密鑰的泄漏；（2）若不知系統(tǒng)的私鑰x，無人能夠?qū)o定的報(bào)文產(chǎn)生簽名；（3）無人能夠產(chǎn)生匹配給定簽名的報(bào)文；（4）無人能夠修改報(bào)文而還使原有的簽名照舊有效。DSS算法包括下列內(nèi)容：（1）選擇p和q（公開的信息）q是160位的素?cái)?shù)，p是512位—1024位的一個(gè)素?cái)?shù)，(其中，且L為64的倍數(shù)：即比特長度在512到1024之間，長度增量為64bit。)且有p=kq+1（）。q和p的選擇是很花費(fèi)時(shí)間的，因此可運(yùn)用標(biāo)準(zhǔn)中建議的數(shù)據(jù)。但是由于公布的質(zhì)數(shù)有可能是陷門數(shù)據(jù)（即不是真的質(zhì)數(shù)），所以在實(shí)現(xiàn)DSS算法時(shí)可考慮自己選擇適應(yīng)的數(shù)據(jù)。（2）產(chǎn)生g（公開的信息）找尋整數(shù)g（不應(yīng)為1），使得1modp

g的計(jì)算可接受如下步驟：1取一隨機(jī)數(shù)，令g;2依據(jù)費(fèi)馬定理（1modp）(或由Eular定理p是素?cái)?shù)，故1modp即1modp）modp留意（p,q,g）稱為全局公開密鑰重量。

選擇公開/私有密鑰對<y,x>1隨機(jī)選取1<x<q,將x作為私鑰；

2公開密鑰y由y=計(jì)算得出。

（4）計(jì)算消息M的簽名附件（r,s）1用戶隨機(jī)地選取一個(gè)整數(shù)k(0<k<q);2計(jì)算r=()modq;3利用Eclid算法，順便計(jì)算，這里表示kmodq的乘法逆，即4計(jì)算報(bào)文M的消息摘要H(M)；5計(jì)算報(bào)文的簽名于是構(gòu)成了消息H(M)的簽名附件（r,s）

（5）向接受方B傳送報(bào)文M，H(M)和（r,s）；（6）接收方用如下步驟驗(yàn)證簽名：1接收者首先檢測收到的消息的簽名（）

若中有一個(gè)不成立，則拒絕接收該簽名。2否則，接收者由和計(jì)算出v值，計(jì)算過程如下：

3比較v和，若則認(rèn)為簽名是有效的，否則認(rèn)為是無效簽名。在DSS算法中當(dāng)v=r時(shí)，簽名驗(yàn)證的有效性證明如下。引理1對任何整數(shù)t,若則