1、代數(shù)攻擊是一種重要的密碼分析技術(shù)，主要利用密碼體制的代數(shù)性質(zhì)及現(xiàn)有代數(shù)系統(tǒng)求解方法來(lái)攻擊密碼體制。它可以用于攻擊流密碼、分組密碼及多變量密碼等體制。常見(jiàn)的代數(shù)攻擊方法有兩類：Gr(o)bner基方法和XL(eXtended Linearization)方法。
　　本文對(duì)求解F[x，y]上理想的約化Gr(o)bner基的算法及Mutant-based Gr(o)bner Basisalgorithm(MGB)算法進(jìn)行了改進(jìn)與實(shí)現(xiàn)，主

2、要工作如下：
　　(1)證明了單項(xiàng)式序?yàn)樽值湫驎r(shí)，多項(xiàng)式組G經(jīng)過(guò)約化和多項(xiàng)式排序后，如果其中相鄰的元素之間的S-多項(xiàng)式被G除得的余式都為零，那么G就是理想的Gr(o)bner基。我們知道當(dāng)理想的單項(xiàng)式序?yàn)榉旨?jí)逆字典序時(shí)是最容易計(jì)算出其Gr(o)bner基。改進(jìn)的算法利用這兩個(gè)單項(xiàng)式序的優(yōu)點(diǎn)，通過(guò)在計(jì)算過(guò)程中改變單項(xiàng)式序，使得S-多項(xiàng)式的計(jì)算次數(shù)大幅減少，最終正確有效地計(jì)算出F[x，y]上理想的Cr(o)bner基。最后隨機(jī)選

3、取了幾組多項(xiàng)式，與著名的F4算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果顯示，改進(jìn)的算法比F4算法更快，甚至快上一個(gè)數(shù)量級(jí)，而且可以求解出陳銀東等的算法不能求解的案例。
　　(2)發(fā)現(xiàn)了MGB算法不能正常終止和不能正確計(jì)算出Gr(o)bner基的案例，并分析其原因，改進(jìn)的算法利用繼續(xù)擴(kuò)展“已滿”分區(qū)、更為細(xì)致地分區(qū)擴(kuò)展等方法來(lái)克服這兩點(diǎn)缺陷。MOB算法忽略了上輪產(chǎn)生的但在Enlarge步驟未被選取的mutants多項(xiàng)式，改進(jìn)的算法發(fā)現(xiàn)繼續(xù)使用這些多項(xiàng)