基于熱帶矩陣密鑰交換協議的密碼分析

黃華偉，李春華

(1.貴州師范大學 數學科學學院，貴州 貴陽 550001；2.華東交通大學 理學院，江西 南昌 330013)

1 概 述

量子計算機的發展對目前廣泛使用的公鑰密碼體制構成了潛在的威脅，具有抗量子分析的密碼體制受到了廣泛關注[1]。目前抗量子分析密碼體制主要基于交換代數結構，如交換群和交換環[2]。許多學者都希望找到可用于密碼學的新的非交換代數結構。例如，Maze提出了基于半群作用問題的公鑰加密方案[3]。Baumslag等[4]把格密碼研究領域中的帶噪聲的學習問題推廣到一般的代數群上，進而構造出非交換密碼方案。Bagheri等[5]提出基于四元數代數的非交換NTRU型密碼體制。Climent等[6]提出基于非交換Bergman環的密碼體制，但被Zhang破解[7]。

近年來，隨著熱帶代數(Tropical Algebra)的研究逐漸深入，熱帶代數理論和計算理論研究方面都有很大進展。Grigoriev[8]提出了求解整系數熱帶齊次線性方程組和整系數熱帶非齊次線性方程組的多項式時間算法，并證明了求解實系數熱帶齊次線性方程組是NP-C問題。無論是超定還是未定的實系數熱帶線性方程組求解都是NP-C問題。Maze等[9]首先提出了基于一類六元單半環的半群作用問題的密碼體制，但Steinwandt等[10]利用六元單半環的運算性質破解了該方案。Atani[11]提出了基于因子半環上的半模的密碼系統。Durcheva[12]提出基于冪等半環的密碼協議。Ahmed等[13]詳細分析了它們的缺點并破解了這兩個方案。Grigoriev，Shpilrain[14]證明了求解多變量熱帶非線性多項式方程組是NP問題，并首次使用熱帶矩陣半環作為平臺來構造密碼系統，提出了基于熱帶矩陣的公鑰密碼體制。由于熱帶代數只涉及數的加法和比較大小兩種運算，因此基于熱帶代數的密碼體制一般效率都非常高。2018年，Kotov等[15]根據整數熱帶矩陣的代數性質破解了該方案。2019年，Grigoreiv，Shpilrain[16]對原方案進行了改進，提出基于熱帶矩陣半環的半直積的公鑰密碼體制。

該文主要研究文獻[16]基于熱帶矩陣半環半直積的密鑰交換協議的安全性，提出了一種攻擊方法。從協議的公開信息通過簡單的二分查找就可獲得用戶的私鑰。結果表明文中的熱帶代數結構并不適合構建公鑰密碼體制。

2 整數的熱帶半環

令Z為整數集合,Z上的熱帶半環[14,16](tropical semi-ring)為(Z∪{∞},⊕,?),其運算為：

(?x,y∈Z)x⊕y=min{x,y},x?y=x+y

(?x∈Z)∞⊕x=x⊕∞=x, ∞?x=x?∞=∞

即(Z∪{∞},⊕)與(Z∪{∞},?)都是半群,且?對⊕滿足分配律。

熱帶半環(Z∪{∞},⊕,?)滿足以下性質[14,16]：

(1)(Z∪{∞},⊕)是交換半群,∞為單位元;

(2)(Z∪{∞},?)是交換半群,無單位元;

(3)(?x∈Z∪{∞})x⊕x=x。

令Uk為Z∪{∞}上所有的k×k矩陣,即:

Uk={(aij)k×k|aij∈Z∪{∞}}

在U上定義運算°如下：

引理[16]：令Ω={(M,H)|M,H∈Uk}，在Ω上定義運算?如下：

(M1,H1)?(M2,H2)=(M1H2+M2,H1H2)

3 熱帶矩陣半環半直積的密鑰交換協議

用戶Alice與用戶Bob希望通過協議交換共享密鑰。首先，他們選取公開的M,H∈Uk，Alice選取保密的正整數m，Bob選取保密的正整數n。

文獻[16]的基于熱帶矩陣半環半直積的密鑰交換協議如下：

(1)Alice計算(M,H)m=(A,Hm)，將A發送給Bob;

(2)Bob計算(M,H)n=(B,Hn)，將B發送給Alice;

(3)Alice計算KA=BHm+A；Bob計算KB=AHn+B。

因為，

(M,H)m+n=(M,H)m?(M,H)n=

(A,Hm)?(B,Hn) =

(AHn+B,Hm+n)

(M,H)m+n=(M,H)n?(M,H)m=

(B,Hn)?(A,Hm) =

(BHm+A,Hm+n)

所以，Alice與Bob交換了共享密鑰K=KA=KB。

(1)Alice計算

(2)Bob計算

(3)Alice計算

KA=BH13+A=

Bob計算

KB=AH11+B=

該協議的優點是執行速度很快,因為所有的運算都只有整數的加法和比較大小。

4 基于熱帶矩陣半環半直積的密鑰交換協議的密碼分析

從協議可知矩陣M,H,A,B都是公開的，正整數m,n是保密的。如果能求出正整數m或n,那么易求出共享密鑰。

由整數熱帶半環的加法定義x⊕y=min{x,y},顯然x⊕y≤x,且x⊕y≤y。下面定義一種矩陣的比較大小關系，易知熱帶矩陣加法也有類似的性質。

定義1：令A=(aij),B=(bij)∈Uk，若?i,j(1≤i≤k,1≤j≤k)都有aij≤bij，則稱矩陣A小于等于矩陣B，記為A≤B。

定義2：令A=(aij),B=(bij)∈Uk，若?i,j(1≤i≤k,1≤j≤k)都有aij≤bij且存在i,j(1≤i≤k,1≤j≤k)使aij

定理1：令A=(aij),B=(bij)∈Uk，則A+B≤A,且A+B≤B。

由運算定義：

(M1,H1)?(M2,H2)=(M1H2+M2,H1H2)

根據命題1，M1H1+M1≤M1，因此(M1,H1)2的第一個分量矩陣小于(M1,H1)的第一個分量矩陣。類似地，(M1,H1)3的第一個分量矩陣小于(M1,H1)2的第一個分量矩陣，……。因此(M1,H1),(M1,H1)2,(M1,H1)3,……。關于第一個分量矩陣是一個遞減矩陣序列。

……

由協議知，(M,H)m=(A,Hm)，容易看到，通過簡單的二分查找就可以由A求出m。

假設用戶A的私鑰整數m滿足：1≤m≤r，則攻擊算法如下：

基于熱帶矩陣半環半直積的密鑰交換協議的攻擊算法：

輸入：矩陣M,H,A(滿足(M,H)m=(A,Hm));

輸出：m

(1)令left=1,right=r;

(2)若left≤right，執行下面循環

(i)mid=left+(right-left)/2;

(ii)計算(M,H)mid=(P,Q)

若P

若A

若P=A，則輸出m=mid結束。

例3：用上述算法破解例1。

在Intel(R) Core(TM) i7-5500 CPU @ 2.40 GHz處理器的計算機上運行攻擊算法的C程序。

實驗一：

按照文獻[16]的建議參數：矩陣的階k=30,矩陣的元屬于[-1 000,1 000]，在Intel(R) Core(TM) i7-5500 CPU @ 2.40 GHz處理器的計算機上運行攻擊算法的C程序，結果見表1和圖1。

表1 攻擊算法運行時間隨指數變化情況

(注：r為指數的上界)

實驗二：

指數固定為m=250-1,r=262-1，矩陣元素取自[-1 000,1 000]。在Intel(R) Core(TM) i7-4700MQ CPU @ 2.40 GHz處理器的計算機上運行攻擊算法的C程序，結果見表2和圖2。

表2 攻擊算法運行時間隨矩陣階k變化情況

圖2 攻擊算法運行時間隨矩陣階k變化情況

固定為r=80，攻擊算法的時間復雜度隨矩陣階k增大的情況比較見表3，攻擊算法時間復雜度隨矩陣階變化情況見圖3。

表3 攻擊算法時間復雜度隨矩陣階k變化情況

(注：矩陣的階為10e，攻擊算法時間復雜度O(2d))

實驗三：

指數固定為m=230-1,r=245-1，矩陣的階固定為k=30。在Intel(R) Core(TM) i7-4700MQ CPU @ 2.40 GHz處理器的計算機上運行攻擊算法的C程序，結果見表4和圖4。

表4 攻擊算法運行時間隨矩陣元素取值范圍變化情況

(注：矩陣元素取值范圍為[-p,p])

實驗三表明，矩陣元素的取值范圍對攻擊算法的時間復雜度影響不大。

5 結束語

該文分析了Grigoriev和Shpilrain[16]提出的基于熱帶矩陣半環半直積密鑰交換協議的安全性, 在Ω={(M,H)|M,H∈Uk}定義的半直積運算具有部分的保序性，由其乘法定義(M1,H1)?(M2,H2)=(M1H2+M2,H1H2)可知，其第一個矩陣分量小于等于M2,這使得{(M1,H1)n}關于第一個分量矩陣構成了一個單調遞減序列。據此，給出了一種二分查找的攻擊算法。該算法通過公開信息可以求用戶密鑰，從而破解了該協議。該攻擊算法的比特位運算的計算復雜度為O(2log2r(2k3+5k2))，其中r為指數上界，k為矩陣的階。實驗結果表明，如果協議參數選取自Grigoriev和Shpilrain建議的范圍，攻擊算法在1分鐘之內就能求出私鑰。矩陣元素的取值范圍對攻擊算法的時間復雜度影響不大。對攻擊算法有影響的參數是矩陣的階k和指數取值的上界r，而其中矩陣的階k的影響又是最主要的。從表3可以看到，除非將矩陣的階增大到100萬階以上，否則即使增大協議的參數，該攻擊仍然有效。因此，熱帶半環代數結構(Ω,?)并不適合構建安全的密碼體制。