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

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

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

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

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

計(jì)算各自的公開(kāi)密鑰:y=axmodp

公鑰是(y,a,p)

私鑰是(x)

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

計(jì)算K=ak(modp)

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

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

簽名是(K,S)

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

6.ElGamal簽名方案舉例

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

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

36.63=25mod11

3.7=32=10mod11

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

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

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

每個(gè)用戶選取私鑰并計(jì)算他們的公鑰:選取x<q

計(jì)算y=gx(modp)

9.DSA簽名生成與驗(yàn)證

簽名消息M生成隨機(jī)簽名蜜鑰k,k<q

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

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

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

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

u2=r.w(modq)

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

v=r簽名有效

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

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

KeyedHash=Hash(Key|Message)

有一些弱點(diǎn)隨后建議:

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)過(guò)填充的密鑰opad,ipad特殊的填充值Opad=01011010重復(fù)b/8次

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

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

HMAC練習(xí)

/zhengdongIllustratetheoperationofElGamalsignatures,giventhefollowingparameters:primep=31