Plans for the Cryptanalysis of the Rijndael Sbox in Maxima/Lisp.
More...
Go to the source code of this file.
Detailed Description
Plans for the Cryptanalysis of the Rijndael Sbox in Maxima/Lisp.
 Todo:
 Connections

See Experimentation/Investigations/Cryptography/AdvancedEncryptionStandard/plans/SboxInvestigations.hpp for experimental investigations.
 Todo:
 Add decomposed Sbox operations

In "Rearranging linear components of Sbox and MixColumns " in Cryptology/Lisp/Cryptanalysis/Rijndael/plans/Translations.hpp we wish to translate the AES by splitting the various parts of the Sbox (inversion, linear multiplication) and moving them into the MixColumns by combining them with the field multiplications.

Therefore we need CNF translations for each of the following functions:

Inversion with the field  tseitin translation as translation function.

Linear multiplication by a GF(b) matrix  tseitin translation as translation function.

Linear multiplication by a GF(b) matrix followed by multiplication in the field  tseitin translation as translation function.

Linear multiplication by a GF(b) matrix followed by multiplication in the field  CNF translation : DONE.

Linear multiplication by a GF(b) matrix  CNF translation : DONE.

DONE Inversion with the field  CNF translation.

All operations are now available in theory using ss_field_op_fulldnf_gen_fcl etc in ComputerAlgebra/Cryptology/Lisp/Cryptanalysis/Rijndael/FieldOperationsAnalysis.mac .
 Todo:
 Representations of the Sbox using additional variables
 Todo:
 Other software systems offering Sbox translations

In the 4.2.1 version of the Sage computer algebra system, there is a module which offers functions related to the cryptanalysis and translation of various substitution boxes to CNF and SymbolicLogic (see http://www.sagemath.org/doc/reference/sage/crypto/mq/sbox.html).

In this system, one can create any substitution box, which is considered as a permutation of the set of numbers 0 to n, and such an SBox object can be generated by specifying the mapping in the same manner as we specify permutations using lists in the Maxima system (modulo the fact that we start with 1). OK: WHERE? LINK? For example, the cyclic shift of the elements {0,...,3} can be generated by
S = sage.crypto.mq.SBox(1,2,3,0)
and then a CNF for this permutation can be generated using or OK: What is the corresponding presentation in our system? for DIMACS, where there are 2 * (log_2(k)+1) variables and k is the number of arguments to SBox, the first log_2(k) + 1 variables are used to represent the big endian representation of the input to the permutation, and the last log_2(k) + 1 variables represent the big endian representation of the output. The CNF generated has (log_2(k)+1) * 2^k clauses, where these clauses are the direct translation of (i_1 /\ ... i_(log_2(k)+1)) => (o_1 /\ ... /\ o_(log_2(k)+1)). OK: What is the "direct translation"? What does this mean for our cases?

There is also a separate module which implements each of the different small scale variations of the AES given in [Algebraic Aspects of the Advanced Encryption Standard], see http://www.sagemath.org/doc/reference/sage/crypto/mq/sr.html#modulesage.crypto.mq.sr).
Definition in file SboxAnalysis.hpp.