一个基于椭圆曲线的可证明安全签密方案.docx
- 文档编号:5001339
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:9
- 大小:19.22KB
一个基于椭圆曲线的可证明安全签密方案.docx
《一个基于椭圆曲线的可证明安全签密方案.docx》由会员分享,可在线阅读,更多相关《一个基于椭圆曲线的可证明安全签密方案.docx(9页珍藏版)》请在冰点文库上搜索。
一个基于椭圆曲线的可证明安全签密方案
一个基于椭圆曲线的可证明安全签密方案
doi:
10.3969/j.issn.1001-3695.2010.03.069
Provablysecuresigncryptionschemebasedonellipticcurves
WANGTian-qin
(SchoolofComputerScience&InformationEngineering,HenanUniversity,KaifengHenan475001,China)
Abstract:
Signcryptioncanprovidesimultaneousdigitalsignatureandencryptionatalowcomputationalandcommunicationoverheadcomparedwiththesignature-then-encryptionapproach.Thispaperproposedasigncryptionschemebasedonellipticcurves.Basedonthetheoryofprovablesecurity,provedthisschemetobesecureundertheGDH(gapDiffie-Hellman)assumptionintherandomoraclemodel.Itissecureagainstadaptivechosenplaintext/ciphertextattack.
Keywords:
signcryption;GDHproblem;randomoraclemodel;provablesecurity
签密的概念是由Zheng[1]于1997年首次提出的。
签密能够在一个合理的逻辑步骤内同时完成数字签名和加密两项功能,而其计算和通信代价要低于先签名后加密方案,因而它是实现既加密又认证地传输和存储信息的较为理想的方法。
由于在电子商务、电子政务、密钥管理等方面都需要既保密又认证的信息传输,签密有着广阔的应用范围[2,3]。
由于椭圆曲线具有较好的密码学特性,基于椭圆曲线的密码算法能够提供更好的加密强度、更快的执行速度和更小的密钥长度,椭圆曲线在公钥密码学中有着广泛的应用。
自20世纪80年代中期椭圆曲线密码体制(ECC)被引入以来[4],其逐渐成为一个令人感兴趣的密码学分支,进而形成了一个研究热点。
许多实用的基于椭圆曲线的密码算法被提出。
可证明安全性理论是在一定的敌手模型下用归约的方法证明安全方案或协议能够达到特定的安全目标。
20世纪90年代Bellare等人[5]著名的RO(randomoracle)模型方法论的提出,使得过去仅作为纯理论研究的可证明安全性理论迅速在实际应用领域取得了重大进展[6]。
其基本思想是把hash函数看成随机函数,首先形式化定义方案的安全性,假设一个概率多项式时间(PPT)的敌手能够以不可忽略的概率破坏方案的安全性;然后模拟者为敌手提供一个与实际环境不可区分的模拟环境,回答敌手的所有询问;最后利用敌手的攻击结果解决基础困难问题。
本文基于文献[7]提出了一个基于椭圆曲线的签密方案,并在RO模型中给出了安全性证明。
与文献[8]的可证明安全签密方案相比,本文的方案能够抵御攻击能力更强的敌手,并且采用了不同的思路对方案的安全性予以证明。
1预备知识
本章简单地介绍了椭圆曲线群中的GDH(gapDiffie-Hellman)问题。
本文提出的签密方案的安全性依赖于GDH问题的困难性。
问题描述:
给定椭圆曲线群(〈P〉,+)中的任意元素aP、bP,以及DDH(decisionalDiffie-Hellman)OracleODDH(?
q,?
q,?
q,?
q),找到Diffie-Hellman密钥K=abP。
其中ODDH的功能是:
对于输入(P,Pu,Pv,z)∈(〈P〉,〈P〉,〈P〉,〈P〉),判定是否有z=uvP。
如果GDH问题从计算上说不可解,则称GDH假设成立。
确切地说,对于安全参数k和攻击者AGDH,定义下述游戏:
GDHgame(k,AGDH)
{a←RZ*q;b←RZ*q
K←AGDH(P,aP,bP|ODDH(?
q,?
q,?
q,?
q))
ifK==abPthenreturn1elsereturn0
}
其中:
←R表示从集合中随机选取元素对变量赋值;
AGDH(P,aP,bP|ODDH(?
q,?
q,?
q,?
q))表示算法在执行过程中可以对符号“|”之后的预言机作询问。
定义SuccGDH=maxPr[GDHgame(k,AGDH)=1]
这里max指对所有可能的敌手取最大值。
如果SuccGDH是关于k的可忽略函数,则称GDH假设成立。
2签密方案的形式化定义
2.1方案组成
签密方案由以下几个算法组成:
a)GC――系统初始化算法。
输入安全参数k,输出系统公共参数cp。
b)GK――密钥生成算法。
输入系统参数cp,输出用户密钥对(sk,pk)。
c)SC――签密算法。
输入系统参数cp,发送者的私钥skA,接收者的公钥pkB,明文m,输出签密C。
d)USC――解签密算法。
输入系统参数cp,接收者的私钥skB,发送者的公钥pkA,签密C,输出明文m或符号“⊥”表示解签密失败。
2.2敌手模型
假定敌手为第三方,即只考虑外部攻击,其目标是从签密信息中获取部分明文信息或伪造签密信息。
假定敌手可以选择任意接收者身份和明文对发送者的签密预言机进行询问,也可以选择任意发送者身份和密文对接收者的解签密预言机进行询问。
2.3安全性定义
定义1密文不可区分性。
设SCR=(GC,GK,SC,USC)为签密方案,O为敌手。
考虑以下游戏:
game(k,O,SCR)
{cp←GC(k)(skA,pkA)←RGK(cp)
(skB,pkB)←RGK(cp)
(m0,m1)←O(k,cp,find,pkA,pkB|SC(cp,skA,?
q,?
q),USC(cp,skB,?
q,?
q))
i←R{0,1}
C*←SC(cp,skA,pkB,mi)
i′←O(k,cp,guess,pkA,pkB,C*|SC(cp,skA,?
q,?
q),USC(cp,skB,?
q,?
q))
ifi′==i∧(pkA,C*)wasneverqueriedtoUSC(cp,skB,?
q,?
q)
thenreturn1elsereturn0
}
其中:
SC(cp,skA,?
q,?
q)表示以任意接收者公钥和明文对A作签密询问;USC(cp,skB,?
q,?
q)表示以任意发送者公钥和密文对B作解签密询问。
(下同)
O的优势定义为
AdvO=|2Pr[game(k,O,SCR)=1]-1|
以S0表示“game输出为1”这一事件。
如果没有任何PPT敌手能够以不可忽略的优势赢得游戏,则称签密方案SCR是密文不可区分的。
定义2不可伪造性。
设SCR=(GC,GK,SC,USC)为签密方案,O为敌手。
考虑以下游戏:
game-1(k,O,SCR)
{cp←GC(k)
(skA,pkA)←RGK(cp)
(C*,pkR)←O(k,cp,pkA|SC(cp,skA,?
q,?
q))
ifpkRisinvalidthenreturn0
m*←USC(cp,skR,pkA,C*)
ifm*≠“⊥”∧(pkR,m*)wasneverqueriedbyOtoSC(cp,skA,?
q,?
q)
thenreturn1elsereturn0?
ィ?
定义SuccO=Pr[game-1(k,O,SCR)=1]
如果没有任何PPT敌手能够以不可忽略的优势赢得游戏,则称签密方案SCR是不可伪造的。
3方案构造
签密方案SCR=(GC,GK,SC,USC)的细节描述如下:
GC(k)
随机选取长度为k的素数q,G1为由点P生成的阶为q的椭圆曲线循环乘法群,假定明文空间为{0,1}k,选取两个安全hash函数G:
G1→{0,1}k,H:
{0,1}*→Zq,cp=(G1,P,G,H)。
GK(cp)
对任意用户i,随机选取秘密数si∈Z*q,令Pi=siP,用户的公钥pki=Pi,私钥ski=siSC(cp,skA,pkB,m)
设skA=sA,pkA=PA,pkB=PB。
x←RZ*q,K←xPB,t←G(K),c←t?
m,r←H(m,PA,PB,K),s←x/(r+sA),C←(c,r,s)
USC(cp,skB,pkA,C)
设skB=sB,pkA=PA,pkB=PB,C=(c,r,s)。
W←s(PA+rP),K←sBW,t←G(K),m←t?
c,
ifH(m,PA,PB,K)==rthenreturnm
elsereturn“⊥”
4安全性分析
1)保密性关于方案的保密性,有以下定理。
定理1如果GDH假设成立,则SCR在本文假定的安全模型下具有密文不可区分性。
确切地说,有
Adv?
┆?
SCR(qG,qH,qSC,qUSC)≤2SuccGDH+(qH+qSC+qUSC)/2k-1+(qSC+qUSC)/2k-1+qSC(qG+qH+qSC+qUSC)/2k-1
其中qG、qH、qSC、qUSC分别表示各预言机被询问的次数。
证明不失一般性,本文假设信息的发送者为A,接收者为B。
设有模拟者M模拟游戏game中的SCR与敌手O作游戏game-1,回答O所提出的询问。
游戏规则修改如下:
a)对于敌手O在find阶段之后所生成的两个长度相等的明文m0、m1,M执行下列操作:
t+←R{0,1}k,i←R{0,1},c+←t+?
mi,r+←RZq,s+←RZ*q
回答C+←(c+,r+,s+)。
b)当G在K+=s+(r++sA)PB被询问时,直接返回t+之值。
c)当H在(mi,PA,PB,K+=s+(r++sA)PB)被询问时,直接返回r+之值。
d)假定SCoracle和USCoracle都是完备的,即对于签密询问,运用sA进行签密应答;对于解签密询问,运用sB进行解签密应答。
以S1表示“game-1输出为1”这一事件。
在敌手O看来,M所提供的模拟环境与实际环境类似,不同之处仅在于:
当H在find阶段中在点(mi,PA,PB,K+)被询问时回答有区别(这是因为mi只有在find阶段结束时才确定),H在该点被询问的次数最多为qH+qSC+qUSC。
因此有
|Pr[S1]-Pr[S0]|≤(qH+qSC+qUSC)/2k
(1)
对game-1进行修改,得游戏game-2。
游戏规则修改如下:
规则a)和d)不变。
b)G被询问时,直接返回Goracle之值;c)H被询问时,直接返回Horacle之值。
注意到,t+仅在计算密文c+时使用。
由于t+的随机性,仅有c+而区分m0和m1是不可能的,从而有
Pr[S2]=1/2
(2)
与game-1相比,不同之处在于:
如果G在K+被询问或H在(mi,PA,PB,K+)被询问,回答可能有差别(game-1中分别以t+、r+应答而game-2中均以随机数应答)。
从而有
|Pr[S2]-Pr[S1]|≤Pr[G在K+被询问或H在(mi,PA,PB,K+)被询问](3)
事件“G在K+被询问或H在(mi,PA,PB,K+)被询问”可以分为三种情形:
由敌手O直接询问,用ask2表示该情形;通过SCoracle询问;通过USCoracle询问。
则有
Pr[G在K+被询问或H在(mi,PA,PB,K+)被询问]≤Pr[ask2]+(qSC+qUSC)/2k(4)
进一步,用GSim、HSim分别代替游戏game-2中的Goracle、Horacle,得游戏game-3。
此时,M需要维护四张表GL1、GL2、HL1、HL2,用于跟踪对各预言机的询问,各表的初始状态均为空表。
模拟算法描述如下:
GSim(K)
{ifODDH(P,W,PR,K)==1
forsome(PR||W||(?
t))∈GL2thenreturnt
elseif(K,t)∈GL1thenreturnt
else{t←R{0,1}k;Add(K,t)toGL1;
returnt}
}HSim(m,PS,PR,K)
{ifODDH(P,W,PR,K)==1
forsome(PR||W||((m,PS,PR,?
),r))∈HL2
thenreturnr
elseif((m,PS,PR,K),r)∈HL1thenreturnr
else{r←RZq;
add((m,PS,PR,K),r)toHL1;
returnr}}
注意到,在此游戏中,GL2、HL2均为空表。
从而有
Pr[ask3]=Pr[ask2](5)
进一步,用SCSim、USCSim分别代替游戏game-3中的SCoracle、USCoracle,得游戏game-4。
模拟算法描述如下:
SCSim(PA,PR,m)
{t←R{0,1}k;c=t?
m;r←RZq;s←RZ*q
W=s(PA+rP)
add(PR||W||(?
t))toGL2
add(PR||W||((m,PA,PR,?
),r))toHL2
C←(c,r,s)
returnC
}
USCSim(PB,PS,C)
{W=s(PS+rP)
ifODDH(P,W,PB,K)==1
forsome(K,t)∈GL1or
ODDH(W,W′,PR,PB)==1
forsome(PR||W’||(?
t))∈GL2
thenm=t?
c
else{t←R{0,1}k;
add(PB||W||(?
t))toGL2;m=t?
c}
ifODDH(P,W,PB,K)==1
forsome((m,PS,PB,K),h)∈HL1or
ODDH(W,W′,PR,PB)==1forsome
(PR||W′||((m,PS,PR,?
),h))∈HL2
thenifh==rthenreturnm
elsereturn“⊥”
else{h←RZq;
add(PB||W||((m,PS,PB,?
),h))toHL2;
ifh==rthenreturnm
elsereturn“⊥”
}}
注意到,仅当SCoracle在点K+对G或H作过询问并且(K+,t)∈GL1或((m,PA,PR,K+),h)∈HL1时,模拟结果才会有误差。
因此有
|Pr[ask4]-Pr[ask3]|≤qSC(qG+qH+qSC+qUSC)/2k(6)
如果事件ask4发生,则说明表中有K+=s+(r++sA)PB存在。
有abP=sAPB=(K+-s+r+PB)1/s+。
进一步,其值可以通过DDHoracle找到(即对于表中的分量K,首先计算(K-s+r+PB)1/s+)=v,然后借助ODDH(P,PA,PB,v)找到正确的K值)。
也就是说,如果ask4发生,则可以解决GDH问题。
从而有
Pr[ask4]≤SuccGDH(7)
由式
(1)~(7)可得
AdvSCR(qG,qH,q?
┆?
SC,qUSC)/2=|Pr[S0]-1/2|≤SuccGDH+(qH+qSC+qUSC)/2k+(qSC+qUSC)/2k+qSC(qG+qH+qSC+qUSC)/2k
从而得到定理的结论。
关于算法的执行时间,通过直接计算不难得到,敌手攻破SCR与解决GDH问题的时间多项式等价。
2)不可伪造性关于方案的不可伪造性,有以下结论:
如果CDH假设成立,则方案SCR在本文假定的安全模型下具有不可伪造性。
运用与定理1的证明过程类似的方法,可以得到具体不可伪造性的度量结果。
3)安全性比较从安全性角度看,该方案能够抵御敌手的自适应选择明文/密文攻击。
与文献[8]中的方案相比,本文基于不同的计算假设,采用了不同的安全性证明思路。
5结束语
本文提出了一个基于椭圆曲线的签密方案,并在RO模型中给出了安全性证明。
在GDH问题难解的假设之下,该方案被证明是安全的。
从安全性角度看,该方案能够抵御敌手的自适应选择明文/密文攻击。
与文献[8]中的方案相比较,本文基于不同的计算假设,并且采用了不同的思路对方案的安全性予以证明。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一个 基于 椭圆 曲线 证明 安全 方案