基于E-DP和DLP一種無限非交換群上的密鑰交換協議

東莞職業技術學院現代工業創新實踐中心 張靜

首先，本文提出與分解問題等價的一個困難問題：等價分解問題。其次，基于等價分解問題(E-DP)和離散對數問題(DLP)，提出了一種無限非交換群上的密鑰交換協議。在協議中，通過半直積的運算法則，使共享密鑰同時包含兩個困難問題。這兩個困難問題共同保證了密鑰交換協議的抗攻擊性。最后利用代數攻擊和暴力攻擊進行分析，證明了協議具有較高的安全性。

Sidelnikov等人提出在無限非交換群和半群上建立公鑰密碼系統的思想[1]。非交換群上的公鑰密碼系統主要是應用困難問題隱藏因子，公開的困難問題有共軛搜索問題、分解問題、子群元素搜索問題、離散對數問題、同態搜索問題等。許多研究已經提出了一些非交換代數結構上基于困難問題的密鑰交換協議。在文獻[2]中，作者提出了無限非交換群上基于分解問題的密鑰交換協議[2]。

在文獻[3]中，作者提出了辮群上基于共軛搜索問題的一種新的密碼系統[3]，其中辮群是一種無限非交換群，并具有很好的密碼特征。隨著量子算法和分解算法的發展[4]，只應用一個困難問題已經不能保證密碼系統的安全性。而且單獨應用共軛搜索問題構建的密碼系統也已經被證明對于安全性是不充分的[5]。為了提高安全性需要同時使用幾個困難問題，2007年，Eligijus等人同時使用共軛搜索問題和離散對數問題在非交換群上構建了一種密碼協議，并闡明了同時使用兩個困難問題足夠保證密碼交換協議的安全性[6]。2013年，Maggie Habeeb等人第一次將群的半直積用到密碼系統中，并提出了一種基于半直積運算的密碼交換協議[7]。

本文，首先提出了等價分解問題，它是分解問題的一種變形，它的求解困難性與分解問題的困難性相同。其次通過半直積的運算法則，構建了基于離散對數問題和等價分解問題在無限非交換群上的密鑰交換協議。因為目前在非交換群上沒有分解困難問題的有效量子算法，并且同時在密鑰協議中設置兩個困難問題可大大提高密鑰的安全性，所以該密碼交換協議具有抗量子攻擊性。最后，通過代數攻擊和暴力攻擊分析，闡明了該協議的安全性。

1 數學知識

定義1 (半直積)：(G,·)和(G',。） 是兩個半群， Aut(G)是G的自同構群，其二元運算是合成運算。ρ:G'→Aut(G)是一個自同構，G和G'的半直積是一個元素對集合：

其二元運算定義為：

其中，g,g`∈G和h,h`∈G`,gρ(h`)表示g在自同構ρ(h`)下的像。

如果G`=Aut(G)，ρ=idG,那么

其二元運算為：

Bij(G)表示G→G上所有雙射構成的集合。在本文的密鑰交換協議中，只需要映射是雙射，即在集合中，仍按以上方式定義二元運算其中表示雙射的合成運算，并定義1(g,φ)， m∈Z+。如果G是一個群，對于?a,b∈G，讓，顯然 是一個雙射，并且那么有

定義2 (中心化子)：G是一個群，g∈G，那么集合

是g的中心化子。

事實上，CG(g)是G的子群，對于?a∈CG(g)滿足ag=ga。

定義3 (等價分解問題): G是一個群，對于?μ,找到滿足μ=α.?n，其中n∈Z+。

定義4 (離散對數問題): G是一個群，對于?μ,找到滿足

2 密鑰交換協議

公鑰：g

私鑰：m,n,k,h

步驟1：Alice選擇私鑰m∈Z+和k∈G滿足kg≠gk，那么她有映射計算中心化子CG(k-1)，選擇中心化子的一個子群G'，使得|G'|≥N，其中N是正整數。Alice計算積：

讓A=k-(m-1)gm，A'=k-1A=k-mgm, 發送A'和G'給Bob。

步驟2：Bob選擇私鑰n∈Z+和h∈G'滿足hg≠gh，那么他有映射Bob計算積：

讓B=h-(n-1)gn,B'=h-1B=h-ngn,發送B'給Alice。

步驟3：Alice計算：

如果你在威尼斯，不如徜徉在迷人的廣場下或者乘坐浪漫的貢多拉（威尼斯特有的小船），當然，起泡酒必不可少，與兩三好友享受此地的浪漫。如果貢多拉的浪漫不適合你，那就試找家地道的意大利餐廳，坐下吃吃意大利面吧，開瓶當地紅酒相配，相信那會是番茄肉醬意粉的最佳拍檔！

這樣Alice的密鑰為：

步驟4：Bob計算：

因為h∈G',G'是一個群，所以h-1∈G'，有等式：

即對于?m,n∈Z+，h-nk-mgm+n=k-mh-ngm+n,得到

共享密鑰為：

在計算CG(k-1)中，Alice不必算出中心化子CG(k-1)中所有的元素，她只需計算出滿足安全要求的元素數量。當Alice發送子群G'給Bob時，她也只發送G'的生成元集合S，即G'=〈S〉。密鑰交換流程如圖1所示，密鑰交換運算量如表1所示。

圖1 密鑰交換協議流程圖Fig.1 Flow chart of key exchange protocol

表1 密鑰交換協議運算量Tab.1 The amount of computation in the key exchange protocol

3 安全性

本文的密鑰交換協議的安全性依賴于無限非交換群上的兩個困難問題：等價分解問題(E-DP)和離散對數問題(DLP)。在構建密鑰過程中，A'和B'通過公共信道被發送，攻擊者可以觀察到；而對攻擊者來說k-m和h-n是未知的，將他們分別看做一個整體，從A'=k-mgm和B'=h-ngn中計算k-m,h-n,gm,gn就是等價分解問題，計算m和n，攻擊者必須解離散對數問題。

Alice和Bob通過公共信道發送信息，攻擊者能夠觀察到傳輸的協議，并得到一個三元組(g,A'=k-mgm,B'=h-ngn)，他的目的是得到共享密鑰K。如果他能從A'中算出k-m和gm，那么共享密鑰K=k-mB'gm就能被得到。類似的，如果他能從B'中算出h-n和gn，那么共享密鑰也能被得到。這里，僅考慮以上兩種情況中的第一種。

3.1 代數攻擊

從上式中計算私鑰m是一個離散對數問題，因此沒有多項式時間算法可以找到m。這樣，讓A代替gm，得到

攻擊者也可以選擇任意一個正整數m∈Z+，讓代替m，代替gm，那么有以下等式：

3.2 暴力攻擊

暴力攻擊意味著攻擊者找遍所有可能的密鑰。因為k∈G，h∈G'并且G'＜G，所以攻擊者從G'入手進行攻擊效率更高，即攻擊者尋找所有可能的和n∈Z+，滿足因為G'＜CG(k)，有N≤|G'|≤|CG(k)|，即至少有N種可能性。假設元素g的階是γ，那么攻擊者必須計算γ次gi(i≤γ)。所以暴力攻擊的復雜度介于Nγ和|CG(k)|γ之間。因為G是無限群，可以選擇具有足夠大的N、|CG(k)|和γ的元素以保證協議的安全性，因此通過暴力攻擊獲得共享密鑰也是不可能的。

引用

[1] Sidel'Nikov V M,Cherepnev M A,Yashchenko V V.Systems of Open Distribution of Keys on the Basis of Noncommutative Semigroups[J].Doklady Mathematics,1993,48(2):566-567.

[2] SHPILRAIN V,USHAKOV A.A New Key Exchange Protocol Based on the Decomposition Problem[J].Contemp.Math.Amer.Math.Soc,2005,172(2):161-167.

…………

[3] Ko K H,Sang J L,Cheon J H,et al.New Public-Key Cryptosystem Using Braid Groups[C]//Annual International Cryptology Conference.Springer,Berlin,Heidelberg,2000.

[4] MYASNIKOV A D,USHAKOV A.Quantum Algorithm for the Discrete Logarithm Problem for Matrices Over Finite Group Rings[J].Group Complexity Cryptology,2014,6(1):31-36.

[5] SHPILRAIN V,USHAKOV A.The Conjugacy Search Problem in Public Key Cryptography:Unnecessary and Insufficient[J].Applicable Algebra in Engineering Communication&Computing,2006,17(3-4):285-289.

[6] SAKALAUSKAS E,TVARIJONAS P,RAULYNAITIS A.Key Agreement Protocol (KAP) Using Conjugacy and Discrete Logarithm Problems in Group Representation Level[J].Informatica,2007,18(1):115-124.

[7] HABEEB M,KAHROBAEI D,KOUPPARIS C,et al.Public Key Exchange Using Semidirect Product of(Simi)Groups[J].Cryptology and Information Security Series,2013:226-237.