0 引言

在当今高度信息化的时代，数字签名得到了广泛的应用.然而标准数字签名^[1-2]在某些情况下会给签名持有者造成一定约束，不能对已签名的数据进行合理的操作.Steinfeld等^[3]于2001年最早提出了可截取签名(content extraction signature, CES)的概念，并给出了具体方案.与标准数字签名方案不同，可截取签名体制允许签名的持有者在不与原始签名者进行交互的情况下，根据自身需要，提取原消息中的部分内容，并为这部分内容计算一个可公开验证的签名，验证时使用的是原始签名者的公钥.可截取签名在某些领域有一定的应用场景.刘军龙等^[4]于2006年提出了基于身份的可截取签名方案，但方案中采用双线性对运算，效率有待提升.Yin等^[5]于2010年提出了一种不含可信第三方的基于属性的可截取签名方案，与文献[4]相比，减少点乘和哈希运算的次数，提高计算效率.曹素珍等^[6]于2012年提出了一种不含双线性对的可截取签名方案，用指数运算代替对运算，从而提高方案效率，之后又于2013年提出了一种基于离散对数问题的可截取签名方案^[7]，进一步减少了指数运算的次数.刘庆华等^[8]于2013年提出了一种高效的无证书内容可截取签名方案^[9]，用椭圆曲线上的标量点乘运算取代双线性对，进一步提高效率.

截止到目前，可截取签名方案大部分是基于双线性对运算或者大数因子分解问题，只有少部分是基于离散对数问题，并且还没有人将国密算法SM2与可截取签名相结合.为此，本文将可截取签名与国密算法SM2相结合，提出了一种基于椭圆曲线离散对数问题的无证书可截取签名方案，避免传统公钥密码系统的公钥验证和基于身份的密码系统^[10]的私钥托管问题.与文献[8]相比，计算效率有所提升，并且在随机预言模型中是可证安全的，在适应性选择消息攻击下存在不可伪造性.

1 可截取签名定义

在可截取签名方案中，将原消息M看作一个集合型数据，由n个子消息组成，M可以表示为：M=(M₁, M₂, M₃, M₄, M₅)，M_i表示M中第i个子消息，截取后得到消息集合为M′.截取子集CI(M′)用来表示截取消息M′中所有子消息编号的集合.M′中仍然有n个子消息，其中被截掉的子消息用标记?表示，保留下来的消息与原消息M中对应编号位置的子消息相同.为了使原始签名者对原消息M具有一定控制权，防止截取者恶意截取，引入了内容截取访问结构(content extraction access structure，CEAS)，CEAS中规定了截取者必须截取的子消息段的编号，并且满足CEAS⊂CI(M′).例如：M=(M₁, M₂, M₃, M₄, M₅)，CEAS={2, 4}，若CI(M′)={1, 2, 4, 5}，则M′={M₁, M₂, ?, M₄, M₅}，满足CEAS⊂CI(M′)，表示截取方式合法；若CI(M′)={1, 2, 5}，则M′={M₁, M₂, ?, ?, M₅}，CEAS⊈CI(M′)，截取方式不合法.

可截取签名需要满足一定的安全属性，具体为：

1) 不可伪造性.攻击者可以访问一个CES签名预言机，如果消息M′满足：a)不是一个合法的访问CES签名预言机的消息a的子消息；b)是一个合法的访问CES签名预言机的消息M的子消息，但是不符合内容截取访问结构.在这种情况下，攻击者想要产生有关M′的一个合法的CES签名几乎是不可能的.

2) 隐私性.对于未被截取的子消息，攻击者若想从截取消息中获取未被截取消息的相关内容是不可行的.

2 基于SM2的无证书可截取签名方案 2.1 SM2数字签名简介

SM2的数字签名算法适用于商用密码应用中的数字签名和验证，在GM/T0003中规定了SM2椭圆曲线公钥密码算法的数字签名算法.具体的算法流程本节不再阐述，只简要介绍一下本文提出的可截取签名方案需要用到的参数表示^[11].

(d_A, p_A)：原始签名者Alice(简称A)的公私钥对，d_A是私钥，p_A是公钥，其中p_A=[d_A]G；

M：原始消息；

M′：待验证的消息；

e：密码杂凑函数作用于消息M的输出值；

e′：密码杂凑函数作用于消息M′的输出值；

G：椭圆曲线的一个基点，其阶为素数；

H()：密码杂凑函数，一般消息摘要长度为256 bit；

mod N：模N运算，例如，11 mod 2=1；

N：基点G的阶;

x‖y：x与y的拼接，其中x、y可以是比特串或字节串；

Z_A：用户A的可辨别标识、部分椭圆曲线系统参数和用户A公钥的杂凑值；

(r, s)：发送的签名；

(r′, s′)：接收到的签名；

(x, y)：椭圆曲线上的点.

2.2 具体方案

本文提出的基于椭圆曲线的无证书可截取签名方案，主要由7个算法构成.

1) 系统建立 输入安全参数k，密钥生成中心(key generation center，KGC)选择k bit的素数q，得到{F_q, E(F_q), G}.KGC选择x∈Z_N^*作为系统主密钥，计算系统主公钥P_pub=xG.KGC选择哈希函数H₁:{0, 1}^*→Z_N^*，H₂:{0, 1}^*→{0, 1}^k.KGC保存主密钥x，公开系统参数params={ F_q, E(F_q), G, P_pub, H₁, H₂}.

2) 设置秘密值 用户A随机选择x_A∈Z_N^*为秘密值，计算P_A1=x_AG，将P_A1传送给KGC用作部分密钥生成.

3) 部分密钥生成 输入系统主密钥x、P_A1以及系统参数，KGC随机选择r_A∈Z_N^*，计算R_A=r_AG，h_A=H₁(ID_A, R_A, P_A1)，然后得到部分私钥s_A=r_A+h_Ax(mod N)，将(s_A, R_A)通过安全信道发送给用户A.

4) 完整密钥生成 用户A收到(s_A, R_A)后，验证s_AG=R_A+h_AP_pub(mod N)是否成立，若成立，计算P_A2=s_AG，用户A将P_A1和P_A2合并在一起作为用户公钥PK_A=(P_A1, P_A2)，用户将自己的秘密值x_A与s_A合并作为用户的私钥SK_A=(x_A, s_A).

5) 签名算法 输入原消息M，原始签名者A给出相应的截取规则CEAS，按以下步骤执行签名过程.

A1对于必选子消息i∈CEAS，计算h_CEAS=H₂((m[i]‖i)_i∈CEAS, CEAS)；对于非必选子消息i∈Γ\CEAS，计算h_i=H₂(m[i], i, CEAS)；

A2计算M= ID_A‖PK_A‖h_CEAS‖ (h_i)_{$\in$i∈Γ\CEAS}，计算e=H₂(M‖Z_A)；

A3随机选取k∈[1, N-1]，计算椭圆曲线点(x₁, y₁)=[k]G；

A4计算r=(e+x₁)mod N，若r=0或r+k=N，则返回步骤A3；

A5令d_A=(x_A+s_A) mod (N-2)；

A6签名得到σ=(1+ d_A) ^-1(k-rd_A) mod N，若σ=0，则返回步骤A3；

A7返回全局签名σ_Full=(CEAS, σ, r).

6) 截取算法截取者B收到全局签名σ′_Full=(CEAS′, σ′, r′)后，根据SM2标准验签过程对接收到的全局签名进行验证，若验证通过，则进行后续的截取过程，否则验证失败.截取过程具体如下.

B1根据原消息M和截取规则CEAS′，获得截取子集CI(M′)，令X′=CI(M′)；

B2对于i∈Γ\X′，截取者B计算h_i=H₂(m[i], CEAS′)；

B3返回截取签名σ_Ext=(CEAS′, σ′, r′, (h_i) _{i∈Γ\CI(M′)}).

7) 验证算法  验证者C收到截取消息M′的签名σ′_Ext=(CEAS″, σ″, r″, (h_i)_{i∈Γ\CI(M′)})后，首先验证CEAS″⊂CI(M′)是否成立，若成立，则继续下一步的操作；否则，终止算法.

C1检验r″∈[1, N-1]是否成立，若成立，则进行下一步操作；否则，验证不通过；

C2检验σ″∈[1, N-1]是否成立，若成立，则进行下一步操作；否则，验证不通过；

C3对于i∈CEAS″，计算h′_CEAS=H₂((m′[i]‖i)_i∈CEAS″, CEAS″)；对于i∈X′\CEAS″，计算h′_i=H₂(m′[i], CEAS″)，结合所收到的截取签名的内容，可以得到对于i∈Γ\CEAS″的子消息的哈希值h′_i；

C4根据CI(M′)和M′恢复M ″，计算e″=H₂(M ″‖Z_A)；

C5计算t″=r″+σ″，若t″≠0，继续进行下一步操作；否则，验证不通过；

C6计算椭圆曲线点(x″₁, y″₁)=[σ″]G+[t″](P_A1+P_A2)；

C7 R=e″+x″₁ (mod N)，判断R=r″是否成立，若成立，则验证通过，签名有效；否则，验证不通过.

3 方案分析 3.1 正确性分析

对于一个诚实的截取者，可以通过以下推导过程来证明该方案的正确性.

首先验证部分私钥的正确性.s_AG=(r_A+h_Ax)G=R_A+h_A[x]G=R_A+h_AP_pub，可以看出，该方案满足部分私钥验证方程.

接下来验证签名的正确性.验证者在收到截取签名后，按照方案中的验证算法对接收到的截取签名的正确性进行验证.验证方程为R=e″+x″₁(mod N)=H₂(M ″‖Z_A)+x″₁.

对于一个诚实的截取者来说，由于在截取过程中并没有对原消息M中的任何一个子消息进行改动，因此验签过程中得到h′_CEAS、(h′_i)_i∈Γ\CEAS与签名过程中计算的哈希值相等，故M″=M，且e″=e.

(x″₁, y″₁)=[σ″]G+[t″](P_A1+P_A2)=[σ″]G+[t″](x_A+s_A)G=[σ″]G+(r″+σ″)(x_A+s_A)G= (1+(x_A+s_A))[σ″]G+r″(x_A+s_A)G=(k-r″(x_A+s_A))G+r″(x_A+s_A)G=[k]G=(x₁, y₁).

因此可以证明e″=e，x″₁=x₁，即R=r″.验证方程通过，该方案是正确的.

对于恶意的截取者，可以通过恶意的截取方式来实施攻击，主要有4种情况.

1) 截取者在对原消息进行截取时没有遵守相应的截取规则CEAS.之后验证者在验证截取签名时，CEAS的改动必然会导致必选子消息的哈希值h′_CEAS发生变化，与原来的h_CEAS不同，同时由于h_CEAS参与签名验证过程，因此截取者如果不遵守相应的截取规则，则签名无法通过验证.

2)截取者按照截取规则对原消息进行截取得到M′，但把M′中的一些子消息m′[i]替换为m″[i]，得到一个伪造的截取消息M″.在之后的验签过程中，需要对一些子消息进行哈希运算，即对于i∈CEAS，存在

H₂((m[i]‖i)_i∈CEAS, CEAS)≠H₂((m″[i]‖i) _i∈CEAS, CEAS)，

或者是对于i∈Γ\CEAS，

H₂(m[i], CEAS)≠H₂(m″[i], CEAS).

由此可知被篡改的子消息m″[i]会使h′_CEAS或h′_i会发生变化，从而M″≠M，使得e″≠e，验签方程R≠r″，因此不能通过验证.

3) 截取者按照截取规则对原消息进行截取得到M′，并在截取消息M′后添加j条子消息得到M″，会造成验签过程无法通过，证明过程类似于2)中的分析，不再过多赘述.

4) 恶意的截取者试图伪装成原始签名者，并想要伪造一个原始签名信息.在可截取签名中，验证者在对签名进行验证时，使用的是原始签名者的公钥，对恶意的截取者来说，只知道原始签名者的公钥，并无法获知原始签名者的私钥(需要解决椭圆曲线离散对数问题).因此，恶意的截取者无法伪造出有效的原始签名对.

3.2 安全性证明

本文所提出的方案在随机预言模型下是可证安全的^[12]，在适应性消息选择攻击下存在不可伪造性，证明过程如下.

定理1  在随机预言模型下，如果存在一个敌手Attacker，之后简称AT，在多项式时间内以不可忽略的概率ε成功攻破本文的方案，那么存在挑战者C同样能够以不可忽略的概率$\frac{1}{{{q_{{H_1}}}}}{\left( {1 - \frac{1}{{{q_{{H_1}}}}}} \right)^{{q_s}}} \cdot \varepsilon $在多项式时间算法内解决椭圆曲线离散对数问题.

证明  在多项式时间内，假设敌手AT最多能进行q_H1次H₁询问，q_s次部分私钥询问，挑战者C随机选取挑战目标身份j，j∈[1, q_H1].如果敌手AT能成功攻破本方案，那么挑战者C可以利用AT作为子程序解决椭圆曲线离散对数问题.

以下是敌手AT与挑战者C之间的交互过程.

1) 系统初始化：挑战者C首先选择安全参数k，产生主密钥x和系统参数params={F_q, E(F_q), G, P_pub, H₁, H₂}，其中P_pub=xG，然后C保存主密钥x，并将params发送给AT.

2) 询问阶段：假设AT一共进行q_H1次H₁询问和q_s次部分私钥询问，设挑战目标身份为ID_j，j∈[1, q_H1].

a) H₁询问 C维护一个初值为空、结构为{ID_i, R_i, s_i, h_1i}的列表L_H1，当AT提交关于H₁(ID_i, R_i, P_i1)的询问请求时，C首先查询L_H1列表，如果L_H1中存在对应的{ID_i, R_i, s_i, h_1i}，则返回h_1i给AT；如果没有对应项，且满足i≠j，则C随机选取h_1i∈Z_N^*，s_i∈Z_N^*，计算R_i=s_iG-h_1iP_pub，把h_1i返回给AT，并将{ID_i, R_i, s_i, h_1i}添加到L_H1中；若不存在对应项，且i=j，设置s_i=⊥，C随机选取h_1i∈Z_N^*，计算R_i=aG-h_1iP_pub，把h_1i返回给AT，并将{ID_i, R_i, s_i, h_1i}添加到L_H1中.

b) 部分私钥询问 C维护一个结构为{ID_i, R_i, P_i2, s_i}部分私钥列表L_s，当收到来自AT的部分私钥询问，若i=j，则C输出⊥，并停止询问过程.否则若i≠j，C查询L_s，如果表中含有{ID_i, R_i, P_i2, s_i}，则返回{R_i, s_i}给AT.否则，C进行H₁询问，得到对应元组{ID_i, R_i, s_i, h_1i}后，将{R_i, s_i}返回给AT.

c) 公钥询问 C创建一个结构为{ID_i, P_i1, P_i2}的公钥列表L_PK.AT提交关于用户ID_i的公钥询问.

首先C查找列表L_PK，若列表中含有{ID_i, P_i1, P_i2}，则C返回PK_i=(P_i1, P_i2)给AT.否则，i)若部分私钥列表中含有{ID_i, R_i, P_i2, s_i}，则C随机选取x_i∈Z_N^*，计算P_i1=x_iG，添加{ID_i, x_i}到秘密值列表中，返回PK_i=(P_i1, P_i2)给AT；ii)若不含有相应项，则C提交关于ID_i的部分私钥询问获得{R_i, s_i}，然后C随机选取x_i∈Z_N^*，计算P_i1=x_iG，添加{ID_i, x_i}到秘密值列表中，最后C返回PK_i= (P_i1, P_i2)给AT.

d) 公钥替换询问 当AT提交关于(ID_i, PK′_i)的公钥替换询问时，如果公钥列表L_PK中含有PK′_i，C定义PK_i= PK′_i；否则，C提交关于ID_i的秘密值询问，然后C定义PK_i=PK′_i.

e) 秘密值询问 C维护一个秘密值列表{ID_i, x_i}，当AT提交关于ID_i的秘密值询问时，如果列表中有对应项，则返回x_i给AT；否则，C随机选取x_i, s_i∈Z_N^*，计算P_i1=x_iG, P_i2=s_iG，添加{ID_i, x_i}到秘密值列表，添加{ID_i, P_i1, P_i2}到公钥列表，然后C返回x_i.

f) 签名询问 当AT对消息(M_i, ID_i)进行签名询问时，C随机选取σ, r∈Z_N^*，生成身份ID_i的签名(σ, r)，计算t=σ+r，(x₁, y₁)=[σ]G+[t](P_i1+P_i2).

3) 输出阶段：游戏最后，AT停止询问阶段，输出一个有效的签名对(ID^*, M^*, s=(σ, r))，若ID^*≠ID_j，则挑战者C挑战失败并终止算法，否则伪造成功，挑战者C可以利用Forking引理^[13]，通过选择不同的H₂可以再另外生成两个有效的签名对(ID^*, M^*, s=(σ₂, r₂))，(ID^*, M^*, s=(σ₃, r₃)).然后有(x′₁, y′₁)=[σ′]G+[t](P_A1+P_A2)=(x₁, y₁)=[k]G，因为P_A1=x_AG，P_A2=s_AG，t=r′+σ′，即

[σ′₁]G+[r′₁+σ′₁](x_A+s_A)G=[k]G,

[σ′₂]G+[r′₂+σ′₂](x_A+s_A)G=[k]G,

[σ′₃]G+[r′₃+σ′₃](x_A+s_A)G=[k]G，

在这3个等式中，有3个未知数x_A，s_A，k，联立以上3个等式，就可以求解出来这3个未知数，进而解决椭圆曲线离散对数问题.接下来我们对挑战者C获胜的概率进行分析.之前我们假设敌手AT进行了q_s次部分私钥提取询问，且j∈[1, q_H1]，则AT不曾对目标用户ID进行部分私钥询问的概率为${\left( {1 - \frac{1}{{{q_{{H_1}}}}}} \right)^{{q_s}}}$，并且AT在多项式时间内以不可忽略的概率ε攻破本文方案，AT不曾对目标用户进行关于消息M的签名询问的概率为$\frac{1}{{{q_{{H_1}}}}}$.则挑战者C成功的概率为$\frac{1}{{{q_{{H_1}}}}}{\left( {1 - \frac{1}{{{q_{{H_1}}}}}} \right)^{{q_s}}} \cdot \varepsilon $.通过上述公式可知，如果敌手AT成功伪造有效签名对(σ, r)的概率ε是不可忽略的，且q_H1、q_s均为常数，则挑战者C同样能够以不可忽略的优势解决椭圆曲线离散对数问题.

定理2  如果哈希函数满足单向性(one-way)，也称为抗原像攻击性，即对于给定的一个哈希输出值，倒推出输入数据是很难的，计算上不可行.那么本文中基于SM2的无证书可截取签名方案满足隐私性.

证明   根据截取签名σ_Ext=(CEAS, σ, r, (h_i)_{i∈Γ\CI(M′)})，可知截取签名σ_Ext包括了所有未截取消息的哈希值，但由于哈希函数具有单向性，故即使得到了所有未被截取消息的哈希值，也无法获知未被截取消息的具体内容.另一方面，截取签名不包含有关截取消息的任何内容，也就是说截取消息与未被截取的消息相独立，对于验证者来说，即使知道了所有的截取消息，也无法从中推出有关未被截取消息的相关内容.因此，本文提出的方案满足隐私性.

3.3 效率分析

本文提出的方案与文献[5-8]中的方案的进行效率比较.为了表示方便，par表示对运算，exp表示指数运算，sca表示基于椭圆曲线密码编码(elliptic curves cryptography, ECC)的标量乘法运算，has表示哈希函数运算.n表示子消息的数目，m表示截取子集中子消息的数目，m_CEAS表示包含在内容截取访问结构CEAS中的子消息的数目.方案的效率比较如表 1所示.

由于进行一次双线性对运算所需的时间大约为椭圆曲线上标量乘法运算的10倍，椭圆曲线上的加法运算也比较高效，点乘运算可以用硬件实验加速^[14].因此与文献[5]的方案相比，本方案不采用双线性对运算，极大提高了方案效率.此外，一次指数运算的时间同样大于椭圆曲线上的标量乘法运算，因此本方案不采用指数运算，进一步提升效率.与文献[8]的方案相比，本方案采用统一计算哈希值的思想，减少签名验签过程中哈希运算的次数，在一定程度上改进方案效率.综上所述，本方案与文献[5-8]中的方案相比，在计算效率上有着明显优势.

4 总结

本文结合国密算法SM2，提出一种新的基于椭圆曲线离散对数问题的无证书可截取签名方案，在随机预言模型下证明该方案满足适应性选择消息下存在不可伪造性.与现有的可截取签名方案相比，本方案结合无证书签名体制，避免了传统公钥体制下的证书管理问题以及基于身份的公钥密码体制的私钥托管问题，从整体上提升了效率.此外，本方案在计算效率方面有优势，在数据隐私保护方面也有广泛的应用前景.