基于椭圆曲线密码体制的零知识身份认证

基于椭圆曲线的密码体制

第2 4卷第 4期V01 24 NO . .4

湖北工业大学学报 J u n l fHu e ie s t fTe h o o y o r a b iUn v r i o c n l g o y

20 0 9年 O 8月Au .2 09 g 0

[章编号]10—48 (0 9 0一0 10文 0 3 6 4 20 )4Q8—3

基于椭圆曲线密码体制的零知识身份认证耿亮，张凯凡，舒蕾(北工业大学理学院，湖北武汉 40 6 )湖 3 0 8[摘要]结合椭圆曲线密码体制和零知识证明的特点，出了一种新的身份认证方案 .安全性、算量及提在计

通信量等方面有较大优势 . [关键词]零知识证明；椭圆曲线密码；身份鉴别[图分类号]TP 0 .中 393[献标识码] A文：

现在 .们已经提出了多种基于零知识证明体人制 .中以 RS其 A零知识证明体制最为著名.安全其性是建立在基于大数分解问题的难解性，要求很它

1 1素数域上的椭圆曲线 .定义在 G q F( )上的椭圆曲线，曲线方程为 E,即Y= 8 =。+甜+ b,:3

高的大长度数据运算 .因而计算十分复杂.者利用作椭圆曲线算法的优点.计了一种新的零知识体制，设

记作 E( F( ) . G q ) G q )E( F( )和定义在 E( F( )上 G q)

算法中利用 E D P椭圆曲线离散对数问题的困难 C L (性构造)它与 R A零知识体制相比，安全性，, S在效率，密钥长度 .带宽，速度等方面具有更大的优势.

的加法运算“构成一个阿贝尔群，素 0为群的+”元单位元 .这个群是构造椭圆曲线密码系统的基础.椭圆曲线的群运算法则可化简为：a) ~ P: (c a,一 ), ( 1)

1椭圆曲线密码体制 18 9 5年 Vi o l r和 Ne l bi c rMie t l a Ko lz提出的 t

此运算为逆元运算 .b )P≠± Q时，P+ Q一 (,3 . 3 Y ) () 2

椭圆曲线密码体制 ( C )将椭圆曲线应用到密码 E C,学中，成为公钥密码学的一个重要分支 .主要优并其

其中3一 (一 l— 2 m o ) dp,

点是密钥尺度小，实现速度快以及安

全性比较高.由于 E C具有在同等安全强度下，以用较小 C可

I3一[ ( l 3一 Y] d . y J一 ) r 1mo p一

、

Z一 2

二 1 .Z 2i

的开销，计算量、储量、宽、件和硬件来实如存带软现，因此特别适用于计算能力和集成电路空间受限、 带宽受限、要求高速实现的情况，例如适用于 S r mat卡和无线应用环境.管椭圆曲线密码体制具有上尽述的诸多优点，目前它并没有完全替代其它的公但

此运算称为点加运算 .c )P— Q时，P+ Q: 2一 ( 3 3 . P -, ) , () 2

其中3一 (一 2 -) a1 mod, p

钥密码体制，因为它的实现速度受到制约，因此对椭圆曲线密码体制加解密速度的研究已经成为一个热点.

I 3 E ( l 3一 Y￣ d . Y一 a x— ) 1mo p

1 .此运算称为倍点运算.如果将椭圆曲线上的点 P自相加志次， k—即 P

椭圆曲线上的点乘运算是实现椭圆曲线密码体制的基本运算，同时也是最耗时的运算，的运算效它率直接决定着 E C的性能. C有效地提高了椭圆曲线中点乘的运算速度~ . [稿日期]2 0一o~ l收 O8 9 O

P+P+…十 P把计算结果记作 k,称此运算为 P则数乘 .

[者简介]耿作

亮 ( 97 ) 1 7一，男，湖北武汉人，北工业大学讲师，究方向：息安全湖研信

基于椭圆曲线的密码体制

82

湖北工业大学学报

20 0 9年第 4期

12椭圆曲线离散对数问题 .

椭圆曲线离散对数问题就是 Q— k Q, P( P均在曲线上 )给定 Q,求解 k的问题 .圆曲线密码系， P,椭统的安全性依赖于椭圆曲线离散对数问题的难解性.整数因子分解问题和一般离散对数问题与 ( L )样，目前为止还没有发现求解椭圆曲线 D P一到B .

3 )示证者A算出+∑ n 给者计 R, X并传验证= l

4验证者B核对(+∑ n P ) R )是否等于 X+i= 1

离散对数的有效算法.与整数因子分解问题和一但般离散对数问题不同，目前求解 E DL C P的算法都是全指数时间复杂度的算法，对前两个问题的

求而

∑“ . y3性能分析3 1正确性 .1 P: (十 R2 P— R。+ R )S R1 X) P XP— V+R2 . Vk k

解存在有亚指数时间复杂度的算法 .这种意义上从讲，圆曲线密码系统是目前安全性最高的公钥密椭码系统 .

2基于椭圆曲线的零知识证明方案 2 1零知识证明 .i=:1

2(+∑ a )R i) x P—R P+∑ n P—V X+i= 1 i= l

∑n . y3 2安全性 .

所谓零知识证明是指示证者使验证者确信自己 拥有某个秘密值，并没有向验证者泄漏该秘密值而

1攻击者截获 y,若想从 Y— X中求出 X, ) P, P 计算的困难性等价于在 K域上计算椭圆曲线的难度.

的任何有用信息 .于零知识证明的这种性质 .]基许多学者把它应用到需要验证用户的身份，时又不同

能暴露用户身份任何有关信息的身份识别系统中.2 2采用串行认证形式 .

2攻击者截获和 P,想从 V— R P求出R )若 或从— R中求出 R,算的困难性也等价于在 P计 K域上计算椭圆曲线的难度 . 3对于重放攻击，以看出，方案是基于挑 )可该战/应答方式，次认证的交换报文不同.每因此，即使攻击者可通过监听而获得一次认证中所交换的全部消息，当他想通过重新发送过时的消息以达到欺骗验证方时，若重发消息 R,假 由于验证方所生成的一

通过对被验证方唯一私钥的确认来实现零知识身份认证 .

将椭圆曲线的算法引入零知识证明，假设 E定义域在有限域 K上，生成元 P∈ E, P产生的群元由素足够多.证者 A选择一个整数 X作为他的私示钥，计算 Y— X将 y, P, P作为公钥 .验证者 B知使道.

次性随机数 R。每次认证中都不一样，在当要求被

可按如下步骤进行：

验证方计算 S—R十R。 时就会发觉是重放攻击.并行协议也是如此.

1示证者 A随机选取尺，算 V— R P,把 )计 并传给验证者 B . 2验证者 B随机选取 R。并传送给示证者 A . ), 3示证者 A计算出 S— R+R X,把 S传给 ) 并验证者

B.

4椭圆曲线密码体制 E C可以用较小的开销 ) C和时延实现较高的安全性.外 . C特别适用于另 E C计算能力和集成电路空间受限，宽受限，求高速带要

实现的情况.圆曲线在安全性、椭效率、密钥长度、带宽、度等方面均优于基于一般离散对数问题的密速

4验证者 B核对 S是否等于+Rz ) P y.2 3采用并行认证形式 .

码体制 .由于椭圆曲线上的一次群运算最终化为其背景上不超过 1 5次的乘法运算，因而便于实现 .在安全性要求相同的情况下， C只需较小的密钥长 EC

通过对被验证方若干私钥组合的确认来实现零知识身份认证，就是以并行方式执行次协议 .也 示证者 A选取 X,,, X… X作为私钥，并计算 Y一 X P(一 1 2…, )为公钥 . i,, k作 可按如下步骤进行 .

度就可以了. E C密钥长度为 1 0bt相当于如 C 6 i就RS密钥长度为 10 4bt达到的安全性 . A 2 i所]

1示证者 A随机选取 R, )计算 V— R并把 P,传给验证者 B.

4结束语 本文结合安全性高于其它密码体制的椭圆曲线密码体制和零知识证明的特点，出了一种新的身提

2验证者 B产生 k个任意数 ( a,,, ) a,… a )并 z传送给示证者 A .

基于椭圆曲线的密码体制

第2 4卷第 4期

耿

亮等

基于椭圆曲线密码体制的零知识身份认证

8 3

份识别方案.它是建立在椭圆曲线密码体制之上的.它具有椭圆曲线密码体制所具有的优点，用的密使

d a p, a e c s ig o .[] W a e Tr p e L wrn e C Wa hn tn密码学概论 3

( 1版 ) M]邹红霞，鹏文，勇奇译 .京，民第[ .许李北人邮电出版社， 0 4 1 4 2 1 2 0:9— 0 .

钥量更小，运算速度更快.计算量和通信量也大为降

低.方案还可以推广到电子支付、该信用卡等要求较高安全性的认证系统中.

[]肖攸安 .圆曲线密码体系研究 ( 1版 ) M]武汉： 4椭第[ .华中科技大学出版社， 0 6 5—6,0—2 5 2 0:6 0 2 9 l .

I] B u e c nir译应用密码学协议、法

与 c源程序 s rc h c . S e算[ .世忠.京：械工业出版社，0 0 7—7 . M]吴北机 20:1 5 []杨霄彩， 6郑强，一然 .种基于椭圆曲线零知识身杨一

[参考文献]

份认证的改进方法[]计算机与现代化， 0 7 9: 4 J. 2 0 ( ) 2—

26 .

[]卢开澄 .算机密码学 ( 2版 ) M]北京，华大学 1计第[ .清出版社 . 9 8 2 1 4 . 1 9:4—2 3

r] 7L J

林

华，荣波 .圆曲线密码算法在零知识证明方案鲁椭

中的应用[]信息安全与通信保密， 0 7 3:9一 J. 20 ( ) 9】O 】.

[] W 2

il m alng . y o a hy a d N e wor c rt li a St li s Cr pt gr p n t k Se u iy

P ic ls n rci s F ut dt n第 4版 ) M] r i e dP a t e, o r E i o ( n p a c h i[ .北京：电子工业出版社，0 6:0~3 3 2 0 3 1 1.

Ze o k o e g d ntt t e i a i n r。 n wl d e I e iy Au h ntc to Ag e m e tBa e n Eli tc Cu v r e n s d o lp i r eG EN G a Ling,ZH A N G a—a K if n,SH U i Le

( c o l f S in e, b i i . f Teh oo y, h n 4 0 6。 ia S h o ce c Hu e v o c n lg Wu a 3 0 8 Ch n ) o UnAb t a t s r c:Th s p pe o os s a ne z r— no e e p oo r t c lofi e tfc to ih c i a r pr p e w e o k wldg r f p o o o d n iia i n wh c omb ne h i ste c a a t rs is o h h r c e itc ft e ECC n e o kn wl d o f The p op s d p ot o s mor d a a e n t e a d z r— o e ge pr o . r o e r oc lha e a v nt g s i h a pe to h a tt fc mpu i g a d t a fc s c ft e qu n iy o o tn n r fi.Ke wo d y

r s￣Ze o kno ldg oo; l i u v s Cr p o s t m; d ntt u he i a i n r— w e e pr f Eli c c r e y t ys e pt I e iy a t ntc to

[任编校：张培炼]责