（运筹学与控制论专业论文）ad+hoc网络的分布式认证模型研究.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名： 日期： 摘要 移动a dh o e 网络在共享无线信道上提供了便利的、没有基础设施的通信服 务。然而由于移动a dh o e 网络的固有特性，使得这种网络更容易遭到安全攻击。 本文通过对a dh o e 网络的研究，结合前人的工作，运用相关的数学工具，提出了 一种具有较强鲁棒性的分布式认证模型。 首先，本文介绍了a dh o e 网络的背景知识、特点和目前该网络在安全方面面 临的问题。接着，详细分析了用于增强a dh o e 网络安全的几种信任方案，并分别 指出了这些方案的优缺点。 其次，介绍了本文用到的相关密码知识。通过对基于不同密码体系签名算法 的对比分析，采用了基于椭圆曲线的签名算法，从而使分布式认证模型在相同条 件下，认证的效率及安全性有了明显的提高。 然后，在指出已有的分布式信任和密钥管理模型不足的基础之上，结合已有 的分布式信任技术、密钥管理技术、邻居节点行为监视技术，提出了一个具有认 证、密钥管理和邻居节点行为监视的分布式认证模型，并对相关算法进行了详细 的介绍。 最后，本文在理论研究的基础之上，对模型进行了总体设计，并用o p n e t 对其进行了系统仿真，仿真结果表明了该模型是可行性，并且在安全性和效率上 比现有模型有显著的改进。 关键字：a dh o e 网络：密钥分享：分布式认证 a b s t r a c t m o b i l ea dh o cu e t w c l r k so f f e rc o n v e n i e u ti n f r a s t r u c t u r e l e s sc o m m u n i c a t i o n o v e rt h es h a r e dw i r e l e s sc h a n n e l h o w e v e r , t h en a t u r eo fm o b i l ea dh o cn e t w o r k s m a k e st h e mv u l n e r a b l et os e c u r i t ya a a c k s b ya n a l y z i n ga dh o cn e t w o r k s ，t h i sp a p e r c o m b i n e sp r e v i o u si d e a sa n db r i n g sf o r w a r dr o b u s t l yd i s t r i b u t e da u t h e n t i c a t i o nm o d e l i nt h ea dh o cn e t w o r kt r a d e rs o m em a t h e m a t i c st o o l s f i r s t ，t h i st h e s i si n t r o d u c e st h eb a c k g r o u n d ，c h a r a c t e r l s t i co fa dh o cn e t w o r k s a n dp r o b l e m so fs e c u r i t yi na dh o cn e t w o r k s s e v e r a lt r u s ts c h e m e so fr e i n f o r c i n g s e c u r i t yo fa dh o cn e t w o r k s a r e a n a l y z e d i n d e t a i la n dt h ea d v a n t a g ea n d d i s a d v a n t a g eo f t h es c h e m e sa r ep o i n t e do u t s e c o n d ，t h ec o r r e l a t i v ec r y p t o s y s t e mi si n t r o d u c e d t h et h e s i sa d o p t se c d a sb y a n a l y z i n ga n dc o m p a r i n gd i f f e r e n tc r y p t o s y s t e m s u n d e rt h e s a m ec o n d i t i o n s ， e c d a sw i l lg r e a t l yi m p r o v et h es e c u r i t ya n de f f i c i e n c yo fd i s t r i b u t e da u t h e n t i c a t i o n t t l i r d a f t e rp o i n t i n g0 u tt h ei n s u 伍c i e n c i e so fa v a l l a b l ed i s t r i b u t e da u t h e n t i c a t i o n a n dm a n a g e m e n tm o d e l so fs e c u r e k e y ，t h ep a p e r i n t r o d u c e sad i s t r i b u t e d a u t h e n t i c a t i o nm o d e lw i t ha u t h e n t i c a t i o n ，m a n a g i n go fs e c u r ek e ya n dm o n i t o r i n g b e h a v i o ro fn e i g h b o r so nt h eb a s i so fc o m b i n i n gc r r r e n tt e c h n o l o g yo fd i s t r i b u t e d a u t h e n t i c a t i o n ，m a n a g i n gs e c u r ek e ya n dm o n i t o r i n gm i s b e h a v i o ro fn e i g h b o r s t h e n t h ec o r r e l a t i r ea l g o r i t h m sa r ed e s c r i b e di nd e t a i l a tl a s t , t h ep a 。e rd e s i g n sas i m p l em o d e lo i lt h eb a s eo ft h e o r yd i s c u s s e da b o v e a n du t i l i z e so p n e tt os i m u l a t ec o m m u n i c a t i o np r o t o c 0 1 t h er e s u l t so fe x p e r i m e n t s h o wt h ef e a s i b i l i t yo ft h i sm o d e a l s ot h er e s u l t ss h o wt h ei m p r o v e m e n t si nt h e s e c u r i t ya n dt h ee m c i e n c yo f t h i sm o d e lc o m p a r i n gw i t ho t h e rc u r r e n tm o d e l s k e yw o r d ：a dh o cn e t w o r k ；k e ys h a r i n g ；d i s t r i b u t e da u t h e n t i c a t i o n 2 b u吾 随着计算机网络的广泛应用，网络安全问题越来越严重。网络入侵和攻击已 经对网络用户产生了严重的威胁。这个威胁对于无线用户也不例外。与有线网络 相比，无线网络安全更容易遭受从主动干扰到被动丢包等方面的攻击。 当我们利用现有的、复杂的安全技术设计一个防止入侵的系统的时候，我们 期望实现一个代价最小，可以实现并且可以完全抵制入侵的系统，这在现实中是 办不到的。因此，为了抵制网络入侵，我们希望能做到从完全阻止入侵到在容忍 一定程度入侵的一个转交。所以我们追求建立一个能使攻击的危害保持在局部， 且使系统的安全得到保障的系统。 移动a d h o c 网络是移动节点利用无线通信的个新案例。由于移动a d h o c 没有提供通信的基础设施，网络拓扑结构的不断变化，网络的分布性等特点，使 得应用于有线或者是其它无线网络的传统安全入侵检测、密钥管理、访问控制等 方法对于大型移动a dh o c 网络来说不太适用。所以移动a dh o c 网络相对于其它 无线网络来说，在安全方面显的更加脆弱。 目前，h a i y u nl u o 等人基于移动a dh o c 网络的特点提出了分布式信任模型。 这个模型相对于单c a 的信任模型、层次的信任模型或者基于w e b 的信任模型更 适合大型移动a dh o c 网络的特点。这个模型提出了一种可扩展的入侵容忍的安 全解决方案。在方案中，使用了门限密钥分享和密钥份额更新的思想来达到入侵 容忍的目的。在网络中，没有单个实体或者节点知道系统的密钥( 如证书签名用 的密钥) ，而是每个节点只拥有用于证书签名密钥的一个部分。门限t 个相邻实 体可以联合完成c a 的功能。只要每个敌对的团伙中，联合入侵的相邻实体个数 小于门限值t ，这个系统就是安全的。 本文基于h a i y u nl u o 等人的思想，结合密钥管理，邻居行为监视技术，提 出了一个改进的分布式模型。经过对原有模型以及相关模型的分析，在其不足的 基础之上，进行了下面的改进：1 ) 采用了同等条件下，相对安全的椭圆曲线密 码体系，从而使得整个模型相对于r s a 的模型在运行、存储等方面的代价有所 下降；2 ) 利用分布式密钥产生算法代替原模型中的临时信任中心，弱化了原有 模型的假设，增强了这个模型的适用范围；3 ) 采用已有的部分证书鉴别机制， 提高了证书的合成效率，降低了通信代价；4 ) 增加邻居行为监视的功能，这个 功能为证书的撤销提供强有利的证据。在对不良行为评价的时候采用了分值计算 的方法，而不是原有的次数计算的方法，从而提高了不良行为的评价粒度。 全文共分为5 章，第章主要介绍了移动a dh o c 网络相关背景、网络特点、 安全方面面临的问题，接着分析了目前解决a dh o c 网络安全的几种模型并分别 指出了它们的优缺点。第二章主要介绍了模型中用到的相关数学知识。第三章描 述了本模型用到的相关算法。第四章对模型进行了总体设计，并通过程序和仿真 实验验证模型的可行性。第五章是对全文工作的总结，以及对后续工作的设想。 论文相关的研究工作得到国家信息产业部项目“安全网管技术”和国家“十 五”“2 1 l 工程”重点学科项目“信息安全保密技术与相关数学理论研究”的资 助。 4 第一章研究的背景 1 1a dh o c 网络介绍 1 1 1a dh o e 网络的背景 第一章研究的背景 a dh o c “2 1 一词来源于拉丁语，是“特别地，专门地为某一即将发生的特定 目标、事件或局势而不为其它的”的意思。这里提出的“a dh o c 技术”所标称 的就是一种特定的无线网络结构，强调的是多跳、自组识、无中心的概念，所以 国内一般把基于a dh o c 技术的网络译为“自组网”，或者“多跳网络”等等。 a dh o c 技术起源于2 0 世纪7 0 年代的美国军事领域，它是在美国国防部 d a r p a 资助研究的“战场环境中的无线分组数据网( p r n e t ) ”项目中产生的 一种新型的网络构架技术。d a r p a 当时所提出的网络是一种服务于军方的无线分 组网络，实现基于该种网络的数据通信。后来，d a r p a 又于1 9 8 3 年和1 9 9 4 年 分别资助进行了抗毁可适应性网络( s u r a n ：s u r v i v a b l ea d a p t i v en e t w o r k ) 和全球移动信息系统( g l o m o ，g l o b a li n f o r m a t i o ns y s t e m s ) 两个项目的研究， 以便能够建立某些特殊环境或紧急情况下的无线通信网络。a dh o c 技术就是吸 取了p r n e t 、s u r a n 以及g l o m o 等项目的组网思想，从而产生的一种新型的网 络构架技术。随着移动通信和移动终端技术的高速发展，a dh o c 技术不但在军事 领域中得到了充分的发展，而且在民用移动通信中也得到了应用，尤其是在一些 特殊的工作环境中，比如所在的工作场地没有可以利用的设备或者由于某种因素 的限制( 投入、安全、政策等) 不能使用已有的网络通信基础设施时，用户之间 的信息交流以及协同工作( c o o p e r a t i v ew o r k ) 就需要利用a dh o c 技术完成通信 网络的立即部署，满足用户对移动数据通信的需求。 基于a dh o c 技术的a dh o c 网络是一种临时自治的分布式系统，其终端具有 无中心接入和多跳等特征。这些特性使得a dh o c 技术涉及到t o s l 分层模型中 的每一个层面。研究者已经在媒质接入问题、路由问题、组播路由问题、电能管 理问题、q o s 问题、安全问题、传输层问题等方面发布了相关的研究成果。 1 1 2a dh o c 网络的特点 刚刚接触a dh o c 网络的人们容易把a dh o c 网络和其它无线通信网络相混淆。 如蜂窝移动通信网络和无线局域网，而实际上它们是有区别的。移动无线通信网 络包括两种类型的网络，单跳网络和多跳网络。其中蜂窝移动通信网络和无线局 第一章研究的背景 域网是单跳网络，而a dh o c 网络属于多跳网络。与其它通信网络相比，移动a dh o c 网络具有以下特征： 1 网络的自组性。h dh o c 网络可以在任何时刻任何地方构建，而不需要现 有的信息基础网络设施的支持，形成一个自由移动的通信网络。 2 网络的动态拓扑结构。从网络的网络层来看，a dh o c 网络中，移动用 户可以以任意速度和任意方式在网中移动，还有无线发送装置发送功率的变化、 无线信道间的相互干扰、地形因素等影响，节点间通过无线信道形成的网络拓扑 结构随时都会发生变化。 3 有限的无线传输带宽。无线信道本身的物理特性使a dh o c 网络的网络 带宽相对有线方式要低的多，另外还要考虑无线信道竞争时所产生的信号衰落、 碰撞、阻塞、噪声干扰等因素，这使得实际带宽会更小。 4 移动终端的有限性。a db o c 网络中的移动终端内存小、c p u 处理能力低、 所带电源有限使得a dh o c 网络的设计更加困难。 5 安全性差。a dh o c 网络是一种无线方式的分布式结构，所以更加容易被 窃听、入侵，遭受网络攻击和拒绝服务等。 6 网络的分布式。a dh o c 网络中的移动节点都兼有独立路由和主机功能， 不存在类似于基站的网络中心控制点，节点地位平等，采用分布式控制方式，增 强了网络健壮性。 7 网络的可扩展性不强。由于采用t c p i p 协议中的子网技术使得i n t e m e t 具有网络的可扩展性，而a dh o c 网络拓扑结构的动态变化使得子网技术所带来的 网络可扩展性不能得到应用。 8 单向无线信道的存在。 9 生存时间短。组网通常是由于某个特定原因而临时创建的，使用结束后， 网络环境将会自动消失。a dh o c 网络的生存时间相对于固定网络是短暂的。 1 1 。3a dh o c 网络的安全目标 a dh o c 网络的安全目标与传统网络的安全目标基本是一致的，包括：数据可 用性、机密性、完整性、安全认证和抗抵赖性，但是两者却有着不同的内涵。下 面是a dh o c 网络安全目标的具体含义： 1 可用性 可用性是指即使受到攻击，节点仍然能够在必要的时候提供有效的服务。可 用性是与网络安全相关的一个关键特性。即使存在拒绝服务攻击的威胁，可用性 也可保证网络服务操作正常并能容忍故障。 6 第一章研究的背景 2 机密性 机密性是保证信息不会泄露给未经授权的用户。 3 完整性 完整性保证信息在发送过程中不会被中断，并且保证节点接收的信息应与发 送的信息完全一样。如果没有完接性保护，网络中的恶意攻击或无线信道干扰都 可能使信息遭受破坏，从而变得无效。 4 安全认证 每个节点需要能够确认与其通信的节点身份，同时要能够在没有全局认证机 构的情况下实施对用户的鉴别。如果没有认证，攻击者很容易冒充某一节点，从 而得以获取重要的资源和信息，并干扰其它节点的通信。只采用认证通常是不够 的，认证只负责证明某人的身份，因此还需要通过授权来决定某种身份是否被允 许做某些事情。 5 抗抵赖性 抗抵赖性用来确保一个节点不能否认它已经发出的信息。它对检查和孤立被 占领节点具有特别重要的意义，当节点a 接收到来自被占领节点b 的错误信息时， 抗抵赖性保证节点a 能够利用该信息告知其它节点b 已被占领。此外，抗抵赖性对 于商业应用中保证用户的利益至关重要。 1 1 4a dh o c 网络面临的安全挑战 与传统网络相比，a dh o c 络具有自己的特点，因此在实现安全目标方面提 出了新的问题。虽然传统的安全机制，例如认证协议、数字签名和加密，在实现 a dh o c 网络的安全目标时依然具有重要作用，但是a dh o c 网络仍面临许多安全问 题，简单概括如下： 1 网络攻击问题 使用多跳的无线链路使a dh o c 网络很容易受到诸如信息攻击和不服务攻击。 信息攻击如被动窃听、主动入侵、信息假冒等各种信息窃取攻击。被动窃听可能 使不良用户获取保密信息：主动窃取攻击中不良用户可以删除有用信息、插入错 误信息或修改信息，从而破坏了数据的可用性、完整性、安全认证和抗抵赖性。 在不服务攻击中，如节点为了节约自己的电源而不为其它节点提供转发的服务， 不良用户时而服务时面不服务，使得整个服务不能正常进行。 2 身份识别的问题 与传统网络或者单跳网络相比，h dh o c 网络节点之间关系的频繁变化，使得 身份识别变的比较困难。而在解决这类问题时大都采用c a 认证策略。而传统的c a 7 第一章研究的背景 认证模式对移动a dh o c 网络来说，实施起来比较复杂和困难。 3 密钥管理的问题 和其它分布式系统一样，正确使用密钥管理系统对于a dh o c 网络的安全十分 重要。a dh o c 网络中，数据的完整性和抗抵赖性一般也需要基于某种加密算法来 实现。加密协议总体上可以分为两大类：对称密钥机制( 如d e s 和i d e a ) 和公开密 钥机制( 如r s a ) 。但是面临的挑战是密钥的管理。如果采用对称密钥机制，则每 个需要通信的节点之间都需要一个秘密密钥，所需管理的密钥数目为n ( n - 1 ) 2 ， 其a n 是节点数。对于规模较大的a dh o c 网络而言，难以实施有效的密钥管理。 如果采用公开密钥机制，由于没有中心节点和证书机构，密钥的管理也比较困难。 4 访问控制问题 在a dh o c 网络中同样需要控制对网络及其所提供的服务的访问。在网络层， 路由协议必须保证不允许非授权节点加入网络，保证没有敌对节点加入和离开网 络而不被检测到。在应用层，访问控制必须保证非授权用户不能访问服务。 5 节点之间的信任问题 在对安全敏感的a dh o c n 络应用环境中，由于节点容易受到攻击，被俘获的 可能性也较大，因此必须建立适当的信任机制。在a dh o c n 缝t = p ，信任问题是中 心问题，我们不能信任媒介，必须借助密钥。因此一个基本的问题是如何生成可 信任的密钥而不依赖受信任的第三方。a dh o c 网络是一个动态自组织的临时网 络，一方面，不能保证网络中各个节点持有被其它节点信任的公钥，另一方面， 节点之间没有办法确认公钥和身份的对应关系。 1 2 已有信任模型的分析 目前应用于a dh o c 网络加强安全的方法主要有四种：1 ) 基于中心的信任模 型：2 ) 基于分层的信任模型；3 ) 基于w e b 的信任模型；4 ) 基于分布式的信任模型。 这四种方法对于大型的移动a dh o e 来说都有着自己的优缺点。下面分别介绍这四 种信任模型。 1 基于中心的信任模型 如图1 1 所示，在基于中心的信任模型。1 中，把中心作为一个合法、权威的 机构，为整个网络提供服务，它可以为网络中的节点或实体提供必要的信息，使 其它节点或者实体相信这个节点是一个合法或者没有危害的好节点。基于中心的 这种方法在许多文章都有介绍。对于个大的移动自组织网，这种方法的可扩展 性是很差的。从安全方面考虑，由于系统的失效、节点的妥协、拒绝服务攻击等 原因，中心会暴露出单点失效的问题。 8 第一章研究的背景 ? i 2 v 3 吁n 图1 1 基于中心的信任模型结构图 2 基于分层的模型 这种模型与基于中心的模型类似，只不过这种方法把整个网络从逻辑上划分 成不同的域，在每个域中有自己的信任中心，这些中心联合完成安全访问控制服 务，如图1 2 所示。在 4 ，5 中对这种方法进行了详细讨论。这种模型虽然可以适 应大型的无线网，但是移动网络的服务特性使的这种方案表现出下面的一些不 足。 1 ) 频繁的移动引起了路由表的频繁更新，这样节点和本地c a 的联系延时在 当今社会中是不能容忍的“3 。除此之外，在h dh o c ! 网络中，本地c a 可能与被服务 的节点相隔多跳，而且c a 也在移动，这不但会使动态配置的网络变的复杂化，而 且也会使查找和追踪本地c a 变的更加困难。 2 ) 在容易出错的无线通信信道中，多跳通信使数据传播丢失率增加。这不 仅降低了成功率，而且还增加了平均服务延时。 3 ) 每个本地的c a 都有可能遭到单点妥协或者d o s 攻击。 口表示普通用户 。表示一个c a 圈1 2 层次信任模型 3 基于w e b 的信任模型 在基于w e b 的信任模型中，一个c a 和一个普通用户没有等级的区别。普通 用户之间依靠证书管理相互信任。每个用户的任务包括证书发布、证书撤销、其 9 第一章研究的背景 它用户的信任等级评价。图1 3 说明这种信任模型。 图1 3 基于w e b 的信任模型 这种信任模型比基于层次的模型提供了更多的灵活性，与分布式环境有着相 似的思想。但是这种类型的模型也存在一些缺陷：1 ) 这种模型比基于结构的层次 模型更容易受到不良代理渗透的影响；2 ) 在由信任个体组成的相对较大的团体 中，信任评价变的比较困难；3 ) 对于每个节点去维持一个比较庞大的信任评价链 表比较困难；4 ) 在网络成员之间对于一个实体的评价形成一致意见也比较困难。 4 分布式的信任模型 这种信任模型在加强a dh o c 网络安全性方面的文献比较多见。模型中，无论 节点加入网络的迟早，它们在服务方面都是平等的，没有本质区别。它们中的任 何节点都有为其本地邻居提供认证服务的能力。在这点上类似基于w e b 的信任模 型，但是在这类模型中没有评价机制。对于这种模型更详细的分析和描述参考第 三章。 1 3 本章小结 本章首先对移动a dh o c 网络的背景、特点、安全目标以及这种网络目前遇到 的问题进行了深入透彻的分析。接着对目前基于不同体系结构的信任模型优缺点 进行了分析，为第三章模型的提出奠定了基础。 1 0 第二章相关数学知识 第二章相关数学知识 2 1 相关签名算法的比较 目前常见的签名算法有r s a 、d s a 、e c c 等，它们主要基于以下三类数学 基础： a ) 因数分解问题( i f p ) ，如r s a ，r a b i n w i l l i a m s 算法等； b ) 普通离散对数问题( d l p ) ，如d s a 算法； c ) 椭圆曲线离散对数问题( e c d l p ) ，如e c d s a 算法。 表2 1 为不同密钥系统对密钥尺寸的需求，图2 1 为几种公钥系统抗攻击性比 较。从中可以看到对于相同的密钥位强度，e c c 系统要比其它几种公钥系统密钥 尺寸小得多。所以e c c 和其它几种公钥系统相比，其抗攻击性具有绝对的优势， 具有单位比特最高强度的安全性。如1 6 0 b i te c c 与1 0 2 4 h i tr s a 、d s a 有相同的 安全强度，而2 2 4 b i te c c 则与2 0 4 8 b i tr s a 、d s a 具有相同的安全强度。鉴于 r s an5 1 2 1 0 2 42 0 4 83 0 7 27 6 8 01 5 3 6 0 d s ap5 1 2 1 0 2 42 0 4 83 0 7 27 6 8 01 5 3 6 0 e c c n1 1 2 1 6 12 2 42 5 63 8 45 1 2 表2 1 不同密钥系统对密钥尺寸的需求 d c c 、r s t 、d s 抗攻击性比较 虢译时阳( 1 i p sy e a r ) 图2 1 几种公钥系统抗攻击性比较 e c d s a 是e c c 系统基本原理在数字签名中的应用，故e c c 系统的安全性就是 e c d s a 的安全性。p o i n t c h e v a l 和s t e m 嘲已经证明了基于椭圆曲线离散对数问题 第二章相关数学知识 且所使用的哈希函数是随机函数的前提下，对于选择明文攻击，e c d s a 在现有的 情况下是不可伪造的。b r o w n “”证明了在基本群为普通群且使用的散列函数是抗 冲突的前提下，e c d s a 本身是安全的。 2 2 有限域上的椭圆曲线签名算法 上面对基于不同数学难题的公钥密码体系进行了对比，可以看出在密钥长度 相当的情况下，椭圆曲线公钥密码系统比其它的公钥密码系统抵抗攻击的能力更 强，因此椭圆曲线密码系统可以使用较短的密钥满足较高的安全性需要。短密钥 使系统实现中对处理单元的计算能力，存储空间的大小，网上传输公钥需要的带 宽等资源的需求相对较小，因此在安全性相当的的情况下，椭圆曲线密码系统比 其它一些密码系统更适合a dh o c 网络。下面详细介绍有限域上的椭圆曲线签名算 法。 2 2 1 有限域、椭圆曲线简介 定义1 。”有限域是有限个元素的集合，元素的个数称为域的阶。设某个域的阶 为q ，则用g f ( q ) 来表示这个域。 定义2 “”1 设q = 2 m ，m 为正整数，则称g f ( q ) 为二进制域，表示为g f ( 2 m ) 。如 果q 是一个素数，则称g f ( q ) 为素数域，表示n g f ( q ) 。 定义3 “2 1 “1 设g f ( q ) 为任意域，椭圆曲线在g f ( q ) 上定义的方程如下： ，+ a x y + b y 2 x 3 + c + d x + e ，其中，a 、b 、c 、d 、e 为常系数。根据素数域 和二进制域各自的特性，其上的椭圆曲线为：素数域：y 2 = x 3 + a x + b ，二进制域： 厂+ x y = x 5 + a x 2 + b 。为使椭圆曲线应用于信息安全，对曲线上的点作了一些运 算定义。 定义4 “”3 椭圆曲线上两点p 、q 加法：过p 、q 两点的直线l 与椭圆曲线交于第三 点r ，设r ，关于曲线的对称轴的对称点为r ，则r = p + q 。如图2 2 所示。 定义5 “”1 椭圆曲线上无穷远点0 ：p + 0 = p ，p 十( 一p ) = 0 ，其中p 为曲 线上一点。由于椭圆曲线的点集构成一个阿贝尔群，可以说无穷远点0 就是这个 群上加法的幺元。 定义6 “。”1 椭圆曲线上点的倍乘：q = k p = p + p + + p ，其中，k 为倍数，p 曲线上一点。 定义7 m 。”1 椭圆曲线上的点的个数称为这条曲线的阶。 对于曲线上一点p ，如果存在一个数r ，使得r p = 0 ，则称r 为点p 的阶。基 于上述椭圆曲线的认识，下面将介绍椭圆曲线签名算法。 第二章相关数学知识 ， r ， 孑 彳f r p + 图2 2 椭圆曲线上加法的定义 2 2 2 具体的签名方案 椭圆曲线数字签名算法( e c d s a ) 是e l g m n a l 密码系统在椭圆曲线密码体 制的平移。其安全性是基于有限域上椭圆曲线加法群的离散对数问题( e c d l p ) 。 在同等的安全强度下，基于椭圆曲线数字签名方案与基于有限域上的乘法群的离 散对数问题的密码体制相比，对数据的要求更低，具有很大的优越性。关于椭圆 曲线数字签名算法的介绍如下“： 设p 是一个大于3 的素数或2 的幂次方，e 是定义在只上的椭圆曲线。设g 是e 上阶数为g 的一个点，使得在( g ) 上的离散对数问题是难处理的。设 p = o ，l ，a = 互x z ；，定义r = ( p ，q ，e ，g ，x ，y ) ：y = s k g ，其中1 卅q 一1 ， 值p ，q ，e ，g 是公钥，s k 为私钥，m 为待签名的信息。 对于k = ( p ，q ，e ，g ，s k ，y ) 和一个秘密随机数k ，1 k q l ，定义 其中 s 姆( 肚，) ( 肌，女) = p ，s ) s “g = ，v ) r = “m o dq j = k - 1 ( s h a - l ( m ) + s k ，、r o o dq ( 如果，20 或s = 0 ，应该为k 另选一个随机数) 对于m o ，1 ) + 和，s z ，验证是通过下面计算完成的： 第二章相关数学知识 w = s 1m o dq i = ws h a l ( m ) m o dq j = w r ( m o dq 、 ( “，v ) = i g + j y v e t x ( m ，( ，s ) ) = t ? l g e c z 1 , 1 m o dq = ， ( 2 ) 从( 1 ) 式中求出s ，代入( 2 ) 式中，如果( 2 ) 式成立，则通过签名验证。这 种情况下存在两个问题，一是为求s 需求k 的逆，二是不能实现消息恢复。下面介 绍无需求逆的方案“”。 2 2 3 无求逆椭圆曲线签名方案 在通常的椭圆曲线加密或签名过程中，求逆是主要的运算负担“”，从( 1 ) 式中得到签名s 需先求k 。( m o dq ) 。但对于大整数k 该运算很慢，使用扩展欧几 里得算法平均需完成0 8 4 3 1 0 9 2 ( 0 3 + 1 4 7 次除法1 ，下面介绍这种新的签名方程 在它的计算过程中不需要求逆的步骤。下面介绍具体的签名与验证方程： 签名方程( s e ) ： s 哦( m ，t ) = ( r ，s ) k g = ，v ) r = “m o dq 5 = 他一m ，s k ) m o dq ( 3 ) 验证方程( v s ) ： v e r k ( m ，( s ，r ) ) = t u r e 营( 蹭+ m r y ) m o dq( 4 ) 下面具体阐述该方案，步骤如下： 签名者在有限域g ( q ) 与椭圆曲线点群选定的基础上选择密钥s k ，由公开 基点g 得公钥y = s k g 并公开y 。 签名者选随机数k ，计算r = k g 和s = m r s k - k 。( s ，r ) 作为对i n 的签 名，并将( s ，r ) 连同m 发送给验证者。 验证者计算s g + m r y ，判断其值是否为r ，相等则签名成立，否则 图2 3 无求逆运算的e c c 签名方案流出 1 4 名成功 名不成功 第= 章相关数学知识 拒绝该签名。模拟程序流程如图2 3 所示。 文献中的实验结果显示上述方案能正确判断签名有效性，且所需计算更简单 相对方程( 1 ，2 ) 式的方案其系统耗时缩短7 2 8 ，因此这种方案在提供相同安全 性的前提下，对系统资源的要求更低，更适用于a dh o c 网络环境。 2 3 门限机制 门限机制这种思想 o h a d is h a m i r “7 1 和g e o r g eb l a k l e y “”两人分别于1 9 7 9 年 提出的，并o h g u ss i m m o n s “”做了广泛的研究。 a d is h a m i r 利用有限域中的多项式来构造门限方案“。选择一个素数q ，使 之比可能的份额数目和最大的可能秘密都大。共享密码时，需产生个次数为t - 1 的任意多项式。例如打算形成一个( 3 ，n ) 门限方案，则产生一个二次多项式： ( a x 2 + b x + m ) m o dq ，其中q 是一个比所有系数都大的随机素数。系数a 和b 为随 机选择，它们是秘密的，在完成份额分发之后便丢弃。m 是信息，素数q 必须公开。 份额通过计算该多项式在几个不同点上的值得到： k i = f ( x i ) 换句话说，第一个份额就是多项式在x = 1 处的值，第二个份额就是多项式在 x = 2 处的值，以此类推。 根据a ds h a m i r 的门限机制的思想，基于椭圆曲线l 拘l a g r a n g e “7 1 插值门限机制 的密钥份额生成算法如下： ( 1 ) 根据e c d s a ，计算生成椭圆曲线签名需要的密钥对 s k ，p k ，其中 p k = p ，q ，e ，g ，y ，且把p k 公开 ( 2 ) f p 是一个有限域，t 为门限，在f p 域上选一个t 1 次多项式，f ( x ) = a o + a lx + + a t 1 x t _ l 使得f ( 0 ) = s k 。 ( 3 ) 在f p 计算密钥份额p 。= f ( v i ) m o dq ，其中：i = l ，2 ，n ，v i 为节点标识。 2 4 门限签名服务 门限签名算法啪“是由门限机制和加密算法结合起来形成的，这种签名算法 主要应用于信任分享的方案中。一个( n ，t ) 门限加密方案允许n 个参与者共享 一个加密操作的能力( 如产生数字签名) ，所以任何t 个参与者共同才能完成这 个操作，然而对于至多是t 一1 个参与者来说，即使他们是共谋的也不能完成这个 操作。 在这个门限签名的方案中，n 个参与者组成了一个服务团体，这个团体中任 第二章相关数学知识 何成员都可以为其他人提供服务，因此参与者也可以称为服务者，被服务者可以 称为联合者。方案中，n 个服务者共享证书签名的能力。对于一个能容忍t 个妥协 者的服务来说，我们使用了( n ，t ) 门限密码方案。在这个方案中把系统的私钥 s k 分成t q 个部分( s k l ，s k 2 ，s k ) ，给每个服务者分配一个份额。我们称( s k l ， s k 2 ，s k n ) 是s k 的一个( n ，t ) 密钥共享。图2 3 说明了这个服务分配过程。 回圈圈 s e r v e r is e r v e r 2s e r v e r n 图2 3 一个门限签名服务的结构。 门限签名服务由n 个服务者组成。就整体而言，这个服务系统有一个密钥对( p k ，s k ) 。 公钥p k 是这个服务系统中的每个成员都知道的，然而私钥s k 被分成了n 个部分( s k ， s k 2 ，s l ( n ) ，每个服务者都拥有一个份额。每个服务者也都有一个自己的密钥对( o k ，s k ) 且公钥可以被所有的节点知道 对于一个证书签名的服务来说，每个服务者使用自己的密钥份额产生一个部 分证书并且把这个证书提交给证书的请求者。拥有t 个正确的部分证书，请求者 才能计算出一个完整有效的证书。然而，妥协的服务节点不能通过他们自己产生 一个完整有效的签名证书，因为他们能产生一个签名的证书至少需要t 个人。图 2 4 使用一个( 3 ，2 ) 门限签名说明怎样产生一个签名服务。 m 图2 4 门限签名 在一个e l i3 个人组成的服务体系中，假设( s k ，p k ) 是系统的密钥对。使用( 3 ，2 ) 门限密码方案，每个服务者v i 得到一个私钥的份额p i ，对于一个信息i t i 服务者 能使用它的份额产生个部分签名的信息 m 。良好的服务者2 和3 也会产生一个 部分签名并且把这个信息发送给服务的请求者c 。即使服务者2 没有成功的将部分签 名的信息发给c ，c 也能产生一个由系统私钥签名的信息 f 3 限值t ) 个节点，彼此之间 都是一跳邻居节点。它们相互协商产生椭圆曲线签名相关的公共参数信息，如f 口， p ，q 等。 2 每个节点v i 在f p 上选择一个随机的t l 阶多项式联x ) ： z ( z ) = 口j o + a j l x + - + a i ( t - 1 ) x 卜 v 一广播j 气= a k gm o d 口，其中k = 0 ，l ，t 。在这里用x i 代表a i o ，用y i 代表x i o o 每个v i 都计算密钥的小份额i = z ( 叶) m o dq r v j - 亍= j ：0 ，1 ，n ，且把万秘密的 发送给v j 。 3 每个v j 验证他接收到来自其它节点的小份额。对于所有的i = o ，l ，n ， 和= 以妒m o dq ( 5 ) k = o 、+ 如果对于一个索引号为i 的检测失败，那么v i 就广播一个对v i 的控告。 4 对于v j 来说，如果所有的小份额都能通过式( 5 ) 的检测，那么v i 根据公 式弓= i 计算它的密钥份额。 5 如果对节点v i 的控告大于设定的闽值时，那么认为节点v i 存在问题，他的 资格将被取消。节点都把接收到的i 设置成o ，x i = o ( 零) 和y i _ o ( 椭圆曲线无穷 远点) 第三章分布式认证模型 6 f f y = 咒m o dq ，系统私钥石= t m o dq ，但是任何节 点都不计算。每个节点v i 保存接收到的所有值，目的是为了验证以后密钥的重建。 经过上面的步骤，参与生成系统密钥的节点都有了自己的密钥份额，它们可 以利用自己的密钥份额通过公式( 6 ) 恢复出系统的私钥s k 。所以在设定门限值t 的时候，应该考虑到门限值对整个系统的安全影响。 豚= ( 弓- f ，( o ) m o dg ) ；s k i ( m o d 口) ( 6 ) 3 2 3 算法分析 3 2 3 1 算法运算代价分析 在a dh o e 网络中使用的设备限制了节点本地的存储容量的大小和它们的通 信能力。因此，在具体设置t 的时候，如果t 太小，那么a d h o c 网络中证书的安全 性就要受到威胁；如果t 太大， j l j z x a dh o c 络中又会对用户和网络造成负担。 在网络组建阶段系统密钥生成的通信费用可以用下面的式子估算： c ( t ，n ) = 配f n + 墨n n 其中，s b 表示广播x i k 的平均大小，s s 表示发送的每份密钥份额的平均大小，t 表示门限值，n 表示当时系统的节点数。 3 2 3 2 本算法和文献 2 2 中使用临时中心密钥产生算法等价性证明 由分布式密钥生成算法产生的系统密钥对及密钥份额和由临时中心产生的 系统密钥对，以及密钥份额，对于分布式认证是连贯的、致的。下面证明由分 布式密钥产生算法得到的密钥对及每个节点得到的密钥份额和由临时中心产生 的密钥对及密钥份额是等价的。 定理1 ：在相同条件下，由分布式密钥产生算法产生的密钥对和由临时中心直接 产生密钥对是等价的。 证明：假设每个节点v i 在f q 域上随机产生的t 一1 阶多项式为： f a x ) = q o + q i l x + + 一l x ”1 把各个节点的多项式联合起来产生的多项式等价于临时管理中心随机产生的 t - 1 阶多项式： ，( x ) = ( q o + 口2 0 + + o ) + ( a l l + q i + 。+ q 1 ) x + ( q l + 口2 l + + d m ) z 卜 5 嘞+ a l x + a , x 2 l 第三章分布式认证模型 所以，由各个节点产生的私钥份额联合起来等价于临时管理中心的私钥，也就是： 2 q o + a 2 0 + 。+ o n o 在有临时中心的密钥产生算法中，基于椭圆曲线的公钥为p k = a o gr o o dq ( 含 义与2 2 2 的相同) 。在分布式密钥产生算法中，每个节点v i 产生的公钥份额为： p k i = a i o g r o o d q ，所以由分布式产生的公钥为： p k j = p k i + p k 2 + + p k 。 = q o g + a 2 0 g + + 口n o g = ( a t o + 啦o + 。+ o ) g 。a o 。g = p k 综上，由分布式产生的公钥与由临时管理中心产生的密钥对是等价的。 定理2 ：在相同条件下，设每个节点v i 根据分布式密钥产生算法产生的密钥份额 为p i ，由临时管理