Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

3 views

Skip to first unread message

Jul 12, 2002, 3:03:30 AM7/12/02

to

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?

Henning Meyer

Jul 15, 2002, 9:29:39 AM7/15/02

to

On Fri, 12 Jul 2002 09:03:30 +0200, 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.

> 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.

Jul 15, 2002, 10:08:23 PM7/15/02

to

> Couple simplifications:

>

> a >> n is the same as a/(2^n)

>

> 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

Jul 22, 2002, 11:08:35 AM7/22/02

to

"Henning Meyer" <Hennin...@web.de> wrote in message news:<aglv00$ra3$1...@news.online.de>...

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.

Jul 23, 2002, 3:10:01 AM7/23/02

to Raphael Jolly

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).

Aug 3, 2002, 2:53:55 PM8/3/02

to

raphae...@free.fr (Raphael Jolly) wrote in message news:<23f716b5.02072...@posting.google.com>...

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

Aug 4, 2002, 4:26:15 PM8/4/02

to

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...

0 new messages

Search

Clear search

Close search

Google apps

Main menu