基于單模數(shù)多變量二次同余方程組設(shè)計(jì)的密碼體系

嚴(yán)深海

（贛南師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西贛州341000）

基于單模數(shù)多變量二次同余方程組設(shè)計(jì)的密碼體系

嚴(yán)深海

（贛南師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西贛州341000）

研究?jī)深惡?xiàng)的單模數(shù)多變量二次同余方程組的求解方法及其在設(shè)計(jì)密碼體系中的應(yīng)用.針對(duì)p≡3 mod 4研究得到了多變量二次密碼體系MVQC（Multivariate Quadratic Cryptography），給出了數(shù)值算例，算例說(shuō)明所設(shè)計(jì)的密碼體系是可行的，鑒于交互確認(rèn)的解密策略，密碼體系是安全的.

二次同余；多變量；密碼體系；MQ-Schemes

0 引言

設(shè)計(jì)多變量密碼體系的思路是使用特殊的非線性多項(xiàng)式函數(shù)組，它的安全性基礎(chǔ)是一個(gè)已被證明的定理，即求解有限域上的2次以上的多元多項(xiàng)式方程組是一個(gè)NPC問(wèn)題[1].多變量密碼體制被許多密碼學(xué)家認(rèn)為具有效率高和抗量子計(jì)算機(jī)攻擊的優(yōu)點(diǎn)[2-3]，是未來(lái)量子計(jì)算時(shí)代密碼的備選方案之一，因此備受關(guān)注.目前，研究了含xixj而不含項(xiàng)的單模數(shù)多變量二次同余方程組的求解方法及依其設(shè)計(jì)了密碼體系的有文獻(xiàn)[4、5、6]，研究了含xixjxk而不含、項(xiàng)的單模數(shù)多變量三次同余方程組的求解方法及依其設(shè)計(jì)了密碼體系的有文獻(xiàn)[5]，文獻(xiàn)[7、8、9]研究了含xixjxkxl的單模數(shù)多變量四次同余方程組的求解方法及其應(yīng)用，尚未見(jiàn)含項(xiàng)情形的報(bào)道.

文中研究?jī)深惡瑇2i項(xiàng)的單模數(shù)多變量二次同余方程組的求解方法及依其設(shè)計(jì)密碼體系，特別是模數(shù)p≡3 mod 4時(shí)的情形.具體來(lái)說(shuō)，文中研究以下單模數(shù)多變量二次同余方程組的求解方法及其在設(shè)計(jì)密碼體系中的應(yīng)用：

這里，p為素?cái)?shù)，X=（x1，x2，…，xn）T，Y=（y1，y2，…，yn）T，xi，yi∈{0，1，…，p-1}，A=（A1，A2，…，An）T，U=（U1，U2，…，Un）T，C=（c1，c2，…，cn）T，W=（w1，w2，…，wn）T，wi，ci∈{0，1，…，p-1}，XTAX=（XTA1X，XTA2X，…，XTAnX）T，YTUY=（YTU1Y，YTU2Y，…，YTUnY）T，其中

特別地，在方程組Ⅰ、Ⅱ中取n=1時(shí)，各自對(duì)應(yīng)的方程為

這里，μ，v，ω，a，b，c∈{0，1，…，p-1}.

上述問(wèn)題屬于MQ(Multivariate quadratic)問(wèn)題，該類問(wèn)題通常表述為：

f1（x1，x2，…，xm，y1，y2，…，yk）≡0 mod p,…，fn（x1，x2，…，xm，y1，y2，…，yk）≡0 mod p，這里fi（x1，x2，…，xm，y1，y2，…，yk）為以x1，x2，…，xm，y1，y2，…，yk為變量的二次多項(xiàng)式[4].基于這類問(wèn)題得到的密碼體系通常記為MQ—Schemes[4].目前，研究較成熟的是“可線性化的二次問(wèn)題”：

1 方程組I的求解及其在密碼體系設(shè)計(jì)中的應(yīng)用

本節(jié)首先討論單個(gè)方程（1）的求解，然后得到方程組I的求解及其應(yīng)用.

引理1[10]當(dāng)a≠0，（a，p）=1，方程（ax2+bx+c）≡0 mod p與（x-x0）（x-x1）≡0 mod p等價(jià)時(shí)，有解x0和x1.

引理2[10]當(dāng)a≠0，（a，p）=1，方程（ax2+bx+c）≡0 mod p與Z2≡c0mod p等價(jià)，這里，Z=x+（2a）-1b,c0=（b2-4ac）（4a2）-1.

引理3[10]當(dāng)p≡3 mod 4c0mod p有解，且解的表達(dá)式為

于是，基于單個(gè)方程y≡（ax2+bx+c）mod p可設(shè)計(jì)密碼體系(簡(jiǎn)記為MVQC-1)如下：

系統(tǒng)設(shè)置：甲方選擇整數(shù)a，b和c及p≡3 mod 4且傳（a，b，c，p）給乙方.

加密：當(dāng)乙方要傳送信息x給甲方時(shí)，乙方找出甲方的密鑰（a，b，c，p），通過(guò)式（1）計(jì)算出y*≡（ax2+bx+c）mod p，且傳y*給甲方.

解密：當(dāng)甲方收到乙方傳來(lái)的信息y*，通過(guò)解方程（ax2+bx+c）mod p≡y*，可得到解x0、x1.于是從x0、x1中選定一個(gè)確認(rèn)為乙方送給甲方的信息x*.

再則，研究方程組I知其有以下等價(jià)式：

定理1考慮到矩陣A、B的特殊結(jié)構(gòu)，方程Y≡（XTAX+BX+C）mod p等價(jià)為：

定理2進(jìn)一步考慮到Ai的特殊結(jié)構(gòu)，方程Y≡（XTAX+BX+C）mod P等價(jià)為：

于是，根據(jù)方程組I對(duì)應(yīng)的式（3）和（4）可設(shè)計(jì)密碼體系(簡(jiǎn)記為MVQC-2)如下：

系統(tǒng)設(shè)置：甲方選擇矩陣Ak（k=1，2，…，n），B和C及p≡3 mod 4，且傳送給乙方.

加密：當(dāng)乙方要傳送信息X給甲方時(shí)，乙方找出甲方的密鑰（Ak，B，C，p），通過(guò)式（3）計(jì)算出Y*≡（XTAX+BX+C）mod pY*給甲方.

解密：當(dāng)甲方收到乙方傳來(lái)的信息Y*，通過(guò)式（4）逐次解單元方程：

得解xi0和xi1，從而同一密文Y*有與之對(duì)應(yīng)的2n個(gè)解Xi=（x1，x1，…，xn）T，這里xi=xi0或xi1.將所有解按字典順序排列，則解與其序號(hào)有唯一對(duì)應(yīng)關(guān)系.

唯一明文的確定：

乙方：根據(jù)信息Y*，通過(guò)式（4）逐次解單元方程：

甲方：根據(jù)乙方傳的數(shù)據(jù)i，在解Xi的排序方案中找到對(duì)應(yīng)的信息X，得到唯一明文.

2 方程II的求解及其在密碼體系設(shè)計(jì)中的應(yīng)用

本節(jié)首先討論單個(gè)方程（2）的求解，然后得到方程組II的求解及其應(yīng)用.容易基于單個(gè)方程μy2+vy+ω≡（ax2+bx+c）mod p設(shè)計(jì)密碼體系(簡(jiǎn)記為MVQC-3)如下：

系統(tǒng)設(shè)置：設(shè)素?cái)?shù)p為通信雙方預(yù)先約定的.當(dāng)甲乙雙方需要通信時(shí)，臨時(shí)建立方程，且甲方選擇整數(shù)（a，b，c）且傳送給乙方；乙方選擇整數(shù)（μ，v，ω）且傳送給甲方.

加密：當(dāng)乙方要傳送x給甲方時(shí)，乙方找出甲方傳給的數(shù)據(jù)（a，b，c），計(jì)算x*≡（ax2+bx+c）mod p，乙方求解方程μy2+vy+ω≡x*mod p得y0和y1，乙方將y=y0或y1傳送給甲方.

解密：當(dāng)甲方得到乙方傳來(lái)的數(shù)據(jù)y時(shí)，甲方找出乙方傳送的數(shù)據(jù)（μ，v，ω），計(jì)算y*≡（μy2+vy+ω）mod p，且求解方程（ax2+bx+c）≡y*mod p得x0和x1，甲方視x0或x1為乙方要傳送給甲方的信息.

再則，研究方程II知其有以下等價(jià)式：

定理3考慮到矩陣U，V，A，B的特殊結(jié)構(gòu)，方程II可整理為：

定理4進(jìn)一步考慮到Ui，Ai的特殊結(jié)構(gòu)，方程（5）可表示為：

這時(shí)，

于是根據(jù)式（5）（6）可設(shè)計(jì)密碼體系(簡(jiǎn)記為MVQC-4)如下：

系統(tǒng)設(shè)置：設(shè)通訊雙方有共同約定的大素?cái)?shù)p，且p≡3 mod 4.甲方選擇矩陣Ai，構(gòu)造出A，且選擇B和C，且傳送（A，B，C）于乙方；乙方選擇矩陣Ui，構(gòu)造出U，且選擇V和W，且傳送（U，V，W）于甲方.

加密：當(dāng)乙方要傳送信息x給甲方時(shí)，F(xiàn)or i=1，2，…，n，乙方找出甲方傳的三元組數(shù)據(jù)（A，B，C），由式（6）計(jì)算n；乙方根據(jù)自己選定的（U，V，W）求解方到y(tǒng)i=yi0，yi1；乙方將最多2n個(gè)可行解中的任一個(gè)傳給甲方.

解密：當(dāng)甲方得到乙方傳來(lái)的數(shù)據(jù)Y時(shí)，甲方找出乙方傳的三元組（U，V，W），由式（6）計(jì)算方根據(jù)自己選定的（A，B，C），求解方此時(shí)2n個(gè)解按字典順序排列，所有解有唯一序號(hào).

唯一明文的確定：

乙方：根據(jù)信息Y*，通過(guò)式（6）逐次解單元方程：

甲方：根據(jù)乙方傳的數(shù)據(jù)i，在解Xi的排序方案中找到對(duì)應(yīng)的信息X，從而得到唯一明文.

3 數(shù)值算例

以密碼體系MVQC-1、MVQC-4為例，說(shuō)明文中得到的密碼體系是信息冗余、可行、安全：

例1設(shè)通訊雙方約定素?cái)?shù)p=107，試由密碼體系MVQC-1實(shí)現(xiàn)：乙方將信息x=71傳送給甲.

解：系統(tǒng)設(shè)置：甲方選擇整數(shù)（a，b，c）=(86，16，46)且傳送給乙方.

加密：乙方欲將信息x=71傳送給甲方，則乙方計(jì)算出y*≡（ax2+bx+c）mod p≡（86*712+16*71+46）mod 107≡74 mod 107，且將y*傳送給甲方.

解密：當(dāng)甲方得到乙方傳來(lái)的數(shù)據(jù)y*時(shí)，則甲方由ax2+bx+c≡y*mod p即86x2+16x+46≡74 mod 107可反解出x0=71，x1=103，于是從x0、x1中選定一個(gè)確認(rèn)為乙方送給甲方的信息x.

例2設(shè)通訊雙方約定素?cái)?shù)p=107，試由密碼體系MVQC-4實(shí)現(xiàn)：乙方將信息X=（66，98，98，64，36）T傳送給甲.

解：系統(tǒng)設(shè)置：甲方選擇矩陣Ak（k=1，2，…，5），B以及向量C如下，并將之傳送給乙方；

乙方選擇矩陣Uk（k＝1，2，3，4，5）、V及向量W如下，并將之傳送給甲方.

加密：乙方欲將信息X=（66，98，98，64，36）T傳給甲方時(shí)，則乙方：

表1 Y所有可能的解（表中“-”標(biāo)識(shí)無(wú)解）

1）由X計(jì)算出X*≡（XTAX+BX+C）mod P≡（46，42，58，89，101）Tmod 107；

2）再由X*通過(guò)方程YTUY+VY+W≡X*mod p解出Y（見(jiàn)表1）；

3）乙方將上表中Y=(34，44，26，5，53)傳給甲方.

解密：當(dāng)甲方得到乙方傳來(lái)的數(shù)據(jù)Y（向量）時(shí)，則甲方：

1）計(jì)算Y*≡（YTUY+VY+W）mod P≡（46，42，58，89，101）Tmod 107；

2）求解方程（XTAX+BX+C）mod P≡Y*得X（見(jiàn)表2）.

唯一明文的確定：

表2 X所有可能的解（表中“-”標(biāo)識(shí)無(wú)解）

甲方：根據(jù)乙方傳的數(shù)據(jù)i=19，在解的排序方案中找到對(duì)應(yīng)的信息X=（66，39，36，104，32），從而得到唯一明文.

綜上所述，文中研究了兩類特殊結(jié)構(gòu)的多變量二次同余方程組的求解及其在密碼體系設(shè)計(jì)中的應(yīng)用.所設(shè)計(jì)的密碼體系采用了一種特殊的矩陣結(jié)構(gòu)和多變量二次同余式，能獲得較高安全性.再加上從按字典排序排列的2n個(gè)解中，雙方在傳遞信息的同時(shí)要臨時(shí)確定一序號(hào)才能得到傳送準(zhǔn)確的信息，解的多樣性，信息的冗余性，也增添了密碼體系傳送信息的安全性.

[1]DingJ，GowerJE，SchmidtDS.Multivariatepublickey cryptosystems[M].Berlin：Springer-Verlag Press，2006.

[2]Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Journal on Computing，1997，26(5)：1484-1509.

[3]王鑫，劉景美，王海梅.多變量簽名模型的改進(jìn)[J].北京郵電大學(xué)學(xué)報(bào)，2009，32(5)：124-127.

[4]Wang L C，Yang B Y，Hu Y H，et al.A“Medium-Field”multivariate public-key encryption scheme[J].Lecture Notes in Computer Science，2006(3860)：132-149.

[5]Tsutomu Matsumoto，Hideki Imai.Public quadratic polynomialtuples for efficient signature-verification and message-encryption[J].Lecture Notes in Computer Science，1988(330)：419-453.

[6]林殊芳，湯紹春.一類帶有冗余信息的Hill密碼體系[J].江西理工大學(xué)學(xué)報(bào)，2010，31(3)：60-63.

[7]李文鋒.基于RSA和Hill密碼體系的文件加密系統(tǒng)的研究和實(shí)現(xiàn)[D].贛州：江西理工大學(xué)，2007.

[8]王志偉，鄭世慧，楊義先，等.改進(jìn)的Medium-Field多變量公鑰加密方案[J].電子科技大學(xué)學(xué)報(bào)，2007，36(6)：1152-1154.

[9]田禮，鮑皖蘇.MFE多變量公鑰改進(jìn)方案分析[J].計(jì)算機(jī)工程，2010，36(18)：155-157.

[10]賴溪松，韓亮，張真誠(chéng).計(jì)算機(jī)密碼學(xué)及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2001.

A cryptosystem based on multivariate quadratic equations with single modulus

YAN Shen-hai

(College of Mathematics and Computer Science，Gannan Normal University，Ganzhou 341000，China)

The article studies the solutions to two types of single modulus multivariate quadratic equations including itemand their applications in the designment of cryptosystems.We get the multivariate quadratic cryptosystem(MVQC)by studyingand give some numerical examples.The examples demonstrate MVQC's feasibility.Given decryption strategy with interactive confirmation,MVQC is a secure encryption scheme.

quadratic congruence;multivariate；cryptosystem；MQ-Schemes

TN918.1

A

2012-02-29

江西省科技廳科技支撐計(jì)劃項(xiàng)目（2009ZDG03600）

嚴(yán)深海（1972-），男，講師，主要從事算法設(shè)計(jì)、圖像處理等方面的研究，E-mail：gnsyysh@126.com.

2095-3046（2012）03-0076-05