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

黃華偉，李春華

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

1 概 述

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

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

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

2 整數(shù)的熱帶半環(huán)

令Z為整數(shù)集合,Z上的熱帶半環(huán)[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∪{∞},?)都是半群,且?對⊕滿足分配律。

熱帶半環(huán)(Z∪{∞},⊕,?)滿足以下性質(zhì)[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 熱帶矩陣半環(huán)半直積的密鑰交換協(xié)議

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

文獻[16]的基于熱帶矩陣半環(huán)半直積的密鑰交換協(xié)議如下：

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

(2)Bob計算(M,H)n=(B,Hn)，將B發(fā)送給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=

該協(xié)議的優(yōu)點是執(zhí)行速度很快,因為所有的運算都只有整數(shù)的加法和比較大小。

4 基于熱帶矩陣半環(huán)半直積的密鑰交換協(xié)議的密碼分析

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

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

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

定義2：令A(yù)=(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(yù)=(aij),B=(bij)∈Uk，則A+B≤A,且A+B≤B。

由運算定義：

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

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

……

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

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

基于熱帶矩陣半環(huán)半直積的密鑰交換協(xié)議的攻擊算法：

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

輸出：m

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

(2)若left≤right，執(zhí)行下面循環(huán)

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

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

若P

若A

若P=A，則輸出m=mid結(jié)束。

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

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

實驗一：

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

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

(注：r為指數(shù)的上界)

實驗二：

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

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

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

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

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

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

實驗三：

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

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

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

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

5 結(jié)束語

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