有限域上代數(shù)方程算法問(wèn)題研究2013年度報(bào)告

胡磊

摘要：本年度圍繞關(guān)鍵科學(xué)問(wèn)題“有限域上代數(shù)方程求解”，結(jié)合密碼學(xué)理論，在求解算法研究及其密碼應(yīng)用方面取得了以下三方面的進(jìn)展：（1）在有限域上方程系統(tǒng)求解算法方面，提出了一個(gè)二元域上帶噪方程系統(tǒng)的求解算法；給出了一種從代數(shù)方程到CNF轉(zhuǎn)換的高效算法。（2）在利用代數(shù)方程求解算法進(jìn)行密碼分析方面，推進(jìn)了分組密碼KATAN、PRINCE等的分析；在多變量密碼的分析方面，利用線性化方法分析了MFE改進(jìn)方案、擴(kuò)展的多變量公鑰密碼方案、兩層非線性Piece in hand增強(qiáng)方案，用多項(xiàng)式向量的不確定插值方法改進(jìn)了對(duì)SFLASH密碼體制的攻擊；利用線性化方法或格基約化算法分析了一些基于格及背包問(wèn)題的密碼算法；在代數(shù)攻擊中自動(dòng)推理方法的研究方面，利用解方程組的思想，提出了基于字的分組密碼算法的不可能差分路徑自動(dòng)化搜索的算法，擴(kuò)展了Mouha等人基于混合整數(shù)線性規(guī)劃的方法，給出了一種自動(dòng)化評(píng)估比特級(jí)分組密碼抵抗相關(guān)密鑰差分攻擊安全性的方法；（3）在利用代數(shù)方法設(shè)計(jì)對(duì)稱(chēng)密碼組件方面，給出了一系列基于線性反饋移位寄存器實(shí)現(xiàn)的低代價(jià)最優(yōu)擴(kuò)散層的構(gòu)造；否證了C.Carlet于1998年提出的“任何一個(gè)AB函數(shù)都EA等價(jià)于一個(gè)置換”的猜想。除以上三方面之外，針對(duì)ALE認(rèn)證加密算法泄露消息沒(méi)有受到密鑰保護(hù)的特點(diǎn)，提出了一種新的偽造攻擊方法——泄露狀態(tài)偽造攻擊。

關(guān)鍵詞：代數(shù)方程；算法問(wèn)題；密碼應(yīng)用

A general report on the study of the project “Algorithmic problems of algebraic equations over finite fields” in 2013

Abstract：This year， our research group， focusing on the key scientific problem of solving algebraic equations over finite fields and its applications in the cryptography， has made the following progress： （1） For solving algebraic equations over finite fields， we proposed an algorithm which can solve systems of polynomial equations with noise over GF（2）， and an efficient method for converting a system of algebraic equations into its conjunction normal form； （2） For the application of algebraic equation solving techniques in the cryptanalysis， we improved the cryptanalysis of block ciphers KATAN， PRINCE， etc.； Also， by employing the linearization technique， we attacked some multivariate public-key cryptosystems such as an improved MFE scheme， the Extended Multivariate Public Key Cryptosystem and a strengthened two-layer Piece in Hand scheme. Moreover， we obtained a more efficient attack on SFLASH with the method of projective interpolation of polynomial vectors and cryptanalyzed some lattice and knapsack based public key schemes using linearization and lattice reduction methods. In addition， by extending Mouha et als methods， we proposed an algorithm for automatic impossible differential path search and automatic security evaluation for bit-oriented ciphers with respect to related-key differential attack. （3） For the application of algebraic methods in designing secure components of block ciphers， we presented a series of low cost diffusion layers which can be implemented using linear shift registers. Whats more， we showed the conjecture proposed by C. Carlet in 1998， stating that every AB function is EA equivalent to a permutation， is not correct. Besides， we proposed a new attack method on the ALE authenticated encryption scheme， the leaked state forgery attack， by exploiting its leaked messages which are not protected by the secret key.

Keywords：algebraic equation；algorithmic problem；general report

閱讀全文鏈接（需實(shí)名注冊(cè)）：http：//www.nstrs.cn/xiangxiBG.aspx？id=48073&flag=1