Cascade密鑰協商的改進方案

賈仁慶，吳曉富，朱衛平

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

Cascade密鑰協商的改進方案

賈仁慶，吳曉富，朱衛平

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

隨著移動互聯網業務的快速發展，無線通信安全已成為一個重要課題。近年來，無線密鑰提取技術引起了研究者們的關注，通過無線密鑰提取技術促使合法通信雙方擁有大量的共享密鑰，結合一次一密機制，使實現信息論意義上的絕對安全成為可能。密鑰協商是提取物理層密鑰的關鍵步驟。在眾多的密鑰協商方案中，Cascade協商方案由于能夠高效地協商出一致的密鑰而備受關注。然而，Cascade協商采用二分法進行糾錯，在糾錯的過程中需要通信雙方不斷交互校驗信息，從而導致Cascade對網絡延遲較為敏感。為了降低Cascade協商的交互次數，提出Cascade的一種改進方案，利用截止二分搜索方案進行密鑰協商。實驗仿真結果表明：所提方案可以在保證密鑰協商效率的同時，有效降低了通信雙方的交互次數。

物理層安全;Cascade協商;交互次數;效率

0 引 言

近年來，物理層安全技術引起了研究者們的廣泛關注。合法用戶可以利用無線信道固有的隨機性協商出一致的密鑰，而不需很大的計算復雜度[1-2]。實際的物理層密鑰提取方案可分為三個步驟進行：第一步為優勢提取階段[3-4]，在TDD半雙工模式下，無線信道具有互易性，且當竊聽者Eve與Alice、Bob的距離都大于波長的一半λ/2時，合法信道與竊聽信道基本不相關，Alice、Bob分別提取信道特征并進行量化，得到不一致的初始密鑰序列[5]；第二步為密鑰協商階段[6]，Alice、Bob在公共信道上交換糾錯信息以達到協商出一致密鑰序列的目的。由于密鑰協商需要在公共信道上傳遞糾錯信息，向竊聽者Eve泄露了部分信息。為了增強密鑰的安全性，協商出來的密鑰需要通過Hash進行密鑰增強[7-10]。

密鑰協商是物理層提取密鑰的關鍵一步。針對協商技術，文獻[11]提出了BBBSS協議，后來文獻[5]提出了著名的Cascade協商技術。在這兩種協議中，首先Alice、Bob分別對密鑰進行分組，并交換每組的奇偶值。若某一個分組的奇偶性不同，則說明在該分組內至少會有一個錯誤比特，然后Alice、Bob通過二分法進行糾錯。在二分法糾錯過程中，需要Alice、Bob之間多次交互每組的奇偶值，從而導致了這種協商技術對網絡延時等較為敏感[12]。文獻[13-15]提出了利用漢明碼的伴隨式進行前向糾錯—Winnow技術，盡管該技術降低了協商的交互次數，但是糾錯效率出現了大幅度的折損。文獻[14]提出利用前向糾錯碼(如LDPC碼)進行協商。LDPC協商技術可以降低交互次數，并提高協商效率。但是，LDPC碼進行協商時需要終端進行比較多的計算，并且協商效率受到碼長的影響。

Cascade采用二分法進行糾錯，二分法可以迅速鎖定錯誤比特的范圍，直到最后找到錯誤比特的位置。然而，一方面二分法糾錯需要Alice、Bob不斷地交互信息，另一方面當分組長度鎖定到s≤3以下時，若繼續使用二分法查詢錯誤比特的位置，則這s個比特密鑰信息幾乎會全部暴露，此時仍然利用二分法搜索錯誤的位置就沒有任何實際意義。

為此文中提出了截止二分法搜索方案，當分塊長度縮小到3時，不再繼續使用二分法糾錯，而是直接刪除，不再作為協商的密鑰部分；為了支持Cascade中回溯二分糾錯功能，Alice把待刪除位置的密鑰直接發送給Bob，從而達到減少Alice、Bob交互次數的目的。仿真結果表明，提出的Cascade改進方案能夠降低Alice、Bob之間的交互次數。

1 Cascade協商

Cascade協商是在二分法糾錯基礎上的一種密鑰協商協議。為了完整地介紹Cascade協商方案，本節將首先介紹二分法糾錯，然后詳細介紹Cascade協商方案。

1.1 二分法

二分法糾錯是Cascade協商的核心步驟，通過二分法可以迅速鎖定錯誤比特的所在位置，并進行糾錯。

令Alice、Bob進行協商的密鑰序列分別為A=A1,A2,…,AN,B=B1,B2,…,BN，密鑰長度為N，誤碼率為ε。如圖1所示，假定序列A,B中有奇數個不同的比特，Alice、Bob通過二分法可糾正一個比特，糾錯的具體步驟如下[4]：

步驟1：Alice把序列A等分為兩部分，并把第一部分的奇偶值a發送給Bob；

步驟2：Bob按照同樣的方式把B分為兩部分，并計算第一部分的奇偶值b，若a≠b，說明在第一部分有奇數個錯誤比特，否則說明在第二部分中有奇數個錯誤比特；

步驟3：重復步驟2，直到獲取錯誤比特的位置，并對該位置的比特進行糾正。

圖1 二分法糾錯

如圖1所示，Alice、Bob中有一個不同的比特信息(第4個)，通過二分法搜索可迅速鎖定錯誤比特所在的位置，并對錯誤比特進行糾正。然而，當二分法把錯誤比特所在的范圍鎖定到s≤3個比特以內時，若繼續使用二分法查詢錯誤比特，這s個比特幾乎會全部泄露給竊聽者。

1.2 Cascade協商方案

文獻[12]提出了Cascade密鑰協商機制。Cascade通過多輪反復糾正錯誤比特，在第一輪通過二分法糾錯使得每個小組內含有偶數個錯誤的比特；在第i>1輪中，Alice、Bob對密鑰串進行隨機分組，比較每組的校驗值并用二分法進行糾錯。當發現一個新的錯誤時，在之前輪中對應的分組內必含有奇數個錯誤比特，再次通過二分法糾錯，從而使得糾正的比特數倍增，提高了密鑰的協商效率。Cascade協商機制的具體步驟如下：

Alice、Bob重新隨機分組并比較每組奇偶性，當某個分組的奇偶性不一樣時，就進行新一輪的糾錯。當第i輪糾錯結束時，從Pass1到Passi所有分組內都包含偶數個錯誤比特(包括0)。文獻[5]中推薦Cascade執行i=4輪糾錯，每輪分組的長度可設定為ki=2ki-1,k1=0.73/p。

經過Cascade協商后，Alice、Bob可以獲取一致的密鑰序列，由于在協商過程中泄露了密鑰信息，完成協商后需要進行密鑰增強[13]以得到安全的密鑰。Cascade協商的效率較高且實現簡單，然而Cascade需要Alice、Bob之間不斷地相互傳遞信息。若設分組長度為k，則一次二分法糾錯需要交互log2k次，尤其是在回溯糾錯的過程中，交互次數會猛增，從而導致傳輸網絡的延遲等情況會影響到Cascade協商的性能。

2 Cascade協商的改進

2.1 改進方案的思路

Cascade采用二分法進行糾錯，二分法可以迅速鎖定錯誤比特的范圍，直到最后找到錯誤比特的位置，進而糾正錯誤比特。通過第1節中的介紹可以看出，Cascade密鑰協商的效率是很高的。然而，Cascade密鑰協商算法也具有一些不可避免的缺陷。一方面二分法需要在合法通信雙方Alice、Bob之間不斷地交互信息，在一個長度k的分組內，一次二分法糾錯過程需要log2k次交互，由于在回溯過程中需要多次二分糾錯，從而導致在Cascade密鑰協商過程中Alice、Bob之間的交互通信次數會大幅度增加，因此當網絡環境出現延遲等特殊情況時可能會對Cascade協商的效率產生不利的影響。另一方面，二分法可以迅速鎖定單個錯誤比特所在的范圍，然而當錯誤比特所在范圍鎖定到3個比特以下時，若繼續利用二分法進行搜索，則會把小組內比特幾乎會全部泄露給竊聽者Eve。以錯誤位置鎖定到3個比特為例，判斷錯誤比特位于這三個比特之內需要1個比特校驗信息，利用二分法找到錯誤比特所在位置又需要「log3?=2個比特的校驗信息，這3個比特基本上全部泄露給了竊聽者Eve，繼續利用二分法搜索錯誤的位置已沒有任何實際意義。為此，文中提出了截止二分法協商方案。如圖2所示，當分塊長度縮小到3以內時就不再繼續二分查找，而是直接刪除該部分的比特，不再作為協商的密鑰部分。為了支持Cascade密鑰協商中的回溯二分糾錯功能，合法通信雙方暫且保留要刪除的數據，Alice把待刪除位置的密鑰直接發送給Bob，同時記錄需要刪除數據的位置，從而達到減少合法通信雙方Alice、Bob交互通信次數的目的。

圖2 截止二分協商

2.2 改進方案的主要步驟

如圖2所示，截止二分協商的步驟如下：

步驟1：Alice把序列A分為兩部分，并把第一部分的奇偶值a發送給Bob。

步驟2：Bob按照同樣的方式把B分為兩部分，并計算第一部分的奇偶值b，若a≠b，說明在第一部有錯誤比特，否則說明在第二部分中有錯誤比特。

步驟3：計算錯誤比特所在部分的序列長度s，當s≤3時，停止迭代；否則重復步驟2。

步驟4：Alice把鎖定的待刪除比特信息發送給Bob，Bob對密鑰信息進行修正。

當Alice、Bob進行Cascade協商時，利用回溯、截止二分協商方案，同時記錄待刪除比特的位置信息。當協商完成以后去掉密鑰序列中的待刪除比特。

3 仿真與結果分析

對原始Cascade與改進的Cascade協商方案進行了仿真比較。文獻[6,16]把在公共信道上交換的比特數與密鑰長度的比值作為統計的協商效率。然而，實際上根據交換的校驗值可以確定部分密鑰信息，以搜索范圍是6個比特為例，首先需要1比特校驗值判斷該區間內含有錯誤比特，然后Alice、Bob比較前3個比特的校驗值，若相同，則把搜索范圍確定在后3個比特中，盡管繼續使用二分法糾錯需要2個比特校驗值，但實際上此時后3個比特已經全部泄露了，若只統計交換的比特數則少統計了一個比特的泄露信息。文中統計協商效率時，以公共信道上交換的比特數與竊聽者根據校驗值可確定的密鑰數之和為泄露的密鑰長度，該長度與密鑰總長度的比值為協商效率。

在協商之前，為了達到錯誤比特隨機分布的目的，Alice、Bob同步打亂密鑰序列的順序。仿真參數設定如下：步驟i的分組長度設定為ki=2ki-1,k1=0.73/p，p為誤比特率BER，密鑰長度N=10 000，仿真結果為20 000次實驗的平均值。

協商效率比較見圖3。

圖3 協商效率比較

由圖3可知，改進的Cascade協商效率與原始Cascade協商效率基本一樣，并無明顯差距。這主要是因為當搜索長度鎖定到3以下時，若繼續利用二分法進行搜索會泄露2～3個校驗比特的信息，從而導致該部分的密鑰全部泄露出去；而在截止二分協商中，當分組長度小于等于3時，不再搜索錯誤比特的位置，而是把這些比特作為待刪除的比特信息直接發送給對方，同樣泄露了比特信息。因此改進的Cascade協商效率基本與原始Cascade相同。

交互次數比較見圖4。

圖4 交互次數比較

由圖4可知，與原始Cascade協商方案相比較，改進Cascade協商方案的交互次數明顯下降。Cascade協商過程中，回溯過程會使Alice、Bob之間的交互次數出現大幅度的增加。而在改進的Cascade協商方案中，采用截止二分協商，當錯誤比特所在位置鎖定到3個比特時，不再繼續二分查詢，從而降低了Alice、Bob之間的交互次數。

4 結束語

Cascade是經典的密鑰協商方案，由于該方案需要Alice、Bob之間不斷交互信息，從而導致Cascade協商對網絡延遲等較為敏感。文中提出了Cascade的一種改進方案。仿真結果表明，改進方案保證了高效率協商，同時降低了Alice、Bob之間的交互次數。

[1]HaoZ,ZhongS,LiL.Towardswirelesssecuritywithoutcomputationalassumptions-anoblivioustransferprotocolbasedonanunauthenticatedwirelesschannel[C]//ProceedingsofIEEE.Shanghai:IEEE,2011:2156-2164.

[2] 李古月,胡愛群,石 樂.無線信道的密鑰生成方法[J].密碼學報,2014,1(3):211-224.

[3]MaurerU.Secretkeyagreementbypublicdiscussionfromcommoninformation[J].IEEETransactionsonInformationTheory,1993,39(3):733-742.

[4]CachinC,MaurerU.Linkinginformationreconciliationandprivacyamplification[J].JournalofCryptology,1997,10(2):97-110.

[5]YeCX,MathurS,ReznikA,etal.Information-theoreticallysecretkeygenerationforfadingwirelesschannels[J].IEEETransactionsonInformationForensicsandSecurity,2010,5(2):240-254.

[6]BrassardG,SalvailL.Secretkeyreconciliationbypublicdiscussion[C]//Workshoponthetheoryandapplicationofcryptographictechniques.[s.l.]:[s.n.],1994:410-423.

[7]PremnathSN,JanaS,CroftJ,etal.Secretkeyextractionfromwirelesssignalstrengthinrealenvironments[J].IEEETransactionsonMobileComputing,2013,12(5):917-930.

[8]BennettC,BessetteG,SalvailL,etal.Experimentalquantumcryptography[J].JournalofCryptology,1992,5(1):3-28.

[9] 徐 津,溫巧燕,王大印.一種基于Hash函數和分組密碼的消息認證碼[J].計算機學報,2015,38(4):793-803.

[10] 王張宜,李 波,張煥國.Hash函數的安全性研究[J].計算機工程與應用,2005,41(12):18-19.

[11] 張曉梅.概率統計在密碼學中的Hash函數中的應用[J].中國高新技術企業,2010(22):56-58.

[12]Martinez-MateoJ,ElkoussD,MartinV.Keyreconciliationforhighperformancequantumkeydistribution[R].[s.l.]:[s.n.],2013.

[13]ZhaoF,FuMX,WangFQ,etal.Errorreconciliationforpracticalquantumcryptography[J].Optik-InternationalJournalforLightandElectronOptics,2007,118(10):502-506.

[14]ButtlerWT,LamoreauxSK,TorgersonJR,etal.Fast,efficienterrorreconciliationforquantumcryptography[J].PhysicalReviewA,2003,67(5):052303.

[15]PearsonD.High-speedQKDreconciliationusingforwarderrorcorrection[C]//Proceedingsof7thinternationalconferenceonquantumcommunication,measurementandcomputing.Glasgow:[s.n.],2004:299-302.

[16]YanH,RenT,PengX,etal.Informationreconciliationprotocolinquantumkeydistributionsystem[C]//IEEEfourthinternationalconferenceonnaturalcomputation.Jinan:IEEE,2008:637-641.

An Improved Scheme of Cascade Protocol

JIA Ren-qing，WU Xiao-fu，ZHU Wei-ping

(College of Telecommunication & Information Engineering,Nanjing University of Posts and Telecommunication,Nanjing 210003,China)

With the rapid development of mobile Internet services,information security for wireless communication is becoming a very important research topic.Recently,there has been great interest in generating the shared secret key based on the physical layer security techniques,which could achieve the perfect secrecy combined with a one-time pad.Information reconciliation is a key step of secret key generation.Cascade is the most famous reconciliation protocol duo to the high efficiency.However,Cascade is highly interactive protocol which makes it very sensitive to network latencies.In order to reduce the number of communications,a modifying strategy of Cascade is proposed by Abort-BINARY searching.Extensive simulation results show that the modifying strategy could ensure high efficiency of information reconciliation and reduce the number of communications effectively.

physical layer security;Cascade;number of communications;efficiency

2016-01-25

2016-05-11

時間：2016-10-24

國家自然科學基金資助項目(61372123)

賈仁慶(1989-)，男，碩士，研究方向為物理層安全；吳曉富，教授，研究方向為物理層安全；朱衛平，教授，研究方向為無線通信信號處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1117.064.html

TN918

A

1673-629X(2016)11-0097-04

10.3969/j.issn.1673-629X.2016.11.022