基于SM2与RSA签密的秘密共享方案*

韩宝杰，李子臣

（北京印刷学院 信息工程学院，北京 102600）

0 引言

对于某些秘密信息诸如国家机密档案、公司机密文件等重要信息，都需要将秘密拆分由多人掌管，并且需要多人同时在场才能恢复秘密信息，而秘密分享技术已经为此类问题提供了解决方案。秘密分享是现代密码学的一个重要研究方向，1979年由Shamir与Blakley提出[1]，主旨是将秘密信息分割成若干分享份，将其发送给相应参与者，仅当有足够的参与者在场时，才能重构出秘密数据。此后，很多学者在秘密分享方案的拓展中做了大量工作。Asmuth与Bloom[2]于1983年提出了一种新的基于中国剩余定理的秘密分享方案，相较于Shamir的分享方案更加高效，运算也更加简洁。随后出现了多秘密分享方案[3-6]，可以直接分割多个秘密，增加了秘密共享的容量与效率。

秘密分享技术在不断创新，拓展研究新的发展方向。2004年，文献[7]有将秘密分享与博弈论相结合，提出了理性的秘密分享方案，进而提供了一个新的研究热点[8-9]。Laih[10]等人提出了可以动态改变参与秘密重构人数的秘密共享方案，可以根据秘密的重要性更改恢复门限。

但是，传统的秘密分享方案存在着不可忽略的安全缺陷。例如，秘密分享份属于机密信息，为了保证安全，需要选取安全信道进行传输，如此增加了信息传输的成本。再如，存在恶意用户使用假的分享份参与秘密重构，致使合法用户获得错误的重构信息。对于上述问题，已有学者在秘密分享与验证技术的结合上进行研究，并取得了相关成果[11-14]。Rabin T[15]提出了一个可验证秘密分享方案，但该方案需要所有参与成员之间都具有秘密通信的能力，提高了通信成本。Harn L[16]提出强力可验证分享方案，保证了所有的分享份始终不变，防止参与者收集分享份重新定义秘密。

本文方案结合中国剩余定理（Chinese Remainder Theorem，CRT）与椭圆曲线问题构造可验证的秘密共享方案，其中中国剩余定理提供了拆分秘密的基础工具，而SM2与RSA签密体制用来构建签名与加密，为分发者与用户创建公私钥对，提供安全的信息传输方案，防止攻击者窃取分享文件。

该方案允许用户在安全环境差的情况下进行传输，节省了信息传输的成本，而且也保证只有合法用户能够获得分享份，且可以验证分享份的正确性与来源。

1 基础知识

1.1 (k,n)门限方案的引入

1.1.1 定 义

设P={P1,P2,…,Pn}是一个由n个参与人组成的集合，P的子集构成集合τ。如果τ恰好可以重构出参与者集合组成的秘密c，则τ可称为接入结构，P的授权子集就是τ中的元素。P的授权子集就是τ中的元素。

接入结构τ是单调性质的，即若B∈τ且B⊆C⊆P，则必有C∈τ。

(k,n)门限方案[17]是接入结构τ={A|A⊆P,|A|≥k}上的秘密共享方案，通用访问结构的秘密共享或广义秘密共享也是一般接入结构的秘密共享，具有很大的实用性。

1.1.2 秘密共享方案的数学模型

设秘密发放者为A，n个参与人记为集合P={P1,P2,…,Pn}，PT是授权子集，共享秘密记为c，秘密可分为集合C´={C1,C2,…,Cn}。

秘密分发算法：A通过某种算法计算出C´={C1,C2,…,Cn}，后由安全信道把秘密份额Ci分发给不同的参与人Pi。

秘密重构算法：授权子集PT中的参与人将自己有的秘密份Ci(Pi∈PT)组合，可经某种算法重构原始秘密。

在这种情况下，一个秘密共享方案称作一个(k,n)门限秘密共享方案。

1.2 中国剩余定理

中国剩余定理[18]是数论中最有用的工具之一。如果已知某个数是关于一些两两互素的数的同类，就可以重构这个数。它的这个特性为秘密分享方案提供了基础理论支持。

设m1,m2,…,mn是两两互素的正整数，有则方程组：

对模M有唯一解。

其中ui满足条件

本文采用Asmuth-Bloom提出的基于CRT的秘密分享方案作为秘密分发步骤的解决办法，计算上会比基于拉格朗日插值法的shamir分享方案速度更快，且也具备门限功能。

1.3 RSA加密算法

（1）随机选择两个不相等的质数p和q；

（2）计算p和n的乘积n（将n转换为二进制形式，也就是密钥的长度，实际应用中一般选择1 024位、2 048位）；

（3）计算出n的欧拉函数φ(n)；

（4）随机选择一个整数e，其中φ(n)＞e＞1，且e与φ(n)互质（实际应用中e一般选为65 537）；

（5）计算e对于φ(n)的模反元素d；

（6）将n和e封装成公钥，n和d封装成私钥。

假设发送方向接收方发送信息C，C未加密，称之为明文。发送方从接收方获得的公钥为(n,e)，加密公式为：

其中，C必须是整数，C必须比n小。

C、e、n已知，利用公式计算出C´即加密后的信息，称之为密文。

1.4 SM2数字签名方案

SM2算法是公钥密码，属于非对称算法体系，是椭圆曲线加密（Elliptic Curve Encryption，ECC）算法的一种[19]。

数字签名及流程如下：设待签名的文件为C，ZA为用户A的可辩别标识、部分椭圆曲线的系统参数以及用户A公钥的杂凑值，h是余因子。要获得秘密文件C的数字签名(r,s)，分发者A要实现以下运算：

（3）随机数发生器要产生随机数k∈[1,n-1]；

（4）需计算椭圆曲线上的点(x1,y1)=[k]G，将x1的数据类型转换为整数；

（5）计算r=(e+x1)modn，若r=0或r+k=0，则返回（3）；

（6）计算s=((1+dA)-1·(k-r·dA))modn)，若s=0，则返回（3）；

（7）将r、s的数据类型转换为字节串，消息C的签名为(r,s)。

1.5 SM2与RSA签密方案

在密码体制中，加密用来保证信息数据的机密性，数字签名是接收者用来确保消息的认证、完整性和不可否认性。如果分享者想同时获得这些性质，传统的方法是先对消息进行加密再进行签名运算，两者独立存在并分别被研究。这种方法在通信成本和计算量上是两者的代价之和，效率不高。

1997年，Zheng[20]提出了一种新的密码原语，能够同时实现以上的安全性质，这就是数字签密（Digital Signcryption）。与传统的“先签名后加密”相比，它的优点包括：（1）简化了需要同时达到保密和认证要求的密码协议的设计；（2）签密算法降低了通信成本和计算量，效率高；（3）签密可以并行计算一些复杂的操作；（4）签密方案的水平设计可以更安全。

所以，本方案采用SM2与RSA结合对分享份进行签密，提高了先签名后加密的效率。

2 可验证分享方案

2.1 方案描述

为了将原始秘密拆分并提供门限重构功能，选用基于中国剩余定理的门限分享方案，再使用SM2与RSA签密技术，保证分享份的安全性与正确性。接收者可以通过收集验证过的分享份进行秘密重构，获取重构信息。假设发送方是A，接收方是集合B={B1,B2,…,Bn}，原始秘密文件为C，任意(Bi)k个接收者拥有(Ci)k份分享，通过k个接收者中任意一位Bj解密和验证后，才能还原出秘密信息C。

本方案流程见图1和图2。

原始秘密C经拆分生成n份分享文件，分享者A再依次将文件进行签密生成签密文件，然后发送给接收者。实际应用中，为了保护数据可以将数据加密。可以利用秘密重构的方案，即将原始文件C分成n份C1,C2,…,Cn，满足任意k或多于k份Ci可以恢复出C，任意k-1或少于k-1份Ci信息不能准确计算出C。这种方式不但对分享份进行了加密，而且大大增加了原始文件的安全性。接收者们收集任意k份或多于k份的分享份，使用中国剩余定理可还原出初始文件。签密文件可以利用自己的私钥进行解签密，即可获得分享份的实际值。任意少于k份分享，将无法还原出正确的重构文件。

图1 秘密分享流程

图2 重构秘密流程

方案具体涉及6个阶段，分别为系统初始化阶段、分享份生成阶段、密钥生成阶段、秘密分发阶段、分享份的解密与验证以及分享份重构阶段。

2.2 方案步骤

2.2.1 签密算法初始化

设分发者A选取SM2签名所需的一条满足安全要求的椭圆曲线以及RSA加密所需的两个不同的大素数p和q。

2.2.2 分享份生成阶段

分发者A选取m1,m2,…,mn和Q，C为秘密。为增加秘密C的复杂性，要求Q≥C，m1,m2,…,mn严格递增，且满足：

分享份的生成：

随机选取整数t，满足计算Z=C+tQ，对Z与mi做模运算，即：

得到C1,C2,…,Cn，将Ci作为分享份。

2.2.3 密钥生成及签密方案

（1）SM2数字签名方案及密钥生成。设lk是安全参数，椭圆曲线的E(Fq)的方程的两个元素a,b∈Fq；E(Fq)上的基点G=(xG,yG)(G≠0)，其中xG和yG是Fq中的两个元素；G点的阶是n1。发送者的公钥pks=PA=[dA]G=(xG,yG)，私钥sks=dA。此外，公开参数params1=(a,b,n1,G,pks,h,ZA)。

（2）SA加密及密钥生成算法[21]。安全参数lk，定义大素数p、q，且n2=p·q，φ(n)=(p-1)(q-1)。随机选取e，其中1＜e＜φ(n)，且gcd(e,φ(n))=1，计算de=1mod(φ(n))，公 钥pks=(e,n)，私 钥sks=d。H1(·)、H2(·)是由密码杂凑函数Hv(·)的密码函数；l(·)表示参数的长度，单位是位；公开参数params2=(n2,e)。

2.2.4 签密算法

发送者A获得接收者Bi的公钥证书后，对分享份Ci进行以下计算（这里是n份分享中的任意一个Ci分享的签密过程）。

（1）生成随机数ki1∈[1,n1]，ki2∈[1,n2]；

（3）计算ai2=ci⊕H1(ki1,ZA)和w=H2(ki1,ci)；

（4）计算椭圆曲线上的点(x1,y1)=ki2G；

（5）计算ri=(x1+w)modn1和si=(1+dA)-1(ki2-rdA)modn1，若ri=0，ri+ki1=0或者si=0，则返回（1），输出密文Ci´=(ai1,ai2,ri,si)。

2.3 分享份的解密与重构

2.3.1 解签密算法

接收者C获得发送者A的公钥以及签密的文件Ci´=(ai1,ai2,ri,si)后需进行计算。

（1）根据接收者的私钥d计算：

（2）计算得出分享份Ci=H1(ki1,ZA)⊕ai2；

（3）计算w=H2(ki1,Ci)，并解出：

（4）计算(x1,y1)=[si]G+[v]PA

（5）验证Ri=(x1+w)modn1是否等于ri，若相等则可得到分享份Ci，若不相等则解签密失败。

2.3.2 秘密重构阶段

Bi位用户可以利用自己的分享份额，合作完成秘密重构。在进行重构计算前，要求各用户Bi使用分发者的公钥PA进行验证，验证通过才可参与重构计算，否则拒绝参与重构。由解签密算法计算出来的分享份Ci，Bj可通过收集到的任意k份分享，进行以下的重构操作。

可根据中国剩余定理由k份分享(Ci)k进行计算：

得到重组秘密C。

3 方案性能分析

3.1 方案的正确性

验证椭圆曲线上的点(x1,y1)是否与公私钥对应，需计算：

3.2 方案的机密性

在随机预言模型下，如果存在一个IND-HCCCA2敌方F能够在有限的时间t内以不可忽略的优势ε赢得游戏，则说明有区分者S，可以在t´＜t+(qs+2qu)te的时间内，可以有的优势攻破大整数分解问题，其中te是幂指数时间。证明：假如挑战者为S，攻击者是F´。

（1）初始阶段。挑战者生成分发者A的公私钥对(pks,sks)，生成参与者的公私钥对(pkr,skr)，s将pks和(pks,sks)发送给攻击者，并将skr保密。

（2）阶段1。F执行以下多项式有界次适应性询问和最先进hash查询，应答交付S。

H1询问：如果是第i次查询，随机选取h1i∈{0,1}C，把(h1i,k1i,ZAi)保存在H1列表中，返回h1i。

H2询问：随机选取h2i∈{0,1}k+C，把(h2i,k1i,Ci)保存在H2列表中，返回h2i。

签密查询：遍历H1和H2列表查询(h2i,k1i,Ci)和(h1i,k1i,ZAi)，使得和ri=(x1i+h2i)modn1等式满足，且满足(x1,y1)=[si]G+[t]PA和Ri=(x1+h2i)modn1=ri则C为签密的结果输出，否则输出错误。

挑战阶段：何时结束阶段1的询问进入挑战阶段取决于F。先由F给挑战者S发送个一样长的明文C0和C1，随后S任意选择一个数据γ∈(0,1)，计算mγ在分发者的私钥sks和接收者的公钥pks，进而计算签密密文c*=Signcrypt(sks,pkr,mg)，并将c*传给F。

阶段2：F可运行阶段1中的所有步骤，但不能执行接收者的私钥查询和解签密查询。

猜测阶段：F产生一个比特γ´，若γ´=γ，则F取得了胜利。

S需在H1的列表h1i,k1i,ZAi中找到它满足的这些计算：

且满足：

假如这些式子都满足，则证明F可以得到一个关于椭圆曲线的离散对数问题的实际解。

F的优势为：

其中Pr[γ´=γ]表示γ´=γ的概率。

在H1询问中有唯一一个(h1i,k1i,ZAi)与之相对，所以拒绝正确密文的概率为因此假如ε是不能略去，则ε´也是不能略去的。但是，这和大整数的难解问题是矛盾的。因此，在大整数问题的难解性下，以不可忽略的优势攻击此签密方案的IND-SC-CCA2敌手是不存在的。由此证明此签密方案是IND-SC-CCA2安全的。

3.3 方案的防伪造性

证明：假如有伪造者F´有不能略去的概率ε去攻击SM2与RSA签密方案的EUF-SC-CMA安全，会有挑战者F通过F´来攻击SM2的EUF-CMA安全性，伪造者F´与挑战者S有以下这些互动。

初始阶段。挑战者输出分发者的公私钥对(pks,sks)和接收者的公私钥对(pkr,skr)，S将pks和(pks,sks)传给F´，并把skr保密。

攻击阶段。F´能够运行签密查询，合理的应答则由S完成。查询中，F´生成一个接收者的公钥pkri及消息mi，S查询消息mi得到(ri,si)。随机选取k1i∈[1,n1-1]，计算：

返回ci=(c1i,c2i,r1,si)给S。

伪造阶段。F´提供接收的一个合法密文ci=(c1i,c2i,r1,si)返回给S，S进行如下操作得到一个合法的签名：

其中(ri,si)就是对ci签名的合法伪造，且满足：

可见，F´造出密文的优势ε不能略去，S伪造合法的签名也不能略去。但是，因为椭圆曲线的离散对数问题的难解条件，SM2签名是EUF-CMA安全的，所以伪造者F´是不存在的。此方案是EUFSC-CMA安全的。

在秘密的恢复阶段，攻击者想要使用伪造的分享份参与信息重构，以破坏重构信息的正确性，需要先通过重构信息前的验证，否则拒绝参与秘密重构。

3.4 方案的性能分析

从计算代价来看。对比先加密而后签名的方案，如采用SM2签名算法对消息摘要进行签名，用SM2公钥密码体制对加密明文的对称密钥进行加密，这里共用到了6个椭圆曲线上的离散点的运算：1个用来产生签名(x1,y1)=[k]G；3个用来加密a1=[k]G=(x1,y1)，s=[h]PB，[k]PB=(x2,y2)；2个用来解密s=[h]C1，[dB]C2=(x2,y2)。使用RSA加密签名，加密需要1次指数运算，解密需要1次指数运算，签名需要1次指数运算，验证需要1次指数运算。

设计的SM2与RSA签密方案，签密只需要使用1次椭圆曲线上的离散点运算和1次指数运算，解签密使用1次椭圆曲线上的离散点运算和1次指数运算，减少了通信量，提高了通信效率。

此外，该方案的安全性能安全分析已经证明，即具有较好的安全性。

4 结语

由于网络的飞速发展，网络安全问题倍受关注，越来越多的人选择将机密信息进行加密，随之而来的是密钥管理问题。一般将密钥简单存储在计算机中，若密钥文档失窃，则会直接威胁机密文档安全。对于机密等级更高的文档，查看与修改的权限也要加以限制，以保证其安全。

所提方案基于中国剩余定理，结合SM2与RSA签密算法，构造了一种分享份可验证的秘密分享方案，为密钥的安全存储与使用权限问题提供了解决方案，保证了分享份的安全来源，节省信道资源的同时保障了分享信息的安全，确保用户能够且只能获得属于自己的分享份。该方案能够有效减少攻击者窃取密钥所造成的损失，也能够防止攻击者通过伪造的分享份破坏导致信息重构。该平台可以被广泛应用于实际环境，如政府重要人员的档案信息密钥管理、公司财务档案密钥管理等，需要在加密的基础上进一步提升安全性能需求。因此，本平台有着广阔的应用场景。

本平台具有5种功能，分别为密钥生成、秘密分享、签名加密、解密验证与信息重构，可以对加密密钥数据在合理的时间内进行以上操作，并且解决了密钥权限与存储的问题，对构建更加安全的数据系统提供了新思路。