[發明專利]一種基于強RSA假設的數字簽名方法

有效

• 申請號: 201010569909.0
• 申請日: 2010-11-26
• 公開（公告）號: CN102013983A
• 公開（公告）日: 2011-04-13
• 發明（設計）人: 喻平;薛銳
• 申請（專利權）人: 中國科學院軟件研究所
• 主分類號: H04L9/32
• 分類號: H04L9/32;H04L9/08;H04L9/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 余長江

技術領域

本發明主要涉及信息安全的數字簽名方法，尤其涉及一種高效的基于強RSA假設的數字簽名方法。

背景技術

隨著網絡技術的不斷發展，網絡信息的交互越來越頻繁，僅僅加密信息已經遠遠不能滿足需求，數字簽名的應用已經越來越廣泛。

數字簽名是現代密碼學中的基礎原語。簽名方案中，簽署者生成包括簽署密鑰和驗證密鑰的密鑰對。簽署密鑰由簽署者秘密保存，驗證密鑰對潛在的驗證者公開。對于一個消息，簽署者使用簽名函數和簽署密鑰生成一個串，該串稱為該消息的簽名。之后驗證者能使用驗證函數和驗證密鑰檢驗該簽名的合法性。

數字簽名的安全性分析中一個常用的方法是隨機應答器模型(Random?Oracle?Model)，在該模型中建立一個能被所有主體訪問的隨機應答器。因為隨機應答器是為在數學上分析方便而引入的一種理想的概念，現實中該算法往往由密碼學中的哈希函數代替。隨機應答器模型下，可以設計出高效的密碼學方案。例如最優非對稱加密填充(OAEP)的RSA方案，RSA方案在這種模式下加密已經被證明在隨機應答器模型下是安全的。然而，Canetti等人提出存在隨機應答器模型下被證明是安全的方案，但是該隨機應答器的任何實例都會導致不安全的構造。他們的工作表明隨機應答器模型在根本上是存在一些問題的。

另外一種模型稱為標準模型(standard?model)，該模型中模擬所有主體的行為都和現實協議中的行為是一樣的或者是不可區分的。安全證明中不再需要其他的假設。由于隨機應答器是啟發式的方法，所以密碼學中趨向于設計在標準模型下安全的方案。

第一個簽名方案是RSA方案，RSA方案組合上填充方式被證明在隨機應答器模型下是安全的，該方案基于的假設是RSA假設。2000年，Cramer和Shoup提出在標準模型下安全的簽名方案，但是該方案是基于一個更強的假設——強RSA假設。之后許多基于強RSA假設的方案越來越多，如Camenish-Lysyanskaya方案，Zhu方案，Yu-Tate方案等等。這些方案的主要優勢在于他們都有在標準模型下的安全性證明，主要的劣勢在于與RSA方案相比，他們需要付出更多的計算代價。例如Camenish-Lysyanskaya方案的計算代價大約是RSA方案的三倍。

下面是現有簽名方法的具體分析：

1)相關概念及定義

安全的RSA模RSA模n＝pq，如果p＝2p′+1并且q＝2q′+1，其中p′，q′為質數，則稱模n是安全的。

強RSA假設：假設n為RSA模，對于一個隨機元素對于任意的多項式概率算法，找到一對(v，e)，使得e＞1并且v^e＝umodn的概率是可忽略的。

安全的簽名方案：一個簽名方案S＝<Gen，Sig，Ver>，Gen表示密鑰生成算法，用于生成驗證公鑰和簽名私鑰；Sig表示簽名算法，用于生成某個消息的簽名；Ver表示驗證算法，用于驗證得到的簽名是否合法。如果偽造者在知道多項式個由他自己選擇的消息對應的簽名后，仍然不能偽造一個新的消息對應的簽名。稱這個簽名方案在自適應選擇消息攻擊下是存在性不可偽造的。

2)Camenish-Lysyanskaya方法及其分析改進

Camenish-Lysyanskaya方法(簡寫為CL方法)的具體內容如下。

密鑰生成輸入1^k，選取安全的RSA模n＝pq，其中p＝2p′+1，q＝2q′+1，且p，q的長度為l_n＝2k。隨機選取a，b，c∈QR_n。輸出公鑰PK＝(n，a，b，c)，私鑰SK＝(p′，q′)。

生成簽名輸入信息隨機選取長度為l_e≥l_m+2的質數e，選取隨機數s，其長度為l_s＝l_n+l_m+l，其中l是安全參數。計算將(e，s，υ)作為消息m的簽名。

進行驗證要驗證(e，s，υ)是否為消息m的簽名，檢查υ^e≡a^mb^scmodn，以及若成立則輸出1，表示該簽名是合法的，否則，輸出0。

CL方案已經證明在標準模型下是存在性不可偽造的。