移动自组织网络的认证方法和系统

暂无

技术领域\n本发明涉及通信领域，特别涉及移动自组织网络的分层分布式身份认证方案。\n背景技术\n移动自组织网络(Mobile Ad Hoc Network，简称“MANET”)，又称为移动ad hoc网络，是一种特殊的没有有线基础结构支持的移动网络，它是由一组带有无线收发器的移动终端所组成的一个无基站多跳步临时性自治网络系统。这种网络的建立快捷、灵活，不受有线网络的约束，它主要应用在军事战场、抗洪救火、无法布线等特殊和紧急环境下，并具有一般通信网络所没有的一些特点：网络的自组织性；动态的网络拓扑结构；有限的无线传输带宽；移动终端的局限性；路由的多跳性；易受攻击等等。由于它的特殊应用，MANET已成为无线通信领域的研究热点，完善的安全机制则是它应用的重要前提。\n移动自组织网络出现之初指的是一种小型无线局域网。这种小型局域网的节点之间不需要经过基站或其它管理控制设备就可以直接实现点对点的通信。而且当两个通信节点之间由于功率或其它原因导致无法实现链路直接连接时，网内其它节点可以帮助中继信号，以实现网络内各节点的相互通信。由于无线节点是在随时移动着的，因此这种网络的拓扑结构也是动态变化的。它们之间的通信模式也就无法直接照搬目前有基础设施的通信网的通信模式。\n自组织网络的组网有两种方式：平面结构和分级结构。平面结构中，所有结点的地位平等，所以又称为对等式结构。而分级结构中，网络被划分为簇。每个簇由一个簇头和多个成员节点组成。簇头结点负责簇间业务的转发。在平面结构中，每一个结点都需要知道到达其它所有结点的路由。由于结点的移动性，维护这些动态变化的路由信息需要大量的控制消息。网络规模越大，路由维护和网络管理的开销就越大，网络的可扩充性较差。分级结构克服了平面结构可扩充性差的缺点，网络规模不受限制。分级结构中，簇头的功能相对较强，而普通节点的功能比较简单，基本上不需要维护路由。这大大减少了网络中路由控制信息的数量。此外，分级结构易于实现节点的移动性管理和保障通信业务的服务质量。因此，当网络规模较大并需要提供一定的服务质量保障时宜采用分级网络结构。\n网络安全是自组织网络中的一个大问题。Ad Hoc网络的特点之一就是安全性较差，易受窃听和攻击。因此，需要研究适用于Ad Hoc网络的安全体系结构和安全技术。目前在安全方面主要集中在有线加密、密码协议安全性分析与攻击方法的研究、消息认证和完整性技术研究等几个方面。\n移动自组织网络中，对移动用户身份的认证是保证网络正常工作的重要组成部分，身份认证可以有效地防止假冒攻击。传统的网络通常需要一个信任的认证中心来提供密钥管理服务，但移动自组织网络是一个无中心的分布式网络，所有的用户都是平等的。而且由于拓扑结构的动态变化，网络用户也呈现一定的流动性，无法保证某个用户能够固定地充当可信中心。特别是当移动自组织网络用于军事目的时，单个的可信中心会成为网络的关键点，降低了网络的抗毁性。\n如前所述，当移动自组织网络的规模比较大时，简单的平面网络的认证机制已经不能满足网络的认证需求。由于基于簇的网络结构比平面网络结构有许多优点：分簇促进了空间资源的重用，极大地提高了系统的容量；分簇能够减少寻找路由时的广播包；分簇能够减少在网络内广播拓扑更新的消息的总量；分簇能够加强网络管理和减少对普通成员的计算和存储能力的需求。因此分簇的分层网络结构更适用于移动自组织网络。对于分簇MANET网络结构，需要分层分布式身份认证方案的支持。\n当移动自组织网络的规模比较大时，网络需要进行分层次的管理，简单的平面网络的认证机制已经不能满足网络的认证需求，分层的分布式认证是一种很好的解决方案。现有的认证方案多基于GQ门限签名和Hash链认证方法。\n门限群签名是门限密码学的主要研究内容之一，最初由Desmedt等学者提出。现有的数字签名方案主要分为基于离散对数密码系统和RSA密码系统两大类，GQ方案属于后一种，即基于大整数分解的难题。GQ签名方案提出之后，得到了广泛的关注。\n尽管GQ签名方案收到了较多关注，但关于GQ门限签名的论文却很少。这主要是由于GQ签名是属于门限RSA签名的一种，其安全性是基于大整数分解的难题。首先，为了保护RSA的模数N的因子分解，不能让参与签名的成员知道。其次，不是域，不能用一般的秘密共享的办法来共享签名密钥d。Liu在2003年提出了一种基于GQ签名的门限群签名方案，详细步骤如下：\n初始阶段：令n＝p·q，m＝p′·q′，并且p＝2p′+1，q＝2q′+1，p、q、p′、q′都是大素数。Qn是zn*中所有二次剩余的集合，g是Qn的一个生成元。可知Qn的阶是m，所有的运算都在集合Qn之中，而幂运算在Zm之中。任选一个在Zm上的多项式f(x)＝atxt+...+a1x+a0，令$s=g^{a_0}\mathrm{mod}n$是主密钥，si＝gf(i)mod n是分配给每个用户Pi的子密钥。假设网络中有l个用户，令L＝l！。随机选择一个整数e，与L2互素，并计算v＝1/semod n。参数(n，g，e，v，L)公开，其它保密。\n部分签名生成阶段：\na.首先所有用户执行一次密钥协商协议。每个用户Pi随机选择一个多项\n式fi(x)＝aitxt+...+ai1x+ai0，计算fi(j)和$A_i=g^{a_{i0}e}\mathrm{mod}n,$并广播给其它用户，j∈{1，...，l}。每个用户得到各自的份额$f_r\left(i\right)=\underset{j=1}{\overset{l}{\Sigma }}{f}_j\left(i\right),$并计算$r_i=g^{f_r\left(i\right)}\mathrm{mod}n,$这里$f_r\left(x\right)=\underset{i=1}{\overset{l}{\Sigma }}{f}_i\left(x\right).$并且，所有用户都得到公共参数$y=\underset{i=1}{\overset{l}{\Pi }}{A}_i=g^{f_r\left(0\right)e}\mathrm{mod}n.$\nb.所有用户再次执行一次密钥协商协议。这次协商中，每个用户Pi任意选择的多项式常数项为0，即fi(x)＝aitxt+...+ai1x，计算fi(j)并广播给其它用户。每个用户都得到各自的份额$f_c\left(i\right)=\underset{j=1}{\overset{l}{\Sigma }}{f}_j\left(i\right),$并计算$c_i=g^{L{f}_c\left(i\right)}\mathrm{mod}n,$这里$f_c\left(x\right)=\underset{i=1}{\overset{l}{\Sigma }}{f}_i\left(x\right).$\nc.所有用户都计算σ＝H(y，M)，其中M是要签名的消息，H(.)是单向的hash函数，并计算出各自的部分签名$z_i={\left(r_i{s}_i^{\sigma }\right)}^L{c}_i\mathrm{mod}n.$\n门限群签名生成阶段：\na.当t+1个以上的用户同意签名时，任意t+1个用户合作，计算$z^{\prime }=\underset{j=1}{\overset{t+1}{\Pi }}{z}_{i_j}^{{\lambda }_{i_j}L}\mathrm{mod}n,$是任意t+1个用户的签名，是相应的拉格朗日插值系数。\nb.存在整数a和b，令L2a+eb＝1，计算出z＝z′a·(y/vσ)bmod n。签名就是(z，σ)。\n群签名验证阶段：验证者计算y′＝zevσmod n。如果σ＝H(y′，M)，签名有效。\n另外一种效率更高的Hash链的认证方法，可以提高密钥的使用效率，Neumann提出了采用多个Hash链作为密钥的方法HORSE，而不是只使用一对公钥和密钥，该方案详细步骤如下：\n令m是要签名的消息。整数t和l都是安全系数，令T是0到t-1的整数集合。选取一个强单向函数H(·)，能够将输入的任意长度的数转换成k个小于t-1的整数，也就是klog2 t≤|H(·)|，这里|H(·)|表示为Hash函数H(·)输出的二进制长度。f(·)也是一个Hash函数。选择t个l位长的值s<0，0>，s<0，1>，...，s<0，t-1>，并用它们构成t个长度为d的Hash链，这些Hash链被用作密钥。初始的密钥SK0和公钥PK0分别是：\nSK0＝(s0，s1，...，st-1)＝(s，s，...，s)\nPK0＝(v0，v1，...，vt-1)＝(f(s)，f(s)，...，f(s))＝(s，s，...，s)\n其中si，j＝fi(s<0，j>)。定义u是Hash链中密钥的序号。Hash链的建立如图1所示。\n签名时，签名者先计算h＝H(m)，并把h分成k个长度log2t的字串{h1，h2，...，hk}，并将hj(1≤j≤k)转换成k个整数ij(1≤j≤k)，并根据当前已经出示的密钥，m的签名就是。假设公钥是(v0，v1，...，vt-1)，并且序列号从1开始计算。签名就是(s，s，...，s)的一个子集。验证此签名时，验证者用同样的方式计算出字串{h1，h2，...，hk}，然后分别转换成整数ij(1≤j≤k)，并验证$v_{i_1}=f^u\left(s_{i_1}\right),$$v_{i_2}=f^u\left(s_{i_2}\right),$...，$v_{i_k}=f^u\left(s_{i_k}\right)$是否成立。如果这些等式成立，则验证通过。\n签名每次使用k个密钥，而每一序号对应t个密钥。当某一序号的密钥大部分使用过以后，序列号加1，密钥向前推进。\n在实际应用中，存在以下问题：Liu提出的基于GQ签名的门限群签名方案计算量太大，对于移动自组织网络的资源环境特点，该方案不适合应用于移动自组网。\n根据该GQ门限签名方案的步骤，容易看出：在部分签名生成阶段，网络中的所有用户执行了两次密钥协商，并且需要计算5l次幂指数函数；而在群签名合成阶段，共需计算t+4次幂指数函数；在群签名验证阶段需要计算2次幂指数函数。可见对于计算资源的要求非常高，而移动自组织网络的特点是不存在基站、网关等处理能力强的网络节点，所有节点都是对等的，顶多存在簇头具有更强的处理能力，因此该方案很难在实际中应用于移动自组织网的安全认证。\n另外，该GQ门限群签名方案是一种针对一般信息签名的协议，而在分簇MANET的分层认证方案中要把群签名作为身份证书颁发给用户，还要考虑到身份证书的保密性和重用，因此该方案在这方面也存在不足。\n而上述第二种基于Hash链的认证方案若应用在移动自组织网络认证中，将存在两个致命的问题：首先，同步问题难以解决，容易引起同步攻击，移动自组织网络中所有节点需要通过多跳通信，认证相关的信息需要在所有节点之间进行同步，该方案对信息同步要求太高，从而降低了网络可靠性和安全；其次，所述Hash函数H(·)输出位数多，直接导致计算量增大，同样地会对MANET的处理资源提出挑战。\n最后，上面所述的方案都是各自给出一种认证方法，缺乏分簇移动自组织网络的分层分布式认证的整体方案，还需要一种能够在实际移动自组织网络环境中应用的分层认证方案。\n造成这种情况的主要原因在于，上述两种方案都只解决了单纯的签名或认证问题，没有给出完整的针对分簇移动自组织网的分层认证方案；而且其中，由于GQ门限签名方案的理论基础缺陷，导致该方案对计算资源的需求太大；而基于Hash链的HORSE方法也由于Hash函数输出位数太多导致计算量太大而无法实现，同时其方案的操作方式还对同步要求太高。\n发明内容\n有鉴于此，本发明的主要目的在于提供一种移动自组织网络的分层认证方法和系统，使得分簇移动自组织网的分层分布式认证方案得以实现。\n为实现上述目的，本发明提供了一种移动自组织网络的分层认证方法，所述移动自组织网络采用分簇组网结构，每个簇包含簇头节点，簇间通信经由簇头，包含以下步骤：\n系统对初始的所有节点进行初始化，按新门限群签名协议，给各节点颁发各节点自身的证书、子密钥；\n当新节点加入时，由规定数目的簇头节点根据其子密钥，按所述新门限群签名协议，联合给该新节点颁发证书；\n节点依据所述证书通过所述新门限群签名协议进行身份认证、实现簇间通信；\n其中，所述新门限群签名协议为基于GQ门限群签名理论改进的协议，与所述GQ门限群签名的区别包括：在子签名生成阶段计算2t次幂指数函数，t为网络中参与群签名的成员数目，群签名合成时不计算幂指数函数，签名验证时计算2次幂指数函数，而部分幂指数运算在网络中同时进行或事先进行。\n其中，按所述新门限群签名协议，首先确定以下参数：N、p、q、m、p′、q′、g、d、v、x、y和hash()，其中，\nN＝p·q，p和q是安全大素数，p′和q′为大素数，且有p＝2p′+1、q＝2q′+1，m＝p′·q′；\n用ZN*表示N的最小剩余系，用QN表示ZN*中所有平方剩余数构成的乘法子群，$g\in Z_N^{*}$是子群QN的生成元；\n随机选取d、v使其均与m互素，群密钥为x＝gd modN，群公钥为y，且xv·y≡1modN；\nhash()为选定的强单向哈希映射函数；\n按所述新门限群签名协议，在初始化时，系统选定一个t-1阶的多项式f(·)，其常数项d＝f(0)modm为整个系统的根密钥，然后把子密钥si＝gf(i)modmmodN分发给每个群成员，1≤i≤t，t为参与群签名的成员数目；按所述新门限群签名协议，任意t个成员进行群签名时，对给定消息M，每个参与群签名成员随机选择一个整数ki，计算并广播每个参与群签名成员再计算及h＝hash(M，R)，得到各自的子签名\n按所述新门限群签名协议，被群签名者获得t个参与群签名成员的子签名ci后，计算生成群签名(c，h)及证书(M，c，h)；\n按所述新门限群签名协议，依据所述群签名证书(M，c，h)进行身份认证时，验证者计算R′＝cvyhmodN，且判断h＝h(M，R′)是否成立，如果成立则身份认证成功，否则身份认证失败。\n本发明还公开了一种移动自组织网络的认证系统，包含：\n对初始的所有节点进行初始化，按新门限群签名协议，给各节点颁发各节点自身的证书、子密钥的单元；\n规定数目的节点，用于在新节点加入时，根据子密钥，按所述新门限群签名协议，联合给该新节点颁发证书；该新节点依据颁发的证书通过所述新门限群签名协议进行身份认证、实现通信；\n其中，所述新门限群签名协议为基于GQ门限群签名理论改进的协议，与所述GQ门限群签名的区别包括：在子签名生成阶段计算2t次幂指数函数，t为网络中参加签名的簇头个数，群签名合成时不计算幂指数函数，签名验证时计算2次幂指数函数，而部分幂指数运算在网络中同时进行或事先进行。\n其中，所述移动自组织网络采用分簇组网结构，每个簇包含簇头节点，簇间通信经由簇头，\n联合给所述新节点颁发证书的所述规定数目的节点都是簇头节点。\n通过比较可以发现，本发明的技术方案与现有技术的主要区别在于，采用分簇移动自组织网络组网结构，提出分层分布式身份认证方案，在簇间通信中采用改进的新门限群签名协议，该协议改进了原先的基于GQ的门限群签名方法，降低幂指数计算次数，提高计算并行性，降低处理资源要求；\n在初始化时由系统统一颁发证书、子密钥，拥有各自子密钥的达到一定数目的簇头即可联合恢复系统密钥，从而进行群签名给新加入节点颁发证书，且采用多跳串行通信的方式实现联合群签名；\n对于普通的节点间簇间通信，簇头仅起到路由、转发作用，身份认证由节点根据证书进行；而对于重要的簇间通信，簇头也参与身份认证，簇头之间相互进行身份认证；节点间进行身份认证时，才还用零知识认证体系，使得被认证方不需向认证方公开任何密钥相关信息；\n簇内通信中，采用HORSC协议实现平面网络式身份认证，该协议实现了效率更高的Hash链认证模式，充分利用了簇头的处理资源，由簇头统一控制簇内同步和公钥更新，解决了同步问题；\n由于簇头与节点的处理任务区别，设置所有加入自组织网络的节点为普通和加强两种工作状态，分别对应于普通节点和簇头节点身份，以配合实现分层分布式认证方案且充分利用网络处理资源。\n这种技术方案上的区别，带来了较为明显的有益效果，即分层分布式身份认证方案按改进的新门限群签名协议实现簇间身份认证、按HORSC协议簇内身份认证，完全解决了分簇组网的移动自组织网络的身份认证问题；\n其中，改进的新门限群签名协议向对于在现有基于GQ门限群签名技术，在子签名生成阶段只需次幂指数计算，群签名合成时不需要计算幂指数计算，签名验证时只需2次幂指数计算，而且部分幂指数运算可以在网络中分布式进行或事先进行，在分簇网络进行联合群签名时身份证书的逐跳生成阶段需要计算次幂指数计算，大大减少了计算量，降低了对节点处理资源的要求，使得簇间身份认证容易实现；\n在给新节点联合颁发证书时，采用串行多跳通信实现参与群签名簇头之间的广播，不仅降低了网络通信次数，节省网络资源，而且减少通信的回合将会加速协议的执行，提高网络反应速度；\n簇间身份认证时采用零知识认证方式，被认证方无需向认证方公开相关信息，确保认证系统的安全程度，实现了身份证书的重用，延长了证书的使用时间，提高了证书的使用效率；\n簇间身份认证时，簇头可以根据通信的安全级别确定是否加入身份认证，在重要通信中，簇头之间需要进行身份认证，进一步确保簇间身份认证的安全；\n簇内基于Hash链的HORSC协议在生成字串时插入随机数到字串中，不仅实现了相同等级的安全程度，而且减少了Hash函数的输出位数，从而直接减少一半计算量，大大降低处理资源的要求，提高可行性；\n基于Hash链的HORSC协议簇内认证充分利用了簇头地处理资源，由于簇头的严格控制同步数，保证同步数的增长快于用户认证服务的最大频率，并且簇内距离短，也不会出现大的延迟，为基于Hash链的认证提供了一个良好的环境，不但加快了处理速度，而且解决了簇内同步问题，提高了认证效率。\n附图说明\n图1是基于Hash链的身份认证方案中的Hash链和初始公钥、密钥示意图；\n图2是根据本发明的第一实施方式的移动自组织网络分簇组网结构和分层分布式认证方案示意图；\n图3是根据本发明的第三实施方式的多个簇头进行联合群签名给新节点颁发证书的流程示意图。\n具体实施方式\n为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。\n移动自组织网络最基础的组网方式是平面式组网，该方式所存在缺陷使其无法得到推广和发展，而分簇式组网得到广泛的认可。特别是当移动自组织网络的规模比较大时，网络需要进行分层次的管理，简单的平面网络的认证机制已经不能满足网络的认证需求，分层的分布式认证是一种很好的解决方案，本发明基于这个出发点，提出一种分层分布式认证解决方案，分别采用改进的新门限群签名协议实现簇间认证，而采用基于Hash链的HORSC协议实现簇内平面式认证。簇间认证采用约束条件较少的更为强壮的GQ签名方案，而簇内则采用更为高效但需要严格管理的Hash链的认证方案，由簇头负责本簇内认证的管理。对于新用户的证书，则采用一种门限群签名的方式颁发，由计算能力较强的簇头联合颁发。从而不但降低了对节点处理能力的要求，而且提高了认证速度和效率，增强分层分布式认证方案可行性。\n本发明的第一实施例首先给出分层分布式认证方案的基本架构，主要包括初始化、颁发新节点证书、簇间认证、簇内认证四个环节。移动自组织网络采用分簇组网结构，每个簇包含簇头节点，簇间通信经由簇头。图2示出了分层分布式认证方案的架构。\n在系统对初始的所有节点进行初始化时，按新门限群签名协议，给各节点颁发其证书、子密钥，其中系统需要首先确定与新门限签名协议相关的参数，然后进行计算得到各个节点证书，并秘密发送给各个节点，同时为了实现新节点加入时联合颁发证书，需要给每个节点发送一个子密钥，子密钥的设计需要根据新门限群协议事先约定的参数，比如参与联合颁发证书群签名的簇头个数，来计算子密钥使得超过该数目的子密钥即可联合恢复系统密钥；\n当新节点加入时，由规定数目的簇头节点根据其子密钥，按所述新门限群签名协议，联合给该新节点颁发证书，其中簇头需要召集达到系统设定的参与群签名簇头数目个簇头，然后按照该协议与新节点交互，通过分布式计算和通信得到新节点的证书，该证书可以根据协议用相同的方法进行身份认证；\n节点依据证书通过新门限群签名协议进行身份认证、实现簇间通信，拥有证书的节点之间即可实行身份认证，认证的方法与传统的门限群签名一致；\n而在簇内，节点只需按哈希获得随机子集(HORSC)协议进行身份认证、实现簇内通信，该协议能够高效地实现平面式认证，充分提高簇内通信的效率，同时确保簇内通信安全。\n本发明的第二实施例首先给出了基于GQ门限群签名理论改进的新门限群签名协议实现细节，该方案借鉴GQ门限群签名的思想，设计一种新颖的(t，n)门限群签名方案，其计算成本低于Liu的方案。\n首先确定以下参数：N、p、q、m、p′、q′、g、d、v、x、y和hash()，其中，N＝p·q，p和q是安全大素数，p′和q′为大素数，且有p＝2p′+1、q＝2q′+1，m＝p′·q′；用ZN*表示N的最小剩余系，用QN表示ZN*中所有平方剩余数构成的乘法子群，$g\in Z_N^{*}$是子群QN的生成元；随机选取d、v使其均与m互素，群密钥为x＝gdmodN，群公钥为y，且xv·y≡1modN；hash()为选定的强单向哈希映射函数。\n在初始化时，系统选定一个t-1阶的多项式f(·)，其常数项d＝f(0)modm为整个系统的根密钥，然后把子密钥si＝gf(i)mod mmod N分发给每个群成员，t为参与群签名的成员数目；任意t个成员进行群签名时，对给定消息M，每个参与群签名成员随机选择一个整数ki，计算并广播$r_i=k_i^v\mathrm{mod}N,$每个参与群签名成员再计算$R=\underset{i=1}{\overset{t}{\Pi }}{r}_i,$及h＝hash(M，R)，得到各自的子签名$c_i={s_i^{h·\underset{j=1,j\ne i}{\overset{t}{\Pi }}\frac{-j}{i-1}}k}_i\mathrm{mod}N;$于是t个以上成员即可通过Lagrange插值算法恢复出群密钥x。\n签名合成时：被群签名者获得t个参与群签名成员的子签名ci后，计算$c=\underset{i=1}{\overset{t}{\Pi }}{c}_i\mathrm{mod}N,$生成群签名(c，h)及证书(M，c，h)。\n签名验证时：依据所述群签名证书(M，c，h)进行身份认证时，验证者计算R′＝cvyhmodN，且判断h＝h(M，R ′)是否成立，如果成立则身份认证成功，否则身份认证失败。\n可见该方案与现有Liu的基于GQ签名方案区别在于，通过计算顺序和结构的改进，减少了计算量，在子签名生成阶段只需要总共计算2t次幂指数函数(假设网络中有t个簇头参加签名)，群签名合成时不需要计算幂指数函数，签名验证时需要计算2次幂指数函数，而有些幂指数运算可以在网络中同时进行或事先进行，如计算$r_i=k_i^v\mathrm{mod}N.$\n该改进的新门限群签名方案的使用方法如下：待签名者发送消息给每个签名者请求群签名，每个签名者签名后发送回子签名，待签名者将所有子签名合成得到群签名，认证时发送该消息和群签名给认证者，认证者对其进行身份认证。\n本发明的第三实施例基于第二实施例所实现的新门限群签名方案给出具体的簇间身份认证实现方案。\n首先在系统初始化时需要做的步骤如下：确定协议规定的参数、生成每个初识节点的证书、生成每个节点的子密钥。\n系统充当可信的密钥分发者(dealer)为每个初始阶段的移动节点颁发各自的子密钥，首先系统选定参数N、p、q、m、p′、q′、g、d、v、x、y和hash()。\n初始阶段，每个成员Pi的身份证书由可信中心(系统)颁发。可信中心选择成员Pi的某一公开信息作为证书内容Mi，如成员ID(身份)号码，用户名或E-mail等能代表用户的唯一信息。再选择一个随机数bi，并计算$B_i=b_i^v\mathrm{mod}N,$hi＝hash(Mi，Bi)，$S_i\equiv b_i·x^{h_i}\mathrm{mod}N,$生成该节点用户的证书(Mi，Si，Bi)，最后将证书(Mi，Si，Bi)秘密地发送给成员Pi。\n子密钥的分发时，假设最终所希望产生的是(t，n)门限方案，所以密钥分发者首先任意选择一个次数为t-1的多项式，f(x)＝at-1xt-1+…+a1x+d，其中x代表自变量、常数项d为整个系统的根密钥。对于系统内的每个成员Pi，分配给唯一的身份号码i，并计算Pi的子密钥si＝gf(i)modmmodN。密钥分发者将si秘密地传送给Pi。这样每个用户得到系统颁发的一个子密钥，子密钥与之后的群签名有关，系统在初始阶段根据群签名的方案产生子密钥，在之后需要进行联合群签名时用到子密钥。\n初始化之后系统即可进行身份认证，但是由于移动自组织网络存在节点变动问题，因此必须处理新加入节点的证书颁发，这就是新门限群签名协议所解决的关键问题。移动自组网是一个动态变化的分布式网络，新入网的用户要依靠移动网络中现有的成员来颁发用户的身份证书。对于新用户的证书，采用门限群签名的算法，由计算能力较强的簇头联合颁发。\n当新节点PN′加入网络时，首先要与一个相近的簇头联系。如果此簇头同意PN′加入，则PN′就成为此簇的一个新成员。如果此簇头不同意PN′加入，PN′必须继续移动并申请加入其它簇，直到本簇簇头CHN′同意其加入本簇。\n当PN′成为一个簇中的成员后，他可以向本簇内的簇头CHN′请求颁发证书，并发送一个整数gamodN，其中a是随机数。如果CHN′在一定时间内认定PN′是可靠的，他就接受PN′的申请，并将gamodN转发给其他簇头。当超过一定数量的簇头接受PN′的申请，就可以向PN′联合颁发证书。\n当网络中任意一个簇头CHi收到请求并同意参与认证时，CHi返回两个数和$K_i=k_i^v\mathrm{mod}N,$ri和ki是CHi产生的随机数。当CHN′收到超过t-1个簇头的回应之后，CHN′任意选择t-1个簇头来共同给PN′颁发身份证书，并且CHN′也同样发送两个随机数给PN′。为方便起见，包括CHN′在内，定义这t个参与认证的簇头{CH1，CH2，…，CHt}构成的集合为A。\nPN′保存集合A中成员返回的随机数，并计算$R=\underset{i=1}{\overset{t}{\Pi }}{K}_i\mathrm{mod}N.$PN′把(M、{A}、R)发送给CH1(即A中第一个节点)，{A}表示集合A中的节点序列号码。\nCH1计算h＝hash(M，R)，${d^{\prime }}_1=g^{a·r_1}{s}_1^{h·\underset{j\in A,J\ne 1}{\Pi }\frac{-j}{1-j}}{k}_1\mathrm{mod}N,$s1是CH1拥有的子密钥。随后CH1把(d′1，M，{A}，R)发送给CH2。CH2计算出h和${d^{\prime }}_2=g^{a·r_2}{s}_2^{h·\underset{j\in A,J\ne 2}{\Pi }\frac{-j}{2-j}}{k}_2\mathrm{mod}N,$然后CH2将(d′1d′2，M，{A}，R)传送给下一个节点。依此类推，最后一个认证节点CHt计算出${d^{\prime }}_t=g^{a·r_t}{s}_t^{h·\underset{j\in A,J\ne t}{\Pi }\frac{-j}{t-j}}{k}_t\mathrm{mod}N,$并将$S^{\prime }=\underset{i=1}{\overset{t}{\Pi }}{d^{\prime }}_i\mathrm{mod}N$返回给PN′。\n整个认证的示例过程如图3所示。PN′收到CHt返回的S′后，计算群签名$S=S^{\prime }·{\left(g^{a\underset{i=1}{\overset{t}{\Sigma }}{r}_t}\right)}^{-1}\mathrm{mod}N,$最后获得的有效签名为S。因此，PN′就得到联合颁发的身份证书(M，S，R)。\n当PN′获得新证书后，就能在以后的簇间通信中用证书来证明身份。簇间通信的证书使用方法与前述一样。移动自组网中的用户在通话前，必须进行身份认证，安全有效的身份证书可以防止假冒攻击。身份证书使用时，验证者收到(M，S，R)。先计算h＝hash(M，R)，然后计算R ′≡SvyhmodN。如果R′＝R，则证明签名(S，R)是移动自组网的成员对消息M的有效签名。\n可以看出，该门限群签名的簇间认证充分利用了簇头的强计算能力和网络通信多跳的特性。新入网用户的身份证书是一定数量的簇头联合工作，通过多跳通信完成的。簇头的计算能力较强，因而对于证书颁发的迅速完成极为有利，并且避免了对普通节点的影响。考虑到无线通信的特点，每次通信的控制信息、每次通信无线电台的收发转换延迟以及一次成功通信的平均发送次数等，减少通信的回合将会加速协议的执行。因此本方案在新入网用户证书合成阶段采用了逐跳通信的方式，减少了通信的回合，降低了网络通信量，节省了网络带宽。\n考虑到一般的认证方法存在公开部分信息的安全隐患，因此本实施例还采用了零知识身份认证协议，即被认证方无需向认证方公开信息，该协议规定如下认证步骤：\n假设移动网中用户A与B要进行通话。首先A要求B出示身份证书，A先发送一个随机数u给B。B收到随机数u后，返回(MB，SBumodN，RB modN)给A。A收到B返回的消息后，计算hB＝hash(MB，RB modN)和$R^{\prime }\equiv S^{u·v}{y}^{u·h_B}\mathrm{mod}N,$并验证是否$R^{\prime }\equiv R_B^u\mathrm{mod}N.$若等式成立，则A相信B的真实性。反过来，B也要求A出示身份证书，具体过程同上面一样。\n这个协议既验证了身份，又避免了泄漏身份证书，是一个简单的零知识证明协议，实现了身份证书的重用。\n由此，当不同簇的节点之间进行普通簇间通信时，经由各自的簇头进行路由和转发，节点之间依据各自证书按新门限群签名协议进行身份认证即可。\n当不同簇的节点之间进行重要的簇间通信时，经由各自的簇头进行路由和转发，簇头可以提供签名来保证本簇内成员的身份，簇头之间也需要身份认证。假设A和B是不同的簇的成员，CHA和CHB分别是他们的簇头。现在A和B进行一次重要的通信，A和B的认证需要各自的簇头的签名。双方认证时，B首先发送给A一个随机数u，A返回(MA，SAu modN，RA modN)给B，其中(MA，SA，RA)是A的身份证书。此时，CHA可以计算$h_1=\mathrm{hash}(M_{{\mathrm{CH}}_A},h_A),$hA＝hash(MA，RA)，并在转发A发送给B的消息时，附加上自己的签名$(M_{{\mathrm{CH}}_A},S_{{\mathrm{CH}}_A}^{h_1}\mathrm{mod}N,R_{{\mathrm{CH}}_A}),$其中$(M_{{\mathrm{CH}}_A},S_{{\mathrm{CH}}_A}\mathrm{mod}N,R_{{\mathrm{CH}}_A})$是CHA的身份证书。CHB在收到CHA转发的消息后，首先确认CHA的签名是否有效。如果签名有效，CHB在转发信息时附加上一个簇内的消息，证实CHA已经对A的真实性提供了保证。这样，B收到A的证书，CHA的签名和CHB的确认，就可以确认A的身份。\n从上述整个簇间认证方案上看，当改进的新门限群签名方法应用于移动自组织网络的分布式认证时，为了保证身份证书的保密性，计算量有所增加，但还是比现有方案效率高。请求颁发身份证书阶段总共需要计算2t+1次幂指数函数，身份证书的逐跳生成阶段需要计算2t+1次幂指数函数，身份证书验证时需要计算2次幂指数函数，计算量均有减少。\n簇间通信认证方式为了满足分簇的结构因此较为复杂，但在簇内通信环境中，没有必要采用如此复杂的认证方式，可以采用较为简单的Hash链平面式认证方式。本发明的第四实施例改进了HORSE认证协议，提出新的哈希获得随机子集(Hash to Obtain Random Subsets of Clusters，简称“HORSC“)协议，高效实现簇内认证。\n首先，Hash链需要一个动态的认证信息M，M包含每个成员的唯一信息，还包含一些变化的信息，如时间戳、同步数以及验证方发送给被验证方的随机数。\nHORSC系统参数包含：整数t′和l都是安全系数；选取一个强单项函数H(·)，能够将输入的任意长度的数转换成k个小于t′-1的整数，也就是klog2t′≤|H(·)|，这里|H(·)|表示为Hash函数H(·)输出的二进制长度；一组哈希函数fi(·)，(0≤i≤t′-1)；以及同步数u。\n然后，选择t′个l位长的值s<0，0>，s<0，1>，…s<0，t′-1>，并用它们构成t′个长度为d的Hash链。这些Hash链被用作密钥。初始的密钥SK0和公钥PK0分别是：\nSK0＝(s0，s1，…，st′-1)＝(s，s，…s)、\nPK0＝(v0，v1，…，vt′-1)＝(f(s)，f(s)，…f(s))＝(s，s，…s)\n其中si，j＝fi(s<0，j>)。\n假设A要向B证明身份，执行该认证协议时，B首先发送一个长度为klog2t′比特的随机数v给A。\nA将自己的身份信息、随机数v、同步数u以及时间戳组成一个签名消息M，计算h＝H(M)，并把h分成k个长度log2t的字串{h1，h2，…，hk}。假设时间戳是大整数，计算时间戳对k的余数a，将随机数v插入到字串h1+a的后面，这样就形成了2k个长度log2t′的字串{h1，h2，…，h2k}。\n将hj(1≤j≤2k)转换成2k个整数ij(1≤j≤2k)，并根据当前的同步数u，M的签名就是假设公钥是(v0，v1，…，vt′-1)，并且同步数从1开始计算。签名就是(s，s，…，s)的一个子集。\nB验证此签名时，用同样的方式计算出字串{h1，h2，…，h2k}，然后分别转换成整数ij(1≤j≤2k)，并验证等式$v_{i_1}=f^u\left(s_{i_1}\right),$$v_{i_2}=f^u\left(s_{i_2}\right),...,$$v_{i_{2k}}=f^u\left(s_{i_{2k}}\right)$是否成立。如果这些等式成立，则验证通过。\n可见该HORSC方案与现有Hash链认证方案相比，将验证方发送的随机数插入到Hash函数的输出字串中，在达到相同等级安全程度时，减少了Hash函数的输出位数。本方案中Hash函数的输出为klog2t′位，加上验证方发送的随机数klog2t′位，可以达到现有技术中Hash函数输出2klog2t′的效果。因此，本方案中Hash函数的输出可以比现有技术中Hash函数的输出减少一半，也就减少了计算量。\n而且该方案的实行需要充分利用簇头的管理、计算能力：\n簇头管理簇内所有节点的簇内公钥，并将自身的簇内公钥广播给簇内所有节点；\n按HORSC协议进行簇内身份认证时，簇内密钥与同步数同时使用；\n簇头根据簇内所有节点公开其密钥的速度来更新同步数，并广播给簇内所有节点；\n当新节点加入本簇时，该节点按HORSC协议重新生成其公钥并发送给簇头；\n但簇头由新节点承担时，重新收集本簇内所有节点的公钥；\n当簇内身份认证时，认证方从本簇簇头获取被认证方的公钥；\n当簇内节点退出本簇时，簇头取消该节点的公钥并通知簇内所有节点；\n簇头根据运行的时间和节点的变动情况发起更新簇内所有节点的公钥，此时所有节点更新其公钥并将同步数重置为1。\n本实施例在实际应用中发现HORSC协议的簇内认证方案不仅解决了同步问题，并且算法速度很快。由于簇头的严格控制同步数，保证同步数的增长快于用户认证服务的最大频率，因此不会出现一个同步数多次使用，而使某个同步数的密钥用尽的情况。并且簇内距离短，也不会出现大的延迟，为基于Hash链的认证提供了一个良好的环境。基于Hash链的认证速度很快，比通常的公钥认证算法要快许多倍。\n在相近的安全性能下，基于HORSC协议的认证速度要大大高于RSA-512。表1给出该实施例应用环境中，RSA-512和基于HORSC的认证的性能比较。其中HORSC的参数是：t′＝128，k＝8，l＝64，d＝210，Hash函数采用MD5。\n表1：RSA-512和HORSC的性能比较\n\n可以看出，为了整合分配网络资源和其他共享处理资源，本实施例还将根据节点是否为簇头设置不同的工作状态，当作为簇内节点时以普通工作状态运行，当作为簇头节点时以加强工作状态运行，处在加强工作状态的节点相对于处在普通工作状态的节点优先获得网络和处理资源支配权。\n假设网络中已经根据一定的规则形成了簇的结构，相对于普通成员，簇头还是需要更强的计算能力，并需要消耗更多的能量。因此，可以将移动自组织网络的移动节点设计成普通和加强两种工作状态。当移动节点被选为簇头后，就从普通状态转变为加强工作状态，从而调动更多的计算能力和能量供应。当移动节点的身份从簇头转化为普通节点后，其工作状态就从加强转变为普通，以减少消耗的资源。\n综上所述，本发明给出一套对于中大型的移动自组织网络的分层分布式的认证服务解决方案。基于分簇的移动自组织网络的分层认证方案中，对于簇间通信采用基于新门限群签名的认证方法，对于簇内通信则采用基于Hash链的HORSC认证方法。而且移动自组织网中t个簇头可以通过合作，实现网络的虚拟可信中心，向新用户颁发证书。\n在基于新门限群签名的簇间认证方案中，充分利用了簇头的强计算能力和网络通信多跳的特性。对于新入网节点证书的颁发，簇头的计算能力较强，能够迅速完成计算并传送给下一个簇头。因此，能够以较快的速度和较大的概率成功完成证书颁发，避免因为节点的移动而造成某些节点在一定时间后就不可达，对网络运行的影响也小。\n此身份认证方案利用了门限密码学的原理，网络中的任意达到数目个的簇头都可以提供认证服务，提高了网络的鲁棒性，特别适合移动自组织网络的动态拓扑的特性。\n移动自组织网络由于网络拓扑的动态变化和有限的带宽，应该尽量减少通信的总跳数来降低网络通信的负担。本发明利用移动自组织网络的多跳特性，设计出移动自组织网络的分布式多跳身份认证方案，减少了通信的回合，降低了网络的通信量。\n还采用具有零知识证明特点的验证协议，实现了身份证书的重用，延长了证书的使用时间，提高了证书的使用效率。\n在HORSC簇内认证方案中，解决了同步问题，并且签名和验证速度快。每个簇内的簇头负责本簇内同步数的广播，所有成员都按照此数来进行签名和验证。簇头能够保证同步数的增长快于用户认证服务的最大频率。而且簇内的通信距离短，不会出现数据转发的较长延时，能够保证Hash链的运行条件，有效地防止同步攻击。实验证实，该基于Hash链的认证大大快于其它公钥认证算法，实用性很强。\n虽然通过参照本发明的某些优选实施方式，已经对本发明进行了图示和描述，但本领域的普通技术人员应该明白，可以在形式上和细节上对其作各种改变，而不偏离本发明的精神和范围。