一种基于HECRT 的物联网密钥管理方案

曾 萍，张 历，杨亚涛，储 旭，刘宇新

(北京电子科技学院通信工程系，北京 100070)

1 概述

物联网(Internet of Things，IOT)［1］已成为当前世界新一轮经济和科技发展的战略制高点之一，随着物联网的快速发展，其网络规模不断扩张，信息在感知节点、数据类型、网络等方面都存在很大的异构特性，敏感信息在节点间传递会越来越频繁，并且物联网中感知层节点受资源限制影响，计算能力和通信能力都很有限，现有的网络安全架构和密钥管理方案无法满足物联网发展新的安全需求，因此需要在现有的研究基础上提出适合物联网的网络架构和密钥管理方案。

目前，针对物联网网络安全架构的研究尚处于起步阶段，并没有统一的安全架构。文献［2-4］结合现有研究，将物联网分为3 层，即感知层、网络层和应用层，对每一层进行安全需求分析，给出了较为完整的安全模型。文献［5］提出ID 保护的物联网T2ToI 中能量高效的健壮密钥管理方案，给出了较清晰的物联网系统模型、网络模型、敌手模型和密钥管理安全需求，并提出了5 种密钥管理方案，但是方案缺少安全性证明，无法保证节点信息的隐私性需求。文献［6］提出基于重复博弈的物联网密钥共享方案，通过引入重复博弈的理论，有效分析并解决了异构节点密钥共享的问题，但是方案中并未给出具体的网络分布模型。

针对上述问题，本文提出了一种基于同态加密与中国剩余定理(Homomorphic Encryption and China Remainder Theorem，HECRT)的密钥管理方案，按不同应用和地理位置对网络进行分层，通过构造双重密钥池矩阵来保证区域和节点安全，节点通过密钥列表来获取共享密钥，密钥采用同态加密(Homomorphic Encryption，HE)和中国剩余定理(China Remainder Theorem，CRT)进行隐私处理，并且由中央控制中心负责分发，从而保证节点的隐私并节约通信资源。

2 预备知识

2.1 中国剩余定理

中国剩余定理［7］:设p1，p2，…，pk是互为素数的k 个正整数，k≥2，令:

其中，Pi=P/pi(i=1，2，…，k)，则同时满足同余方程组:

正整数解为:

2.2 同态加密技术

同态加密由Rivest R L［8］于1978 年提出，是允许直接对密文进行操作的加密交换。但是由于其对已知明文攻击是不安全的，由Domingo 作了进一步的改进。同态加密技术最早是用于对统计数据进行加密的，由算法的同态性，保证了用户可以对敏感数据进行操作但又不泄露数据信息，同态技术是建立在代数理论上的，其基本思路如下:

假设Ek1和Dk2分别代表加密、解密函数，明文数据空间中的元素是有限集合{M1，M2，…，Mn}，α 和β代表整数域上的同态加密运算，若式(4)成立:

则称函数族{Ek1，Dk2，α，β}为一个同态。

3 基于HECRT 的物联网密钥管理方案

3.1 网络模型建立

为实现物联网全面感知，又不带来信息采集网络布局的混乱，根据不同应用将物联网分成不同的区域［9］，对同一区域进行地理位置的部署划分，结合现有文献中关于物联网的网络架构建立基于HECRT 的物联网网络模型，假设每个区域设有中央控制中心(Control Center，CC)，中央控制中心接收各个节点GPS 采集的信息，从而获取每个节点的位置以及与中央控制中心的距离、节点位置与CC 的角度，CC 根据不同的距离划分不同的层。物联网网络模型见图1。

图1 基于HECRT 的物联网网络模型

物联网感知层主要由一些资源有限的设备节点组成，且大部分采用无线通信的方式来交换采集信息，考虑通信距离受设备自身资源的限制，该方案在进行网络部署时，考虑每个节点设备的通信能力各不相同，所以，将通信能力最弱的节点的通信半径设为R。以某一区域控制中心CC 为中心，记设备节点与CC 的距离为d，节点通信区域是以节点为中心、半径为R 的整个圆形区域。根据节点与CC 的距离对区域进行如下分层，假设区域分为K 层:

第1 层:d∈(0，R/2］;

第2 层:d∈(R/2，R］;

…

第K 层:d∈((j-1)R/2，jR/2］，j=1，2，…，k。

按照上述规则分层，中央控制中心CC 为同一层的每个节点分发区域密钥和层密钥，这些密钥分别用于区域之间节点通信和层之间节点的通信。为了能够保证同一层的任意2 个节点都可以直接通信，在这些设备之间加入中间转发设备，如无线电发射塔或基站。取节点间的弧长L ＜R，根据弧长来确定层中部署无线电发射塔的数目。以第i 层中不同节点通信距离模型进行分析，如图2 所示。

图2 同一层中的节点通信距离模型

从图2 可以看出，当节点距离d1＞R 时，节点间无法进行通信，对于第i 层，取其最大圆弧，即为半径(i-1)R/2 的圆的周长，计算得出周长为2π ×(i -1)R/2，即π(i-1)R，那么该层需要的无线发射塔数目为π(i-1)R/2R，即π(i -1)R/2，整个区域分为k 层，需要即πk(k -1)/4 个无线电发射塔。

3.2 方案描述

3.2.1 密钥池建立

文献［10］中构造M ×N 矩阵，节点根据自身哈希H(ID)值，从每列中选取对应位置的密钥共计N 个密钥，组成自身的密钥环，但该方案未考虑物联网环境、不同应用下的网络分布，且只设定一个控制中心管理密钥的产生和分发，不适用于海量节点的物联网环境。为此，本文方案构造了2 个T × L 矩阵，分别存储对应区域、层的源密钥和私钥。seedij表示第i 个区域、第j 层所有节点的源密钥。另一矩阵存储节点的私钥pij，pij为第i 个区域、第j 层所有节点的私钥，pij为一大素数，seedij，pij∈［-2ρ，2ρ］，作为安全参数，这里的安全参数可以根据不同的应用需求取不同值，其密钥池矩阵如式(5)、式(6)所示:

其中，seedij=H(seedi‖dkij)，seedi是由离线服务器为每个区域控制中心CC 随机产生的种子密钥，不同区域其产生的种子密钥不同，而且种子密钥由CC存储，离线后敌手无法获得。若整个网络分为T 个区域，则每个区域控制中心CC 存储T 个种子密钥:［seed1，seed2，…，seedT］。

通过上述产生规则可以保证同一区域、同一层的节点所获得的seedij相同，但敌手无法通过该值推测出seedi值;每次密钥更新时，控制中心CC 需要通过更新seedi值来更新seedij值。

这样构造矩阵的前提假设是不同应用(区域)的层数以及每层节点数相同或者相近，但是实际应用中不同应用对应的网络规模不同，甚至差别很大，考虑到这些原因，在给每个节点定义唯一身份标识时不能再根据该层的规模来进行编号处理，因此，本文方案根据节点与控制中心CC 的距离d 和方向(由CC 选定x，y 垂直坐标轴，再计算节点与CC 的连线与x 轴所成的角度a)，这样设定的优点是标识随节点位置的改变而变化，敌手不易猜测，并且x，y 垂直坐标轴由CC 选取，增加了敌手猜测攻击的难度。

3.2.2 密钥预分配

方案中各节点的部署信息为DKij=(IDij| |dkij)，其中，ID 表示该节点的唯一标识:ID=H(d| |a);dkij表示该节点的地理位置编号，即第i 区域、第j 层。中央控制中心CC 产生密钥的步骤如下:

假设节点部署信息为DKij，其对应的私钥值为pij。在矩阵中，删除第i 行、第j 列，得到(T -1)×(L -1)矩阵，用于构造节点密钥环。这样构造的原因是删除第i 行、第j 列后，可以提高同一层节点发现共享密钥的概率，而且可以防止同一层节点的共谋攻击，如式(7)所示:

方案中任意节点密钥环的构造过程如下:

假设节点U 与CC 的距离为du，则该层内所有节点密钥环构造过程为:

(1)CC 根据节点U 的唯一标识IDU，计算H(IDU)=B1B2…BL-1，其中，Bi为十进制数，对应到seedij矩阵的某一行，CC 根据Bi值为每个节点选取seedij值。

(2)CC 根据pij矩阵中该层对应的L -1 个pij值按顺序分配给对应的seedij，然后根据H(seedij||pij)计算出节点密钥环中的所有密钥值。这样保证了同一层内以一定概率p 存在共享密钥，且概率值仅与每个节点ID 的哈希值有关。

设同一层中节点发现i 个共享密钥的概率为p(i)，则:

不同层节点发现共享密钥的概率为0。由于本文方案删除了节点所在第i 区域和第j 层的矩阵行列值，概率p(i)值比文献［10］高，并且这样的选取机制可以防止同一区域、同一层的共谋攻击，节点不能通过自身的seedij值和pij值计算其中的一个共享密钥。

上述选取机制可能会造成不同层之间的节点满足距离小于等于R，但是却没有共享密钥的情况。为了弥补上述缺陷，在通信过程中采用2 种方式:(1)除了要交换必要的身份和地域信息外，还需要交换各自的距离信息，当节点间发现其满足不同层，且距离差为R 之内时，由CC 分配给它们通信密钥。(2)改变上述b 中产生pij的规则，即pij的选取是从相邻两列中(即2 ×(L -1)个pij中选取L -1 个)，i=1，2，…，L -1。这样任何节点相邻两层之间节点都能以p 的概率发现共享密钥，p 的值介于0～p(1)之间。

3.2.3 通信协议

本文方案的通信协议参照somewhat 同态加密技术的相关参数设定本文协议，协议实现具体过程如下:

设区域i 分为A 层，由上文分析可知，对应同一层节点，其存储的私钥pij和seedij是相同的，因此在同一区域中只讨论不同层间节点的情况，CC 构造中国剩余方程式，如式(9)所示:

其中，pij为i 区域、j 层的私钥;seedij为i 区域j 层的种子密钥。由中国剩余定理知，存在一个值Y，满足式(10):

由中央控制中心CC 将计算得到的Y 值广播给区域内的每个节点，节点利用自身的私钥pij，根据中国剩余定理，对Y 进行如下处理:

其中，rij作为该区域的层密钥，存储在节点中。每个节点密钥环中的L -1 个密钥由CC 采用同态加密技术用区域密钥加密并广播给每个节点，同时需要传输的还有每个节点密钥选取时对应矩阵中的行列坐标值。

在完成上述步骤后，相邻节点之间可以通过区域密钥加密该节点的密钥行列表给对方，对方只需从表中查找与自己相同信息就可以找出所有的共享密钥。此外，考虑到方案中设备节点受资源限制，采用文献［11］的轻量级通信协商协议进行密钥协商。

3.2.4 密钥更新

本文方案的密钥更新涉及到周期更新、节点加入/离开时的密钥更新两部分。方案的更新工作由中央控制中心CC 完成，CC 的计算能力强、资源充足，方案中节点加入/离开时seedij进行更新外，周期更新时还要对节点的私钥pij进行更新。CC 更新源密钥矩阵，每个区域控制中心CC 更新自己的密钥形成新的密钥。

seedij具体更新过程如下:

CC 根据新产生的seed'ij值，为每个节点产生新的密钥环，并以上述广播的形式分发给每个节点，每个节点接收后根据通信协议恢复明文，同时更新自己的密钥环以及对应的矩阵行列表。

4 方案性能分析

4.1 共享密钥发现概率

根据3.2.2 节描述的密钥分配可知，任意2 个物联网设备节点之间有i 个共享密钥的概率为:

任意2 个节点之间至少有t 个共享密钥的概率为:

由式(14)、式(15)可知，若T 值不变，随着L 值变大，p 值也相应增大，通过计算可知，当T=128，L=256，t=1 时，p 值高达90%，t=3 时，p 值仍大于30%。

表1 将本文方案和文献［10，11］中的q 复合度密钥预分配方案进行仿真比较。从其中的数据可看出，选择相近L 和T 值能得到较理想的概率值，该概率值与使用q 复合度密钥预分配方法得到的概率值相近。

表1 各方案共享密钥的概率比较

4.2 网络连通性分析

根据共享密钥概率分析，任意2 个节点能直接建立安全链路的概率可由式(14)计算得出。为方便阐述，记2 个节点间能直接建立安全链路即单跳的概率为p1，2 个节点通过一个中间节点建立安全链路即两跳的概率为p2，设每个节点有d 个邻居节点，对每个邻居节点而言，可直接与源节点IDi和目标节点IDj建立安全链路的概率为。因此，节点IDi和IDj能通过单跳和两跳建立通信的概率p1，2为:

显然，概率p1，2随着概率p1的增加而增加，而增加的幅度随邻居节点的个数d 的增加而变大，根据式(16)可以计算出在通信范围内的任意2 个节点能直接或间接(两跳)建立安全链路的概率高达90%以上。

本文方案设定节点通信距离的范围，在允许的通信范围内，节点间可保持较高的共享密钥发现协议。由于设定的通信距离2R 可能会因为应用的不同，包含同一区域数个层或者不同区域，降低共享密钥发现概率，但由于方案中还为不同区域和层通过同态加密技术分配了区域密钥和层密钥，可作为当共享密钥发现出现较低概率时的补充，确保整个方案的连通性。由上述矩阵的构造过程可知，矩阵设计以所有区域中最大层数为基数，便于整个网络的扩展。

4.3 网络扩展性分析

本文方案的2 个密钥池构造均根据区域和层划分，考虑到区域之间的异构特性，初始阶段若按照部署信息来构造矩阵密钥池往往不能满足所有的区域，为此，选择所有区域中层最多的作为标准，构造L ×T矩阵，这样的构造方式可以很好地满足网络的扩展性，同时也增加了密钥池容量，提高了安全性。表1 仿真结果中L 和T 的取值为128 和256，未涉及到更大的网络规模，主要受限于仿真软件的功能，不能进行仿真，但理论上分析从构造的方式以及密钥产生的过程可知，随着网络规模的不断扩大，其概率优势将更为明显。

在该方案中，节点需要存储自身的长期私钥pij、公钥pk、源密钥seedij以及广播区域密钥;共享密钥发现过程只需要广播自身的行列坐标列表即可，其复杂度为O(1)，同时加密传输机制采用Gentry 的全同态加密方案，有比较完整的硬件实现过程。因此，该方案具有较强的可行性。

5 安全性分析

在本文方案中，攻击者可以通过捕获其他节点来获得某一特定节点的所有密钥从而获得该节点与其他节点的通信密钥，假设已有k 个节点(同一区域、同一层)已被捕获，计算攻击者能获得某一节点所有密钥的概率P 为:

利用Matlab 软件进仿真，得到捕获节点数与破解节点密钥概率，如图3 所示。

对于整个网络的攻击，在理论上攻击者可以通过捕获一定数量的节点来获得密钥池中的所有密钥，从而破坏感知层网络。假设已有K 个节点被捕获的情况下，攻击者能够获得密钥池中所有密钥的概率p'，当k 个节点中的所有密钥都不重复时，k 值为m，因此攻击者至少要捕获m 个节点才能获得所有密钥，设S(k，m)为第二类Stirling 数，则攻击者能获得密钥池中所有密钥的概率p'为:

图3 捕获节点数与破解节点密钥概率的关系

当k=m=n=128 时，p'值趋近于0，当k=1 000，M=N=128 时，p'=0.001 6。

(1)防共谋攻击。本文方案的理论基础是同态加密技术以及中国剩余定理。密钥池矩阵由资源充足的中央控制中心产生和更新，密钥的产生(采用Hash 函数)具有单项不可逆性，密钥的预分配采用随机方式进行。节点的位置信息首先由CC 秘密选择垂直坐标，然后计算出角度和距离，因此节点的位置信息会随着位置的变化而变化，敌手破解的难度增大。密钥经同态加密技术隐私处理后分发给节点，节点被分配到相同密钥的概率可以忽略不计，并且在选取产生密钥因子的过程中删除了节点所在的行和列，能有效防止区域内部的共谋攻击，敌手无法通过俘获节点，计算自身H(seedij||pij)值获得额外的密钥，从而不能为猜测区域内部其他节点的密钥带来效果，同时该方案良好的扩展性、密钥池的构造方式和产生也给敌手攻击网络节点带来很大的难度。

(2)敌手破解节点私钥和源密钥可能性小。方案采用同态加密技术结合剩余定理进行信息加密传输，节点通过自身的私钥和源密钥进行解密。考虑到物联网节点自我保护措施较弱，且无人看管，为此CC 需要对各节点进行定期的查询反馈，以便及时发现节点的异常行为，需要进一步增强CC 检测异常节点的有效途径和方法。为了保护节点的安全，定义节点部署信息DK 中包含了dk(地理位置信息)，ID(节点与CC 的距离和角度)，这些都是隐私的，因此在上述同态传输过程中，虽然敌手很容易通过通信数据业务流分析得到来自相同层加密后的广播消息，但是敌手只能获取该区域、该层，无法获得具体节点的编号，因此敌手无法进行针对性的腐化攻击，破解节点私钥和源密钥的难度大大增加。

(3)敌手俘获密钥池矩阵可能性小。本文方案假设区域控制中心作为一个管理中心，具备足够的数据处理能力和可持续工作能力，映射到物联网中可以作为大型服务器和数据处理控制中心。CC 负责产生、更新和存储源密钥，不同区域的数据处理交换认证工作。从本文方案中seedij的产生可知，敌手通过俘获节点的方式可以获得节点的密钥环，通过异步攻击和同谋攻击的方式可以获得整个seedij密钥矩阵和pij密钥矩阵，但是由于seedij是由seedi和dij通过Hash 作用产生的，敌手破解的难度相当于破译单向函数的难度，因此敌手无法控制密钥矩阵的源密钥和更新能力;同时敌手采取针对攻击的可能性大大降低，考虑到物联网设备的移动特性，同一设备的ID 随着部署位置的不同将产生变化，并且敌手无法通过破译设备的部署信息获得节点的ID(ID 只由CC 产生)。由上述破解节点共享秘钥的分析中可知，节点至少俘获同一区域、同一层中1 000 个数目以上的节点才能以极低的概率破解密钥矩阵;节点通过俘获不同区域、不同层的节点来破解密钥矩阵的可以忽略不计。

(4)满足前后向安全性。新设备节点离开时，为保证通信前向安全性，更新pij矩阵第j 列的所有密钥信息，通过CC 重新产生并分配给该区域、该层的所有设备节点，由于其他区域的节点不涉及到第j列的密钥值，因此不需要更新，减少了更新成本。

不同应用对应不同区域，可以根据不同的安全需求设定对应的安全等级。例如，可以通过改变同态加密机制中的参数p 和安全参数r 来提高或者降低安全等级，节点的私钥pij也可以根据不同的需要进行相应提高。

6 结束语

本文提出一种基于HECRT 的物联网密钥管理方案，给出了基于节点位置信息的网络分层模型，与现有方案相比有以下优点:(1)根据节点通信的最大距离，计算出同一层内需要的无线电发射塔数据，给出详细的部署安排。(2)构造双重密钥池分别用于区域密钥和节点私钥，同时节点位置信息与中央控制中心CC 垂直坐标轴的选取相关，确保节点位置信息的隐私。(3)有效提高了节点共享密钥发现概率。(4)给出具体的密钥更新协议，能够满足节点加入/离开时的动态密钥更新。(5)方案的安全性得到了较好的增强。

［1］ITU Internet Reports 2005:The Internet of Things［EB/OL］.(2005-07-11).http://bbs.cnttr.com/viewthread.Phptid=241077.

［2］王 晶，全春来，周 翔.物联网公共安全平台软件体系架构研究［J］.计算机工程与设计，2011，32(10):3374-3377.

［3］白 蛟，全春来.基于物联网的公共安全云计算平台［J］.计算机工程与设计，2011，32(11):3696-3701.

［4］Liu Jihong，Yang Li.Application of Internet of Things in the Community Security Management［C］//Proceedings of the 3rd International Conference on Computational Intelligence，Communication Systems and Networks.Bali，Indonesia:IEEE Press，2011:314-318.

［5］任 伟，雷 敏，杨 榆.ID 保护的物联网T2ToI 中能量高效的健壮密钥管理方案［J］.小型微型计算机系统，2011，32(9):1903-1907.

［6］李大伟，杨 庚.基于重复博弈的物联网密钥共享方案［J］.通信学报，2010，31(9A):97-103.

［7］席国宝，陈惠芳，赵问道.基于中国剩余定理的秘密共享组播密钥管理方案［J］.电子与信息学报，2006，28(12):2378-2381.

［8］Rivest R L，Adleman L，Detrouzos M L.On Data Banks and Privacy Homomorphism［M］.New York，USA:Academic Press，1978.

［9］Banihashemian S，GhaemiBafghi A.A New Key Management Scheme in Heterogeneous Wireless Sensor Networks［C］// Proceedings of the 12th International Conference on Advanced Communication Technology.［S.l.］:IEEE Press，2010:141-146.

［10］章 睿，刘吉强，赵 佳.一种基于ID 的传感器网络密钥管理方案［J］.电子与信息学报，2009，31(4):929-932.

［11］曾 萍，张 历，胡荣磊，等.WSN 中基于ECC 的轻量级认证密钥协商协议［J］.计算机工程与应用，2014，50(2):65-69，80.

［12］Chan Haowen，Perrig A，Song D.Random Key Predistribution Schemes for Sensor Networks ［C］//Proceedings of 2003 IEEE Symposium on Security and Privacy.Washington D.C.，USA:IEEE Computer Society，2003:197-213.