Research On The Algebraic Attacks And Its Applications

Algebraic attack is an important cryptanalysis method developed inrecent years,which have been used against a variety of crypto-systems:symmetric or public key, block ciphers and stream ciphers. The attackconsist of two steps: building a system of algebraic equations to describethe encryption firstly and then solving these equations to recover the keybits.This thesis studies algebraic attack and its applications on someciphers and,at the same the software implementations of keyequation-solving algorithms are also discussed in the last part of the thesiswhich included the following topics:Firstly,we summarized the algorithms to solve a system of algebraicequations over binary field.These algorithms have three categories, thefirst is the classical Gr bner-basis based methods which directly emergedfrom commutative algebra and algebraic geometry and characterized intheoretical soundness and extensive application; the second coming from cryptanalysis practice includes Linearization, Relinearization andeXtended Linearization method;the last is using efficient SatisfiabilitySolver to attain the unknown keys after change the unlinear equations to ainstance of Satisfiability problem and it is now the most efficient method.Secondly,the AES round function has been thoroughly analysed withthe algebraic method.By virtue of meet-in-middle method,under conditionof only unknowing some bits of keys algebraic equations to describe theAES’s round function has been formulated in Mathematica software andthen solve them successfully in two algorithms,the one is F4algorithm—the fast implementation of computation of Gr bner basis,theother is the famous CryptoMiniSat Solver.the result is that the former atmost can only solve40-bit unknown equations,the latter,however,96-bitunknowns,so the latter is far beyond the former in efficiency.Thirdly, Trivium’s security is investigated in details here and somenew result are given under the hypothesis that only part of all288bits keyshad unknown. In recent years, research on Trivium has become a hot topicin stream cipher, especially in cryptanalysis though the full-scale versionstill remains unbroken.With regard to the Trivium-typed algebraic equations there is no notable difference in speed comparing two typicalsolving method.At the same, the propagation ability of Trivium and itsvariants is thoroughly researched in the last part of the paper.Lastly，an integrated software platform for testing algebraic attacks isdeveloped in the VC++6.0IDE on the Windows XP operating system.Allof testing data and results come from this software which implemented theprocedure obtaining algebraic equations of AES round function andTrivium etc. and two typical efficient algorithms to solve algebraicequations。...