（计算数学专业论文）基于网络编码和hash函数的一个保密通信方案.pdf

李克荣：基于网络编码和h a s h 函数的一个保密通信方案 中文摘要 r w y e u n g 、r a h l s w e d e 等人在2 0 0 0 年首次提出网络编码的概念。网络编码一改以往 s t o r e - a n d f o r w a r d 的路由方式，允许中问结点对输入信道的输入信息进行编码后再传输出 去。通过网络编码，可以充分的利用网络的信道通信容量，达到由最小割最大流定理所确 定的最大流上界。根据节点的输入和输出关系不同可分为线性网络编码和非线性网络编 码。其中线性网络编码的编码简单，实施方便。因而对于网络编码的研究大多基于线性网 络编码。 在传统的信息传输过程中，对一些重要的信息要设法提高传输的安全性。那么在网 络编码中，必然也存在安全性问题。问题是能否结合网络编码的特殊性，来实现网络传输 的安全性呢? 答案是肯定的。n c a i 和v y e u n g 在文献【2 4 】中提出了安全性问题的模型，即 窃听信道通信网络( c s 胍) 模型。并给出了在这个问题模型上存在安全的线性网络编码的 充要条件，同时也给出了一个解决的方法。后来基于这个方法，有许多方法被陆续提出。 如在c s w n 上用秩距码来实现安全通信。无论使用何种方法，保证通信安全的方法都是在 要传输的信息中加入冗余字符。如果窃听者能够同时窃听到t 条信道的话，那么加入的冗 余至少要t 个。在窃听者能够同时窃听到的信道数量比较大的情况下，严重的降低了信息 传输的效率。 为了减少所加入的冗余字符的数量，提高信息传输的效率。m a d e l i 和h l i u 在参考 文献 3 6 中提出了一个基于线性网络编码和h a s h 函数的安全通信协议。该协议利用带密钥 的h a s h 函数，只需添加一个独立于消息字符的随机变量k ，便可以在要传输的每个字符上 叠加上一个随机变量，从而对要传输的消息进行了加密。为了达到完善保密性的要求，随 机变量k 至关重要。一旦k 被窃听者窃听，则窃听者便能综合所窃听到信息，很容易地恢 复出信源传输消息的部分信息。m a d e l i 和h l i u 在参考文献【3 6 】中，给出的保密k 的方法 存在严重的漏洞，一旦窃听到的信道组合得当，便能很容易的恢复出k 。该论文对之进行 了改善，得到了能够完全的保密k ，从而实现完善保密性要求的可行的编码方法。 该论文按照下面的步骤进行组织。在第一章介绍了网络编码的相关知识；第二章介绍 了保密通信的相关知识；第三章引入了c s w n 模型，并给出了一些已有的在c s w n 模型上实 现安全通信的方法；第四章给出了本文的主要结果，给出了对基于h a s h 函数的在c s w n 模 型上实现安全通信的方法的改善方法，并给出了一个例子。 关键词：网络编码信息安全完善保密性h a s h 函数信息率 扬州大学硕士毕业论文 n e t w o r kc o d i n gi sf i r s ti n t r o d u c e d i sd i f f e r e n tf r o mt h et r a d i t i o n a l s t o r e - a n d - f o r w a r d r o u t i n gs c h e m e a b s t r a c t 2 b yr w y e u n ga n dr a h l s w e d ei n2 0 0 0 n e t w o r kc o d i n g i n f o r m a t i o n p r o c e s s i n gm e t h o d ，w h i c h i sc a l l e d a sam a t t e ro ff a e t , o ni n t e r m e d i a t en o d e s ，n e t w o r k c o d i n ge n c o d e st h ei n f o r m a t i o no fi n p u tc h a n n e l st h e ns e n d so u tt h r o u g ho u t p u tc h a n n e l s s t u d y s h o w sn e t w o r kc o d i n gc a ni n c r e a s et h en e t w o r kt h r o u g h p u t ，a n da c h i e v et h eu p p e rb o u n d w h i c h i sd e t e r m i n e db yt h em a x - f l o wm i n - c u tt h e o r e m a c c o r d i n gt ot h er e l a t i o n s h i pb e t w e e ni n p u t a n do u t p u tn o d e s ，t h en e t w o r kc o d i n gc a nb ed i v i d e di n t ol i n e a rn e t w o r kc o d i n ga n dn o n l i n e a r n e t w o r kc o d i n g c o n s i d e rt h el i n e a rn e t w o r kc o d i n gw h i c hc o d i n gs i m p l ea n df a s tt o i m p l e m e n t ，s or e s e a r c ha n da p p l i c a t i o no fn e t w o r kc o d i n gi sm a i n l yb a s e do nt h el i n e a rn e t w o r k c o d i n g 。 i nt h et r a d i t i o n a li n f o r m a t i o nt r a n s m i s s i o np r o c e s s ，f o rs o m ei m p o r t a n ti n f o r m a t i o nw et r y t oi m p r o v et h es e c u r i t yo ft r a n s m i s s i o n t h e ni nt h en e t w o r kc o d i n g ，t h e r ea l s oe x i s ts e c u r i t y i s s u e s t h eq u e s t i o ni sc o u l dw ec o m b i n et h es p e c i a ln a t u r eo fn e t w o r kc o d i n gw h e nw et r yt o s o l v et h ei s s u e s t h ea n s w e ri sa b s o l u t e l y n c a ia n dw y e u n gi nt h el i t e r a t u r e 【2 4 】p r o p o s e da m o d e lo ft h es e c u r i t yi s s u e sw h i c hi sc a l l e dac o m m u n i c a t i o ns y s t e m so naw i r e t a pn e t w o r k ( c s w n ) ，i nt h el i t e r a t u r ean e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nf o r t h ef e a s i b i l i t yo fc o n t r u c t i n ga s e c u r el i n e a rn e t w o r kc o d ei sd e r i v e d ，a n da l s og i v eas o l u t i o nt ot h ei s s u e l a t e r , b a s e do nt h i s a p p r o a c h ，t h e r ea r em a n ym e t h o d sh a v eb e e np u t t i n gf o r w a r dp r o p o s a l s f o re x a m p l e ，u t i l i z et h e r a n kd i s t a n c ec o d et oa c h i e v et h es e c u r ec o m m u n i c a t i o n n om a t t e rw h a tm e t h o dt ob eu s e d ，t h e e s s e n c eo ft h e s em e t h o d sa r eb a s e do ne m b e d d i n gu n i f o r m l yd i s t r i b u t e dr a n d o ms y m b o l si nt h e i n f o r m a t i o nv e c t o ra n dm i x i n gt h e mw i t hi n f o r m a t i o ns y m b o l st h r o u g hl i n e a rc o m b i n a t i o n s i t h a sb e e ns h o w nt h a tw i t he x i s t i n ga p p r o a c h e s ，t h en u m b e ro fn o i s ys y m b o l sm u s tb ea tl e a s t e q u a lt ok ，i ft h ea d v e r s a r yc a na s s e s sa tm o s tki n d e p e n d e n tc h a n n e l s i nt h ec a s eo fkl a r g e r , t h e s ee x i s t i n ga p p r o a c h e si ns i g n i f i c a n tr e d u c t i o ni ni n f o r m a t i o nr a t e i no r d e rt or e d u c et h en u m b e ro fr e d u n d a n ts y m b o l sa n di m p r o v et h ee f f i c i e n c yo f i n f o r m a t i o nt r a n s m i s s i o nm a d e l i ，a n dh l i ui nt h er e f e r e n c el i t e r a t u r e 3 6 】h a sp r o p o s e da s c h e m et h a tr e q u i r e so n l yo n en o i s ys y m b o lt ob ee m b e d d e di nt h eo r i g i n a li n f o r m a t i o ns y m b o l v e c t o rt oa c h i e v ec o m p l e t es e c r e c y t h i ss c h e m eu t i l i z e sh a s hf u n c t i o n st og e n e r a t ed i f f e r e n t r a n d o mn o i s ys y m b o l sb yu s i n gt h eo n l yu n i f o r m l yd i s t r i b u t e dr a n d o ms y m b o la n dt h e i n f o r m a t i o ns y m b o l s t h en o i s ys y m b o lki sv e r yi m p o r t a n ti nt h i ss c h e m e ，b u ti nt h em a d e l i ， a n dh l i us c h e m e ，t h ekc a n tb ep r o t e c t e dw e l l ，c a nb ee a s i l yr e c o v e r e dt h r o u g hl i n e a r c o m b i n a t i o n t h i st h e s i st r yt oi m p r o v em a d e l i ，a n dh l i u ss c h e m e 李克荣：基于网络编码和h a s h 函数的一个保密通信方案 3 t h i st h e s i sw a so r g a n i z e da sf o l l o w i nc h a p t e r1 ，d e s c r i b e st h en e t w o r kc o d i n gk n o w l e d g e i nc h a p t e r2 ，d e s c r i b e st h ek n o w l e d g eo fs e c l l r ec o m m u n i c a t i o n i nc h a p t e r3 ，i n t r o d u c et h e c s w nm o d e l ，a n dg i v e ss o m ee x i s t i n gs c h e m e sw h i c ha c h i e v es e c u r ec o m m u n i c a t i o n s i n c h a p t e r4 ，t h em a i nr e s u l t so f t h i st h e s i sw a sg i v e ，w h i c hi m p r o v em a d e l i ，a n dh l i u ss c h e m e i nt h el a s tw e g i v eae x a m p l et oi l l u s t r a t et h ei m p r o v e ds c h e m e k e y w o r d s ：n e t w o r kc o d i n g s e c u r ec o m m u n i c a t i o n c o m p l e t es e c r e c y h a s hf u n c t i o ni n f o r m a t i o nr a t e 李克荣：基于网络编码和h a s h 函数的一个保密通信方案 扬卅i 大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 4 3 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究成果。 除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表的研究成果。对本 文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人 承担。 。 学位论文作者签名： 彦芡眷 签字日期：) 。年月) 芬日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关 部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。本人授权扬州大 学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。同时授权中国科学技术信息研究所将本学位论文收录 到 1 ) 个单位信息时，我们就用n 条平行边表示。 在图g = ( v ，e ) 中，s 表示信源节点。对每一个中间节点t ，我们用i n ( t ) 表示t 的所有 输入信道集合，o u t ( t ) 表示t 的所有输出信道的集合。这里我们用i n ( s ) 表示信源节点的 输入信道的集合，当然它们是没有起始节点的。事实上信源节点是没有输入信道的，只是 为了后面的讨论方便才引入砌( s ) 。故而我们称i n ( s ) 为虚拟信道。记彩= i i n ( s ) l 表述虚拟 扬州大学硕士毕业论文 信道的数量。 在网络中传输的数据一般用有限域f 中的元素表示。例如当传输的信息时一个比特时 我们可以设f = g f ( 2 ) 。一个消息一般包含c o 个数据。因此可以用一个缈一维的向量x f 口 表示。信源节点产生x 并传输一个符号到每一个输出信道。消息在网络中以z ( x ) f 在每 个信道e 上传输。一个非源节点并不需要接收到信源发出的消息x 的全部信息。它将从输 入信道接收的所有信息进行编码再通过输出节点发送出去。一个网络编码被网络中节点的 编码函数所惟一确定。 下面我们给出网络编码的两种定义方式。 定义i i ( 无圈图上网络编码的局部描述) 9 】设f 为一有限域，国为一正整数。一个无圈 图上的缈一维f 一赋值的网络编码由局部编码映射危构成。 元：f 阳) i 专f ， 恕对应于网络中的每一个节点t 和e o u t ( t ) 。 由于该网络是无圈的，因此我们可以通过局部编码映射屯从信源节点开始往信宿节点 方向计算与每一个信道e 对应的z ( x ) 。当然上面的定义1 1 并没有明确的给出z ( x ) 的数 学性质。下面给出一个与定义1 1 等价的定义，根据该定义可以递归的得到z ( 功。 定义1 2 ( 无圈图上网络编码的全局描述) 9 设，为一有限域，国为一正整数。一个无圈 图上的彩一维f 一赋值的网络编码包含局部编码映射元：，陋( r m 哼f 并且对每一个信道e 有 全局编码函数：z ：，。哼，且满足下面的两个条件： ( 1 ) 对网络中的任意节点t e o u t ( t ) ，z ( 石) 是被( z o ) ，dei n ( t ) ) 所惟一确定的， 其中冠是映射( 五( x ) ，d 砌( z ) ) j z ( 功。 ( 2 ) 对于c o 个虚拟信道e ，全局编码函数z 将，。分别映射到缈个不同的坐标。 下面给出一个关于局部编码函数和全局编码函数的例子。 设x = ( 口，6 ) 为【口( 2 ) 】2 中的一个向量。图1 ( b ) 给出了一个2 一维2 元网络编码。其全局 编码函数如下： z ( x ) = 口其中p = o s ，s t ，朋和t y z ( 工) = 6 其中e = o s ，s u ，v w 和u z 李克荣：基于网络编码和h a s h 函数的一个保密通信方案 9 一 z ( 功= a o ) b 其中p = w x ，胛秘 其中o s 和o s 表示我们上面提到的虚拟信道。相应的局部编码核如下： 专汀( 口，6 ) = a ，七妇( 口，功= 6 七邢( 口) = 七矗( 口) = 口，毛啷( 6 ) = 局忆( 6 ) = b 尼麟( 口，b ) = a 0 6 ，焉w ( 口o b ) = 足如( 口o b ) = a 0 6 网络编码在物理实现时，在信道和节点上都会带来一定的时延。特别是节点要处理一 定量的数据，成为了延时的主要部分。在节点上采用易于用电路实现的编码方式成为了减 少延时的一个重要方向，而线性函数相对于其它映射函数来说更容易用硬件实现，因此采 用线性函数作为编码函数是有意义的。 1 3 线性网络编码及一般线性网络编码 一、线性网络编码 当定义1 2 中提到的全局编码函数z 是线性的时候，它对应了一个缈一维列向量z 使得 z ( 工) = x z 。其中x 表示信源产生的缈一维列向量。相应的，对于局部编码函数厄， e e o u t ( t ) ，同样存在一个i 砌( 丁) | _ 维的列向量t 使得乞( 工) = y 也，这里y f 陋刊是节点t 接收到的信息组成的一个i 砌( r ) i - 维行向量。在一个国一维f 赋值的无圈通信网络中，如果 所有的局部编码函数都是线性的，由于全局编码函数是由局部编码函数构成的，则其也是 线性的。 如果存在节点t 使得d z n ( r ) ，e o u t ( t ) 。则称有序边对( d ，e ) 为邻接边对。下面系 统的阐述局部编码函数和全局编码函数都是线性函数的线性网络编码。与上- - + 节中定义 1 1 和定义1 2 类似，这里关于线性网络编码的描述也有局部描述和全局描述两种方式。 定义1 3 ( 无圈图上线性网络编码的局部描述) 【9 】设f 为一有限域，国为一正整数。一个 无圈图上的国一维f 一赋值的线性网络编码机制如下：对于每一对邻接边( d ，e ) 存在一个标 量幻。与之对应，称之为局部编码核。同时在节点t 也存在局部编码核，为一个 l 砌( r ) i i 仇f ( d i 的矩阵砗= l 乃，已- j d 扬( n p m ，( r ) 。 需要注意的是，上面的定义中关于膨的定义已经在网络中默认以一种先后顺序。 定义1 4 ( 无圈图上线性网络编码的局部描述) 9 设，为一有限域，c o 为一正整数。一个 无圈图上的缈一维，一赋值的线性网络编码机制如下：对于每一对邻接边( d ，e ) 存在一个标 扬州大学硕士毕业论文 l o 量乞。与之对应，同时对每一条边e 存在一个缈维列向量z 满足下面的两个条件： ( 1 ) 正= 向，。厶，其中p d 眦( d ， ( 2 ) 对于所有的虚拟信道p z n ( s ) ， 正i e e i n ( s ) 构成向量空间f 。的基向量。 在上面的定义1 4 中z 也称为信道e 的全局编码核。设信源产生一个缈一维列向量x 。 节点t 接收到的信息为工z ，e e i n ( t ) 。节点t 还计算出z z 输出到相应的输出信道 e eo u t ( t ) 上去。通过下面的公式 z 正= x b ，p 厶= b ，“厶) 。 如果给出了一个无圈网络中网络编码的局部编码核，就可以根据上面的定义从信源向信宿 方向递归的计算出全局编码核。定义1 4 中的条件( 2 ) 给出了这种递归计算的边界条件。 例：在图1 ( b ) 中网络编码实际上也是一个线性网络编码。它在节点上的局部编码核为下面 给出的矩阵： k j = 三? ，k r = k 。= 。= 【】，盔靠= ： 。 相应的全局编码核如下： z = 小忙傩, s t , t w 玎， 李克荣：基于网络编码和h a s h 函数的一个保密通信方案 z = 0 正= 田 其中e = o s ，s u ，唧和u z ， 其中e = w x ，x y ，x z 和盯。 在图3 中标出了相应的局部编码核和全局编码核。 二、一般线性网络编码及其存在性 本章前面提到的在一些网络中间节点的编码方案必须遵守信息守恒的原则。网络中任 何非源节点集所能发送出去的信息，必须由这个非源节点集所接收到的信息得到。特别地， 网络中的任一个非源节点发出的信息必须由它接收到的信息得到。我们定义网络中从信源 节点s 发送到任一非源节点t 的最大流为m a x f l o w ( t ) 。由最大流最小割定理我们知道， 节点t 接收到的信息量不可能超过m a x r i o * * ( r ) 。同样的定义网络中从信源节点s 发送到 任一非源节点集p 的最大流为m a xf l o w ( o ) ，则节点集p 接收到的最大信息量不可能超过 m a x f l o w ( 鬈o ) 。 最大信息量的上界能否达到取决于网络的拓扑结构，维数缈以及编码方案。下面将介 绍在三种不同程度上达到最大信息量上界的三种线性网络编码。这里( ) 用来表示向量的线 性张成空间。 定义1 5 【9 】用z 表示无圈网络中缈一维f 一赋值的线性网络编码的全局编码核。记 巧= ( z ：p 砌( 丁) ) 。一个线性网络编码分别被称为线性组播，线性广播，线性散播如果 满足下面对应的条件： ( 1 ) d i m ( v r ) = 国，对于满足m a x f l o w ( t ) 国的非源节点t 。 ( 2 ) d i m ( v r ) = m i n w , m a x f l o w ( t ) ) ，对于每个非源节点t 。 ( 3 ) d i m ( ) = r a i n c o ，m a x f l o w ( f o ) ) ，对于每个非源节点集矽。 很明显，( 3 ) j ( 2 ) j ( 1 ) ，即线性散播必然是线性广播，线性广播必然是线性组播。反 之未必成立。但是线性广播，线性组播和线性散播并不是总是存在的。在给出它们存在性 条件之前，先介绍一般线性网络编码。 定义1 6 ( 一般线性网络编码) 【9 设，为一有限域，缈为一正整数。对于无圈图上的一个缈一 维f 一赋值的线性网络编码，设 q ，吃， 为网络中的任意m 个信道的集合，其中 勺伽f ( 乃) 。如果向量，厶，乞国) 是线性独立的，能够推出 塑州大学砸圭望些鲨塞 一旦 ( 以：de 砌( 乃) ) z ( k ：七拼( 1 ，z ) 则称这个线性网络编码是一般线性网络编码。 在定义1 6 中，假设所有的节点z 等价于一些节点t 。我们可以得到，如果一个网络编 码是线性网络编码，则对于节点t 的任何一个元素个数不大于d i m ( 巧) 的输出信道的集合， 其相应的全局编码核是线性独立的。特别地，如果i o u t ( t ) i d i m ( 巧) ，则节点t 的所有输 出信道对应的全局编码核实线性独立的。下面给出一般线性网络编码的存在性定理。 定理1 1 9 】对于一个无圈网络，如果有性域f 足够大的话，就一定存在一个缈一维f 一赋 值的一般线性网络编码。 在参考文献 9 】中以给出一个构造算法。 定理1 2 9 】一般线性网络编码一定是线性散播。 由前面的定义1 5 我们知道，线性散播一定是线性广播，线性广播一定是线性组播。 则结合定理1 1 和定理1 2 得到如下推论。 推论1 1 对于一个无圈网络，如果有性域f 足够大的话，就一定存在一个彩一维f 一赋值的 线性散播，从而也使线性散播和线性广播。 同样可以根据参考文献中给出的在单信源无圈图上构造一般线性网络编码的多项式时 间算法，推导出构造缈一维f 一赋值的线性散播、线性广播和线性组播算法。值得注意的 是，定理1 2 说明了一般线性网络编码一定是线性散播，反之未必，下面给出一个反例。 图4 是一个2 一维二进制的线性散播。但是并不是一般线性网络编码，因为信源节点的3 条输出信道中的有两条并不是线性独立的，与定义1 6 矛盾。 图4 李克荣：基于网络编码和h a s h 函数的一个保密通信方案 1 4 网络编码的主要构造方法及研究现状 1 3 网络编码根据节点的输入和输出关系可分为线性网络编码和非线性网络编码，根据编 码系数生成的随机性可分为随机网络编码和确定网络编码。下面介绍几种目前比较成熟的 单源无环组播网络的编码构造方法，其中分为集中式和分布式。 一、集中式网络编码 ( 1 ) 代数法 代数法实际上是通过对矩阵行列式的研究，来判断网络编码的存在性，并构造网络编 码的。代数法将构造网络编码的问题归结为求解系统转移矩阵的问题，通过寻找一组使行 列式不为0 的参数来求解网络编码。k o e t t e r 等人在文献 1 0 o e 给出了网络编码构造的代数 法框架，将系统转移矩阵m 分解为i 引个子矩阵m 。，鸩，m 1 7 1 ，通过构造一组参数使得 每个子矩阵的行列式不为0 ，从而得到网络编码的解。基于代数法的构造算法的优点是可 以借助比较成熟的矩阵理论来分析各种拓扑结构网络编码问题，其缺点是可扩展性差，计 算量大。 ( 2 ) 信息流法 信息流法主要是利用解耦技术，将网络编码问题分解为确定编码子图和给子图分配码 字两个子问题分别求解。s a g g i 等人 1 1 1 给出了网络编码的一个多项式时间复杂度的构造算 法。主要分为两个步骤：首先采用流算法为每个信宿找到从信源到信宿的n 条边部重叠的 路径的集合，然后采用贪婪算法对已知的边按拓扑顺序分配线性码，并保证任意信宿的n 条入边上的全局编码核线性独立，且能扩张成有限域，从而获得所需的网络编码。信息流 法的优点在于耦合的两个闯题可以通过成熟的优化理论中的分布式算法求解，难点在于保 证信宿所有入边上的编码向量都要线性独立。 ( 3 ) 其它方法 除了以上两类构造方法外，还有图染色法、矩阵满秩法、冲突图法等几种构造方法。 f r a g o u l i 等人 1 2 1 利用解耦技术获得网络的最小子树图，然后采用对图顶点染色的贪婪算法 给出单信源组播网络的网络编码解。文献 1 3 1 从构造混合矩阵满秩的角度求解组播网络的 网络编码，并给出了一种具有多项式时间复杂度的确定性构造算法。s u n d a r a r a j a n 等人 1 4 】 利用冲突图理论模型将网络编码问题转化为受约束的链路状态分配问题，并通过在冲突图 中寻找特殊稳定集的方法进行求解。该方法的一个缺点是随着字母表的增大，而引起冲突 图爆炸，导致求解困难。 扬州大学硕士毕业论文 1 4 二、分布式编码方法 ( 1 ) 确定系数构造法 文献 1 5 1 首先针对组播网络提出了确定系数的分布式网络编码算法，其核心思想是将网 络分解成多个子树，并保证每个子树的编码矢量属于其父树编码矢量的扩张空间，且任意 两个子树的共有信宿的编码矢量均线性无关。该方法具有很好的可扩展性，但并不是最优 的算法，所需要的字母表空间随节点规模呈线性增长 ( 2 ) 随机系数构造法 h o 等人 1 6 1 给出了一种随机系数的分布式网络编码算法，其编码系数从有限域中均匀 随机选取。该方法对线性相关的信源具有信息压缩作用，适用于链路动态变化的网络，如 节点可以在一定区域内自由活到的无线通信问题。当给定的字母表足够大时能够渐进达到 最大组播速率，具有很强的实用性。 经过近年来的发展，网络编码的理论研究已取得重要的进展，在应用理论和工程实践 方面正在蓬勃的发展。网络编码正广泛的应用于传感器网络 1 7 1 、p 2 p 网络【8 ，1 8 、a dh o e 网络 1 9 ，2 0 、分布式文件存储 2 l 】和网络安全等领域。随着对网络编码研究的深入，理论 和实践上的成熟，预计将来网络编码在电脑通讯、无线电通讯、以及其它各种通讯网络中 能得到广泛的应用。 1 5 小结 本章主要介绍网络编码的一些基本知识。首先介绍了网络编码提出的背景，及其优点。 接着分别给出了网络编码、线性网络编码和一般线性网络编码的定义并对相关知识作了简 单的介绍。本章还对目前存在的网络编码的构造方法以及网络编码的研究进展作了一定的 介绍。后面的三、四章正是对这些知识的深入及拓展得出的。 李克荣：基于网络编码和h a s h 函数的一个保密通信方案 2 保密通信 1 5 本章的主要目的是对密码学的相关知识作一个简单的介绍，并对后面要用到的各种数 学知识也傲了相应的引入。 2 1 密码学及其数学模型 密码学是一名古老而又年轻的科学。早在4 0 0 0 多年前，由于军事，外交，政治斗争的 需要，人们就已经开始将密码技术应用于军事和外交通信。斗争双方在信息的“保密 和 “破译”上斗争，促进了密码学的发展。随着现代通信网络和计算机技术的发展，社会的 信息化程度越来越高，信息的传输已经涉及到社会生活的各个方面，信息的安全和保密问 题成了人们关心的问题。 密码学的基本目的就是使在不安全信道中的两个人，通常简称为a l i c e 和b o b ，以一种 使他们的对手( 信道的窃听者) o s c a r 不能明白和理解通信内容的方式进行通信。其实这 样的不安全信道在实际生活中是存在的。例如电话线和计算机网络。a l i c e 发给b o b 的信 息，通常称为明文( p l a i n t e x t ) ，例如英文单词，数据和符号。a l i c e 使用预先商量好的密钥 ( k e y ) 对明文进行加密，加密后的明文称为密文( c i p h e r t e x t ) 。a l i c e 将密文通过不安全的 信道，即o s c a r 可以窃听到的信道传输给b o b 。o s c a r 可以知道信道中a l i c e 发送出来的明 文，但是由于他不知道密钥，从而也就无法知道其对应的明文。而由于b o b 知道密钥，则 可以用密钥对密文进行解密，从而得到明文，实现安全通信。 用数学的方式对上面描述进行描述，如下 定义2 1 一个密码体制是满足以下条件的五元组( p ，c ，k ，占，d ) 1 p 表示所有可能的明文组成的有限集。 2 c 表示所有可能的密文组成的有限集。 3 k 代表密钥空间，由所有可能的密钥组成的有限集。 4 对每一个k k ，都存在一个加密规则p r k 和相应的解密规则d x d 。并且对每对 e k ：p c ，农：c p ，满足条件：对每个明文石p ，均有d x ( 吼( z ) ) = x 。 定义2 1 中，最关键的性质是性质4 。保证了如果使用e k 对明文工进行加密得到密文， 则可以用相应的以对密文解密得到明文x 。 a l i c e 和b o b 通过下面的方法使用一个特定的密码体制。首先，他们随机选择一个密钥 k k ，k 是通信能达到安全性要求的保证，因此绝对不能让o s c a r 知道。因此两人可以 扬州大学硕上毕业论文 1 6 在同一地点协商密钥，或者使用一个绝对安全的信道来单独传输密钥k 。假设a l i c e 想要 通过不安全的信道将消息发送给b o b ，不妨设此消息串为 工2 x , x 2 n 为正整数，x i p ，i = l ，2 ，刀。对每一个玉，使用加密规则对其进行加密。k 是预 先协商好的密钥。a l i c e 计算y i = ( 五) ，l f 刀。然后将密文串 y 2h y 2 y 。 通过信道发送给b o b 。b o b 接收到密文串咒儿以后，使用解密规则以对其进行解密。就 可以得到明文串x , x 2 毛。下图5 具体描述了一个保密系统的通信模型。 图5 保密系统模型 从上面的说明很容易看出，用来加密的加密函数必须是个单射函数，否则将会给解密 带来很到的麻烦。例如，如果 y = ( 五) = ( 恐) ，r x , x 2 。 则b o b 无法判断y 是由五还是恐生成。如果p = c ， 则具体的加密函数就是一个置换。 即加密函数仅仅是对明文空间里面的元素重新进行排列。 2 2 密码分析 这一节对密码分析( 即对密码体制的攻击) 作一个简单的介绍。 一般我们都是假设对手o s c a r 是知道a l i c e 和b o b 在通信时所采用的密码体制的，通常 把这一假设称为k e r c k h o f f 假设。确实，如果o s c a r 不知道a l i c e 和b o b 在通信时所采用的 密码体制的话，完成密码的分析将会更加困难。但是不能将密码体制的安全性建立在对手 o s c a r 不知道所采用的密码体制这种不确定的假设之上，因此一般都是在k e r c k h o f f 假设之 李克荣：基于网络编码和h a s h 函数的一个保密通信方案 1 7 下进行问题的讨论。 密码分析就是在不知道密钥的情况下，试图通过密文y 获得关于明文x 的信息。一般 情况下，我们也假设对手的目标是正在使用的密钥k 。这样难度更大，但一旦获得，将会 给以后的破译工作带来很大的方便。意义更大。 根据对手所拥有的信息，我们将攻击模型主要分为一下几种： 唯密文攻击( c i p h e r t e x to n l ya t t a c k s ) ：对手只拥有密文串y 。 已知明文攻击( k n o wp l a i n t e x ta t t a c k s ) ：对手拥有明文串及其对应的密文串y 。 选择明文攻击( c h o s e np l a i n t e x ta t t a c k s ) ：对手可获得对加密机的临时访问权限，这 样他可以选择一个明文串x ，并可以获得相应的密文串y 。这样对手就可以选择特定的x 去加密，进而能得到更多的关于k 的信息。 选择密文攻击( c h o s e nc i p h e r t e x ta t t a c k s ) ：对手可获得对解密机的临时访问权限，这 样他可以选择一个密文串y ，并获得相应的密文串x 。 很明显，唯密文攻击时最难的，对手所知道的信息最少。上面四种攻击方式的攻击强 度是递增的。通常我们说一个密码体制是安全的，是指在前三种情况下是安全的。 具体的讲，密码分析的主要步骤为：分析、推断、假设和证实。 2 3 密码的安全性 这一节我们先简单介绍几种评价密码安全性的不同方法。然后着重介绍与最后一种评 价方法相关的完善保密性。 计算安全性( c o m p u t a t i o n a ls e c u r i t y ) 这种度量涉及的是破译一个密码体制所做的计算上的努力，如果使用最好的的算法破 译一个密码体制至少要进行n 次操作，n 是一个非常大的数字。即用现在的或将来可得到 资源在足够长时间内都不能得到密钥k 。我们可以定义这个密码体制是计算安全的。但是 目前没有一个已知的密码体制在这个定义下是安全的。在实际中人们总是通过几种特定的 攻击类型来研究计算上的安全性，例如穷尽密钥攻击。但是这并不能保证没有比其它更好 的攻击类型。在更好的攻击类型下，这种体制也是安全的。 可证明安全性( p r o v a b l es e c u r i t y ) 另一种方式是通过归约的方式为安全性提供依据。把密码体制的安全性归约为某个被 认为困难的经过深入研究的数学问题。即如果能用某个具体的方法破译一个密码体制，那 么这个困难的数学问题就可以被解决。而后者往往是很难解决的，那么就等价于这个密码 扬州大学硕士毕业论文 1 8 体制很难破译。例如，可以证明这样一类命题：如果给定的整数n 是可以分解的，那么给 定的密码体制就是安全的。我们称这种类型的密码体制是可证明安全的。但是，这往往只 能说明密码的安全是和某一个问题相关的，并没有完全证明是安全的。这和证明一个问题 是n p 问题类似：证明给定的问题和其他的n p 问题的难度是一样的，但并没有证明这个 问题的复杂程度。 无条件安全性( u n c o n d i t i o n a ls e c u r i t y ) 这种度量考虑的是对攻击者o s c a r 的计算量没有限制时的密码体制的安全性。即使提 供了无限的计算资源，也是无法被攻破的。我们定义这种密码体制是无条件安全的。可以 证明一次一密对于唯密文攻击是无条件安全的。因为对手即使获得密文的很多信息，具备 无限的计算能力，仍然无法获得关于明文的任何信息。 如果一个密码体制对于唯密文攻击时无条件安全的，我们称该密码具有完善保密性 ( p e r f e c ts e c r e c y ) 。通俗的讲，完善保密性就是说o s c a r 不能通过观察获得明文的任何信 息。可以用概率分布中的术语，给出数学上的精确定义。 定义2 2 一个密码体制具有完善保密性，如果对于任意的x p 和y c ，都有 p r ( xij ，) = p r ( x ) 。也就是说，给定密文y ，明文x 的后验概率等于明文x 的先验概率。 对于任意固定的x p 。对每一个y c ，我们有p r ( x i y ) = p r ( x ) 0 。因此，对于每一 个y c ，一定至少存在一个密钥k 满足e r ( x ) = y 。这样我们就有冈l ci 。在任意一个密 码体制中，因为加密函数都是单射。一定有i c l - - i p i 。当冈= l c i = i p i 时，s h a n n o n 最早提出 了一个关于什么时候能取得完善保密性的很好的性质。 定理2 1 【4 1 】假设密码体制( p ，c ，k ，g ，d ) 满足i 厌i = i c i = i p i 。该密码体制是完善保密的， 当且仅当每个密钥使用的概率都是1 i ( i ，并且对于任意的x p 和y c ，存在唯一的密 钥k 使得e r ( x ) = y 。 个著名的具有完善保密性的密码体制是“一次一密”密码体制。该体制最先由由 g i l b e r t v e m a m 于1 9 1 7 年用于报文消息的自动加密和解密。“一次一密”密码体制虽然很多 年来被认为是不可破解的。但是一直都没有严格的数学证明，直到s h a n n o n 在3 0 年后提 出完善保密性后才得到严格的证明。一次一密密码体制的具体描述如下。 定义2 3 4 1 】一次一密密码体制 假设刀l 是正整数，p = c = k = ( z ：) ”。对于k ( z ：) ”，定义( 工) 为k 和x 的模2 的向 量和( 或者说是两个相关比特串的异或) 。因此，如果z = ( ，x 2 ，吒) 并且 k = ( k s ，k 2 ，k n ) ，则 李克荣：基于网络编码和h a s h 函数的一个保密通信方案 1 9 气( 功= ( x t + k ，恐+ 墨，+ k ) m o d 2 解密时与加密一样的。如果y = ( y 1 y 2 ，以) ，则 或( x ) = ( y l + k s ，咒+ 如，只+ e ) m o d 2 需要说明的是，一次一密具备完善保密性这一性质，为本论文后面章节中所构建的加 密体制具备完善保密性提供了保证。下面是关于一次保密性具备完善保密性的证明。 定理2 2 “一次一密”密码体制具备完善保密性 证明：我们假设密文序列，消息序列，密文序列都是产生于( z ：) 4 。先对所要用到的记号作 一个说明 x ：a l i c e 发出的明文序列， y - b o b 收到