[發明專利]壓縮的ECDSA簽名

有效

• 申請號: 200780041946.0
• 申請日: 2007-11-13
• 公開（公告）號: CN101647229A
• 公開（公告）日: 2010-02-10
• 發明（設計）人: 斯科特·A·范斯騰
• 申請（專利權）人: 塞爾蒂卡姆公司
• 主分類號: H04L9/32
• 分類號: H04L9/32;H04L12/58
• 代理公司: 中科專利商標代理有限責任公司
• 代理人: 王 瑋

技術領域

本發明涉及密碼方案并且在數字簽名算法中尤其實用。

背景技術

消息的數字簽名是依賴于某些只有簽名者知道的秘密的數，此 外，該數又依賴于被簽名的消息的內容。簽名應當是可驗證的。如果 對一方是否對文檔進行了簽名出現爭議(由于簽名者試圖否認其確實 創建的簽名，或者由于欺騙性聲明而導致)，無偏的第三方應當能公正 地解決這件事，而不需要訪問簽名者的秘密信息(例如，私有密鑰)。

數字簽名在信息安全中具有很多應用，特別地，它們被使用在密 碼方案中。一些應用包括認證、數據完整性和不可否認性。數字簽名 的一種特別重要的應用是驗證大型網絡中的公共密鑰。對于可信的第 三方，驗證是一種將用戶的身份與公共密鑰綁定的方式，使得在以后 某個時間，其它實體可以對公共密鑰進行認證而無需來自可信第三方 的幫助。

被稱為數字簽名算法(DSA)的密碼方案基于公知的且經常討論 的離散對數問題的難解決性。DSA由美國國家標準和技術學會(NIST) 于1991年提出并已經成為美國聯邦信息處理標準(FIPS?186)，稱為 數字簽名標準(DSS)。該算法是公知的ElGamal簽名方案的變型，并 且可以被分類為具有附錄的數字簽名(即一種依賴于密碼散列(hash) 函數而不是定制冗余函數的數字簽名)。

橢圓曲線數字簽名算法(ECDSA)是一種可以應用于橢圓曲線密 碼系統且具有類似于DSA的屬性的簽名方案。它通常被認為是最廣泛 標準化的基于橢圓曲線的簽名方案，出現在ANSI?X9.62，FIPS?186-2， IEEE?1363-2000和ISO/IEC?15946-2標準以及多個草案標準中。

ECDSA簽名生成過程對若干域參數、私有密鑰d和消息m進行 運算。輸出是簽名(r，s)，其中簽名分量r和s是整數，并且如下進 行處理。

1、選擇隨機整數k∈_R[1，n-1]，n是域參數之一。

2、計算kG＝(x₁，y₁)并且將x₁轉換為整數其中G是在橢圓曲 線E上的點并且是域參數之一。

3、計算其中如果r＝0，則返回步驟1。

4、計算e＝H(m)，其中H代表密碼散列(hash)函數，其輸出具 有不超過n的比特長度(如果不滿足該條件，則可以截斷H的輸出)。

5、計算s＝k^-1(e+αr)mod?n，其中α是簽名者的長期私有密鑰。 如果

s＝0，則返回步驟1。

6、將(r，s)對作為消息m的ECDSA簽名輸出。

ECDSA簽名驗證過程對若干域參數、長期公共密鑰Q(其中Q＝ αP)、消息m以及以上導出的簽名(r，s)進行運算。ECDSA簽名驗 證輸出對簽名的拒絕或接受，并且如下進行處理。

1、驗證r和s是區間[1，n-1]中的整數。如果驗證失敗，則返回拒 絕。

2、計算e＝H(m)

3、計算w＝s^-1modn

4、計算u₁＝ew?modn以及u₂＝rw?modn

5、計算R＝u₁P+u₂Q＝s^-1(eP+rQ)(根據以上3和4)

6、如果R＝∞，則拒絕該簽名

7、將R的x坐標x₁轉換為整數計算

8、如果v＝r，則接受該簽名，否則拒絕該簽名

為了提高ECDSA簽名驗證的效率，在上面包括s的倒置在內的 特定步驟5中，已知通過省略2b比特來截斷s而對ECDSA簽名進行 了壓縮。這樣的壓縮的代價是額外的驗證步驟，已知其代價為驗證者 近似2^2b次額外的橢圓曲線組運算。

在帶寬節約極為重要而且驗證者可以容易地處理額外密碼運算 的密碼應用中特別需要簽名壓縮。一個示例是二維條形碼，其中帶寬 非常有限而驗證者的處理器可能較快。另一個示例是RFID標簽，RFID 標簽需要來自射頻場的功率以便傳輸數據，并因此非常希望低傳輸帶 寬。

需要一種ECDSA簽名壓縮的方案，該方案中驗證者所付出的代 價低于上述這種壓縮方案。