《《數(shù)字簽名算法》PPT課件.ppt》由會員分享,可在線閱讀,更多相關(guān)《《數(shù)字簽名算法》PPT課件.ppt(16頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、第十二講 數(shù)字簽名算法,上海交通大學計算機科學與工程系,鄭東,要求: 掌握數(shù)字簽名的基本原理及用途 掌握RSA, ElGamal, DSA數(shù)字簽名算法,1. 數(shù)字簽名方案,公鑰簽名方案: 利用私鑰生成簽名 利用公鑰驗證簽名 只有私鑰的擁有者才能生成簽名 所以能夠用于證明誰生成的消息 任何知道公鑰的人可以驗證消息 (他們要確認公鑰擁有者的身份,這是公鑰的密鑰分配問題) 通常不對整個消息簽名,因為這將會使交換信息長度增加一倍 使用消息的 hash 值 數(shù)字簽名可以提供消息的不可否認性,,2. RSA,RSA 加密解密是可交換的 可以用于數(shù)字簽名方案 給定 RSA 方案 (e,R), (d,p,q)
2、 要簽名消息M:計算: S = Md(mod R) 要驗證簽名,計算: M = Se(mod R) = Me.d(mod R) = M(mod R),3. RSA 使用,使用RSA加密、認證: 使用發(fā)送者的私鑰簽名一個消息 使用接收者的公鑰加密消息 看起來,一個消息可用RSA加密、簽名而不改變大小 但是,加密使用的是消息接收者的模,簽名是消息發(fā)送者的模,后著可能比前者小 交換兩者順序? 簽名常使用HASH函數(shù)值,4. El Gamal Signature Scheme,ElGamal 加密算法是不可交換的 存在一個相關(guān)的簽名算法 安全性是基于計算離散對數(shù)的困難性 方案的密鑰生成是相同的: 有個
3、共享的素數(shù) p, 公開的本原根 a 每個用戶選擇一個隨機數(shù)作為私鑰 x 計算各自的公開密鑰: y = ax mod p 公鑰是 (y,a,p) 私鑰是 (x),5. El Gamal 簽名方案的使用,簽名消息 M: 選擇隨機數(shù) k, GCD(k,p-1)=1 計算 K = ak(mod p) 用 Euclidean (inverse) 擴展算法求 S:M = x.K + k.S mod (p-1); 即求 S = k-1(M - x.K) mod (p-1) 簽名是 (K,S) k 應(yīng)該被銷毀 同ElGamal 加密方案, 簽名信息也是消息的2倍 驗證 (K,S) 是 對M的簽名: yK.KS
4、mod p = aMmod p,6. ElGamal 簽名方案舉例,取 p=11, g=2 選擇私鑰 x=8 計算: y = ax mod p = 28 mod 11 = 3 公鑰是: y=3,g=2,p=11 對 M=5 簽名: 選擇隨機數(shù) k=9 確定 gcd(10,9)=1 計算: K = ak mod p = 29 mod 11 = 6 解: 5 = 8.6+9.S mod 10; nb 9-1 = 9 mod 10;因此 S = 9.(5-8.6) = 3 mod 10 簽名是 (K=6,S=3) 要驗證簽名, 確認:36.63 = 25 mod 113.7 = 32 = 10 mo
5、d 11,7. DSA (Digital Signature Algorithm),US Federal Govt approved signature scheme (FIPS PUB 186) 使用 SHA hash alg NIST & NSA 在 90s初設(shè)計 DSA 是算法, DSS 是標準 對此標準宣布的爭議! 是否需要使用 RSA DSA 是 ElGamal 及Schnorr algorithms 的變形 生成 320 bit 簽名 安全性是基于離散對數(shù) 被廣泛接收,8. DSA 密鑰生成,首先選取公開參數(shù) (p,q,g) : 選取大素數(shù) p = 2L L= 512 to 102
6、4 bits(64倍數(shù)) 選取 q, 160 bit 素因子( of p-1 ) 選擇 g = h(p-1)/q 對任何 h1 每個用戶選取私鑰并計算他們的公鑰: 選取 x
7、q) v=r 簽名有效,10. DSA 安全性,基于離散對數(shù) 最初建議使用一個共同的 modulus p 現(xiàn)在建議不同的工作組使用不同的 (p,q,g) Gus Simmons 發(fā)現(xiàn)存在潛信道,能夠泄露私鑰,13. 帶密鑰的HASH,以上的簽名方法都是公鑰技術(shù) 計算與數(shù)據(jù)量較大 需要私鑰的認證方案 好的方法是使用快速的hash 函數(shù): 密鑰與消息同時參加運算:KeyedHash = Hash(Key|Message) 有一些弱點 隨后建議:KeyedHash = Hash(Key1|Hash(Key2|Message)),14. HMAC,HMAC 是使用帶密鑰的HASH函數(shù)的結(jié)果 成為int
8、ernet標準 (RFC2104) 結(jié)構(gòu):HMACK = Hash((K+ XOR opad)||Hash((K+ XOR ipad)||M)) K+ 是經(jīng)過填充的密鑰 opad, ipad 特殊的填充值 Opad=01011010重復b/8次 ipad=00110110重復b/8次 安全性是基于原來的HASH函數(shù)的安全性 任何 MD5, SHA-1, RIPEMD-160 都可以這樣使用,15. 小結(jié),數(shù)字簽名 (RSA, ElGamal, DSA,) HMAC,練習,Illustrate the operation of El Gamal signatures, given the following parameters: prime p=31 prim root a=3 Determine a suitable private and public key, and then show the signing and verification of a message M=7.,