基于權重的偽隨機密鑰選取的無可信 第三方不可否認協議

高 明，汪學明

（貴州大學計算機科學與技術學院，貴州 貴陽 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