Comparison of Solving Techniques for Non-linear Sparse Equations over Finite Fields with Application in Cryptanalysis

Abstract

The work on this thesis gives a summary of the Gluing/Agreeing techniques, as well as a reference implementation of this methods. Furthermore widely used SAT-solving techniques are explained and a short insight to the theory of Gröbner basis is given. To demonstrate the application of this techniques two ciphers are presented along with an explanation how to obtain a system of non-linear equations for them. By the reference implementation obtained experimental results are presented in comparison to results of an up-to-date SAT-solver, called minisat. In the last part of this thesis further improvements to the Gluing/Agreeing techniques are presented. Finally the results and cognitions obtained during the work on this thesis are discussed.