（通信与信息系统专业论文）无线传感器网络对密钥分配算法研究.pdf

杭州电子科技大学硕士学位论文 摘要 无线传感器网络( w n l e s ss e n s o rn e 觚o r k s ，w s n s ) 是一个由大量传感节点构成的无线 自组织网络。由于它是一个开放性网络，因此数据安全传输对w s n s 十分重要。数据的安全 传输必然涉及加解密技术，加解密中的密钥管理是w s n s 安全研究的重点。由于无线传感节 点的计算能力、存储空间、能量等受到限制，使得传统的密钥分配和管理方案不能很好地应 用于w s n s 。 基于部署知识，本文对无线传感器网络的对密钥分配算法进行了深入地研究，并做了以 下工作： ( 1 ) 基于网格模型，提出了e g k 方案。在d u 方案的基础上，e g k 方案对子密钥池的构 造进行了改进，提高了本地连接概率；同时利用哈希函数的不可逆性保护节点密钥信息，使 得链路安全性提高了近1 0 0 。 ( 2 ) 基于部署知识和双密钥池，提出了，d k 方案。该方案中的子密钥池由两种类型的 密钥池混合而成：一种是能保证任意一个被相邻三个蜂窝共享的密钥池，该密钥池在部署前 由服务器利用哈希函数将其扩展为2 倍；另一种是分配至各个蜂窝并保证互不重叠的密钥池。 改进的子密钥池构造方式能够提高本地连接概率。同时，服务器为每个蜂窝分配4 个随机数， 并保证任意相邻蜂窝存在一个共同的随机数。节点利用相应的哈希函数和随机数产生对密钥 以提高安全性。 ( 3 ) 在正六边形模型的基础上，利用素域中b l o m 矩阵和对称多项式的阈值特性及哈希链 的不可逆性，提出了l d k 方案。该方案在节点建立对密钥时，同一区域中节点利用分配 的哈希链值构造一系列b l o m 矩阵建立对密钥，并保证相同矩阵的个数不超过各其的阈值； 不同区域间相邻节点利用随机分配的密钥构造多项式，并以此建立对密钥，从而使得敌方难 以破解，增强了安全性。 ( 4 ) 为达到更高的本地连接概率和链路安全性，在正方形模型的基础上利用部署知识和 哈希链，提出了b d k h 方案。该方案在节点部署前由离线服务器构造一系列哈希链，并保证 同一个区域中节点对密钥的建立来自一对反向哈希链；不同区域中节点对密钥来自一对与部 署知识相关的哈希链，从而使得敌方无法破解，同时本地连接概率能够达到1 。 关键字：无线传感器网络，密钥管理，安全，部署知识，哈希函数 a b s t l 认c t w i r e l e s ss e i l s o rn e 眦o r k s ( w s n s ) a r es e l f - o 玛a 1 1 i z i n gn 咖o r k sw i n la1 a r g en u m b e ro fs e l l s o r n o d e s w s n sa r eo p e i ln e m o r k s ，s ot l l e i rs e 删晡t i e sa r ev e r yi m p o r t a n t t h ed a t as a f et r a l l s f 轩i s i n e 访t a b l yi n v o l v e di n b o t l lt 1 1 ee n c r y p t i o n 锄dt l l ed e c 唧t i o n 、7 i ，h i c hm a l ( ek e ym a i l a g 锄e n t c r u c i a l l yt ot h es 咖打t ) ro fw s n s d u et 0t h el i m i t e dc 0 叫 u t a t i o n ，s t o r a g es p a c ea l l de 1 1 e r g yi nt h e s e i l s o rn o d e s ，t h e 仃a d i t i o n a lk e yd i s t r i b u t i o n 锄dm a l l a g e m e i l ts c h 锄e sc a i ln o tb ed i r e c t l yw e l l a p p l i e di nw s n s h 1t h i s d i s s e r t a t i o n ，k e ym 锄a g 锄e 1 1 ts c h e m 嚣 b a s e do nd 印1 0 m e i l t k n o w l e d g e a r e i i l v e s t i g a t e d t h em a i n w o r ki ss 1 】1 l 珊a r i z e d 弱f o l l o w s ： ( 1 ) a ne i l l l a l l c e dk e yd i s t r i b u t i o ns c h e m ee g kw h i c hi sb a s e do nm e 鲥dm o d e l i sp r o p o s e d o nt 1 1 eb a s i so f 【ms c h e m e ，t i l ec o n s n l l c t i o no fs u b - k e y p o o l si l lt 1 1 i ss c h e m eh a sb e 朗i m p r o v e d w l l i c hi n c r e a s e sm ep r o b a b i l 时o ft h el o c a lc o n n e c t i v i 够a tt h es a n l et i m e ，o u rs c h e m eu s e sh a s h 如n c t i o n st 0p r o t e c tt h ek e yi n 南彻a t i o ns t o r 。di nt h en o d e s 锄dm a l ( et 王l es e c u r i t i e so ft h e1 i n k s i n c r e a s e da p p r o x i m a t e l ylo o ( 2 ) a ni m 即v e ds c h e i i l ek p d kb a s e d0 nd u a l - k e yp 0 0 1 si sp r e s 朗t e df o rp a i r - k e y s e s t a b l i s l l i n e n tb yu s i n gt h ed 印l o y m 锄tk n o w l c d g ea l l dt h ec e l l u l a rm o d e l e a c hs u b k e yp 0 0 1 i nt l l e s c h e l i l ec o n t a i l l st w ot ) r p c so fk e yp o o l s ：o n ed o u b l e db yo m i n es e e r ( u s i n gh a s hf u n c t i o n ) i s s h 锄觅b y3a d j a c e n tc e l l u l a rb e f o r ed 印l o y m e l l t ；t l l eo t l l e rd i s t r i b u t e dt 0e a c hc e l l u l a ri s n o n - o v 甜a p p i n 辱t h ei m p r 0 v e dc o n s t r u c t i o no f 毗k e yp 0 0 l sc a l li n c r e a s el o c a lc 0 皿e c t i v 咄 m e 柚w 量l i l e ，s e e rd i s t r i b u t e sf o l l rr 觚d o mn 硼曲e r sf o re a c hc e l l u l a ra 1 1 de i l s u r e s 锄ya d j a c e i l t c e l l u l a rs h a r i n go n e 啪d o mm m l b 既h lo r d e rt 0i l n p r o v et l l es e c u d t yo f l en 酣o r k s ，n o d e s 锄o n g n e i g h b o r i n gc e l l sa d o p th a s h 如n 以。娜a n dc o r r e s p o n d i n gm d o mn 硼曲e r st 0g e l l e r a t ep a i r - w i s e k e y s ( 3 ) b yu s i n gb 1 0 mm a t r i c s y l l l l l l e t r i cp 0 1 y n o m i a lt 1 1 r 镪h o l d si n 州m ef i e l d sa 1 1 dm e i 仃e v e r s i b i l i t ) ，o f h a s hc h a i n s ，k d d ks c h 锄eb a s e do nh e x a g o ni sp u tf o n ) l ，莉b e f o r ep a i r - w i s e k e y st 0b ee s t a b l i s h e d ，t 1 1 ed i s 倒b u t e db a s hc h a i nv a l u e sa r eu s e dt 0c o n s t r u c tan u m b e ro fb l o m m 删c e sw h o s en u m b e r sa r ei e s st h a nt 1 1 e i r 1 r e s h o l d s w eu s em e s em a 研c e st og e i l e r a t ep a i r - w i s e k e y s 锄o n gt l l en o d e si nt 1 1 es 锄er e 舀o n w h e nm en e i 曲b o r i n gn o d 鼯a r ei nt h ed i 缗j r e n tr e 百o n s ， m ep o l y i l 咖i a l sc o n s t n l c t e db ym d o m l y p r e d i s 倒b u t e dk e y sa f ee m p l o y c dt oe s t a b l i s hp a i r - 、i s e k e y s t 1 1 e s ed e s i 伊sm a k et l l es e c 嘶t yo ft h ep r o p o s e dk e yd i s t r i b u t i o ns c h e i l l eg r e a t l yi m p r o v e d a 1 1 dm a l ( ee n 锄i e sh a r d e rt ob r ea ：kt l l en e 栅o r k s ( 4 ) t oa c h i e v et h eh i 曲e rl o c a lc 0 衄e c t i v i t ya n dt h es a f 钉l i i l l ( si nw i r e l e s ss e l l s o rn e t w o r k s ，a 杭州电子科技大学硕士学位论文 s q l l a r e - b 舔酣s c h 锄eb d k h i sp r e s e i l t e db yu s i n gt l l ed 印l o y i i l e n tl ( 1 1 0 w l e d g e 锄dt h eh a s hc h a i l l s b e f o r et l l en o d e st 0b ed 印l o y e d ，t l l eo 们i n es e r v e rc o n s j 叽c t sam l m b e ro fh a s hc h a i l l s 觚d e i l s u r e su s i n gv a l u e s 五r o map a i ro fr e v e f s eh a s hc h a i n st oe s t a b l i s hp a i r - w i s ek e y s 锄o n gt l l en o d e s i i lt l l es 锄er e 百o n m i l e 锄o n gt l l en e i g h b o r i n gn o d e si nm ed i 伟舅a 呲r e 百o n s ，ap a i ro fh a s h c h a i l l sw i md 印l o y m 锄t r e l a t e da r e 锄p l o y e dt oe s t a b l i s hp a i r - w i s ek e y s t h e s ed e s i 印sm a l 【e e n e i l l i e sh a r d e rt ob r e a l ( t h en e 研o r k sa 1 1 de l l s l l r et l l ep r o b a b i l i 锣o fp a i r - 、析s ek e y s 鹤t a b l i s h m e i l t r e a c h 】o o k e yw o r l d s ：w i r e l e s ss e i l s o rn e t 、j i ，o r k ( w s n s ) ，k e ym a l l a g 锄e n t ，s e c u r i t y ，d 印l o y m e i l t k h o w l e d g e ，h a s hf 1 1 i l 嘶0 n i l l 杭州电子科技大学硕士学位论文 第一章绪论 无线传感器网络是由大量传感节点部署在目的区域，以完成系列感知任务的无线网络 【1 。5 1 。无线传感器网络技术涉及嵌入式、分布式、传感等众多技术【6 】。随着微电子技术、现代 网络和无线技术的不断发展，无线传感器网络的发展取得了长足的进步【_ 丌。在人难以接近的 环境中，利用无线传感器网络可轻松地获取各种侦察和监测信息并出现了许多应用，如战场 敌情监测、火灾情况监控、环境污染监测、智能家居、建筑物状态监控等 8 - 1 3 】。随着技术发 展和应用深入，无线传感器网络也逐渐成为学者研究的热点。 1 1 研究背景 1 9 7 8 年，由美国国防部资助卡耐基梅隆大学研究的分布式网络是无线传感器网络的雏形。 此后，无线传感器网络的理论研究和应用不断发展。9 0 年代初，无线传感器网络作为大学教 程进入了麻省理工学院、加州大学、康奈尔大学等高校。随后，加拿大、英国、德国、意大 利、日本等一些国家也纷纷加入无线传感器网络的研究行列，2 0 0 3 年开始开始有了一些丰富 的研究成果。国内方面，无线传感器网络的研究和应用还处于一个起步阶段，清华大学、南 京邮电、中科院、沈阳自动化研究所、软件研究所等单位院校近几年才开始对无线传感器网 络进行研究。可以预测，无线传感器网络发展前景十分良好，美国的商业周刊和技术 评论等期刊曾经将无线传感器网络视为2 1 世纪最具影响力的技术之一【1 4 】。无线传感器网络 技术在目前发展势头强劲的物联网中也占有重要的一席。自美国、中国相继提出“智慧地球” 和“智慧城市”的口号剧1 5 。1 引，无线传感器网络搭载物联网这辆快车将使其发展更为迅猛。 随着应用深入，数据安全传输成为制约无线传感器网络推广和商用的重要因素。保证数 据安全必然涉及加解密技术，如何分配和管理网络大量密钥是保证数据安全的关键。因此， 以提供安全和可靠通信为目标的密钥分配算法也就成为了w s n s 的研究重点。 1 2 研究对象 无线传感器网络是一个开放、暴露的自组织网络，这表明以无线电波方式传输的网络数 据能够被任何组织或个人监听，容易遭受各种攻击【1 9 。2 1 】。网络管理者通常使用多种技术手段 确保数据的安全传输：( 1 ) 加密技术；( 2 ) 密钥分配和管理技术；( 3 ) 节点认证技术。 节点认证技术通常需要使用各类加密手段，它与加密技术一样同样存在着密钥分配和管 理问题。直接破解加密数据或加密算法，攻击者需要付出大量精力、物力和财力，因此敌手 更倾向于从密钥分配和管理的漏洞方面直接获取密钥以达到窃取信息的目的。因此，密钥分 配和管理技术对于无线传感器网络的安全至关重要i 鹚，这是本文的主要研究对象。 1 3w s n s 的密钥管理协议分类 近年来，许多w s n s 的密钥分配和管理方案被提出。根据分配和管理方法的不同，w s n s 的密钥分配方案通常划分为如下三类【2 列： 杭州电子科技大学硕士学位论文 ( 1 ) 信任第三方方案( t r u s t e d s e r v e rs c h e m e ) ：节点依赖于网络中可信任的第三方协调和 分配网络中节点的密钥信息。 ( 2 ) 自我执行方案( s e l f - e n f o r c i n gs c h e m e ) ：节点依赖于非对称加密算法如d i f f i e h e l l m a n 或者r s a 交换彼此密钥信息。 ( 3 ) 预分配方案( p r e d i s t r i b u t i o n ) ：节点部署前由离线服务器分配一定的密钥信息给节 点，然后由节点按照定的方案建立对密钥。 方案( 1 ) 和( 2 ) 都是基于传统网络的密钥管理方案，对于无线传感器网络并不是十分适用： 方案( 1 ) 需要一个固定的设备担当可信任的第三方，但在覆盖区域广泛且危险的w s n s 网络中 难以找到一个适合的节点，因而方案( 1 ) 难以直接应用于w s n s 的密钥管理；而非对称加密算 法如d i f f i e h e l l m a n 等计算量大且能耗高，与w s n s 中节点的计算能力及能量受刚2 4 】的矛盾 也决定了方案( 2 ) 不能直接应用于w s n s 的密钥管理。普遍认为方案( 3 ) 是比较可行的无线传感 器网络密钥管理方案。 1 4 典型的密钥管理方案及分析 无线传感器网络的数据需加密保证其安全性【2 5 1 。对称加密和非对称加密是两类常见的数 据加密技术。非对称加密算法如r s a 2 7 1 、e c c 2 8 。2 9 1 具有计算量大，能耗高等特点，通常被 认为不适合直接应用于无线传感器网络中。因此，w s n s 普遍采用对称加密技术。较于花费 大量时间和资源破解截获的数据，攻击者更倾向于捕获加密密钥。因此，合理的密钥分配成 为无线传感器网络安全的重要因素。下面简单介绍目前几种典型的密钥管理方案。 1 4 1e s c h e n a u e r 随机密钥分配方案 2 0 0 2 年e s c h e n a u e r 和g l i g o r 最早提出了随机密钥预分配方案【3 川( e g 方案) 。该方案要求 网络中的节点在部署前由离线服务预先配置一些密钥信息，然后利用简单的共享密钥发现协 议来实现节点密钥的分配、撤销及更新。e g 方案包括三个阶段： ( 1 ) 密钥预分配阶段：设离线服务器构造一个大的主密钥池为s ，其大小为isl 。服务器 从s 中随机选取研个密钥( 朋 s ) 及相应标识并分配给节点。这种分配方式能够保证网络 中的邻居节点能以一定的概率建立共享对密钥； ( 2 ) 对密钥建立阶段：密钥预分配结束署后，节点开始广播所存储的密钥链标识( 即节点 存储的朋个密钥的标识) 。邻居节点根据接收的广播信息决定是否建立对密钥：若发现彼此存 在相同的密钥标识，则邻居节点从相同的密钥中任意选取一个密钥作为彼此的对密钥；否则， 进入第( 3 ) 步； ( 3 ) 路径密钥建立阶段：经过步骤( 2 ) ，有些邻居节点可能无法直接建立对密钥，这时可 以通过多跳的方式建立。 通过上面描述，可推出e - g 方案的本地连接概率玖和抗毁性鼠如式( 1 1 ) 和式( 1 2 ) 所示， 其中，本地连接概率是指任意两个邻居节点能直接建立对密钥的概率；抗毁性是指网络中有x 个节点被捕，将导致网络剩余链路被破解的概率。 2 杭州电子科技大学硕士学位论文 纠一褊 ：l 一堡创二型鲨 ( i s l _ 2 m ) ! ( i s l ) ! 纠- ( 1 一爵 ( 1 2 ) 1 4 2q - c o m p o s i t e 随机密钥分配方案 c h a r t p e r r i g s o n g 在e g 方案的基础上提出了g c o m p o s i t e 随机密钥分配方案【3 。该方案 将任意两个邻居节点的共享密钥从1 个上升到g 个。通过g 值的提高来弥补e g 方案抗毁性 差的缺点。若相邻节点的共享密钥数为t ( f q ) ，则将这t 个密钥按照一定的操作计算共享对 密钥。 g 值的选择是q - c o m p o s i t e 随机密钥分配方案的一个难题。文献 3 1 】表明，当网络中只有 少量的节点被捕获时，q c o m p o s i t e 方案的安全性优于e g 方案；但当网络中大量的节点被捕 获时，q - c o m p o s i t e 方案的安全性比e g 差，其理由如下：在相同的节点的本地连接概率条件 下，q - c o m p o s i t e 方案中节点所需存储的密钥数将迅速增加。因当敌手此捕获相同数量的节点 时，q - c o m p o s i t e 方案所泄露的密钥数也将迅速增加。 设lsi 为网络主密钥池大小，m 为节点密钥链大小，工为被捕获的节点的数量，则 q - c o m p o s i t e 方案中节点的本地连接概率凡和抗毁性见分别如式( 1 3 ) 和式( 1 4 ) 所示，其中式 ( 1 5 ) 表示任意两个节点共享i 个密钥的概率。 玩：1 一芝 l = o 二：) ( 2 2 ) 见2 耖”印等 p ( f ) ( 1 3 ) ( 1 4 ) ( 1 5 ) 1 4 3 多密钥空间随机密钥分配方案 w e n l i a n gd u 等人在b l o o m 的密钥预分配方案【3 2 l 的基础上结合随机密钥的思想，提出了 多密钥空间的密钥分配方裂3 3 1 。 b l o m 矩阵利用素数域g f ( q ) 生成对称矩阵a x g ，其中q 为支撑网络节点数量的最小素 数，g 是一个( 2 + 1 ) x n 的公开的矩阵( 可由范德蒙行列式构成，节点只需保保存相应列的第 酬竺几一 n 厂，一一 、iv一， m 驯仰c 杭州电子科技大学硕士学位论文 2 个元素即可推导出该列的整个元素) ，五为链路安全阈值，为网络节点数量。b l o m 矩阵具 有阈值特性：当被捕节点数量少于允时，网络链路仍然安全。假设a = ( d xg 1 r ，由d 是一个 ( 五+ 1 ) ( 兄+ 1 ) 的秘密对称矩阵可知，a x g 为一个对称的n x n 矩阵。网络中的节点通过对称 矩阵a g 来计算相应的对密钥。 文献 3 3 】的多密钥空间方案中，部署前由服务器产生缈个对称矩阵，并设其分别为 d i ，d 2 ，p ，并将墨= ( 口，g ) ，( i = l ，2 ，缈) 作为系列密钥空间，其中( 2 f 国) ；同时， 任意选取f 个密钥空间并计算4 = ( 口g ) r 。当密钥空间s 被节点_ ，( ，为该节点国) 选中 时，就将4 的第，行4 ( ，) 和g 的第，列g ( ，) 存入节点。在密钥协商阶段，每个节点广播自 己的仍、密钥空间索引和g 的列元素。假定f ，为邻居节点，当它们接收到广播信息并发现 具有相同的密钥空间4 时，则共享密钥可通过式( 1 6 ) 获得： 毛= 七，= 4 ( f ) g ( ) = 4 ( ) g ( f ) ( 1 6 ) 设网络中有x 个节点被捕获，则该方案中本地连接概率眈和抗毁性b 的推导如式( 1 7 ) 和式( 1 8 ) 所示。 p t 。= l 一黔箍 m 7 ， p 。 c a 毒( 九1 一广7 ，= 量+ i ( 1 8 ) 1 4 4 对称多项式随机密钥预分配方案 对称多项式随机密钥预分配方案【3 4 】在文献 3 5 的基础上进行了改进。文献【3 5 】是最早将多 项式引入无线传感器网络密钥分配的方案。令厂j ，) 为一个二元对称t 次多项式，由其对称 性可知f ( x ，y ) = 厂( y ，x ) 。多项式f ( x ，y ) 有良好的阈值特性，即当破解关于该多项式的数量低 于t + 1 个时，该多项式仍然安全。对称多项式随机密钥预分配方案的基本原理如下 部署前，离线服务器在素域g f ( q ) ( g 为支持网络的最小素数) 上生成i s l 个对称多项式 作为主密钥池s ，然后每个节点随机从s 中选取m 个多项式，并保存该多项式的关于该节点 仍的份额( 相当于存储了m ( t + 1 ) 个密钥) 。初始化时，节点广播自己的仍和所存储多项式的 d ，邻居节点利用共同的多项式和彼此皿建立对密钥。设耐和耐，分别为两个邻居节点u ， ， 的四，则u 和，的对密钥k 与，和u 的对密钥分别为= 厂( i d l ，娩) ，= 厂( 娩，i d 。) ，由 多项式的对称性有k = 。 设网络中有x 个节点被捕获，则该方案的本地连接概率仇和抗毁性见分别如式( 1 9 ) 和式 ( 1 1 0 ) 所示。 仇_ 1 - f j 啭孚 ( 1 9 ) 4 杭州电子科技大学硕士学位论文 纠一划tx 吲m ( ，一盯 ( 1 1 0 ) 1 4 5 基于部署信息的随机密钥分配方案 节点的部署位置可预测并且能应用于密钥分配方案。文献 3 6 】提出了基于部署位置的对密 钥分配方案，它要求每个节点随机的与自己最近的c 个节点建立对密钥。例如，服务器为节 点f ，分别分配密钥信息对( j ，岛，) 和( f ，j j f ) ，同时节点广播自己的肋。节点i ，j 根据接收的 密钥i d 决定共享对密钥。该方案的优点为：节点的共享密钥信息与位置信息进行了绑定，任 意节点被捕获均不会对其他的节点产生影响。 6 l 足i ai 墨l b i 最i j i a i & i ，ai 墨l 。 1r 6 i 疋i a i & i bj 疋i 图1 1 相邻区域的共享密钥池 文献 3 7 提出了一种基于部署知识的随机密钥分配方案。如图1 1 所示，将网络的部署区 域划分为m x n 个的正方形区域，主密钥池大小为lsi ，每个区域内的子密钥池大小为l 足l 。 根据区域划分位置不同，每个区域子密钥池与上下左右4 个区域子密钥池有共享的a i 足1 个 密钥，与对角线方向密钥池有共享的b 1 只1 个密钥，( 0 a ，b 0 2 5 ，4 a + 劬= 1 ) 。然后节点从 各自的密钥池中随机选取m 个密钥，类似e g 方案进行密钥建立。设网络中有x 个节点被捕 获，则方案 3 7 】的本地连接概率耽和抗毁性见分别为( 1 1 1 ) 和式( 1 1 2 ) 所示，其中五= 0 ，l ，a ，b 。 纠一鼍刚 只2 1 ( 1 一御m x 1 4 6 基于组合论的密钥预分配方案 ( 1 1 2 ) 杭州电子科技大学硕士学位论文 表1 1 6 q ( s ，t ) 参数 2 0 0 7 年，c a r n t e p e 把组合设计理论首次应用到确定性的无线传感器网络密钥预分配方案 【3 8 】中。文献 3 8 】讨论了三种常见的广义四边形g q ( s ，t ) ( g e n e r a l i z e dq u a d r a n g l e s ) ：g q ( q ，q ) ， g q ( q ，q 2 ) 和g q ( q 2 ，q 3 ) ，可分别构造b 条直线和，个点，其详细参数见表1 1 。g q ( s ，t ) 中的 点和直线是在素域f ( q ) 中构造的点和直线。g q ( s ，t ) 有以下两个性质：( 1 ) 在g o 中的任意一 个点都有t + l 条直线通过；( 2 ) 任意一条直线都通过j + 1 个点。 表1 2c q ( s 。f ) 各参数与k p s 参数映射 g q ( j ，f ) k p s 点集( s ) 点集大小( j _ l sj ) 直线集大小( 6 = ( f + 1 ) ( 础+ 1 ) ) 每条直线上的j + 1 点 密钥池( s ) 密钥池大小i s l 网络节点数( 规模) ( ) 密钥链大小m 为了便于网络密钥的构造，g q ( s ，t ) 方案中将g q ( s ，t ) 中的点视为一个密钥，而将直线上 的点视为一个密钥链。g q ( s ，t ) 各参数与预分配方案( k p s ，k e yp r e d i s t r i b u t i o ns c h e m e ) 参数 映射如表1 2 所示。由结合g q ( s ，t ) 的性质可知：网络中节点密钥链的大小为m = s + 1 ，并且 密钥链中的每个密钥均会出现在网络中其他的s + 1 个节点中。 g q ( s ，f ) 方案适合于大规模的传感器网络，但该方案在本地连接概率性能方面不理想。密 钥链中没有共同密钥的邻节点只能通过多跳的方式建立对密钥。设网络中有x 个节点被捕 获，则g q ( s ，f ) 方案中本地连接概率既和抗毁性见分别为式( 1 1 3 ) 和式( 1 1 4 ) 所示。 玩：坐业一丛生! ) ( 1 1 3 ) 纠一皆 ( 1 1 4 ) 1 4 7 基于栅格的密钥预分配方案 栅格密钥分配方案将部署区域划分为系列栅格。假定栅格的大小为n n ，网络节点数为 n ，则咒万。文献 3 4 】为栅格中的每一行和每一列分配一个二元对称多项式( 共2 ，1 个) ， 每个节点存储自己所属的栅格的行和列的2 个多项式，这样能够保证网络中所有的节点直接 建立对密钥，即节点对密钥建立概率为l ，但该方案计算开销大。 6 杭州电子科技大学硕士学位论文 署之初建立对密钥时，同一区域中节点利用分配的哈希链中的值构造一系列b l o m 矩阵来建 立对密钥并保证相同矩阵的个数不超过各自的阈值；不同区域中邻居节点利用随机分配的密 钥构造出的多项式建立对密钥。这种方法使得敌方难以破解，增强了抗毁性，同时提高了节 点的本地连接概率。 ( 4 ) 方案( 3 ) 能够保证同一小区内的节点直接建立对密钥，但是由于相邻小区间的节点采 用随机密钥的方式建立对密钥，因此相邻小区间的邻居节点仍有不能直接建立对密钥的可能。 针对方案( 3 ) 中相邻小区邻居节点的本地连接概率不高的问题，利用部署知识和哈希链的不可 逆性，提出了一种新的无线传感器网络的密钥分配方案。该方案在节点部署前由离线服务器 构造一系列哈希链，并保证同一个区域中节点对密钥的建立来自一对反向哈希链；不同区域 中节点对密钥来自一对与部署知识相关的哈希链，从而使得敌方无法破解，同时本地连接概 率能够达到1 。 1 6 本文的组织结构 第一章指出本文的研究背景、对象、w s n s 密钥管理的类型和当前几种经典的无线传 感器网络密钥分配算法，并详细分析了这些算法的两个重要指标本地连接概率和安全性； 接着对本文的主要贡献和创新点进行了论述。 第二章介绍基于网格的密钥分配增强方案，并对该方案的密钥分配过程和各个性能指 标进行了详细的分析及仿真。 第三章介绍基于部署知识和双密钥池的密钥分配方案，并对该方案的密钥分配过程和 各个性能指标进行了详细的分析及仿真。 第四章介绍基于部署知识和随机密钥分配方案，并对该方案的密钥分配过程和各个性 能指标进行了详细的分析及仿真。 第五章介绍基于部署知识和哈希链的密钥分配方案，并对该方案的密钥分配过程和各 个性能指标进行了详细的分析及仿真。 第六章总结本文的研究工作，并指出需要进一步完成的工作。 8 杭州电子科技大学硕士学位论文 第二章基于网格的密钥分配增强方案 绪论指出了几种经典的密钥分配方案，并介绍了基于部署信息的随机密钥分配方案，如 d u 方案【3 7 】。本章在d u 方案的基础上进行了改进，并利用哈希函数提出了一种基于网格的密 钥分配增强方案。 2 1 引言 目前广泛使用预分配技术对网络节点的密钥进行分配和管理，但是传统的预分配技术存 在一定缺点：( 1 ) 节点有限的存储空间存储了大量的冗余信息，浪费了存储空间；( 2 ) 在相同 节点被捕的条件下，节点存储的冗余信息使得网络链路更脆弱。 为此许多学者利用部署知识提出了系列密钥分配方案来弥补预分配技术的不足【4 1 。5 0 】。本 章在d u 方案的基础上提出了一种增强的无线传感器密钥管理方案e g k 方案( e i l l l a l l c e d 西d - b a s e dk e yd i s 仃西u t e ds c h e m e ) 。与d u 方案类似，该方案将部署区域划分为网格状，并对 网络密钥池的构造进行了改进；同时利用哈希函数的不可逆性对网格密钥池中的密钥信息进 行保护。2 4 小节的分析和仿真表明，与d u 方案和e g 方案相比，本章提出的方案能提高节 点的本地连接概率和链路安全性。 2 1 1 哈希函数 定义2 1 ( 哈希函数5 卜5 2 】) 哈希函数是一个输入数据到输出数据的不可逆映射。记 = 壳( 功 表示为哈希函数的生成过程，其中石为输入数据，五( ) 为哈希函数，j i l 为输出值。哈希函数具 有下面3 个性质： ( 1 ) 单向性：给定输出值j j l ，寻找石，使j j l ( x ) = | j l 在计算量上不可行。 ( 2 ) 抗弱碰撞性：给定x ，寻找j ，使y x 且j j l ( 工) = ( y ) 在计算上不可行； ( 3 ) 抗强碰撞性：寻找偶对( x ，y ) ，使 ( 石) = ( y ) 在计算上不可行。 2 1 2 节点部署模型 通常大规模网络中的节点是分批次进行部署的，且假设节点部署后静止不动。实际上同 一次播撒的节点成为邻居的概率远大于不同批次的节点，其部署位置近似服从二维高斯分布 【5 3 5 ( 称为部署知识) 。在逻辑上e g k 方案将不同批次节点的部署区域划分为网格。假设目的 区域面积为x 】，服务器将目的区域划分为膨个网格，记每个网格为q ， ( f = 1 ，2 ，m ，歹= l ，2 ，) ，服务器为每个节点分配一个唯一的标识泐，图2 1 所示为一个 4 4 的网络模型图。 2 2e g k 方案实现 表2 1 所示为本章常用的符号及所表示含义。e g k 方案的密钥分配过程有三个阶段：( 1 ) 预分配密钥阶段；( 2 ) 对密钥建立阶段；( 3 ) 路径密钥建立阶段。下面详细阐述这三个阶段： 9 杭州电子科技大学硕士学位论文 s s i j ，行 s i d 。 k 矿( 力 密钥池 子密钥池 节点密钥链长度 节点“的d 节点、1 ，的对密钥 对x 执行鼯次的哈希过程 i s i 密钥池s 的大小 i i每个钥池s ，的大小，其值均为i 疋i 圈珥密钥毛的 2 d 网格g ，的边长 “节点安全级别 灭节点发射半径 2 2 1 预分配密钥 2 2 1 1 密钥池构造 离线服务器随机产生一个主密钥池s ( 大小为lsi ) ，并为s 中的每个密钥分配一个唯一的 标识比。如不特别说明，本章中涉及分配给节点的密钥不仅包含密钥而且包括相应的标识 k i d 。 图2 1 节点部署模型 初始化时，离线服务器将为网格g ，构造相应的子密钥池& ，。墨，由其在网络中的相对 位置和主密钥池s 共同决定，其中i 墨。，i = i l ，f = 1 ，2 ，m ，_ ，= 1 ，2 ，。e g k 方案能够保证 两个相邻的子密钥池之间拥有一定比例的共享密钥，这样可以保证相邻网格间的邻居节点能 以一定的概率建立对密钥。设口为子密钥池重叠因子，o 口l 3 ，则子密钥池墨，的构造具 体方法有如下4 个步骤( 可参照图2 1 ) ： ( 1 ) 当f - 1 ，_ = 1 时，服务器随机地从s 中选择i 疋1 个密钥作为子密钥池墨i ，之后在s 中 删除s i 1 0 杭州电子科技大学硕士学位论文 ( 2 ) 当f _ l ，1 ，s 时，服务器随机地从墨，- 。中选取口l 1 个密钥，同时从s 中随机选择 ( 1 一口) i 爰1 个密钥作为子密钥墨。，之后从s 中删除这( 1 一口) i 1 个密钥，否则进入第( 3 ) 步； ( 3 ) 当l f 膨，歹= 1 时，服务器分别随机地从墨。j 和墨_ i ，+ 。中选取口l 1 个密钥，同时从 s 中随机选择( 卜2 口) l 1 个密钥作为子密钥池墨，之后从s 中删除这( 卜2 口) i 1 个密钥，否 则进入第( 4 ) 步； ( 4 ) 当l _ ， 膨，l j e g 。理由如下： ( 1 ) 当节点的本地连接概率风相同时，e g k 方案中节点所需存储的密钥数是最少的。 相应地，敌手捕获相同数量的节点时泄露的密钥数也最少。例如，陬= o 3 3 时，e g 方案 和d u 方案中节点存储的密钥数分别为1 7 9 和2 9 ，而e g k 方案仅需存储2 6 个密钥； ( 2 ) e g k 方案中使用哈希函数来保护节点密钥信息，相当于主密钥池大小扩大了一倍 ( 链路被攻破的概率公式如式( 2 8 ) 所示) ，这也增加了链路被攻破的难度。 o 钆 褥 饔 g 铤 铎 籍 瀣 撑 被捕节点个数工 图2 5 九= o ，3 3 被捕节点数与链路破解概率 1 6 杭州电子科技大学硕士学位论文 u q - 褂 鼙 g 督 铎 辎 密 撑 被捕节点个数石 图2 6几= o 5 被捕节点数与链路破解概率 2 4 2 存储空间分析 分析存储空间主要是指节点在一定本地连接概率下，节点存储的密钥的数量情况：当 节点的本地连接概率相同时，方案中节点所需存储的密钥数越少，则表明该方案中节点的 存储空间性能越有优势，反之，节点的存储空间性能越差。 子密钥池共享因子口= o 1 2 5 时，e g k 方案、d u 方案和e - g 方案中节点的平均本地连 接概率与存储密钥数的关系如表2 4 所示。表2 4 表明，当节点所需的本地连接概率相同时， e g k 方案中节点所需存储的密钥数在三个方案中是最少的。例如，当平均本地连接概率为 o 7 时，e g k 方案中节点只需存储4 8 个密钥，而d u 方案和e g 方案则分别需存储5 2 和 3 4 7 个密钥。因此，相同的本地连接概率时，e g k 方案的中密钥所占节点的空间在三个方 案中是最少的。节点存储空间方面，相较于d u 方案和e g 方案更优。 表2 4口= o 1 2 5 ，平均本地连接概率不同时，各方案中节点存储的密钥数 2 4 3 扩展性分析 利用网格模型，e g k 方案能够方便地实现网络扩展。假设扩展之前，部署区域的网格 数目为m ，扩展后的网格数为m ，主密钥池为s 。下面为子密钥池的扩展和新节 1 7 杭州电子科技大学硕士学位论文 点对密钥建立过程： ( 1 ) 扩展时必须保证子密钥池共享因子口和子密钥池的大小i i 不变，然后利用公式 ( 2 1 ) 计算出扩展的主密钥池s 的大小(