數(shù)字簽名算法培訓(xùn)講學(xué)

第十二講數(shù)字簽名算法上海交通大學(xué)計算機科學(xué)與工程系鄭東要求：掌握數(shù)字簽名的基本原理及用途掌握RSA,ElGamal,DSA數(shù)字簽名算法1.數(shù)字簽名方案公鑰簽名方案：利用私鑰生成簽名利用公鑰驗證簽名只有私鑰的擁有者才能生成簽名所以能夠用于證明誰生成的消息任何知道公鑰的人可以驗證消息（他們要確認(rèn)公鑰擁有者的身份，這是公鑰的密鑰分配問題）通常不對整個消息簽名，因為這將會使交換信息長度增加一倍使用消息的hash值數(shù)字簽名可以提供消息的不可否認(rèn)性,3.RSA使用

使用RSA加密、認(rèn)證：使用發(fā)送者的私鑰簽名一個消息使用接收者的公鑰加密消息看起來，一個消息可用RSA加密、簽名而不改變大小但是，加密使用的是消息接收者的模，簽名是消息發(fā)送者的模，后著可能比前者小交換兩者順序？簽名常使用HASH函數(shù)值

4.ElGamalSignatureSchemeElGamal加密算法是不可交換的存在一個相關(guān)的簽名算法安全性是基于計算離散對數(shù)的困難性方案的密鑰生成是相同的:有個共享的素數(shù)p,公開的本原根a

每個用戶選擇一個隨機數(shù)作為私鑰x

計算各自的公開密鑰:y=axmodp

公鑰是(y,a,p)

私鑰是(x)

5.ElGamal簽名方案的使用簽名消息M:選擇隨機數(shù)k,GCD(k,p-1)=1

計算K=ak(modp)

用Euclidean(inverse)擴展算法求S:

M=x.K+k.Smod(p-1);即求S=k-1(M-x.K)mod(p-1)

簽名是(K,S)

k應(yīng)該被銷毀同ElGamal加密方案，簽名信息也是消息的2倍驗證(K,S)是對M的簽名:yK.KSmodp=aMmodp

6.ElGamal簽名方案舉例

取p=11,g=2選擇私鑰x=8計算:y=axmodp=28mod11=3公鑰是:y=3,g=2,p=11對M=5簽名：選擇隨機數(shù)k=9確定gcd(10,9)=1計算:K=akmodp=29mod11=6解:5=8.6+9.Smod10;nb9-1=9mod10;

因此S=9.(5-8.6)=3mod10簽名是(K=6,S=3)要驗證簽名,確認(rèn):

36.63=25mod11

3.7=32=10mod11

7.DSA(DigitalSignatureAlgorithm)USFederalGovtapprovedsignaturescheme(FIPSPUB186)使用SHAhashalgNIST&NSA在90‘s初設(shè)計DSA是算法,DSS是標(biāo)準(zhǔn)對此標(biāo)準(zhǔn)宣布的爭議!是否需要使用RSADSA是ElGamal及Schnorralgorithms的變形生成320bit簽名安全性是基于離散對數(shù)被廣泛接收8.DSA密鑰生成首先選取公開參數(shù)(p,q,g):選取大素數(shù)p=2L

L=512to1024bits（64倍數(shù)）選取q,160bit素因子（ofp-1）選擇g=h(p-1)/q

對任何h<p-1,h(p-1)/q(modp)>1

每個用戶選取私鑰并計算他們的公鑰:選取x<q

計算y=gx(modp)

9.DSA簽名生成與驗證

簽名消息M生成隨機簽名蜜鑰k,k<q

計算r=(gk(modp))(modq)

s=k-1.SHA(M)+x.r(modq)

發(fā)送簽名(r,s)及消息M驗證簽名,計算:w=s-1(modq)

u1=(SHA(M).w)(modq)

u2=r.w(modq)

v=(gu1.yu2(modp))(modq)

v=r簽名有效

10.DSA安全性基于離散對數(shù)最初建議使用一個共同的modulusp現(xiàn)在建議不同的工作組使用不同的(p,q,g)GusSimmons發(fā)現(xiàn)存在潛信道，能夠泄露私鑰13.帶密鑰的HASH

以上的簽名方法都是公鑰技術(shù)計算與數(shù)據(jù)量較大需要私鑰的認(rèn)證方案好的方法是使用快速的hash函數(shù)：密鑰與消息同時參加運算:

KeyedHash=Hash(Key|Message)

有一些弱點隨后建議:

KeyedHash=Hash(Key1|Hash(Key2|Message))

14.HMAC

HMAC是使用帶密鑰的HASH函數(shù)的結(jié)果成為internet標(biāo)準(zhǔn)(RFC2104)結(jié)構(gòu)：HMACK=Hash((K+XORopad)||Hash((K+XORipad)||M))

K+是經(jīng)過填充的密鑰opad,ipad特殊的填充值Opad=01011010重復(fù)b/8次

ipad=00110110重復(fù)b/8次安全性是基于原來的HASH函數(shù)的安全性任何MD5,SHA-1,RIPEMD-160都可以這樣使用

15.小結(jié)數(shù)字簽名(RSA,ElGamal,DSA,)

HMAC練習(xí)

/zhengdongIllustratetheoperationofElGamalsignatures,giventhefollowingparameters:primep=31