基于多元二次拟群的公钥体制改进

邱忠升，王 蓉，蒋飘蓬

(海军航空工程学院训练部，山东烟台264001)

在公钥密码学的发展历程中，基于多元二次方程的公钥密码体制是公钥密码学领域中的热点。该密码体制利用有限域上的多元二次方程集合作为非对称密码系统的公钥［1－2］。其设计是基于一个NP－C问题，即求解一个有限域上的多元二次方程组是困难的。Gligoroski D等［3－4］提出利用拟群理论［5］构造多元二次方程组的方法，进而得出一种新的公钥体制:基于多元二次拟群的公钥算法(简称MQQ公钥算法)。MQQ公钥算法具有高度并行的优点，其在FPGA硬件上的并行实现速度可达同等条件下RSA公钥的10 000倍以上［6］。同时，MQQ公钥算法存在一个不可回避的缺陷，即密钥生成速度较慢，这是其生成多元二次拟群的算法低效造成的。

本文分析了MQQ公钥算法所依据的拟群变换理论及性质，提出了基于右拟群构造密钥的方法，大大提高了密钥的生成速度。通过程序模拟分析，得出了该改进算法的应用特点，并给出了在构造密钥过程中需遵循的设计原则，以防止弱密钥产生。

1 MQQ公钥算法中密钥构造的缺点分析

MQQ公钥算法［4］在创建密钥的过程中，将用到8个拟群运算*1，…，*8:

通过私钥解密的算法中使用此8个拟群的左除运算:

式中左除i(i=1，…，8)运算分别对应拟群*i(i=1，…，8)的左除。

多元二次拟群的构建到目前为止还没有高效的算法。文献［4］介绍了一种能构造出2d阶且属Quadd－kLinkk类型的多元二次拟群的流程MQQ(d，k)。该算法在巨大未定空间内随机搜索判断，其搜索成功的计算代价很高。事实上，当d=5，生成一个Quad5Link0类型的MQQ大约需要尝试216次［4］。构造8个随机构造的多元二次拟群的过程占用的时间太多，从而使得MQQ公钥算法中构造密钥的过程变得非常慢。相比其他公钥算法，在密钥生成速度方面MQQ公钥算法具有很大劣势。

2 应用右拟群改进MQQ公钥算法

2.1 右拟群的定义

定义1 如果(Q'，*)是一个集合Q'与一个二元运算* 的结合，若Q'中的任意元素a和b都存在唯一的Q中元素x，满足a*x=b，则这个群(Q'，*)被称为右拟群。

行和列中都没有重复元素的方阵被称为拉丁方阵，拟群可表示为拉丁方阵形式［5］。而右拟群如果表示为方阵形式，各行中都没有重复的元素，而列中会出现重复的元素。右拟群具有左除运算x=a，而没有右除运算，因为右除得不到唯一右除值。

只要保证式(1)中*ij是右拟群(而不必是拟群)，那么式(2)同样是有效的可逆变换，即MQQ公钥算法不需要严格的多元二次拟群，而只需多元二次右拟群。

2.2 多元二次右拟群的构造

定理1 设A1=［fij］d×d是一个d×d的各元素为线性布尔表达式的布尔矩阵，b1=［ui］d×1是各元素为线性或二次布尔表达式的布尔向量。其中，设fij和ui只依赖于参数x1，x2，…，xd。

如果在GF(2)中

那么向量乘操作*vv(x1，…，x2d)=A1·(xd+1，…，x2d)T+b1就定义了一个2d阶的多元二次右拟群(Q'，*)。

证明:考虑操作*vv(a1，…，ad，xd+1，…，x2d)=(c1，…，cd)，其中 xd+1，…，x2d是未知比特，而 ai、ci是已知比特，在GF(2)域中有类似的线性系统

式中A'1和b'1是将已知布尔向量(a1，…，ad)代入A1和b1后得出的布尔矩阵。

由于 Det(A1)=1，所以 Det(A'1)=1，因此式(4)具有唯一的解(xd+1，…，x2d)T=(A'1)－1·((c1，…，cd)T－b'1。从而可判定该群运算符合右拟群的定义。

证毕。

根据定理1，本文给出了构造2d阶多元二次右拟群(MQQ’)的算法(见图1)。

图1 构造2d阶多元二次右拟群的算法

与生成多元二次拟群 MQQ(d，k)算法［4］相比，该 MQQ'(d，k)算法并不需要进行大量随机循环，每次都可返回一个待选目标。这样，每次都可以判断该待选目标是否符合设定的密钥安全性指标，如果符合即可使用，不符合则继续构造新的待选目标。

2.3 右拟群构造算法的应用特点

图2 一个8阶的右拟群

图2使用拉丁方阵形式表示一个8阶多元二次右拟群。在MQQ'(d，k)算法中，将构造的右拟群表示为拉丁方阵形式，则各列中出现重复的元素总数r越少，其抗线性分析能力就越好。因此，为了防止生成弱密钥，必须对选取的右拟群所隐含的密码学特征进行限制。

对n=3、n=4条件下的右拟群构造进行统计(见表1、表2)。通过分析可知，随着搜索的进行，最优r值指标在最初很快降低后，会出现大幅度的瓶颈段，降低该指标的代价变得越来越高。所以，要取得强度更高的密钥，不得不考虑运算代价。根据这个指标，可以在一个在限定时间内构造可接受的安全密钥，如对于n=4条件下r=48是一个性价比较好的折衷指标，所有r小于48的右拟群都认为符合要求。

表1 n=3条件下的右拟群构造统计分析

表2 n=4条件下的右拟群构造统计分析

3 结论

本文提出了多元二次右拟群的概念，并给出其判断方法和构造算法，将其应用在MQQ公钥体制中。根据统计规律可获得右拟群的最佳性价比安全指标，应用该指标可以有效地避开巨大搜索空间中的大幅瓶颈区，提高密钥生成速度。

［1］ Hideki Imai，Tsutomu Matsumoto.Algebraic methods for constructing asymmetric cryptosystems［J］.Lecture Notes in Computer Science，1986，229(1):108－119.

［2］ Adi Shamir.Efficient Signature Schemes Based on Birational Permutations［C］//Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology.Springer－Verlag，1993:1 －12.

［3］ Gligoroski D，Markovski S，Knapskog S J.Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups［J］.Math Proceedings of the American Conference on Applied Mathematics，2008.

［4］ Danilo Gligoroski，Smile Markovski，Svein Johan Knapskog.Public Key Block Cipher Based on Multivariate Quadratic Quasigroups［EB/OL］.2008 －11 －20.http://eprint.iacr.org/2008/320.

［5］ Markovski S，Gligoroski D，Bakeva V.Quasigroup String Processing［J］.Part Contributions Sec.math.tech.sci.manu XX，2003(1－2):1－2.

［6］ Mohamed El－ Hadedy，Danilo Gligoroski，Svein J Knapskogz.High Performance Implementation of a Public Key Block Cipher－MQQ，for FPGA Platforms［EB/OL］.(2008 －08 －11)［2008 －11 －22］.http://eprint.iacr.org/2008/339.