基于权重的伪随机密钥选取的无可信 第三方不可否认协议

高 明，汪学明

（贵州大学计算机科学与技术学院，贵州 贵阳 550025）

基于权重的伪随机密钥选取的无可信 第三方不可否认协议

高 明，汪学明*

（贵州大学计算机科学与技术学院，贵州 贵阳 550025）

现实中几乎不存在完全可信的第三方，通信双方使用的会话密钥的选取在一定程度上决定了这次通信的安全系数。为了能让协议不依赖于可信第三方，且使得密钥库中的密钥得以在随机选取的情况下得到最充分的利用，提出了一种基于权重的伪随机密钥选取机制的无可信第三方的不可否认协议，防止某些密钥的使用过于频繁，导致不必要的安全隐患出现。另外，还提出了一种让对方根据收到的密钥标识在密钥库中通过检索来取得此次通信密钥以代替把密钥打包发送的方式，降低了密钥泄露的风险。

可信第三方；不可否认；密钥；伪随机；权重；标识

引言

随着网络科学技术的迅速普及，互联网生活也越来越精彩，电子商务的迅速发展和完善使得越来越多的人们足不出户就可以买到自己心仪的商品。然而，由于电子商务的蓬勃发展而引发的网络竞争，可能使得商家们之间互相攻击服务器，利用不正当的竞争来使自己的利益最大化；便利的网络条件和丰富的网络资源也给其他不法分子们提供了可乘之机，产生了较多的网络安全隐患[1]。网络就像是一台机器，要想让它安全又有效地运转下去，造福于人类，就要有各种规章制度对其进行制约和规范。电子商务协议就是保证人们网购安全的协议，它对网购各个参与方的行为进行了规范。公平性和不可否认性等都是电子商务的重要安全属性，前者是指通信双方在通信过程中拥有相同的地位，即：要么均无法从通信中取得对自己有益的信息或权限，要么都能取得等价的信息或者权限；而后者是指通信中的任何一方在发送或接收完消息后，不得对此行为予以否认，出现纠纷后一般由可信第三方（TTP）根据发方或者接收方的不可否认证据来判断谁是责任方[2-3]。

对于不可否认思想的研究，最初是在1983年，当时T.Tedrick构思出了一种“分信息汇总”的方法[4]。通信中消息发送者把一个完整的信息分成几个“分信息”，而后逐一地将分信息发送给接收者，接收者需要在每次接收到那些“分信息”之后，都要予以回应。然而这种方法所必需的双方之间大量的通信在网络拥塞时会使通信停滞。另外，这是建立在参与通信的各方都有相同计算能力的前提下，这是不符合实际的。1996年T.Coffey等人提出了一种把协议安全性建立在一个可信第三方基础上的想法[5]，随后N.Zhang等人在T.Coffey想法的基础上降低了可信第三方在协议中的参与力度，只让可信第三方在协议最后完成密钥的分配以及证据的生成[6]。然而，在现实环境中，找到一个可以完全信赖的第三方是几乎不可能的事情。即使能找到少量的绝对可信第三方并运用到协议里面，也可能由于第三方的计算、处理能力有限，以及所处网络拥塞状况的好坏耽误协议的及时运行，使之超出了时效。因此在1997年Micali和Asokan研究了一个不依赖于可信第三方的协议，即可信第三方不被要求必须参与协议中的通信，只在需要的时候参与协议[7]。国内也在本世纪初开始了对不可否认协议模型的研究与改进，其中，卿思汉对国外在不可否认上的研究做了一个总体的概括，提供了一个研究的方向；韩志耕等人对一些不可否认协议进行了形式化分析并且予以了改进等[8]。另外协议的分析工具也比较多，比如从CTL演化来的ATL，还有对ATL进行改进的ATEL等[9]。不过，在降低可信第三方在协议中的参与度上，还没有取得突破进展。

本文提出了一种离线TTP协议模型，即没有可信第三方参与协议，协议的安全性也不会受到影响。在此模型基础上，提出了一种信息接收方通过自身的标识访问通信服务器密钥库，并通过收到的密钥标识检索并获得密钥，以此来防止密钥在传输过程中可能出现的安全问题的发生。另外，为了使得密钥库中的密钥能得到尽可能少重复的完全利用，减少由于密钥频繁使用而带来不必要的被破译隐患，又提出了一种基于权重的伪随机密钥选取方法，并用相应的代码予以实现。

1 基础知识

1.1 TTP协议分类

可信第三方TTP，Trusted Third Party，起初是被用来在协议中转发各方参与者的消息，然后在转发的过程中，记录并生成各方的消息发送和接收证据，以便在出现纠纷的时候便于根据证据来判断责任归属，这种模型叫做完全在线TTP协议模型（inline TTP）。而后，为了减少可信第三方参与协议的比例，人们让TTP只去在协议最后对通信各方进行密钥的分配，并且收集各方对信息的发送接收证据，这类叫做在线TTP协议模型（online TTP）,比较出名的有Zhou-Gollman非否认协议、挂号电子邮件协议[10]、网上购买货物协议等。

然而在现实中，我们很难找到绝对可以信赖的第三方。即使存在，那也可能会由于网络拥塞或者第三方服务器的处理能力受限而使得整个通信处于延迟状态，严重的会导致整个协议的时效期已过，通信各方都退出了本次通信，造成不小的时间以及成本损失。因此在1997年一个不依赖于可信第三方的协议被提了出来[7]，在此协议中的可信第三方不被要求必须参与协议中的通信，但如果出现纠纷的时候，各方可以请求可信第三方介入且加入到协议运行中来维护安全。这种协议模型被称为离线协议模型（Offline）。

除上述的分类外，可信第三方还可以根据它在各协议参与者们中间的信誉度（被各方信任的程度）被划分为可以被完全相信的可信第三方，可以根据具体环境状况而选择是否相信的条件可信第三方以及可以被部分相信的半可信第三方，各种种类都得到了深入研究并在不同程度下于协议中得到了应用。

1.2 不可否认证据及假设

不可否认分为发方不可否认和接收方不可否认。

fNRO：发方不可否认证据，表示消息发送方不可对自己已经发送过的消息的行为予以否认；

fNRR：接收方不可否认证据，指消息接收方不得对已经接收到消息的行为予以否认。

对于模型建立和分析，需要有四个前提假设。一是各协议参与方都不会做出损害自己利益的事情；此外，还要假设可信第三方都是完全可信的，这包括它既不会与其他各方合谋谋取不正当利益，也不会自己利用漏洞和权益去谋取不当利益；还要认为协议中各方的密钥体制都是安全的，都是不会被破解的；最后，还需要假设通信的信道是弹性信道，即：消息可能会延迟，但始终会在规定时间内到达接收者。

1.3 协议的分析工具

本文运用交替时序逻辑ATL对协议模型进行形式化分析。它是为了克服传统的时序逻辑（LTL、CTL等）把协议看成是一个封闭的系统这一缺陷，由Kremer博士等提出了一种新的基于博弈的分析方法。

定义1 一个交替转换系统是一个六元组S=<∏,∑,Q,Q0,π,σ>。其中∏是命题集合，∑是参与者集合，Q是状态集合，Q0是初始状态集合，π是一个从状态到命题集合的映射：Q→2π,σ是一个转换函数（从{状态×参与者}到非空的选择集合）：Q×∑→22QQ}，此处的每个选择都可能是系统的下一个状态集合（可能对状态集合有些许约束）。定义2ATL的公式有如下的几种表示形式：（1）p，其中，命题p∈∏；（2）Φ，或者Φ1∨Φ2，其中Φ1和Φ2是ATL公式；（3）如果参与者P∈∑，那么<

>°Φ,<

>□Φ，<

>Φ1UΦ2是ATL公式。其中Φ1和Φ2是ATL公式。上述符号语句中，<<>>表示路径，是路径量词；°是表示下一个（next）；□表示必然（always）；U表示直到（until），它是时态算子，也叫时态操作符；◇表示可能（may）。利用这些符号可以实现各个公式之间的等价形式转换。例如，公式<

>trueUΦ就可以用<

>◇Φ来表示。其余的符号，类似于，∨等与普通的逻辑符号意义相同，并无更改。具体的各个符号的详细语义可以在文献[11]中查阅。定义3 策略，一个参与者的策略是一个映射，即fp:Q+→2Q，使得对所有的λ∈Q*和所有的q∈Q，fq（λ，q）∈σ（q，p）成立。对协议模型进行建模之后，用ATL公式将性质表述出来，而后用MOCHA工具验证公式是否成立。

2 基于权重伪随机密钥分配

协议中密钥库里关于各组通信所使用的密钥选取尤为重要，特别是密钥的分离、管理以及时效期[12]。既要保证各个秘钥的普遍使用率，也要避免连续两次选中同一个密钥的可能。密钥库选择静态密钥管理，即一个密钥标识代表一组密钥；若采用动态密钥储存可能会导致多个通信同时进行的时候密钥信息管理的混乱。当然，密钥标识和密钥也需要不定期的进行更新，防止随着通信次数和频率的增加，可能会出现同一参与者获得与之前相同的密钥标识，这样参与者可以不经过标识管理处的鉴别就推测出密钥，而服务器在这次通信中没有任何证据证明参与者获得了密钥，不符合公平性。正常情况下密钥库中的密钥数量有很多，但是为了便于说明，这里假设它有五组密钥，设为Key1，Key2，Key3，Key4，Key5。每组密钥的初始随机因数设为1，具体过程如表1所示。

表1

每组密钥的初始随机因数设为1。计算过程描述如下：（1）算出全部密钥的随机因子总和，称为权重总和，用S表示；（2）随机选取一个0到1的系数x（根据对象多少选取适当位数的小数，小数位数需比项目总数的位数大3，过少的话就使得有的项目取不到抑或一个项目所对应的系数范围太小），然后计算系数x与权重总和S的乘积，记为f；（3）依次累加随机因子，看累加到哪个的时候，累加值不小于f，即取这个密钥。比如初始时候，S=5，随机选取x=0.3（可以多位小数），那么f=1.5，当累加到第二项时，1+1=2>1.5,那么此时Key2被选择使用。接下来它的随机因数会变为0，下次无论如何也不会选到它。这里只是提供了一种参数，此方法也可以拓展开来：比如初始随机因数可以不为1，或者使得累加可以变为累乘，抑或加入复杂的计算公式，使得别人无法轻易模仿出模型。利用这种基于权重的伪随机方法来选择密钥，一来可以避免同一组密钥连续两次被选中；二来长时间未被选到的密钥，随着随机因数的不断增加，在选择中站的权重也不断增加，使其被选中的概率也大大加大，因此被叫做基于权重的伪随机。

3 无可信第三方不可否认协议模型

3.1 协议模型

下面给出一种服务器客服模式下，非私人用户型的服务器在通信中采用的基于离线TTP的不可否认协议模型，可以定义协议中服务器接受各方通信请求，是协议通信的共通点（即所有通信都与其有关，其他各方都向他请求通信）。不可否认性需要两个证据来支持，即发方不可否认证据fNRO以及接收方不可否认证据fNRR。

定义1：服务器S，各方通信参与方为Ai（i=1,2,3……），m为相应的明文，R为相应的通信标识符，Key-number为对应服务器密钥库中密钥的密钥标识符。

定义2：服务器S有信息身份板，密钥库，黑匣，以及标识管理处。信息身份板用来记录并公布S发送的信息，以便通信参与方后期查询；密钥库中存储的密钥分别拥有自己对应的标识信息，短期内选择通信空闲时间不定时的进行更新；黑匣负责记录服务器S的一切操作并进行记录，无法被修改，除了仲裁机构外其他人无法访问；而标识管理处则是用来分发给通信各方的暂时身份标识以及在后期对此标识进行鉴别的机构。

过程如下：（i=1,2,3，……）

（1）S→ALL：PKS，acceptance；

（2）Ai→S：Sign（{request，PKAi}PKS）；

（3）S→Ai：{IDS，IDAi，NS，R，TAi，m}PKAi；

（4）Ai→S：Sign（{IDS，IDAi，NAi，A，R，TAi’，m}PKS）（ifAiinquirypassed）；

（5）S→Ai：{R，Key-numberAi}；

（6）AigettheKey。

首先，服务器S告知所有人自己的公钥PKS,并且公告自己处于可通信状态，接受各方的通信请求。而后各方参与者们根据实际需求，选择是否向S发送通信请求以及A1的公钥。假若S收到A1的通信请求之后，会发送用A1公钥PKA1加密的自己的身份标识IDS以及暂时给予A1的身份标识IDA1，随机数NS，此次通信标识符R，相关明文m以及要求对方给出回复的时效标签TA1。A1如果可以接受这个时效，那么可以申请查询S的公示板，看看消息是否来自于S。此时，S的标识管理处会鉴别A1的身份标识是不是自己在先前发送过去的那个，如果是，则在身份板处对A1显示自己发给A1的上一条信息的内容以及证据；若鉴别不通过，则予以回绝。

A1查询完结果，确定上条信息来自于服务器S后，首先将此信息进行存储，而后便会向其发送用S的公钥PKS加密过的随机数NA1，在S处取得的此次通信中的暂时身份标识IDA1，自身原本的身份标识A，此次通信标识符R，相关明文m以及自己对下一条信息的设定时效TA1’，并且对此进行签名，生成报文摘要，一起发送给S。S收到消息后，先将摘要保存来证明此信息来自于A1，便于在后期出现纠纷的时候提供给仲裁方。而后通过权重伪随机在密钥库中选取相应的密钥标识信息Key-numberA1（结合原始密钥库中的密钥标识、分发此密钥的对象的暂时身份标识IDAi以及此接受者的公钥三者通过计算得出），连同此次通信标识符R一起用PKA1加密后发送给A1。A1凭借获取的身份标识和密钥标识去密钥库中检索出密钥。作为此次通信接下来要使用的密钥，开始与S正式的通信。

其中，服务器S的所有的记录以及操作都被黑匣记录下来，A1每次发送过来的信息都会被要求用A自身的私钥（非S分配的）进行数字签名，报文摘要会被S储存下来留作证据。由于只有A1有自己的私钥，所以此报文摘要只有A1才能生成。

3.2 争议解决

（1）如果A1表示自己收到了消息，而服务器S对次表示了否认，那么A1就会提供出当时访问信息身份板的信息储存以及自己的暂时标识IDA1，以此来证明确实收到过S的信息，否则他无法通过鉴别管理处的身份鉴别进入S的信息身份板；也可以申请让仲裁机构就进入S的黑匣，查询S的过往行为操作，以此来进行判断。这样也能大大降低第三方的参与度。

（2）如果S表示自己收到了消息，而A1却对此予以否认，那么S就会提供出先前保存下来的报文摘要，让仲裁方根据A1的私钥进行相应的鉴别。

（3）如果传递的消息极端的隐秘，为了防止中间人攻击，那么在A1取得了会话密钥之后，可以分别与服务器S把刚开始使用的密钥以及约定好后续使用的密钥两组合二为一，进行相关的复杂计算得出一组新的密钥，这样即使中间人盗取了会话密钥，也无法得知最终的密钥结果。具体算法这里暂且不表。

这样子，就保证了协议的身份认证以及对消息收发的行为不可否认性。

3.3 协议形式化分析

对于通信中，服务器S与参与者Ai的行为转换图如图1所示：

图1

验证协议公平性，公平性就是指协议通信各方要么均无法从通信中取得对自己有益的信息或权限，要么都能取得等价的信息或者权限。用ATL公示表达就是

（2）<>◇（proofs∧<>◇proofAi）；

其中，proofAi和proofS分别代指Ai与S参与协议的证据。（1）表示S不会拥有策略使得它可以通过操控信道使得S拥有Ai参加协议的证明而Ai却没有S参加的证明，表明对A来说，是公平的；（2）则是与（1）相反，描述的是S在协议中享有公平性。经过MOCHA工具验证，协议符合公平性。在协议中具体分析，可以知道，如果中途A1终止了协议，那么S就将此次通信设为终止状态，相应的密钥也宣布在此次通信中作废，更新鉴别管理处的信息。A1再后来将无法得到更多的信息。如果S终止了协议，那么A1也没有什么损失，并且陷入纠纷时可以通过仲裁介入黑匣维护自己的权益，满足了公平性。

关于抗合谋性，是指参与通信的两方，合伙谋划获取关于服务器S的不正当权益或信息。用ATL公式表达如下：

'<>◇（'A1_Get_K∧'A1_Success∧'A1_Send_Mes'<>◇（S_Get_Proof））

其中A1_Get_K表示A1获得了相应的信息，A1_Success表示A1成功完成了协议，另外的A1_Send_Mes表示A1发送了消息，S_Get_Proof表示S获得了相应的证据。该公式表示A1不会拥有策略，使得自己虽然未能成功完成协议却通过别的方法获得了重要信息，而发送方S对此毫无证据。输入MOCHA进行检验，结果符合抗合谋性。因为协议中，Key-number中有关于使用者的相关信息组成，因此即使是同一组密钥，只要使用者身份不同，就不会出现个两个相同的Key-number，而发送的信息都由各自使用者的公钥加密，只要相对的私钥不丢失，就不会落入他人手里。

4 结论

本文结合当下绝对可信第三方难以找寻的现况，提出了无可信第三方协议模型，使得协议本身在运行的时候无需可信第三方对消息进行转发或保存收发方的相应证据，各方都能够拥有相关维护自身权益的证明。其中，还提出了一个密钥自己去“取”，不会经过消息发送的构思，避免了密钥在传输过程中可能遇到的各种安全问题的发生。另外，本文还对密钥库的密钥分配提出了一种基于权重的伪随机算法，在保证不会连续两次选中同一密钥的同时，也能增加未被选中过的密钥在今后被选中的可能性，使得各个密钥的普遍利用率适当的加大。今后的工作方向是找寻一个更加完善的算法，使得在选择密钥的时候，只遍历一次各参与方的随机因数，这样能够挑选密钥所需时间，加大工作效率。

[1]XIAOYun，XUJieMin.Applicationofcomputersecuritytechnologyinelectroniccommercetransaction[J].ComputerKnowledgeandTechnology，2016（12）：275-276.

[2]WANGXueming，WENGLichen.AnalysisandImprovementofAFairMulti-partyNon-repudiationProtocolBasedonATLLogic[J].TechnologyandStudy，2011（09）:22-23.

[3]LIUDongmei，QINGSihan，MAHengtai，etal.AKindofAnalysisMethodofOff-LineTTPFairNon-RepudiationProtocol[J].JournalofComputerResearchandDevelopment，2011，48（4）：656-665.

[4]LiQiang.DesignandAnalysisofNon-RepudiationProtocolbasedonOffline-likeTTP[D].Chongqing：CollegeofChongqingUniversity，2014.

[5]ZDjuric，DGasevic.ASecureFair-ExchangePaymentSystemforInternetTransactions[J].ComputerJournal，2014，58（10）: 27-31.

[6]AAlotaibi，HAldabbas.DesignandEvaluationofaNewFairExchangeProtocolBasedonanOnlineTTP[J].InternationalJournalofNetworkSecurity&ItsApplications，2012，4（4）.

[7]SHTian，LJChen，LIJian-Ru.FairnessanalysisofelectronicpaymentprotocolbasedonofflineTTP[J].JournalofComputerApplications，2009，29（7）:1839-1843；

[8]HANZhigeng，LUOJunzhou.AnalysisandImprovementofTimelinessofaMulti-PartyNon-RepudiationProtocol[J].ACTAELECTRONICASINICA，2009，37（2）:377-381.

[9]NINGZhengyuan，HUShanli，LAIXianwei.Alternating-timetemporalbelieflogicanditsmodelChecking[J].JOURNALOFNANJINGUNIVERSITY（NATURALSCIENCES），2008，44（2）:171-178.

[10]GAOYuexiang，PENGDaiyuan.DesignandformalanalysisofcertifiedE-mailprotocol[J].JOURNALOFCOMPUTERAPPLICATIONS，2008，28（8）.

[11]AlurR，HenzingerTA，KupfermanO.Alternating-timetemporallogic[M].In38thAnnualSymposiumonFoundationsofComputerScience，MiamiBeach，IEEEComputerSocietyPress，1997:100-109.

[12]SPJohn，PSamuel.Self-organizedkeymanagementwithtrustedcertificateexchangeinMANET[J].AinShamsEngineeringJournal，2015.

[责任编辑：袁向芬]

Non-repudiation protocol with pseudo-random key selection based on the weight in offline TTP model

GAO Ming, WANG Xue-ming*

（College of Data and Information Engineering, Guizhou University, Guiyang, Guizhou, 550025）

Thereis almost no fully trusted TTP in reality, and the selection of the session key used by the communication parties determines the safety coefficient to some extent.The paper comes up with a kind of Non-repudiation protocol with pseudo-random key selection based on the weight in offline TTP model in order to make the protocol be independent of the TTP and make full use of the keys in key-store in the case of random selection.It can prevent some keys from being using toofrequently and cause the emergence of unnecessary security risks.What’s more, it also presents one way to get the secret keys by searching in key-store instead of sending secret keys by messages to reduces the risks of keys leakage.

TTP； Non-repudiation； Secret key； Pseudo-random； Weight； Identification

2016-08-29

国家自然科学基金项目[2011]61163049；贵州省自然科学基金资助项目黔科合J字[2014]7641。

高 明（1990-），男，山东淄博人，贵州大学计算机科学与技术学院在读硕士，研究方向：协议分析、密码学与信息安全。*通讯作者：汪学明（1965-），男，安徽绩溪人，博士，贵州大学计算机科学与技术学院教授，研究方向：无线与移动通信、协议分析与模型检测、密码学与信息安全。

TP309

A

1674-7798（2016）12-0022-06