（计算机软件与理论专业论文）无线传感器网络中的密钥分配协议的研究.pdf

无线传感器网络中的密钥分配协议的研究 计算机软件与理论 研究生杜薇指导教师何明星教授 无线传感器网络w s n ( w i r e l e s s s e n s o rn e t w o r k s ) - - 般是由大量体积小，价 格便宜，仅依靠电池供电的具有数据处理、传输以及存储和计算能力的专用传 感器节点( s e n s o rn o d e ) 和功能相对强大的基站( b a s es t a t i o n ) 所组成的网络。传 感器节点大多被部署在无人照看地方或者区域，很容易受到监听和物理俘获等 攻击，保证无线传感器网络的安全性更是应该首先考虑的问题。由于无线传感 器网络所固有的特点，例如受限的计算、通信、存储能力等，使得传统的密钥 分配技术很难直接运用于传感器网络中，因此应采用新的适合于无线传感器网 络的密钥分配协议，同时也应使其具有容侵的特性。 本文首先提出的一种新的适用于无线传感器网络的密钥预分配n r k p d 协议。n r k p d 协议主要将密钥演化的概念运用到密钥预分配协议中。在直接 对密钥建立阶段后增加了密钥环演化阶段。这样，每个节点在完成直接对密钥 建立后，演化密钥环上的每一个密钥，并删除之前的原始密钥。这样，即便节 点被敌手物理俘获时，也能够在很大程度上防止密钥池里的密钥泄露，从而大 大降低了由于节点被敌手俘获而对其他安全的网络路径造成的影响。 由于无线传感器网络的不稳定性，如网络延迟等原因，拥有自愈能力的密 钥分配协议在无线传感器网络中显得十分重要。本文分析了现有的两种存储量 为常数的自愈密钥分配协议：d u t t ae ta 1 协议【3 8 l 和r o b u s t 协谢删，并给出了对 d u t t ae ta 1 协议的两种攻击，并提出了对d u t t ae ta 1 协测3 8 】的一种修改协 m s h k d 协议。 此外本文在m s h k d 协议的基础上，给出了一种新的能够抵抗合谋攻击 的自愈密钥分配协议n s k dw i t hr r 协议。n s k dw i t hr r 协议不仅满足了基 本的安全属性，同时也能够有效防止敌手通过俘获一个撤销用户和新用户而获 得它们不是合法成员时的群会话密钥。 接着，本文又给出了一种新的存储量为常数的自愈密钥分配协议c s s k d w i t hr 协议。n c s s k dw i t hr 协议满足前向安全、后向安全，同时用户私钥 的使用周期不再受到限制。通过对比可以看出本文提出的n c s s k dw i t hr 协 议更高效和实用。 最后，利用c + + 环境，对本文提出的n c s s k dw i t hr 协议进行了实验仿 真，其运行结果表明了理论的i f 确性和可行性，证明了该协议是一个适用于 w s n 的高效、可行的自愈密钥分配协议。 关键词：密钥预分配，密钥演化，自愈密钥分配，无线传感器网络 n g r o u pk e y d i s t r i b u t i o np r o t o c o l s i nw i r e l e s ss e n s o rn e t w o r m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y m d c a n d i d a t e ：w e id us u p e r v i s o r ：p r o f m i n g x i n g h e w i r e l e s ss e n s o rn e t w o r k s ( w s n ) c o n s i s t so fal a r g en u m b e rs e n s o rn o d e s w i t h l i m i t e dp o w e r c o m p u t a t i o n ，s t o r a g ea n dc o m m u n i c a t i o nc a p a b i l i t i e s s e n s o rn o d e s c a nb ed e p l o y e di nm a n yd i f f e r e n tf i e l d ss u c ha sm i l i t a r y , e n v i r o n m e n t ，h e a l t h ， h o m ea n do t h e rc o m m e r c i a la r e a se t c m o r e o v e r , i ns o m ed e p l o y m e n ts c e n a n o s s e n s o rn o d e sn e e dt oo p e r a t eu n d e ra d v e r s a r i a lc o n d i t i o n s e c u r i t ys o l u t i o n s f o r s u c ha p p l i c a t i o n sd e p e n do ne x i s t e n c eo fs t r o n ga n de f f i c i e n tk e y d i s t r i b u t i o n m e c h a n i s m s i nt h i sp a p e r , w ef i r s ti n t r o d u c et h ec o n c e p to fk e yr i n ge v o l u t i o ni n t ot h ek e y p r e d i s t r i b u i o ns c h e m e w ea d dt h ek e yr i n g e v o l u t i o np h a s ea f t e rt h ed i r e c t p a i r w i s ek e ye s t a b l i s h m e n tp h a s et op r o p o s ea ne a s ya n dp r a c t i c a lr e s i s t e n ti a n d o m k e yp r c d i s t r i b u t i o ns c h e m e i n t h ep r o p o s e ds c h e m e ，e a c hn o d ee v o l v e st h ek e y si n i t sk e vr i n ga f t e rt h ed i r e c tp a i r w i s ek e ye s t a b l i s h m e n tp h a s e a n dd e l e t e st h e o r i 西n a lk e y si ni t st h ek e yr i n g t h i sw i l ld e c r e a s et h er i s ko fl e a k i n gt h eo r i g i n a l k e y si nt h ek e vp o o le v e ni ft h en o d e s w e r ec o m p r o m i s e db ya t t a c k e r , b e c a u s ek e y s i nk e yr i n ga r en o t 勰t h es a m ea st h eo r i g i n a lo n e si nt h ek e yp 0 0 1 b e s i d e s ，t h i s k e vr i n ge v o l u t i o np h a s ed o e sn o ti n v o l v ea n yn e t w o r k - w i d eb r o a d c a s tm e s s a g c f o r mb s ( b a s es t a t i o n ) , h e n c e ，i t i s e s p e c i a l l ys i m p l ea n d e f f c i e n t t h en e w p r o p o s e ds c h e m e a l s oc o m b i n e st h ep r o p e r t yo fe n e r g y e f f c i e n ti nt h ek e y d i s c o v e r yp h a s et or e a l i z en oc o m m u n i c a t i o n r e q u i r e m e n t i i i d u et ot h el o s s yo ft h en e t w o r k s ，s e l f - h e a l i n gk e yd i s t r i b u t i o ni si m p o r t a n t i n t h i s p a p e r ，w e a l s oa n a l y z et w oe x i s t i n gc o n s t a n ts t o r a g es e l f h e a l i n gk e y d i s t r i b u t i o ns c h e m e si nw i r e l e s ss e n s o rn e t w o r k s t h e n ，w es h o w t w oa t t a c k st ot h e d u t t ae ta 1 ，ss c h e m ea n dp r o p o s e am o d i f i e ds c h e m em s h k ds c h e m et o o v e r c o m et h et w of l a w s t h e n ，w ep r o p o s ean e ws e l f - h e a l i n gk e yd i s t r i b u t i o ns c h e m en s k d w i t hr r s c h e m et oi m p r o v et h em o d i f i e ds c h e m e t h em o s tp r o m i n e n tp r o p e r t i e so ft n en e w p r o p o s e ds c h e m ea r e 弱f o l l o w s ：a c h i e v i n gf o r w a r ds e c r e c y , b a c k w a r ds e c r e c y a 仰 r e s i s t i n gt oac o l l u s i o na t t a c k s ot h a t ar e v o k e du s e rw i t ht h ea s s i s t a n c eo ft h e n e w l yi o i n e du s e r sc a n n o tg e ta n yi n f o r m a t i o no fg r o u ps e s s i o nk e y s w h i c hi ti sn o t e n t i t l e dt og e t f u r t h e r m o r e ，w ep r o p o s ea n o t h e rn e ws e l f - h e a l i n gk e y d i s t r i b u t i o ns c h e m e n c s s k dw i t hrs c h e m e i ti s s h o w nt h a tt h ep r o p o s e ds c h e m er e a l i z e s t h e p r o p e r t i e s s u c h弱 c o n s t a n ts t o r a g e ，f o r w a r ds e c r e c y a n db a c k w a r ds e c r e c y m o r e o v e r t h ep r o p o s e ds c h e m eh a st h ep r o p e r t yo fl o n gl i f e - s p a no ft h e u s e r s p e r s o n a ls e c r e tk e y s s ot h eu s e r sp e r s o n a ls e c r e tk e yi s n o tr e s t r i c t e di naf i x e d s e s s i o ni nt h es e t u pp h a s ea n dt h eu s e r sp e r s o n a ls e c r e tk e yc a nb eu s e du n t i lt h e u s e ri sr e v o k e df r o mt h eg r o u p f i n a l l y , w ew i l lp r e s e n tt h a tt h ep r o p o s e ds c h e m e 1 s m o r ep r a c t i c a la n de f f c i e n tt h a ns o m ee x i s t i n gs c h e m e s l a s t l y , w eu s eo ft h ec + + c o m p i l e dl a n g u a g et op e r f o r mt h es y s t e mo ft h e n c s s k dw i t hrs c h e m e t h ee x p e r i m e n tr e s u l td e m o n s t r a t e st h a tt h ea n a l y s i s 1 s l i g h ta n dt h ep r o p o s e dp r o t o c o l i sf e a s i b l ea n de f f i c i e n ti np r a c t i c e k e y w o r d s ：k e yp r e d i s t r i b u t i o n ，k e ye v o l u t i o n ，s e l f - h e a l i n gk e yd i s t r i b u t i o n ， w i r e l e s ss e n s o rn e t w o r k s i v 1 1 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。除了文中特, 另t l d h 以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签名：永率k 口尸年咕月护6 r 新编移眈哆年乡月石同 7 4 1 2 授权书 西华大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，西华大学可以将本论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 印手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书； 2 、不保密彩适用本授权书。 ( 请在以上口内划) 学位论文作者签名：和薇 日期：吖口彳0 6 指导教师签名： 历t 砚陟 日期：砂叩钐 1 绪论 1 1 研究目的及意义 无线传感器网络w s n ( w i r e l e s ss e n s o rn e t w o r k s ) - - 般是由大量体积小，价 格便宜，仅依靠电池供电的且具有数据处理、传输以及存储和计算能力的专用 传感器节点( s e n s o rn o d e ) 和功能相对强大的基站( b a s es t a t i o n ) 所组成的网络。 节点将感知到的如温度、声音等信息通过安全的无线链路进行交换、融合，然 后再将数据与基站交换。基站再通过互联网或卫星与用户交流。无线通信技术 和微电子技术的进步，大大促进了无线传感器网络的研究和应用，例如在刑事 案件侦察、病人跟踪、环境检测、建筑物和地震检测以及军事等方面都具有广 泛的应用前景，引起了国内外广泛的关注和研究。传感器节点大多被部署在无 人照看地方或者区域，很容易受到监听和物理捕获等攻击，保证无线传感器网 络的安全性更是应该首先考虑的问题。由于无线传感器网络所固有的特点，例 如受限的计算、通信、存储能力等，使得传统的密钥分配技术都很难直接运用 于传感器网络中，因此应采用新的适合于无线传感器网络的密钥分配协议，同 时也应使其具有容侵的特性。 能否在无线传感器网络中安全地建立密钥极大地关系到网络通信安全。同 时也是密码学界的重要研究课题之一，意义重大。根据传统的通信群体的逻辑 结构的不同，存在两种基本的密钥建立协议：集中式的密钥分配协议和分布式 的密钥协商协议。由于传感器节点本身资源受限的特点，使得这两种协议很难 直接应用于无线传感器网络中，再加上传感器节点没有物理防护，节点遭受物 理俘获也是不可避免的。如何减少各种攻击对密钥分配协议的影响、特别是在 受到攻击的情况下仍然能提供必要而安全的密钥分配的核心服务是本项研究 的重点。这更加要求无线传感器网络的密钥分配协议具有自我诊断、恢复和重 构的自适应的容侵的能力【。 1 2 国内外研究现状 这一节中主要介绍了无线传感器网络中的密钥预分配协议和拥有撤销能 力的自愈密钥分配协议的国内外研究现状。 1 2 1 密钥预分配协议 近年来，无线传感器网络中的密钥分配的研究已经取得了许多进展。其中， 最原始的密钥预分配协议有两种。一种是网络中所有节点共享同一个主密钥， 需要的存储量很小，但一旦任何一个节点被俘获，就会暴露整个系统的主密钥， 从而导致整个网络被敌手俘获。尽管有文章提出可以采用物理防护的硬件存储 这个密钥，增强其安全性。但研究结果表明，这样不仅大大增加了成本和电源 的消耗，而且安全性也不一定得到保型引。另一种协议是网络中任意两个节点共 享一个对密钥。如果网络中有j v 个节点，每一个节点则需存储n 一1 个对密钥。 该协议安全性很强，但存储量太大，再者由于老节点中未存储新节点的对密钥， 很难解决新节点加入问题 2 0 0 2 年e s c h e n a u e r e ta 1 提出了随机密钥预分配1 9 j 协议( 简称为e g 协议) 。 其基本思想足在节点部署i j ，所有的节点随机地从一个很大的密钥池中选取一 部分密钥子集作为该节点的密钥环，并预先存储到节点中；在节点部署后，通 过某种方式与直接邻居互相发现彼此问共同捐j 有的密钥。每两个节点问以一定 的概率p 共享同一个密钥，并将共享的密钥作为直接邻居问的会话密钥。若直 接邻居间没有共享密钥，则需要通过已建立的安全链路建立会话密钥。 2 0 0 3 年c h a ne ta 1 等人在e g 协议的基础上提出了q c o m p o s i t e 协议1 1 0 l ，将 e g 协议中节点共享密钥的数量从一个提高到了q 个，提高了系统的抵抗力， 这对于防止小范围的节点俘获有所提高，但是随着被俘获节点的增多，网络中 剩余的部分受影响的范围将迅速增加。 同年d ue ta 1 将b l o o me ta 1 【1 2 l 的基于矩阵的单密钥空间密钥预分配协议扩 展为多密钥空间随机密钥预分配协议【1 1 l 。b l o o me ta 1 的单密钥空间协议1 1 2 】是 利用矩阵的方法让网络中任意两个节点都可以直接建立对密钥，利用对称矩阵 的特性，构造了一类新的会话密钥分发方式，并将其应用到传感器网络中，使 得节点能够与邻居中的任何一个节点独立计算会话密钥，即 k ft 彳o ) g ( j ) ；a f t ) - g a ) = k ，和k 豇作为节点f 和歹之间的对密钥。只 要受损节点数目不超过门限值a 时，便不会泄露其他节点的机密信息。d ue ta 1 提出的协议从某种意义上是对b i o t ae ta 1 协议和e g 协议的结合于扩展。每个 节点从密钥空间中随机选取t 个密钥空间作为自己的密钥子集。部署后，只要 2 两个节点的共享的密钥在同一个密钥池内就可以按照b l o me ta 1 的协议建立起 对密钥，从而大大增加了节点抗俘获的能力。同年l i ue ta 1 利用b l u n d oe ta 1 协谢1 4 j 中的对称二元多项式的性质厂“，) ，) ，厂( ，z ) ，提出了基于多个对称二元 多项式的随机密钥预分配协议i l 引。 同年l i ue ta 1 又在静态无线传感器网络里提出了基于地理信息的密钥预 分配协议【1 5 】，假设部署前节点的位置信息或者部署信息可以大概估算出来， 可以更加有针对性为节点预置密钥。 2 0 0 4 年又有许多基于地理信息的密钥预分配协议1 1 6 1 7 j 提出。2 0 0 5 年大量 研究指出基于预先知道地理环境的密钥预分配协议不可行，尤其是在战场上， 传感器节点是从飞机上撒下去的，很难确定节点准确的位置。 2 0 0 5 年c h e n gc ta 1 基于地理信息和双线性对技术提出了基于身份的密钥 预分配的协议【1 8 j 。该协议具有很强的容侵能力，同时也采用了可靠的节点认 证机制，但节点对资源的使用需求很高，制约了其应用范围。 z h ue ta 1 提出了一种能够大大降低传感器节点功耗的密钥预分配协议1 1 9 j 。 其主要思想是利用随机生成器根据每一个节点的身份为其选择密钥种子来生 成各自密钥环上的密钥。这样使得节点无法知道其他节点密钥环上的密钥，不 仅大大提高了协议的抗毁性同时节点在共享密钥发现节点也不需要进行通信， 大大减少了通信量。 r p b e r t o c ta 1 1 2 0 j 首次指出，大部分的密钥预分配协议在分析其抗毁性时， 只考虑“健忘的”敌手，它们只是随机选择所要俘获的节点。而实际中，光考 虑这样的敌手能力是远远不够的，于是首次提出了一种对“聪明的”敌手的定 义，即敌手根据之前从所俘获的节点中所获得的信息分析来确定这次所要俘获 的节点。此外，r p b e r t oc ta 1 在文献【1 9 趣2 1 l 的基础上还提出了e s p ( e f f c i e n t a n d s e c u r e p r e d i s t r i b u t i o n ) 协谢2 2 l 。在密钥预分配阶段，基站根据节 点的身份和密钥池中的密钥，采用单向杂凑函数进行计算，只有符合条件的密 钥才会被分配给节点。同时在共享密钥发现阶段，也只需要广播自己的身份， 不仅大大减少了通信量，而且减少了节点密钥环上密钥暴露的机会，获得了更 高的抗毁性。 还需要指出的是传感器节点容易被俘获，这是无法避免的。拥有容侵和容 3 错的性质是非常必要的。2 0 0 7 年，u ue ta 1 1 2 3 j 指出，如果敌人俘获了一个节点 就可以提取存储于该节点的所有数据。假设敌人俘获了节点c ，c 是一个帮助 节点a 和b 建立对密钥的中间节点，那么敌人俘获了该节点也就可以知道a 和 b 的对密钥。这样敌人只需俘获较小量的节点就可以很轻松的获得其他未被俘 获节点之白j 的对密钥，从而很轻松地获得所有网络中的对密钥。 在现存的密钥预分配协议中，几乎很少有协议考虑到对传感器网络中节点 密钥环上的密钥进行演化。这样，就很容易出现l i ue ta 1 所指出的状况发生。 综上所述，在无线传感器网络中的密钥分配协议不仅要满足基本的安全特 性，更应该考虑使其拥有容侵的能力，这也是本文研究的重点之一。 1 2 2 拥有撤销能力的自愈密钥分配协议 由于无线网络不稳定性，在群密钥更新时，存在网络延迟、中断或者：符点 电池耗尽等原因，使得一些节点无法及时或者无法收到密钥更新的消息。传统 的方法中，节点需要请求群管理员重新发送节点没有收到的广播，这样不仅增 加了群管理员的负荷，增加了通信量，同时由于节点与群管理员的频繁交互， 增大了节点暴露自己位置的机率。在2 0 0 2 年，s t a d d o ne ta 1 提出了具有密钥自 愈能力的密钥分配协测删。所谓自愈能力是指通过不可靠网络进行密钥更新 时用户离线或者丢失群组密钥时，用户不需要向群管理者请求重传，就能够独 立地恢复出丢失的群组密钥，这样降低了网络传输开销，降低了群管理者的负 荷等。2 0 0 3 年，l i ue ta 1 f 3 1 j 结合基于撤消用户多项式的个人密钥分配协议和 s t a d d o ne ta 1 中的思想，提出了一种新颖的密钥自愈的方法，在通信量和存储 量上都得到了大幅度的优化。2 0 0 4 年，b l u n d oe ta 1 瞄j 分析并证明了s t a d d o ne t a 1 2 1 l 中的定义存在问题，提出了新的定义并给出了在无条件安全下的证明， 同时又提出了一个满足新定义的新机制进一步减少了通信量。近年来，许多研 究者在文献【3 0 3 1 ，3 2 】的基础上又提出了一系列无线传感器网络中具有自愈能力 的密钥分配协谢3 8 ，4 1 _ 5 引，大多采用了单向密钥链的技术，在通信量上有大幅 度减少。但是只有少数协议的存储量为常数，此外几乎所有的适用于无线传感 器网络的自愈密钥分配协议都存在一个致命的问题，无法抵抗合谋攻击，即一 个已经撤销的用户和一个新加入的用户合作可以计算出它们均不是群成员时 4 的群会话密钥。 因此如何让协议的存储量是常数，如何在通信量尽可能小的情况下，让协 议能够抵抗合谋攻击也都是本文研究的重点之一。 1 3 本文研究特点 本文主要进行了两方面研究。第一是密钥预分配协议，第二是具有撤销能 力的自愈密钥分配协议。 本文首先提出了一种新的密钥预分配协议。主要是在将密钥演化的思想引 入到r p b c r t oe ta 1 密钥预分配协谢2 2 】中，在每次完成直接对密钥建立后，节点 都会对密钥环上的所有密钥进行演化。密钥环的演化，进一步提高了密钥的安 全性。该协议的通信量与r p b c r t oe ta 1 密钥预分配协测2 2 j 相同，在r p b e r t oe ta 1 密钥预分配协议【2 2 】的基础上进一步增加了协议的抗毁性，大大减少了节点俘 获对新的安全路径的影响。 其次，本文分析了目前的两种存储量为常数的自愈密钥分配协议d u t t ae t a 1 协议【3 8 l 和r o b u s t 协议【柏1 ，并针对d u t t ae ta 1 的自愈密钥分配协议【3 8 】，提出 了两种攻击，并进一步分析了其存在漏洞的根源，此外给出了一种对d u t t ae ta 1 协议的改进协议m s h k d 协议。 接着，本文又在m s h k d 协议的基础上提出了一种新的具有撤销能力且 能抵抗合谋攻击的自愈密钥分配协议n s k dw i t hr r 协议。因为在无线传感器 网络中，节点很容易被敌手物理地俘获，且节点一旦被物理俘获，敌手可以提 取存储在节点中的所有数据。一旦敌手能够同时俘获一个新加入的用户和一个 已经撤销的用户，便能够得到它们均不是合法用户的群密钥。而我们所提出的 一种能抵抗合谋攻击的自愈密钥分配协议正是针对这种攻击所提出的，在实际 中是非常有意义的。 此外，本文还提出了一种新的存储量为常数的拥有撤销能力的自愈密钥分 配协议n c s s k dw i t hr 协议。由于传感器节点的存储量是有限的，因此本协 议也是非常有用的。同时我们还对本协议与之前介绍的两种存储量为常数的自 愈密钥分配协议【3 8 锕】进行了对比。从中可以看出我们所提出的新的存储量为 常数的拥有撤销能力的自愈密钥分配协议无论是在安全性上还是在实际中均 5 更加实用。 最后，本文还针对n c s s k dw i t hr 协议进行了实验仿真。从实验结果可 以看出该协议的正确性和高效性。 1 4 内容组织 本文主体部分共分为八章： 第1 章主要介绍了本文的研究目的和意义，同时回顾国内外无线传感器网 络中的密钥预分配协议和自愈密钥分配协议的研究现状，最后还介绍了本文的 研究特点。 第2 章主要介绍了与本文相关的密码基础知识、密码体制、密钥管理等基 本概念。 第3 章介绍了本文针对分布式无线传感器网络提出的一种新的密钥预分 配n r l o d 协议，并对n r k p d 协议进行了分析。 第4 章首先介绍了两种存储量为常数的自愈密钥分配协议：d u t t ae ta 1 协 议和r o b u s t 协议。其次给出了对d u t t ae ta 1 协议的两种攻击，并分析了其存在 漏洞的原因。最后还提出了一种对d u t t ae ta 1 协议的改进协议m s h l 协议， 并给出了对m s h k d 协议的粗略的分析。 第5 章详细介绍了在m s h k d 协议的基础上所提出的具有撤销能力且能 抵抗合谋攻击的自愈密钥分配协议n s k dw i t hr r 协议。并给出了协议的安全 性分析，性能分析和对比。 第6 章介绍了本文提出的一种新的存储量为常数的拥有撤销能力的自愈 密钥分配协议n c s s k dw i t hr 协议。并给出了安全性和性能分析，此外还与 r o b u s t 协议进行了对比。 第7 章是算法实现。利用m i r a c l 库和c 语言在v c + + 6 0 中实验仿真了第 6 章所提出的n c s s k dw i t hr 协议。其运行结果表明本协议的可行性和高效 性。 第8 章对本文进行了总结，同时也对未来的研究目标进行了展望。 6 2 基本理论 本文所提出的密钥预分配协议，拥有撤销能力的自愈密钥分配协议主要 是以杂凑函数、秘密共享等密码原语作为基础。此外，还有大量的数学理论 为基础。在这一章，对本文所涉及的理论进行讲解，希望对后续几章的理解 起到一定作用。 2 1 密码体制 现代密码学形成于2 0 世纪7 0 年代，其重要标志有两个：美国制定并于 1 9 7 7 年1 月1 5r 批准公布了公用数据加密标准( d e s ) 【z 7 j 公钥密码体制的诞 型引。这两个事件在密码学历史上具有罩程碑意义。 1 8 8 3 年荷兰密码学家a k e r c h o f f 给出了密码学的一个基本原则：密码的 安全，从某种意义上来说，必须完全寓于密钥安全之中。如果以密钥为标准， 密码系统可以分为对称密码( 单钥密码) 和非对称密码( 公钥密码) 体系i 捌。 在单钥体制下，加密密钥和解密密钥是一样的，或实质上是等同的，这 种情况下，密钥就必须经过保密信道发送给收方。单钥密码的优点是：安全 性高，加密速度快。缺点是：随着网络规模的扩大，密钥管理成为一个难点； 无法解决认证问题；缺乏自动检测密钥泄露的能力。 在公钥体制下，加密密钥和解密密钥是不同的，此时就不需要安全信道 来传送密钥，而需要一个单向函数，用本地密钥发生器产生解密密钥即可。 公钥体制的优点是：密钥管理相对容易，拥有数字签名功能。缺点是：公钥 密码算法一般比较复杂，加解密速度较慢。 因此，网络中普遍采用公钥和单钥密码相结合的混合加密体制，即加解 密时采用单钥体制，而密钥传送时则采用公钥体制。这样既解决了密钥管理 的困难，又解决了加解密速度的问题。 密码体制模型如下： 明文消息空间m ：某个字母表上的串集 密文消息空间c ：可能的密文消息集 加密密钥空间k ：可能的加密密钥集；解密密钥空间k ：可 7 能的解密密钥集 有效的密钥生成算法：n 呻k k 有效的加密算法亭：m k c 有效的解密算法d ：c k 。_ m f i g u r e2 1t h em o d e l o fc r y p t o s y s t e m 图2 1 密码体制模型 对于整数1 ，双1 。) 输出长为，的密钥对( k e ，k d ) e kx k 。对t - k e e k 和肌 m ，我们将加密变换表示为：c 一瓦锄) ，意思为c 是m 在密钥妇下的加密； 将解密变换表示为：肌i 巩( c ) ，意思为r n 是c 在密钥崩下的解密。对于所 有的肌m ，k e k ，一定存在尉k 。：( 免) ) = m 。图2 1 是密码体制 模型的图示。 2 2 密钥管理 根据k e r c h o f f 原则1 4 5 1 ，一个密码系统的安全性完全取决于对密钥的保密， 而与算法无关，即算法可以公开。简单而言，不管算法多么安全，一旦密钥 丢失或出错，不但合法用户不能提取信息，而且可能会使非法用户窃取信息。 密钥管理的任务是处理密钥从产生到最终销毁的整个过程中的有关问 题，大体上讲，密钥管理包括密钥的产生、装入、存储、备份、分配、更新、 吊销和销毁等内容，其中分配和存储是最棘手的问题。一般地说，密钥可以 分为以下几种： 主密钥( 或基本密钥) ：是由用户选定或由系统分配的。可以在较长时间内 ( 相对于会话密钥) 由一对用户所专用的秘密钥。要求它既安全又便于交换，和 8 会话密钥起去启动和控制某种算法所构造的密钥产生器，来产生用于加密 数据的密钥流。 会话密钥：是一群通信用户在一次会话时所用的密钥。会话密钥的作用 是使主密钥不至于频繁地更换，有利于密钥的安全和管理。它的使用时间很 短，一般是会话结束后就销毁，这限制了密码分析者所能得到的同一密钥加 密下的密文量，并且即使丢失也不会造成大损失。通常会话密钥在萨式通话 前通过协议建立，从而降低了密钥的分配存储量。 密钥加密密钥：用于对传送的会话密钥进行加密时采用的密钥。这个密 钥一般是用户和丌p 之问共享，由于通常以会面的方式建立这样一个密钥， 所以花费很大，它应该长期使用，因此也称为长期密钥。 2 3 杂凑函数【3 】 现代密码学的一个基础要素便是密码散列函数。在很多非正式地情况下， 被称为单向杂凑函数( o n e w a yh a s hf u n c t i o n ) 。 杂凑函数可以分为两类：不带密钥的杂凑函数和带密钥的杂凑函数。前 者规定只有一个输入参数，即消息；后者则规定要有两个不同的输入，一个 是消息和一个秘密密钥。 定义2 1 杂凑函数( 在不严格的意义上) 是至少满足下列两个性质的函数h ： 1 压缩( 固定长度输出) ：h 将任意有限比特长度的输入x 映射为固定长 度为n 的输出h ( x 1 。 2 容易计算：给定h 和输入x ，容易计算出h ( x ) 基本性质： 1 抗原像：本质上对所有预先给定的输出，找到任何输入使得它的杂凑值 等于这个输出在计算上是不可行的，即任意给定的y ，其对应的输入是不知 道的，要找到原像x ，使得h ( x _ ) 一y 在计算上是不可行的。 2 抗第二原像：对任何确定的输入，找到任何与它有同样输入的第二个输 入在计算上是不可行的，即给定x ，求第二原像x = x 满足h ( x ) = h ( x ) 是计算 上不可行的。 3 抗碰撞：找到任何两个不同的输入x ，z ，使它们的输入是同一个值，即 满足h ( x ) 。h ( x7 ) 在计算上是不可行的( 注意输入是自由选择的) 。 9 其中，抗原像暑单向，抗第二原像鼍抗弱碰撞，抗碰撞暑抗强碰撞。 定义2 2 消息认证码( m a c ) 算法是一族被密码密钥k 定义的函数吃，它具 有以下性质： 1 容易计算：对于已知函数h k ，给定一个值k 和一个输a , x ，吃 ) 容易 计算出来。结果称为m a c 值或m a c 2 压缩：玩将任意的有限比特长度的输入x 映射为固定长度为甩比特的输 出h 10 ) 。 进一步，给定函数族h 的描述，对每个给定的允许值k ( 敌手不知道) ， 如下性质成立： 3 抗计算性：给定0 个或多个文本- m a c 对( 薯，吃( x i ) ) ，对任何新的输入 z 一( 包括对某个f ，可能有吃o ) ；以“) ) ，计算出任何文本m a c 对 ( 葺，吮 ) ) 是计算上不可行的。 2 4s h a m i r 的秘密共享方案 s h a m i r 3 9 1 利用有限域中的多项式方程，采用l a g r a n g e 插值多项式方案来 构造o ，以) 门限秘密共享方案。具体方案如下： n 代表参与者的最大数目。选择一个大素数p ，且p n 。其中k 表示需 要恢复的秘密。群管理员是秘密的分发者，p ( i = 1 ，刀) 代表每一个参与者， 鼍( f 一1 ，以) 是每一个参与者p 的身份。 群管理员随机选择一个t 一1 次多项式f ( x ) ，其中每一个系数a ；z 。， ( f 一1 ，t - 1 ) ： 厂o ) 一( 七+ 口l x + a z x 2 + + a t _ i x 卜1 ) m o d p( 2 1 ) 群管理员为每一个参与者只计算一个秘密的份额墨t ，“) m o d p ，其中 ia l ，n 。并通过安全信道将s 发给参与者只。 当群组中至少有t 个参与者出示二元组( t ，墨) ，并且利用拉格朗r 插值公 式，便可以恢复出秘密k ： 一露= 善ts ，j ：l t ；蠹m 咖 1 0 ( 2 2 ) 2 5 安全术语 群密钥分配协议中有一些重要的安全属性。( 假定m 轮的群密钥序列为 kt 慨帅k ，k 。) ) 【l o 3 6 】 ( 1 ) 群密钥安全这是群密钥分配协议中最基本的属性，该属性保证了 被动攻击者获得任何群密钥k ；r 是计算不可行的。 ( 2 ) 前向安全如果被动攻击者仅知道一组以前的群密钥 七。，k i ，他 不可能计算出任何群密钥k i ，这里的 i 。 ( 3 ) 后向安全如果被动攻击者仅知道一组群密钥 t ，k m ，k ，) ，他不 可能计算出第砖仑以前的任意z 轮群密钥k ，这里的， f l ，其中z 。 代表一个新部署的传感器节点与其所有一跳邻居建立对密钥所需的最长时问。 我们认为这种假设是合理的，因为敌手想要俘获一个节点必须首先采用物理的 方式获得该传感器节点，再从中提取存储于该传感器节点中的所有数据。此外， 在许多协议中，如文献【2 4 , 2 5 , 2 6 1 也都采用这种假设。 ( 5 ) 最后，假设每一个传感器节点与基站之间采用文献【1 5 l 中所提到的机制 与基站之间同步更新时间。这样每一个传感器节点都能知道当前部署到网络中 的新节点的所在组的身份标识。这种机制能避免与已被俘获的节点建立对密 钥，大大增加了系统的安全性。c h a k i be ta 1 1 2 4 1 中对这个机制进行了详细的描述， 本协议中不再赘述。 3 1 2n r k p d 协议的网络模型! 町 基站连续地向网络中部署大量的新节点，根据所部署的时间，可记为 g l ，g f ，q 小，g n ，其中甩代表所部署的最大轮值，s o g i g = 1 ，刀) 表示节点 s 。在第礴仑被部署到网络中。注意，每一个节点按照所部署的时间，属于且仅 属于一个部署组。 协议中，有且只有新部署的到网络中的传感器节点所发起的建立对密钥的 请求被视为是合法的。因为传感器节点在网络中是静止的，只有新加入的节点 才需要与其邻居节点建立对密钥。而新节点的邻居可能是与它一样刚被部署到 网络中的节点，也可能是之前部署到网络中的老节点。出于安全性的考虑，如 果之前部署到网络中的老节点要求建立对密钥，其请求均会被拒绝。 3 1 3n r k p d 协议的敌手能力 根据r p b e r t o e ta 1 1 2 2 l 所定义的两种类型的敌手。一种称为“健忘的”敌手， 另一种称为“聪明的”敌手。 定义l ( “健忘的”敌手) ：敌手发起新一轮攻击时，是随机选择所要俘获 的传感器节点，不会利用从已经俘获的传感器节点所得到的信息来确定将要俘 获的节点。 定义2 ：( “聪明的”敌手) ：敌手发起新一轮攻击时，不是随机选择所要 俘获的传感器节点，而是利用从已经俘获节点所得到的信息中来确定将要俘获 的节点。 3 2 术语与符号 在下面介绍的具体协议中将使用表3 1 中的符号： 3 3n r k p d 协议的具体实现 协议分成三个阶段：第一阶段密钥预分配，详细描述了在节点部署到 网络之前，基站如何为每一个传感器节点预先分配密钥信息；第二阶段直 接对密钥建立，详细描述了传感器节点部署到网络后，如何与其一跳邻居建立 直接对密钥，本协议在这个阶段还增加了密钥环演化环节：第三阶段密钥 路径建立，详细描述了对于那些无法直接建立对密钥的传感器节点如何通过其 他传感器节点的帮助，建立间接对密钥。 1 3 表3 1n r k p d 协议中的符号标记 t a b l e3 1t h en o t a t i o no fn r k p ds c h e m e 符号 含义 b s无线传感器网络中的基站 p由基站随机选择的一个人小为m 的密钥池 k ： 密钥池p 中的密钥 谴 第f 个密钥的标识 k e y , d ，所对应的密钥的值 s 4 无线传感器网络中的1 y 点，其中a 是1 ，点s 。的唯一的身份标识 q 第f 轮被部署剑网络中的1 了点所组成的集合 k二1 y 点s 。的密钥环，其中k = 忙? ， k1 ，点s 。的密钥环上的密钥 k e y ： 强所对应的在i l 6 i s 的密钥环上的密钥的值只有在1 7 点还没宵 进行对密钥环演化之前，满足坳? 一k e y 7 k e ) 7 ：b _ i i t j - 思o5 。与黾的密钥环中所共享的密钥 n 。由1 7 点s 。产生的一个