MIMO格密碼的設(shè)計(jì)與實(shí)現(xiàn)

劉年生

集美大學(xué) 計(jì)算機(jī)工程學(xué)院，福建 廈門 361021

1 引言

MIMO（Multiple Input Multiple Output）技術(shù)最早是由G.Marconi于1908年提出的，用于抑制信道衰落[1]。在過去的50年，經(jīng)過Cox、Foschini和Andersen等著名學(xué)者創(chuàng)造了一系列新的MIMO實(shí)現(xiàn)方法，在不增加帶寬的情況下，MIMO成倍地提高通信系統(tǒng)的容量和頻譜利用率。MIMO從早期單用戶模式逐步發(fā)展到大規(guī)模、3D模式，成為下一代無(wú)線通信的關(guān)鍵技術(shù)之一[2]，應(yīng)用廣泛。

由于MIMO無(wú)線傳輸?shù)膬?nèi)在特性（如傳輸?shù)膹V播性、疊加性和共享性等），現(xiàn)有的安全機(jī)制缺陷[3]，加之攻擊者的計(jì)算能力越來(lái)越強(qiáng)[4]。因而，MIMO通信安全問題備受關(guān)注，開始從物理層來(lái)解決這一問題[5]。根據(jù)大規(guī)模MIMO的固有特性，提出一種基于格和OAEP+的密碼方案，以提高M(jìn)IMO通信的安全性。

2 安全模型

Shannon在1949年提出了保密通信模型[6]，如圖1所示。在圖1中 Alice和Bob是一對(duì)合法通信用戶，Eve是竊聽者。當(dāng)Alice發(fā)送消息M給Bob時(shí)，先在密鑰K的參與下，將明文M加密成密文X，然后將密文X通過公共信道發(fā)送給合法接收者Bob。Bob將收到的密文X在密鑰K的參與下恢復(fù)出明文M。與此同時(shí)，竊聽者Eve從公共信道上也收到密文X，但在不知道密鑰K的情況下恢復(fù)明文至少在計(jì)算上是困難的。Shannon加密系統(tǒng)比較適合對(duì)稱密碼體制。

圖1 Shannon保密通信模型

在Shannon保密通信模型基礎(chǔ)上，Wyner提出了竊聽信道模型[7]，如圖2所示。合法通信者Alice和Bob之間的信道為主信道，是無(wú)噪聲的，而Eve和Alice（或Bob）之間的信道為次信道（即：竊聽信道），是有噪聲的；將K比特長(zhǎng)的數(shù)據(jù)MK編碼成N(N>K)比特長(zhǎng)的數(shù)據(jù)XN通過二級(jí)制對(duì)稱信道（BSC）發(fā)送時(shí)，可推導(dǎo)出如下關(guān)系式：

公式（1）中，Δ為數(shù)據(jù)不確定性度，H為條件信息熵，φ為XN的一個(gè)子集，子集元素個(gè)數(shù)為μ(μ

圖2 Wyner竊聽信道模型

3 格密碼

在量子計(jì)算機(jī)時(shí)代，原有的許多密碼算法如RSA和Diffie-Hellman等不再具有可接受的應(yīng)用安全性，一般推測(cè)認(rèn)為，只有基于NPC（Nondeterministic Polynomial Complete）或NP-Hard問題的密碼算法才具有抗量子計(jì)算機(jī)攻擊的能力。因此，格密碼近年來(lái)備受關(guān)注[9]。格是Rm中一類具有周期性結(jié)構(gòu)離散點(diǎn)的集合。嚴(yán)格地說，格是m維歐式空間Rm的n(n≥m)個(gè)線性無(wú)關(guān)向量組A1,A2,…,An的所有整系數(shù)線性組合，即：

向量組 A1,A2,…,An稱為格L(A)的一組基，Zn為n維復(fù)數(shù)集，m稱為格的維數(shù)，n稱為格的秩，當(dāng)n=m時(shí)稱為滿秩。在格理論研究中，存在一系列困難問題[10]，主要有最短向量問題（Shortest Vector Problem，SVP）、最近向量問題（Closest Vector Problem，CVP）、小整數(shù)解問題（Small Integer Solution Problem，SIS）和誤差學(xué)習(xí)（Learning With Errors Problem，LWE）等。在不同近似參數(shù)γ和不同范數(shù)Lp(1≤p≤∞)下，對(duì)SVP和CVP問題的計(jì)算難度結(jié)論是不同的，如表1所示。

表1SVP和CVP計(jì)算難度

在表1中，Boas在1981年證明了L∞范數(shù)下的精確SVP計(jì)算難度是NP-hard的[11]，精確CVP計(jì)算難度是NP-C的，并猜測(cè)在L2范數(shù)下精確SVP計(jì)算難度同樣是NP-hard的。2007年，Peikert證明了近似參數(shù)為O n，范數(shù)為L(zhǎng)p(p≥2)下n維格的CVP和SVP都是CoNP的。一些與SVP密切相關(guān)的格問題，如GapSVP（Decision Shortest Vector Problem）、aSVP（approximation SVP）、SIVP（Shortest Independent Vector Problem）、BDD（Bounded Distance Decoding）等等，都可以歸約為不同制約條件下的SVP問題。同樣，對(duì)一些與CVP密切相關(guān)的格問題，存在類似的歸約。

LWE和SIS在格問題的最壞情況到一般情況的歸約中扮演著重要的角色，這種歸約能保證格問題在一般情況下?lián)碛信c最壞情況類似的復(fù)雜度，在常規(guī)的理論求解和分析中，最壞情況的問題困難程度結(jié)果比較容易獲得。

4 MIMO格密碼原理

在Wyner竊聽模型下，主信道和竊聽信道都采用MIMO方式，不失一般性，假設(shè)n×h的MIMO是n根發(fā)射天線，h根接收天線，則MIMO接收信號(hào)矢量y表示為：

其中，x∈Rn為需要傳輸?shù)男盘?hào)矢量，A∈Rn×h為信道增益矩陣，信道增益矩陣的元素值分布為零均值、標(biāo)準(zhǔn)偏差為k/的高斯分布，記為Ψk，e∈Rh為信道噪聲，分布為零均值、標(biāo)準(zhǔn)偏差為α/的高斯分布Ψα。對(duì)于實(shí)數(shù)型信道系數(shù)的MIMO而言，傳輸星座圖χ可以定義為[0,M)的整數(shù)集合。

若用矢量ai表示發(fā)射端到第i根接收天線的信道增益，x為來(lái)自χn的傳輸信號(hào)矢量，ei為發(fā)射端到第i根接收天線的噪聲矢量，則第i根接收天線接收的信號(hào)為：

若MIMO信道的最小噪聲和星座大小滿足如下條件，就可以將MIMO解碼問題與解標(biāo)準(zhǔn)格問題關(guān)聯(lián)起來(lái)，在物理層構(gòu)建起MIMO格密碼，提高信息傳送的安全水平[19]。

最小噪聲：

星座大小：

其中參數(shù)p>0，它是由用戶或系統(tǒng)來(lái)選擇的，是信噪比（SNR）要求與星座大小的折中。

為了把消息x傳送給Bob，Alice將對(duì)其進(jìn)行線性預(yù)測(cè)編碼[20]，對(duì)信道增益矩陣A進(jìn)行奇異分解得到A=UΣVH，其中，U 是n×n階酉矩陣，Σ是n×h對(duì)角矩陣，VH是h×h階酉矩陣V 的共軛轉(zhuǎn)置。將x=Vx發(fā)送給Bob。Bob收到Alice發(fā)來(lái)的消息后，計(jì)算 y =UHy=Σx+e，由于Σ是A的對(duì)角矩陣，表示A的奇異值的；所以Bob能在關(guān)于n的線性復(fù)雜度內(nèi)估算出x。同時(shí)，注意到U是酉矩陣，因此，

同時(shí)，竊聽者Eve通過竊聽信道收到Vx后，其計(jì)算表示為：

應(yīng)注意到V是關(guān)于A的右奇異向量，跟B無(wú)關(guān)，為一酉矩陣；同時(shí)，高斯隨機(jī)矩陣具有正交不變性[21]；所以BV跟B屬于同一分布。Eve通過公式（7）恢復(fù)出x的困難性等可以歸約為解標(biāo)準(zhǔn)格問題（如GapSVP、SIVP和BDD等）的困難性[19]，并通過LWE歸約機(jī)制，保證在一般情況下MIMO解碼難度，具有在最壞情況下同樣的解碼難度，計(jì)算復(fù)雜度為O()2n，因此，當(dāng)n足夠大時(shí)，竊聽者Eve即使具備量子計(jì)算機(jī)的計(jì)算能力，也難以恢復(fù)出x。

5 MIMO格密碼的實(shí)現(xiàn)與分析

MIMO格密碼在理論上被證明是可能的，其實(shí)現(xiàn)方案就成為研究者所關(guān)注的熱點(diǎn)。根據(jù)Shoup所提的OAEP+算法[22]，設(shè)計(jì)出一種大規(guī)模MIMO格密碼實(shí)現(xiàn)方案，方案如下：

不妨設(shè)K=nlbM是每個(gè)MIMO信道所傳輸?shù)谋忍財(cái)?shù)，Alice想把消息m傳送給Bob，消息m長(zhǎng)度為η=K-2n比特。若Alice和Bob都能訪問三個(gè)隨機(jī)預(yù)言函數(shù)：G:{0,1}n→{0,1}η，H′:{0,1}n+η→{0,1}n，H:{0,1}n+η→{0,1}n。Alice從{0,1}n+η隨機(jī)均勻選取r，按圖3所示的加密公式計(jì)算 s∈{0,1}n+η，t∈{0,1}n和 x∈{0,1}K，然后將X與Bob信道的右奇異向量相乘，即：x=Vx，發(fā)送給Bob。Bob收到 x消息后，計(jì)算 y =UHx，恢復(fù)出 X ，按圖3所示的解密公式計(jì)算，恢復(fù)明文消息m，并根據(jù)c=H′(r||m)是否成立，驗(yàn)證所收到的Alice消息，如果c=H′(r||m)不成立，則拒絕接受所收到的Alice消息，否則就接受所收到的Alice消息。

圖3 MIMO格密碼加解密計(jì)算流程

在MIMO格密碼方案實(shí)現(xiàn)時(shí)，上述三個(gè)隨機(jī)預(yù)言函數(shù)G、H和H′一般采用安全散列函數(shù)，如SHA-2類（SHA-256、SHA-512等），它們具有高度的雪崩效應(yīng)和抗碰撞攻擊能力。為此，在如下參數(shù)設(shè)置條件下，α=1，p=0.03，k=0.04，三個(gè)隨機(jī)預(yù)言函數(shù)G、H和H′就采用SHA-256，用Matlab（2014a版）對(duì)該MIMO格密碼方案進(jìn)行了仿真實(shí)現(xiàn)，仿真結(jié)果證明該方案是可行的。因?yàn)榉桨钢胁捎昧税踩⒘泻瘮?shù)，必須保證Alice和Bob之間能正確解碼，其誤碼率低至某一可接受的水平，而Eve不能正確解碼。這種安全的解碼方式與MIMO信道的可計(jì)算保密容量密切相關(guān)。根據(jù)格基歸約算法[23]，在參數(shù)α=1，p=1條件下MIMO每條信道的可計(jì)算保密容量（Computational Secrecy Capacity）如圖4所示，隨著發(fā)射天線數(shù)目的增加，MIMO每條信道的可計(jì)算保密容量呈線性增長(zhǎng)。線性判定系數(shù)R2=0.999 8，接近于1，證明這兩者之間具有較強(qiáng)的線性擬合關(guān)系。

圖4 MIMO發(fā)射天線數(shù)目與每條信道可計(jì)算保密容量的關(guān)系

盡管發(fā)射天線數(shù)目的增加既有助于提高抗量子計(jì)算攻擊，又有助于提高信道保密容量。但是，如果發(fā)射天線數(shù)目太高，會(huì)增加工程實(shí)現(xiàn)的困難和成本，在安全性、可實(shí)現(xiàn)性和經(jīng)濟(jì)性博弈中，合理選取一個(gè)發(fā)射天線數(shù)目。

所提密碼方案是基于大規(guī)模MIMO的解碼復(fù)雜性，將大規(guī)模MIMO的解碼復(fù)雜性歸約為解標(biāo)準(zhǔn)格問題（如GapSVP、SIVP和BDD等），即使在最壞情況下，它的解碼復(fù)雜度至少為O(2n)。因此，本方案的計(jì)算復(fù)雜度隨MIMO發(fā)射天線n呈指數(shù)關(guān)系增大，當(dāng)n足夠大時(shí)，所提方案具有抗量子計(jì)算攻擊的能力。其次，在本方案設(shè)計(jì)中采用了OAEP+算法，而OAEP+算法被證明是具有抗自適應(yīng)選擇性密文攻擊的能力[22]，本方案自然繼承這一特性，具有抗自適應(yīng)選擇性密文攻擊的能力；而自適應(yīng)選擇性密文分析是目前已知的最強(qiáng)的密碼分析方式，如果一個(gè)密碼系統(tǒng)能夠抵抗自適應(yīng)選擇性密文攻擊，那就可以認(rèn)為它能夠抵抗其他常見攻擊，包括唯密文攻擊、已知明文攻擊、選擇性明文攻擊和非適應(yīng)性選擇密文攻擊等。第三，本方案在進(jìn)行加密通信時(shí)雙方不需要預(yù)先共享密鑰，從而簡(jiǎn)化了密鑰管理。

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

在Wyner竊聽信道模型下，利用較強(qiáng)的高斯隨機(jī)噪聲對(duì)MIMO信道的影響，使得MIMO信道呈現(xiàn)出復(fù)雜的時(shí)空動(dòng)態(tài)變化特性，從而將竊聽者對(duì)大規(guī)模MIMO的解碼復(fù)雜性問題歸約為解標(biāo)準(zhǔn)格問題，并利用大規(guī)模MIMO信道增益矩陣的奇異分解特性和OAEP+算法原理，構(gòu)建出一種MIMO格密碼實(shí)現(xiàn)方案，并在Matlab開源平臺(tái)中進(jìn)行了原型驗(yàn)證，結(jié)果證明所提方案是可行的，加密通信雙方不需要預(yù)共享密鑰。仿真計(jì)算結(jié)果還顯示在格基歸約算法下MIMO信道保密容量與發(fā)射天線的數(shù)目呈較強(qiáng)線性關(guān)系，MIMO發(fā)射天線數(shù)目越多，信道保密容量相應(yīng)增大。

[1]Andersen J B.History of communications/radio wave propagation from marconi to MIMO[J].IEEE Communications Magazine，2017，55（2）：6-10.

[2]Larsson E G，Edfors O，Tufvesson F，et al.Massive MIMO for next generation wireless systems[J].IEEE Communications Magazine，2014，52（2）：186-195.

[3]Wallace J W，Sharma R K.Automatic secret keys from reciprocalMIMO wirelesschannels：Measurementand analysis[J].IEEE Transactions on Information Forensics and Security，2010，5（3）：381-392.

[4]Kapetanovic D，Zheng G，Rusek F.Physical layer security for massive MIMO：An overview on passive eavesdropping and active attacks[J].IEEE Communications Magazine，2015，53（6）：21-27.

[5]Poor H V，Schaefer R F.Wireless physical layer security[J].Proceedings of the National Academy of Sciences Current Issue，2017，114（1）：19-26.

[6]Shannon C E.Communication theory of secrecy systems[J].Bell System Technical Journal，2014，28（4）：656-715.

[7]Wyner A D.The wire-tap channel[J].Bell System Technical Journal，1975，54（8）：1355-1387.

[8]Ozarow L H，Wyner A D.Wire-tap channel II[J].Bell System Technical Journal，1984，63（10）：2135-2157.

[9] 王小云，劉明潔.格密碼學(xué)研究[J].密碼學(xué)報(bào)，2014，1（1）：13-27.

[10]王旭陽(yáng)，胡愛群.格困難問題的復(fù)雜度分析[J].密碼學(xué)報(bào)，2015，2（1）：1-16.

[11]Boas P E.Another NP-complete partition problem and the complexity of computing short vectors in a lattice，Technical Report 81-04[R].Mathematische Instituut，University of Amsterdam，1981.

[12]Ajtai M O.The shortest vector problem in L2 is NP-hard for randomized reductions（extended abstract）[C]//Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing，Dallas，Texas，USA，1998：10-19.

[13]Micciancio D.Inapproximability of the shortest vector problem：Toward a deterministic reduction[J].Theory of Computing，2012，8（1）：487-512.

[14]Khot S.Hardness of approximating the shortest vector problem in lattices[C]//45th Symposium on Foundations of Computer Science（FOCS 2004），Rome，Italy，2004：126-135.

[15]Haviv I，Regev O.Tensor-based hardness of the shortest vector problem to within almost polynomial factors[C]//Proceedings of the 39th Annual ACM Symposium on Theory of Computing，San Diego，California，USA，2007：469-477.

[16]Peikert C.Limits on the hardness of lattice problems in Lp norms[J].Computational Complexity，2008，17（2）：300-351.

[17]Arora S，Babai L，Stern J，et al.The hardness of approximate optima in lattices，codes，and systems of linear equations[C]//34th Annual Symposium on Foundations of Computer Science，1993：724-733.

[18]Dinur I，Kindler G，Raz R，et al.Approximating CVP to within almost-Polynomial factors is NP-hard[J].Combinatorica，2003，23（2）：205-243.

[19]Dean T R，Goldsmith A J.Physical-layer cryptography through massive MIMO[J].IEEE Transactions on Information Theory，2017，63（8）：5419-5436.

[20]Goldsmith A J.Wireless communications[M].Cambridge，MA，USA：Cambridge University Press，2004.

[21]Edelman A，Rao N.Random matrix theory[J].Acta Numerica，2005，14：233-297.

[22]Shoup V.OAEP reconsidered[C]//Proceedings of 21st Annual International Cryptology Conference，Santa Barbara，California，USA，2001：239-259.

[23]Micciancio D，Walter M.Practical predictable lattice basis reduction[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques，Vienna，Austria，2016：820-849.