SM2椭圆曲线门限密码算法 - 密码学报201402

密码学报 ISSN 2095-7025 CN 10-1195/TN E-mail: jcr@

Journal of Cryptologic Research,2014,1(2):155–166 ©《密码学报》编辑部版权所有. Tel/Fax: +86-10-81033101

SM2椭圆曲线门限密码算法*

尚 铭1, 马 原1,2,3, 林璟锵2,3, 荆继武2,3

1. 中国科学院大学, 北京 100049

2. 中国科学院数据与通信保护研究教育中心, 北京 100093 3. 中国科学院信息工程研究所, 北京 100093 通讯作者: 马原, E-mail: yma@

摘 要: 在门限密码学中, 私钥信息被分享给独立的多个参与者, 每一次私钥计算都需要多个参与者同意, 从而提高算法安全性; 而且当少量参与者发生故障、不可用时,不影响私钥的可用性. 一个安全的(t,n)门限密码算法应当满足: (1)任意多于t个参与者可以计算最终的签名、交换的密钥或明文, 而t个或少于t个参与者不能得到关于以上结果的任何信息; (2)在算法执行过程中不泄露关于私钥和参与者的子私钥的任何信息. 相比于其他密码体制, 椭圆曲线密码体制在达到相同安全性的条件下所需要的密钥更短, 因此具有优越性. 本文基于最近发布的SM2椭圆曲线公钥密码算法, 提出了安全有效的门限密码方案, 包括门限签名算法、门限密钥交换协议和门限解密算法, 同时分析了上述算法的安全性和效率。本文提出的门限密码算法可支持有可信中心和无可信中心的不同情况, 并且具有较小的通信复杂度. 安全分析表明, (1)在n.2t+1(n.3t+1)情况下, 提出的门限签名方案可容忍对t个成员的窃听(中止)攻击, (2)在n.t+1(n.2t+1)情况下, 提出的门限密钥交换和门限解密算法可以容忍对t个成员的窃听(中止)攻击.

关键词: SM2椭圆曲线密码算法; 门限密码学 中图法分类号: TP309. 7 文献标识码: A

中文引用格式: 尚铭, 马原, 林璟锵, 荆继武. SM2椭圆曲线门限密码算法[J]. 密码学报, 2014, 1(2): 155–166. 英文引用格式: Shang M, Ma Y, Lin J Q, Jing J W. A threshold scheme for SM2 elliptic curve cryptographic algorithm[J]. Journal of Cryptologic Research, 2014, 1(2): 155–166.

A Threshold Scheme for SM2 Elliptic Curve Cryptographic Algorithm

SHANG Ming1, MA Yuan1,2,3, LIN Jing-Qiang2,3, JING Ji-Wu2,3

1. University of Chinese Academy of Sciences, Beijing 100049, China

2. Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing 100093, China 3. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China Corresponding author: Ma Yuan, E-mail: yma@

Abstract: In threshold cryptography, a private key is shared among multiple participants, and any private-key computation involves a threshold number of participants, hence to improve the security. When a small number of participants are unavailable, the shared private key is still available. A secure threshold cryptographic algorithm should satisfy that, (1) any t players can figure out the signature, the exchanged 基金项目: 国家重点基础研究发展项目(973计划)(2013CB338001)

收稿日期: 2013-12-15 定稿日期: 2014-03-14

156 Journal of Cryptologic Research 密码学报 Vol.1, No.2, Apr. 2014

key or the plaintext, and t or less than t players cannot obtain any available information of the above results, and (2) the execution of the algorithm must not leak any information about the key or the subkeys. Compared with other cryptosystems, elliptic curve cryptosystem uses a much shorter key to achieve an equivalent level of security, thus is superior. In this paper, we design a threshold scheme for the SM2 elliptic curve cryptographic algorithm, consisting of a threshold signature scheme, a threshold key exchange protocol and a threshold decryption algorithm. In addition, we analyze the security and efficiency of the proposed SM2 threshold schemes. Our schemes can work with or without a trusted dealer, and have a small communication load. The security analysis indicates that, (1) the proposed threshold signature algorithm is secure in the presence of t eavesdropping (halting) faults if the total number of players is n.2t+1 (n.3t+1), (2) the proposed threshold key exchange protocol and threshold decryption algorithm are secure in the presence of t eavesdropping (halting) faults if the total number of players is n.t+1(n.2t+1). Key words:

SM2 elliptic curve cryptographic algorithm; threshold cryptography

1 引言

对于一个(t,n)秘密分享方案[1], 任意多于t个参与者可以恢复出秘密, t个或少于t个参与者不能得到关于秘密的任何信息; 门限密码算法是在秘密分享方案的基础上构建而来. 门限密码算法中的私钥信息被分享给独立的多个参与者, 每一次私钥计算都需要多个参与者同意, 从而提高算法安全性和健壮性; 当少量参与者发生故障、不可用时, 不影响私钥的可用性. 一个合理的(t,n)门限密码算法应当满足: (1)任意多于t个参与者可以计算最终的签名、交换的密钥或明文, 而t个或少于t个参与者不能得到关于以上结果的任何信息; (2)在算法执行过程中不泄露关于私钥和参与者的子私钥的任何信息.

目前的门限密码一般可以分为需要可信中心和不需要可信中心两类. 当可信中心存在时, 可以方便地实现秘密分发, 减少小组成员之间的通信量和计算量; 但一个被小组内所有成员信任的可信中心并不是一直存在的, 此时需要小组成员联合实现对秘密的分享, 即无可信中心方案.

门限签名作为门限密码学的重要研究内容, 最早由Desmedt[2]等人提出. 1991年Desmedt和

Frankel提出了基于RSA的(t,n)门限签名方案[3], Wang等人给出了基于离散对数的门限签名方案[4], 此后Harn在1994年提出了基于ElGamel的、不需要可信中心的门限签名方案[5]. Gennaro等人解决了

DSS(Digital Signature Standard)签名方案的构造[6], 提出了秘密乘积、求逆运算的分享方法, 并基于多种分布式可验证秘密分享方案来构造一个健壮安全的门限DSS签名. Miyazaki[7]在2001年提出了一个基于椭圆曲线EIGamal的门限签名方案. 门限加解密算法广泛应用在在分布式系统中以保护数据安全. 门限解密可以用来保证存储系统中的数据机密性和完整性[8], 以及保证密钥管理系统的安全性[9].

因为基于椭圆曲线上离散对数问题的困难性要高于一般乘法群上的离散对数问题的困难性, 且椭圆曲线所基于的域的运算位数要远小于传统离散对数的运算位数, 椭圆曲线密码体制比原有的密码体制(如RSA和DSA)更具优越性. 2010年底, 我国国家密码管理局发布了SM2椭圆曲线公钥密码算法[10], 包括数字签名算法、密钥交换协议和公钥加解密算法. 作为我国的首个发布的公钥密码算法标准, SM2算法旨在保障各类信息系统的安全, 对我国商用密码产品和信息安全体系建设意义重大.

本文首先分析了SM2数字签名算法, 并针对存在可信中心和不存在可信中心的情况, 分别提出了门限签名方案; 接着, 设计了门限密钥交换协议和门限解密算法; 然后分析了上述门限密码算法的安全性. 安全分析表明, 在n>2t条件下, 任何2t+1个参与者集合可以生成一个有效的数字签名; 我们的门限签名方案可以抵抗n/2的窃听攻击和n/3中止攻击. 最后, 对方案的效率和安全性进行了分析.

尚 铭 等: SM2椭圆曲线门限密码算法 157

2 安全模型与定义

2.1 敌手模型

假设敌手A可以至多攻击n个成员中的t个, 我们定义了如下三种敌手

(1) 窃听(eavesdropping)敌手, 可以获得用户节点的存储信息以及窃听到所有广播的消息; (2) 中止(halting)敌手, 可以在每轮通信开始的时候让用户中止发送消息; (3) 恶意(malicious)敌手, 除了具有窃听能力, 还可以迫使用户修改协议

我们假设敌手的计算能力是在概率多项式图灵机模型下的, 因此是无法求解椭圆曲线上的离散对数问题的. 敌手类型又可以分为静态的(static)和自适应的(adaptive), 静态敌手在协议开始前选定要攻击的用户, 而自适应敌手可以在计算中选择. 本文针对窃听和中止敌手, 而且只考虑静态敌手的情况. 对于恶意敌手, 可以在方案中引入可验证的密码分享技术来容忍恶意敌手; 对于自适应敌手, 可以采用Canetti等人[11]提出的技术对方案进行改进来容忍自适应敌手, 这将是本文的下一步工作. 2.2 安全性定义

本文定义的门限方案的安全性包括不可伪造性/保密性和健壮性, 定义如下.

定义1((t,n)门限签名方案的不可伪造性) 给定系统参数, 敌手A最多可以破坏t个成员, 可以拥有交互运行中的视图, 可以进行k次适应性的选择消息m1,",mk的门限签名查询, 而最终敌手A能产生一个新消息m的门限签名的伪造的概率是可忽略的.

定义2((t,n)门限密钥交换方案的保密性) 给定系统参数, 敌手A最多破坏t个成员, 可以拥有交互运行中的视图, 可以进行k次适应性的选择协商密钥K1,",Kk的查询, 而最终敌手A能成功冒充成员进行密钥协商的概率是可忽略的.

定义3((t,n)门限解密方案的保密性) 给定系统参数, 敌手A最多可以破坏t个成员, 可以拥有交互运行中的视图, 可以进行k次适应性的选择密文C1,",Ck的门限解密结果查询, 而最终敌手A能解密新密文C的概率是可忽略的.

定义4((t,n)门限签名/密钥交换/解密方案的健壮性) 在敌手A最多可以破坏t个成员的情况下, 方案仍然能够成功的运行.

3 SM2椭圆曲线公钥密码算法

SM2椭圆曲线公钥密码算法包括了数字签名算法、密钥交换协议和公钥加密算法3部分. 3部分使用相同的公钥和私钥, 但设计了不同的算法来实现数字签名、密钥交换和公钥加解密功能.

在使用SM2算法之前, 各通信方先设定相同的公开参数, 包括p、q、E和G: p是大素数, E是定义在有限域Fp上的椭圆曲线, G=(xG,yG)是E上q阶的基点. 3.1 数字签名算法 密钥产生:

(1) 随机选取秘密d,d∈[1, 1q ];

(2) 计算P=dG, 并将P作为公钥公开, d作为私钥保存. 签名生成:

(3) 签名者选取随机数k∈[1, 1q ], 计算kG=(x1,y1);

158 Journal of Cryptologic Research 密码学报 Vol.1, No.2, Apr. 2014

(4) 计算r=(Hash(m)+x1)modq, 其中m是待签名的消息, Hash( )为单向哈希函数; 若r=0或

r+k=q, 则重新选取随机数k;

(5) 计算s=(1+d)(k rd)modq; 若s=0, 则重新选取随机数k; 否则, 将(r,s)作为签名结果. 签名验证:

1

(6) 验证者接收到m和(r,s)后, 先检查是否满足r,s∈[1, q 1]且r+s≠q; 然后计算

(x1′,y1′)=sG+(r+s)P;

′)modq; 判断r′与r是否相等, 若二者相等则签名验证通过, 否则验证(7) 计算r′=(Hash(m)+x1

失败.

3.2 密钥交换协议

PA、PB和dA、dB分别表示用户A和B的公钥和私钥, ZA和ZB分别表示A和B的唯一标识, &

表示数据拼接, &表示比特与运算, KDF(ks,klen)是密钥派生函数: 以ks为种子、产生klen比特的伪 log2(q) 1. 随机序列, 记ω=

()

用户A

(A.1) 选取随机数rA∈[1, 1q ], 计算RA=rAG=(x2,y2)并发送给用户B; 用户B

(B.1) 选取随机数rB∈[1, 1q ], 计算RB=rBG=(x3,y3)并发送给用户A; (B.2) 计算xB=2w+(x3&(2w 1))和tB=(dB+xBrB)modq;

(B.3) 验证接收到的RA是椭圆曲线E上的点, 验证通过后计算xA=2w+(x2&(2w 1));

(B.4) 计算V=tB(PA+xARA)=(xV,yV); 若V是椭圆曲线E上的无穷远点, 则重新选取rB、重新

协商;

(B.5) 计算KB=KDFxVyVZAZB,klen; 用户A

()

(A.2) 计算xA=2w+(x2&(2w 1))和tA=(dA+xArA)modq;

(A.3) 验证接收到的RB是椭圆曲线上的点, 验证通过后计算xB=2w+(x3&(2w 1));

(A.4) 计算W=tA(PB+xBRB)=(xW,yW); 若W是椭圆曲线E上的无穷远点, 则重新选取rA、重新

协商;

(A.5) 计算KDFxWyWZAZB,klen; 3.3 公钥加解密算法

M是比特长度为mlen的明文, ⊕表示比特异或.

()

加密算法:

(1) 选取随机数l∈[1, 1q ], 分别计算C1=lG=(x4,y4)和lP=(x5,y5); (2) 计算e=KDF(x5y5,mlen);

(3) 计算C2=M⊕e和C3=Hash(x5My5);

尚 铭 等: SM2椭圆曲线门限密码算法 159

(4) 输出密文C=C1C3C2. 解密算法:

(1) 验证C1是否在椭圆曲线上, 计算dC1=(x5,y5); (2) 计算e=KDF(x5y5,mlen); (3) 计算M=C2⊕e;

′=Hash(x5My5), 并验证C3′=C3是否成立, 若不成立则报错退出; (4) 计算C3

(5) 输出明文M.

4 门限密码预备知识

4.1 Shamir秘密分享方案(SS)

在Shamir(t,n)门限秘密分享方案中, 可信中心把秘密d拆分成n份, 分发给n个参与者U1,U2,",Un. 任意t+1个或t+1个以上的参与者一起可恢复秘密d, 任意t个参与者一起不能得到秘

密d的任何信息. 详细方案如下:

(1) 可信中心秘密构造t阶多项式f(x)=∑aixi, 其中秘密d=f(0)=a0;

i=0

t

(2) 可信中心计算di=f(i), 并秘密地把di分别发送给参与者Ui, 1-i-n; (3) Ui将di作为份额保存.

上述过程称为t阶SS, 并称多项式f(x)为分享多项式. 此时, 任意t+1个参与者集合Q可通过拉格朗日插值公式d=∑(di

i∈Q

j∈Q,j≠i

∏

j

恢复出秘密. j i

4.2 联合Shamir随机秘密分享(Joint-RSS)

在联合Shamir随机秘密分享中, n个参与者U1,U2,",Un分别选择任意的秘密值, 并各自按照“可信中心”的步骤来分发所选秘密值的份额, 从而实现对一个随机值的秘密分享. 该随机值等于所有被分享的秘密值之和, 整个过程不需要可信中心的参与. 详细过程如下:

(i)

(1) 每个参与者Ui将自己作为“可信中心”, 选取随机的秘密值a0, 构造多项式为

fi(x)=∑a(ji)xj, 执行t阶SS;

j=0

t

(2) Uj(1-j-n)收到其余n 1个参与者Ui(1-i-n,i≠j)发送给自己的fi(j), 计算σj=∑fi(j)作

i=1

n

为Uj的份额.

()上述过程称为t阶Joint-RSS, 此时参与者们分享的秘密为σ=∑a0, 相应的分享多项式为

i

i=1n

f(x)=∑ajxi, 其中aj=∑a(ji).

j=0

tn

i=1

4.3 联合Shamir零秘密分享(Joint-ZSS)

联合Shamir零秘密分享与联合Shamir随机秘密分享类似; 不同的是, 此时每个参与者Ui选取的

160 Journal of Cryptologic Research 密码学报 Vol.1, No.2, Apr. 2014

(i)

=0, 所以参与者分享的秘密a0也为0. 秘密a0

4.4 秘密和/差的分享

假设参与者Ui已经得到了u和v的t阶SS分享份额: ui=fu(x)、vi=fv(x), 其中u=fu(0)、

v=fv(0), fu(x)和fv(x)是不同的t阶多项式.

容易看出, 每个参与者Ui分别计算zi=ui±vi即可得到秘密和/差z=u±v的秘密分享份额, z的分享多项式是fz(x)=fu(x)±fv(x), fz(x)也是t阶的. 4.5 秘密乘积的分享[6](Mul-SS)

与秘密和/差的分享类似, 参与者Ui将自己的分享份额ui与vi相乘, 就可实现对乘积h=uv的秘密分享. 此时, 分享多项式fh(x)=fu(x)×fv(x)的阶数为2t, 也就是说需要至少2t+1个参与者才能恢复秘密uv. 需要注意的是, fh(x)是由两个t阶多项式相乘得到, 所以fh(x)不是不可约多项式, 例如

fh(x)不可能是x2+1. 因此fh(x)的系数并不是完全随机的, 这就会降低安全性. 为此, 需要对fh(x)进一步“随机化”: 加上随机的2t阶多项式, 使其系数完全随机. 详细过程如下:

(1) 参与者执行2t阶Joint-ZSS, Ui的分享份额为αi, 作为随机化因子; (2) Ui计算hi=uivi+αi作为对秘密h=uv的分享份额.

此时参与者们分享的秘密为uv, 至少2t+1个参与者Ui广播其hi, 通过插值公式可以恢复出

h=uv.

4.6 秘密逆的分享[6](Inv-SS)

设Ui已经分享了u, 份额是ui. 逆分享的基本思想为首先分享一个随机秘密β, 在计算(βu)的基础上得到c=u 1 mod q的分享份额. 逆的分享过程如下:

1

(1) 参与者集合执行t阶Joint-RSS分享随机秘密β, 分享份额为βi;

(2) 至少2t+1个参与者执行3. 5节中u与β乘积的分享过程Mul-SS, 并广播自己乘积的分享份额

(βu)i;

(3) Ui记录广播的(βu)j(1-j-n), 通过插值公式计算出βu, 并计算ci=(βu)βimodq得到u 1的

分享份额.

需要注意的是, 广播(βu)i不会影响机密性, 因为βi随机并且保密, 所以ui的信息不会泄露. 由于分享随机数β的多项式是t阶, 所以c的分享多项式也是t阶, 也就是说虽然需要至少2t+1个参与者才能得到分享份额ci, 但t+1个ci的持有者就可以恢复出c. 4.7 点乘的分享(PM-SS)

1

Shamir秘密分享方案可以直接应用在椭圆曲线上点乘运算的分享中. 设Ui已经分享了u, 份额是ui, 任意t+1个参与者的集合Q计算通过分享uiG计算uG的过程如下:

(1) 至少t+1个Ui计算点乘uiG, 并广播; (2) Ui通过插值公式计算

j j

uG= ∑ui∏ G=∑(uiG)∏j ij ii∈Qj∈Q,j≠ii∈Qj∈Q,j≠i

尚 铭 等: SM2椭圆曲线门限密码算法 161

5 SM2椭圆曲线门限密码算法

5.1 SM2门限签名方案(SM2-Sign-Thresh)

门限签名方案一般包括三个部分: 密钥产生、签名生成和签名验证. 在密钥产生阶段, 参与者们(通过可信中心, 或不通过可信中心)对私钥分享并公开公钥; 签名生成时, 每个参与者首先通过秘密分享的方式计算得到r, 而后得到s的分享份额si, 超过门限个的参与者广播其si则可通过插值公式计算出签名s; 在签名验证时, 直接对签名结果(r,s)进行验证.

对于SM2门限签名方案, 需要分享的秘密为私钥d. 但是, 对于随机数k, 因为在已知签名(r,s)和k的情况下, 参与者可以推导出私钥d, 所以在签名过程中k也必须保密.

为了降低复杂度, 我们对SM2签名方案中s计算式进行如下等价变形:

s=(1+d)

1

(k rd)=(1+d)(k (1+d)r+r)=((1+d)(k+r) r)modq

1

1

1

可以看出, 上式只用到了(1+d)而没有单独用到d. 接下来, 在以上讨论和分析的基础上, 我们针对存在和不存在可信中心的情况, 分别提出了安全有效的SM2算法门限签名方案. 可信中心只在密钥产生时参与, 签名生成和验证时并不需要可信中心参与.

对于存在可信中心的情况, 密钥产生比较简单, 可信中心可以直接将(1+d)作为秘密, 通过t阶

1

SS分享给参与者; 对于不存在可信中心的情况, 参与者们需要联合分享秘密, 每个参与者Ui独立生成

()

秘密a0, 通过t阶Joint-RSS分享私钥d, ,再执行Inv-SS得到(1+d)的分享份额用于门限签名.

i

1

签名生成阶段, 参与者首先通过Joint-RSS分享随机数k, 执行PM-SS计算r, 在分享(1+d)和

1

(k+r)的基础上, 执行

Mul-SS, 再减去r即可得到子签名si, 最后, 超过2t+1个参与者广播其子签名

就可以通过插值得到签名(r,s). 门限签名详细过程如下. 5.1.1 密钥产生

A. 存在可信中心

给定门限t, 参与者集合{U1,U2,",Un}, n.2t+1. 可信中心随机选取一个整数d作为私钥保密, 计算P=dG作为公钥公开.

秘密分发时, 计算d′=(1+d)modq并执行t阶SS, 将d′分享给参与者Ui.

1

B. 不存在可信中心

对于参与者集合{U1,U2,",Un}, n.2t+1. 每个参与者Ui首先执行t阶Joint-RSS, 分享秘密为私钥d, 分享份额为子私钥di; 参与者集合执行PM-SS得到公钥P=dG.

由于在签名时需要用到d′=(1+d), 因此参与者需要将d′分享, 执行Inv-SS得到d′的分享份额di′. 具体过程如下:

1

(1) 参与者集合执行t阶Joint-RSS和2t阶Joint-ZSS, 分享份额分别为βi和αi; (2) Ui计算γi=βi(1+di)+αi并广播;

(3) Ui记录广播的γj(1-j-n), 通过插值公式恢复出γ=β(1+d); (4) Ui计算di′=γ 1βi得到(1+d)的分享份额.

5.1.2 签名生成

至少2t+1个参与者Ui执行以下过程对消息进行签名生成:

1

162 Journal of Cryptologic Research 密码学报 Vol.1, No.2, Apr. 2014

(1) 执行2t阶Joint-ZSS, 分享份额μi;

(2) 执行分享随机秘密k的t阶Joint-RSS, 分享份额为ki;

(3) 执行PM-SS得到点乘kG=(x1,y1), 并计算r=Hash(m)+x1modq; (4) Ui计算si=di′(ki+r)+μi r, 得到签名s的分享份额si; (5) 至少2t+1个参与者Ui广播其si; (6) Ui通过插值公式得到签名结果s.

5.1.3 签名验证

门限签名验证过程和3.1节中的签名验证是一致的.

5.2 SM2门限密钥交换协议(SM2-Exch-Thresh)

对于SM2门限密钥交换协议, 由于不需要秘密乘积或秘密逆的分享, 因此在密钥产生时与5.1节略有不同. 当存在可信中心时, 可信中心执行t阶SS将私钥dA和dB分别分享给参与者集合A和

B; 当不存在可信中心时, A和B分别执行t阶Joint-RSS分享私钥dA和dB, 并执行PM-SS得到公钥PA和PB.

密钥交换时, 至少t+1个B的参与者, 进行如下过程进行门限密钥交换(参考3.2节, 这里只列举了B需要用到门限密码的部分B.1、B.2和B.4):

(B.1.1) 执行t阶Joint-RSS, 共享随机数rB, 共享份额为rB,i;

(B.1.2) 执行PM-SS, 计算RB=rBG=(x3,y3); (B.2)

Ui计算xB=2w+(x3&(2w 1))和tB,i=(dB, i+xBrB,i)modq, 秘密保存tB,i;

(B.4.1) Ui计算Vi=tB,i(PA+xARA)=(xV,i,yV,i);

(B.4.2) 通过插值公式恢复出点V; 若V是椭圆曲线E上的无穷远点, 则重新选取rB,i、重新

协商.

5.3 SM2门限解密算法(SM2-Decry-Thresh)

与门限密钥交换中的密钥产生过程一致, 在门限解密算法中, 参与者集合{U1,U2,",Un}分享私钥

d, 分享份额为di. 在这里, 我们对3.3节解密过程中的第(1)步进行扩展, 其他步骤没有用到门限密码的知识. 至少t+1个参与者:

(1.1) Ui计算di和点P点乘diC1=(x5,i,y5,i); (1.2) 通过插值公式恢复出点dC1=(x5,y5).

6 安全性和效率分析

6.1 安全性

根据文献[12]有:

引理1[12] 如果签名方案是不可伪造的, 而且门限签名方案是可模拟的, 那么这个门限签名方案也是不可伪造的.

引理2 对于t个成员的的窃听攻击, 如果n.2t+1, 那么(t,n)门限签名方案SM2-Sign-Thresh是健壮的; 对于t个成员的中止攻击, 如果n.3t+1, 那么(t,n)门限签名方案SM2-Sign-Thresh是健壮的.

证明: 根据式si=di′(ki+r) +μi r, 由于分享d′和k的多项式都是t阶, 那么分享s的多项式是

2t阶, 所以2t+1以上个参与者广播其子签名si, 能通过插值公式恢复出签名s, 也即是说, 需要至少

尚 铭 等: SM2椭圆曲线门限密码算法 163

2t+1个参与者就能完成签名. 因此, 对于t个成员的中止攻击, 需要保证n≥3t+1才能完成签名过程. 证毕.

引理3 门限签名方案SM2-Sign-Thresh在t个成员的窃听攻击下是不可伪造的.

证明: 首先证明门限签名方案是可模拟的. 方案的模拟过程如图1所示. 输入公钥P, 消息m, 签名(r,s), 不失一般性, 设一个敌手可以控制前t个参与者: 对他们进行窃听攻击或者中止攻击, 其′,",dt′, 容易证明通过私钥份额di执行Inv-SS得到di′余参与者为诚实参与者. 因此控制的份额为d1′,d2

的过程是安全的.

从图1不难看出, 模拟协议SIM与签名方案SM2-Sign-Thresh中的变量是一致的, 接下来我们证明他们具有相同的概率分布.

(1) 因为Shamir的秘密分享方案是信息论安全的, 因此所有的分享份额具有相同的概率分布.

i的分布与μi一致, 都是[1, 1因此μq ]上的均匀随机分布.

(2)

,k ,",k 是由Joint-RSS产生的, 因此r*=k G(1-i-t)满足均匀分布, 而剩下的r*(t+1-i-2n)k12tiii是由ri*(1-i-t)和r*所确定的. 因此ri*(t+1-i-2n)与ri*(1-i-t)具有相同的概率分布.

i也满足在[1, 1 i也(3) 如上所证, sq ]上的均匀随机分布, 并且与si=di′(ki+r)+μi r一致, s

满足该等式.

结合引理1, 可证明门限签名方案SM2-Sign-Thresh具有不可伪造性. 证毕.

图1 门限签名方案的模拟协议

Figure 1 Simulation protocol for the threshold signature scheme

进一步, 根据引理2和引理3, 可以得到:

定理1 门限签名方案SM2-Sign-Thresh是安全的, 即具有不可伪造性和健壮性: 当n.2t+1时, 可抵抗对t个成员的窃听攻击; 当n.3t+1时, 则可抵抗对t个成员的中止攻击.

定理2 当n.t+1(n.2t+1)时, SM2门限密钥交换协议SM2-Exch-Thresh和门限解密算法

SM2-Decry-Thresh可以容忍对t个成员的窃听(中止)攻击.

证明: 首先证明健壮性. 对于SM2-Exch-Thresh和SM2-Decry-Thresh, 根据PM-SS可知, 1t+个参与者联合即可完成密钥交换和解密.

164 Journal of Cryptologic Research 密码学报 Vol.1, No.2, Apr. 2014

其次证明机密性, 即协议交互过程中没有额外有效的信息泄露. 对于SM2-Exch-Thresh, 通过参与者Ui的Vi=tB,i(PA+xARA)=(dB,i+xBrB,i)(PA+xARA), 无法得到tB,i的信息, 这是一个椭圆曲线上的离散对数问题. 另外, 类似的, 门限密钥交换过程也只广播了diC1信息. 又由于Joint-RSS本身的安全性, 所以破坏少于t+1个参与者不能获得关于私钥的任何信息. 因此, SM2-Exch-Thresh和

SM2-Decry-Thresh是安全的. 证毕. 6.2 效率

6.2.1 通信量

本文以协议中传输的数据量来估算门限密码算法的通信复杂度. 由于门限密钥交换协议和门限解密算法的门限密码部分较为简单, 在这里只讨论门限签名方案的通信量. 在以下说明中, x表示x的比特位数.

对于门限签名方案, 在密钥产生阶段, 当不存在可信中心时, 每个参与者首先执行Joint-RSS, 此时需要向其他参与者发送q比特信息得到子私钥, 并广播自己的子公钥2p比特(包括x坐标和y坐标, 可通过点压缩至p比特). 此后, 参与者需分享(1+d), 需执行两次Joint-RSS和广播γi. 因此在私钥产生阶段共需广播2p+q比特以及秘密传送3(n 1)q比特. 当可信中心(trusted dealer, TD)存在时, 可信中心将私钥d和(1+d)分享给参与者(若只做签名, 私钥d不必分享, 只需分享享(1+d)即可), 再广播公钥即可. 如表1所示, 需要注意的是, 可信中心存在时, 参与者在密钥产生阶段并不需要通信, 表中的数据是可信中心的通信量. 在SM2椭圆曲线推荐参数中, p和q的比特长度都是256比特, 因此p=q.

在签名阶段, 假设有T(T>2t)个参与者参与签名, 则每个参与者需要执行t阶Joint-RSS和2t阶

1

1

1

Joint-ZSS, 以及广播2p比特的kiG和q比特的si. 因此共需要秘密传送2(T 1)q比特, 广播2p+q比特.

表1 SM2门限签名方案的通信量

Table 1 The communication traffic for the SM2 threshold signature scheme 过程

密钥产生(存在TD)

签名生成

广播(bit) 秘密传送(bit)

2(n 1)q 2(T 1)q

2p

2p+q

在ECDSA中, 签名s=k 1(Hash(m)+rd)modq, r=kGmodq. 因此, 在使用相同的基础知识来设计基于ECDSA的门限签名方案时, 签名生成s时需要执行Inv-SS分享k 1再执行Mul-SS分享s. 而在

SM2中, 是对私钥d求逆, 因此, 我们基于SM2门限签名方案的签名通信量更小, 只需在密钥产生时执行Inv-SS, 接下来的每次签名都只执行Mul-SS. 此外, 在可信中心存在的情况下, SM2的门限签名方案的优势就更加明显, 因为只需要可以由可信中心执行一次求(1+d)的过程即可, 参与者不需要执行Inv-SS.

1

6.2.2 计算量

本文以椭圆曲线EFp上点加、点乘以及Zq上逆元运算的计算量来估计门限签名方案的计算复

()

尚 铭 等: SM2椭圆曲线门限密码算法 165

杂度. 相比上述运算, 签名时其他运算的计算量都很小.

不存在可信中心时, 在密钥产生和签名生成阶段各执行了一次PM-SS, 并且在密钥产生时执行了逆元运算; 存在可信中心时, 可信中心只需计算执行逆元运算计算(1+d)和执行一次点乘计算公钥.

点乘运算是由若干步点加运算组成的, 对于整数k∈Zq和基点G, 点乘运算kG可以转换为2(q 1)次点加运算. 在PM-SS过程中, 每个参与者需要执行t+2次点乘和t次点加运算, 约为2(t+2)(q 1)次点加.

1

门限签名方案的计算量如表2所示. 需要注意的是, 可信中心存在时, 参与者在密钥产生阶段并不需要计算, 表中的数据是可信中心的计算量.

表2 SM2门限签名算法的计算量

Table 2 The computation quantity for the SM2 threshold signature scheme 过程

密钥产生(存在TD)

签名生成

E(FP)上的点加(次)

Zq的逆元(次)

1 0

2(q 1) 2(t+2)(q 1)

7 结束语

本文提出了SM2门限密码算法, 包括门限签名算法、门限密钥交换协议和门限解密算法, 并对它们的安全性和效率进行了分析. 文章对可信中心是否存在的情况分别进行了讨论, 结果表明: 在不存在可信中心的情况下我们的方案具有较小的通信复杂度, 当可信中心存在时该优势更加明显. 安全分析表明: 在n>2t条件下, 任何2t+1个参与者集合可以生成一个有效的数字签名; 我们的门限签名方案可以抵抗n的窃听攻击和n3中止攻击. 接下来对于恶意敌手和自适应敌手下安全门限方案的研究是下一步工作的重点. References

[1] Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612–613.

[2] Desmedt Y, Frankel Y. Threshold cryptosystems[C]. In: Advances in Cryptology—CRYPTO '89 Proceedings. Springer

New York, 1990: 307–315.

[3] Desmedt Y, Frankel Y. Shared generation of authenticators and signatures[C]. In: Advances in Cryptology—CRYPTO '91.

Springer Berlin Heidelberg, 1992: 457–469.

[4] Wang C T, Lin C H, Chang C C. Threshold signature schemes with traceable signers in group communications[J].

Computer Communications, 1998, 21(8): 771–776.

[5] Harn L. Group-oriented (t, n) threshold digital signature scheme and digital multisignature[J]. IEE Proceedings-Computers

and Digital Techniques, 1994, 141(5): 307–313.

[6] Gennaro R, Jarecki S, Krawczyk H, et al. Robust threshold DSS signatures[C]. In: Advances in

Cryptology—EUROCRYPT’96. Springer Berlin Heidelberg, 1996: 354–371.

[7] Miyazaki K, Takaragi K. A threshold digital signature scheme for a smart card based system[J]. IEICE Transactions on

Fundamentals of Electronics, Communications and Computer Sciences, 2001, 84(1): 205–213.

[8] Herlihy M P, Tygar J D. How to make replicated data secure[C]. In: Advances in Cryptology—CRYPTO '87. Springer

Berlin Heidelberg, 1988: 379–391.

[9] Reiter M K, Franklin M K, Lacy J B, et al. The key management service[C]. In: Proceedings of the 3rd ACM Conference

on Computer and Communications Security. ACM, 1996: 38–47.

[10] 国家密码管理局. SM2椭圆曲线公钥密码算[EB/OL].(2010:12). /UpFile/2010122214822692.pdf [11] Canetti R, Gennaro R, Jarecki S, et al. Adaptive security for threshold cryptosystems[C]. In: Advances in

Cryptology—CRYPTO '99. Springer Berlin Heidelberg, 1999: 98–116.

[12] Goldwasser S, Micali S, Rivest R L. A digital signature scheme secure against adaptive chosen-message attacks[J]. SIAM

Journal on Computing, 1988, 17(2): 281–308.

166 Journal of Cryptologic Research 密码学报 Vol.1, No.2, Apr. 2014

作者信息

尚铭(1965–), 博士, 高级工程师. 主要研究领域为网络与信息安全.

E-mail: shm@

马原(1988–), 博士. 主要研究领域为网络与信息安全.

E-mail: yma@

林璟锵(1978–), 博士, 副研究员. 主要研究领域为网络与信息安全.

E-mail: linjq@

荆继武(1964–), 博士, 研究员, 中国密码学会理事. 主要研究领域为网络与信息安全. E-mail: jing@

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

中国密码学会2014年1–8月学术会议一览

一、2014年国产密码算法电子认证国际互操作技术研讨会

主办单位: 中国密码学会电子认证专业委员会 承办单位: 国民技术股份有限公司 会议时间: 2014年5月20日 会议地点: 深圳市五洲宾馆

会议网址: /TCCA

二、中国密码学会2014年量子密码专委会学术会议

主办单位: 中国密码学会量子密码专业委员会 承办单位: 清华信息科学技术国家实验室（筹）

清华大学物理系和赤峰学院物理与电子信息工程学院

会议时间: 2014年7月19日–20日 会议地点: 赤峰学院国际学术报告厅

会议网址: /event/211326/

三、中国密码学会2014年会

主办单位: 中国密码学会 承办单位: 信息工程大学

会议时间: 2014年8月27日–30日 会议地点: 河南郑州

会议网址: /

本文来源：https://www.bwwdw.com/article/2jxe.html