一種基于橢圓曲線的數字簽名與盲簽名方案

韓然，吳正朋，胡小莉

(中國傳媒大學理學院，北京 100024)

一種基于橢圓曲線的數字簽名與盲簽名方案

韓然，吳正朋，胡小莉

(中國傳媒大學理學院，北京 100024)

橢圓曲線數字簽名算法實際上是數字簽名算法的橢圓曲線模擬，本文在ANSI(1999)頒布的橢圓曲線數字簽名(ECDSA)標準的基礎上，提出了橢圓曲線數字簽名的一個變形方案，并設計了一種新的基于橢圓曲線的盲數字簽名方案，其安全性是建立在橢圓曲線離散對數問題的難解性基礎上的，從理論上講是安全的，具有一定的實用價值。

橢圓曲線離散對數;橢圓曲線數字簽名;盲數字簽名

1 引言

隨著密碼理論的研究深入，計算機技術的飛速發展，經典的RSA，Diffie-Hellman等公鑰密碼體制(密鑰長度一般為512bit)已變得越來越不安全了。因此，為了確保信息安全，密碼體制的密鑰要達到足夠的長度，這對于速度緩慢的RSA密碼體制來說，更是不堪負重，同時一些較短密鑰的應用產品(例如Smart卡等)也需要新的密鑰體制來實現。自1985年N.Koblitz和V.Miller提出橢圓曲線公鑰密碼體制的新思想以來［1］，使得被數學家研究了一百多年的橢圓曲線在密碼領域中得以發揮重要作用。人們利用橢圓曲線上有理點組成的Abel群及其上離散對數問題求解的困難性構成了一些公鑰密碼體制，它們具有每bit位最高安全強度，也就是說，使用較短的密鑰，即可具有滿足現實要求的安全強度。例如，橢圓曲線密碼體制中160bit長的密鑰所具有的安全強度相當于RSA密碼體制中1024bit長的密鑰所具有的安全強度。橢圓曲線密碼體制不僅能夠對信息進行加密，而且還能用來構造數字簽名和盲數字簽名方案，橢圓曲線數字簽名算法(ECDSA)實際上是數字簽名算法(DSA)的橢圓曲線模擬。

在本文中，基于橢圓曲線數字簽名算法，我們給出了一個橢圓曲線數字簽名的變形方案，并設計了一種新的基于橢圓曲線的盲數字簽名方案。本文結構如下:第2節介紹相關的數學背景，有限域上的橢圓曲線;第3節描述了安全橢圓曲線的選擇問題;第4節給出了一個ECDSA的變形方案，并設計了一種基于橢圓曲線的盲數字簽名方案。

2 有限域上的橢圓曲線

設Fq是特征值大于3的有限域，其中q=pm，a，b∈Fq，滿足4a3+27b2≠0，則在仿射坐標平面上，由參數a，b定義在有限域Fq上的橢圓曲線E(Fq)是方程y2=x3+ax+b 的所有解(x，y)，x∈Fq，y∈Fq連同一個附加的“無窮遠點”(記為O)的元素組成的點的集合。E(Fq)的點數用#E(Fq)表示。點集合E(Fq)對應下面的加法規則構成一個Abel加法群:群運算的恒等元是O，設P，Q∈E(Fq)，

關于橢圓曲線更詳細內容請參考［2］。

3 安全橢圓曲線的選擇

對于給定的橢圓曲線E(Fq)，若給定一個點P∈E(Fq)，R∈E(Fq)，那么給定一個整數m，計算mP=R是容易的，但是若從點R及點P推導出整數m，則是非常困難的，即沒有多項式時間求解算法，這就是橢圓曲線離散對數問題(ECDLP)。橢圓曲線密碼體制是以橢圓曲線離散對數問題的難解性為基礎的。從目前的研究結果看，橢圓曲線上的離散對數問題比有限域上的離散對數問題似乎更難處理，迄今還沒有出現類似于解有限域上的離散對數問題的indexcalculus算法來求解一般橢圓曲線上的離散對數問題，這就意味著可以在橢圓曲線公鑰密碼中采用較小的數以達到與更大的有限域同樣的安全性。

對于橢圓曲線離散對數問題的攻擊，如果橢圓曲線是超奇異的(#E(Fq)=q+1)，可以用一個MOV歸約法能有效的將這些曲線上的離散對數問題約簡到有限域上的離散對數問題，從而可應用index-calculus算法來求解，這類曲線已被橢圓曲線公鑰密碼標準禁止使用。同樣還有一類弱的橢圓曲線是“反常曲線”，這是定義在Fq上的橢圓曲線E(Fq)，#E(Fq)恰好等于q，對這類曲線的攻擊是由Semave，Smart以及Satoh和Araki分別獨立發現的［3］。這類曲線也在橢圓曲線公鑰密碼標準中禁止使用。目前已知的求解橢圓曲線離散對數問題的最好算法是Pollard-ρ算法和Pohlig-Hellman算法，其時間都是指數級的，但當橢圓曲線的階含有較大素因子時這兩種方法也是無效的［4］。

因此，用來構建密碼體制的橢圓曲線最好是非超奇異的，且滿足條件:

1.#E(Fq)=c·l，其中l是一個大于2160的素數，正整數c通常叫做余因子，考慮到運算效率的問題，通常取 c≤4，詳見［5］。

2.#E(Fq)≠q，這是為了避免“反常曲線”帶來的攻擊;

3.對 v=1，2，…，10，qv-1 不能被大素數 l整除，這個條件保證MOV歸約法不能實現。

4 基于橢圓曲線的盲簽名方案

數字簽名是電子信息特殊的產物，是保證電子數據真實性的有效手段，數字簽名可以用秘密密鑰密碼體制實現，也可以用公開密鑰密碼體制實現。橢圓曲線數字簽名算法(ECDSA)實際上是數字簽名算法(DSA)的橢圓曲線模擬，它在1999年作為一個ANSI(美國國家標準學會)標準認可，命名為ANSI X9.62［5］。本節先給出了一個ECDSA的變形方案，接著設計了一個基于橢圓曲線的盲數字簽名方案，在簽名前，為了提高效率，一般需要對文本(設為m)進行一定的預處理——應用Hash函數提取文件摘要，然后對文件摘要進行簽名。

4.1 ECDSA的一個變形方案

(1)系統初始化:構造有限域Fq上的橢圓曲線，E(Fq)該曲線是非奇異的，且滿足安全條件，選擇一個公開的基點G∈E(Fq)，其階為n，系統有一個安全Hash函數h:{0，1}*→Z，輸入任意長度的消息，它將返回一特定長度的消息摘要(160比特是一種流行的選擇)。

(2)密鑰生成:用戶A隨機選取一個整數d作為密鑰，公開點GA=dG作為公鑰。

(3)簽名生成:

4.2 基于橢圓曲線的盲簽名方案

一般的數字簽名中，簽名者總是首先要知道簽名文件的內容，然后才對文件簽名，但是有時候，要求認證者只能通過簽名來認證簽名者的身份是否合法而不能得知具體的明文消息，稱這種簽名為盲簽名。

(1)簽名生成:系統初始化與密鑰生成與上述ECDSA一樣，

①用戶A隨機選一個整數k∈{1，…，n-1}，計算R=kG，并將R'傳送給用戶B;

③用戶A計算s=k-rd mod n，將s傳送給用戶B;

④用戶B計算y=r1s mod n，輸出簽名(y，e)即為m的盲簽名。

(2)簽名驗證:只需驗證Rx(yG+eGA)mod n=t是否成立即可，若成立，則簽名正確，否則不正確。這是因為:y≡r1s≡r1k-r1rd≡r1k-r1(r2+r-11e)d≡r1k-r1r2d所以yG+eGA=r1kG-r1r2GA。

(3)性能分析:①由盲數字簽名的特性，明文消息m對用戶A來說應該是盲的;②攻擊者若截取R'，試圖通過R'來求解k，這是求解橢圓曲線離散對數問題;③攻擊者若截取s，試圖偽造s，但是不知道用戶A的密鑰，也是徒勞的。因此，本方案滿足盲數字簽名的要求。

5 結束語

本文設計了一個基于橢圓曲線密碼體制的盲數字簽名方案，其安全性是基于橢圓曲線離散對數問題的難解性基礎上的，由于目前還沒有對離散對數問題的有效解法，所以本方案是安全的。由于橢圓曲線密碼體制有著自己獨特的優越性如較短的密鑰、運算速度快、便于計算機實現等方面，可被廣泛應用于電子商務、較短密鑰的應用產品中去。

［1］Neal Koblitz.Elliptic curve cryptosystems［J］.Math Comp，1987，(48):203-209.

［2］Silverman J H.The arithmetic of elliptic curves［M］.GTM106，Springer Verlag，New York，1986.

［3］N P Smart.The Discrete Logarithm Problem on Elliptic Curves of Trace One［J］.Journal of Cryptology，1999，12(3):193-196.

［4］Johannes Buchmann and Harald Baier.Efficient construction of cryptographically strong elliptic curves［C］.Progress in Cryptology-INDOCRYPT 2000，Springer，2000.

［5］ANSI X9.62 Public Key Cryptography for the Financial Services Idustry:The Elliptic Curve Digital Signature Algorithm(ECDSA)［R］.1999.

［6］張方國，王常杰，王育民.基于橢圓曲線的數字簽名與盲簽名［J］.通信學報，2001，22(8)，22-28.

［7］楊君輝，戴宗擇，楊棟毅，劉宏偉.一種橢圓曲線簽名方案與基于身份的簽名協議［J］.軟件學報，2000，11(10):1303-1306.

A Scheme Based on the Elliptic Curve Digital Signature and Blind Signature

HAN Ran，WU Zheng-peng，HU xiao-li
(College of Science，Communication University of China，Beijing 100024)

Elliptic curve digital signature algorithm is the elliptic curve analogue of the digital signature algorithm.This paper proposes a varied form of elliptic curve digital signature scheme by ANSI(1999)standard and a new blind digital signature scheme based on the elliptic curve cryptosystem.The safety of this scheme is based on the difficulty of solving the elliptic curve discrete logarithm problem.The scheme is secure in theory and is suitable for some practical application.

elliptic curve discrete logarithm;elliptic curve digital signature;blind digital signature

TP 309

A

1673-4793(2012)02-0075-03

2011-03-29

韓然(1976—)，男，山東濰坊人。中國傳媒大學碩士研究生。Email:hanran@cuc.edu.cn。

(責任編輯

:龍學鋒)