基于多元二次擬群的公鑰體制改進(jìn)

邱忠升，王 蓉，蔣飄蓬

(海軍航空工程學(xué)院訓(xùn)練部，山東煙臺264001)

在公鑰密碼學(xué)的發(fā)展歷程中，基于多元二次方程的公鑰密碼體制是公鑰密碼學(xué)領(lǐng)域中的熱點。該密碼體制利用有限域上的多元二次方程集合作為非對稱密碼系統(tǒng)的公鑰［1－2］。其設(shè)計是基于一個NP－C問題，即求解一個有限域上的多元二次方程組是困難的。Gligoroski D等［3－4］提出利用擬群理論［5］構(gòu)造多元二次方程組的方法，進(jìn)而得出一種新的公鑰體制:基于多元二次擬群的公鑰算法(簡稱MQQ公鑰算法)。MQQ公鑰算法具有高度并行的優(yōu)點，其在FPGA硬件上的并行實現(xiàn)速度可達(dá)同等條件下RSA公鑰的10 000倍以上［6］。同時，MQQ公鑰算法存在一個不可回避的缺陷，即密鑰生成速度較慢，這是其生成多元二次擬群的算法低效造成的。

本文分析了MQQ公鑰算法所依據(jù)的擬群變換理論及性質(zhì)，提出了基于右擬群構(gòu)造密鑰的方法，大大提高了密鑰的生成速度。通過程序模擬分析，得出了該改進(jìn)算法的應(yīng)用特點，并給出了在構(gòu)造密鑰過程中需遵循的設(shè)計原則，以防止弱密鑰產(chǎn)生。

1 MQQ公鑰算法中密鑰構(gòu)造的缺點分析

MQQ公鑰算法［4］在創(chuàng)建密鑰的過程中，將用到8個擬群運(yùn)算*1，…，*8:

通過私鑰解密的算法中使用此8個擬群的左除運(yùn)算:

式中左除i(i=1，…，8)運(yùn)算分別對應(yīng)擬群*i(i=1，…，8)的左除。

多元二次擬群的構(gòu)建到目前為止還沒有高效的算法。文獻(xiàn)［4］介紹了一種能構(gòu)造出2d階且屬Q(mào)uadd－kLinkk類型的多元二次擬群的流程MQQ(d，k)。該算法在巨大未定空間內(nèi)隨機(jī)搜索判斷，其搜索成功的計算代價很高。事實上，當(dāng)d=5，生成一個Quad5Link0類型的MQQ大約需要嘗試216次［4］。構(gòu)造8個隨機(jī)構(gòu)造的多元二次擬群的過程占用的時間太多，從而使得MQQ公鑰算法中構(gòu)造密鑰的過程變得非常慢。相比其他公鑰算法，在密鑰生成速度方面MQQ公鑰算法具有很大劣勢。

2 應(yīng)用右擬群改進(jìn)MQQ公鑰算法

2.1 右擬群的定義

定義1 如果(Q'，*)是一個集合Q'與一個二元運(yùn)算* 的結(jié)合，若Q'中的任意元素a和b都存在唯一的Q中元素x，滿足a*x=b，則這個群(Q'，*)被稱為右擬群。

行和列中都沒有重復(fù)元素的方陣被稱為拉丁方陣，擬群可表示為拉丁方陣形式［5］。而右擬群如果表示為方陣形式，各行中都沒有重復(fù)的元素，而列中會出現(xiàn)重復(fù)的元素。右擬群具有左除運(yùn)算x=a，而沒有右除運(yùn)算，因為右除得不到唯一右除值。

只要保證式(1)中*ij是右擬群(而不必是擬群)，那么式(2)同樣是有效的可逆變換，即MQQ公鑰算法不需要嚴(yán)格的多元二次擬群，而只需多元二次右擬群。

2.2 多元二次右擬群的構(gòu)造

定理1 設(shè)A1=［fij］d×d是一個d×d的各元素為線性布爾表達(dá)式的布爾矩陣，b1=［ui］d×1是各元素為線性或二次布爾表達(dá)式的布爾向量。其中，設(shè)fij和ui只依賴于參數(shù)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)域中有類似的線性系統(tǒng)

式中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。從而可判定該群運(yùn)算符合右擬群的定義。

證畢。

根據(jù)定理1，本文給出了構(gòu)造2d階多元二次右擬群(MQQ’)的算法(見圖1)。

圖1 構(gòu)造2d階多元二次右擬群的算法

與生成多元二次擬群 MQQ(d，k)算法［4］相比，該 MQQ'(d，k)算法并不需要進(jìn)行大量隨機(jī)循環(huán)，每次都可返回一個待選目標(biāo)。這樣，每次都可以判斷該待選目標(biāo)是否符合設(shè)定的密鑰安全性指標(biāo)，如果符合即可使用，不符合則繼續(xù)構(gòu)造新的待選目標(biāo)。

2.3 右擬群構(gòu)造算法的應(yīng)用特點

圖2 一個8階的右擬群

圖2使用拉丁方陣形式表示一個8階多元二次右擬群。在MQQ'(d，k)算法中，將構(gòu)造的右擬群表示為拉丁方陣形式，則各列中出現(xiàn)重復(fù)的元素總數(shù)r越少，其抗線性分析能力就越好。因此，為了防止生成弱密鑰，必須對選取的右擬群所隱含的密碼學(xué)特征進(jìn)行限制。

對n=3、n=4條件下的右擬群構(gòu)造進(jìn)行統(tǒng)計(見表1、表2)。通過分析可知，隨著搜索的進(jìn)行，最優(yōu)r值指標(biāo)在最初很快降低后，會出現(xiàn)大幅度的瓶頸段，降低該指標(biāo)的代價變得越來越高。所以，要取得強(qiáng)度更高的密鑰，不得不考慮運(yùn)算代價。根據(jù)這個指標(biāo)，可以在一個在限定時間內(nèi)構(gòu)造可接受的安全密鑰，如對于n=4條件下r=48是一個性價比較好的折衷指標(biāo)，所有r小于48的右擬群都認(rèn)為符合要求。

表1 n=3條件下的右擬群構(gòu)造統(tǒng)計分析

表2 n=4條件下的右擬群構(gòu)造統(tǒng)計分析

3 結(jié)論

本文提出了多元二次右擬群的概念，并給出其判斷方法和構(gòu)造算法，將其應(yīng)用在MQQ公鑰體制中。根據(jù)統(tǒng)計規(guī)律可獲得右擬群的最佳性價比安全指標(biāo)，應(yīng)用該指標(biāo)可以有效地避開巨大搜索空間中的大幅瓶頸區(qū)，提高密鑰生成速度。

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