基於rsa算法的前向安全數字籤名算法的製作方法

2023-09-17 22:55:30

專利名稱：基於rsa算法的前向安全數字籤名算法的製作方法
技術領域：
本發明屬於通信技術領域，涉及網絡通信的安全問題，應用於網絡數字籤名。
背景技術：
在現實中，對數字籤名方案最大的威脅來自於(秘密或者說籤名)密鑰的洩露。只 要使用知名的方案和足夠大的安全參數，即使敵手能成功分析籤名方案，其造成的威脅也 遠不如密鑰洩露造成的威脅。然而一旦籤名者的秘密密鑰洩露，敵手可以利用洩露的密鑰 偽造任何時間的籤名，整個方案的安全性將瓦解。雖然數字籤名中可以附加時間戳，然而這 個時間是秘密密鑰的使用者聲稱的，其安全性是建立在秘密密鑰的保密上的，持有了秘密 密鑰的敵手一樣可以偽造時間戳。 通常考慮的解決密鑰洩露的方法是通過數個伺服器經由秘密的共享實現密鑰分 配，密鑰分配有許多實例化的方案比如門限籤名方案等。然而，使用密鑰分配的方式開銷相 當大，當大企業或者證書權威組織能分配密鑰時，只擁有一臺機器的普通用戶卻沒有這樣 的選擇。其他針對密鑰洩露的保護方法包括使用受保護的硬體或者smartcard等，但這些 方法也往往是昂貴或不切實際的。此外，密鑰分配方案不一定能提供想像中的安全性，比 如，密鑰分配易受共模故障的影響因為所有機器使用相同的作業系統，如果找出一個系統 的可能造成非法入侵的漏洞，所有的機器都會受影響。 —般的數字籤名還有一個基本的限制如果一位籤名者的秘密密鑰已經不安全 (洩露)了，則該籤名者(過去和未來的)的所有籤名都不可信了，這樣的限制破壞了數字 籤名所應該提供的不可否認性，對於某個惡意的籤名者來說，最簡單的否認其籤名(其可 能從中獲益)的方法就是將自己的秘密密鑰匿名地發送到網際網路上的某處並宣稱計算機 受到了入侵。 針對這樣的問題和限制，R. Anderson首先於1997年在ACM CCS會議上提出了前 向安全數字籤名方案的概念。隨後M. Bellare和S. Miner與1999年在Crypto99會議上發 表了"AForward-Secure Digital Signature Scheme，，一文，文中提出了數字籤名的前向安 全性的正式定義，給出了可行的前向安全數字籤名方案——Bellare-Miner方案，並給出了 衡量具體的前向安全性的方法，可以說其奠定了前向安全數字籤名研究的基礎。
直觀上來說，前向安全的特性是指對於一個數字籤名方案，當前秘密密鑰的洩露 不會造成敵手得到偽造屬於過去的籤名的能力。Rose Anderson在1997年ACM CCS會議首 次提出前向安全數字籤名的概念時粗略地將其表示為當前私鑰的洩露不會影響到過去的 大量數字籤名的安全性，而Bellare和Miner在其發表的文章中給出了較正式的定義，即對 於一個具有密鑰更新(或者說演化)機制的數字籤名方案，在其安全性分析模型中允許敵 手進行選擇消息攻擊，並在其所選的時間段j洩露秘密密鑰，敵手將試圖對於消息m偽造出 關於某個時間段i(i < j，對應秘密密鑰洩露之前的時間)的籤名，如果敵手的偽造是計算 上不可行的，那麼稱方案具有前向安全性。 除了前面提到的前向安全數字籤名算法外，Hugo Krawczyk在文章"Simple
3Forward—secure Signature From Any Signature Scheme，，中給出了——禾中將普通數字籤 名算法轉化為前向安全數字籤名算法的一般方法，並基於RSA籤名算法給出了前向安全數 字籤名算法，但是這個算法的驗證算法要用到交互式零知識證明，效率很低，除了特定場合 外，在實際應用上價值不高。本發明基於RSA籤名算法給出一個前向安全數字籤名算法，與 其他前向安全數字籤名算法比較，具有效率高，密鑰長度短的優勢，具有很高的實用價值。 並且本發明其實也隱含地給出了一種將普通數字籤名算法轉化為前向安全數字籤名算法 的一般方法。 —個前向安全的數字籤名方案應當首先是一個具有密鑰更新機制的數字籤名方
案。這樣的一個方案和標準方案類似，但方案的生命周期被分為若干時間段，每個時間段中
使用不同的秘密密鑰來對消息進行籤名，秘密密鑰由一個基於當前時間段的密鑰計算下一
時間段密鑰的算法更新，這個算法使用單向函數以保證不能由當前的秘密密鑰得出以前的
秘密密鑰，整個生命周期內公開密鑰保持不變，即籤名的驗證算法也保持不變。 更進一步表述，一個前向安全的數字籤名方案FSign—般來說包括下面四個算法。 (1)密鑰生成算法FSign. gen(T， lk):一個概率性算法，由時間段數量T和安全參 數k生成秘密密鑰和公開密鑰PK。 (2)密鑰更新算法FSign. upd(j， SKj):可能的概率性算法，在方案的生命周期內 PK保持不變，而秘密密鑰隨時間段的改變而更新，令時間段j內使用的秘密密鑰為SKj，則 一旦時間段j結束進入時間段j+l，就啟用密鑰更新算法，通過一個單向函數f和SKj計算 出新的秘密密鑰SK,p然後刪除SKj。由於使用了單向函數，由SKj+1求出SKj是不可行的。
(3)籤名算法FSign. sig(j，SKj，m):可能的概率性算法，使用當前時間段j對應的 秘密密鑰SKj對消息m籤名，生成形如(j，s)的籤名。 (4)驗證算法FSign. ver (PK， m， (j， s)):確定性算法，使用公開密鑰PK，消息m來 驗證一個聲稱的時間段j內產生的籤名(j，s)是否確實為時間段j內關於消息m的有效籤 名，對於任何真實有效的籤名其都能正確驗證。 前向安全數字籤名的出現，以一種不需要分配密鑰或使用受保護的存儲設備的較 簡單的方式，從某種程度上保護了籤名的安全性("向前的"，而不是全面的安全性)，降低 了秘密密鑰洩露造成的風險和損失。

發明內容
本發明給出了一個新的前向安全的數字籤名算法。
本發明用到的函數及主要符號
T表示密鑰周期總數； 函數《對任意輸入正整數n，輸出不大於n且與n互素的正整數的個數；
函數gcd對輸入的兩個整數，輸出它們的最大公約數； 函數H為一個哈希函數，對任意一個0、1序列進行哈希函數運算，所得到的結果 為一個不大於n的整數； PK表示籤名者的公鑰，表示第i個密鑰周期的籤名密鑰；
運算mod表述模運算，運算I I表示字符串連接運算。
本發明的詳細過程如下 密鑰生成算法FSign. gen (T， lk): 1.選擇兩個大素數p，q，計算n二pq，^(")-(P- 2.選擇安全的哈希函數H:U)，ir— {0，l}logn; 3.選擇T+l個數e。， …，eT，使得1 < ei < f (n)，且gcrf(e" <K"))=1; 4.計算《s e「'(附od (0 = i = T)，《s《^(/tkm/ ") (1《i《T-l); 5.計算^ s好(e。 1l"ll/lle,."(附orf"),CERTi = (e0， n， i， e丄，k》(1 = i = T)。 公鑰PK = (e。， n， H)，私鑰= (1， c^， n， H)。 安全刪除p， q， e。， ei，， eT， d。， c^，…，dT， p(")註冊自己的公鑰PK，安全保存私 鑰S&，保存d'《i《T-l)，CERTi(l = i = T)。其中d' i， CETRi不用安全保存。 密鑰更新算法FSign. upd(j， SK》 1.如果j = T，運行FSign. gen (T， lk)重新初始化系統，否則； 2.計算《.+1 s rf，") ， SKj+1 = (j+l， dj+1， n， H)，安全刪除SK」，安全保存SKj+1。 籤名算法FSign. sig(j， SKj， m):
1.計算t = H(m);
2.計算ss,(wt^m); 3. s = (s， CERTj) ， (j， s)是對消息m的籤名。 驗證算法FSign. ver (PK， m， (j， s)): 令s = (s， CERTj) ， CERT」=(e。， n， i， k》 1.驗證CERTj中的e。是否和籤名者的公鑰一致； 2.驗證CERTj中的i是否等於j ; 3.驗證<。=II" II ! II e;)(附^ "); 4.驗證P ") 5.如果以上驗證都通過，則籤名是有效的，否則籤名無效。 本發明得到的前向安全的數字籤名算法不但具有一般數字籤名算法所具有的所 有特性與安全性，而且還具有前向安全性。因為籤名密鑰&是獨立選取的，攻擊者即使的 到密鑰A,也不可能得到關於密鑰dj (j < i)的任何信息，如果攻擊者在不知道密鑰&的情 況下能夠偽造一個第i密鑰周期的合法籤名，那麼他就能夠攻破RSA困難問題，這與RSA困 難問題是難解的假設矛盾，因此本發明具有前向安全性。 與其他具有前向安全性的數字籤名算法相比較，本算法的籤名算法，驗證算法以 及密鑰更新算法都具有很高的效率。其中簽名算法系需要一次哈希運算及一次模指數運 算；驗證算法只需要兩次模指數運算，兩次哈希運算及四次比較運算；密鑰更新算法只需 要一次模指數運算。除了效率高外，本算法還具有密鑰短的特點，大大減小了密鑰保存所需 要的空間。


附圖是本發明的前向安全數字籤名算法。
具體實施例方式
本發明的發明內容部分對本發明的技術方案已經做出了詳細說明，在此不再重複 描述。
權利要求
基於RSA算法的前向安全數字籤名算法，該方法用於網絡數字籤名，其中T表示密鑰周期總數；函數對任意輸入正整數n，輸出不大於n且與n互素的正整數的個數；函數gcd對輸入的兩個整數，輸出它們的最大公約數；函數H為一個哈希函數，對任意一個0、1序列進行哈希函數運算，所得到的結果為一個不大於n的整數；PK表示籤名者的公鑰，SKi表示第i個密鑰周期的籤名密鑰；運算mod表示模運算，運算||表示字符串連接運算。其特徵是，包括以下四個多項式時間算法密鑰生成算法Fsign.gen(T，1k)1)選擇兩個大素數p，q，計算n＝pq，2)選擇安全的哈希函數H{0，1}*→{0，1}logn；3)選擇T+1個數e0，e1，…，eT，使得且4)計算(0≤i≤T)，(1≤i≤T-1)；5)計算CERTi＝(e0，n，i，ei，κi)(1≤i≤T)。公鑰PK＝(e0，n，H)，私鑰SK1＝(1，d1，n，H)。安全刪除p，q，e0，e1，…，eT，d0，d1，…，dT，註冊自己的公鑰PK，安全保存私鑰SK1，保存d′i(1≤i≤T-1)，CERTi(1≤i≤T)。其中d′i，CETRi不用安全保存。密鑰更新算法Fsign.upd(j，SKj)1)如果j＝T，運行Fsign.gen(T，1k)重新初始化系統，否則；2)計算SKj+1＝(j+1，dj+1，n，H)，安全刪除SKj，安全保存SKj+1。籤名算法Fsign.sig(j，SKj，m)1)計算t＝H(m)；2)計算 s t dj ( mod n ); 3)σ＝(s，CERTj)，(j，σ)是對消息m的籤名。驗證算法Fsign.ver(PK，m，(j，σ))令σ＝(s，CERTj)，CERTj＝(e0，n，i，ei，κi)1)驗證CERTj中的e0是否和籤名者的公鑰一致；2)驗證CERTj中的i是否等於j；3)驗證 i e0 H ( e0 | | n | | i | | ei ) ( mod n ); 4)驗證 s ei H ( m ) ( mod n ) 5)如果以上驗證都通過，則籤名是有效的，否則籤名無效。F2009102160199C0000011.tif,F2009102160199C0000012.tif,F2009102160199C0000013.tif,F2009102160199C0000014.tif,F2009102160199C0000015.tif,F2009102160199C0000016.tif,F2009102160199C0000017.tif,F2009102160199C0000018.tif,F2009102160199C0000019.tif
全文摘要
本發明屬於通信技術領域，涉及網絡通信的安全問題，用於網絡數字籤名。本發明與一般的數字籤名算法相比較，在具有高效的籤名及驗證效率的同時，還具有前向安全性；與其他具有前向安全性的數字籤名算法相比，具有高效的密鑰更新效率，還具有密鑰短的特性，其公鑰及私鑰都不隨密鑰周期數T的增長而線性增長，從而減小了密鑰保存的昂貴代價。並且本發明同時也隱含地給出了一種將普通數字籤名算法轉化為前向安全數字籤名算法的一般方法。
文檔編號H04L29/06GK101714919SQ200910216019
公開日2010年5月26日 申請日期2009年10月29日 優先權日2009年10月29日
發明者李成邦, 許春香 申請人:電子科技大學