李紹華，尚緒鳳

(中國計量學(xué)院理學(xué)院，浙江杭州 310018)

基于非交換代數(shù)結(jié)構(gòu)的公鑰密碼體制

李紹華，尚緒鳳

(中國計量學(xué)院理學(xué)院，浙江杭州 310018)

提出了一個新的基于非交換代數(shù)結(jié)構(gòu)的Diffie－Hellman密鑰交換協(xié)議，并在此基礎(chǔ)上建立了一個新的公鑰密碼體制.它的安全性取決于一個基本問題的困難性，而這個基本問題是共軛搜索問題和Diffie－Hellman問題的結(jié)合變形問題.最后將提出的體制應(yīng)用到數(shù)字簽名方案中，并給出一個類似于ElGamal的簽名方案.

非交換代數(shù)結(jié)構(gòu);Diffie－Hellman密鑰交換協(xié)議;扭共軛搜索問題;公鑰密碼體制

0 引言

隨著密碼技術(shù)的發(fā)展，非交換代數(shù)結(jié)構(gòu)已成為構(gòu)造密碼體制的一個趨勢，也引起了學(xué)者們的廣泛關(guān)注.許多優(yōu)秀的以非交換結(jié)構(gòu)為平臺的密碼體制相繼提出［1－2］，例如辮群就是一個很好也很重要的平臺.非交換結(jié)構(gòu)中常見的問題是共軛搜索問題和Diffie－Hellman問題.本文將提出一個基本問題，它是共軛搜索問題和Diffie－Hellman問題的結(jié)合問題，本文提出的方案就是基于該基本問題，并且適用于一般的非交換結(jié)構(gòu).文獻［1］也提出了一個類似的問題，但是是以辮群為指定的平臺進行討論的.

共軛搜索問題:已知x，y∈G，且x與y互為共軛的，找出a∈G，s.t:y=axa－1.共軛搜索問題還有一個推廣，即扭共軛搜索問題［3］:已知x，y∈G，φ，ψ∈End( G)，*為G上的反同態(tài)，找出a∈G，s.t:y=ψ(a) xφ( a*).這一問題比一般的共軛搜索問題更為不平凡，并且更適合于構(gòu)造復(fù)雜的密碼體制.再給出DH問題:已知g，gkA，gkB∈F，計算gkAkB.Diffie－Hellman問題也有一個推廣的問題，即:令φ，ψ∈Aut( G)，且φψ=ψφ，已知a，φ(a)，ψ(a)，求φ( ψ(a)).本文使用的基本問題:設(shè)G是非交換的代數(shù)結(jié)構(gòu)，已知x∈G且x?Z( G)，φ，ψ是G到Z( G)上的同態(tài)，*為G上的反同態(tài)，y1=ψ(a) xφ( a*)，y2=ψ(b) xφ( b*)，a，b∈G是隱藏的，計算ψ(a) y2φ( a*)或ψ(b) y1φ( b*).此問題可以看成共軛搜索問題和Diffie－Hellman問題的一個變形，它顯然比一般的共軛搜索問題和Diffie－Hellman問題更難解決.一般的共軛搜索問題存在所謂的“基于長度的攻擊”，一些試探性的算法已經(jīng)顯示出非常高的成功率［4－7］.而考慮我們所提出的基本問題時，線性攻擊似乎是不可行的，見文獻［3］中的具體分析.

注:在非交換結(jié)構(gòu)中，ψ(a) y2φ( a*)不一定等于ψ(b) y1φ( b*)，而由于φ，ψ是G到Z( G)上的同態(tài)，故兩者是相等的.這是共軛問題應(yīng)用到Diffie－Hellman密鑰交換協(xié)議的關(guān)鍵問題，文獻［1］中是利用辮群的自身結(jié)構(gòu)來解決這一問題的，而本文通過同態(tài)的選取可將方案推廣到一般的非交換結(jié)構(gòu)中.

1 提出的方案

1.1 非交換群上的Diffie－Hellman密鑰交換協(xié)議

假設(shè)Alice想與Bob達(dá)成一個會話密鑰，G是非交換群，公開信息為x∈G－Z(G)，φ，ψ:G→Z( G)，G上的反同態(tài)*，協(xié)議如下

(1)Alice選取隨機元a∈G，計算y1=ψ(a) xφ( a*)，并將y1發(fā)給Bob;

(2)Bob選取隨機元b∈G，計算y2=ψ(b) xφ( b*)，并將y2發(fā)給Alice;

(3)Alice和Bob分別計算KA=ψ(a) y2φ( a*)和KB=ψ(b) y1φ( b*).

由于

故達(dá)成的會話密鑰為K=KA=KB.

1.2 非交換群上的公鑰密碼體制

利用上面的協(xié)議，建立一個新的公鑰密碼體制.令G為非交換群，H:G→{0，1}k是一個適當(dāng)選取的雜湊函數(shù).

(1)密鑰生成系統(tǒng)選擇x∈G－Z( G)，兩同態(tài)φ，ψ:G→Z( G)，和G上的一個反同態(tài)*.A選擇隨機元a∈G，計算y= ψ(a) xφ( a*)，則A的公鑰為(x，y)，私鑰為a.

(2)加密給定消息m∈{0，1}k，假設(shè)B要將m發(fā)給A，則B選擇隨機元b∈G，利用A的公鑰計算c=ψ(b) xφ( b*)，d= H( ψ(b) yφ( b*))⊕m，密文為(c，d).

(3)解密A收到密文(c，d)，利用私鑰解密得m=H( ψ(a) cφ( a*))⊕d.

以上體制是正確的，因為

2 應(yīng)用

上一節(jié)提出的公鑰密碼體制可以用于構(gòu)造各種數(shù)字簽名方案.下面給出一個類似于ElGamal的簽名方案.

設(shè)G為非交換群，x∈G－Z( G)，兩同態(tài)φ，ψ:G→Z( G)，反同態(tài)設(shè)為元素的逆運算.假設(shè)用戶要為消息m簽名.

(1)選擇隨機元a∈G，計算y=ψ(a) xφ( a*);

(2)選擇隨機元k∈G，計算r=ψ( k－1)xφ(k)，z=ψ( r－1)yφ(r);

(3)計算δ，s.t:m=δk(ar)－1.

最后得到的簽名為(m，z，δk).這里a可以看做簽名人的私鑰，公鑰為y，保密信息為(a，k，r，δ).

接收者收到簽名后，計算L=ψ(m) xφ( m－1)，R=ψ( δk) zφ((δk)－1)，當(dāng)且僅當(dāng)L=R時接受簽名.

此簽名方案是正確的，因為

3 結(jié)束語

本文將一般的共軛搜索問題與Diffie－Hellman問題相結(jié)合提出了一個基本問題，這個問題的困難性不低于共軛搜索問題和Diffie－Hellman問題.在此基礎(chǔ)上提出了新的Diffie－Hellman密鑰交換協(xié)議和新的公鑰密碼體制，并且提出了一個數(shù)字簽名方案.我們的體制比一般的基于共軛搜索問題或Diffie－Hellman問題的方案更有優(yōu)勢.一方面是提出的基本問題能更好地抵抗線性攻擊，另一方面我們的方案對一般的非交換結(jié)構(gòu)都是適用的，更具有普遍性.

［1］KO K H，LEE S J，CHEON J H.New public key cryptosystem using braid groups［J］.Lecture Notes in Computer Science，2000，30(1880): 166－183.

［2］PAENG S H，HA K C，KIM J H，et al.New public key cryptosystem using finite non Abelian groups［J］.Lecture Notes in Computer Science，2001，31(2139):470－485.

［3］SHPILRAIN V，USHAKOV A.An authentication scheme based on the twisted conjugacy problem［J］.Lecture Notes in Computer Science，2008，38(5037):366－372.

［4］GARBER D，KAPLAN S，TEICHER M，et al.Probabilistic solutions of equations in the Braid group［J］.Advances in Applied Mathematics，2005，35(3):323－334.

［5］GARBER D，KAPLAN S，TEICHER M，et al.Length-based conjugacy search in the Braid group［J］.Contemp Math Amer Math Soc，2006，54 (418):75－87.

［6］MYASNIKOV A D，USHAKOV A.Length based attack in braid groups［J］.Lecture Notes in Computer Science，2007，37(4450):76－88.

［7］RUINSKIY D，SHAMIR A，TSABAN B.Cryptanalysis of group-based key agreement protocols using subgroup distance functions［J］.Lecture Notes in Computer Science，2007，37(4450):61－75.

NEW Public Key Cryptosystem Using Non-Abelian Algebra Structures

LI Shao-hua，SHANG Xu-feng

(Colleg of Science，China Jiliang University，Hangzhou 310018，China)

Propose a new Diffie-Hellman key exchange scheme based on non-Abelian algebra structures and also propose a new public key cryptosystem based on the proposed scheme.The security of this scheme relies on the difficulty of a base problem，which combines the conjugacy search problem with the Diffie-Hellman problem，and which is a transformation problem.At last，apply the proposed cryptosystem to a signature scheme which is similar to ElGamal scheme.

non-Abelian algebra structure;Diffie-Hellman key exchange scheme;twisted conjugacy search problem;public key cryptosystem

TP309.7

A

1007－0834(2011)03－0035－02

10.3969/j.issn.1007－0834.2011.03.012

2011－05－23

國家自然科學(xué)基金資助項目(11071081);浙江省自然科學(xué)基金杰出青年團隊項目(R1090138)

李紹華(1986—)，男，黑龍江哈爾濱人，中國計量學(xué)院理學(xué)院.