一种基于组合公钥的密钥派生方案

罗一帆， 张大伟， 常 亮， 刘晓东， 马儒潇

(1.北京交通大学 计算机与信息技术学院 北京 100044； 2. 桂林电子科技大学 广西可信软件重点实验室 广西 桂林 541004； 3.山东大学 网络信息安全研究所 山东 济南 250100)

0 引言

在安全等级要求很高的系统中，单一密钥的签名方案存在风险，一旦密钥泄露或是被攻破，整个系统的安全就不复存在了.为了提高系统的安全性，一般考虑采用密钥派生方案.常用的密钥派生都是采用多次迭代哈希的方案，将最后的哈希作为派生密钥[1].但是这种方案在泄露其中一个密钥后可以通过迭代算法推导出之后的派生密钥，存在着安全隐患.

基于标识的组合公钥(combined public key，CPK)体制[2-5]是一种新的集中式公钥管理模式，它可以通过公私钥矩阵中的公私钥因子经线性组合派生出大量的公私钥对，而公私钥矩阵本身的存储开销并不大.目前CPK的主要用处是基于用户身份的大规模密钥分配，但CPK还有其他方面的应用.例如文献[6]提出了一种基于CPK的用户身份认证算法,文献[7]提出了一种基于CPK的数字签名方案,但是它们并没有分析解决CPK本身存在的安全问题.由于公私钥是通过公私钥矩阵中的公私钥因子经过线性叠加得到的，因此存在针对公私钥的3种共谋攻击：线性共谋攻击[8-9]、选择共谋攻击和随机共谋攻击[10].文献[11-12]通过引入映射系数的方式提高了系统安全界限，解决了选择共谋攻击，但是经过深入分析，发现其对模运算理解有误，导致对线性共谋攻击的分析有误.文献[13]通过引入辅助矩阵和乘法关系改变了密钥间的线性关系，但是没有完全解决线性共谋攻击，也增加了计算的复杂性.

本文设计了一种基于CPK的密钥派生方案，对不同的消息采用不同的密钥签名.通过改变映射算法，让私钥由私钥矩阵中每个元素乘上素数映射系数后模加得到，使映射系数矩阵的秩达到列满秩m×h.同时，任意小于其秩的数量的私钥间均是线性无关的，无法通过合谋得到其他消息的签名私钥，使得系统在泄露私钥的个数小于m×h时都是安全的.

1 CPK算法

系统参数记为T=(a,b,n,G,p)，其中(a,b)是定义在有限域上的椭圆曲线y2=(x3+ax+b)modp的非负整数；G是加法群的基点；n是以G为基点的群的阶；p是有限域的阶.

根据椭圆曲线参数生成公私钥对，构造规模为m×h的公钥矩阵PKM和私钥矩阵SKM：

(1)

根据用户身份ID计算与ID对应的矩阵元素坐标(index1,1),(index2,2),…,(indexh,h)，其中(indexi,i)表示密钥矩阵中行数为indexi、列数为i的元素.按照与ID对应的矩阵元素坐标，选取公钥矩阵中的元素计算用户公钥PK=(rindex1,1+rindex2,2+…+rindexh,h)G，选取私钥矩阵中的元素计算用户私钥sk=(rindex1,1+rindex2,2+…+rindexh,h)modn.由此可见用户公钥PK=sk×G，满足椭圆曲线公私钥对的对应关系.

2 密钥派生算法

本算法的基本思想是利用CPK派生出大量公私钥，对不同的消息使用不同的私钥进行签名，使用对应公钥验证签名.整个算法包括系统参数生成、密钥派生、签名与验签3个部分.

2.1 系统参数生成

选取椭圆曲线密码参数T=(a,b,n,G,p)，在Zn(Zn为模n的有限域)中随机选取m×h个私钥种子构建私钥矩阵SKM和公钥矩阵PKM，如(1)式所示. 选取不同的素数构成映射系数序列MCS，MCS={m1,m2,…}，其中mi为素数.公开椭圆曲线密码参数T、公钥矩阵PKM和映射系数序列MCS.

2.2 密钥派生

密钥派生算法主要包括以下3个步骤：

1) 计算映射系数.对消息M进行哈希后按位分成m×h帧，即H(M)=w1,w2,…，wm×h，第i帧对应映射系数序列MCS中的第i个素数，故消息M的m×h个映射系数为MCS(w1),MCS(w2),…,MCS(wm×h).

2) 计算签名私钥.映射系数与私钥矩阵SKM中私钥种子相乘后模加得到签名私钥skM，skM=(MCS(w1)×r1,1+…+MCS(wm)×rm,1+…+MCS(wm×h)×rm×h)modn.

3) 计算验证公钥.映射系数与公钥矩阵PKM中公钥种子相乘后相加得到验证公钥PKM，PKM=MCS(w1)×R1,1+…+MCS(wm)×Rm,1+…+MCS(wm×h)×Rm×h.

其中签名者需要执行步骤1)和2)，验签者需要执行步骤1)和3).

2.3 签名与验签

签名. 签名者按照上述私钥生成算法生成签名私钥skM，对消息M用标准椭圆曲线签名算法(ECDSA、SM2)进行签名得到sigskM(M)：sigskM(M)←sig(skM,M).

验签. 验签者希望验证签名sigskM(M)时，按照上述公钥生成算法计算对应公钥PKM后进行验证：0/1←Verify(PKM,sigskM(M),M).若结果是1，说明验证通过，否则验证不通过.

3 安全分析

在传统CPK算法中，私钥是由私钥种子经过映射选取后模加得到，因此存在一定的线性关系.针对这种线性关系，存在3种共谋攻击的方法，即线性共谋攻击、选择共谋攻击和随机共谋攻击.

3.1 线性共谋攻击

线性共谋攻击可以分为两种：一种是通过联立足够的私钥方程解出私钥矩阵的通解；另一种是通过多个私钥线性组合得到其他私钥.在基本CPK方案中，私钥是通过私钥矩阵每列随机选取一个值模加得到，即sk=(rindex1,1+rindex2,2+…+rindexh,h)modn.将所有的私钥组合用矩阵形式表示为

(2)

映射系数矩阵中的元素，即ta(b,c)的含义是：a表示第几个私钥的组合方程，b表示在私钥矩阵的第几行，c表示在私钥矩阵的第几列.ta(b,c)的取值集合ξ={1,0}，1表示私钥矩阵中对应位置被取到，0则表示未被取到.对映射系数矩阵进行初等变换，将第i+1,…,i+m(i=1,m+1,2m+1,…)列加到第i列，会得到h个全1的列，故映射系数矩阵的秩为m×h-h+1.

对于第1种线性共谋攻击，要想解出私钥矩阵的通解，至少需要m×h-h+1个线性无关的私钥.因此，提高矩阵的规模可以增加安全性.但是，对于第2种线性共谋攻击，并不是小于映射系数矩阵秩的私钥个数就一定线性无关，可能存在小于秩数量的私钥经过线性组合得到新的私钥，而出现这种问题的根本原因是基本CPK方案中私钥矩阵每列只取一个元素，导致映射系数矩阵中存在全零的列，映射系数矩阵达不到满秩.

在本文提出的密钥派生算法中，生成私钥时不再是从私钥矩阵中每列取一个元素，而是所有的元素均用到，而且在每个种子前乘上素数的映射系数后模加得到.这样ta(b,c)的取值就不再是0和1，而是完全随机的素数.对于第1种线性共谋攻击，由于经过初等变换也无法得到相同的列，映射系数矩阵的秩达到满秩m×h，因此提高了系统的抗攻击能力.对于第2种线性共谋攻击，由于映射系数矩阵中是完全随机的素数，故从中任取小于m×h行，均是线性无关的.只要共谋私钥数量小于m×h，都不可能经过线性组合得到其他私钥.

3.2 选择共谋攻击

选择共谋攻击的描述是：设用户A与用户B是(j1,j2,…,jt1)层不同，用户A与用户C是(s1,s2,…,st2)层不同，且集合{j1,j2,…,jt1}和{s1,s2,…,st2}交集为空，则用户A、B、C共谋可以得到与A是{j1,j2,…,jt1,s1,s2,…,st2}层不同的用户私钥.在本算法中，私钥是由私钥矩阵中每一个私钥种子与素数系数相乘后模加得到的，故不存在层不同与层互斥不同的关系，因此也不存在选择共谋攻击.此外，选择共谋攻击的本质是私钥之间存在线性关系，因此可以通过线性组合得到其他的私钥.而在本文算法中，由于任意小于矩阵秩的私钥均是线性无关的，故不可能通过线性组合得到其他的私钥.

3.3 随机共谋攻击

随机共谋攻击的描述是：设两个共谋用户A、B的私钥分别为skA、skB，公钥分别为PKA、PKB.然后进行如下步骤：① 计算两者的私钥差ΔskAB=skA-skB，ΔskBA=skB-skA；公钥差ΔPKAB=PKA-PKB，ΔPKBA=PKB-PKA.② 在公钥矩阵中选取公钥因子组合出一个新的公钥PKC，如果PKC-PKB=ΔPKBA或PKC-PKA=ΔPKAB，则该公钥对应的私钥skC=2skB-skA或skC=2skA-skB，否则就继续执行②.

随机共谋攻击的本质是公钥与私钥之间存在关系:PK=sk×G.虽然本算法中添加映射系数后仍然存在这种关系，但是由于需要签名的消息事先是未知的，所以无法确定消息的映射系数，也无法得到消息对应的公钥，因此随机共谋攻击在实施上是不可行的.

4 实验方案

4.1 实验环境

实验主机配置为2.40 GHz、i5-2 430 M CPU，8 GB RAM,系统为Ubuntu16.10.整个实验选择在Python语言下实现，曲线选择ecdsa库中提供的标准曲线NIST256p,哈希函数选取hashlib库中提供的sha256.私钥矩阵和公钥矩阵选取sympy库中提供的Matrix类构建，大小设为4×4，其中私钥矩阵中的元素为小于曲线阶的随机数私钥.公钥矩阵中的元素为对应公钥，以Point类型存储.映射系数序列MCS选取前4 096个素数.

4.2 实验过程

具体实验过程如下.

1) 验证映射系数矩阵是否列满秩. 构建一个行数为44=256，列数为4×4=16的映射系数矩阵，所有元素从映射系数序列MCS中随机选取.由于行数太大，截取其中部分映射系数矩阵，如图1所示.

使用求秩函数计算映射系数矩阵的秩，结果是16，证实了该算法确实能够使映射系数矩阵达到满秩，提高系统的安全界限.

2) 验证映射系数矩阵任意16行是否满秩. 任意选取映射系数矩阵中的16行构成一个新的矩阵，再次使用求秩函数计算其秩，结果仍然是16，证实了该算法确实能使小于映射系数矩阵秩的任意数量私钥均线性无关，无法共谋得到其他私钥，系统的安全界限达到m×h.

3) 签名与验签. 需要验证采用CPK的密钥派生算法的签名和验签是否通过.生成一条消息m=“helloworld”，计算其sha256哈希值h,根据哈希在映射系数序列中取出对应位置素数，与私钥矩阵中的种子相乘后模加得到消息的签名私钥sk.然后调用签名函数用该私钥对消息m进行签名得到sig.同样地，根据消息的哈希在映射系数序列中取出对应位置素数，与公钥矩阵中的种子相乘后相加得到消息的验签公钥PK.调用验签函数，用公钥PK验证消息m的签名sig，结果验签通过.

图1 部分映射系数矩阵Fig.1 Partial mapping coefficient matrix

4.3 性能比较

由于私钥矩阵、公钥矩阵、映射系数序列是事先生成好的，故不考虑其生成时间.表1为传统ECDSA与密钥派生算法的性能比较.从表中可以看出，采用密钥派生算法后的签名时间接近ECDSA的4倍，验签时间接近2倍，性能损耗在可以接受的范围内.

表1 ECDSA与密钥派生算法的性能比较

5 计算量与存储量

在计算量方面，本文算法对于不同的消息采用不同的私钥签名.在签名阶段，签名者需要执行1次消息的哈希运算，m×h次映射系数与私钥种子的数乘运算，m×h-1次Zn域上的模加运算.在验签阶段，验签者需要执行1次消息的哈希运算，m×h次映射系数与公钥种子在椭圆曲线上的点乘运算，m×h-1次椭圆曲线上的模加运算.由于Hash运算速度很快，椭圆曲线上的加法运算也很高效，点乘运算可以用硬件实现加速，故整体的计算开销不大.

在存储量方面，相比于普通CPK，存储开销仅多了映射系数序列MCS，私钥矩阵、公钥矩阵的存储都完全一样，故整体的存储开销也不大.

6 结束语

为了提高单密钥签名的安全性，设计了一种基于组合公钥的密钥派生算法.同时，针对CPK现有的安全问题，引入映射系数，改变了私钥的生成方式，使得映射系数矩阵达到满秩m×h.由此，任意小于映射系数矩阵秩数量的私钥均线性无关，无法共谋得到其他私钥，使系统的安全界限提高到m×h.但是本文算法无法解决共谋私钥数量大于m×h的情况，如何彻底地解决CPK的共谋攻击问题，还需要进一步的研究.

参考文献：

[1] 聂文霞, 孙贵芳, 张形形. TD_LTE系统中密钥派生函数(KDF)研究[J]. 广东通信技术,2015，35(4): 40-43.

[2] 唐文, 南相浩, 陈钟. 基于椭圆曲线密码系统的组合公钥技术[J]. 计算机工程与应用, 2003，39(21): 1-3.

[3] 南湘浩. CPK五种版本要点[J]. 计算机安全, 2010(10): 1.

[4] 南湘浩. CPK组合公钥体制(v8.0)[J]. 信息安全与通信保密, 2013(3): 39-41.

[5] 南湘浩. CPK组合公钥体制(v7.0)[J]. 计算机安全, 2012(5): 2-4.

[6] 邵春雨, 苏锦海. 基于组合公钥的用户公钥认证算法[J]. 计算机工程,2011，37(4): 145-146.

[7] 张锋, 王明华, 杨欣. 基于CPK的数字签名系统设计与实现[J]. 信息通信, 2016(5): 104-106.

[8] 熊荣华, 李增欣, 杨恒亮,等. 组合公钥(CPK)体制密钥间的线性关系[J]. 计算机安全, 2012(1): 30-33.

[9] 熊荣华, 李增欣, 杨恒亮,等. 组合公钥(CPK)体制的安全性分析[J]. 中国信息安全, 2011(12): 75-77.

[10] 赵美玲, 张少武. 基于ECC的组合公钥技术的安全性分析[J]. 计算机工程, 2008，34(1): 156-157.

[11] 李方伟, 马安君, 朱江,等. 解决组合公钥共谋攻击和密钥碰撞的新方法[J]. 计算机应用研究, 2014，31(4): 1176-1179.

[12] 马安君, 李方伟, 朱江. 组合公钥体制的线性共谋攻击分析[J]. 计算机应用, 2013，33(8): 2225-2227.

[13] 邵春雨, 苏锦海, 魏有国,等. 一种双矩阵组合公钥算法 [J]. 电子学报, 2011, 39(3): 671-674.