Document Type
Article
Publication Date
5-2011
First Advisor
Joshua Holden
Abstract
Cryptographic algorithms are based on a wide variety of difficult problems in mathematics. One of these problems is finding a solution to a system of multivariate quadratic equations (MQ). A generalization of this problem is to find a solution to a system of higher order non-linear equations. Both of these problems are NP-hard over any field. Many cryptosystems such as AES, Serpent, Toyocrypt, and others can be reduced to some form of the MQ problem. In this paper we analyze the relinearization and XL algorithms for solving overdetermined systems of non-linear equations, as well as two variations of the XL algorithm. We then introduce the Toyocrypt stream cipher and show how it can be reduced to a system of non-linear equations. We analyze an attack introduced by Courtois using a variation of XL. We also implemented the attack for a smaller version of Toyocrypt, and made many interesting observations that have not been explained by our analysis.
Recommended Citation
Crockett, Eric, "Algebraic Solutions to Overdefined Systems with Applications to Cryptanalysis" (2011). Mathematical Sciences Technical Reports (MSTR). 10.
https://scholar.rose-hulman.edu/math_mstr/10
Included in
Algebra Commons, Discrete Mathematics and Combinatorics Commons, Theory and Algorithms Commons
Comments
MSTR 11-06