无线传感器网络对称密钥建立方案

每一个节点 u 从 K 当中选出一个大小为 m 的子密钥池 Ku ， 并计算每个节点对应的多项式片段 gu ( y ) = f (u, y ) 。最后，对 于任何一个节点 u，密钥部署服务器将 idu 、 gu ( y ) 以及 Ku 下 载到其中。 共享密钥发现阶段 节点部署完成以后，节点首先进行邻居发现。依据节点 的邻居信息，节点为自身携带的密钥池中的每个密钥计算密 钥 id。对于任意 2 个相邻的节点 u 和 v，其各自计算密钥 id 的算法如下： 3.2
Symmetry Key Establishment Scheme for Wireless Sensor Network
XU Liang1, MA Xing-po2, ZHANG Ling1
(1. Department of Information Science and Engineering, Hunan First Normal University, Changsha 410205, China; 2. School of Information Science and Engineering, Central South University, Changsha 410083, China) 【Abstract】The special characteristic of Wireless Sensor Network(WSN) asks the key establishment scheme for WSN to be secure and effective. According to the past research, the key-pool based key establishment scheme is fit for WSN. However, the secure link connectivity of WSN is not so good. The symmetric pair-wise key establishment scheme based on the bivariate polynomial can get a high secure connective link rate, but it does not secure enough. Based on the two schemes, a new key establishment scheme is presented. Analysis and simulation results show that this new pair-wise key establishment scheme makes much more improvement than the classical pair-wise key establishment scheme on the security, the connectivity, the scalability, the effectiveness and so on. 【Key words】key-pool; pre-allocation scheme; bivariate polynomial; Wireless Sensor Network(WSN) DOI: 10.3969/j.issn.1000-3428.2011.08.039
无线传感器网络对称密钥建立方案
许 亮 1，马行坡 2，张 玲 1
(1. 湖南第一师范学院信息科学与工程系，长沙 410205；2. 中南大学信息科学与工程学院，长沙 410083) 摘 要：传感器网络的固有特点要求密钥建立方案既要达到一定的安全性标准又要高效。基于密钥池的密钥预分配方案虽然比较适合无线 传感器网络，但节点的安全链路连通率不高。基于双变量多项式的密钥预分配方案具有高连通率的特点，但安全性存在缺陷。为此，将基 于多项式的密钥建立方案与基于密钥池的密钥建立方案相结合，提出一种新的密钥建立方案。分析和实验表明，该方案在安全性、安全链 路连通性、可扩展性、有效性等方面和现有一些典型方案相比有较大的提高。 关键词： 关键词：密钥池；预分配方案；双变量多项式；无线传感器网络
f ( x, y ) = ∑ aij x i y j
i , j =0 t
双变量多项式密钥预分配方案
系数 aij (0 ≤ i, j ≤ t ) 随机取自于有限集 GF (Q) ，Q 是能够 足够容纳一个加密密钥的大素数。双变量多项式有一个对称 性质：
f ( x, y ) = f ( y , x )
对于任意 2 个相邻节点 A 和 B，只要这 2 个节点知道彼 此的 id，就可以利用双变量多项式的这一对称性质建立对称 密钥。双变量多项式密钥预分配方案可以保证密钥很高的联 通概率却不能保证密钥的安全性，因为当网络中有 t 个节点 被捕获时，所有密钥都被泄露。
概述
钥预分配方案相结合， 提出一种新的高效的密钥与分配方案。
2
多项式密钥预分配方案首先由文献 [5]提出，主要思想是 在传感器节点布置之前由密钥发布服务器为每一个节点分配 一个 t 度多项式片段， 利用该多项式片段以及其他 t-1 个节点 的 id，每个节点都能独立地计算出与其他 t-1 个节点的通信 密钥。 一个 t 度双变量多项式 f ( x, y ) 可以定义为：
第 37 卷 第 8 期 Vol.37 No.8 ·安全技术· 安全技术·
计 算 机 工 程 Computer Engineering
文章编号： 文章编号：1000—3428(2011)08—0115—03 文献标识码： 文献标识码：A
2011 年 4 月 April 2011
中图分类号： 中图分类号：TP393.08
i , j =0 k
新的密钥预分配方案
这一密钥作为这 2 个节点所在链路的通信密钥。如果一条链 路可以直接建立对称密钥，称这条链路为安全链路，否则为 不安全链路。共享密钥发现阶段任意 2 个相邻节点能够建立 对称密钥的概率为：
p connect = 1 −
) = 1 − m −1 M − m − i
∏
i=0
M −i
由于任意 2 个相邻节点都可以利用对称二元多项式建立 对称密钥，因此用对称二元多项式进行密钥建立可使传感器 网络的密钥连通概率是 1。虽然仅用对称二元多项式建立对 称密钥就可以达到百分之百的密钥连通率，但由于其抗捕获 能力差 ( 当网络中被捕获节点的书目小于对称二元多项式的 度时，非被捕获节点之间的对称密钥是安全的；而当网络中 被捕获节点的书目达到对称二元多项式的度时，整个网络的 对称密钥都会被揭露 )， 因此需要将其与基于密钥池的密钥预 分配方案相结合。 可以通过将这种新的无线传感器网络对称密钥建立方案 和经典的 EG 方案 [1]以及文献 [10]所提出的密钥预分配方案进 行对比说明这种新的密钥建立方案的优越性。依据文献 [1]， 在 EG 方案中，如果设定密钥池的大小为 10 000，则至少需 要在每一个节点中下载 75 个密钥才能保证节点之间的安全 连通概率为 50%。如果设定密钥池的大小为 100 000，则至 少需要在每个节点当中下载 250 个密钥才能保证节点之间的 安全链路连通概率为 50%。依据文献 [10]，在密钥预分配方 案中，为了使得网络的安全联通概率为 100%，每个节点至 少保存 150 个多项式片段，所消耗的存储空间比较大。 而在本文所提出的密钥建立方案中，即使在共享密钥发 现阶段没有建立对称密钥，也必然能够利用对称二元多项式 建立对称密钥，因此，这种对称密钥建立方案的连通概率为 100%。 4.2 存储开销分析 存储开销分析 每个节点需要存储的密钥材料包含 3 个部分： 节点标志， 大小为 m 的子密钥集以及二元多项式片段。假设节点标志占 a 个字节，子密钥集中每个密钥占用 b 个字节，对称二元多 项式片段 gu ( y ) 的系数平均长度为 c 个字节， 对称二元多项式 度为 t，密钥材料所占节点空间为 Total，则： Total =a + m ×b +c × t 由于部分节点在第 2 阶段便可与所有的邻居节点建立对 称密钥，下载在其上的对称二元片段会被删除，并且在第 2 阶 段所计算出来的密钥 id 也将会被删除，因此节点的最大存储 开销为 Total。 4.3 开销分析的 开销分析的计算 为了计算密钥 id，每个节点需要进行 m 次伪随机函数运 算。如果节点邻居的平均个数为 d，则每个节点需要进行 m× d 次伪随机函数运算。文献 [2]指出由于伪随机函数运算的高 效性，这些计算开销都是可以忽略的。部分节点由于在第 2 阶 段没有与其所有邻居建立对称密钥，因此需要利用对称二元 多项式建立对称密钥。 假设每个节点平均有 q 个邻居是利用对称二元多项式来 建立对称密钥的， 每次二元多项式运算的计算复杂度为 O(t)， t 为对称二元多项式的度，则每个节点的平均计算复杂度为 O( q ×t)。
基金项目： 基金项目：湖南省教育厅科研基金资助项目(09C231) 作者简介： 作者简介：许 亮(1982－)，女，讲师、硕士研究生，主研方向：无 线传感器网络密钥管理；马行坡，博士研究生；张 硕士 收稿日期： 收稿日期：2010-10-22 E-mail：dysfxul@ 玲，讲师、
node u： for ( ∀ key∈KeyRingu ) do: generate keyid =PRF key (idu ⊕ idv ); add keyid corresponding to the key in its key ring; node v ： for ( ∀ key∈ KeyRingv ) do: generate keyid =PRF key (idu ⊕ idv ); add keyid corresponding to the key in its key ring;
116
计 算 机
工 程
2011 年 4 月 20 日
3
本方案分为 3 个阶段， 第 1 阶段为密钥材料预分配阶段， 第 2 阶段为共享密钥发现阶段，第 3 阶段为利用对称二元多 项式进行密钥建立阶段。 3.1 密钥材料预分配 密钥材料预分配是在节点部署之前由密钥部署服务器完 成的。首先，密钥部署服务器为每一个节点 u 分配一个唯一 的标志 idu ，并随机生成一个大小为 M 的密钥池 K 以及一个 对称二元多项式 f ( x, y ) = ∑ aij x i y j 。然后密钥部署服务器为