賈仁慶，吳曉富，朱衛(wèi)平

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

Cascade密鑰協(xié)商的改進(jìn)方案

賈仁慶，吳曉富，朱衛(wèi)平

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

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

物理層安全;Cascade協(xié)商;交互次數(shù);效率

0 引 言

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

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

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

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

1 Cascade協(xié)商

Cascade協(xié)商是在二分法糾錯(cuò)基礎(chǔ)上的一種密鑰協(xié)商協(xié)議。為了完整地介紹Cascade協(xié)商方案，本節(jié)將首先介紹二分法糾錯(cuò)，然后詳細(xì)介紹Cascade協(xié)商方案。

1.1 二分法

二分法糾錯(cuò)是Cascade協(xié)商的核心步驟，通過二分法可以迅速鎖定錯(cuò)誤比特的所在位置，并進(jìn)行糾錯(cuò)。

令A(yù)lice、Bob進(jìn)行協(xié)商的密鑰序列分別為A=A1,A2,…,AN,B=B1,B2,…,BN，密鑰長(zhǎng)度為N，誤碼率為ε。如圖1所示，假定序列A,B中有奇數(shù)個(gè)不同的比特，Alice、Bob通過二分法可糾正一個(gè)比特，糾錯(cuò)的具體步驟如下[4]：

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

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

步驟3：重復(fù)步驟2，直到獲取錯(cuò)誤比特的位置，并對(duì)該位置的比特進(jìn)行糾正。

圖1 二分法糾錯(cuò)

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

1.2 Cascade協(xié)商方案

文獻(xiàn)[12]提出了Cascade密鑰協(xié)商機(jī)制。Cascade通過多輪反復(fù)糾正錯(cuò)誤比特，在第一輪通過二分法糾錯(cuò)使得每個(gè)小組內(nèi)含有偶數(shù)個(gè)錯(cuò)誤的比特；在第i>1輪中，Alice、Bob對(duì)密鑰串進(jìn)行隨機(jī)分組，比較每組的校驗(yàn)值并用二分法進(jìn)行糾錯(cuò)。當(dāng)發(fā)現(xiàn)一個(gè)新的錯(cuò)誤時(shí)，在之前輪中對(duì)應(yīng)的分組內(nèi)必含有奇數(shù)個(gè)錯(cuò)誤比特，再次通過二分法糾錯(cuò)，從而使得糾正的比特?cái)?shù)倍增，提高了密鑰的協(xié)商效率。Cascade協(xié)商機(jī)制的具體步驟如下：

Alice、Bob重新隨機(jī)分組并比較每組奇偶性，當(dāng)某個(gè)分組的奇偶性不一樣時(shí)，就進(jìn)行新一輪的糾錯(cuò)。當(dāng)?shù)趇輪糾錯(cuò)結(jié)束時(shí)，從Pass1到Passi所有分組內(nèi)都包含偶數(shù)個(gè)錯(cuò)誤比特(包括0)。文獻(xiàn)[5]中推薦Cascade執(zhí)行i=4輪糾錯(cuò)，每輪分組的長(zhǎng)度可設(shè)定為ki=2ki-1,k1=0.73/p。

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

2 Cascade協(xié)商的改進(jìn)

2.1 改進(jìn)方案的思路

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

圖2 截止二分協(xié)商

2.2 改進(jìn)方案的主要步驟

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

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

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

步驟3：計(jì)算錯(cuò)誤比特所在部分的序列長(zhǎng)度s，當(dāng)s≤3時(shí)，停止迭代；否則重復(fù)步驟2。

步驟4：Alice把鎖定的待刪除比特信息發(fā)送給Bob，Bob對(duì)密鑰信息進(jìn)行修正。

當(dāng)Alice、Bob進(jìn)行Cascade協(xié)商時(shí)，利用回溯、截止二分協(xié)商方案，同時(shí)記錄待刪除比特的位置信息。當(dāng)協(xié)商完成以后去掉密鑰序列中的待刪除比特。

3 仿真與結(jié)果分析

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

在協(xié)商之前，為了達(dá)到錯(cuò)誤比特隨機(jī)分布的目的，Alice、Bob同步打亂密鑰序列的順序。仿真參數(shù)設(shè)定如下：步驟i的分組長(zhǎng)度設(shè)定為ki=2ki-1,k1=0.73/p，p為誤比特率BER，密鑰長(zhǎng)度N=10 000，仿真結(jié)果為20 000次實(shí)驗(yàn)的平均值。

協(xié)商效率比較見圖3。

圖3 協(xié)商效率比較

由圖3可知，改進(jìn)的Cascade協(xié)商效率與原始Cascade協(xié)商效率基本一樣，并無明顯差距。這主要是因?yàn)楫?dāng)搜索長(zhǎng)度鎖定到3以下時(shí)，若繼續(xù)利用二分法進(jìn)行搜索會(huì)泄露2～3個(gè)校驗(yàn)比特的信息，從而導(dǎo)致該部分的密鑰全部泄露出去；而在截止二分協(xié)商中，當(dāng)分組長(zhǎng)度小于等于3時(shí)，不再搜索錯(cuò)誤比特的位置，而是把這些比特作為待刪除的比特信息直接發(fā)送給對(duì)方，同樣泄露了比特信息。因此改進(jìn)的Cascade協(xié)商效率基本與原始Cascade相同。

交互次數(shù)比較見圖4。

圖4 交互次數(shù)比較

由圖4可知，與原始Cascade協(xié)商方案相比較，改進(jìn)Cascade協(xié)商方案的交互次數(shù)明顯下降。Cascade協(xié)商過程中，回溯過程會(huì)使Alice、Bob之間的交互次數(shù)出現(xiàn)大幅度的增加。而在改進(jìn)的Cascade協(xié)商方案中，采用截止二分協(xié)商，當(dāng)錯(cuò)誤比特所在位置鎖定到3個(gè)比特時(shí)，不再繼續(xù)二分查詢，從而降低了Alice、Bob之間的交互次數(shù)。

4 結(jié)束語(yǔ)

Cascade是經(jīng)典的密鑰協(xié)商方案，由于該方案需要Alice、Bob之間不斷交互信息，從而導(dǎo)致Cascade協(xié)商對(duì)網(wǎng)絡(luò)延遲等較為敏感。文中提出了Cascade的一種改進(jìn)方案。仿真結(jié)果表明，改進(jìn)方案保證了高效率協(xié)商，同時(shí)降低了Alice、Bob之間的交互次數(shù)。

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

[2] 李古月,胡愛群,石 樂.無線信道的密鑰生成方法[J].密碼學(xué)報(bào),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函數(shù)和分組密碼的消息認(rèn)證碼[J].計(jì)算機(jī)學(xué)報(bào),2015,38(4):793-803.

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

[11] 張曉梅.概率統(tǒng)計(jì)在密碼學(xué)中的Hash函數(shù)中的應(yīng)用[J].中國(guó)高新技術(shù)企業(yè),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

時(shí)間：2016-10-24

國(guó)家自然科學(xué)基金資助項(xiàng)目(61372123)

賈仁慶(1989-)，男，碩士，研究方向?yàn)槲锢韺影踩?；吳曉富，教授，研究方向?yàn)槲锢韺影踩恢煨l(wèi)平，教授，研究方向?yàn)闊o線通信信號(hào)處理。

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