嚴深海

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

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

嚴深海

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

研究兩類含項的單模數(shù)多變量二次同余方程組的求解方法及其在設計密碼體系中的應用.針對p≡3 mod 4研究得到了多變量二次密碼體系MVQC（Multivariate Quadratic Cryptography），給出了數(shù)值算例，算例說明所設計的密碼體系是可行的，鑒于交互確認的解密策略，密碼體系是安全的.

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

0 引言

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

文中研究兩類含x2i項的單模數(shù)多變量二次同余方程組的求解方法及依其設計密碼體系，特別是模數(shù)p≡3 mod 4時的情形.具體來說，文中研究以下單模數(shù)多變量二次同余方程組的求解方法及其在設計密碼體系中的應用：

這里，p為素數(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時，各自對應的方程為

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

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

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為變量的二次多項式[4].基于這類問題得到的密碼體系通常記為MQ—Schemes[4].目前，研究較成熟的是“可線性化的二次問題”：

1 方程組I的求解及其在密碼體系設計中的應用

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

引理1[10]當a≠0，（a，p）=1，方程（ax2+bx+c）≡0 mod p與（x-x0）（x-x1）≡0 mod p等價時，有解x0和x1.

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

引理3[10]當p≡3 mod 4c0mod p有解，且解的表達式為

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

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

加密：當乙方要傳送信息x給甲方時，乙方找出甲方的密鑰（a，b，c，p），通過式（1）計算出y*≡（ax2+bx+c）mod p，且傳y*給甲方.

解密：當甲方收到乙方傳來的信息y*，通過解方程（ax2+bx+c）mod p≡y*，可得到解x0、x1.于是從x0、x1中選定一個確認為乙方送給甲方的信息x*.

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

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

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

于是，根據(jù)方程組I對應的式（3）和（4）可設計密碼體系(簡記為MVQC-2)如下：

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

加密：當乙方要傳送信息X給甲方時，乙方找出甲方的密鑰（Ak，B，C，p），通過式（3）計算出Y*≡（XTAX+BX+C）mod pY*給甲方.

解密：當甲方收到乙方傳來的信息Y*，通過式（4）逐次解單元方程：

得解xi0和xi1，從而同一密文Y*有與之對應的2n個解Xi=（x1，x1，…，xn）T，這里xi=xi0或xi1.將所有解按字典順序排列，則解與其序號有唯一對應關系.

唯一明文的確定：

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

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

2 方程II的求解及其在密碼體系設計中的應用

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

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

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

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

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

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

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

這時，

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

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

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

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

唯一明文的確定：

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

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

3 數(shù)值算例

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

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

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

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

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

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

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

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

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

表1 Y所有可能的解（表中“-”標識無解）

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

2）再由X*通過方程YTUY+VY+W≡X*mod p解出Y（見表1）；

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

解密：當甲方得到乙方傳來的數(shù)據(jù)Y（向量）時，則甲方：

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

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

唯一明文的確定：

表2 X所有可能的解（表中“-”標識無解）

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

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

[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].北京郵電大學學報，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].江西理工大學學報，2010，31(3)：60-63.

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

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

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

[10]賴溪松，韓亮，張真誠.計算機密碼學及其應用[M].北京：國防工業(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

江西省科技廳科技支撐計劃項目（2009ZDG03600）

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

2095-3046（2012）03-0076-05