Ahlswede等[1]于2000年第一次提出了网络编码技术。它打破了原有网络传输中,中间节点只对信息进行存储和转发的禁锢,允许中间节点对其接收到的信息进行组合。网络编码具有高吞吐率和高带宽利用率的特性,此外网络编码还能均衡网络负载,提高网络的鲁棒性。Ho等[2-3]提出了随机线性网络编码算法,该算法的中间节点在编码域中随机地选取本地编码系数对接收到的信息进行组合。
网络编码面临的威胁主要有两类:窃听攻击和污染攻击。窃听攻击也被称为被动攻击,是指攻击者通过窃听网络信道从而得到网络中传输的信息还原出信源消息的攻击方式。污染攻击也被称为主动攻击,是指攻击者利用网络编码允许中间节点对接收到的信息进行组合的特点,向网络中加入破坏信息包,从而使信宿节点无法还原出信源消息的攻击方式。本文主要关注的是窃听攻击。
2002年,Cai等[4]提出了r-安全网络编码方案,该方案假设窃听者最多能够窃听r条线性无关信道,其中r小于网络的多播容量。通过向信源消息中加入r个随机密钥,该方案能够使窃听者无法得到信源消息的任何信息。由于向信源消息中加入了随机密钥,因此该方案降低了网络的传输速率,使其无法达到理论上限。2005年,Bhattad等[5]提出了弱安全网络编码方案,该方案通过对信源消息进行线性变换使窃听者无法得到任何有意义的信息。该方案没有引入额外的带宽开销,使得网络的传输速率能够达到理论上限。在实际应用中弱安全网络编码已经足够安全。2015年,Cao等[6]提出了一种抗窃听安全网络编码方案,该方案在窃听者窃听线性无关信道数小于多播容量的情况下可以保证窃听者得不到信源消息的任何信息。2015年,Guang等[7-8]分别对线性安全网络编码的随机密钥的数目和有限域的大小进行了分析,并给出了更低的下界。文献[4-6]提出的方案都对窃听者的能力进行了限制,而随着无线网络的大规模应用,由于无线网络具有多播特性,窃听者可以轻易地窃听所有线性无关的信道,这样的窃听被称为全局窃听。这使得对抗全局窃听成为当下研究的一个重点。
2008年,Vilela等[9]提出一种安全实用网络编码(Secure Practical Network Coding,SPOC)方案,该方案首先在信源节点随机生成一个预编码矩阵,之后用这个预编码矩阵对信源消息进行预编码,最后将这个预编码矩阵加密后和信源消息一同发送出去;该方案能够对抗全局窃听,但其在信息包中加入了预编码矩阵,造成了额外的带宽开销。2009年,Lima等[10]为了提高解码速率在文献[9]的基础上采用下三角矩阵作为预编码矩阵,但该方案仍有较大的加密量和带宽开销。2009年,Fan等[11]通过对全局编码矩阵进行同态加密,从而对抗全局窃听攻击,但是此方案的编码域较大,并且有较高的运算复杂度。2010年,Zhang等[12]提出了一种称为P-coding的方案,该方案要对于整个信源消息以及全局编码矩阵进行置换加密。该方案虽然编码速率较快,但其无法抵抗已知明文攻击。2010年,Guo等[13]提出一种基于全有或全无变换(All or Nothing Transform,AONT)的安全网络编码方案,该方案首先采用文献[14]提出的稀疏AONT矩阵对信源消息进行线性变换,然后对变换后的信源消息的最后一行进行加密;虽然其只对信源消息的最后一行进行了加密,但仍然有较大的加密量。2013年,Liu等[15]设计的基本型方案通过信源消息的第一列生成稀疏的预编码矩阵对其他信源消息进行混合;该方案虽然没有造成额外的带宽开销但加密量较大。2014年,Liu等[16]提出了一种轻量安全网络编码方案,该方案通过两个矩阵分别对信源消息的第一行和整个信源消息进行混合,从而减少了加密量;该方案虽然加密量较小,但编码过程中进行了两次矩阵乘法运算,增加了编码时间。2015年,Liu等[17]提出一种低复杂度的对抗全局窃听的安全网络编码方案,该方案引入了一个稀疏矩阵作为预编码矩阵,并且采用流密码进行加密;由于该方案对信源消息的至少一行进行加密,因此加密量也比较大。
基于以上背景,本文提出一种新的抗全局窃听安全网络编码方案。该方案没有额外的带宽开销,对中间节点的编码方式不需要作任何修改。由于方案加密算法简单且不需要预编码操作,因此具有较高的实际编码效率。此外本方案除了可以对抗唯密文攻击,还可以对抗已知明文攻击。
1 网络模型和概念本文主要关注的是单源多播无环网络,包括有线网络和无线网络,用有向无环图G=(V,E)表示。其中V表示网络中的节点集合,E表示网络中的信道集合,图中的每条边都代表一条无差错信道。用S表示网络的信源节点,用T表示所有信宿节点的集合。此外用有限域Fq表示编码域,其中q为一个素数或者素数的幂,表示编码域的大小。
在发送文件之前,源节点S将要发送的文件分为多个代,其中每一代包含m个从Fqn中随机选取的n维向量,其中m$\ll $n。每一代也可以看作一个m×n的矩阵,用X表示。
本文所关注的窃听者具有以下三个特点:
1) 他可以窃听网络中的任何信道;
2) 他知道所有的编解码方案;
3) 他在计算上是有界的。
2 安全网络编码方案定义1 置换序列,对于一个长度为n的序列P,令P(i)表示序列P的第i个元素,如果P满足以下条件我们就称其为一个置换序列:
1) P(i)∈{0,1,…,n-1};i=0,1,…,n-1。
2) P(i)≠P(j);i≠j。
令h表示置换序列函数,假设a是一个长度为n的序列,令hP(a)表示将序列a按照置换序列P的顺序排列,即:
${{h}_{P}}\left( a \right)={{h}_{P}}\left( \left[ {{a}_{0}},{{a}_{1}},\cdots ,{{a}_{n\text{-}1}} \right] \right)=\left[ {{a}_{P\left( 0 \right)}},{{a}_{P\left( 1 \right)}},\cdots ,{{a}_{P\left( n\text{-}1 \right)}} \right]$ | (1) |
信源消息由XT=[X0*T,X1*T,…,X(m-1) *T]表示,其中Xi*=[xi0,xi1,…,xi(n-1) ](0≤i<m)表示X中的第i行。令X*j=[x0j,x1j,…,x(m-1) j] (0≤j<n)表示X中的第j列。
在本文方案中存在一个密钥管理器用于信源端与信宿端交换共享密钥。下面给出安全网络编码方案的具体步骤。在编码方案中上方有一个“~”的运算符用来表示有限域内的运算。 信源端编码:
1) 信源节点生成信源消息矩阵X。
2) 由密钥生成长度为q的置换序列P1,生成伪代码如下:
Function Permutation_sequence(q)
for 0≤i<q
P(i)←i
for 0≤i<q-1
r←rand()%q
P(i)$\leftrightarrow $P(r)
return P
3) 令P2=hP1(P1)。
4) 将序列P1和P2转换成k1×k2的矩阵分别用P1′和P2′表示,其中k1为q的因子,k2=q/k1(k1和k2尽可能接近)。令Pi′x(a)(i=1,2) 表示符号a在矩阵Pi′中的横坐标,同理Pi′y(a)表示纵坐标。令Pi′(x,y)(i=1,2) 表示矩阵Pi′中位于(x,y)上的符号的值。
5) 将X按照以下方式进行编码得到X′:
$x{{'}_{ij}}={{x}_{ij}}\tilde{+}{{P}_{1}}\left( \left( j\times m+i+i\times j\times \left\lfloor \left( j\times m+i/q \right) \right\rfloor \right)\bmod q \right)$ | (2) |
6) 将X′的每一列X′*j按照以下方式进行编码得到X″:
$x{{''}_{ij}}={{\mathbf{P}}_{1}}'\left( {{\mathbf{P}}_{2}}{{'}_{x}}\left( x{{'}_{\left( \left( i+1 \right)\bmod m \right)j}} \right),{{\mathbf{P}}_{2}}{{'}_{y}}\left( x{{'}_{\left( \left( i+2 \right)\bmod m \right)j}} \right) \right)$ | (3) |
7) 将X″按照以下方式进行编码得到X′′′:
$\begin{align} & x''{{'}_{ij}}=x'{{'}_{ij}}\tilde{+}{{P}_{2}} \\ & \left( \left( j\times m+i+i\times j\times \left\lfloor \left( j\times m+i \right)/q \right\rfloor \right)\,\bmod \,q \right) \\ \end{align}$ | (4) |
8) 将X′′′按照随机线性网络编码的方式编码发送出去。
中间节点编码:
中间节点不需作任何改动,编码方式与随机线性网络编码相同。
信宿节点解码:
1) 利用高斯消元法,根据全局编码矩阵从接收到的消息中还原出X′′′。
2) 按照信源端同样的方式生成置换序列P1和P2。
3) 将序列P1和P2转换成k1×k2的矩阵P1′和P2′。
4) 将X′′′按照以下方式进行解码得到X″:
$\begin{align} & x'{{'}_{ij}}=x''{{'}_{ij}}\text{\tilde{-}}{{\text{P}}_{\text{2}}} \\ & \left( \left( \text{j}\times \text{m+i+i}\times \text{j}\times \left\lfloor \left( \text{j}\times \text{m+i} \right)\text{/q} \right\rfloor \right)\,\bmod \,\text{q} \right) \\ \end{align}$ | (5) |
5) 将X″的每一列X″*j按照以下方式进行解码得到X′:
$x{{'}_{ij}}={{\mathbf{P}}_{2}}'\left( {{\mathbf{P}}_{1}}{{'}_{x}}\left( x{{''}_{\left( \left( i\text{-}1+m \right)\bmod m \right)j}} \right),{{\mathbf{P}}_{1}}{{'}_{y}}\left( x{{''}_{\left( \left( i\text{-}2+m \right)\bmod m \right)j}} \right) \right)$ | (6) |
6) 将X′按照以下方式进行解码得到X:
$\begin{align} & {{x}_{ij}}=x{{'}_{ij}}\text{\tilde{-}}{{\text{P}}_{\text{1}}} \\ & \left( \left( \text{j}\times \text{m+i+i}\times \text{j}\times \left\lfloor \left( \text{j}\times \text{m+i} \right)\text{/q} \right\rfloor \right)\,\bmod \,\text{q} \right) \\ \end{align}$ | (7) |
为了减少密钥传输,且保证窃听者在破解上一代置换序列后,当前代的置换序列仍然安全,从第二代信源消息的传输开始,本文采用文献[12]提出的方案对置换序列进行扰动。与文献[12]相同,假设窃听者每秒可以测试1020个可能的扰动密钥,设扰动密钥key的比特数为l,为了使窃听者无法在100年内破解扰动密钥则需满足:
$\begin{align} &{{2}^{l}}\ge {{10}^{20}}\times 3600\times 24\times 365\times 100\Rightarrow \\ &{{2}^{l}}\ge {{2}^{98}}\Rightarrow l\ge 98 \\ \end{align}$ | (8) |
文献[12]中的扰动方案共需要3个扰动密钥分别为扰动序列起始位置s、扰动序列长度len以及扰动序列生成密钥d,由于len并非必须,所以本文扰动中不再设置len。本文利用key的前「lb q个比特作为密钥s,整个key作为d对置换序列P1进行扰动。然后再利用扰动后的置换序列P1生成P2,其中P2=hP1(P1)。
3 编码方案举例下面给出一个有限域q=16的例子,假设置换序列P1=[0x0,0x0f,0x06,0x04,0x03,0x05,0x0d,0x08,0x0e,0x00,0x09,0x0a,0x0c,0x0b,0x02,0x07],令k1=4,多播容量m=3,则矩阵P1′如下:
${{\mathbf{P}}_{1}}'=\left[ \begin{matrix} 0\text{x}01&0\text{x}0\text{f}&0\text{x}06&0\text{x}04 \\ 0\text{x}03&0\text{x}05&\text{0x0d}&0\text{x}08 \\ \text{0x0e}&0\text{x}00&\text{0x09}&\text{0x0a} \\ \text{0x0c}&\text{0x0b}&\text{0x02}&\text{0x07} \\ \end{matrix} \right]$ |
P2′如下:
${{\mathbf{P}}_{2}}'=\left[ \begin{matrix} 0\text{x}0\text{f}&0\text{x}0\text{7}&0\text{x}0\text{d}&0\text{x}03 \\ 0\text{x}04&0\text{x}05&\text{0x0b}&0\text{x}0\text{e} \\ \text{0x02}&0\text{x}01&\text{0x00}&\text{0x09} \\ \text{0x0c}&\text{0x0a}&\text{0x06}&\text{0x08} \\ \end{matrix} \right]$ |
假设信源消息如下:
$\mathbf{X}=\left[ \begin{matrix} 0\text{x}05&0\text{x}0\text{c}&0\text{x}02 \\ 0\text{x}0\text{b}&0\text{x}05&0\text{x}00 \\ 0\text{x}03&0\text{x}01&0\text{x}07 \\ \end{matrix} \right]$ |
以x00为例进行编码演示,首先根据式(2) 得到x′10和x′20,x′10=x10${\tilde{+}}$ P1(1) =0x0b${\tilde{+}}$ 0x0f=0x04,x′20=x20${\tilde{+}}$ P1(2) = 0x03${\tilde{+}}$ 0x06=0x05。其次根据式(3) 用x′10和x′20对x″00进行替换,因为 P2′x(0x04)=0、P2′y(0x05)=1,所以x″00=P1′(0,1) =0x03。根据式(4) 有x′′′00=x″00${\tilde{+}}$ P2(0) =0x03${\tilde{+}}$ 0x0f=0x0c。信源消息编码后的结果为:
$\mathbf{X}'''=\left[ \begin{matrix} 0\text{x}0\text{c}&0\text{x}0\text{e}&0\text{x}01 \\ 0\text{x}02&0\text{x}08&0\text{x}0\text{a} \\ 0\text{x}0\text{e}&0\text{x}02&0\text{x}0\text{e} \\ \end{matrix} \right]$ |
如表 1所示,文献[9]和[10]的方案都引入了预编码矩阵对信源消息进行预编码,并将预编码矩阵放到了信息包中,因此信息包中每一行都增加了m个符号。文献[17]需要将预编码矩阵中的非零元素发送出去,因此其带宽开销为r+1(r为预编码矩阵中非稀疏列的数量),其余方案都没有额外的带宽开销。本文提出的方案同样没有引入带宽开销。
本文方案与其他方案的加密量如表 1所示,文献[9]对预编码矩阵进行加密,因此加密量为m2。文献[10]需要对预编码矩阵中的非0元素进行加密,此外还需要加密信源消息的某一行,因此加密量为0.5(m+1) m+n。文献[12]需要对整个信源消息矩阵和全局编码矩阵加密,因此加密量为m2+mn。文献[13]需要对AONT变换后的信源消息的最后一行进行加密,因此加密量为n。文献[15]需要对信源消息的第一列和第一行进行加密,因此加密量为n+m-1。文献[16]的加密量与参数k(将信源信息的第一行变换为矩阵后的行数)有关,加密量为n/k。文献[17]的加密量与参数r有关,其需要加密预编码矩阵中的非零元素和信源消息矩阵中的r行,因此加密量为(r+1) m+rn。本文提出的方案对整个信源消息矩阵进行了加密,加密量为mn。
4.3 编码复杂度如表 1所示,文献[9-10]一样都采用了一个非稀疏的预编码矩阵进行预编码操作,所以编码复杂度较大,为O(m2n)。文献[12]没有进行预编码,只是对整个信源消息矩阵和预编码矩阵进行置换加密,因此编码复杂度为O(mn)。而文献[13, 15-16]都采用稀疏矩阵作为预编码矩阵,大大地降低了编码的运算复杂度,为O(mn)。文献[17]虽然也是利用稀疏矩阵进行预编码,但其编码复杂度与r有关为O(rmn)。本文提出的方案没有采用预编码矩阵对信源消息矩阵进行预编码处理,而是直接对信源消息的每个符号进行加密操作,编码复杂度为O(mn)。
4.4 编码时间不同编码方案的编码速率不仅仅与编码复杂度有关,还与方案的加密等操作相关,因此本文对于不同方案的编码时间进行了比较,如图 1所示。其中网络的多播容量m=8,信源消息的长度n=1480(以太网的信息包长),有限域大小q=256,编码信息包数量为10000。文献[16]中的参数k取值为8,文献[17]中的参数r取值为1。仿真中的加密方式均为文献中所采用的加密方式。
影响实际编码效率的因素主要有两个方面:预编码时间和加密时间,下面从这两个角度对编码时间进行分析。文献[9-10, 13, 15-16]均采用高级加密标准(Advanced Encryption Standard,AES)加密,所以先对以上方案进行分析,本文对长度为m、m2、n/k和n的数据包分别进行了加密仿真,每种数据包的仿真个数均为1000。结果显示,长度为m的1000个数据包加密时间为0.341 s,而另外三种分别为1.554s、5.382s和33.436s。由此可以看出加密量为n的方案的加密时间要远远大于加密量为m2、m和n/k的方案。由于文献[10]和文献[15]的加密量均大于n,所以这两种方案编码时间最长。但文献[15]的编码复杂度低,且加密量相对较少,所以编码时间略小于文献[10]。文献[13]的加密量和编码复杂度虽然与文献[15]都很接近,但文献[13]的预编码操作几乎没有进行有限域内的乘法运算而只有加法运算,这大大减少了预编码的时间,从而编码时间也远小于文献[15]。文献[9]的加密量最小,但其编码复杂度较高,而文献[16]的加密量大于文献[9],但编码复杂度低于文献[9],因此二者编码时间基本相同。由于文献[12, 17]以及本文方案均没有采用AES加密算法,因此本文还对AES加密算法、RC4流密码加密算法(文献[17])、置换加密算法(文献[12])和本文提出的算法的加密时间进行了仿真比较,均对1000个8×16的矩阵进行加密。AES加密算法的加密时间为1.856s,流密码加密时间为0.02s,置换加密时间为0.008s,而本文提出的加密方案的加密时间为0.013s,因此AES加密算法的单位符号加密时间分别为后三者的92倍、232倍和142倍。虽然文献[12]、文献[17]和本文方案加密量较大,加密量分别为采用AES加密算法中编码时间最短的文献[16]加密量的8倍、64倍和64倍。但是由于文献[12]、文献[17]和本文方案单位符号加密时间相较于AES加密减少的比例更大,因此整体的加密时间小于文献[16],所以整个编码时间更短。此外由于文献[12]和本文提出的方案不需要预编码且加密更加简单,因此编码时间小于文献[17],本文方案和文献[12]的编码时间基本相同。
首先分析窃听者在没有得到任何明文的情况下是否能够得到信源消息的信息。在这里假设信源消息矩阵足够大。
定理1 当x″ij相互独立时Pr(X″|X′′′)=1/q!。
证明 当给定一个X′′′时,对于任意一组置换序列P1和P2而言,都有且仅有一个矩阵YP1P2满足式(5) ,所以对于任何一个X′′′在无法得到置换序列的情况下可以求出q!个可能的Y。又因为x″ij相互独立,因此对于窃听者而言每一个Y为X″的可能性都相等,因此Pr(Y=X″|X′′′)=1/q!。
对于窃听者而言其要想还原出信源消息,必须要得到X″。而由定理1可以看出,当x″ij相互独立时Pr(Y=X″|X′′′)=1/q!,所以窃听者必须穷举所有可能的置换序列P1进而得到P2。而在本文的方案中经过前两步的变换可以近似地认为X″中的元素是独立的,所以本文的方案在唯密文攻击的条件下是安全的。
4.5.2 已知明文攻击下面对窃听者在已知部分明文的情况下是否能够还原信源消息进行分析。
定理2 窃听者在已知明文的情况下无法获得置换序列P1和P2。
证明 令Xw为窃听者已知的明文集合,因为加密过程中Xw′到Xw″是非线性变换,且窃听者无法获得Xw′和Xw″,所以窃听者无法建立对应位置上明文Xw和密文Xw′′′的变换关系,也就无法求出置换序列P1和P2。
定理3 当mn≤q2时窃听者在已知部分明文的情况下无法进一步破解任何明文。 证明 定理2中已经证得窃听者在已知明文的情况下无法获得P1和P2,所以其无法由置换序列P1和P2入手进一步破解更多的明文。令Xc表示未知明文集合,下面分析当Xw′′′中的某些符号和Xc′′′中的某些符号相等时其对应的Xw和Xc是否相等。为了方便讨论令:
$L\left( i,j \right)=\left( j\times m+i+i\times j \right)\times \left\lfloor \left( j\times m+i \right) \right\rfloor \bmod q$ | (9) |
首先分析L(i,j)的周期性,令k=j×m+i则可以将式(9) 简化为L(i,j)=(k+i×j×$\left\lfloor k/q \right\rfloor $) mod q,不难发现其周期为q2,因为:
$\begin{align} &\left( k+{{q}^{2}}+i\times j\times \left\lfloor \left( k+{{q}^{2}} \right)/q \right\rfloor \right)\bmod q= \\ &\left( k+i\times j\times \left\lfloor k/q \right\rfloor +i\times j\times q \right)\bmod q \\ &=\left( k+i\times j\times \left\lfloor k/q \right\rfloor \right)\bmod q \\ \end{align}$ | (10) |
由解码过程可知当满足以下条件时必有xi1j1=xi2j2,其中i1=i2和j1=j2不能同时成立:
$L\left( {{i}_{1}},{{j}_{1}} \right)=L\left( {{i}_{2}},{{j}_{2}} \right)$ | (11) |
$L\left( \left( {{i}_{1}}-1+m \right)\bmod m,{{j}_{1}} \right)=L\left( \left( {{i}_{2}}-1+m \right)\bmod m,{{j}_{2}} \right)$ | (12) |
$L\left( \left( {{i}_{1}}-2+m \right)\bmod m,{{j}_{1}} \right)=L\left( \left( {{i}_{2}}-2+m \right)\bmod m,{{j}_{2}} \right)$ | (13) |
$x''{{'}_{\left( \left( {{i}_{1}}-1+m \right)\bmod m \right){{j}_{1}}}}=x''{{'}_{\left( \left( {{i}_{2}}-1+m \right)\bmod m \right){{j}_{2}}}}$ | (14) |
$x''{{'}_{\left( \left( {{i}_{1}}-2+m \right)\bmod m \right){{j}_{1}}}}=x''{{'}_{\left( \left( {{i}_{2}}-2+m \right)\bmod m \right){{j}_{2}}}}$ | (15) |
下面分析以上条件是否能同时满足。当L(i1,j1)=L(i2,j2)时有以下等式:
$\begin{align} &L\left( {{i}_{1}}+1,{{j}_{1}} \right)-L\left( {{i}_{2}}+1,{{j}_{2}} \right)= \\ &{{k}_{1}}+1+{{j}_{1}}\times \left( {{i}_{1}}+1 \right)\times {{t}_{1}}- \\ &\left( {{k}_{2}}+1+{{j}_{2}}\times \left( {{i}_{2}}+1 \right)\times {{t}_{2}} \right)= \\ &{{k}_{1}}+{{j}_{1}}\times {{i}_{1}}\times {{t}_{1}}-\left( {{k}_{2}}+{{j}_{2}}\times {{i}_{2}}\times {{t}_{2}} \right)+{{j}_{1}}\times {{t}_{1}}-{{j}_{2}}\times {{t}_{2}}= \\ &L\left( {{i}_{1}},{{j}_{1}} \right)-L\left( {{i}_{2}},{{j}_{2}} \right)+{{j}_{1}}\times {{t}_{1}}-{{j}_{2}}\times {{t}_{2}}= \\ &{{j}_{1}}\times {{t}_{1}}-{{j}_{2}}\times {{t}_{2}} \\ \end{align}$ | (16) |
式(16) 中令k=j×m+i,t=$\left\lfloor \left( j\times m+i \right)/q \right\rfloor $。当j1≠j2时,不妨设j1<j2,则必然有t1≤t2,因此j1×t1-j2×t2≠0,所以L(i1+1,j1)≠L(i2+1,j2)。当j1=j2时,如果t1≠t2,则L(i1+1,j1)≠L(i2+1,j2);如果t1=t2,因为L(i1,j1)=L(i2,j2),所以有:
$\begin{align} &L\left( {{i}_{1}},{{j}_{1}} \right)=L\left( {{i}_{2}},{{j}_{2}} \right)\Rightarrow \\ &{{j}_{1}}\times m+{{i}_{1}}+{{j}_{1}}\times {{i}_{1}}\times {{t}_{1}}={{j}_{1}}\times m+{{i}_{2}}+{{j}_{1}}\times {{i}_{2}}\times {{t}_{1}}\Rightarrow \\ &{{i}_{1}}-{{i}_{2}}=\left( {{i}_{1}}-{{i}_{2}} \right)\times {{j}_{1}}\times {{t}_{1}} \\ \end{align}$ | (17) |
使式(17) 成立的条件有两个:j1×t1=1或者i1=i2,因为j1和t1都为自然数,因此j1×t1=1成立的充要条件是j1=1,t1=1。由于mn≤q2且m$\ll $n所以m$\ll $q,所以当j1=1时$\left\lfloor \left( {{j}_{1}}\times m+{{i}_{1}} \right)/q \right\rfloor $不可能为1,式(17) 成立的条件只能是i1=i2,但这使得i1=i2,j1=j2同时成立,与前提条件相矛盾。综上所述,当L(i1,j1)=L(i2,j2)时L(i1+1,j1)=L(i2+1,j2)不成立,等式 (11) 、(12) 和(13) 不可能同时成立。所以当信源消息矩阵中符号的数量不大于q2时,即使Xc′′′中有符号与Xw′′′中的某些符号相同但由于窃听者无法得到置换序列P1和P2,因此无法进一步得到相应位置上的明文。 当mn>q2时,只有在已知xi1 j1且式(11) ~(15) 同时成立的情况下可由xi1 j1=xi2 j2得到未知明文xi2 j2。由于本文采用的是随机网络编码,而文献[18]证明当编码域q=28时,采用随机网络编码信宿端就可以以接近1的概率解码。当q=28时q2=65536,也就是说当信源消息矩阵中的符号数不大于65536时窃听者在已知部分明文的情况下无法进一步获取更多明文。这个信源消息矩阵的容量足以满足随机网络编码的要求。
以上定理证明当mn≤q2时在窃听者已知部分明文的情况下本文方案可以防止其进一步获取更多明文。
4.5.3 扰动后方案的安全性本文方案从第二代开始对置换序列进行随机扰动,以保证在窃听者获得当代的置换序列的前提下,下一代的编码仍然安全。本文对扰动前后的置换序列以及扰动前后相同密文对应明文的扰动符号(对应位置上数值不相等的符号)的数量分别进行了统计,结果如图 2所示,其中置换序列的长度和密文的符号数均为256,对不同的扰动次数分别进行了500次仿真,取扰动符号数量的平均值。
由图 2可以看出当只进行一次扰动时,相同密文对应的明文的扰动符号数所占的比例接近50%。并且这一比例随着扰动次数的增加不断增大,当扰动三次时这一比例增大到80%以上。所以当窃听者获得当前代的置换序列并用其解码下一代的密文时,其得到的明文中有一半左右的明文是错误的。由于窃听者无法获取扰动密钥,所以其无法获得错误符号的具体位置。此外由于错误符号的比例较大无法忽略,因此在其获得当前代的置换序列后仍然很难破解下一代的密文。为了使扰动后的加密更加安全,信源端可以在每一代都从密钥key中选取多个不同的s对置换序列进行多次扰动。
5 结语本文提出了一种新的对抗全局窃听的安全网络编码方案。该方案只需在信源节点利用置换序列对信源消息进行混合和替换便可实现对抗全局窃听,网络的中间节点不需作任何的改变。该方案不需要预编码操作,因此不需要传输预编码矩阵,没有带宽开销。此外该方案加密算法简单,编码复杂度低,因此具有较高的编码效率。虽然本文方案的实际编码时间与P-coding方案基本相同,但相较于其无法抵抗已知明文攻击,本文方案不但可以对抗唯密文攻击,还可以在一定条件下有效地抵抗已知明文攻击。
[1] | AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46 (4) : 1204-1216. doi: 10.1109/18.850663 |
[2] | HO T, MEDARD M, KOETTER R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52 (10) : 4413-4430. doi: 10.1109/TIT.2006.881746 |
[3] | HO T, MÉDARD M, SHI J, et al. On randomized network coding[C]//Proceedings of the 200341st Annual Allerton Conference on Communication Control and Computing. New York:Allerton Press, 2003:11-20. |
[4] | CAI N, YEUNG R W. Secure network coding[C]//Proceedings of the 2002 IEEE International Symposium on Information Theory. Piscataway, NJ:IEEE, 2002:323. |
[5] | |
[6] | CAO Z H, ZHANG S B, JI X D, et al. Secure random linear network coding on a wiretap network[J]. AEU-International Journal of Electronics and Communications, 2015, 69 (1) : 467-472. doi: 10.1016/j.aeue.2014.10.018 |
[7] | GUANG X, LU J Y, FU F W. On the optimality of secure network coding[J]. IEEE Communications Letters, 2015, 19 (7) : 1165-1168. doi: 10.1109/LCOMM.2015.2430862 |
[8] | GUANG X, LU J Y, FU F W. Small field size for secure network coding[J]. IEEE Communication Letters, 2015, 19 (3) : 375-378. doi: 10.1109/LCOMM.2014.2385053 |
[9] | VILELA J P, LIMA L, BARROS J. Lightweight security for network coding[C]//ICC 2008:Proceedings of the 2008 IEEE International Conference on Communications. Piscataway, NJ:IEEE,2008:1750-1754. |
[10] | LIMA L, BARROS J, MÉDARD M, et al. Towards secure multiresolution network coding[C]//ITW 2009:Proceedings of the 2009 IEEE Information Theory Workshop on Networking and Information Theory. Piscataway, NJ:IEEE, 2009:125-129. |
[11] | FAN Y F, JIANG Y X, ZHU H J, et al. An efficient privacy-preserving scheme against traffic analysis attacks in network coding[C]//Proceedings of the 2009 International Conference on Computer Communications. Piscataway, NJ:IEEE, 2009:2213-2221. |
[12] | ZHANG P, JIANG Y X, LIN C, et al. P-coding:secure network coding against eavesdropping attacks[C]//Proceedings of the 2010 IEEE INFOCOM. Piscataway, NJ:IEEE, 2010:1-9. |
[13] | GUO Q, LUO M X, LI L X, et al. Secure network coding against wiretapping and Byzantine attacks[J]. EURASIP Journal on Wireless Communications and Networking, 2010, 2010 : 216524. doi: 10.1155/2010/216524 |
[14] | STINSON D R. Something about all or nothing (transforms)[J]. Designs, Codes, and Cryptography, 2001, 22 (2) : 133-138. doi: 10.1023/A:1008304703074 |
[15] | LIU G J, ZHOU H. Efficient schemes for securing network coding against wiretapping[J]. Wuhan University Journal of Natural Sciences, 2013, 18 (4) : 355-362. doi: 10.1007/s11859-013-0942-8 |
[16] | LIU G J, LIU X M, XIONG J B, et al. A lightweight secure network coding scheme against wiretapping[J]. Wuhan University Journal of Natural Sciences, 2014, 19 (2) : 156-160. doi: 10.1007/s11859-014-0994-4 |
[17] | LIU G J, LIU B Y, LIU X M, et al. Low-complexity secure network coding against wiretapping using intra/inter-generation coding[J]. China Communications, 2015, 12 (6) : 116-125. doi: 10.1109/CC.2015.7122470 |
[18] | CHOU P A, WU Y, JAIN K. Practical network coding[C]//Proceedings of the 200341st Annual Allerton Conference on Communication Control and Computing. New York:Allerton Press, 2003:40-49. |