一種基于辮群的密鑰交換協(xié)議

權(quán)雙燕，張 靜

（1.陜西理工大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,陜西 漢中 723000;2.東莞職業(yè)技術(shù)學(xué)院現(xiàn)代工程創(chuàng)新實(shí)踐中心,廣東 東莞 523808）

0 引言

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

本文通過半直積的運(yùn)算法則，在辮群上構(gòu)建了基于離散對(duì)數(shù)問題和分解問題的密鑰交換協(xié)議.因?yàn)槟壳霸谵p群上沒有求解離散對(duì)數(shù)問題和分解問題的有效量子算法，并且同時(shí)在密鑰協(xié)議中設(shè)置兩個(gè)困難問題可大大提高密鑰的安全性，所以本文的密碼交換協(xié)議具有抗量子攻擊性.為證明協(xié)議的安全性，本文通過代數(shù)攻擊和窮盡搜索攻擊分析，闡明了該密碼協(xié)議的抗攻擊性.同時(shí)，在理論上分析了該密碼交換協(xié)議的時(shí)間復(fù)雜度和空間復(fù)雜度，數(shù)據(jù)顯示本文的密碼交換協(xié)議具有可行性.

1 準(zhǔn)備知識(shí)

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

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

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

其中，?°?′表示自同構(gòu)的合成，并且先執(zhí)行運(yùn)算?′.

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

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

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

是g的中心化子.

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

其中，整數(shù)被稱為辮指數(shù)，的元素被稱為-辮.

辮群有不同的群表示，如Burau 表示、Garsides表示、Birman-Ko-Lee 表示.本文中的密鑰交換協(xié)議用辮群的Elrifai-Morton 表示，每一個(gè)辮都有唯一的左標(biāo)準(zhǔn)型.

定理1[6]任意辮W∈，左標(biāo)準(zhǔn)型是唯一的，可表示為

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

2 密鑰交換協(xié)議

該密鑰交換協(xié)議基于辮群，所有的辮用左標(biāo)準(zhǔn)型表示，通過文獻(xiàn)[6]中詞的算法，一個(gè)辮可以表示成左標(biāo)準(zhǔn)型.對(duì)映射

Alice和Bob選擇不同的參數(shù)b作為私鑰，對(duì)辮群和辮g∈達(dá)成一致.密鑰交換協(xié)議為公鑰g.

Alice計(jì)算積

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

步驟3：Alice 計(jì)算.

3 安全性分析

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

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

3.1 代數(shù)攻擊

由于k和m未知，k-m，gm不能被直接計(jì)算得到，但是攻擊者可以選擇任意一個(gè)元素，讓代替k-m，那么有

從上式中計(jì)算私鑰m是一個(gè)離散對(duì)數(shù)問題，因此沒有多項(xiàng)式時(shí)間算法可以找到m.這樣，讓A′-1代替gm，得到

對(duì)于h和n攻擊，代數(shù)攻擊結(jié)果是一樣的.通過代數(shù)攻擊，攻擊者無法得到共享密鑰，因此本文的密鑰交換協(xié)議對(duì)于代數(shù)攻擊是安全的.

3.2 窮盡搜索攻擊

4 復(fù)雜度分析

依據(jù)辮的左標(biāo)準(zhǔn)型，在計(jì)算復(fù)雜度時(shí)，需要考慮兩個(gè)參數(shù)：辮指數(shù)和標(biāo)準(zhǔn)長(zhǎng)度.為了計(jì)算方便，我們假設(shè)在本文的密鑰交換協(xié)議中的辮指數(shù)是，標(biāo)準(zhǔn)長(zhǎng)度是p.

4.1 時(shí)間復(fù)雜度分析

表1 Alice的時(shí)間復(fù)雜度

與Alice類似，Bob的時(shí)間復(fù)雜度見表2.

表2 Bob的時(shí)間復(fù)雜度

4.2 空間復(fù)雜度分析

對(duì)于Alice，在最糟糕的情況下空間復(fù)雜度見表3.

表3 Alice的空間復(fù)雜度

對(duì)于Bob，在最糟糕的情況下空間復(fù)雜度見表4.綜上，對(duì)于 Alice，空間復(fù)雜度小于對(duì)于Bob，空間復(fù)雜度小于

表4 Bob的空間復(fù)雜度