韓然，吳正朋，胡小莉

(中國(guó)傳媒大學(xué)理學(xué)院，北京 100024)

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

韓然，吳正朋，胡小莉

(中國(guó)傳媒大學(xué)理學(xué)院，北京 100024)

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

橢圓曲線離散對(duì)數(shù);橢圓曲線數(shù)字簽名;盲數(shù)字簽名

1 引言

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

在本文中，基于橢圓曲線數(shù)字簽名算法，我們給出了一個(gè)橢圓曲線數(shù)字簽名的變形方案，并設(shè)計(jì)了一種新的基于橢圓曲線的盲數(shù)字簽名方案。本文結(jié)構(gòu)如下:第2節(jié)介紹相關(guān)的數(shù)學(xué)背景，有限域上的橢圓曲線;第3節(jié)描述了安全橢圓曲線的選擇問(wèn)題;第4節(jié)給出了一個(gè)ECDSA的變形方案，并設(shè)計(jì)了一種基于橢圓曲線的盲數(shù)字簽名方案。

2 有限域上的橢圓曲線

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

關(guān)于橢圓曲線更詳細(xì)內(nèi)容請(qǐng)參考［2］。

3 安全橢圓曲線的選擇

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

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

因此，用來(lái)構(gòu)建密碼體制的橢圓曲線最好是非超奇異的，且滿足條件:

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

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

3.對(duì) v=1，2，…，10，qv-1 不能被大素?cái)?shù) l整除，這個(gè)條件保證MOV歸約法不能實(shí)現(xiàn)。

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

數(shù)字簽名是電子信息特殊的產(chǎn)物，是保證電子數(shù)據(jù)真實(shí)性的有效手段，數(shù)字簽名可以用秘密密鑰密碼體制實(shí)現(xiàn)，也可以用公開(kāi)密鑰密碼體制實(shí)現(xiàn)。橢圓曲線數(shù)字簽名算法(ECDSA)實(shí)際上是數(shù)字簽名算法(DSA)的橢圓曲線模擬，它在1999年作為一個(gè)ANSI(美國(guó)國(guó)家標(biāo)準(zhǔn)學(xué)會(huì))標(biāo)準(zhǔn)認(rèn)可，命名為ANSI X9.62［5］。本節(jié)先給出了一個(gè)ECDSA的變形方案，接著設(shè)計(jì)了一個(gè)基于橢圓曲線的盲數(shù)字簽名方案，在簽名前，為了提高效率，一般需要對(duì)文本(設(shè)為m)進(jìn)行一定的預(yù)處理——應(yīng)用Hash函數(shù)提取文件摘要，然后對(duì)文件摘要進(jìn)行簽名。

4.1 ECDSA的一個(gè)變形方案

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

(2)密鑰生成:用戶A隨機(jī)選取一個(gè)整數(shù)d作為密鑰，公開(kāi)點(diǎn)GA=dG作為公鑰。

(3)簽名生成:

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

一般的數(shù)字簽名中，簽名者總是首先要知道簽名文件的內(nèi)容，然后才對(duì)文件簽名，但是有時(shí)候，要求認(rèn)證者只能通過(guò)簽名來(lái)認(rèn)證簽名者的身份是否合法而不能得知具體的明文消息，稱這種簽名為盲簽名。

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

①用戶A隨機(jī)選一個(gè)整數(shù)k∈{1，…，n-1}，計(jì)算R=kG，并將R'傳送給用戶B;

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

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

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

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

5 結(jié)束語(yǔ)

本文設(shè)計(jì)了一個(gè)基于橢圓曲線密碼體制的盲數(shù)字簽名方案，其安全性是基于橢圓曲線離散對(duì)數(shù)問(wèn)題的難解性基礎(chǔ)上的，由于目前還沒(méi)有對(duì)離散對(duì)數(shù)問(wèn)題的有效解法，所以本方案是安全的。由于橢圓曲線密碼體制有著自己獨(dú)特的優(yōu)越性如較短的密鑰、運(yùn)算速度快、便于計(jì)算機(jī)實(shí)現(xiàn)等方面，可被廣泛應(yīng)用于電子商務(wù)、較短密鑰的應(yīng)用產(chǎn)品中去。

［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］張方國(guó)，王常杰，王育民.基于橢圓曲線的數(shù)字簽名與盲簽名［J］.通信學(xué)報(bào)，2001，22(8)，22-28.

［7］楊君輝，戴宗擇，楊棟毅，劉宏偉.一種橢圓曲線簽名方案與基于身份的簽名協(xié)議［J］.軟件學(xué)報(bào)，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—)，男，山東濰坊人。中國(guó)傳媒大學(xué)碩士研究生。Email:hanran@cuc.edu.cn。

(責(zé)任編輯

:龍學(xué)鋒)