- Turkish Journal of Electrical Engineering and Computer Science
- Vol: 21 Issue: 1
- A time--memory trade-off approach for the solution of nonlinear equation systems
A time--memory trade-off approach for the solution of nonlinear equation systems
Authors : Hüseyin DEMİRCİ
Pages : 186-197
Doi:10.3906/elk-1103-42
View : 5 | Download : 2
Publication Date : 9999-12-31
Article Type : Makaleler
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 237 operations where a brute force approach requires 272 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. 2n/2) operations and using O(2n/2) units of memory rather than O(2n) trials of the equation system.Keywords : Key words: Time-memory trade-off, solution of nonlinear equations, AES, cryptanalysis