ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 05 Nov 2018 00:28:09 +0100Solving underdetermined system of quadratic equations over GF(2)https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/Hi folks!
All of the following operations are done over GF(2).
I want introduce you to my problem with a little example: I have two algebraic expressions of the keystream bits Z0 and Z1 of a stream cipher. The algebraic expressions just consist of key bits (key bits are named with X). For example:
Z0=X56+X43+X31+X10+X4+X2+X1
Z1=X57+X44+X32+X11+X5+X3+X2
In this little example we have, m = 2 = number_of_equations and n = 13 = number_of_unknown_variables. If I would now have konwledge about the Z0 and Z1 bit (e.g. Z0 = Z1 = 0), it must be possible to gain knowledge about key bits again by solving these underdetermined system of equations. My normal approach would be guessing 11 of the 13 and try to solve equation system for the unknown 2. If the system has a solution I know that could be the right answer.
At the moment my sage script says the following:
F=GF(2) //Define the Galois Field
M=Matrix(F, [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1], [1,0, 1, 0, 1,0, 1, 0, 1, 0, 1, 1, 0]]) //Define the equation system
v = vector(F, (0,0)) //Define vector for solve_right()
M.solve_right(v)
My abstract algorithm is the following to make it more clear:
for all 2^13 possible values:
1. Guess variables till m = n.
2. Try to solve the system. If system has a solution, save it.
How would get the guessing of the variables realized in a smart way (matrice syntax or symbolic syntax?), that automatically all possible values of the variables will be guessed and what would be the normal approach for that problem?
A little syntax example will be appreciated!
Greetings
ChewieThu, 05 Jul 2018 17:21:25 +0200https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/Comment by tmonteil for <p>Hi folks!</p>
<p>All of the following operations are done over GF(2).</p>
<p>I want introduce you to my problem with a little example: I have two algebraic expressions of the keystream bits Z0 and Z1 of a stream cipher. The algebraic expressions just consist of key bits (key bits are named with X). For example:</p>
<pre><code>Z0=X56+X43+X31+X10+X4+X2+X1
Z1=X57+X44+X32+X11+X5+X3+X2
</code></pre>
<p>In this little example we have, m = 2 = number_of_equations and n = 13 = number_of_unknown_variables. If I would now have konwledge about the Z0 and Z1 bit (e.g. Z0 = Z1 = 0), it must be possible to gain knowledge about key bits again by solving these underdetermined system of equations. My normal approach would be guessing 11 of the 13 and try to solve equation system for the unknown 2. If the system has a solution I know that could be the right answer.</p>
<p>At the moment my sage script says the following:</p>
<pre><code>F=GF(2) //Define the Galois Field
M=Matrix(F, [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1], [1,0, 1, 0, 1,0, 1, 0, 1, 0, 1, 1, 0]]) //Define the equation system
v = vector(F, (0,0)) //Define vector for solve_right()
M.solve_right(v)
</code></pre>
<p>My abstract algorithm is the following to make it more clear:</p>
<p>for all 2^13 possible values:</p>
<ol>
<li>Guess variables till m = n.</li>
<li>Try to solve the system. If system has a solution, save it.</li>
</ol>
<p>How would get the guessing of the variables realized in a smart way (matrice syntax or symbolic syntax?), that automatically all possible values of the variables will be guessed and what would be the normal approach for that problem?</p>
<p>A little syntax example will be appreciated!</p>
<p>Greetings
Chewie</p>
https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/?comment=42835#post-id-42835Could you please provide the actual equtions, not the toy one, which are linear ?Fri, 06 Jul 2018 00:03:09 +0200https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/?comment=42835#post-id-42835Comment by Chewie for <p>Hi folks!</p>
<p>All of the following operations are done over GF(2).</p>
<p>I want introduce you to my problem with a little example: I have two algebraic expressions of the keystream bits Z0 and Z1 of a stream cipher. The algebraic expressions just consist of key bits (key bits are named with X). For example:</p>
<pre><code>Z0=X56+X43+X31+X10+X4+X2+X1
Z1=X57+X44+X32+X11+X5+X3+X2
</code></pre>
<p>In this little example we have, m = 2 = number_of_equations and n = 13 = number_of_unknown_variables. If I would now have konwledge about the Z0 and Z1 bit (e.g. Z0 = Z1 = 0), it must be possible to gain knowledge about key bits again by solving these underdetermined system of equations. My normal approach would be guessing 11 of the 13 and try to solve equation system for the unknown 2. If the system has a solution I know that could be the right answer.</p>
<p>At the moment my sage script says the following:</p>
<pre><code>F=GF(2) //Define the Galois Field
M=Matrix(F, [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1], [1,0, 1, 0, 1,0, 1, 0, 1, 0, 1, 1, 0]]) //Define the equation system
v = vector(F, (0,0)) //Define vector for solve_right()
M.solve_right(v)
</code></pre>
<p>My abstract algorithm is the following to make it more clear:</p>
<p>for all 2^13 possible values:</p>
<ol>
<li>Guess variables till m = n.</li>
<li>Try to solve the system. If system has a solution, save it.</li>
</ol>
<p>How would get the guessing of the variables realized in a smart way (matrice syntax or symbolic syntax?), that automatically all possible values of the variables will be guessed and what would be the normal approach for that problem?</p>
<p>A little syntax example will be appreciated!</p>
<p>Greetings
Chewie</p>
https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/?comment=42840#post-id-42840I just wanted to make it as simple as it could be at first with just two linear equations. If that works, it shouldn't be that hard to expand the working example. That was the reason, why I just posted the first two linear equations of the system. With my guessing approach, I think it should be also possible to find a possible solution but just considering the first two equations.
Greetings ChewieFri, 06 Jul 2018 10:49:00 +0200https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/?comment=42840#post-id-42840Comment by Chewie for <p>Hi folks!</p>
<p>All of the following operations are done over GF(2).</p>
<p>I want introduce you to my problem with a little example: I have two algebraic expressions of the keystream bits Z0 and Z1 of a stream cipher. The algebraic expressions just consist of key bits (key bits are named with X). For example:</p>
<pre><code>Z0=X56+X43+X31+X10+X4+X2+X1
Z1=X57+X44+X32+X11+X5+X3+X2
</code></pre>
<p>In this little example we have, m = 2 = number_of_equations and n = 13 = number_of_unknown_variables. If I would now have konwledge about the Z0 and Z1 bit (e.g. Z0 = Z1 = 0), it must be possible to gain knowledge about key bits again by solving these underdetermined system of equations. My normal approach would be guessing 11 of the 13 and try to solve equation system for the unknown 2. If the system has a solution I know that could be the right answer.</p>
<p>At the moment my sage script says the following:</p>
<pre><code>F=GF(2) //Define the Galois Field
M=Matrix(F, [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1], [1,0, 1, 0, 1,0, 1, 0, 1, 0, 1, 1, 0]]) //Define the equation system
v = vector(F, (0,0)) //Define vector for solve_right()
M.solve_right(v)
</code></pre>
<p>My abstract algorithm is the following to make it more clear:</p>
<p>for all 2^13 possible values:</p>
<ol>
<li>Guess variables till m = n.</li>
<li>Try to solve the system. If system has a solution, save it.</li>
</ol>
<p>How would get the guessing of the variables realized in a smart way (matrice syntax or symbolic syntax?), that automatically all possible values of the variables will be guessed and what would be the normal approach for that problem?</p>
<p>A little syntax example will be appreciated!</p>
<p>Greetings
Chewie</p>
https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/?comment=42839#post-id-42839Hi, these are the real first 17 keystream bit equations,
m: 17
n_s (Number variables single occurences): 38
n_m (Number variables multiple occurences): 31
n_o (Number of variables overall): 69
Z0=X56+X43+X31+X10+X4+X2+X1
Z1=X57+X44+X32+X11+X5+X3+X2
Z2=X58+X45+X33+X12+X6+X4+X3
Z3=X59+X46+X34+X13+X7+X5+X4
Z4=X60+X47+X35+X14+X8+X6+X5
Z5=X61+X48+X36+X15+X9+X7+X6
Z6=X62+X49+X37+X16+X10+X8+X7
Z7=X63+X50+X38+X17+X11+X9+X8
Z8=X64+X51+X39+X18+X12+X10+X9
Z9=X65+X52+X40+X19+X13+X11+X10
Z10=X66+X53+X41+X20+X14+X12+X11
Z11=X67+X54+X42+X21+X15+X13+X12
Z12=X68+X55+X43+X22+X16+X14+X13
Z13=X69+X56+X44+X23+X17+X15+X14
Z14=X70+X57+X45+X24+X18+X16+X15
Z15=X71+X58+X46+X25+X19+X17+X16
Z16=X79+X72+X59+X47+X26+X20+X18+X17+X56*X79+X43*X79+X31*X79+X10*X79+X4*X79+X2*X79+X1*X79
Possible to solve with the guessing?Fri, 06 Jul 2018 10:35:38 +0200https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/?comment=42839#post-id-42839Answer by slelievre for <p>Hi folks!</p>
<p>All of the following operations are done over GF(2).</p>
<p>I want introduce you to my problem with a little example: I have two algebraic expressions of the keystream bits Z0 and Z1 of a stream cipher. The algebraic expressions just consist of key bits (key bits are named with X). For example:</p>
<pre><code>Z0=X56+X43+X31+X10+X4+X2+X1
Z1=X57+X44+X32+X11+X5+X3+X2
</code></pre>
<p>In this little example we have, m = 2 = number_of_equations and n = 13 = number_of_unknown_variables. If I would now have konwledge about the Z0 and Z1 bit (e.g. Z0 = Z1 = 0), it must be possible to gain knowledge about key bits again by solving these underdetermined system of equations. My normal approach would be guessing 11 of the 13 and try to solve equation system for the unknown 2. If the system has a solution I know that could be the right answer.</p>
<p>At the moment my sage script says the following:</p>
<pre><code>F=GF(2) //Define the Galois Field
M=Matrix(F, [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1], [1,0, 1, 0, 1,0, 1, 0, 1, 0, 1, 1, 0]]) //Define the equation system
v = vector(F, (0,0)) //Define vector for solve_right()
M.solve_right(v)
</code></pre>
<p>My abstract algorithm is the following to make it more clear:</p>
<p>for all 2^13 possible values:</p>
<ol>
<li>Guess variables till m = n.</li>
<li>Try to solve the system. If system has a solution, save it.</li>
</ol>
<p>How would get the guessing of the variables realized in a smart way (matrice syntax or symbolic syntax?), that automatically all possible values of the variables will be guessed and what would be the normal approach for that problem?</p>
<p>A little syntax example will be appreciated!</p>
<p>Greetings
Chewie</p>
https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/?answer=44187#post-id-44187It might be possible to use [libFES - Fast Exhaustive Search for Polynomial Systems over $\mathbb{F}_2$](http://www.lifl.fr/~bouillag/fes).Mon, 05 Nov 2018 00:28:09 +0100https://ask.sagemath.org/question/42833/solving-underdetermined-system-of-quadratic-equations-over-gf2/?answer=44187#post-id-44187