自同構(gòu)群在公鑰密碼學(xué)中的應(yīng)用

潘 平

(陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西漢中 723000)

自同構(gòu)群在公鑰密碼學(xué)中的應(yīng)用

潘 平

(陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西漢中 723000)

綜述了近年來(lái)自同構(gòu)群在公鑰密碼學(xué)中的應(yīng)用及其最新進(jìn)展。MOR密碼系統(tǒng)是ElGamal密碼系統(tǒng)在非交換群上的推廣，更具有一般性。以幾類經(jīng)典的非交換群(如單位三角矩陣群、特殊線性群、冪零群、有限p群等)為主線，介紹了MOR密碼系統(tǒng)在這些非交換群的自同構(gòu)群下的研究成果及自同構(gòu)群的一個(gè)應(yīng)用:密鑰交換協(xié)議。為了實(shí)現(xiàn)安全、高效的MOR密碼系統(tǒng)，最后給出了仍需深入研究的一些問(wèn)題。

公鑰密碼學(xué); 非交換群; 自同構(gòu)群; MOR密碼系統(tǒng)

目前，大多數(shù)公鑰密碼系統(tǒng)的安全性依賴于交換群上的密碼難題。其中最著名的公鑰密碼系統(tǒng)是ElGamal密碼系統(tǒng)［1］及其變種，如橢圓曲線密碼系統(tǒng)［2］(ECC)，其安全性依賴于有限域上的離散對(duì)數(shù)問(wèn)題。這些公鑰密碼系統(tǒng)的數(shù)學(xué)基礎(chǔ)平臺(tái)分別為有限域上的乘法交換子群及橢圓曲線上有理點(diǎn)的加法交換群。然而，從理論上看，量子計(jì)算已經(jīng)使得基于交換群上的密碼難題破解。1994年，Shor提出了求解大整數(shù)分解問(wèn)題和有限域上離散對(duì)數(shù)問(wèn)題的高效量子算法。2003年，Proos和Zalka給出了求解橢圓曲線上離散對(duì)數(shù)問(wèn)題的高效量子算法。而這些公鑰密碼系統(tǒng)在量子計(jì)算下不安全了。因此人們很自然地將這些公鑰密碼系統(tǒng)推廣到非交換群上，這是一項(xiàng)很有意義的研究。

2001年，Paeng等［3］在亞密會(huì)議上給出了一個(gè)基于非交換群的內(nèi)自同構(gòu)群上的離散對(duì)數(shù)問(wèn)題假設(shè)下的公鑰加密系統(tǒng)，即MOR密碼系統(tǒng)。也就是說(shuō)，MOR密碼系統(tǒng)是ElGamal密碼系統(tǒng)在非交換群上的一般推廣，更具有一般性。此后，人們不斷地為實(shí)現(xiàn)安全、高效的MOR密碼系統(tǒng)尋求適當(dāng)?shù)姆墙粨Q代數(shù)結(jié)構(gòu)，從而對(duì)自同構(gòu)群的密碼應(yīng)用研究(如數(shù)字簽名、密鑰交換協(xié)議、哈希函數(shù)等)開始引起了學(xué)者的普遍關(guān)注［4-12］，隨后也出現(xiàn)了對(duì)MOR密碼系統(tǒng)安全性的攻擊［13-16］。迄今為止，人們主要在單位三角矩陣群、特殊線性群、冪零群、有限p群等非交換群上研究其自同構(gòu)群的密碼學(xué)特性，并獲得了安全的MOR密碼系統(tǒng)及密鑰交換協(xié)議。2008年至今，Mahalanobis一直致力于MOR密碼系統(tǒng)的研究。他認(rèn)為MOR密碼系統(tǒng)是密碼學(xué)中的一塊金礦，并存在實(shí)現(xiàn)MOR密碼系統(tǒng)安全的非交換群的自同構(gòu)群。本文以單位三角矩陣群、特殊線性群、冪零群、有限p群等非交換群為主線，總結(jié)了近年來(lái)這些非交換群的自同構(gòu)群在公鑰加密系統(tǒng)(即MOR密碼系統(tǒng))及密鑰交換協(xié)議中的應(yīng)用及最新進(jìn)展。

1 公鑰密碼系統(tǒng)

1.1 MOR 密碼系統(tǒng)

MOR密碼系統(tǒng)是ElGamal密碼系統(tǒng)在非交換群上的一般推廣，其方案描述如下［3］:

令G={g1，g2，…，gt}是一個(gè)有限群，其中t∈N，φ是一個(gè)非平凡的自同構(gòu)。Alice的密鑰如下:

私鑰:m∈N;

公鑰:φ(gi)和 φm(gi)，i=1，…，t。

加密算法:Bob 隨機(jī)選擇 r∈N，對(duì)消息 a∈G，Bob 計(jì)算 φr和 φmr。則密文為(φr(gi)，φmr(a))，i=1，…，t。

解密算法:Alice知道私鑰 m，收到密文(φr，φmr(a))后，先由 φr計(jì)算 φmr，然后計(jì)算 φ-mr，最后從φmr(a)中恢復(fù)出消息a。

Alice知道 φ的階，她可以通過(guò) φk-1=φ-1，其中 φk=1，計(jì)算 φ-mr。

MOR密碼系統(tǒng)的實(shí)現(xiàn)依賴于其所在的非交換群及其自同構(gòu)。下面根據(jù)非交換群的不同實(shí)例化，將近年來(lái)的研究進(jìn)展列表如表1。

表1 MOR密碼系統(tǒng)的實(shí)現(xiàn)

1.2 自同構(gòu)群及其密碼難題

群的自同構(gòu)分為內(nèi)自同構(gòu)和外自同構(gòu)。其中外自同構(gòu)有對(duì)角自同構(gòu)、中心自同構(gòu)、圖自同構(gòu)等。

定義1(內(nèi)自同構(gòu))［5］設(shè)G是非交換群，g∈G，對(duì)任意的x∈G，Inn(g)(x)=gxg-1，稱Inn(g)是G的自同構(gòu)。

定義2(對(duì)角自同構(gòu))［5］設(shè)G是一個(gè)群，g∈G，對(duì)任意的對(duì)角矩陣x，有φ(x)=gxg-1。這里，對(duì)角矩陣定義為主對(duì)角元素非零，而其余均為零的矩陣。

定義3(中心自同構(gòu))［5］設(shè)G是一個(gè)群，如果對(duì)任意的g∈G，有φ(g)=gzg，其中zg∈Z(G)，那么φ稱為中心自同構(gòu)。

定義5(置換自同構(gòu))［6］設(shè)G是一個(gè)群，如果對(duì)任意的A∈G，有φ(A)=P-1AP，則φ稱為置換自同構(gòu)。

定義6(自同構(gòu)群，Automorphism Group)［5］群G的全體自同構(gòu)組成的集合對(duì)映射的乘法構(gòu)成的一個(gè)群，稱為G的自同構(gòu)群。

定義7(離散對(duì)數(shù)問(wèn)題)［3］設(shè)g是群G中的一個(gè)元素。那么群G上的離散對(duì)數(shù)問(wèn)題是:給定g和ga，找一個(gè)元素 a∈N。

2 基于自同構(gòu)群的公鑰密碼系統(tǒng)

下面按照不同非交換群的自同構(gòu)群來(lái)闡述近年來(lái)重要的工作。

2.1 特殊線性群的內(nèi)自同構(gòu)群

2001年，Paeng等［3］首次提出了MOR密碼系統(tǒng)，該密碼系統(tǒng)建立在矩陣群和循環(huán)群所構(gòu)成的一個(gè)半直積群，即SL(2，Zp)×Zp，所用的自同構(gòu)是內(nèi)自同構(gòu)。為了提高方案的效率，Paeng等用SL(2，Zp)×{0}代替SL(2，Zp)×Zp，隨后，又將MOR密碼系統(tǒng)建立于新的半直積群GL(2，R)×Zn，其中R是環(huán)。但是基于上述非交換群上的MOR密碼系統(tǒng)遭受了各種攻擊，如唯密文攻擊、已知明文攻擊等。2003年，Paeng［4］表明:SL(2，Zp)×Zp的內(nèi)自同構(gòu)群上的離散對(duì)數(shù)問(wèn)題等同于SL(2，Zp)上的離散對(duì)數(shù)問(wèn)題，即存在一個(gè)亞指數(shù)時(shí)間算法能夠求解此非交換群的內(nèi)自同構(gòu)群上的離散對(duì)數(shù)問(wèn)題。

2.2 單位三角矩陣群的自同構(gòu)群

2008年，Mahalanobis［5］用單位三角矩陣群UT(d，q)于MOR密碼系統(tǒng)，如果使用對(duì)角自同構(gòu)，那么在該群上的密碼系統(tǒng)的安全性等同于有限域上的ElGamal密碼系統(tǒng)。為了能獲取更好的安全性，可以采用幾種自同構(gòu)的合成，即中心自同構(gòu)、內(nèi)自同構(gòu)與對(duì)角自同構(gòu)的合成，但是這樣涉及較多的矩陣運(yùn)算(矩陣乘積)的實(shí)現(xiàn)，致使解密較慢。2013年，Mahalanobis［7］研究了有限域上的單位三角矩陣群的自同構(gòu)群的生成元問(wèn)題。這對(duì)進(jìn)一步研究此群上的MOR密碼系統(tǒng)的安全性和計(jì)算復(fù)雜性提供了很好的理論依據(jù)。

2.3 幺模矩陣群的自同構(gòu)群

2012年，Mahalanobis［6］基于有限域的特殊線性群，即幺模矩陣群SL(d，q)，即有限域Fq上的d階特殊線性群，研究了MOR密碼系統(tǒng)，其中自同構(gòu)是對(duì)角自同構(gòu)和置換自同構(gòu)的合成。要攻破此群上的MOR密碼系統(tǒng)，就必須能夠求解有限擴(kuò)張域Fqd上的離散對(duì)數(shù)問(wèn)題。應(yīng)用指數(shù)算法計(jì)算Fqd上的離散

2.4 有限p群的自同構(gòu)群

2011年，Mahalanobis［8］研究了指數(shù)為p(p為素?cái)?shù))，階為p3的超特殊p群上的MOR密碼系統(tǒng)。2013年，Mahalanobis［9］分析了有限p群上MOR密碼系統(tǒng)的安全性，其安全性依賴于有限p群的自同構(gòu)群上的離散對(duì)數(shù)問(wèn)題。Mahalanobis將自同構(gòu)分為兩類:p自同構(gòu)和p'自同構(gòu)。對(duì)p'自同構(gòu)而言，MOR密碼系統(tǒng)在p群上是安全的。但MOR密碼系統(tǒng)在p自同構(gòu)作用下是否安全仍一個(gè)開放性問(wèn)題。

2.5 冪零群的自同構(gòu)群

2008年，Mahalanobis［10］給出了非交換冪零群的自同構(gòu)群的交換子群上的密鑰交換協(xié)議，其中所用自同構(gòu)是中心自同構(gòu)。該協(xié)議可以說(shuō)是Diffie-Hellman密鑰交換協(xié)議在非交換群上的一般推廣。這表明了除辮群外，在其他非交換群，如冪零群，甚至有限p群上也可以用來(lái)在不安全信道上有效地傳輸密鑰或分享密碼。

3總結(jié)

本文分析了幾類非交換群(如單位三角矩陣群、特殊線性群、冪零群、有限p群等)的自同構(gòu)群上的MOR密碼系統(tǒng)及密鑰交換協(xié)議的研究現(xiàn)狀和最新進(jìn)展。密碼學(xué)首要解決的問(wèn)題是實(shí)用性，因此必須選擇適當(dāng)?shù)姆墙粨Q群的自同構(gòu)群，使得有效地實(shí)現(xiàn)MOR密碼系統(tǒng)，并且能保證MOR密碼系統(tǒng)安全。

另外，基于幾類非交換群的自同構(gòu)群的密碼方案中的一些關(guān)鍵問(wèn)題(如生成元的生成問(wèn)題，運(yùn)算效率及實(shí)現(xiàn)細(xì)節(jié)等)還沒有完全得到解決。當(dāng)然，上述問(wèn)題的解決也有助于將MOR密碼系統(tǒng)的研究拓展到其他密碼原語(yǔ)(如密鑰交換協(xié)議、哈希函數(shù)、簽名、秘密分享等)，這既有重要的理論意義，也有實(shí)際的應(yīng)用價(jià)值。

最后，目前還沒有可證明安全性的基于幾類非交換群的自同構(gòu)群的密碼方案。MOR密碼系統(tǒng)是ElGamal密碼系統(tǒng)的一般化推廣，顯然，MOR密碼系統(tǒng)在選擇密文攻擊下沒有達(dá)到不可區(qū)分性安全。但是，不妨嘗試借鑒Cramer-Shoup公鑰密碼方案的思路，使得MOR密碼系統(tǒng)在選擇密文攻擊下達(dá)到不可區(qū)分性安全。

［1］ELGAMAL T.A public key cryptosystem and a signature scheme based on discrete logarithms［J］.IEEE Trans.on Info.Theory，1985，31(4):469-472.

［2］MILLER V S.Use of elliptic curves in cryptography［M］.New York:Springer-Verlag，1986:417-426.

［3］PAENG S H，HA K C，KIM J H，et al.New Public key cryptosystem using finite non-abelian groups［M］.Heidelberg:Springer-Verlag，2001:470-485.

［4］PAENG S H.On the security of cryptosystem using the automorphism groups［J］.Information Processing Letters，2003(88):293-298.

［5］MAHALANOBIS A.A simple generalization of the ElGamal cryptosystem to non-abelian groups［J］.Communications in Algebra，2008，36(10):3880-3891.

［6］MAHALANOBIS A.A simple generalization of the ElGamal cryptosystem to non-abelian groups II［J］.Communications in Algebra，2012，40(8):3583-3596.

［7］MAHALANOBIS A.The automorphism group of the group of unitriangular matrices over a field［J］.International Journal of Algebra，2013，7(15):723-733.

［8］MAHALANOBIS A.The MOR cryptosystem and extra-special p-groups［EB/OL］.(2011-11-04)［2014-03-10］.http://arxiv.org/abs/1111.1043.

［9］MAHALANOBIS A.The MOR cryptosystem and finite p-groups［EB/OL］.(2013-09-07) ［2014-03-10］.http://arxiv.org/abs/1309.1859.

［10］MAHALANOBIS A.The Diffie-Hellman key exchange protocol non-abelian nilpotent group［J］.Israel Journal of Mathematics，2008(165):161-187.

［11］PAN Ping，WANG Li-cheng，WANG Li-hua，et al.Chameleon Hash Functions and One-Time Signature Schemes from Inner Automorphism Groups［J］.Fundamenta Informaticae，2013，126(1):103-119.

［12］PAN Ping，WANG Li-cheng，XU Cheng-qian，et al.Blind Signature Scheme from non-commutative group［J］.International Journal of Digital Content Technology and its Applications，2012，6(19):538-545.

［13］TOBIAS C.Security Analysis of the MOR Cryptosystem［M］.Heidelberg:Springer-Verlag，2003:175-186.

［14］TOBIAS C.Security analysis of MOR［M］.Heidelberg:Springer-Verlag，2003:175-186.

［15］KORSTEN A.Cryptanalysis of MOR and Discrete Logarithms in Inner Automorphism Groups［M］.Heidelberg:Springer-Verlag，2008:78-89.

［16］LEE I S，KIM W H，KWON D，et al.On the security of MOR public key cryptosystem［M］.Heidelberg:Springer-Verlag，2004:387-400.

［責(zé)任編輯:謝 平］

Applications of automorphism group in public-key cryptography

PAN Ping
(School of Mathematics and Computer Science，Shaanxi University of Technology，Hanzhong 723000，China)

This paper surveys the applications and new developments of automorphism groups in the public-key cryptography later years.MOR cryptosystem is a simple generalization of the ElGamal cryptosystem to non-commutative group.Through several kinds of non-commutative groups(such as unitriangular matrix group，special linear group，nilpotent group and finite p-group etc.)，MOR cryptosystem and the key exchange protocol based on automorphism groups of non-commutative groups are described.Finally，some future problems concerning secur and efficient MOR cryptosystem are put forward.

public-key cryptography; non-commutative group; automorphism groups; MOR cryptosystem

TP309.7

A

1673-2944(2014)05-0025-04

2014-03-27

陜西省教育廳科學(xué)研究計(jì)劃項(xiàng)目(2013JK059);陜西理工學(xué)院博士科研基金資助項(xiàng)目(SLGQD13-24)

潘平(1975—)，女，甘肅省天水市人，陜西理工學(xué)院講師，博士，主要研究方向?yàn)樾畔踩?、密碼學(xué)。