基于ECC和零知識證明的盲簽名方案設(shè)計與實現(xiàn)*

白永祥

(渭南職業(yè)技術(shù)學院，陜西 渭南 714000)

基于ECC和零知識證明的盲簽名方案設(shè)計與實現(xiàn)*

白永祥

(渭南職業(yè)技術(shù)學院，陜西 渭南 714000)

橢圓曲線密碼系統(tǒng)具有穩(wěn)定的數(shù)學結(jié)構(gòu)和較高的安全性，與目前流行的RSA公鑰密碼系統(tǒng)相比較有很大優(yōu)勢，成為當前研究的熱點?；跈E圓曲線密碼體制，設(shè)計和實現(xiàn)了一種高效安全的盲簽名方案。首先，對相關(guān)概念及文獻進行了分析與比較，介紹了橢圓曲線密碼系統(tǒng)和盲簽名的基本原理；其次，基于橢圓曲線密碼系統(tǒng)的優(yōu)勢，設(shè)計了一種盲簽名新方案.在方案中，為了不向簽名者泄漏請求簽名者的身份信息，消息發(fā)送者使用零知識證明協(xié)議隱藏了身份信息；最后，對設(shè)計方案的盲化、不可追蹤性進行了分析，并與常見的盲簽名算法進了分析比較，證明了本設(shè)計方案的高效性。

橢圓曲線密碼系統(tǒng)；盲簽名；零知識證明；橢圓曲線離散對數(shù)問題

0 引 言

隨著Internet的廣泛應用，大量重要數(shù)據(jù)信息要通過互聯(lián)網(wǎng)絡(luò)到達目的地，在這個過程中，數(shù)據(jù)保密和安全認證顯得十分重要。在傳統(tǒng)簽名模式中，手寫簽名是所簽署的文件的物理部分，不可分割，而在計算機網(wǎng)絡(luò)上無法實現(xiàn)，比如簽名雙方不在同一地方，甚至相隔千里，于是，數(shù)字簽名技術(shù)便應運而生。數(shù)字簽名的作用與傳統(tǒng)的手寫簽名相同，只是數(shù)字簽名是在雙方不見面的情況下通過計算機網(wǎng)絡(luò)完成的一種簽名方式-電子簽名。數(shù)字簽名種類較多，這里只討論一種很有發(fā)展?jié)摿Φ奶厥鈹?shù)字簽名-盲簽名。盲簽名是David Chaum于1982年提出的一種簽名方案，還給出了一個基于RSA的實現(xiàn)方案[1]，盲簽名在電子投票和電子現(xiàn)金方面有著重要的應用。橢圓曲線密碼系統(tǒng)是近年來的研究熱點，它具有一定的優(yōu)勢，下面結(jié)合零知識證明技術(shù)，設(shè)計一種基于ECC的盲簽名方案。

1 相關(guān)理論

1.1 橢圓曲線密碼學

1985年，Neal Koblitz[2]和Victor Miller[3]各自獨立地提出了一種公鑰密碼系統(tǒng)，稱為橢圓曲線密碼系統(tǒng)(Elliptic Curve Cryptosystem ，ECC)。ECC以其較少的系統(tǒng)參數(shù)、密鑰短小、低帶寬、實現(xiàn)快速、低能耗和更小的硬件處理器需求等特性，顯示了其優(yōu)越的性能。因此，要建立一個安全高效的密碼系統(tǒng)，使用ECC是再合適不過的。應用于密碼學的橢圓曲線一般使用模素數(shù)的橢圓曲線，這里p>3是素數(shù)， 在p上的橢圓曲線同余方程如下：

y2(modp)≡x3+ax+b(modp)

它的所有解(x,y)∈p×p，定義O為一個特殊的無窮遠點，它們一起構(gòu)成p上的橢圓曲線y2=x3+ax+b。其中a,b∈p是滿足4a3+27b2≠0的常量。

橢圓曲線E上的加法運算定義如下[4]：

假設(shè)P,Q為曲線上的兩個點，且P=(x1,y1)，Q=(x2,y2)

(1)x1=x2且y2=-y1，則P+Q=O

(2)x1≠x2，則P+Q=R=(x3,y3)，R為PQ直線與橢圓曲線交點于X軸對稱點。

x3=λ2-x1-x2

y3=λ(x1-x2)-y1

對于所有的P∈E，定義 P+O=O+P=P

1.2 零知識證明

1989年，Goldwasser等人提出了零知識證明(Zero-knowledge Proof Protocol，ZKP)的概念[5]。所謂零知識證明就是指用戶A能夠在不向用戶B提供任何有用信息的前提下，使用戶B確認用戶A的某個論斷是正確的。其實，零知識證明是一種涉及A、B雙方或更多方的一種通信協(xié)議，即A、B雙方或更多方為了完成一項任務，卻不想泄漏相關(guān)信息所需要采取的一系列保護措施或步驟。用戶A向用戶B證明他知道或擁有某消息，而且用戶A在證明過程中不會向用戶B泄漏關(guān)于被證明消息的任何內(nèi)容。近年來，隨著人們網(wǎng)絡(luò)信息安全意識的增強，零知識證明在密碼學應用中非常廣泛，例如將零知識證明用于消息或身份驗證，可以防止信息泄漏。

1.3 盲簽名

1.3.1 概念及特性

所謂盲簽名[2]就是消息發(fā)送者Alice在發(fā)送消息之前，首先將消息m使用盲因子r進行盲化，再讓簽名者Bob對盲化后的消息m′進行簽名，最后用戶Alice對簽名除去盲因子r，得到關(guān)于原消息的簽名。在整個簽名過程中，Bob無法獲取所簽名消息的內(nèi)容，稱這種特殊的數(shù)字簽名技術(shù)為盲簽名。

比如：消息發(fā)送者Alice先將隱蔽的信件放進信封里，為了得到Bob的簽名，她在信封里放一張復寫紙，當信件被密封在信封中時，任何人不能讀它，包括Bob；Bob在信封上簽名，他的簽名便透過復寫紙印寫到信件上；信件返回給Alice后，Alice除去密封，并打開這個信封，得到簽名。

盲簽名除具有數(shù)字簽名的一般性質(zhì)外，還有自身的一些特征：

(1)機密性：簽名者只對消息實施簽名，而對所簽署消息的內(nèi)容是不可見的，關(guān)于這一點也存在一些爭議，比如可能給犯罪分子造成一些可乘之機；

(2)不可追蹤性：如果簽名需要仲裁，就必須打開簽名信息，簽名者不能確定何時為何內(nèi)容進行過簽名；

(3)防偽造性：簽名者使用自身的私鑰實施簽名，其他人都不可能假冒他的身份進行簽名，這是一條最基本的特征；

(4)防抵賴性：簽名者對某消息實施了簽名后，如果發(fā)生爭議，那么他無法否認曾經(jīng)對消息的簽名。

1.3.2 D. Chaum盲簽名方案

1982年，D. Chaum提出了盲簽名的概念，還給出了第一個基于RSA的實現(xiàn)方案[1]，具體過程如下：

Bob的公鑰為e，私鑰為d，n為一個公開模數(shù)，Alice打算讓Bob對消息m進行盲簽名。

(1)Alice隨機選擇k∈[1,n]，并計算t=mkemodn，隱藏m，然后發(fā)送t給Bob；

(2)Bob對t進行簽名：td=(mke)dmodn；

(3)Alice要揭開td，進行計算：s=td/kmodn；

(4)取掉盲因子，結(jié)果為：s=mdmodn，

這是因為：td≡(mke)d≡mdkmodn，

所以td/k=mdk/k≡mdmodn。

后來，Chaum又設(shè)計了一些更復雜的盲簽名算法，雖然這些在結(jié)構(gòu)上都比較復雜，但是更為靈活。我們在設(shè)計盲簽名方案時，必須考慮可操作性和高效性兩個重要因素，這兩個重要因素的實現(xiàn)都要依靠使用密鑰的長度、盲簽名算法和驗證算法的復雜度。

2 研究現(xiàn)狀

1982年，Chaum第一次提出了盲簽名的概念[1]；1995年，Camenisch 等提出了基于離散對數(shù)問題的盲簽名方案[6]，其缺點是不具有不可追蹤性；2005年，吳和王證明Camenisch方案的不可跟蹤性[7]，他們糾正了李的證明不可跟蹤性,得出的結(jié)論是Camenisch仍然比李的方案更有效率；后來，Jena等人提出了兩種新穎的盲簽名方案[8]，然而卻不能證明它們的正確性；最近Fan等人設(shè)計了一種攻擊這些盲簽名方案的方法[9]，因此，設(shè)計一種高效安全的盲簽名方案十分必要。

橢圓曲線密碼系統(tǒng)是一種公認的安全高效的公鑰密碼系統(tǒng)。文獻[10]已證明ECC效率比基于大整數(shù)因子分解或離散對數(shù)的公鑰密碼系統(tǒng)高10倍以上，當然這些得益于ECC的計算開銷小、短密鑰和低帶寬。ECC的安全性主要還是基于橢圓曲線離散對數(shù)難解問題之上。同大整數(shù)因子分解問題和離散對數(shù)問題一樣，目前很難找到一種有效算法解決橢圓曲線離散對數(shù)據(jù)問題，橢圓曲線離散對數(shù)難解問題比大整數(shù)因子問題和離散對數(shù)問題更難解決。文獻[11]提出了一種基于橢圓曲線離散對數(shù)問題的簽密方案。所有這些方案既有優(yōu)點，又有缺點，下面基于前人的研究成果，提出一種比較合理的盲簽名方案。

3 方案設(shè)計

方案包含了以下4個步驟：初始化及密鑰生成、消息盲化、簽名、去盲化和驗證，除去初始化及密鑰生成外，方案流程如圖1所示。

圖1 方案流程

3.1 初始化

在初始化階段，選擇一條安全的有限域Fp上的橢圓曲線Ep(a,b)，并產(chǎn)生一些公共參數(shù)，選擇基點等。

例如：

y2modp=(x3+ax+b)modp

a=1,b=1,x=10,y=6,p=13

62mod13=(103+10+1)mod13

10=10

同樣，可以計算出有限域橢圓曲線上的所有點，并運用加法原則和倍乘計算出對應的點，公式如下：

點加法：P+Q=R，且P≠Q(mào)

點倍乘：2P=R，且P=Q

橢圓曲線密碼系統(tǒng)的安全性，主要取決于定義在橢圓曲線上的有限阿貝爾群中點的個數(shù)。在有限群Ep(a,b)中，點的個數(shù)N的范圍是[12]：

所以，Ep(a,b)上點的個數(shù)約等于Zp中元素的個數(shù)，即p個元素。

(2)密鑰生成

計算出橢圓曲線Ep(a,b)上的所有點，選擇基點G=(x1,y1)，G的循環(huán)群階為n，且nG=O，O為無窮遠點。Ep(a,b)、G和n是公共參數(shù)。公鑰和私鑰產(chǎn)生過程如下：

①請求簽名者隨機在橢圓曲線上選擇點,并計算出公鑰和私鑰；

②簽名者隨機選擇一個小于n的整數(shù)ds，作為私鑰，再計算出公鑰Ps=ds×G，該公鑰也是Ep(a,b)中的一個點；

③簽名者再隨機選擇整數(shù)i，i∈Fp，然后他計算出點R1=iG，簽名者發(fā)回R1給請求簽名者；

3.2 盲化

發(fā)送者需要對消息m簽名后再發(fā)送給接收者，為了防止簽名者知道消息內(nèi)容，發(fā)送者需要對消息進行盲化后再發(fā)送給最終的接收者，整個過程如圖2所示。

圖2 盲簽名過程

發(fā)送者在E(Fp)隨機選擇一個點G'(x1,y1)，x1作為盲因子，然后再進行以下計算：

(2)再計算r=x0modn；

(3)對消息m進行盲化：m′=x1rm+y1；

(4)發(fā)送者把盲化后的消息傳送給簽名者。

3.3 證明和簽名

簽名者收到要求簽名的盲化后的消息m′后，使用零知識技術(shù)計算消息的真實值，驗證者再使用零知識技術(shù)進行驗證。簽名者通過向發(fā)送者詢問e的值{0,1}，驗證是否和發(fā)送者發(fā)送的消息相同，圖3和圖4為零知識證明過程。

圖3 e=1的證明過程

圖4 e=0的證明過程

簽名者收到要簽名的消息后，進行簽名：s′=dsm′+i，然后把盲簽名結(jié)果s′發(fā)送給請求簽名者。

3.4 去盲化

3.5 驗證

驗證者通過式子S=rmPs+R進行簽名驗證，對消息m簽名(R,S) 的有效性證明如下[13]：

圖5 盲簽名方案流程

4 方案分析

4.1 安全性能分析

我們的方案具有盲簽名的基本特性，即不可追蹤性、不可偽造性、不可抵賴性及簽名者不能識別簽名消息的內(nèi)容等。方案的安全性基于橢圓曲線離散對數(shù)問題的難解性。

(1)消息盲化

(2)不可追蹤性

簽名者也不可能依據(jù)參數(shù)(i,R1,m′,s′)對所簽名文件進行追蹤，因為簽名者不可能知道要求簽名者的參數(shù)(x1,y1,r)，要進行逆推導，就要面臨解決橢圓曲線離散對數(shù)問題的難題。

4.2 效率分析

我們對橢圓曲線上點加與點乘的時間復雜度進行了研究分析，相對于點乘的逆運算，點加所用時間很短，這里主要討論點乘和逆運算的情況。

下面是我們的方案與常見盲簽名方案所用時間對比如表1所示。

表1 3種方案時間開銷比較分析

從表1中數(shù)據(jù)看出我們的方案相對較好，事實上我們的盲簽名方案的安全性與另兩個方案相同。用戶和簽名者在簽名時只需要很少的操作步驟，所以我們的方案更有效。

5 結(jié) 語

本文提出了一種基于橢圓曲線離散對數(shù)問題和零知識協(xié)議的盲簽名方案，證明了方案的安全性和不可追蹤性。由于橢圓曲線密碼算法占用內(nèi)存少，運算速度快等原因，所以本方案的效率較高，同時本方案基于橢圓曲線離散對數(shù)問題，實現(xiàn)了以較短的密鑰與RSA相同安全性的效果。方案還基于零知識協(xié)議，使簽名請求者向簽名者證明自己知道或擁有某消息，但又未向簽名泄漏任何消息內(nèi)容和身份信息，所以，本方案能很好的應用于電子現(xiàn)金系統(tǒng)的支付，也能應用于匿名投票選舉。

[1] David Chaum. Blind Signatures for Untraceable Payments[C]// In Advances in Cryptology CRYPTO′82.California: Springer，1982：199-203.

[2] Koblitz N. Elliptic Curve Cryptosystems[J]. Mathematics of Compution,1987(48)：203-209.

[3] Miller V. Use of Elliptic Curves in Cryptography[C]// Advances in Cryptology-CRYPTO’85(LNCS 218).Santa Barbara：Springer，1986：417-426.

[4] 白永祥.一種高效群簽名方案的設(shè)計與分析[J].通信技術(shù)，2015(48)：214-218. BAI Yong-xiang. Design and Analysis of Efficient Group Signature Scheme[J].Communications Technology,2015(48)：214-218.

[5] Goldwasser, Micali, Rackoff. Knowledge Complexity of Interactive Proof-Systems[J].SIAM Journal of Computing.1989 (18)：186-208.

[6] Camenisch, Piveteau, Markus . Blind Signatures based on the Discrete Logarithm Problem[C]// In Advances in Cryptology Eurocrypt′94. Perugia:Springer 1994:428-432.

[7] WU Ting ,WANG Jin-rong. Comment: A New Blind Signature based on the Discrete Logarithm Problem for Untraceability[J]. Applied Mathematics and Computation, 2005,170(2)：999-1005.

[8] Jena, Kumar, Majhi. A Novel Untraceable Blind Signature based on Elliptic Curve Discrete Logarithm Problem[J]. IJCSNS International Journal of Computer Science and Network Security, 2007,7(6)：269-275.

[9] FAN, GUAN,LIN Dai-rui . Cryptanalysis of Lee Hwang-Yang Blind Signature Scheme[J]. Computer Standards & Interfaces, 2009,31(2)：319-320.

[10] Vanstone. Elliptic Curve Cryptosystem-the Answer to Strong, Fast Public Key Cryptography for Securing Constrained Environments[J]. Information Security Technical Report, 1997 (2)：78-87.

[11] Amounas, Sadki , Kinani. An Efficient Signcryption Scheme based on the Elliptic Curve Discrete Logarithm Problem[J]. International Journal of Information & Network Security (IJINS), 2013 (2)： 253-259.

[12] [加]Douglas R Stinson. 密碼學原理與實踐[M].第3版.馮登國等譯. 北京：電子工業(yè)出版社, 2015：201-207. Douglas R Stinson. Cryptography Theory and Practice [M]. Third Edition. Beijing: Publishing House of Electronic Industry, 2015：201-207.

[13] Amounas, Kinani. Proposed Developements of Blind Signature Scheme based on ECC[J]. Computer Engineering and Applications 2013(2)：151-160.

Design and Implementation of Blind Signature Scheme based on ECC and Zero-Knowledge Proof

BAI Yong-xiang

(Weinan Vocational & Technical College, Weinan Shaanxi 714000，China)

Owing to its robust mathematical structure and high security, elliptic curve cryptosystem enjoys obvious superiority as compared with current RSA public key cryptosystem, thus becomes the hottest research topic. Based on elliptic curve cryptosystem, an efficient and secure blind signature scheme is designed and implemented. The related concepts and documents are analyzed and compared, and the basic principles of elliptic curve cryptosystem and blind signature also described in this paper. Finally, a novel scheme of blind signature based on the advantages of elliptic curve cryptosystem is designed. In this scheme, message sender hides the identity information through zero-knowledge proof protocol, thus leaking no identity information of the request signer to the signer. Finally the blinding and untractability of the design scheme are analyzed, and comparison of and analysis on several common blind signature algorithms indicate the high efficiency of this design scheme.

elliptic curve cryptosystem； blind signature ；zero knowledge proof； elliptic curve discrete logarithm problem

10.3969/j.issn.1002-0802.2015.10.015

2015-05-21；

2015-09-03 Received date:2015-05-21；Revised date：2015-09-03

渭南市科技創(chuàng)新扶持資金資助(No.2013JCYJ-6)；渭南職業(yè)技術(shù)學院教研基金項目資助(No.WZJY201303)

Foundation Item：Weinan Fund Support Science and Technology Innovation(No.2013JCYJ-6)；Teaching & Research Project Fund of Weinan Vocational & Technical College (No. WZJY201303)

TP309.7

A

1002-0802(2015)10-1174-05

白永祥(1970—)，男，碩士，網(wǎng)絡(luò)工程師，副教授，主要研究方向為網(wǎng)絡(luò)與信息安全。