MIMO格密码的设计与实现
2018-06-26刘年生
刘年生
集美大学 计算机工程学院,福建 厦门 361021
1 引言
MIMO(Multiple Input Multiple Output)技术最早是由G.Marconi于1908年提出的,用于抑制信道衰落[1]。在过去的50年,经过Cox、Foschini和Andersen等著名学者创造了一系列新的MIMO实现方法,在不增加带宽的情况下,MIMO成倍地提高通信系统的容量和频谱利用率。MIMO从早期单用户模式逐步发展到大规模、3D模式,成为下一代无线通信的关键技术之一[2],应用广泛。
由于MIMO无线传输的内在特性(如传输的广播性、叠加性和共享性等),现有的安全机制缺陷[3],加之攻击者的计算能力越来越强[4]。因而,MIMO通信安全问题备受关注,开始从物理层来解决这一问题[5]。根据大规模MIMO的固有特性,提出一种基于格和OAEP+的密码方案,以提高MIMO通信的安全性。
2 安全模型
Shannon在1949年提出了保密通信模型[6],如图1所示。在图1中 Alice和Bob是一对合法通信用户,Eve是窃听者。当Alice发送消息M给Bob时,先在密钥K的参与下,将明文M加密成密文X,然后将密文X通过公共信道发送给合法接收者Bob。Bob将收到的密文X在密钥K的参与下恢复出明文M。与此同时,窃听者Eve从公共信道上也收到密文X,但在不知道密钥K的情况下恢复明文至少在计算上是困难的。Shannon加密系统比较适合对称密码体制。
图1 Shannon保密通信模型
在Shannon保密通信模型基础上,Wyner提出了窃听信道模型[7],如图2所示。合法通信者Alice和Bob之间的信道为主信道,是无噪声的,而Eve和Alice(或Bob)之间的信道为次信道(即:窃听信道),是有噪声的;将K比特长的数据MK编码成N(N>K)比特长的数据XN通过二级制对称信道(BSC)发送时,可推导出如下关系式:
公式(1)中,Δ为数据不确定性度,H为条件信息熵,φ为XN的一个子集,子集元素个数为μ(μ 图2 Wyner窃听信道模型 在量子计算机时代,原有的许多密码算法如RSA和Diffie-Hellman等不再具有可接受的应用安全性,一般推测认为,只有基于NPC(Nondeterministic Polynomial Complete)或NP-Hard问题的密码算法才具有抗量子计算机攻击的能力。因此,格密码近年来备受关注[9]。格是Rm中一类具有周期性结构离散点的集合。严格地说,格是m维欧式空间Rm的n(n≥m)个线性无关向量组A1,A2,…,An的所有整系数线性组合,即: 向量组 A1,A2,…,An称为格L(A)的一组基,Zn为n维复数集,m称为格的维数,n称为格的秩,当n=m时称为满秩。在格理论研究中,存在一系列困难问题[10],主要有最短向量问题(Shortest Vector Problem,SVP)、最近向量问题(Closest Vector Problem,CVP)、小整数解问题(Small Integer Solution Problem,SIS)和误差学习(Learning With Errors Problem,LWE)等。在不同近似参数γ和不同范数Lp(1≤p≤∞)下,对SVP和CVP问题的计算难度结论是不同的,如表1所示。 表1SVP和CVP计算难度 在表1中,Boas在1981年证明了L∞范数下的精确SVP计算难度是NP-hard的[11],精确CVP计算难度是NP-C的,并猜测在L2范数下精确SVP计算难度同样是NP-hard的。2007年,Peikert证明了近似参数为O n,范数为Lp(p≥2)下n维格的CVP和SVP都是CoNP的。一些与SVP密切相关的格问题,如GapSVP(Decision Shortest Vector Problem)、aSVP(approximation SVP)、SIVP(Shortest Independent Vector Problem)、BDD(Bounded Distance Decoding)等等,都可以归约为不同制约条件下的SVP问题。同样,对一些与CVP密切相关的格问题,存在类似的归约。 LWE和SIS在格问题的最坏情况到一般情况的归约中扮演着重要的角色,这种归约能保证格问题在一般情况下拥有与最坏情况类似的复杂度,在常规的理论求解和分析中,最坏情况的问题困难程度结果比较容易获得。 在Wyner窃听模型下,主信道和窃听信道都采用MIMO方式,不失一般性,假设n×h的MIMO是n根发射天线,h根接收天线,则MIMO接收信号矢量y表示为: 其中,x∈Rn为需要传输的信号矢量,A∈Rn×h为信道增益矩阵,信道增益矩阵的元素值分布为零均值、标准偏差为k/的高斯分布,记为Ψk,e∈Rh为信道噪声,分布为零均值、标准偏差为α/的高斯分布Ψα。对于实数型信道系数的MIMO而言,传输星座图χ可以定义为[0,M)的整数集合。 若用矢量ai表示发射端到第i根接收天线的信道增益,x为来自χn的传输信号矢量,ei为发射端到第i根接收天线的噪声矢量,则第i根接收天线接收的信号为: 若MIMO信道的最小噪声和星座大小满足如下条件,就可以将MIMO解码问题与解标准格问题关联起来,在物理层构建起MIMO格密码,提高信息传送的安全水平[19]。 最小噪声: 星座大小: 其中参数p>0,它是由用户或系统来选择的,是信噪比(SNR)要求与星座大小的折中。 为了把消息x传送给Bob,Alice将对其进行线性预测编码[20],对信道增益矩阵A进行奇异分解得到A=UΣVH,其中,U 是n×n阶酉矩阵,Σ是n×h对角矩阵,VH是h×h阶酉矩阵V 的共轭转置。将x=Vx发送给Bob。Bob收到Alice发来的消息后,计算 y =UHy=Σx+e,由于Σ是A的对角矩阵,表示A的奇异值的;所以Bob能在关于n的线性复杂度内估算出x。同时,注意到U是酉矩阵,因此, 同时,窃听者Eve通过窃听信道收到Vx后,其计算表示为: 应注意到V是关于A的右奇异向量,跟B无关,为一酉矩阵;同时,高斯随机矩阵具有正交不变性[21];所以BV跟B属于同一分布。Eve通过公式(7)恢复出x的困难性等可以归约为解标准格问题(如GapSVP、SIVP和BDD等)的困难性[19],并通过LWE归约机制,保证在一般情况下MIMO解码难度,具有在最坏情况下同样的解码难度,计算复杂度为O()2n,因此,当n足够大时,窃听者Eve即使具备量子计算机的计算能力,也难以恢复出x。 MIMO格密码在理论上被证明是可能的,其实现方案就成为研究者所关注的热点。根据Shoup所提的OAEP+算法[22],设计出一种大规模MIMO格密码实现方案,方案如下: 不妨设K=nlbM是每个MIMO信道所传输的比特数,Alice想把消息m传送给Bob,消息m长度为η=K-2n比特。若Alice和Bob都能访问三个随机预言函数:G:{0,1}n→{0,1}η,H′:{0,1}n+η→{0,1}n,H:{0,1}n+η→{0,1}n。Alice从{0,1}n+η随机均匀选取r,按图3所示的加密公式计算 s∈{0,1}n+η,t∈{0,1}n和 x∈{0,1}K,然后将X与Bob信道的右奇异向量相乘,即:x=Vx,发送给Bob。Bob收到 x消息后,计算 y =UHx,恢复出 X ,按图3所示的解密公式计算,恢复明文消息m,并根据c=H′(r||m)是否成立,验证所收到的Alice消息,如果c=H′(r||m)不成立,则拒绝接受所收到的Alice消息,否则就接受所收到的Alice消息。 图3 MIMO格密码加解密计算流程 在MIMO格密码方案实现时,上述三个随机预言函数G、H和H′一般采用安全散列函数,如SHA-2类(SHA-256、SHA-512等),它们具有高度的雪崩效应和抗碰撞攻击能力。为此,在如下参数设置条件下,α=1,p=0.03,k=0.04,三个随机预言函数G、H和H′就采用SHA-256,用Matlab(2014a版)对该MIMO格密码方案进行了仿真实现,仿真结果证明该方案是可行的。因为方案中采用了安全散列函数,必须保证Alice和Bob之间能正确解码,其误码率低至某一可接受的水平,而Eve不能正确解码。这种安全的解码方式与MIMO信道的可计算保密容量密切相关。根据格基归约算法[23],在参数α=1,p=1条件下MIMO每条信道的可计算保密容量(Computational Secrecy Capacity)如图4所示,随着发射天线数目的增加,MIMO每条信道的可计算保密容量呈线性增长。线性判定系数R2=0.999 8,接近于1,证明这两者之间具有较强的线性拟合关系。 图4 MIMO发射天线数目与每条信道可计算保密容量的关系 尽管发射天线数目的增加既有助于提高抗量子计算攻击,又有助于提高信道保密容量。但是,如果发射天线数目太高,会增加工程实现的困难和成本,在安全性、可实现性和经济性博弈中,合理选取一个发射天线数目。 所提密码方案是基于大规模MIMO的解码复杂性,将大规模MIMO的解码复杂性归约为解标准格问题(如GapSVP、SIVP和BDD等),即使在最坏情况下,它的解码复杂度至少为O(2n)。因此,本方案的计算复杂度随MIMO发射天线n呈指数关系增大,当n足够大时,所提方案具有抗量子计算攻击的能力。其次,在本方案设计中采用了OAEP+算法,而OAEP+算法被证明是具有抗自适应选择性密文攻击的能力[22],本方案自然继承这一特性,具有抗自适应选择性密文攻击的能力;而自适应选择性密文分析是目前已知的最强的密码分析方式,如果一个密码系统能够抵抗自适应选择性密文攻击,那就可以认为它能够抵抗其他常见攻击,包括唯密文攻击、已知明文攻击、选择性明文攻击和非适应性选择密文攻击等。第三,本方案在进行加密通信时双方不需要预先共享密钥,从而简化了密钥管理。 在Wyner窃听信道模型下,利用较强的高斯随机噪声对MIMO信道的影响,使得MIMO信道呈现出复杂的时空动态变化特性,从而将窃听者对大规模MIMO的解码复杂性问题归约为解标准格问题,并利用大规模MIMO信道增益矩阵的奇异分解特性和OAEP+算法原理,构建出一种MIMO格密码实现方案,并在Matlab开源平台中进行了原型验证,结果证明所提方案是可行的,加密通信双方不需要预共享密钥。仿真计算结果还显示在格基归约算法下MIMO信道保密容量与发射天线的数目呈较强线性关系,MIMO发射天线数目越多,信道保密容量相应增大。 [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] 王小云,刘明洁.格密码学研究[J].密码学报,2014,1(1):13-27. [10]王旭阳,胡爱群.格困难问题的复杂度分析[J].密码学报,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.3 格密码
4 MIMO格密码原理
5 MIMO格密码的实现与分析
6 结束语