Tools for
Experimental Algebraic Cryptanalysis
The content of this page is provided without any warranty. It
is subject to copyright and does contain some efficient and
innovative algorithms and data structures that were never published
but are fully [or sometimes tentatively] implemented.
Thirdparty tools will also be published here.
P.S. Support can not be guaranteed.
Here is our
AX64.exe program that allows to know a rank (number
of linearly independent equations) of a system of polynomial equations
over GF(2).
Under windows open cmd.exe, type "cd
c:\CurentPathWhereTheseProgramsAre\" and type the following command:
 AX64.exe 417 [/deg2] Filename.extension [/quiet]
[/up3] . Legend:
 /degX means the degree of the equations is X.
Faster code is used for lower degrees.
 /upY is applied to systems of degree 2
: they are expanded by XL to degree Y before
their rank is computed.
This can be used for studying the ElimLin and XL algorithms.
"ax64.exe 4000" can be used to replace "XL64.exe" (previously known as "XL0.exe" which was
discontinued) used with the same option /upY implements the full XL
algorithm and much more, see below.
 [/quiet]
makes it more
discrete, and in particular avoids popup windows.
Now to do the same modulo P, we use the following command:
 AX64.exe 47717 Filename.extension [/quiet] .
This can be slow. The first line of the file should be like "modulo
67". Legend:
 [/quiet]
makes it more
discrete, and in particular avoids popup windows.
About Programs Provided Here.
Some tools
found here are fairly simple, some are more complex.
All have been implemented to handle
very large but quite sparse systems of Boolean
polynomial equations on a PC with insufficient
memory. Most computer algebra systems are actually
totally incapable of manipulating systems of equations
with comparable type and size on a PC. Not to say solving them.
These programs will only work if some Microsoft ms*.dll
files are present on your PC. These files are not provided
here but can be found on most PCs, they can copied by hand to
your windows/system32/ directory, but really the
simplest way to install them all at once it
to install Microsoft Visual Studio.
Programs are experimental versions with no guarantee nor
support. They produce a lot of spare intermediate and log
files, that can be discarded later. They generate popup windows if
they find a solution, the option /quiet
disables it. If this notepad solution window is not closed,
this will prevent other programs from running in the same directory.
Programs use heavily the CPU, as well as the OS core, and in order to
manage memory that is never sufficient, they continuously use the disk
drives of the computer. They may use much more RAM than showed
by Windows task manager, the showings of the Windows task manager are
simply not accurate. The system should have at least 1 Gigabyte of RAM
per running process (e.g. 4 Giga for a quadcore PC). They will work
better if a particularly fast extra hard drive (or two) are attached to
the computer with a special letter that could be i: or x: or y: or all
of these:. Backup your data regularly: some disk drives will
develop faults after a few months of intensive usage.
These tools are a mix of various code developed by
Nicolas T. Courtois at various occasions. To the best of our knowledge
they are free of any third party intellectual property rights. The exe
files (closedsource code programs) can
be used freely if the user acknowledges that
they use ready tools developed by Nicolas T. Courtois
AND links to this page. Source code is a private property of
the author and is not intended to be made public ever.
Basic Equation Solving Toolbox
 ElimLin over GF(P)
Here is the AX64.exe
and also AXEL.exe
program that allows to solve systems of equations by the
famous ElimLin method. Both programs work more or less the
same, except that AXEL is for 32bit windows version and it can
allocate less memory. The first line of the file should be like "modulo
67" or start with comments like "//P=hex encoding of 67". Command line reference:
 AX64.exe 47747 [/maxmpz256] [/up3 /up4 /xsl]
[/maxmpz256] Filename.extension [/quiet] .
Legend:
 /quiet
makes it more
discrete, and in particular it avoids popup windows.
 /up3 expands to degree 3, only if quadratic initially.
 /xsl expands monomials XSLstyle to degree 4, only if
quadratic initially.
 /maxmpz256
faster code for
integers up to 256 bits, less malloc calls.
Basic Equation Solving Toolbox
 ElimLin over GF(2^n)
We
use the same AX64.exe
The first line of the file should be like "//P=ireeducible polynomial"
for example "//P=0x020000000000000000000000000201" which has 113 bits. Command line reference:

AX64.exe 47742 [/maxmpz256] [/up3 /up4 /xsl] [/maxmpz256] [/skipnormal]
Filename.extension [/quiet] .
Legend:
 /quiet
makes it more
discrete, and in particular it avoids popup windows.
 /up3 expands to degree 3, only if quadratic initially.
 /xsl expands monomials XSLstyle to degree 4, only if
quadratic initially.
 /maxmpz256
faster code for
integers up to 256 bits, less malloc calls.
Basic Equation Solving Toolbox
 ElimLin in GF(2)
Here is the same AX64.exe
which can also handle ElimLin over GF(2). This has a lot more useful
options. If and after it stops working the option /gtp is called by default, see
below. Some options will only work if extra files are present on the
PC. Command line reference:
 AX64.exe 4000 [/degX] Filename.extension [/quiet]
[/up3][/dense] [/alt] [/alt2] [/retract] [/inert] [/fullg] [/xsl or
/xsm or /xsn] . Legend:
 /degX means the degree of the equations is X
. Memoryefficient up to degree 4 . Works
for any degree.
 /upY
is applied to systems of degree2:
they are expanded by XL to degreeY
before ElimLin. This can be applied to any system of degree 2
and implements a powerful version of the XL
algorithm, which should be called XLElimLinGTP algorithm, where
Elimlin and it it fails, the "geometric generalised T' method
over GF(2) ", do
replace the final step of the XL algorithm by something, as it seems,
much more powerful than any other known version of the XL
algorithm.
 /quiet
makes it more
discrete, and in particular it avoids popup windows.
 /dense
is another very
different implementation, for dense systems.
 /alt is an STL implementation, works for any degree but
VERY bad in RAM usage.
 /alt2 is a new implementation, slow but also works over
fields like GF(2^n) , well almost.
 /retract
is a normal verison
but does retract from all the substitutions and at the end write the
initial system plus all the linear equations it could find.
 /inert
is an implementation
close in the spirit to F4 algorithm, with substituion being replaced by
adding suitable products of linear equations by monomials [but it
avoids doing it for all monomials in a somewhat intelligent
way, so in presence of sparsity it could still be
actually better than standard F4].
 /fullg
is a basic
implementation, though the default version [without /fullg] is in fact
faster due to a trick that we do not describe here.
 /singular
will convert any
system of equations to singular format and will try to call Singular if
properly installed under cygwin.
 /magma
will convert any
system of equations to Magma format but will not try to call Magma.
 /xsl
/deg2 this the [in]famous
XSL algorithm. Works only for degree 2 and expands to degree
4. Then it does apply ElimLin. It is a bad algorithm, but
whoever told you it doesn't work, they lied to you. There are two other
versions
/xsm and /xsn that apply ElimLin first.
 /tp
is a simple but generalized T' method, don't use it, /gtp is
better.

/gtp is the default option, no need to call it,
geometric generalised T' method over GF(2),
a slow but clever and powerful algorithm, never published, and
which is called through GTP.exe
that must be in the same directory. Has effect only after ElimLin stops working
and called afterwards.

/gugtf
is a sort of guess and determine, simple and slow, generalized but not
geometric T' method. Not so good except for rare systems that collapse
after a few guesses.
 /gtpl8 is a dedicated generalized T' method with lifting
from GF(2) to GF(8) , or even
to any of GF(2^Z)
with option /gtplZ.
Another very interesting algorithm, never published.
Java tool for DEEP INSPECTION of equations generated with ElimLin over
GF(2)
in Cryptalanalysis of Block Ciphers
Here is the program DeepElimlin1.5SNAPSHOT.jar.
It is a Java tool developed by Guangyan Song [and Nicolas Courtois].
Command line reference:
 java.exe jar DeepElimlin1.5SNAPSHOT.jar
Filename.extension
Inside
the file it expects a list of linear equations with spaces between
sections generated as stages r0,r1 etc of ElimLin. Currently it makes
strong assumptions about variable numbering, and was designed for Simon
block cipher primarily.
Here is one example how to use it for block cipher
Simon:
 We need Simon.exe
file which is doumented here. We
also need to make sure that ax64.exe
and DeepElimlin1.4SNAPSHOT.jar
are in the same
directory.
 Then we type in Windows command
prompt:
 Simon.exe 8 /fixk40 /ins4 /xl0 [/cp]
 Finally we
type:
 java.exe jar
DeepElimlin1.5SNAPSHOT.jar accumulated_lin.txt 8.
BTW. if the java installation directory
was the same as ours = C:\\Program
Files\\Java\\jre1.8.0_91\\bin\\java.exe, this will actually
happen
automatically.
Requirements: Sun Java must be installed on
a PC under Windows x64. Java.exe should be
accessible through system path.
Remarks:
Another way to invoke this tool is to run ax64.exe
4040 8 after some ElimLin run. It will automatically
import the results.
What can this tool do?
 It will produce XX new
files which show what happens inside ElimLin algorithm.
 It will also attempt to
simulate what happens for K<4 (less instances), e.g. K=2 4 6 8
etc...
 This
tool was primarily designed for deep
inspection of equations generated during ElimLin attack on Simon.
 It
recognizes automatically from the variable names where round inside
the cipher they belong to.
 It
should work for other ciphers but it may
be necessary to rename variables so that the tool can parse the round
number correctly [e.g. a number 1..8 encoded as sth_001_005 for example
which means variable 5 in round 1].
 The
tool pays special attention to
variables which occur in the middle of encryption and less attention to
those from the first or final round.
Basic Equation
Solving Toolbox  Conversion to
SAT Techniques (and Semaev Algorithms)
The
same AX64.exe
and also AXEL.exe
program allows to solve systems of equations with SAT
solvers if and only if the option
/sat is specified. A plethora
of solving and conversion methods are implemented.
Command line reference for
using ax64.exe as an entry point for playing with SAT solvers and
conversion:
 AX64.exe 4000 [/degX] [/zoo or
/sat /bard or nothing or ...] Filename.extension [/quiet]
[/up3] [/minisat or /go or ...] [/learn1] [/dnf] . Legend:

option /degX
should be considered as obligatory to specify. It m
eans the maximum
degree of the algebraic polynomials equations is X
. Memoryefficient up to degree 4 . A
few options work for any degree.

the syntax
ax64.exe 4000 /zooXX /deg2 Filename.ext is by far the
simplest and the most powerful way of running the program on a
powerful multicore PC with XX CPUs. It will run XX different things in
parallel, selected from the options of ax64.exe listed
below. Warning: this program will create several
subdirectories of the current directory and will create lots
of files there. There is no cleanup and it can get quite messy.
 is /sat
is the default way of solving systems by sat solvers and activates sat
solvers. Alternative options are /sau,
/sav, /saw , /sax,
/say which are
versions that mix linear algebra, ElimLin and T' methods prior to
applying SAT solvers. (Use at own risk, all these variants are nice but
most of the time just totally useless as systems can be solved quickly
by other means.)

/dontsat
is
a hack which is normally used for debugging, in conjunction with /sat . If
used the program does not run any SAT solver at all. Useful in
some cases, if we want to just get then .cnf file generated, or/and use
an external solver, or if we want to replace the
solution obtained with a different one, and do further steps
such as converting the solution back to an algebraic system, which can
then be examined more easily with the orginal variable naming.
 /upY is applied to systems of degree 2
: they are expanded by XL to degree Y before it is solved with SAT solvers.

/learn1 produces a bigger system via assumptions on key
bits, only interesting of certain variable names start with "k_".
Slow implementation.
 /dnf creates an extra file XXX.dnf . The dnf file is a ready set of
"symbols" separated by double line breaks, suitable for Semaevtype
AgreeingGluing methods.
 It also generates a
helper file .resolve, that contains the dictionnary between the
variables names in cnf and dnf files, and their actual text names in
other files.
 /quiet
makes it more
discrete, and in particular it avoids popup windows.

/bard will
use the BCJ = BardCourtoisJefferson CNF to ANF
converter written in Java by Gregory Bard, folowing this frequently
cited paper .This option of ax64.exe works only if the
necessary Java files are on the PC with special fixed directories, and
compiled...it is fast, and a working Windows distibution can be
dowloaded here&
(it requires a careful manual installation).

/likebard
is another builtin BCJ =
BardCourtoisJefferson CNF to ANF
converter which replaces /bard
and is quite similar in spirit, though implementation is not identical
and much slower for now. It does not require any extra files.
 Another major ANF to CNF
conversion option is /nobard which was
sometimes the default recenlty but not when CryptoMiniSat is used.
This /nobard
option is also known as Local Interpolation or LI in the litterature,
for example in this
paper or on slide 40 here.
 We also have /nobardXX
which has some specific rarely used options.
 /xsplit3
is an option to split XORs into shorter ones, normally in
/nobard
XORs of length up to about 6 are encoded as clauses of length
6. Produces shorter clauses but adds extra variables.
 /noconv
is a hack, the conversion is skipped but the program assumes it worked
and produced the .cnf and /resolve file it should have produced, and
runs nest step such as running the sat solver and converting back.

/minisat,
will try first to use the sat solver
MiniSat 2.0.6. compiled under cygwin only if it is
present under the path c:\cygwin\sat\minisat20.exe exactly.
Otherwise it will try to use
MiniSat2.exe compiled under windows which needs to
be present in the current directory.
 option /minisat114 uses even
an
older version 1.14 if present
under c:\cygwin\sat\MiniSat_v1.14_cygwin exactly.
 /timeout2000
will make the SAT solver task to be aborted/killed after 2000 seconds.

/minisat206
and /minisat207 and
/minisat220 will
try to use a specific version like
MiniSat206.exe or
MiniSat207.exe or
MiniSat220.exe exactly, and only if present. It
seems that the older versions are frequently
faster. The version 206 is currently also our default
one (as used with the above option /minisat ). The source
files, but only for versions 207 and 220, can be found at the
MiniSat page . We have developed our own modified versions
in order to make them compile under Visual Studio 9 (version
2008 and not earlier).

/minisat64220
and /minisat64206 are
two 64bit versions of MiniSat to try. Requires one
of the x64 versions Windows. Also requires the
corresponding compiled file
MiniSatx64v220.exe or
MiniSatx64v206.exe to be present in the current
directory. Will not work under Windows 32 bit. The key feature is that they can allocate a lot of
memory, much more than 2 gigabytes, and wll not crash due to
the lack of memory.

/cryptominisat292
and /cryptominisat64292
are two recent versions (2011) of the famous CryptoMiniSat by Mate Soos
The second being 64bit. It is sometimes better and can be for example
3x faster than MiniSat on UNSAT instances, but it is general not very
good at solving satisifiable instances. It requires a corresponding
compiled exe file and dll which are bundled here for convenience: CryptoMiniSat2_allx32.zip
or CryptoMiniSat2_allx64.zip
to be present in the current directory. Under Windows 64 bit both will
work but only one at a time, depending which dll is present (they have
the same name but they are different dlls).
 option /elite uses a preprocessor,
the famous SatElite, the source code of which can be also found at the
MiniSat page . Apparently not needed for versions MiniSat
2.0. and above, SatElite gives very good results combined with
some other SAT solvers. It requires the file SatElite2005.exe to
be present in the current directory. There are many cases when Elite
produces and empty set and it not useful at all, but there are also
cases when the encoding of our problem as SAT is greatly improved by
SatElite and it is very useful to solve problems efficiently. A simple
alternative is /unitpre.
 option /unitpre uses a simple
homegrown preprocessor based on unit propagation, mostly meant to
eliminate redundant variables and find some shorter clauses, currently
based on unit propagation version 3 also known as /unitt, subject to
change. Currently it does not rename variables and does
not produce a .map file. Known to give very competitive timings in
conjunction with /nobard
and MiniSat.
 option /unitr before a SAT solver it
uses a very simple builtin unit propagation checker. Not very fast but
displays interesting details about what it does: find units of
size 1, eliminate them then check for equivalent variables due to
clauses of size 2 generated and eliminate these equivalent variables.
Has no effect other than informative. Will run the usual SAT solver
anyway, unless
option
/unitr /dontsat
is specified. Or unless the option /unitpre is used .
Then the unit propagation in another version is really used as a
preprocessor.

option /unitr
/dontsat is already a standalone builtin SAT
solver. Beta version: for now it can detect UNSAT correctly
but will not claim that the system is SAT.
 option /units
/dontsat is a slightly better unit propagation
checker also able to detect that when k_56 OR V1 and also
1+k_56 OR V1, means that V1 must be true.
 option
/unitt /dontsat is an
even better unit propagation checker also able to detect that
when k_56 OR C2 and also 1+k_56 OR C2, this means that C2 must
be true where C2 is a clause of length 2. Visibly slower
though.
 /pico will use PicoSat instead of MiniSat. It
is usually many times slower but it never allocates too much
memory and will therefore sometimes works where MiniSat will
allocate too much RAM and fail. The file
picostat.exe needs to be in the same directory.
 /hoX
is an exact parallel SAT solver with no assumptions and
massive learning and restricting the choice of the branching
variable. X should be equal to the number of CPUs on your
computer. It works by creating separate processes that run for a
limited time. The general philosophy used is to split the task
through restricting the choice of the branching variable and
then periodically stop and aggregate things learned
during the process. Unhappily due to the lack of memory many longer
clauses learnt during the process will have to be
discarded. Only short ones are kept. Global stats for the
aggregated file are displayed. Works only if the
file minisatgo.exe
is in the same directory.
 /timeoutZZ
makes
the sat solver time out after ZZ seconds
 /goX
[/depY] [/timeoutZZ] is a stochastic parallel SAT solver
focusing on SAT and using Minist 206 by default. Here
we split the task through adding extra Y assumptions.
Here if Y>1 one UNSAT means nothing, and another random choice
is attempted instead. No crosstask support for learning
except that choices of Y variables leading to a contradiction are
learned indeed. BTW. /depY
does NOT need to be
specified, and will be decreased
automatically if contradictions are easy to find.
 /koX [/depY] [/timeoutZZ] is the same
but only variables starting with k_i are used for assumptions.
Much better for converted cryptanalysis problems.
 moreover if we use /soos or /soosX and the option
/bard
is not active, a special version of the ANFtoCNF converter
will be used, which will produce NATIVE XORs in the cnf file (lines
starting with x). This cnf file can only be used with some very special
SAT solvers such as Crypto_Mini_Sat developed by Mate Soos.
 /soos1
uses the solver minisat_gauss.exe which
is compiled version 1 by Mate Soos and needs to be in the same
directory.
 /soos2 uses the solver minisat_gauss2.exe which
is compiled version 2 by Mate Soos and needs to be in the same
directory. Source files can be found at
Mate Soos page .

an
extra option /submons is
available only with
/likebard and
/soosX .
It will add submonomials for all existing monomials,
and some extra clauses to relate monomials with their
submonomials, this making solving maybe easier, or not, we
start with a bigger CNF system and there is no evidence this
mechanism makes solving easier, on the contrary.

another
weird option /vexp2 which
in theory adds some extra variables to have more sparsity... but in
many cases most or all of the new variables will be
ignored by MiniSat right away (unless they are transformed by
equivalences).
 another extra option /wyucz is
available only with
/likebard and
/soosX
. It will add
some extra relations between existing monomials mostly for monomials
having a common submonomial, making solving maybe easier, and
the conversion for sure much slower.
 there is a very special
solver triggered by the option /forall100 in
this solver, all the variables starting with x or y are treated as
formal variables. All the variables startign with abc as
constants. All the remaining as functions of formal variables.
Currently not compatible with most other options above, so rather use
this option in isolation.
A Tool for Sillicon Optimization / Multiplicative
Complexity for Sboxes
This
is a unique piece of software which has no equivalent elsewhere. It
takes as input an Sbox and outputs circuit with low multiplicative
complexity or a silicon optimization.
Done with our ax64.exe
program.
Input = truth table of the Sbox,
for example {12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2}
ax64.exe 11117777 target
{12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2}
[/cryptominisat64292] [/freedomXX] [[/goX /depY /timeoutZZ]].
Legend:
 Command 11117777
can be replaced by
111177XX
 Where XX=14 to allow ONLY NAND gates.
 We
can also have XX=03 for AND/OR/XOR/NOT (a.k.a. bitslice),
XX=13
for AND/OR/XOR, XX=10 for AND/NAND/NOT and XX=05 for
gates
being AND/OR/XOR/NAND/NOR/NXOR/NOT
 The integer target
is how many multiplications/gates should be used, e.g. 4.
 XOR/NOR gates are typically not counted.
 Input and output size should be recognised
automatically.
 Here /cryptominisat64292
is some version of CryptoMiniSat by Mate Soos. Can be
found here for example, see CryptoMiniSat2_allx64.zip
bundle which files must be copied to current directory including the
dll. Works under most versions of Windows x64.
 /freedomXX
is an option which regulates extra variables used in the computation
process, it does not affect satisfiability/the existence of the
solution but makes that there exists several solutions (SAT solver
finds only one).
 /goX [/depY] [/timeoutZZ]
is a
variant using a stochastic parallel SAT solver
focusing on SAT and using Minisat 206 by default, use this file
MiniSat206.exe.
References:
 Nicolas T. Courtois, Daniel Hulme, Theodosis Mourouzis:
Multiplicative Complexity and Solving Generalized Brent Equations With
SAT Solvers.
In COMPUTATION TOOLS 2012, pp. 2227, 22 July 2012, full paper vailable
here.
Best Paper Award.
 Here are extended slides
by Courtois et al. about Multiplicative Complexity.
 Here is an excellent 2016 followup paper
which uses the same methodology.
 Here is the PhD thesis
by Theodosis Mourouzis.
 Nicolas T. Courtois, Daniel Hulme, Theodosis Mourouzis:
Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis.
In SHARCS 2012,Washington, 2012,in page 179 here.
 Nicolas T. Courtois, Daniel Hulme and Theodosis Mourouzis:
Solving Circuit Optimisation Problems in Cryptography and
Cryptanalysis.
In electronic proceedings of 2nd IMA Conference Mathematics in Defence
2011,
short 6page version is found here. A
longer version is available here.
 Nicolas T. Courtois, Gregory V. Bard and Daniel Hulme:
A New GeneralPurpose Method to Multiply 3x3 Matrices Using Only 23
Multiplications, .
At arxiv.  Here are some related works: this
paper and this
paper.
 Here are some examples of equations which have been obtained with some wellchosen options of this program for GOST and other ciphers.
 Om Bhallamudi (with help from MariaBristena Oprisanu and Varnavas Papaioannou):
Tool for Software Algebraic attacks on T310 block cipher, see our codegen.py
program.
This
software is a combination of several programs and we advocate to run it
under any version of Windows 64bit with Python 2.7 x64 installed. The
basic reference is: python codegen.py Nr /fix230 /insX /xl /sat
/T310set26.  A tool for Differential Cryptanalysis (DC) for T310 block cipher by Matteo Scarlata, here.
 ax64 also contains a lot of T310 code.
Advanced Research and Experimental Tools.
Here is an old GTP.exe
program (may use AX64 4161 instead).
GTP.exe allows to solve systems of equations by "The
Geometric Generalised T' Method" by Courtois. This is
an advanced geometric algorithm, never published, for
finding extra linearly independent equations at a given
degree, which would normally be found by Gröbner
bases techniques, but at a higher degree(!) with much higher
memory and with much higher
complexity. So in practice, this algorithm has no
competitors in producing such equations on current
computers. It somewhat an amazing tool albeit, the
current implementation is very slow, waiting to be improved later. It
should be considered as a research
prototype for an early detection of exploitable algebraic
vulnerabilities, and is a very powerful tool in this respect
(the number of linearly independent
equations typically grows and grows).
An additional second advanced T' method (but
not yet in a 'geometric flavour', so less advanced) is also included.
It starts by lifting of arbitrary equations
over GF(2)
to GF(2^k)
. See option /gtplX
option described below.
Command line reference for GTP:
 GTP.exe
[/degX] Filename.extension [/quiet][/tp] [
/tp or /gtplZ or
/gugtf] [/up3]
. Legend:
 /degX means the degree of the equations is X
. Faster code is used for lower degrees, but for now only for the
degree 2 the program is satisfactory, higher degrees are
not fully implemented (should still work at "half steam" at degree 3
and 4).
 /tp should revert to the most basic old T' method.
 /gugtf is a fancy guess and determine T' method.
 /gtplZ  will take a
quadratic system over GF(2) and consider it as a system over GF(2^Z) , and do heuristic guesses and apply the
unpublished "Generalized T' method over GF(q) ", instead of
the default "systematic geometric GTP method over
GF(2)".
 /upY when applied to systems of degree 2: they are
expanded by XL to degree Y
before GTP is called.
 /quiet
makes it more
discrete, and in particular avoids popup windows.
Examples of
Systems of Equations to Solve.
How to Write
the Equations.

Write variable names like A_3_5_2 or maybe like BC[4][1] which
is not the preferred form but should work too.
 Always use * sign, for
example A_3_5_2*A_1_2_1.
 Use line breaks to signify a
new equation.
 Use k_XXX where XXX is a
number of key variables. Variables with such names should have
special treatment and will be the last to be eliminated, but this only
possible if they are distinguished by their names starting by k.
 Avoid variable names starting
with the letter "l".
 Do not hesitate to add extra
variables if this makes the equations more sparse or improves clarity,
for example instead of writing
X_2_4=1+k_34, write X_2_4=P_2_4+k_34 and P_2_4=1, where P_2_4 is a bit
of the plaintext.
 Try to make ALL equations of
low degree, preferably 2, 3 or 4, avoid having the slighest monomial of
degree more than 4. The algebraic degree of arbitrary Boolean
functions can be easily reduced by introducing extra variables.

When converting files with polynomial algebraic equations (ANF) to SAT
problems (CNF) with ax64.exe, native OR clauses are also allowed in the
source text file, for example one can write a line of the form: OR
x23 A_3_5_2 1+A_1_2_1. They are
not coverted but just copied to the file.
 For
coding of Sboxes see these examples for GOST and other ciphers. Here iare our slides about Multiplicative Complexity and our paper on MC.
 In a sperate file write the
assignments of ALL the variables, for debugging and
guessthenalgebraic attacks.
Tool For
Point Splitting and Experimentation on EC Codes.
Here is our ec2decomp.exe
program.
 ec2decomp.exe
... . Some desciption can be found here.
 /sub23cubic is a special option which mixes MQ2 and MQ3
equations...
 /cubic is applied to systems of degree 2
: they are expanded by XL to degree Y before
their rank is computed.
Maintained by Nicolas T. Courtois
Last updated in July
2016.