【文章內容簡介】 。 1994年發(fā)表的一個研究報告稱 ， 可以花費 1000萬美元去制造一套專門的機器 ， 針對 MD5搜索兩個不同的報文具有相同的摘要 ，即 “ 碰撞 ” 現(xiàn)象 ， 平均用 24天才能找到一次碰撞 。 目前 ， MD5被認為仍是一個安全和最常用的報文摘要算法 ， 它可由任意長度的數(shù)據(jù)計算出一個 128比特的 MD5值 。 MD5是一種在加密軟件中被用來單向變換用戶口令和對信息簽名的單向散列算法 。 一種單向散列的強度體現(xiàn)在他能把任意的輸入隨機化到什么程度并且能產生唯一的輸出 。 對單向散列的直接攻擊可以分為普通直接攻擊和 “ 生日 ” 攻擊 。 對 MD5的普通直接攻擊 。 所謂直接攻擊又叫野蠻攻擊 。 攻擊者為了找到一份和原始明文 m散列結果相同的明文 m’ ， 就是 H ( m ) = H ( m’ )。 普通直接攻擊 ， 顧名思義就是窮舉可能的明文去產生一個和 H (m)相同的散列結果 。 對 MD5來說散列結果為 128比特 ， 就是說如果攻擊者有一臺每秒嘗試 1000000000條明文的機器需要計算約 1022年 。 對 MD5的生日攻擊 。 生日攻擊實際上只是為了找到兩條能產生同樣散列結果的明文 。 記得那個有名的概率生日問題嗎 ， 在 N 個人中至少有兩個人的生日相同的概率是多少 ？ 所謂生日攻擊實際上只是用概率來指導散列沖突的發(fā)現(xiàn) ， 對于 MD5來說如果嘗試 264條明文 ， 那么它們之間至少有一對發(fā)生沖突的概率是 50%。 僅此而已 ，對當今的科技能力來說 ， 它是不可能的 。 DSA算法的改進 1． 改進算法 DSA算法的安全性依賴于整數(shù)有限域上的離散對數(shù)問題的困難性 ，安全強度和速度均低于 RSA算法 ， 因此不少人對 DSA算法提出了改進 ， 下面介紹其中一種新的改進方案 （ NDSA） 。 NDSA簽名方案中的參數(shù)選取同 DSA， 即： p： L比特長的素數(shù) ， 其中 L范圍是從 512比特到 1024比特 ， 并且要求是 64的整數(shù)倍 （ 在原始標準中 p的尺寸固定的 512比特 ， 后來 p的尺寸由 NIST作了改變 ） 。 q： 160比特的數(shù) ， 并且要求是 p1的因子 。 g： g ? h(p1)/q mod p ， 其中 h是小于 p1的任意數(shù) ， 并且 h(p1)/q mod p?1 x：小于 q的數(shù) y： y ? gx mod p 前三個參數(shù) p、 q、 g是公開的 ， 可以由一組網絡用戶共享 。 秘密密鑰為 x， 公開密鑰為 y 。 簽名時 ， 先產生一個隨機數(shù) k， (kq) 簽名方程： r = ( gk mod p) mod q s = (k r H(m) x ) mod q 簽名： （ r， s） 或 (m； (r， s)) 簽名驗證：為了驗證 （ r， s） 的正確性 ， 驗證者先計算 u1 = s mod q u2 = r H (m) mod q， 然后驗證方程： r = 是否成立 。 成立則正確 ，否則不正確 。 qpgg uu mod)mod( 21 2． 改進算法 （ NDSA） 的性能 NDSA具有以下性能： 1） 無逆簽名 由一上簽名和簽名驗證過程可見 ， 使用 NDSA無論是進行簽名還是進行簽名驗證都無需求逆 ， 是一個真正的無逆簽名算法 。 該算法既提高了簽名速度 ， 又提高了驗證速度 ， 這一特點是 DSA和以有些其他算法所不及的 。 2） 多重簽名 由于 DSA的特殊結果 ， 利用它無法建立多重簽名方案 ， 而在 DSA算法基礎上能過實現(xiàn)多重簽名方案 ， 它可使任意 n個簽名人產生的 n個簽名組合成一個單一的簽名 。 敘述如下： 簽名產生 設共有 n個簽名人 Ui (i = 1,2,… ,n)。 每個簽名人 Ui計算 并將 ci對所有簽名人公開 ， 因此每個簽名人 Ui可計算 pgc iki mod? 并將 ci對所有簽名人公開 ， 因此每個簽名人 Ui可計算 和 si = (ki – rH(m)xi) mod q 即 Ui關于 m的簽名為 (ci， si) 多重簽名 設某人為 n個簽名人和簽名收方之間的中間人 ， 稱其為組合者 C， 每個簽名人 Ui (i = 1,2,… n)都將其關于 m的簽名送給組合者 C，當 C 收到 （ ci， si） (i = 1,2,… n)后 ， 先計算： 和 在驗證每個 （ ci， si） 是否滿足 (i = 1,2,… n) 若對于所有的 i 上式成立 ， 則 （ r， s） 便是 Ui (i = 1,2,… n)關于消息 m的多重簽名 ， C將 （ r， s） 發(fā)送給接收方 。 pcrnii mod)(1??? qcr nii mod)(1??? qssnii mod)(1???qgygc mrHisi i mod)(?? 簽名驗證 簽名接收方受到 （ r， s） 后 ， 先驗證 0 r q和 0 s q是否成立 ， 若成立 ， 則計算： （ 其中 yi為 Ui的公鑰 ） u1 = s mod q u2 = r H (m) mod q 然后驗證方程 : 若方程成立 ， 則簽名驗證通過 。 pyynii mod)(1???qpggr uu mod)mod( 21? 4） 盲簽名 簽名產生 設簽名人為 A， 簽名驗證者和消息擁有者為 B。 A任選隨機密鑰 k， 計算： 然后將 發(fā)送給 B。 B選隨機數(shù) a， b?Zq。 計算： B將盲消息送簽名人 A。 A利用簽名方程 求得部分盲簽名后送 B。 B再計算 完成簽名： 為 A關于盲消息的簽名 ， 為 B 給出的為消息 m的簽名 。 簽名驗證 簽名接收方得到簽名 、 后 ， 只有它們都滿足驗證方程 才被通過驗證 。 pgc k mod? qpgr k mod)mod(?),( rc qpgcr ba mod)mod(? qrmam mod)( 11 ??? qxmrks mod)( ?? qbsmrrm mod)()( 11 ?? ??)),(,( srm)),(,( sr )),(,( srm ))(,(m rms ygr ?? 5） 分批驗證 對簽名進行分批驗證就是簽名驗證人將某個簽名人簽名方程產生的關于 n個不同消息的 n個簽名進行一次性驗證 ， 而不是逐個驗證 ， 從而提高其驗證速度 。 在 NDSA上可建立兩種分批驗證方案 ，它們可以防止除簽名者以外的任何人對簽名的偽造 ， 也就是說 ，在假定簽名人可信的情況下 ， NDSA分批驗證方案是安全的 。 這兩個分批簽名驗證方案介紹如下： 方案 1： 簽名方程 ： 得到簽名為： 或 （ i = 1， 2， … ， ） 分批驗證方程 ： 如果方程成立 ， 則 n個簽名驗證通過 。 pg iki mod?? qxmHks iiii mod))(( ???),( ii s? ),(,( iii sm ? qygniIinii mHinisi mod11 )(1????? ????? 方案 2： 簽名方程 ： （ i = 1， 2， … ， n） （ i = 1， 2， … ， n） 得到 n個簽名： (?i， si) （ i = 1， 2， … ， n） 分批驗證方程 ： 或 如果驗證方程成立 ， 則簽名驗證通過 。 pg iki mod?? prnii mod)(1??? ?qxmrHks iii mod))(( ?? qygniIinii mHinisi mod11 )(1????? ?????qpygrni Iini i mHis mod)mod(11)(???? ??? 6） NDSA安全性分析 偽造者要想從公鑰 y = g x mod p求得 x或先任選 r再從 r = (g s?y r H ( m)mod p)mod q求部分簽名 s均等于求離散對數(shù)或比求離散對數(shù)還難 。 如果將 y看作是 n個簽名人之公鑰在模 p下的乘積 ， 則說明對于多重簽名的偽造也是不可能的 。 5． 4 基于離散對數(shù)的若干新型代理簽名方案 代理簽名是一種新型簽名方案 ， 由于這種簽名機制在許多領域都有重要的應用 ， 因此引起了人們的極大興趣 。 代理簽名的目的是當某簽名人 (這里稱為原始簽名人 )因公務或身體健康等原因不能行使簽名權力時 ， 將簽名權委派給其他人替自己行使簽名權 。 目前 ， 一些代理簽名方案存在以下問題 :： (1)代理簽名方案在驗證方程中僅含代理簽名者的公鑰 ， 從而實際簽名權和代理簽名權沒有實現(xiàn)有效地分離； (2)授權方程的建立都是采用交互式傳遞數(shù)據(jù)的方法 ， 而且不包含代理簽名者的身份碼 。 因此 ， 授權方程的建立既煩瑣 ， 又使簽名收方不易驗證代理簽名人的真實性 。 (3)對代理簽名而言 ， 如何實現(xiàn)一個人同時受多人之托 ， 進行代理多重簽名 。 針對以上三點下面介紹一個新型代理簽名方案和一個代理多重簽名方案 1． 代理簽名方案的基本要求 在一個代理簽名方案中 ， 如果假設Ａ委托Ｂ進行代理簽名 ， 則此簽名方案應滿足以下三個最基本的條件： 簽名收方能夠象驗證Ａ的簽名那樣驗證Ｂ的簽名 Ａ的簽名和Ｂ的簽名應當完全不同 ， 并且容易區(qū)分 Ａ和Ｂ對簽名事實不可否認 2． 新型代理簽名方案 安全參數(shù) ：Ｐ為大素數(shù) ， ｇ ∈ Ｇ Ｆ (ｐ )為本原元 ， ｆ是單向函數(shù) ，原始簽名人Ａ的公鑰為 ， 代理簽名人Ｂ的公鑰為 ， xB∈ (1,ｐ 1)， 且 gcd(xB,ｐ 1)=1。 pgy AxA mod? pgy BxB ? 授權方程 ： 當Ａ打算將簽名權委托給Ｂ時 ,Ａ選取隨機數(shù) ｋ ∈ (1,ｐ 1)， 并利用Ｂ的身份碼 IDB計算ｒ = gk mod ｐ 和 ｓ ′=ｒ xA+IDBｋ mod ｑ ， 然后將 (IDB,ｒ ,ｓ ′)送Ｂ 。 Ｂ收到 (IDB,ｒ ,ｓ ′)后 ， 先驗證 ， 以確認受委托數(shù)據(jù)源的可靠性 。 確認數(shù)據(jù)可靠性之后Ｂ再做如下計算： ， 則 (IDB,ｒ ,ｓ )滿足 。上式成立的原因是： 。 在這里 為授權方程 ， 它建立了Ａ和Ｂ兩者公鑰之間的內在聯(lián)系 ， 而這種聯(lián)系只有在Ａ同意轉讓自己的權力時才可建立 。 其中Ｂ的簽名密鑰ｓ只有Ｂ自己知道 ， 其他人包括Ａ也無法知道 。 pry BIDrAs mod39。 ? qxss B mod139。 ?? pryy BIDrAsB mod? pyggg sBxsxxxss BBBB mod)( 139。139。39。 ??? ??pryy BIDrAsB m