| Meno: | Martin
|
|---|
| Priezvisko: | Voros
|
|---|
| Názov: | Algebraic attack on stream ciphers
|
|---|
| Vedúci: | RNDr. Martin Stanek, PhD
|
|---|
| Rok: | 2007
|
|---|
| Blok: | MMI
|
|---|
| Kµúčové slová: | Algebraic attack, fast algebraic attack, stream ciphers, linear feedback shift register, A5/1, XL algorithm, SAT solver.
|
|---|
| Abstrakt: | An algebraic attack is a new cryptanalytic method. The main idea behind this method is finding and solving a system of multivariate polynomial equations over finite field. Recently, algebraic attacks were very successful against certain stream ciphers based on LFSRs (e.g. nonlinear filter generators and nonlinear combination generators). In this paper, we explain the main ideas of algebraic attack on stream ciphers and illustrate them with examples. We describe methods for generating systems of polynomial equations for some classes of the stream ciphers based on LFSRs. We set out to study the XL algorithm for solving these systems and run various computer simulations for verifying the behaviour of the XL algorithm. Afterwards, the method for solving the system of nonlinear equations using SAT solvers is presented, and the experimental analysis of our heuristic for speeding up the conversion from algebraic normal form to conjunctive normal form is described. Efficiency of this conversion is eminent for the use of SAT solver for solving the system of equations. We concluded that the presented heuristic is highly efficient for the systems with high density. We also explain the improvement of the algebraic attack -- namely the fast algebraic attack.
|
|---|