自同构群在公钥密码学中的应用

潘 平

(陕西理工学院数学与计算机科学学院，陕西汉中 723000)

自同构群在公钥密码学中的应用

潘 平

(陕西理工学院数学与计算机科学学院，陕西汉中 723000)

综述了近年来自同构群在公钥密码学中的应用及其最新进展。MOR密码系统是ElGamal密码系统在非交换群上的推广，更具有一般性。以几类经典的非交换群(如单位三角矩阵群、特殊线性群、幂零群、有限p群等)为主线，介绍了MOR密码系统在这些非交换群的自同构群下的研究成果及自同构群的一个应用:密钥交换协议。为了实现安全、高效的MOR密码系统，最后给出了仍需深入研究的一些问题。

公钥密码学; 非交换群; 自同构群; MOR密码系统

目前，大多数公钥密码系统的安全性依赖于交换群上的密码难题。其中最著名的公钥密码系统是ElGamal密码系统［1］及其变种，如椭圆曲线密码系统［2］(ECC)，其安全性依赖于有限域上的离散对数问题。这些公钥密码系统的数学基础平台分别为有限域上的乘法交换子群及椭圆曲线上有理点的加法交换群。然而，从理论上看，量子计算已经使得基于交换群上的密码难题破解。1994年，Shor提出了求解大整数分解问题和有限域上离散对数问题的高效量子算法。2003年，Proos和Zalka给出了求解椭圆曲线上离散对数问题的高效量子算法。而这些公钥密码系统在量子计算下不安全了。因此人们很自然地将这些公钥密码系统推广到非交换群上，这是一项很有意义的研究。

2001年，Paeng等［3］在亚密会议上给出了一个基于非交换群的内自同构群上的离散对数问题假设下的公钥加密系统，即MOR密码系统。也就是说，MOR密码系统是ElGamal密码系统在非交换群上的一般推广，更具有一般性。此后，人们不断地为实现安全、高效的MOR密码系统寻求适当的非交换代数结构，从而对自同构群的密码应用研究(如数字签名、密钥交换协议、哈希函数等)开始引起了学者的普遍关注［4-12］，随后也出现了对MOR密码系统安全性的攻击［13-16］。迄今为止，人们主要在单位三角矩阵群、特殊线性群、幂零群、有限p群等非交换群上研究其自同构群的密码学特性，并获得了安全的MOR密码系统及密钥交换协议。2008年至今，Mahalanobis一直致力于MOR密码系统的研究。他认为MOR密码系统是密码学中的一块金矿，并存在实现MOR密码系统安全的非交换群的自同构群。本文以单位三角矩阵群、特殊线性群、幂零群、有限p群等非交换群为主线，总结了近年来这些非交换群的自同构群在公钥加密系统(即MOR密码系统)及密钥交换协议中的应用及最新进展。

1 公钥密码系统

1.1 MOR 密码系统

MOR密码系统是ElGamal密码系统在非交换群上的一般推广，其方案描述如下［3］:

令G={g1，g2，…，gt}是一个有限群，其中t∈N，φ是一个非平凡的自同构。Alice的密钥如下:

私钥:m∈N;

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

加密算法:Bob 随机选择 r∈N，对消息 a∈G，Bob 计算 φr和 φmr。则密文为(φr(gi)，φmr(a))，i=1，…，t。

解密算法:Alice知道私钥 m，收到密文(φr，φmr(a))后，先由 φr计算 φmr，然后计算 φ-mr，最后从φmr(a)中恢复出消息a。

Alice知道 φ的阶，她可以通过 φk-1=φ-1，其中 φk=1，计算 φ-mr。

MOR密码系统的实现依赖于其所在的非交换群及其自同构。下面根据非交换群的不同实例化，将近年来的研究进展列表如表1。

表1 MOR密码系统的实现

1.2 自同构群及其密码难题

群的自同构分为内自同构和外自同构。其中外自同构有对角自同构、中心自同构、图自同构等。

定义1(内自同构)［5］设G是非交换群，g∈G，对任意的x∈G，Inn(g)(x)=gxg-1，称Inn(g)是G的自同构。

定义2(对角自同构)［5］设G是一个群，g∈G，对任意的对角矩阵x，有φ(x)=gxg-1。这里，对角矩阵定义为主对角元素非零，而其余均为零的矩阵。

定义3(中心自同构)［5］设G是一个群，如果对任意的g∈G，有φ(g)=gzg，其中zg∈Z(G)，那么φ称为中心自同构。

定义5(置换自同构)［6］设G是一个群，如果对任意的A∈G，有φ(A)=P-1AP，则φ称为置换自同构。

定义6(自同构群，Automorphism Group)［5］群G的全体自同构组成的集合对映射的乘法构成的一个群，称为G的自同构群。

定义7(离散对数问题)［3］设g是群G中的一个元素。那么群G上的离散对数问题是:给定g和ga，找一个元素 a∈N。

2 基于自同构群的公钥密码系统

下面按照不同非交换群的自同构群来阐述近年来重要的工作。

2.1 特殊线性群的内自同构群

2001年，Paeng等［3］首次提出了MOR密码系统，该密码系统建立在矩阵群和循环群所构成的一个半直积群，即SL(2，Zp)×Zp，所用的自同构是内自同构。为了提高方案的效率，Paeng等用SL(2，Zp)×{0}代替SL(2，Zp)×Zp，随后，又将MOR密码系统建立于新的半直积群GL(2，R)×Zn，其中R是环。但是基于上述非交换群上的MOR密码系统遭受了各种攻击，如唯密文攻击、已知明文攻击等。2003年，Paeng［4］表明:SL(2，Zp)×Zp的内自同构群上的离散对数问题等同于SL(2，Zp)上的离散对数问题，即存在一个亚指数时间算法能够求解此非交换群的内自同构群上的离散对数问题。

2.2 单位三角矩阵群的自同构群

2008年，Mahalanobis［5］用单位三角矩阵群UT(d，q)于MOR密码系统，如果使用对角自同构，那么在该群上的密码系统的安全性等同于有限域上的ElGamal密码系统。为了能获取更好的安全性，可以采用几种自同构的合成，即中心自同构、内自同构与对角自同构的合成，但是这样涉及较多的矩阵运算(矩阵乘积)的实现，致使解密较慢。2013年，Mahalanobis［7］研究了有限域上的单位三角矩阵群的自同构群的生成元问题。这对进一步研究此群上的MOR密码系统的安全性和计算复杂性提供了很好的理论依据。

2.3 幺模矩阵群的自同构群

2012年，Mahalanobis［6］基于有限域的特殊线性群，即幺模矩阵群SL(d，q)，即有限域Fq上的d阶特殊线性群，研究了MOR密码系统，其中自同构是对角自同构和置换自同构的合成。要攻破此群上的MOR密码系统，就必须能够求解有限扩张域Fqd上的离散对数问题。应用指数算法计算Fqd上的离散

2.4 有限p群的自同构群

2011年，Mahalanobis［8］研究了指数为p(p为素数)，阶为p3的超特殊p群上的MOR密码系统。2013年，Mahalanobis［9］分析了有限p群上MOR密码系统的安全性，其安全性依赖于有限p群的自同构群上的离散对数问题。Mahalanobis将自同构分为两类:p自同构和p'自同构。对p'自同构而言，MOR密码系统在p群上是安全的。但MOR密码系统在p自同构作用下是否安全仍一个开放性问题。

2.5 幂零群的自同构群

2008年，Mahalanobis［10］给出了非交换幂零群的自同构群的交换子群上的密钥交换协议，其中所用自同构是中心自同构。该协议可以说是Diffie-Hellman密钥交换协议在非交换群上的一般推广。这表明了除辫群外，在其他非交换群，如幂零群，甚至有限p群上也可以用来在不安全信道上有效地传输密钥或分享密码。

3总结

本文分析了几类非交换群(如单位三角矩阵群、特殊线性群、幂零群、有限p群等)的自同构群上的MOR密码系统及密钥交换协议的研究现状和最新进展。密码学首要解决的问题是实用性，因此必须选择适当的非交换群的自同构群，使得有效地实现MOR密码系统，并且能保证MOR密码系统安全。

另外，基于几类非交换群的自同构群的密码方案中的一些关键问题(如生成元的生成问题，运算效率及实现细节等)还没有完全得到解决。当然，上述问题的解决也有助于将MOR密码系统的研究拓展到其他密码原语(如密钥交换协议、哈希函数、签名、秘密分享等)，这既有重要的理论意义，也有实际的应用价值。

最后，目前还没有可证明安全性的基于几类非交换群的自同构群的密码方案。MOR密码系统是ElGamal密码系统的一般化推广，显然，MOR密码系统在选择密文攻击下没有达到不可区分性安全。但是，不妨尝试借鉴Cramer-Shoup公钥密码方案的思路，使得MOR密码系统在选择密文攻击下达到不可区分性安全。

［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.

［责任编辑:谢 平］

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

陕西省教育厅科学研究计划项目(2013JK059);陕西理工学院博士科研基金资助项目(SLGQD13-24)

潘平(1975—)，女，甘肃省天水市人，陕西理工学院讲师，博士，主要研究方向为信息安全、密码学。