用辛几何构造传感器的密钥预分配方案

陈尚弟，文洁晶

（中国民航大学理学院，天津　300300）



用辛几何构造传感器的密钥预分配方案

陈尚弟，文洁晶

（中国民航大学理学院，天津300300）

摘要：密钥管理方案的设计是密码学中基本且十分重要的研究领域。密钥预分配是无线传感器网络中极具挑战性的安全问题之一，目的是为无限传感器网络设计一个新的密钥预分配方案。在借鉴Samiran Bag的密钥预分配方案和有限关联结构的基础上，基于有限域上的四维辛几何，获得了一个新的无线传感器网络密钥预分配方案。结果表明，本方案能够有效地提高网络的连通性，保证节点间均有共享密钥，从而提高了节点间的连通率。分析表明，与其它一些已有的密钥预分配方案相比，该方案具有良好的连通性和抗毁性。

关键词：无线传感器网络；密钥分配；密钥预分配方案；辛几何

近些年来，随着传感技术、计算机技术飞速发展与成熟，带动了信息科学领域中的一个全新的发展方向——无线传感器网络，即具有感知能力、计算能力和通信能力的微型传感器构成的网络。该网络在世界范围内得到应用，是传统学科与新兴学科交叉的结果。因此由这些微型传感器构成的无线传感器网络（wireless sensor network，W SN）引起了人们的极大关注。

无线传感器网络[1-2]是由大量体积小、成本低，具有感知能力、计算能力和通信能力的微型传感器节点构成的自组织、分布式网络系统。其目的是在感知、采集和处理网络覆盖的地理区域中协作地感知对象的信息，并发布给观察者。可广泛应用于军事中地形侦察、环境与能源的监测、医疗卫生领域护理和监护、交通运输中的管理和分派、日常生活中的智能居家、反恐斗争中信息的采集和火灾地震等诸多领域，具有巨大的实用价值和商业潜力，引起了国内外学术界广泛与高度的关注。随着无线传感器应用的普及，传感器网络的安全[1]显得日益重要，尤其是其中最基础和最关键的密钥管理问题。在传统网络中，密钥的管理已有许多国内外的学者和研究人员进行了探索并取得了许多重要的成果，但由于无线传感网络自身固有的特点，如无线传感网络中无线传感器的计算能力有限、可通信的物理范围较小、存储能力不强，缺乏节点部署的先验知识等，使得这些成果不能直接应用于无线传感网络。因此，密钥管理方案成为无线传感器网络安全的研究热点与难点。

在无线传感器网络中，经过反复的探索与研究，通常使用的是对称密码体质与密钥预分配机制实现安全的信息传递，在部署节点以前为其预分配若干密钥（通常称为密钥链），部署后，如果不同节点之间需要安全通信，则其可以通过使用共享的密钥来对信息加密，然后用同样的密钥对信息解密（如果没有共享密钥就需要建立密钥路径来实现安全通信）。目前已有很多无线传感器网络的密钥预分配的研究，包括不确定型随机分配密钥方案、随机型分配密钥方案的扩展以及之后出现的许多基于组合结构的确定型的密钥预分配方案，围绕共享概率、密钥路径长度指标、支持的网络规模、密钥安全强度等指标进行了大量有阶段性成果的工作。

由于无线传感器网络中节点的计算能力以及内存有限，所以公钥密码体制不适合无线传感网络（公钥密码体制在解密时计算量很大，消耗的能量和占有的内存也很大，故不适用于无线传感网络）。如果传感网络的每一个节点被分配N-1个密钥（其中N为传感网络节点的个数），虽然保障了每一对通信的节点都有共享密钥并且抗毁性与安全性达到最大，但是整个网络的节点个数N很大以至于需要的内存很大，因此这个方案不适用于无线传感器网络。如果传感网络的每一个节点都分配同一个密钥（即每一个节点分配一个密钥），这样虽然占用的内存最小，但是一个节点被捕获那么整个网络就不再安全，此方案的抗毁性及安全性太低，所以也不适用于传感器网络。Eschenauer L. 和Gligor V.[3]提出了密钥预分配方案。无线传感器的每一个节点在部署之前都分配给他们一些满足其内存的密钥，在通信的过程中他们彼此交换其密钥的ID选取共同的密钥，或者建立安全的通讯路径来进行安全通信。

使网络规模、节点内存及整个网络的连通性、抗毁性和安全性彼此之间相互制约，没有一个方案使他们都同时达到最大，所以近些年来许多学者都在探索和研究更好的密钥预分配方案。

1　相关成果叙述

根据给节点分配密钥方法的不同，无线传感器网络的密钥预分配方案有以下两种划分，即概率不确定型密钥预分配方案和基于组合结构的确定型密钥预分配方案。

概率型密钥预分配方案是一种基于求概率结果的密钥预分配模型，计算任意两个节点存在共享密钥的概率，并且这个值高于一定概率，进而使得整个系统的密钥共享图构成以一个确定概率连通的连成图。随机密钥预分配方案有以下两种：

1）Eschenauer等[3]提出了基本的随机密钥预分配方案，目的是达到在确保任意节点之间含有共享密钥的前提下，尽可能多的减少方案对节点资源的消耗。方案设计的具体过程如下：

a）密钥分发从一个较大的密钥空间选取一个密钥池S，并为每个密钥分配一个ID。在进行节点部署前，每个节点从密钥池中随机地选取k个密钥构成自己的密钥环，k大小的选择要保证每两个节点存在相同密钥的概率p大于预先设定的概率值。

b）密钥发现节点之间通信时，通过交换各自的ID来发现共享密钥。

c）密钥路径的建立在b）不成功时，需要通过与其地理位置上相邻节点经过若干次信息的传递建立一条间接连接两个通信节点的安全路径，然后进行安全通信。

在Eschenauer等[3]提出的随机密钥预分布模型方案中，两个节点之间共享密钥的概率p与密钥池的大小S及密钥链长度k之间的数学关系如下

2）在E-G方案的基础上，Chan等[4]对E-G方案的安全性进行改进，提出了q-composite密钥预分配方案，要求共享密钥数为q（q>1），此时两个节点之间共享密钥的概率p与密钥池的大小S及密钥链的长度k之间的关系如下

确定型密钥管理方案是节点的密钥链以某种确定的方式来设计，避免了随机型方案密钥分配盲目性的一种密钥预分配模型。通过合理组合结构可以设计的密钥链，可以充分利用节点存储空间，提高了节点之间直接通讯的概率。Camtepe等[5]首先将设计理论应用于确定型密钥预分配方案的设计，给出了基于SBIBD和广义四边形的密钥预分配方案，设计出的方案所含的节点数为n2+ n + 1，密钥链长度为n + 1，并且保障了每对节点之间都共享一个密钥，所得方案的连通概率比E-G方案更高，并且每个节点所含的密钥更少（即密钥链的长度更短）。Liu等[6]提出基于多项式的密钥预分配方案，Lee等[7]提出了基于横截设计的密钥预分配方案等，这些模型虽然能够有效建立密钥路径，实现安全通信，保证网络的安全运行，但无线传感器不同的节点间共享密钥概率很低，通信中资源消耗太大。夏戈明[8]提出了一种基于Hamand矩阵与SBIBD设计的密钥预分配方案，实现了对网络的连通，并且在一定程度上优化了对能量的消耗，但是支持的网络规模很小。

基于组合设计的确定性管理方案可以大幅度降低密钥环的存储空间，但大都存在构造困难、可扩展性问题。本文分为6个部分：①介绍了无线传感网络的实际应用背景及密钥预分配方案问题的提出；②介绍了已有的一些相关结果；③介绍了本文用到的一些相关理论知识；④利用辛空间给出了密钥预分配的组合方案，其中q是素数或素数的幂；⑤分析了所提出的方案，并与已有的方案进行安全性和连通性对比；⑥总结全文。

2　基础知识

2.1有限关联结构

通常用（P）表示与点P关联的区组集，用（x）表示与区组x关联的点集。因此（Pi）∩（P）j表示既与点Pi关联又与点Pj关联的区组集。通常以v表示点集的

对1≤i≤v，令ri表示中与点Pi关联的区组数；1≤j≤b，令kj表示中与区组xj关联的点的个数；对1≤i，j≤v，i≠j，令λi，j表示中同时与点Pi及Pj关联的区组数。ri叫做点P的重复度，kj叫做区组xj的长度，λi，j叫做Pi与Pj的相遇数，即

上述定义出自文献[9]。

2.2辛空间简介

定义2设Fq是q元有限域，q是一个素数的幂。令

有限域Fq上满足TKTT= K的2v×2v矩阵T的集合关于矩阵的乘法构成一个群，叫做Fq上的2v阶辛群，记作Sp2v（Fq）。即

证明设P0也是（m，s）型子空间，因辛群Sp2v（Fq）可迁地作用在同类型的子空间集合上，不妨设

由假设知P与P0是同类型子空间，根据可迁性得知，存在使得P = AP0T，可推出P0T = A-1P。

证明设Q是与P正交的（m'，s'）型子空间，则Q⊆P⊥。由定理1知，P⊥是（2v-m，v+s-m）型子空间，即求包含在（2v-m，v+s-m）型子空间中的（m'，s'）型子空间的个数，即为N（m'，s'；2v-m，v+s-m；2v）。

上述定理定义出自文献[10]。

3　密钥预分配方案构造

给定素数q，在Fq上的四维辛几何中选取包含一个固定一维子空间的二维子空间全体记为V。

参数的选择如下：

密钥链节点ni分配的密钥为包含Pi的所有（3，1）型子空间。每一个ni对应一个Pi，无线传感器网络节点组成的集合{n1，n2，…，nM}与集合{P1，P2，…，PN}之间有一个单射。

上述关联结构和密钥预分配方案的对应关系如表1所示。

表1　密钥预分配方案Tab.1 Key pre-distribution schem e

4　方案分析

无线传感器网络的密钥管理方案必须具有连通性和安全性。下面对本文提出方案中的节点存储能力及这两个最重要的性能进行分析。

存储要求下面先计算节点ni存储的密钥量。

引理2设节点ni= Pi，则包含Pi的（3，1）型子空间的个数为q + 1。

证明若Pi是（2，0）型子空间，则包含Pi的（3，1）型子空间的个数为N'（2，0；3，1；4）= q + 1。

若Pi是（2，1）型子空间，则包含Pi的（3，1）型子空间的个数为N'（2，1；3，1；4）= q + 1。因此，包含Pi的（3，1）型子空间的个数为q + 1。从上述引理可以得到：

定理3任意一个节点ni存储的密钥量为q+ 1。

下面计算任意两个节点ni与nj共享的密钥量。

引理3若Pi与Pj都是（2，0）型子空间，则是（3，1）型子空间。

又因Vi、V、Vj都是中的一维子空间，所以。否则Vi、V、Vj两两正交，则与最大迷向子空间是二维的相矛盾。即

引理4若Pi是（2，0）型子空间，Pj是（2，1）型子空间，则是（3，1）型子空间。

引理5若Pi与Pj都是（2，1）型子空间，则是（3，1）型子空间。

定理4任意两个节点ni与nj的共享密钥量为1。

证明由上述几个引理可知，两个节点所对应的子空间，则这两个子空间的交是一维子空间的二维子空间构成一个（3，1）型子空间，即节点ni与nj的共享密钥量为1。

由以上分析可知，所构造方案的参数（q2+ q + 1，q + 1，1）为射影平面的参数，因此得到了一种新的构造射影平面的方法。

无线传感器网络的密钥管理方案必须具有连通性和安全性。下面就对本文提出方案中的这两个最重要的性能进行分析。

连通性连通性就是一个网络中任何两个节点至少共享一个密钥的概率。在此方案中，从共享密钥来分析，任两个节点拥有多个共享密钥，能保证任何两个节点共享一个密钥，共享概率为1，明显高于其它方案，如表2所示。

表2　比较不同方案的连通性Tab.2 Difference from different schem es

表2中，A-G、S-B、P-S分别出自于文献[11-13]。在大部分现有文献[14-18]中，W SN的全局连通性都只有0.6左右。

安全性如果某个节点被敌人所捕获，则该节点存储的密钥等信息不再安全。节点ni与nj之间的共享密钥都在节点nk中，一旦节点nk被捕获，则节点ni与nj之间的连接就会破坏。定义损失概率为

抗毁性是影响无线传感器网络应用方面的一个很重要的因素。假设攻击者可以随机或者选择性地攻击节点，对此做最坏的假设，假设攻击者选择性地攻击节点。如果一个攻击者足够聪明和幸运，可以掌控整个无线传感网络，然后从中挑选其想要的节点。因为每个节点含有一个密钥链，每个密钥链中有q + 1个密钥，由于本文给出的方案中有q2+ q + 1个节点，一个足够聪明的攻击者至少需要q + 1个密钥链才能恢复密钥池中所有的密钥（因为q（q + 1）= q2+ q，所以q个密钥链恢复不了整个密钥池）。这时两个节点的通信是不安全的。

由以上分析可知，如果W SN中部署1 723（412+ 41 + 1 = 1 723）（这里的q = 41）个传感器节点，当有41个节点被捕获时，整个密钥池被攻破。

5　结语

无线传感器网络越来越广泛，其安全性越来越受到人们的关注，其中密钥分配和管理是无线传感器网络安全的热点研究问题。无线传感器网络不同于传统网络，考虑到其能量供应、计算能力、存储容量的限制，密钥分配机制有其自身的特点。在现有方案中，基于概率的随机预分配方案存在共享概率和密钥路径长度无法得到确定性保证的问题，并且在节点密钥组长度受限的情况下难以支持较大规模的网络。本文在介绍了无线传感器网络特点的基础上，对目前已有的随机型和确定型密钥预分配方案的设计进行详细分析，以较高的概率保证邻居节点之间建立对立密钥，同时也解决了原始方案中的安全问题。

参考文献：

[1]孙利民.无线传感器网络[M].北京：清华大学出版社，2005.

[2] AKYILDIZ IF，SU W，SANKARASUBRAMANIAM Y.A survey on sensornetworks[J].IEEE Communications，2002，40（8）：102-114.

[3] ESCHENAUER L，GLIGOR V D.A Key-Management Scheme for Distributed Sensor Networks[C]//Proc of the9th ACM Confon Computer and CommunicationsSecurity.New York：ACM Press，2002：41-47.

[4] CHAN H，PERRIG A，SONG D X.Random Key Pre-Distribution Schemes for Sensor Networks[C]//Proc of2003 IEEE Symp on Research in Securityand Privacy.New York：ACM Press，2003：197-213.

[5] CAMTEPE S A，YENER B.Combinatorial Design of Key DistributionMechanisms forW ireless Sensor Networks[C]//Proc of the 9th European Symp on Research in Computer Security.Berlin：Springer，2004：293-308.

[6] LIU D，NING P.Establishing Pair-W ise Keys in Distributed Sensor Networks[C]//Proc of the 10th ACM Confon Computer and CommunicationsSecurity.New York：ACM Press，2003：52-61.

[7] LEE J，STINSON D R.Deterministic Key Pre-Distribution Schemes for Distributed Sensor Networks[C]//Proc of the 11th Int W orkshop on Selected Areas in Cryptography.Berlin：Springer，2004：1-14.

[8]夏戈明，黄遵国，王志英.基于对称平衡不完全区组设计的无线传感器网络密钥预分配方案[J].计算机研究与发展，2008，45（1）：154-164.

[9]沈颢.组合设计理论[M].上海：上海交通大学出版社，2008.

[10] W AN Z X.Geometry ofClassical Groups over Finite Field[M].Lund：Student Literature，1993.

[11] PERRIG A，STANKOVIC J，W AGNER D.Security in sensor networks [J].Communicationsof the ACM，2004，47（6）：53-57.

[12]RUJS，ROY B.Key Pre-Distribution Using Partially Balanced Designs inW ireless Sensor Networks[C]//Proceedings of ISPA 2007.Canada： Niagara Falls，2007：431-445.

[13] CAMTEPE S A，YENER B.Combinatorial Design of Key Distribution Mechanisms forW ireless Sensor Networks[C]//Proc of the 9th European Symp on Research in Computer Security.Berlin：Springer，2004：293-308.

[14]PATERSON M B，STINSON D R.A unified approach to combinatorial key predistribution schemes for sensornetworks[J].DesCodesCryptogr，2014，71：433-457.

[15]Chen C Y，Chao H C.A survey ofkey predistribution inwirelesssensor networks[EB/OL].（2011-07-13）[2014-10-26].http：//www.arxiv.org.

[16] MARTIN K M.On the Applicability of Combinatorial Designs to Key Predistribution forW ireless Sensor Networks[C]//IW CC，2009.Lecture Notes in Computer Science，2009，5557：124-145.

[17] MARTIN K M.The rise and fall and rise of combinatorial key predistribution[J].Leture Notes in Computer Science，2011，6544：92-98.

[18]PEID Y，DONG JW，RONG C M.A novelkey predistribution scheme forwirelessdistributed sensorneyworks[J].SciChina Inf Sci，2010，53：288-298.

（责任编辑：杨媛媛）

Key pre-distribution schem e based on sym plectic geom etry for w ireless sensor networks

CHEN Shangdi，W EN Jiejing
（College of Science，CAUC，Tianjin 300300，China）

Abstract：The design of keymanagementscheme，whosemain objective is to provide secure and reliable communication，is one of themost importantparts of securitymechanism ofwireless sensornetwork.W ith regard to the limitation of power，computation and storge recourse ofwireless sensor network，a key pre-distribution scheme based on the 4-dimensional symplectic geometry ofwireless sensor networks is proposed.The obtained results show that the scheme considerably enhances the network scalability，and it has achieved good connectivity and good overallperformance.

Key words：wirelesssensornetwork（W SN）；key distribution；key pre-distribution scheme；symplectic geometry

作者简介：陈尚弟（1964—），男，山西应县人，教授，博士，研究方向为代数、图论、编码与密码.

收稿日期：2014-10-31；修回日期：2014-12-23基金项目：中央高校基本科研业务费专项（ZXH2012K005）；国家自然科学基金项目（61179026）

中图分类号：O157

文献标志码：A

文章编号：1674-5590（2016）01-0059-06