传统数字签名中通常假设攻击者无法获取秘密信息, 但在实际应用中并非如此. 边信道攻击^[1]可以利用设备运行时的电磁辐射特征, 分析设备的边信道信息如功耗、电磁辐射等推断出秘密参数和密钥. 故障注入攻击^[2]可以向某些嵌入式系统注入故障信号获取系统写保护的敏感参数信息. 冷启动攻击^[3]在系统或应用程序初始化和操作等过程中仍能获取系统内部的部分秘密信息. 真实数据传输过程^[4–6]中通常也没有真正意义上的完美安全的信道用来传递秘密参数或者密钥, 特别是野外硬件设施和通讯网络无法做到真正意义上的物理隔离, 比如铁路和公路的实时传感控制系统网络^[7,8], 因此容忍泄露的数字签名方案在实际中具有重要的应用价值.

短签名方案由Boneh等人^[9]首次提出, 方案签名长度是DSA (digital signature algorithm)签名的一半. 文献[10]基于Boneh等人^[9]短签名和Gap-Diffie-Hellman群提出了新型短签名方案, 缩减了签名运算次数, 并在随机预言模型下证明了方案的适应性选择密文攻击的安全性, 文献[11]构造一种可证安全短盲签名方案, 并证明了方案安全性, 方案适用于带宽受限的数据传输场景, 文献[12]提出了一种基于双线性映射的短代理签名, 并基于Diffie-Hellman问题和选择密文攻击证明了方案的安全性. 文献[13]结合公钥密码体制提出了一种基于证书的短签名方案, 并证明了方案的安全性和运行效率. 文献[14]针对代理签名重签名方案存在的效率缺陷, 结合短盲签名思想提出了短盲代理重签名方案的定义. 文献[15,16]基于短签名构造了高效的数据完整性签名验证方案. 文献[17–19]的方案通过结合短签名减少签名运算量, 提升了方案计算效率.

这些方案没有考虑实际中可能发生的敏感信息^[20](例如部分秘钥和秘密参数)可以泄露的情形, 在以前工作的基础上, 本文提出了一种安全的容忍泄露的内容关联短签名方案, 可以容忍部分秘密信息泄露并做到签名与待签名内容强关联, 提高签名方案的安全性.

1 相关基础与安全模型 1.1 数学基础

定义1. 双线性对映射. $ {G_1} $和$ G_{2} $是椭圆曲线上$ q $阶循环加法群, $ P $是$ {G_1} $的生成元, $ Q $是$ {G_2} $的生成元, $ G $是乘法循环群, 则有双线性映射$ e = {G_1} \times {G_2} \to G $满足以下性质.

(1)双线性性: 对于任意的$ a, b \in Z_q^* $, 有$ e(aP, bQ) = e{(P, Q)^{ab}} $.

(2)非退化性: $ e(P, Q) \ne 1 $.

(3)可计算性: 存在多项式算法计算$ e(P, Q) $的值.

定义2. 计算Diffie-Hellman问题(CDH). 椭圆曲线群$ G $, 其阶为$ q $, $ P $为生成元, 给定$ a, b \in Z_q^* $, $ aP $, $ bP $, 求$ abP $.

1.2 容忍泄露

定义3. 容忍泄露限. 在一个签名或者加密方案中, 秘密参数的总信息量是与安全参数$ k $正相关的一个常量$ {I_0} $, 如果存在一个阈值$ \lambda < {I_0} $, 在泄露信息量小于$ \lambda $的情况下方案仍然是安全的, 则称该方案为$ \lambda $-容忍泄露方案. 称$ \lambda $为容忍泄露限.

传统的构造容忍泄露的方案的思路是利用秘密分割方案把秘密参数分成很多碎片, 只要没有收集到足够多的碎片, 无法恢复出秘密信息和参数, 方案就是安全的. 本文我们采用内容关联多组秘钥的方式实现容忍泄露, 虽然增加了存储成本, 但计算量远小于传统基于门限分割的签名方案, 且具有较大的容忍泄露限. 只要$ n $组密钥中有1组密钥没有泄露, 泄露信息量小于$ 2(n - 1)k $, $ \lambda = 2(n - 1)k $则方案是安全的, 其中, $ k $为单个私钥长度.

1.3 敌手模型

容忍泄露模型假设攻击者可获得系统部分秘密信息, 如部分密钥等. 因此敌手模型中需要提供泄露询问.

敌手$ A $与挑战者$ C $之间的游戏如图1所示. 挑战者$ C $要借用敌手$ A $求解困难问题.

(1)系统建立: 挑战者$ C $运行系统生成算法, 生成系统的公开参数、秘密参数、私钥和公钥, 公布系统参数$ params $发送给敌手$ A $.

(2)询问阶段: 敌手$ A $对$ C $进行多次选择适应性询问.

1) $ {\mathrm{hash}} $询问: $ A $询问消息$ m $的哈希值, $ C $返回$ H(m) $.

2)泄露询问: $ A $询问$ m $的泄露信息, $ C $返回泄露的部分信息.

3)签名询问: $ A $询问消息$ m $的签名, $ C $生成的签名$ S $返回给敌手$ A $.

(3)伪造阶段: $ A $结束询问并输出伪造的签名$ ({m^*}, {S^*}) $, 游戏结束.

2 签名方案与安全性分析 2.1 签名方案

传统签名方案使用相同私钥对不同消息摘要进行签名, 很容易在电磁辐射频谱中出现稳定的辐射特征. 本文通过一个哈希函数实现待签名消息与签名密钥相关联, 这样只要待签名消息改变就会造成使用的签名密钥不一样, 极大地增强了签名方案的容忍泄露能力. 方案构造主要如下.

(1)系统参数建立. 选取安全参数$ k $, 秘钥组参数$ n $, 选择阶为素数$ q $的椭圆曲线上的循环加法群$ {G_1} $($ P $为$ {G_1} $的生成元), 循环乘法群$ G_{2} $, 非退化的双线性映射$ e = {G_1} \times {G_1} \to {G_2} $, 选择安全抗碰撞哈希函数$ {H_1}:{\{ 0, 1\} ^*} \to {\{ 0, 1\} ^{len}} $, $ {H_2}:{\{ 0, 1\} ^*} \to {G_1} $, 其中哈希函数$ {H_1}(m) $的哈希长度$ len > n $, $ {H_1}(m) = {b_1}{b_2}\cdots{b_{len}} $, $ {b_i} \in \{ 0, 1\} $, 公开系统参数$ params = \{ k, {G_1}, {G_2}, P, {H_1}, {H_2}\} $.

(2)密钥生成. 随机生成签名者的私钥组$ x = \left\{ \begin{gathered} {x_{10}}, {x_{20}}, \cdots, {x_{n0}} \\ {x_{11}}, {x_{21}}, \cdots, {x_{n1}} \\ \end{gathered} \right\} $, 计算签名者公钥组$ y = xP = \left\{ \begin{gathered} {y_{10}}, {y_{20}}, \cdots, {y_{n0}} \\ {y_{11}}, {y_{21}}, \cdots, {y_{n1}} \\ \end{gathered} \right\} $, 其中$ {x_{ij}} \in Z_q^* $, $ {y_{ij}} = {x_{ij}}P $, 公开公钥组.

(3)签名算法. 签名者对消息$ m \in {\{ 0, 1\} ^*} $进行签名, 签名过程如下.

1)计算$ {x_m} = \displaystyle\sum\limits_{i = 1}^n {{x_{i{b_i}}}} $, 其中$ {x_{i{b_i}}} $表示当$ {b_i} = 1 $时, 取$ {x_{i1}} $, 当$ {b_i} = 0 $时, 取$ {x_{i0}} $.

2)计算$ S = {x_m}{H_2}(m) $, $ S $为签名者对消息$ m $的签名, 将$ S $发送给签名验证者.

(4)验证算法. 对给定的消息和对应签名$ S $进行验证, 过程如下.

1)计算$ {H_1}(m) = {b_1}{b_2}\cdots{b_{len}} $, $ {y_m} =\displaystyle \sum\limits_{i = 1}^n {{y_{i{b_i}}}} $.

2)验证$ e(S, P) = e({H_2}(m), {y_m}) $.

正确性有以下恒等式保证, 当且仅当等式验证成立接受签名.

$ \begin{split} e(S, P) & = e({x_m}{H_2}(m), P) \\ & =e({H_2}(m), {x_m}P) \\ &= e\left({H_2}(m), \sum\limits_{i = 1}^n {{x_{i{b_i}}}P} \right) \\ &= e\left({H_2}(m), \sum\limits_{i = 1}^n {{y_{i{b_i}}}} \right) \\ &= e({H_2}(m), {y_m}) \end{split} $

2.2 签名方案安全性分析

定理1. 本文方案在CDH困难问题假设和容忍ROM模型下是可证安全的.

引理1. 若算法$ A $在概率多项式时间$ t $内, 以一个不可忽略的优势$ \varepsilon $, 成功伪造签名, 则存在概率多项式时间算法$ C $, 在时间$ {t{'}} < t + ({q_s}{t_s} + {q_d}{t_d} + 2{q_{{H_1}}}{t_{{H_1}}} + 2{q_{{H_2}}}{t_{{H_2}}}) $内以不可忽略的优势解决CDH问题:

$ \varepsilon ' \geqslant \left(\varepsilon - \frac{1}{{{2^k}}}\right) \cdot \left(1 - \frac{1}{{{q_d}}}\right) \cdot \left(1 - \frac{1}{{{q_S}}}\right) \cdot \frac{1}{{{q_{{H_1}}}}} \cdot \frac{1}{{{q_{{H_2}}}}} $

其中, 参数意义如下: $ {q_d} $: 泄露询问次数($ {q_d} < n $), $ {t_d} $: 询问一次所需时间, $ {q_{{H_1}}} $: 询问$ {H_1} $预言机次数, $ {t_{{H_1}}} $: 一次询问所需时间, $ {q_{{H_2}}} $: 询问$ {H_2} $预言机次数, $ {t_{{H_2}}} $: 一次询问所需时间, $ {q_s} $: 签名询问次数, $ {t_s} $: 一次询问所需时间.

证明: 给定一个CDH困难问题的实例: $ {G_1} $是椭圆曲线上$ q $阶循环加法群, $ P $是$ {G_1} $的生成元, 输入$ aP \in {G_1} $, $ bP \in {G_1} $, 输出$ abP $.

算法$ C $需要通过调用算法$ A $来求解CDH问题. 不妨设$ A $不会做两次相同的询问, 并在每轮游戏一开始初始化清空所有记录列表. $ C $选取安全参数$ k $, 秘钥组参数$ n $, 随机生成$ 2n{{ - }}2 $个秘密参数$ {x_{ij}} \in Z_q^* $ ($ 1 \leqslant i \leqslant n - 1 $)构建签名者的私钥组$ x = \left\{ \begin{gathered} {x_{10}}, {x_{20}}, \cdots, {x_{n0}} \\ {x_{11}}, {x_{21}}, \cdots, {x_{n1}} \\ \end{gathered} \right\} $, 这里需要说明的是$ i = n $时$ {x_{n0}} $, $ {x_{n1}} $位置本来应该是$ a $, 但因为$ a $未知, 因此填入“$ \bot $”表示空缺. 对应的公钥组为 $ y = \left\{ \begin{gathered} {y_{10}}, {y_{20}}, \cdots, aP \\ {y_{11}}, {y_{21}}, \cdots, aP \\ \end{gathered} \right\} $, 即当$ 1 \leqslant i \leqslant n - 1 $时$ {x_{ij}} \in Z_q^* $, $ {y_{ij}} = {x_{ij}}P $, 当$ i = n $时, $ {y_{n0}} = {y_{n1}} = aP $, 将实例的输入条件之一$ a{P_1} $嵌入在指标为$ i $的公钥之中, $ C $秘密保存$ x $但允许$ A $做$ {q_d} $次不包括$ {x_{n0}} $和$ {x_{n1}} $的私钥泄露询问. $ C $在系统初始化后将系统参数$ params = \{ k, n, {G_1}, {G_2}, q, P, y, {H_1}, {H_2}\} $发送给$ A $, 交互中会选择一个消息$ {m^*} $为目标消息在其哈希值中嵌入$ bP $.

(1) $ {H_1} $询问: $ C $维护表$ L{H_1} $, $ L{H_1} $由数组$ (m, w) $组成, $ A $向$ C $提交关于消息$ m $的$ {H_1} $询问时, 如果$ (m, w) $已经在$ L{H_1} $中, 直接返回$ w $给$ A $, 否则随机选择一个$ w = {b_1} {b_2}\cdots {b_{len}} $返回给$ A $同时将$ (m, w) $记录到$ L{H_1} $.

(2) $ {H_2} $询问: $ C $维护一个列表$ L{H_2} $, $ L{H_2} $由数组$ (m, u, h) $组成, 当$ A $向$ C $提交一个消息$ m $的$ {H_2} $询问时, 如果$ (m, u, h) $已经在$ L{H_2} $中, 直接返回$ h $给$ A $, 否则执行以下操作.

1)当$ m \ne {m^*} $时随机选择一个$ u \in Z_q^* $, $ h = uP $, 将$ h = uP $返回给$ A $同时将$ (m, u, h) $记录到$ L{H_2} $.

2)当$ m = {m^*} $时, 令$ h = bP $, 将$ h $返回给$ A $同时将$ (m, \bot , h) $记录到$ L{H_2} $.

(3)泄露询问: $ C $维护一个由数组$ (i, j, {x_{ij}}) $组成的列表$ {L_{sk}} $. 当$ A $向$ C $提出关于指标$ (i, j) $泄露部分私钥询问时, $ C $执行如下操作.

1)如果表$ {L_{sk}} $中已有指标$ (i, j) $相应记录$ (i, j, {x_{ij}}) $, 则返回$ {x_{ij}} $给$ A $.

2)如果$ i \ne n $, $ C $将$ {x_{ij}} $返回给$ A $的同时将$ (i, j, {x_{ij}}) $保存到表$ {L_{sk}} $中.

3)如果$ i = n $, $ C $返回“$ \bot $”给$ A $同时将$ (i, j, \bot ) $保存到表$ {L_{sk}} $中, 此事件记录为$ {E_1} $.

(4)签名询问: $ A $向$ C $输入待签名消息$ m $, $ C $从$ L{H_2} $中恢复$ (m, u, h) $, 然后进行以下操作.

1)如果$ m \ne {m^*} $, 则$ C $从列表$ L{H_1} $获得对应数组$ (m, w) $, 此时$ w = {b_1}{b_2}\cdots{b_{len}} $, $ {b_i} \in \{ 0, 1\} $, $ h = uP $计算$ {x_m} = \displaystyle\sum\limits_{i = 1}^{n - 1} {{x_{i{b_i}}}} $, $ S = {x_m}uP + uaP $, 则$ S $即为身份为$ ID $对消息$ {m_{ID}} $的签名. $ C $将$ S $返回给$ A $.

2)如果$ m = {m^*} $, $ C $终止模拟, 输出“$ \bot $” (记该事件为$ {E_2} $).

经过多项式有界次询问后, $ A $输出一个关于消息$ {m^*} $且满足最终验证等式使得$ Verify({m^*}, {S^*}) = 1 $的消息/签名对$ ({m^*}, {S^*}) $, 用$ {E_3} $表示该事件. $ C $从列表$ L{H_1} $中恢复$ ({m^*}, {w^*}) $和列表$ L{H_2} $中恢复数组$ ({m^*}, {u^*}, {h^*}) = ({m^*}, \bot , bP) $, 因为签名验证等式$ e({S^*}, P) = e({H_2}({m^*}), {y_{{m^*}}}) $成立, 则有以下等式成立:

$ \begin{split} & e({S^*}, P) = e({x_{{m^*}}}{H_2}(m), P) = e({H_2}({m^*}), {x_{{m^*}}}P) \\ & =e\left(bP, aP + \sum\limits_{i = 1}^{n - 1} {{x_{i{b_i}}}P} \right) = e\left(P, abP + \sum\limits_{i = 1}^{n - 1} {{x_{i{b_i}}}bP} \right) \end{split} $

$ C $计算$ {S^*} - \displaystyle\sum\limits_{i = 1}^{n - 1} {{x_{i{b_i}}}bP} = abP $, 输出$ {S^*} - \displaystyle\sum\limits_{i = 1}^{n - 1} {{x_{i{b_i}}}bP} $作为实例的解答. $ C $解决CDH问题的时间和优势.

(1) $ A $对消息都经过了$ {H_1} $询问和$ {H_2} $询问, 并且答案是有效的.

(2) $ {E_1} $, $ {E_2} $不发生时, 游戏才能正常完成.

(3) $ {E_1} $, $ {E_2} $都不发生时, $ {E_3} $发生, 则$ C $能解决CDH问题的一个实例. 则$ {E_1} $和$ {E_2} $都不发生的概率为:

$ \Pr (\neg {E_1} \wedge \neg {E_2}) = \left(1 - \frac{1}{{{q_d}}}\right)\left(1 - \frac{1}{{{q_S}}}\right) $

当$ A $没询问$ {H_2} $的概率为$ \dfrac{1}{{{2^k}}} $, 所以$ C $的优势下界为:

$ \varepsilon ' \geqslant \left(\varepsilon - \frac{1}{{{2^k}}}\right) \cdot \left(1 - \frac{1}{{{q_d}}}\right) \cdot \left(1 - \frac{1}{{{q_S}}}\right) \cdot \frac{1}{{{q_{{H_1}}}}} \cdot \frac{1}{{{q_{{H_2}}}}} $

运行时间的一个上界为:

$ {t{'}} < t + ({q_s}{t_s} + {q_d}{t_d} + 2{q_{{H_1}}}{t_{{H_1}}} + 2{q_{{H_2}}}{t_{{H_2}}}) $

其中, $ t' $为概率多项式时间, $ \varepsilon ' $为不可忽略的概率. 因此$ C $在$ t' $内以$ \varepsilon ' $成功地求解了CDH问题实例.

由引理1即证定理2, 说明本文方案可以抵抗适应性选择消息攻击下的存在性伪造攻击.

本文提出的短签名方案由于构造的抗泄露短签名方案的签名密钥是内容关联密钥, 通过提取签名消息的部分敏感信息生成与原始文件内容相关的密钥, 密钥与特定内容相关且具有单向性, 只能用于特定的加密和解密内容, 抵御了密钥破解的相关推断攻击.

另外方案将私钥表示为密钥组形式, 恶意中间人若要成功伪造消息签名, 必须达到泄露门限值, 否则无法完整恢复私钥进行签名, 由方案可知获取密钥组元素是困难的, 所以当部分私钥泄露时, 整体安全性不会受到影响, 签名私钥具有抗泄露性. 另外方案签名时对数据进行了哈希计算, 若传输检测数据受到篡改, 则会引起哈希值的变化, 导致签名验证失败, 因此方案可抵抗消息篡改攻击.

3 实现与效率比较 3.1 方案代码实现

本文在64位Windows 10操作系统的IntellijIDEA2020开发平台下, 为了方便比较, 使用了国密SM2和SM9算法相同的椭圆曲线和双线性对, 使用SM3做哈希运算, 使用Java语言(JDK版本为1.8)实现了本文短签名方案, 图2为方案实验结果, 方案主要代码如算法1.

算法1. 本文短签名方案主要代码

//循环计算50次

for (int i =0; i<50; i++){

　//(1)初始化参数

　sm9Curve sm9Curve = new sm9Curve();

　sm9 sm9 = new sm9(sm9Curve);

　sm3 sm3 = new sm3();

　Pairing bp = sm9.getCurve().sm9Pairing;

　byte[] hash1;

　int n = 10;

　Element g = sm9.getCurve().P2; //生成元g

　Map<String, Element[][]> keyMap = getKeys(bp, n, g);

　Element[][] priKeys = keyMap.get(“pri”); //生成私钥组

　Element[][] pulKeys = keyMap.get(“pul”); //生成公钥组

　stimeh = System.currentTimeMillis(); //计算执行时间

　//(2)签名运算

　hash1 = sm3.hash(m);

　boolean[] h1 = byteToBoolean(hash1);

　h2 = bp.getG1().newElementFromHash(hash1, 0, hash1.length);

　Map<String, Element> xyMap = getXY(bp, priKeys, pulKeys, n, h1, g);

　Element xm = xyMap.get(“xm”);

　Element ym = xyMap.get(“ym”);

　Element S = h2.mulZn(xm); //签名生成

　stimeh1 = System.currentTimeMillis(); //计算执行时间

　signtime += stimeh1 – stimeh; //计算签名时间

　//(3)签名验证

　left = bp.pairing(S, g); //计算等式左边

　right = bp.pairing(h2, ym); //计算等式右边

　stimeh2 = System.currentTimeMillis();

　verifytime += stimeh2 – stimeh1;//计算验证时间

}

long etime = System.currentTimeMillis(); // 计算执行时间

System.out.println(“待签名消息 m:” + m);

System.out.println(“等式左边 e(S, P)=\n” + left);

System.out.println(“等式右边 e(H2(m), ym)=\n” + right);

if (left.isEqual(right)) {

　System.out.println(“签名验证成功!”);

} else {

　System.out.println(“验证失败!”);

}

3.2 方案性能分析

本方案选取了经典短签名方案和近年来提出的短签名方案. 这些方案基于盲签名、代理签名以及多重短签名实现, 具有签名效率高、计算量小等特点. 这里从签名长度、计算复杂度以及安全性等方面与本文方案进行性能上的分析, 表1记录了各方案的签名计算效率和签名长度. $ H $为$ {\mathrm{h}}{\text{ash}} $计算, $ {G_1} $为加法群, $ M $为$ {G_1} $上的倍点标量乘, $ {P_r} $为双线性对运算, $ E $为幂乘运算, $ |{G_1}| $表示$ {G_1} $上元素的长度, $ |Z_q^*| $表示$ Z_q^* $上元素的长度.

由表1可知, 本方案在签名阶段只需要1次标量乘$ M $和1次$ {\mathrm{h}}{\text{ash}} $计算$ H $, 验证阶段需2次双线性对运算$ {P_r} $和1次$ {\mathrm{h}}{\text{ash}} $运算$ H $, 签名长度为$ |{G_1}| $. 根据对比结果分析, 本方案使用的签名长度短于文献[21,22], 与其他短签名方案^[9,11,12,23]长度保持一致, 签名阶段计算复杂度低于文献[12,21–23], 验证阶段计算复杂度低于文献[12,22], 本方案理论上整体计算效率与性能与文献[9,11]接近一致. 虽然椭圆曲线对运算相对倍乘运算效率略低, 但该方案优势主要在签名长度上, 且椭圆曲线运算交互次数少, 为了保证抗泄露性牺牲了一些存储空间和性能, 所以综上本方案适用于窄带传输场景.

3.3 运行效率分析

在相同实验环境下实现以上几种方案, 计算运行50次完成签名所耗时间, 得到的效率比较如表2所示. 由表中结果可知, 本方案签名过程平均耗时0.006 s, 验证过程平均耗时0.643 s, 方案总平均耗时0.917 s, 方案总耗时与文献[9,11]耗时接近一致, 比文献[12,21–23]分别减少了35%、40%、48%和43%. 总体来看, 本方案整体计算耗时低, 运行效率更高.

4 总结

本文提出了一种基于容忍泄露的内容关联密钥短签名方案, 并在随机预言模型下证明了方案的安全性. 将本文方案与其他方案进行实验对比, 由实验比较结果可以得出结论, 本文方案具有较短的签名长度, 计算效率高, 并能抵抗泄露攻击, 适用于各种需要数据安全快速传输的计算场景. 在下一步研究中, 将利用盲签名的构造思想, 设计一套适用于数据安全传输系统的容忍泄露盲签名方案.