代數(shù)攻擊及其在HFE中的應用.pdf

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

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

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