俞惠芳，李雯

（西安邮电大学网络空间安全学院，陕西 西安 710121）

1 引言

网络编码[1]是一种新型的信息传输技术，在提升网络的吞吐量、增加网络的强壮性、减少网络宽带资源的消耗等方面比传统的路由技术都具有明显的优势。但是当节点受到恶意攻击或网络传输信道不稳定时，产生的污染信息将会随着编码传输与其他有效消息进行编码组合，进而将污染传染给其他消息，最终使信宿节点无法正确解码恢复出原始消息。

近年来，研究人员提出了一些抵抗污染攻击的方案，使网络编码污染问题在传统的签名方法中得到了很好解决。Yu 等[2]提出了基于同态签名的线性网络编码方案，可以检测出污染攻击的发生。但是Yun 等[3]已证明了Yu 等[2]提出的算法不满足同态性质，虽然能检测出污染攻击的发生，但是不能处理该节点。Boneh 等[4]提出了一种全局编码向量的签名方案，可以抵御代内/外污染，但是签名和验证的计算复杂度高，时延较长。Li 等[5]提出了分布式污染节点定位方案，每个节点都可运行算法，自行判断污染节点，缺点是算法精度不高，存在误判概率，并且需要运行多次才能确定污染处。Charles 等[6]利用椭圆曲线上的点设计了一种同态签名方案，缺点是存在漏洞，可以伪造通过验证[7]。He 等[8]提出了自适应网络编码方案，中间节点可根据网络污染情况自动调整策略进行验证，缺点是网络节点必须保证时间同步，这样会消耗大量网络资源。裴恒利等[9]使用时间戳生成网络编码的随机系数，利用RSA 同态签名抵抗污染攻击和重放攻击，但是数据分组部分的正交分量计算复杂，增加了资源浪费。蒙云番等[10]构造了椭圆曲线密码体制（ECC,elliptic curve cryptography）下的同态签名方案，保障了无线体域网的通信安全，缺点是不能抵抗代间污染，计算开销大。Wu 等[11]提出了一种基于密钥预分发的标签编码方案，可以抵御污染攻击和标签污染攻击，但是不能检测出代间污染攻击。Cheng 等[12]提出了一种改进的同态子空间网络编码签名方案，将代间标识符结合到密钥生成过程中，不足之处是签名过程较复杂，网络负载大，易造成缓存溢出。

上述的抵抗污染攻击算法仅限于单源的网络编码，多源网络编码中的污染问题比单源网络编码复杂。Agrawal 等[13]针对多源网络编码构造了同态签名机制，当中间节点组合来自多个源的数据分组时，该机制能提供完整性，然而每个分组需要进行多次的签名验证，导致计算开销大。Yang 等[14]提出了能够保证数据完整性的无条件安全认证码的多源网络编码方案，不足之处是存在安全漏洞，容易受到重放攻击。Zhang 等[15]提出了一种实时签名方案以抵抗多源网络污染攻击，但在安全性方面存在一些缺陷。Le 等[16]提出了适用于多源网络编码的基于同态消息认证码的签名方案，缺点是中间节点不能将被污染的数据分组过滤掉。Li 等[17]为了解决网络编码认证问题，提出了一种多源线性同态网络编码签名方案，但节点的签名和验证运算中需要进行大量的模指数运算，增加了计算复杂度。俞惠芳等[18]采用Schnorr 签名机制，提出了适用于多源网络编码的环签名方案，在环签名中引入时间概念，既能抵抗污染攻击又能抵抗重放攻击。彭勇等[19]为了预防多源网络的污染攻击和背叛攻击，提出了多源网络编码同态签名算法，改变了数据分组的组合方式，但是接收节点解码速度较慢。牛淑芬等[20]提出了一种多源网络编码数据完整性验证方案，利用私钥对散列值进行聚合签名，接收节点利用公钥验证线性编码消息的完整性，但需要在有限域中进行大量的指数运算，降低了验证效率。

针对单源网络编码中签名、验证计算复杂度高、效率低、资源浪费、不能有效地抵抗代间污染等不足，本文借鉴文献[10,21]的思想提出了一种单源网络编码体制下椭圆曲线同态签名方案，实现了确定污染节点和过滤污染信息的功能，从而可以抵抗代内/间的污染，仿真实验显示，所提方案比同类方案[22]提高了节点验证效率，减少了能源消耗。同时，针对所述多源网络编码方案中计算开销大、签名验证过程复杂、不能预防重放攻击等缺点，本文在文献[9,23]的理论基础上提出了基于双线性映射的多源网络编码同态签名方案，能有效抵抗污染攻击和重放攻击，分析表明，所提方案比同类方案降低了对节点计算能力的要求，减少了系统开销和节点的验证时间。

2 预备知识

2.1 单源线性网络编码模型

图1 适用于网络编码的单源传输网络模型

源节点在发送数据M之前将其分为m个块，即M1,M2,…,Mm，每块用n维向量来表示，即，p是一个大素数，同时将所有的文件块按照如下规则进行扩充

将原始传输的文件设为M1,M2,…,Mm，恢复原始文件时计算

2.2 多源线性网络编码模型

文献[23]的多源网络编码模型中，每个源节点发送的每条消息都有统一分配的唯一的二维索引[25]，不同的源节点发送相同的多播消息有着相同的索引。将多播的多源网络编码用G=(V,E)来描述，其中V和E分别是节点和边的集合，S={s1,s2,…,sm}⊂V是源节点集，D={d1,d2,…,dk}⊂V是目的节点集。D接收S发送的m条多播消息，如图2所示。

图2 适用于网络编码的多源传输网络模型

将m条多播消息表示为V1,…,V m，将每条消息Vi看成是n维向量空间V/Fp中的一个向量，记为，其中1≤i≤m。

设W=(W1,W2,…,Wl)为多播网络中任意一条边上发送的消息，接收节点收到l条消息的线性组合，即

其中，α=(a1,a2,…,al)称为局部编码向量。易知，任意一条边上发送的消息W也是原消息Vj(1≤j≤m)的线性组合，即

其中，β=(β1,β2,…,βm)称为全局编码向量。

设接收节点ti收到m个线性无关的编码消息W1,W2,…,Wm，而且相关的全局编码向量用G表示，恢复原消息

原消息V1,…,Vm为

消息后面附加全局编码向量βi与消息一起传输，扩展的原消息可看成m+n维的向量空间V/Fp中的一个向量，记作

所以，编码消息可以表示为Wi=(wi,1,…,wi,n,βi,1,βi,2,…,βi,m)，为了方便，将编码消息表示成Wi=(wi,1,…,wi,m+n)。

2.3 双线性对

令a,b∈Zp*；令G1是阶为大素数q的加法循环群，生成元为P；令G2是阶为q的乘法循环群。若映射e:G1×G1→G2满足如下性质，则为双线性对[26]。

1)双线性：对于任意的P,Q∈G1，都有e(aP,bQ)=e(P,Q)ab。

2)非退化性：存在P,Q∈G1使e(P,Q)≠1。

3)可计算性：对于任意的P,Q∈G1，e(aP,bQ)=e(P,Q)ab=e(P,abQ)=e(abP,Q)。

2.4 椭圆曲线密码简介

椭圆曲线密码体制（ECC）是基于椭圆曲线离散对数问题的公钥密码体制，椭圆曲线加法群的离散对数问题的求解比有限域乘法群的离散对数问题求解更难，它可用小密钥来保证高级别的安全性。选取椭圆曲线E(a,b)：y2≡x3+ax+b(modp)。E(a,b)通过一组参数(p,a,b,G,q,h)唯一确定。在有限域Fp中，p是一个大素数，表示域的大小；a,b∈Fp是椭圆曲线方程的参数，满足方程4a3+27b2(modp)≠0，G是椭圆曲线上阶为大素数q的基点，q＜＜p，且q＞2160和，要满足q不能整除pk-1。

2.5 散列碰撞

输入P1,…,Pr（r>1）是有限域Fp中阶为q的椭圆曲线上的点

输出元组a=(a1,…,ar)，b=(b1,…,br)∈Fpr，使a≠b且

椭圆曲线上q阶循环群上的离散对数到散列碰撞有一个多项式时间约简。

3 单源网络编码同态签名方案

3.1 方案实例

3.1.1 系统设置

HG是一个单向抗碰撞 hash 函数，。其中G1是阶为大素数q的加法循环群，G是椭圆曲线上的基点。密码学安全的散列函数选取秘密随机数假设源节点要发送l个代的消息，标识符I表示消息代。计算SPK=HG(I)，SSK=α SPK，SSK是代对应的私钥。

1)源节点处

2)中间节点处

3.1.2 签名算法

1)源节点的签名过程

2)组合

3)中间节点签名过程

4)验证

①接收节点收到传递来的消息向量时，先对每一个接收到的签名进行验证，通过验证后再进行编码。

③计算

如果X=0，则拒绝签名，否则，令。若成立，则接受签名；否则，拒绝该签名。

④验证依据

将式(8)代入式(13)，得到组合后消息的散列函数为

由此说明了散列函数具有同态性质。

将式(10)和式(11)代入X=U1G+U2Pid=(x1id,y1id)中，可得

3.2 安全性分析

在单源网络编码椭圆曲线同态签名中，为了防止污染攻击，在每个转发节点处进行一次签名验证和签名。在证明中利用了随机预言模型，假设某个节点被攻击者攻破，得到该节点的私有数据及所有公共参数，要伪造能通过验证的信息，必须破解椭圆曲线离散对数难题。攻击者A 可以用这些参数来伪造签名，但是这相当于在求解椭圆曲线离散对数难题。

定理1当且仅当在多项式时间内求解椭圆曲线离散对数问题是困难的，单源网络编码椭圆曲线同态签名是安全的。

证明令B 是一个挑战者，B 的目标是利用攻击者A 攻破椭圆曲线离散对数困难问题。A 和B 进行的游戏如下。A 选择消息提交给B。

系统设置。B 通过运行系统初始化算法得到(G,Kid,K′,H G(I),R)，然后发送系统参数给A。

h询问。B 在任意时刻都可以询问h预言机，h-list 是一个起初为空的列表。如果表h-list 有匹配的元组，则返回该值；否则，B 随机选择值返回，并将该值添加到表h-list 中。

h1询问。B 在任意时刻都可以询问h1预言机，h1-list 是一个起初为空的列表。如果相应的值已经在表h1-list 中，则返回该值；否则，B 随机选择值返回，然后添加该值到表h1-list 中。

证毕。

定理2当且仅当在多项式时间内散列函数是抗碰撞的，单源网络编码椭圆曲线同态签名是安全的。

证明攻击者A 伪造信息w′(w′≠w)，使λ′=λ。因为，可得，但是A 的伪造过程等价于在有限域Fp上证明式(16)成立。

证毕。

定理3当且仅当在多项式时间内能抵抗代间重放攻击，单源网络编码椭圆曲线同态签名是安全的。

证明当I′≠I时，在随机预言模型下，散列函数H G(I)被看成是一个随机预言机，而攻击者不能在多项式时间内找到I′≠I使H G(I′)=H G(I)。因此，所提方案中代间重放攻击无法成功实施。

证毕。

3.3 实验结果与分析

本节利用Matlab工具对所提方案和Cheng等[22]方案进行计算开销对比，主要密码操作的计算成本定义如下。

执行一次指数运算的时间用Cme表示，Cme=0.83 ms。

执行一次椭圆曲线上标量乘运算的时间用Cmul表示，Cmul=0.75 ms。

执行一次散列运算的时间用Cmtp表示，Cmtp=1.18 ms。

执行一次双线性对运算的时间用Cpar表示，Cpar=2.75 ms。

所提方案和Cheng 等方案的性能比较如表1所示。考虑到椭圆曲线上标量乘（160位）比相同安全级别下的模指数运算（1024位）成本更低，因此所提方案平均具有最优的计算复杂度。具体来说，数据分组签名时，Cheng 等方案需要(m+n+2)Cmul+(m+n+2)Cme，而所提方案需要(m+n+2)Cmul+2Cmtp。为了验证数据分组，Cheng等方案需要(3(m+n)+2)Cmul+3(m+n+1)Cme，而所提方案需要(m+n+1)Cmul+2Cmtp。很明显，所提方案效率优于Cheng 等方案，因为所提方案中签名和验证也是基于椭圆曲线实现的，运算中用到椭圆曲线上的标量乘，没有模指数运算，从而减少了运算时间。

图3和图4分别表示所提方案和Cheng 等[22]方案签名耗时和验证耗时的仿真曲线。本节选用椭圆曲线的安全参数q=2159+217+1，q是160位的Solinas 素数，p是512位素数，令m=50，消息向量维数m+n分别为100、200、300、400、500、600、700、800。由图3和图4可以看出，随着消息向量维数的增加，所提方案签名和验证的耗时低于Cheng 等方案，因此得出所提方案优于Cheng 等方案的结论。

4 多源网络编码同态签名方案

4.1 方案实例

1)系统设置

G1是阶为大素数q的加法循环群，其中G为G1的生成元，用户ud(1≤d≤s)随机选择作为私钥，计算pk=s kG作为公钥。Hg是一个单向抗碰撞hash 函数，Hg:{0,1}*→G1。Ti为时间戳，且，T为当前时刻。，其中β1,β2,…,βm是随机系数，当前时刻T收到的m条消息组合中的时间戳为(T1,T2,…,Tm)。

表1 单源网络编码签名性能比较

图3 签名耗时比较

图4 验证耗时比较

2)签名算法

一个消息Vj的签名为σj(ud)，其中第k个数据分量的签名是

输出用户ud对Vj(1≤j≤m)的签名。当不涉及其他用户时，签名可以记为

3)组合

α=(α1,α2,…,αl)为局部编码向量，σ1,…,σl分别为消息向量W1,…,Wl的签名，其中组合后形成的向量为

生成W的签名(σ1,σ2,…,σs)为

其中，σi,k(1≤i≤m,1≤k≤s)是σi的第k个元素。

4)签名验证算法

公钥为p1,p2,…,p s∈G1，消息向量W的全局编码向量是β=(β1,β2,…,βm)，签名为σ，验证H g(T)=Hg((β1T1+β2T2+…+βmT m)modp)是否成立，若不成立，则拒绝验证；若成立，则验证等式

是否成立，若成立，则验证成功。

4.2 正确性分析

1)由多源网络编码可得

为了区分不同用户的相同消息可组合在一起，设

在消息W的组合过程中，消息Vj来源于用户u1,u2,…,us，βj为消息Vj的全局组合系数。βj(u1),…,βj(us)分别是每个用户u1,u2,…,us对消息Vj赋予的组合系数，因此W可以表示为

组合的签名为

签名σ第k个分量σk为

其中，σj,k(ud)是用户ud对消息Vj签名σj(ud)的第k个分量。

2)由于

4.3 安全性分析

定理4采用双线性对的多源网络编码签名能够抵抗污染攻击。

证明挑战者B 运行系统初始化算法，生成公开参数和系统私钥，然后将系统公开参数发送给攻击者A，保存私钥。

当m*不是时间戳Ti时刻的消息时，证明方式与文献[22]类似。在询问阶段，A 选择的消息子空间V°是由向量(V1,V2,…,Vm)张成的，并向B 询问此消息子空间中各消息向量的签名。B 收到询问请求后，先选取Ti作为V°的时间戳，然后生成各向量Vi的签名σi，并将签名σi和时间戳Ti发送给A。由此A 可获得式(22)所示的方程组

A 输出一系列伪造消息(Ti,m*,σ*)，m*∉V°，若伪造的消息量可通过验证，那么式(23)所示方程组成立

设在式(22)中，ζ为系数矩阵与增广矩阵的秩，其解的个数为p n-ζ，即式(23)的秩为ζ+1，解为p n-ζ-1，易知式(22)中将有p个解满足式(23)。A 赢得游戏的概率为，可忽略不计（p是一个很大的素数）。

签名伪造。由式(17)易知，签名σj,k(ud)是关于n个未知Hg(T)sk的一个线性方程。A 试图从传输的数据分组中推导出Hg(T)sk，而Hg(T)是m个时间戳Ti线性组合的单向碰撞散列函数，A 不能通过解决单向碰撞散列函数问题得到Hg(T)sk，没有Hg(T)sk就不能伪造一个有效的签名，即签名不可伪造。

证毕。

定理5采用双线性映射的多源网络编码签名能够抵抗重放攻击。

证明攻击者A截获(m,T,σ)并将其重放到网络中，重放签名(m,T′,σ′)在中间节点处重复发送，但因消息组合中的时间T′(T′≠T)，即Hg(T)≠Hg(T′)，则可以断定该消息为重放消息签名并丢弃，所以攻击无效。

证毕。

4.4 实验结果与分析

本节中的主要密码操作的定义与3.3节中的一样，此处不再赘述，信源节点的个数用s表示，表2显示了不同方案的签名性能。

所提方案与Li 等[17]方案、Zhang 等[15]方案的签名耗时仿真曲线如图5所示，三者的验证耗时仿真曲线如图6所示。通过Matlab 仿真数据可以看出，随着消息向量维数的增加，不同方案的运行时间均线性增长，但是所提方案比Li 等方案、Zhang 等方案增长缓慢，而且所提方案的签名和验证的耗时比同类方案低。

经过几组方案的对比可得出，所提方案效率优于同类方案是因为运算大多是标量乘，几乎不用指数运算，减少了运算时间的开销。

表2 多源网络编码签名性能比较

5 结束语

单源网络编码椭圆曲线同态签名是在ECC 签名的基础上结合了同态散列函数和“代”的概念提出的，能够有效抵抗代内/代间污染。相比于同类方案，该方案的签名和验证计算时间短，能节约资源，减少通信开销。使用双线性对的多源网络编码同态签名是采用时间戳的同态签名方案，能够抵御污染攻击和重放攻击，该方案中的双线性对内部进行的是标量乘运算，与进行大量的指数运算的双线性对同类方案相比计算复杂度低，签名和验证效率更高；该方案在选择性攻击情况下是安全的。强安全性和更高签名验证效率的多源网络编码同态签名是本文下一步计划之一。