一種基于代數(shù)幾何理論的Jonquières密碼體制

張茂勝 孫小雁

1 玉林師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院 廣西 537000

2 玉林師范學(xué)院計算機(jī)科學(xué)與工程學(xué)院 廣西 537000

0 引言

當(dāng)前主流的公鑰密碼體制如 RSA密碼、橢圓曲線密碼(ECC)等的安全性基于大整數(shù)分解或離散對數(shù)的困難性問題，這兩種密碼體制都能夠轉(zhuǎn)換為廣義離散傅里葉變換，1994年貝爾實(shí)驗(yàn)室科學(xué)家Peter Shor提出Shor算法的擴(kuò)展算法，能在量子計算機(jī)下以多項(xiàng)式時間攻擊此類算法。因此量子計算機(jī)的發(fā)展對當(dāng)前的公鑰密碼體制的安全性造成了本質(zhì)威脅。多變量公鑰密碼體制是對抵抗量子計算機(jī)的密碼算法之一，且其運(yùn)算效率非常高，成為近年來密碼學(xué)領(lǐng)域的熱點(diǎn)。本文在多變量公鑰密碼體制的理論基礎(chǔ)上，針對Jonquières映射的缺點(diǎn)，提出Jonquières映射的改進(jìn)方案，彌補(bǔ)Jonquières映射不能抵抗線性攻擊的缺點(diǎn)。

本文內(nèi)容安排如下：第1章引言部分介紹當(dāng)前密碼體制面臨的挑戰(zhàn)，第2章簡要介紹多變量公鑰密碼體制的結(jié)構(gòu)、框架和Jonquières映射理論，第3章從理論上改進(jìn)Jonquières映射并給出一個簡單的有限域上的實(shí)例，最后在第4章總結(jié)本文并給出下一步的研究內(nèi)容。

1 Jonquières映射介紹

1.1 多變量公鑰密碼體制的一般結(jié)構(gòu)

多變量公鑰密碼體制(MQ)是建立在有限域上的多變量多項(xiàng)式，多變量公鑰密碼系統(tǒng)的安全基礎(chǔ)是：求解有限域上的非線性多變量多項(xiàng)式方程組是NP-困難性問題。目前，沒有研究表明量子計算機(jī)在處理該問題上具有優(yōu)勢。確定有限域Fq和Fq的擴(kuò)域，其中n，m為正整數(shù)，分別構(gòu)造可逆仿射變換U,T如式(1)所示。

構(gòu)造中心映射f 如式(2)所示。

中心映射f由m個方程n個變量構(gòu)成，每個方程最高次數(shù)為2，主要用于構(gòu)造單向陷門函數(shù)Y。最后建立域Fq上的多變量公鑰密碼體制，其結(jié)構(gòu)如式(3)。如何構(gòu)造具有良好密碼性質(zhì)的非線性可逆變換Y是MQ密碼的核心。

將式(3)展開可得公鑰Y為有限域Fq上的m個方程n個變元的二次多項(xiàng)式方程組，如式(4)所示。

MQ公鑰密碼的框架圖見圖1。

圖1 MQ密碼的結(jié)構(gòu)

由此可見，MQ密碼體制的私鑰由三部分組成：(U,F,T)。將Y分解成U,F,T是一個IP問題，給定公鑰Y求解一組解x稱為MQ問題，1996年歐密會上Patarin證明了IP問題是一個NP困難性問題，1997年P(guān)atarin和Goubin證明了任意域上的MQ問題是NP完全問題，多變量公鑰密碼體制基于這兩個數(shù)學(xué)難題來構(gòu)造單向陷門函數(shù)Y。

1.2 Jonquières映射基本原理

不同的中心映射的結(jié)構(gòu)決定了不同類型的MQ公鑰密碼體制，其中三角形體制是比較特殊的一類，因?yàn)檫@一類體制的思想來源于代數(shù)幾何。該體制由T.T. Moh于1998首次提出并在美國申請了專利。三角形體制有多種形式，其中最著名的可逆三角映射是 Jonquières提出的 Jonquières映射，其形式如式(5)所示。

其中 xi∈Fq, gi∈ F[ x1, x2,...,xn],1≤i≤n 是任意多項(xiàng)式。由于這種結(jié)構(gòu)的特殊形式，該體制十分容易求逆，因此構(gòu)造出的公鑰體制即可以適用于簽名，又可以用于加解密。但是從安全性的角度衡量，該體制由于滿足線性化攻擊而不能做為安全的密碼算法。

2 改進(jìn)的 Jonquières映射

2.1 Jonquières映射改進(jìn)的原理及結(jié)構(gòu)

根據(jù)Jonquières映射的缺點(diǎn)，重新設(shè)計中心映射，使之不滿足線性化攻擊以增強(qiáng)算法的安全性。在Jonquières映射中，第i個輸出值如式(6)所示。易知yi的值是關(guān)于xi,xi+1,…,xn的多項(xiàng)式。

由式(6)可以看出，第n個輸出yn與第n個輸入xn呈明顯的線性關(guān)系，同樣的，確定yn與xn后，yn-1與第n-1個輸入xn-1呈線性關(guān)系，以此類推?？梢园l(fā)現(xiàn)，Jonquières映射解密高效的同時也造成該映射存在嚴(yán)重的安全漏洞。鑒于此，重新設(shè)計映射的結(jié)構(gòu)，使各輸出與輸入之間不存在線性關(guān)系，以抵抗線性化攻擊。首先重新設(shè)計Jonquières映射(IJ Map)的結(jié)構(gòu)如式(7)所示。

根據(jù)式(7)可以進(jìn)行加密操作，由式(7)可得到 IJ變換的逆變換如式(8)，根據(jù)式(8)可以進(jìn)行解密。

若刪除后(7)中的后n-r個元素，保留前r個，如式(9)所示，則可以構(gòu)造良好的簽名體制。

將式(9)寫成多項(xiàng)式的形式如式(10)所示。

其中fi(xi,…,xn)為域Fq上的多項(xiàng)式，其最高次數(shù)必須為二次及以上。從計算效率上考慮，f為二次多項(xiàng)式即可滿足足夠的安全性，將(y1,…,yr)作為公鑰公開以便驗(yàn)證簽名。

2.2 改進(jìn) Jonquières映射實(shí)例

在{0,1}上構(gòu)建基本域GF(22)，共有q=22=4個元素，乘法群K的生成元α滿足α2+α+1=0，GF(22) 上的乘法和加法運(yùn)算規(guī)則如表1所示。

表1 GF(22)上的乘法和加法運(yùn)算規(guī)則

設(shè)待加密的消息為X=(xi,…,xn)，構(gòu)造如式(11)所示的變換。

構(gòu)造IJ加密變換如式(12)所示。

設(shè) 明 文 M=(1,α,α2,α)， 依 據(jù) 式 (12)可 計 算 得 密 文y=(1,α,α2,α2)，計算過程如式(13)所示。

由加密過程(12)可得解密過程如式(14)所示。

將密文 y=(1,α,α2,α2)代入式(14)可恢復(fù)明文 M=(1,α,α2,α)，計算過程如式(15)所示。

3 結(jié)束語

在介紹對多變量公鑰密碼體制的基本框架和 Jonquières映射的一般結(jié)構(gòu)后，提出Jonquières映射的改進(jìn)方案，以消除Jonquières映射在面對線性攻擊時的脆弱性，同時計算效率并沒有降低。改進(jìn)的Jonquières映射在抵抗其它已知各類攻擊的復(fù)雜度，及是否會有新的攻擊方法，是下一步繼續(xù)研究的內(nèi)容。

[1]SHOR P. W. Algorithms for quantum computation: discrete logarithms and factoring[C].proceedings of the Foundations of Computer Science,1994 Proceedings,35th Annual Symposium on.Santa Fe.NM. USA, 20-22 Nov 1994.

[2]WANG H. Z.,ZHANG H.G.,GUAN H.M.et al.A new perturbation algorithm and enhancing security of SFLASH signature scheme[J].Science China-Information Sciences.2010.

[3]DING J.,GOWER JASON E.,SCHMIDT D.Multivariate public key cryptosystems[M].New York:USA:Springer.2006.

[4]WOLF C.Multivariate quadratic polynomials in public key cryptography[M]. Mierlo: Leuven.2005.

[5]PATARIN JACQUES,GOUBIN LOUIS. Trapdoor one-way permutations and multivariate polynomials Information and Communications Security [M]//HAN Y,OKAMOTO T,QING S.INFORMATION AND COMMUNICATIONS SECURITY Lecture Notes in Computer Science.Berlin/Heidelberg; Springer.1997.

[6]PATARIN JACQUES. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials(IP):Two New Families of Asymmetric Algorithms[C].Advances in Cryptology-EUROCRYPT’96,Berlin/Heidelberg.1996.