my boolean problem
Henning Meyer
may be this is the wrong newsgroup, but I have the following problem.
Given are a',b',m and n. All numbers are 32-bit ints.
Now I know:
t = ( (a >> n) XOR b) AND m
a' = a XOR (t << n)
b' = b XOR t
Is there a chance to find a and b, that fit the equations?
How do I revert a boolean equation in general?
Henning Meyer
Charles Krug
> Hello,
>
> may be this is the wrong newsgroup, but I have the following problem.
> Given are a',b',m and n. All numbers are 32-bit ints.
Boolean algebra has only two values. Once you have two bits, you aren't doing
boolean algebra any longer, though you MAY be doing Boolean operations on the
indivitual bits.
>
> Now I know:
>
> t = ( (a >> n) XOR b) AND m
> a' = a XOR (t << n)
> b' = b XOR t
>
> Is there a chance to find a and b, that fit the equations?
> How do I revert a boolean equation in general?
In general, you're aren't doing Boolean algebra, as you have entities with
values other than zero and one.
What you ARE doing is a HS conventional algebra, with a few additional
operators with odd properties. OTOH, just as a first approximation, 32-bit
integers appear to be a group under XOR, so there ya go . . .
Couple simplifications:
a >> n is the same as a/(2^n)
t << n is the same as t*(2^n).
Were I in your shoes, I'd avoid dealing with shifted values for as long as I
could.
Somewhere in your text (meaning go buy one if you dont' have one) is a table
showing the properties of Boolean operations. Conveniently, so long as you're
only doing bitwise operations, you can pretend you're doing Boolean
operations.
Check your identities. DeMorgan's law is probably going to be useful.
Rick Nungester
>
> a >> n is the same as a/(2^n)
No, there is an "integer part" involved, and the issue of sign extension
needs to be addressed. "32 bit int" doesn't specify signed or unsigned,
and "a>>n" fills in the high-order bits differently for signed/unsigned
with MS bit = 1.
> t << n is the same as t*(2^n).
No, since there are no restrictions on t and overflow is possible.
Rick
Raphael Jolly
One method you could try is using groebner bases with polynomial
coefficients in Z/2Z. I have implemented such an algorithm in meditor
( http://raphael.jolly.free.fr/meditor ). Here is how your problem is
handled:
(I take x = a >> n and y = t << n ; the calculations are on 4 bit for
simplicity.)
groebner({x[0]+a[0]*n0+a[1]*n1+a[2]*n2+a[3]*n3+a[3]*n4,
x[1]+a[1]*n0+a[2]*n1+a[3]*n2+a[3]*n3+a[3]*n4,
x[2]+a[2]*n0+a[3]*n1+a[3]*n2+a[3]*n3+a[3]*n4,
x[3]+a[3]*n0+a[3]*n1+a[3]*n2+a[3]*n3+a[3]*n4,
y[3]+t[3]*n0+t[2]*n1+t[1]*n2+t[0]*n3,
y[2]+t[2]*n0+t[1]*n1+t[0]*n2,
y[1]+t[1]*n0+t[0]*n1,
y[0]+t[0]*n0,
n0+(n[0]+1)*(n[1]+1)*(n[2]+1),
n1+(n[0])*(n[1]+1)*(n[2]+1),
n2+(n[0]+1)*(n[1])*(n[2]+1),
n3+(n[0])*(n[1])*(n[2]+1),
n4+(n[2]),
t[0]+(x[0]+b[0])*m[0],
t[1]+(x[1]+b[1])*m[1],
t[2]+(x[2]+b[2])*m[2],
t[3]+(x[3]+b[3])*m[3],
a'[0]+a[0]+y[0],
a'[1]+a[1]+y[1],
a'[2]+a[2]+y[2],
a'[3]+a[3]+y[3],
b'[0]+b[0]+t[0],
b'[1]+b[1]+t[1],
b'[2]+b[2]+t[2],
b'[3]+b[3]+t[3]},
{n[0],n[1],n[2],
a'[0],a'[1],a'[2],a'[3],
b'[0],b'[1],b'[2],b'[3],
m[0],m[1],m[2],m[3],
a[0],a[1],a[2],a[3],
b[0],b[1],b[2],b[3],
x[0],x[1],x[2],x[3],
y[0],y[1],y[2],y[3],
t[0],t[1],t[2],t[3],
n0,n1,n2,n3,n4},0,2)
There are 25 equations in 36 unknowns, which means the solution is
11-dimensional. After groebner elimination you should get ni,t,y,x,b,a
in function of m,b',a',n.
However this method isn't very efficient : I didn't have enough memory
(250M) to carry even this simplified version of your problem. What you
can do is:
1-try the above computation with enough RAM (and processing power (or
time !))
2-replace your parameters with numerical values
3-try other Groebner implementations
Note : there are lots of computations that reduce into boolean
computations : multiplication of big primes, cryptography, etc. and
being able to revert them using a general algorithm like the above
would be interesting, if we could make it efficient enough.
Carl Devore
On 22 Jul 2002, Raphael Jolly wrote:
> "Henning Meyer" <Hennin...@web.de> wrote in message news:<aglv00$ra3$1...@news.online.de>...
> > Given are a',b',m and n. All numbers are 32-bit ints.
> > t = ( (a >> n) XOR b) AND m
> > a' = a XOR (t << n)
> > b' = b XOR t
> >
> > Is there a chance to find a and b, that fit the equations?
> > How do I revert a boolean equation in general?
>
> One method you could try is using groebner bases with polynomial
> coefficients in Z/2Z. I have implemented such an algorithm in meditor
> ( http://raphael.jolly.free.fr/meditor ).
> ....
> However this method isn't very efficient : I didn't have enough memory
> (250M) to carry even this simplified version of your problem. What you
> can do is:
> 1-try the above computation with enough RAM (and processing power (or
> time !))
> 2-replace your parameters with numerical values
> 3-try other Groebner implementations
The free CAS Singular (http://www.singular.uni-kl.de) claims to have the
fastest Groebner basis computations over finite fields. I'd be curious to
see how it fares with this problem.
Singular is available for download for Windows, Unix, and MacIntosh.
This is the most polished an easiest installation I've ever done for a
free software download. The Windows version comes with the Cygwin Unix
emulator, bash shell, Xemacs, etc. The package runs stand-alone or in
Xemacs.
A book is available about the system, _A Singular Introduction to
Commutative Algebra_ by G.-M. Greuel and G. Pfister (Springer Verlag,
2002).
Daniel Lichtblau
I wrote up some Mathematica code based on Raphael Jolly's idea to use
Groebner bases modulo 2. I did not actually follow how he obtained his
polynomials; some are cubic whereas mine are all linear or quadratic.
Possibly we interpreted the '>>' and '<<' operators differently. I am
assuming they indicate shifts although I am not certain whether they
are to be taken as linear (shift in zeros at the appropriate end) or
circular.
Following Jolly's approach, I also work with these integers as lists
of bits. The idea is to set up a bunch of polynomials given m, n,
aprime, and bprime, then solve for a and b. These are returned as
lists. I treat n as an ordinary integer and the other inputs as lists.
The code below assumes, probably incorrectly, that the shifts are
circular. I'll say more about this presently. Another caveat I should
note is that I have not checked any of this for correctness.
invert[m_, n_, aprime_, bprime_] := Module[
{len=Length[aprime], t, a, aa, b, bb, vars, gb},
a = Array[aa, len];
b = Array[bb, len];
t = (RotateRight[a,n] + b) * m;
polys = Join[aprime+a+RotateLeft[t,n], b+t+bprime];
vars = Join[a,b];
gb = GroebnerBasis[polys, vars, Modulus->2];
PolynomialMod[{a,b} /. Solve[gb==0, vars], 2]
]
Here is a random example with bit strings of length 32 and a rotation
length of 7.
In[84]:= len = 32;
In[85]:= n = 7;
In[91]:= InputForm[m = Table[Random[Integer], {len}]]
Out[91]//InputForm=
{1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0,
1, 1,
1, 0, 1, 1, 1, 1, 0}
In[92]:= InputForm[aprime = Table[Random[Integer], {len}]]
Out[92]//InputForm=
{0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1,
1, 1,
1, 1, 0, 1, 0, 1, 0}
In[93]:= InputForm[bprime = Table[Random[Integer], {len}]]
Out[93]//InputForm=
{1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1,
0, 1,
1, 0, 1, 1, 1, 0, 0}
In[94]:= InputForm[Timing[invert[m, n, aprime, bprime]]]
Out[94]//InputForm=
{0.05999999999999995*Second,
{{{0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1,
1, 0,
1, 1, 1, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0,
0, 0, 1,
0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0}}}}
So what we have is not a closed form of "solution" but rather a
black-box sort of solver: given appropriate inputs it will return the
result. Actually it is a bit more general in that it can return a
result in terms of symbolic m, aprime, and bprime (but not n).
In[96]:= InputForm[Timing[invert[Array[mm,len], n, Array[ap,len],
Array[bp,len]]]]
Out[96]//InputForm=
{0.27999999999999986*Second,
{{{ap[1] + ap[1]*mm[8] + bp[8]*mm[8], ap[2] + ap[2]*mm[9] +
bp[9]*mm[9],
ap[3] + ap[3]*mm[10] + bp[10]*mm[10], ap[4] + ap[4]*mm[11] +
bp[11]*mm[11], ap[5] + ap[5]*mm[12] + bp[12]*mm[12],
ap[6] + ap[6]*mm[13] + bp[13]*mm[13], ap[7] + ap[7]*mm[14] +
bp[14]*mm[14], ap[8] + ap[8]*mm[15] + bp[15]*mm[15],
ap[9] + ap[9]*mm[16] + bp[16]*mm[16], ap[10] + ap[10]*mm[17] +
bp[17]*mm[17], ap[11] + ap[11]*mm[18] + bp[18]*mm[18],
ap[12] + ap[12]*mm[19] + bp[19]*mm[19], ap[13] + ap[13]*mm[20] +
bp[20]*mm[20], ap[14] + ap[14]*mm[21] + bp[21]*mm[21],
ap[15] + ap[15]*mm[22] + bp[22]*mm[22], ap[16] + ap[16]*mm[23] +
bp[23]*mm[23], ap[17] + ap[17]*mm[24] + bp[24]*mm[24],
ap[18] + ap[18]*mm[25] + bp[25]*mm[25], ap[19] + ap[19]*mm[26] +
bp[26]*mm[26], ap[20] + ap[20]*mm[27] + bp[27]*mm[27],
ap[21] + ap[21]*mm[28] + bp[28]*mm[28], ap[22] + ap[22]*mm[29] +
bp[29]*mm[29], ap[23] + ap[23]*mm[30] + bp[30]*mm[30],
ap[24] + ap[24]*mm[31] + bp[31]*mm[31], ap[25] + ap[25]*mm[32] +
bp[32]*mm[32], ap[26] + ap[26]*mm[1] + bp[1]*mm[1],
ap[27] + ap[27]*mm[2] + bp[2]*mm[2], ap[28] + ap[28]*mm[3] +
bp[3]*mm[3],
ap[29] + ap[29]*mm[4] + bp[4]*mm[4], ap[30] + ap[30]*mm[5] +
bp[5]*mm[5],
ap[31] + ap[31]*mm[6] + bp[6]*mm[6], ap[32] + ap[32]*mm[7] +
bp[7]*mm[7]}, {bp[1] + ap[26]*mm[1] + bp[1]*mm[1],
bp[2] + ap[27]*mm[2] + bp[2]*mm[2], bp[3] + ap[28]*mm[3] +
bp[3]*mm[3],
bp[4] + ap[29]*mm[4] + bp[4]*mm[4], bp[5] + ap[30]*mm[5] +
bp[5]*mm[5],
bp[6] + ap[31]*mm[6] + bp[6]*mm[6], bp[7] + ap[32]*mm[7] +
bp[7]*mm[7],
bp[8] + ap[1]*mm[8] + bp[8]*mm[8], bp[9] + ap[2]*mm[9] +
bp[9]*mm[9],
bp[10] + ap[3]*mm[10] + bp[10]*mm[10], bp[11] + ap[4]*mm[11] +
bp[11]*mm[11], bp[12] + ap[5]*mm[12] + bp[12]*mm[12],
bp[13] + ap[6]*mm[13] + bp[13]*mm[13], bp[14] + ap[7]*mm[14] +
bp[14]*mm[14], bp[15] + ap[8]*mm[15] + bp[15]*mm[15],
bp[16] + ap[9]*mm[16] + bp[16]*mm[16], bp[17] + ap[10]*mm[17] +
bp[17]*mm[17], bp[18] + ap[11]*mm[18] + bp[18]*mm[18],
bp[19] + ap[12]*mm[19] + bp[19]*mm[19], bp[20] + ap[13]*mm[20] +
bp[20]*mm[20], bp[21] + ap[14]*mm[21] + bp[21]*mm[21],
bp[22] + ap[15]*mm[22] + bp[22]*mm[22], bp[23] + ap[16]*mm[23] +
bp[23]*mm[23], bp[24] + ap[17]*mm[24] + bp[24]*mm[24],
bp[25] + ap[18]*mm[25] + bp[25]*mm[25], bp[26] + ap[19]*mm[26] +
bp[26]*mm[26], bp[27] + ap[20]*mm[27] + bp[27]*mm[27],
bp[28] + ap[21]*mm[28] + bp[28]*mm[28], bp[29] + ap[22]*mm[29] +
bp[29]*mm[29], bp[30] + ap[23]*mm[30] + bp[30]*mm[30],
bp[31] + ap[24]*mm[31] + bp[31]*mm[31], bp[32] + ap[25]*mm[32] +
bp[32]*mm[32]}}}}
If you instead wish to use linear shifts with zeros entering at the
ends, the code below can be used.
shiftLeft[ll_, n_] :=
Drop[RotateLeft[PadRight[ll, Length[ll]+n], n], -n]
shiftRight[ll_, n_] :=
Drop[RotateRight[PadLeft[ll, Length[ll]+n], n], n]
invert2[m_, n_, aprime_, bprime_] := Module[
{len=Length[aprime], t, a, aa, b, bb, vars, gb},
a = Array[aa, len];
b = Array[bb, len];
t = (shiftRight[a,n] + b) * m;
polys = Join[aprime+a+shiftLeft[t,n], b+t+bprime];
vars = Join[a,b];
gb = GroebnerBasis[polys, vars, Modulus->2];
PolynomialMod[{a,b} /. Solve[gb==0, vars], 2]
]
Note that now you cannot solve for all elements in general. For
example, say n is 1 and the first (that is, leftmost) element of m is
1. Regardless of whether the first element of b is 0 or 1, the first
element of bprime must be 0. What this means is you will not be able
to recover the value of the first element of b. In the result from
invert2 this will show up (in the "symbolic" m, aprime, bprime case)
as a division by 1+m[1], as that denominator vanishes mod 2 when m[1]
is 1.
Other such boolean problems might be tackled by similar means to that
above. By appropriate mapping of logical operators to boolean algebra
and use of defining equations such as var^2+var==0 (which rather
conveniently I did not need above) you can perhaps code up something
to handle much more general sets of equations.
Daniel Lichtblau
Wolfram Research
Raphael Jolly
On 3 Aug 2002 11:53:55 -0700, Daniel Lichtblau wrote:
>raphae...@free.fr (Raphael Jolly) wrote:
>> "Henning Meyer" <Hennin...@web.de> wrote:
>> > Hello,
>> >
>> > may be this is the wrong newsgroup, but I have the following problem.
>> > Given are a',b',m and n. All numbers are 32-bit ints.
>> >
>> > Now I know:
>> >
>> > t = ( (a >> n) XOR b) AND m
>> > a' = a XOR (t << n)
>> > b' = b XOR t
>> >
>> > Is there a chance to find a and b, that fit the equations?
>> > How do I revert a boolean equation in general?
[...]
>I wrote up some Mathematica code based on Raphael Jolly's idea to use
>Groebner bases modulo 2. I did not actually follow how he obtained his
>polynomials; some are cubic whereas mine are all linear or quadratic.
>Possibly we interpreted the '>>' and '<<' operators differently. I am
>assuming they indicate shifts although I am not certain whether they
>are to be taken as linear (shift in zeros at the appropriate end) or
>circular.
Maybe it will be clearer if I stress the fact that for instance in:
x[0]+a[0]*n0+a[1]*n1+a[2]*n2+a[3]*n3+a[3]*n4,
...
n0+(n[0]+1)*(n[1]+1)*(n[2]+1),
n1+(n[0])*(n[1]+1)*(n[2]+1),
...
, n0=1 iff n[2],n[1],n[0] = 0,0,0
n1=1 iff " " " = 0,0,1
, etc.
I took the shift operators to have the meaning they have in C : linear,
with sign-extension in the case of '>>'.
[...]
>So what we have is not a closed form of "solution" but rather a
>black-box sort of solver: given appropriate inputs it will return the
>result. Actually it is a bit more general in that it can return a
>result in terms of symbolic m, aprime, and bprime (but not n).
[...]
>Note that now you cannot solve for all elements in general. For
>example, say n is 1 and the first (that is, leftmost) element of m is
>1. Regardless of whether the first element of b is 0 or 1, the first
>element of bprime must be 0. What this means is you will not be able
>to recover the value of the first element of b. In the result from
>invert2 this will show up (in the "symbolic" m, aprime, bprime case)
>as a division by 1+m[1], as that denominator vanishes mod 2 when m[1]
>is 1.
[...]
I succeeded to compute the "closed form" of the 2bits version.
It took 3 hours in meditor on my Pentium 133. The result is a
33 equations, 21 unknowns Groebner basis, which takes 10Kb.
Here are expressions for a[0], a[1], b[0], b[1]:
{a'[0]+a'[0]*m[0]+n[0]*a'[0]*m[0]+n[1]*a'[0]*m[0]+n[0]*n[1]*a'[0]*m[0]+b'[0]*m[0]+n[0]*b'[0]*m[0]+n[1]*b'[0]*m[0]+n[0]*n[1]*b'[0]*m[0]+a[0],
a'[1]+n[0]*a'[1]+n[1]*a'[1]+n[0]*n[1]*a'[1]+a'[1]*m[1]+n[0]*a'[1]*m[1]+n[1]*a'[1]*m[1]+n[0]*n[1]*a'[1]*m[1]+b'[1]*m[1]+n[0]*b'[1]*m[1]+n[1]*b'[1]*m[1]+n[0]*n[1]*b'[1]*m[1]+a[1]+n[0]*a[1]+n[1]*a[1]+n[0]*n[1]*a[1],
b'[0]+n[0]*b'[0]+n[1]*b'[0]+n[0]*n[1]*b'[0]+a'[0]*m[0]+n[0]*a'[0]*m[0]+n[1]*a'[0]*m[0]+n[0]*n[1]*a'[0]*m[0]+b'[0]*m[0]+n[0]*b'[0]*m[0]+n[1]*b'[0]*m[0]+n[0]*n[1]*b'[0]*m[0]+b[0]+n[0]*b[0]+n[1]*b[0]+n[0]*n[1]*b[0],
a'[1]*b'[1]*m[0]+n[0]*a'[1]*b'[1]*m[0]+a'[1]*b'[0]*b'[1]*m[0]+n[0]*a'[1]*b'[0]*b'[1]*m[0]+a'[1]*b'[1]*m[0]*b[1]+n[0]*a'[1]*b'[1]*m[0]*b[1]+a'[1]*b'[0]*b'[1]*m[0]*b[1]+n[0]*a'[1]*b'[0]*b'[1]*m[0]*b[1]}
The other equations (not reproduced) include constraints to be
verified for the problem to have a solution : as you pointed out,
this is not always the case. I think these constraints are
responsible for the great complexity of the problem, and that
the answer is indeed to work with numerical values, using
a "black-box" algorithm as you did : in that case the Groebner
basis is 0-dimensional and much easier to compute.
The best would be to know the intent of the original poster...