•  
  •  
 

Turkish Journal of Electrical Engineering and Computer Sciences

DOI

10.3906/elk-1103-42

Abstract

We propose a memory-based method for the solution of a specific type of nonlinear equation systems. We observe that when the equations in a system can be separated into 2 parts, where each subset contains fewer parameters than the whole set of equations, the system can be solved faster with a preprocessing phase. We show that reduced rounds of AES produce such a system under a chosen plaintext scenario. This observation enables us to solve that system within a practically applicable complexity of 2^{37} operations where a brute force approach requires 2^{72} trials. The method can be used for the solution of other equation systems of the same structure. In the optimal case where we can divide the equations into 2, a problem that contains n binary variables can be solved at time O(n/2. 2^{n/2}) operations and using O(2^{n/2}) units of memory rather than O(2^n) trials of the equation system.

Keywords

Time-memory trade-off, solution of nonlinear equations, AES, cryptanalysis

First Page

186

Last Page

197

Download

Share

COinS