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.

Comments

MSTR 11-06

Download

Share

COinS