一種基于辮群的密鑰交換協議

2022-09-06 03:45:56權雙燕

喀什大學學報 2022年3期

權雙燕，張靜

（1.陜西理工大學數學與計算機科學學院,陜西漢中 723000;2.東莞職業技術學院現代工程創新實踐中心,廣東東莞 523808）

0 引言

1993 年，Sidelnikov 等人提出在無限非交換群和半群上建立公鑰密碼系統的思想[1]，其主要解決如何應用困難問題隱藏因子.如，文獻[2]提出了無限非交換群上基于分解問題的密鑰交換協議;1947年，Artin提出了辮群的概念，它也是一種無限非交換群，其結構復雜，辮群的乘法和求逆等運算所需要時間和空間都很小.而且辮群上有許多難解的數學問題，如共軛搜索問題、分解問題、馬爾科夫問題、根問題等.基于解決這些問題，2000 年Ko等人提出了辮群上基于共軛搜索問題的一種新的密碼系統[3]，此后辮群引起了密碼學家的關注并被廣泛采用.隨著量子算法和改進的分解算法的發展，只應用一個困難問題已經不能保證密碼系統的安全性，為了提高安全性，同時使用幾個困難問題成為一個流行的方法.2007 年Eligijus S 等人同時使用共軛搜索問題和離散對數問題在群上構建了一種密碼協議，并闡明了同時使用兩個困難問題足夠保證密碼交換協議的安全性[4].2013 年，Maggie Habeeb 等人第一次將群的半直積用到密碼系統中，并提出了一種基于半直積運算的密碼交換協議[5].

本文通過半直積的運算法則，在辮群上構建了基于離散對數問題和分解問題的密鑰交換協議.因為目前在辮群上沒有求解離散對數問題和分解問題的有效量子算法，并且同時在密鑰協議中設置兩個困難問題可大大提高密鑰的安全性，所以本文的密碼交換協議具有抗量子攻擊性.為證明協議的安全性，本文通過代數攻擊和窮盡搜索攻擊分析，闡明了該密碼協議的抗攻擊性.同時，在理論上分析了該密碼交換協議的時間復雜度和空間復雜度，數據顯示本文的密碼交換協議具有可行性.

1 準備知識

定義1 (半直積)(G,?)和(G′,°)是兩個半群,Aut(G)是G的自同構群，其二元運算是合成運算.ρ:G′→Aut(G)是一個自同構.G和G′的半直積是一個元素對集合

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

事實上，(Γ?)是一個群，也是直積的擴群.如果(G,?)和(G′,°)是無限群，那么(Γ?)就是一個無限的非交換群.如果G′=Aut(G)，ρ=idG，那么

其中，?°?′表示自同構的合成，并且先執行運算?′.

Bij(G?)表示G→G上所有雙射構成的集合.在本文的密鑰交換協議中，只需要映射?是雙射，即?∈Bij(G).在集合

其中?°?′表示雙射的合成運算，并定義(g,?)m=(g,?)m-1(g,?)(m∈Z+).如果G是一個群，對于?a,b∈G，讓?=?b(a)=b-1a，顯然?b(a)是一個雙射，并且.那么有

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

是g的中心化子.

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

其中，整數被稱為辮指數，的元素被稱為-辮.

辮群有不同的群表示，如Burau 表示、Garsides表示、Birman-Ko-Lee 表示.本文中的密鑰交換協議用辮群的Elrifai-Morton 表示，每一個辮都有唯一的左標準型.

定理1[6]任意辮W∈，左標準型是唯一的，可表示為

因此，一個辮W=Δu A1A2…Ap能用一個多元組(u,π1,π2,…,πp)描述，置換辮Ai對應于置換πi，p被稱為W的標準長度，用len(W)表示.在文獻[6]中，對于用Artin 生成元生成的辮，作者提出了將辮化簡為左標準型的算法.

2 密鑰交換協議

該密鑰交換協議基于辮群，所有的辮用左標準型表示，通過文獻[6]中詞的算法，一個辮可以表示成左標準型.對映射

Alice和Bob選擇不同的參數b作為私鑰，對辮群和辮g∈達成一致.密鑰交換協議為公鑰g.

Alice計算積

讓B=h-(n-1)gn，B′=h-1B=h-ngn發送B′給Alice.

步驟3：Alice 計算.

3 安全性分析

本文的密鑰交換協議的安全性依賴于辮群上的兩個困難問題：分解問題和離散對數問題.A′和B′通過公共信道被發送，攻擊者可以觀察

尋找k-m，h-n，gm，gn等價于尋找k-m，h-n，gm-1，gn-1，所以通過三元組(g，A′)，B′ 尋找k-m，h-n，gm，gn是辮群上的分解問題，計算m和n，攻擊者也必須解辮群上的離散對數問題.如果攻擊者能從A′中算出k-m和gm，那么共享密鑰K=k-mB′gm就能被得到.類似的，如果他能從B′中算出h-n和gn，那么共享密鑰也能被得到.這里，僅考慮以上兩種情況中的第一種.