Math question...

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Math question...

Postposted on Sat Feb 06, 2010 10:53 pm

So apparently my brain isn't working well today... ...and it's been many years since I went through my linear algebra class. I am trying to find the inverse the following transform.

L(m)=m ^ (m << 6) ^ (m << 10)

Where ^ is XOR and << is rotate left.

What's sad is even my Google fu is failing. If someone wants to flat out give the answer, fine, but I'd rather and explanation or a pointer to an explanation.

--SS
SecretSquirrel
Gerbil Jedi
Gold subscriber
 
 
Posts: 1716
Joined: Tue Jan 01, 2002 7:00 pm
Location: The Colony, TX (Dallas suburb)

Re: Math question...

Postposted on Sat Feb 06, 2010 11:01 pm

You have the value for L(m) and you want to find the value for m?

Can you explain what you mean by 'rotate left'? Is this like an integer bit-shift, or like a clockwise rotation?
wibeasley
Gerbil Elite
Gold subscriber
 
 
Posts: 952
Joined: Sat Mar 29, 2008 3:19 pm
Location: Norman OK

Re: Math question...

Postposted on Sun Feb 07, 2010 12:26 am

You may not be able to -- XOR is generally not onto or one-to-one.

ie, x^y = 1111 works with x = 1010, y = 0101 or x = 1100, y = 0011 or x = 1001, y = 0110.

To even try and say more than that I'd also need to know what you mean by "rotate left."
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals
SNM
Emperor Gerbilius I
 
Posts: 6206
Joined: Fri Dec 30, 2005 10:37 am

Re: Math question...

Postposted on Sun Feb 07, 2010 12:59 am

For the rotate left, m << 1 shifts all bits left one position with the MSB becoming the LSB. 1100b << 1 = 1001b.

Yes, you have the value of L(m) and need to solve for m. This transform is from a substitution, permutation block cypher. In order to implement the decryption, I have to work out the inverse of the SP block and hence the inverse of this transform.

--SS
SecretSquirrel
Gerbil Jedi
Gold subscriber
 
 
Posts: 1716
Joined: Tue Jan 01, 2002 7:00 pm
Location: The Colony, TX (Dallas suburb)

Re: Math question...

Postposted on Sun Feb 07, 2010 2:45 am

I have the same concern as SNM with inversing the XOR; you're sure there's a unique solution? I hoping there's something with the three shifts (where the first m is shifted zero positions) that reduces the number of possibilities so there is a unique solution. How many bits does m have?

Maybe I'm missing something you've figured out already. It may help if you explain how you're casting this as a linear algebra problem.
wibeasley
Gerbil Elite
Gold subscriber
 
 
Posts: 952
Joined: Sat Mar 29, 2008 3:19 pm
Location: Norman OK

Re: Math question...

Postposted on Sun Feb 07, 2010 3:17 am

Are there any constraints on the input? 32-bit input? Is there a possibility that some of the most/least significant bits are known to be zero?

Oh, wait, I bet it's 16-bit input. So the left-most bit in the original number is XORed with the bit in position seven (from left) and position 11 to get the output's bit. So:
(ry = result bit position y, numerals stand for the bit position from left, 1-based indexing)
r1 = 1 ^ 7 ^ 11
r2 = 2 ^ 8 ^ 12
r3 = 3 ^ 9 ^ 13
r4 = 4 ^ 10 ^ 14
r5 = 5 ^ 11 ^ 15
r6 = 6 ^ 12 ^ 16
r7 = 7 ^ 13 ^ 1
r8 = 8 ^ 14 ^ 2
r9 = 9 ^ 15 ^ 3
r10 = 10 ^ 16 ^ 4
r11 = 11 ^ 1 ^ 5
r12 = 12 ^ 2 ^ 6
r13 = 13 ^ 3 ^ 7
r14 = 14 ^ 4 ^ 8
r15 = 15 ^ 5 ^ 9
r16 = 16 ^ 6 ^ 10

Now XOR is the inverse of itself, so to find the actual value of bit one we need to XOR r1 with the actual values of bits 7 and 11.
1 = r1 ^ 7 ^ 11
1 = r1 ^ r13 ^ 13 ^ 3 ^ 11
1 = r1 ^ r13 ^ r3 ^ 9 ^ 11
1 = r1 ^ r13 ^ r3 ^ r15 ^ 15 ^ 5 ^ 11
Hey look, 15 ^ 5 ^ 11 = r5.
1 = r1 ^ r13 ^ r3 ^ r15 ^ r5.
I just got all these by looking.

Wash, rinse, and repeat. There is almost certainly a sequence of bit shifts and XORs on the result that will have the same outcome, but I can't summon up the math to prove it directly right now, if I ever knew it. But once you work out all the equations you can probably come up with them anyway, and they will then be immediately obvious and intuitive. ;)

EDIT: Wow, this stuff becomes a lot more fun once out of college. I think I just spent an hour on that. :oops:
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals
SNM
Emperor Gerbilius I
 
Posts: 6206
Joined: Fri Dec 30, 2005 10:37 am

Re: Math question...

Postposted on Sun Feb 07, 2010 3:46 am

wibeasley wrote:I have the same concern as SNM with inversing the XOR; you're sure there's a unique solution? I hoping there's something with the three shifts (where the first m is shifted zero positions) that reduces the number of possibilities so there is a unique solution. How many bits does m have?

Maybe I'm missing something you've figured out already. It may help if you explain how you're casting this as a linear algebra problem.


It turns into a system of linear equations (that should be independent if I didn't miss something) with n equations for an n-bit number (m0m1...m_n) with each equation of the following form:
m0^6^10,
m1^7^11,
m2^8^12,
...
m_n-10^n-4^m_n
...
m_n^5^9
= L(m)
where n is the number of bits and m is the value (I left off the 'm' prefix after the first as a shorthand)

Hope that helps (and that I didn't go crazy somewhere on my math).

edit: SNM's solution is the kind I went with first, but here's the 'linear algebra' approach :p
arsenhazzard
Gerbil First Class
 
Posts: 169
Joined: Thu Oct 18, 2007 4:30 pm

Re: Math question...

Postposted on Sun Feb 07, 2010 4:14 am

arsenhazzard wrote:edit: SNM's solution is the kind I went with first, but here's the 'linear algebra' approach :p

Same approach, I just solved it for a specific n and didn't dress it up in generalized language/notation because I didn't realize they would be independent in the general case, being a bit slow. :)
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals
SNM
Emperor Gerbilius I
 
Posts: 6206
Joined: Fri Dec 30, 2005 10:37 am

Re: Math question...

Postposted on Sun Feb 07, 2010 10:16 am

It is 16 bits wide. Here is the whole block cypher.

Image

K1 through K4 are 16 bit keys which are disjoint subsets of a larger 64 bit key .
SecretSquirrel
Gerbil Jedi
Gold subscriber
 
 
Posts: 1716
Joined: Tue Jan 01, 2002 7:00 pm
Location: The Colony, TX (Dallas suburb)

Re: Math question...

Postposted on Sun Feb 07, 2010 2:47 pm

That's cool, I wish I knew more about cryptology. Thanks guys for spelling out the linear equations. I'm curious. If the length of m was an arbitrary/unsepcified number of bits, does anyone have a feeling if a unique solution would exist? If it was longer than 16 bits, you'd need more XORs and shifts, right?
wibeasley
Gerbil Elite
Gold subscriber
 
 
Posts: 952
Joined: Sat Mar 29, 2008 3:19 pm
Location: Norman OK

Re: Math question...

Postposted on Sun Feb 07, 2010 5:54 pm

I'm in the middle a software implementation of the large encryption algorithm of which that cypher is a part. There is a very interesting job opening here in town for a system engineer/programming type. It is what my degree is in and I really enjoy it, but unfortunately my professional resume is all IT type stuff. So I figure I need to "go the extra mile" to get notice. Once I have it working in software (C), I'm going to due an implementation in Verilog.

BTW, I feel like a real idiot now as the inverse transform was actually printed in one of the papers I'm reading. For those that are interested...

L(m) = m ^ ( m << 6 ) ^ ( m << 10 )
L'(m) = m' ^ ( m' << 2 ) ^ ( m' << 4 ) ^ ( m' << 12 ) ^ ( m' << 14 )

--SS
SecretSquirrel
Gerbil Jedi
Gold subscriber
 
 
Posts: 1716
Joined: Tue Jan 01, 2002 7:00 pm
Location: The Colony, TX (Dallas suburb)

Re: Math question...

Postposted on Sun Feb 07, 2010 5:58 pm

SecretSquirrel wrote:I'm in the middle a software implementation of the large encryption algorithm of which that cypher is a part. There is a very interesting job opening here in town for a system engineer/programming type. It is what my degree is in and I really enjoy it, but unfortunately my professional resume is all IT type stuff. So I figure I need to "go the extra mile" to get notice. Once I have it working in software (C), I'm going to due an implementation in Verilog.

BTW, I feel like a real idiot now as the inverse transform was actually printed in one of the papers I'm reading. For those that are interested...

L(m) = m ^ ( m << 6 ) ^ ( m << 10 )
L'(m) = m' ^ ( m' << 2 ) ^ ( m' << 4 ) ^ ( m' << 12 ) ^ ( m' << 14 )

--SS


I am surprised that has a unique solution. I would have expected it to be irreversible like the result of a modulus operation because of the XOR operator.
Disclaimer: I over-analyze everything, so try not to be offended if I over-analyze something you wrote.
Shining Arcanine
Gerbil Jedi
 
Posts: 1717
Joined: Wed Jun 11, 2003 11:30 am

Re: Math question...

Postposted on Sun Feb 07, 2010 7:21 pm

Shining Arcanine wrote:I am surprised that has a unique solution. I would have expected it to be irreversible like the result of a modulus operation because of the XOR operator.

It's because it's doing two XORs on the original number, just displaced. There's no data destruction -- otherwise it wouldn't be a very good cipher! ;)

Did the paper give you a proof or anything, Squirrel? I saw that pattern in the equation I solved but figured there had to be a more elegant derivation of it.
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals
SNM
Emperor Gerbilius I
 
Posts: 6206
Joined: Fri Dec 30, 2005 10:37 am

Re: Math question...

Postposted on Sun Feb 07, 2010 9:59 pm

Nope. No proof. The paper is an analysis of the larger algorithm so the implementation discussion is purely to show what is being talked about. Now I just have to figure out how to undo the XOR at the beginning of the block.

--SS
SecretSquirrel
Gerbil Jedi
Gold subscriber
 
 
Posts: 1716
Joined: Tue Jan 01, 2002 7:00 pm
Location: The Colony, TX (Dallas suburb)

Re: Math question...

Postposted on Sat Dec 04, 2010 3:55 am

Wow, this is pretty old but I'm bored... :-)

I don't think any cipher can destroy any data as one of the basics is f'( f(x) ) = x (must be invertible; wouldn't be useful if even intended receiver can't figure out what the secret message was) and you can't reconstruct original data from nothing... (at the simplest, what if you just burn the secret message? safe but again not very useful).

The system of equations were getting somewhere but doesn't seem to state lower 6-bits of m and m' are actually the same and that is what make this very easy to solve (0-base indexing, mi = ith bit of m):

Code: Select all
L(m) = m ^ ( m << 6 ) ^ ( m << 10 )
L(m) = ... m11 m10 m9 m8 m7 m6 m5 m4 m3 m2 m1 m0
     ^ ... m5  m4  m3 m2 m1 m0 0  0  0  0   0  0
     ^ ... m1  m0  0  0  0  0  0  0  0  0   0  0


m'0 = m0 ^ 0 ^ 0 = m0 (or m0 = m'0)
m'1 = m1 ^ 0 ^ 0 = m1
m'2 = m2 ^ 0 ^ 0 = m2
m'3 = m3 ^ 0 ^ 0 = m3
m'4 = m4 ^ 0 ^ 0 = m4
m'5 = m5 ^ 0 ^ 0 = m5

m'6 = m6 ^ m0 ^ 0 = m6 ^ m0 (or m6 = m'6 ^ m0 = m'6 ^ m'0)
m'7 = m7 ^ m1 ^ 0 = m7 ^ m1
m'8 = m8 ^ m2 ^ 0 = m8 ^ m2
m'9 = m9 ^ m3 ^ 0 = m9 ^ m3

So to get up to 10-bits of original value:
Code: Select all
L'(m') = m' ^ (m' << 6)
L'(m') = ... m'11 m'10 m'9 m'8 m'7 m'6 m'5 m'4 m'3 m'2 m'1 m'0
       ^ ... m'5  m'4  m'3 m'2 m'1 m'0 0   0   0   0   0   0


m'10 = m10 ^ m4 ^ m0 (or m10 = m'10 ^ m4 ^ m0 = m'10 ^ m'4 ^ m'0)
m'11 = m11 ^ m5 ^ m1

To get up to 12-bits of original value:
Code: Select all
L'(m') = m' ^ (m' << 6) ^ (m' << 10)
L'(m') = ... m'11 m'10 m'9 m'8 m'7 m'6 m'5 m'4 m'3 m'2 m'1 m'0
       ^ ... m'5  m'4  m'3 m'2 m'1 m'0 0   0   0   0   0   0
       ^ ... m'1  m'0  0   0   0   0   0   0   0   0   0   0


m'12 = m12 ^ m6 ^ m2 (or m12 = m'12 ^ m6 ^ m2 = m'12 ^ m'6 ^ m'0 ^ m'2; m6 = m'6 ^ m'0 so we need an extra m'0 term)
m'13 = m13 ^ m7 ^ m3
m'14 = m14 ^ m8 ^ m4
m'15 = m15 ^ m9 ^ m5 // after this, we'll need to XOR more shifted terms since once again m6 will need to be derived, should be fine for 16-bits with maybe & 0xFFFF for safe measure

To get up to 16-bits of original value:
Code: Select all
L'(m') = m' ^ (m' << 6) ^ (m' << 10) ^ (m' << 12)
L'(m') = ... m'12 m'11 m'10 m'9 m'8 m'7 m'6 m'5 m'4 m'3 m'2 m'1 m'0
       ^ ... m'6  m'5  m'4  m'3 m'2 m'1 m'0 0   0   0   0   0   0
       ^ ... m'2  m'1  m'0  0   0   0   0   0   0   0   0   0   0
       ^ ... m'0  0    0    0   0   0   0   0   0   0   0   0   0
Lans
Gerbil In Training
 
Posts: 7
Joined: Thu Jun 05, 2008 7:06 pm

Re: Math question...

Postposted on Sat Dec 04, 2010 11:34 am

Lans wrote:I don't think any cipher can destroy any data as one of the basics is f'( f(x) ) = x (must be invertible; wouldn't be useful if even intended receiver can't figure out what the secret message was) and you can't reconstruct original data from nothing... (at the simplest, what if you just burn the secret message? safe but again not very useful).


At a glance, it looked like a hash function, which lacks the property of bijection.
Disclaimer: I over-analyze everything, so try not to be offended if I over-analyze something you wrote.
Shining Arcanine
Gerbil Jedi
 
Posts: 1717
Joined: Wed Jun 11, 2003 11:30 am

Re: Math question...

Postposted on Sat Dec 04, 2010 12:37 pm

I am not sure if it looked like a hash function as I didn't see a variable length string to fixed length output...

Anyways why I bother posting to this thread is, in addition to be being bored, at a glance I didn't buy the inverse function:

L(m) = m ^ ( m << 6 ) ^ ( m << 10 )
L'(m) = m' ^ ( m' << 2 ) ^ ( m' << 4 ) ^ ( m' << 12 ) ^ ( m' << 14 )

Namely, I see (m & 0x3F) ^ 0 ^ 0 based only left shifts of 6 and 10 so (m' << 2) and (m' << 4) looks very odd. Lets try:

L(15) = 15 ^ (15 << 6) ^ (15 << 10) = 15 ^ 960 ^ 15360 = 16335
L'(16335) = 16335 ^ (16335 << 2) ^ (16335 << 4) ^ (16335 << 12) ^ (16335 << 14) = 16335 ^ 65340 ^ 261360 ^ 66908160 ^ 267632640 = 202116099 and if you only take the lower 16-bits, 3,075

So lets try what I proposed:
L'(m') = m' ^ (m' << 6) ^ (m' << 10) ^ (m' << 12)
M'(16335) = 16335 ^ 1045440 ^ 16727040 ^ 66908160 = 51118095 (lower 16-bits is indeed 15)
Lans
Gerbil In Training
 
Posts: 7
Joined: Thu Jun 05, 2008 7:06 pm

Re: Math question...

Postposted on Sat Dec 04, 2010 1:45 pm

Shining Arcanine wrote:At a glance, it looked like a hash function, which lacks the property of bijection.

Not necessarily; XOR preserves information, and (assuming that L(m) has the same number of bits as m) there very well could be a 1-to-1 mapping of values. Hash functions generally reduce the number of bits by a some large factor; that does not appear to be the case here.
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37705
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Math question...

Postposted on Fri Dec 10, 2010 11:01 am

just brew it! wrote:
Shining Arcanine wrote:At a glance, it looked like a hash function, which lacks the property of bijection.

Not necessarily; XOR preserves information, and (assuming that L(m) has the same number of bits as m) there very well could be a 1-to-1 mapping of values. Hash functions generally reduce the number of bits by a some large factor; that does not appear to be the case here.


<A> XOR <A> = 0, for all <A> in W.

If I do <A> XOR <A> for some <A> and tell you the result, can you tell me which <A> I used?

Now that I think about it, there is a contradiction in saying that a ^ (a <<n) = 0 where n > 0 and a is non-zero, which can be used to prove that the result zero only occurs when a = 0, but I neither had the time to consider it then nor do I have the time to do it now that have considered it. It also would need to be generalized to repeated XORs and it is not clear to me that such a thing is possible in all cases.
Disclaimer: I over-analyze everything, so try not to be offended if I over-analyze something you wrote.
Shining Arcanine
Gerbil Jedi
 
Posts: 1717
Joined: Wed Jun 11, 2003 11:30 am

Re: Math question...

Postposted on Fri Dec 10, 2010 11:17 am

<A> XOR <A> is not a hash function either, since (as you've pointed out) it always results in zero.

<A> XOR <C> (where C is a known constant) preserves information.

As another interesting example, consider the swapping of two variables without the use of a temporary -- the following sequence will swap the contents of the variables <A> and <B>, and would not be possible if XOR destroyed information:
Code: Select all
<A> := <A> XOR <B>
<B> := <A> XOR <B>
<A> := <A> XOR <B>
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37705
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Math question...

Postposted on Fri Dec 10, 2010 12:23 pm

Shining Arcanine wrote:Now that I think about it, there is a contradiction in saying that a ^ (a <<n) = 0 where n > 0 and a is non-zero, which can be used to prove that the result zero only occurs when a = 0, but I neither had the time to consider it then nor do I have the time to do it now that have considered it. It also would need to be generalized to repeated XORs and it is not clear to me that such a thing is possible in all cases.

Does anybody even know what this paragraph means?
Let's try out a = 10101010b and n = 2.
a << 2 = 10101010
a ^ (a<<2) = 10101010 ^ 10101010
a ^ (a<<2) = 0.

But I'm not sure what this even applies to in the discussion above, is anybody else?
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals
SNM
Emperor Gerbilius I
 
Posts: 6206
Joined: Fri Dec 30, 2005 10:37 am

Re: Math question...

Postposted on Sat Dec 11, 2010 9:53 am

just brew it! wrote:<A> XOR <A> is not a hash function either, since (as you've pointed out) it always results in zero.

<A> XOR <C> (where C is a known constant) preserves information.

As another interesting example, consider the swapping of two variables without the use of a temporary -- the following sequence will swap the contents of the variables <A> and <B>, and would not be possible if XOR destroyed information:
Code: Select all
<A> := <A> XOR <B>
<B> := <A> XOR <B>
<A> := <A> XOR <B>


<A> XOR <A> is a hash function; there is no logical law that states that hash functions must have desirable properties. See the description at Wikipedia:
A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array (cf. associative array).


http://en.wikipedia.org/wiki/Hash_function

As for XOR, under certain circumstances, XOR destroys information. Under other circumstances, it preserves information. It is like asking whether or not e^(at) and e^(bt) are linearly independent. They are linearly dependent when a = b and linearly independent in all other cases.
Disclaimer: I over-analyze everything, so try not to be offended if I over-analyze something you wrote.
Shining Arcanine
Gerbil Jedi
 
Posts: 1717
Joined: Wed Jun 11, 2003 11:30 am

Re: Math question...

Postposted on Sat Dec 11, 2010 10:40 am

SNM wrote:
Shining Arcanine wrote:Now that I think about it, there is a contradiction in saying that a ^ (a <<n) = 0 where n > 0 and a is non-zero, which can be used to prove that the result zero only occurs when a = 0,

Let's try out a = 10101010b and n = 2.
a << 2 = 10101010
a ^ (a<<2) = 10101010 ^ 10101010
a ^ (a<<2) = 0.

I suspect a confusion between the different meanings of the << operator. In the original question it has been defined as Rotate Left so a << 2 = 10101010, however in C it is defined as Shift Left so a << 2 = 1010101000 which if stored in an 8 bit identifier would be a << 2 = 10101000.
notfred
Grand Gerbil Poohbah
 
Posts: 3736
Joined: Tue Aug 10, 2004 10:10 am
Location: Ottawa, Canada

Re: Math question...

Postposted on Sat Dec 11, 2010 11:29 am

notfred wrote:
SNM wrote:
Shining Arcanine wrote:Now that I think about it, there is a contradiction in saying that a ^ (a <<n) = 0 where n > 0 and a is non-zero, which can be used to prove that the result zero only occurs when a = 0,

Let's try out a = 10101010b and n = 2.
a << 2 = 10101010
a ^ (a<<2) = 10101010 ^ 10101010
a ^ (a<<2) = 0.

I suspect a confusion between the different meanings of the << operator. In the original question it has been defined as Rotate Left so a << 2 = 10101010, however in C it is defined as Shift Left so a << 2 = 1010101000 which if stored in an 8 bit identifier would be a << 2 = 10101000.


That would be my fault. I mistook the original poster's operator definitions for the typical information that I usually have to provide to mathematics majors when describing computer calculations, so I did not realize that the original poster was redefining the << operator. With that mistake, my brain misinterpreted the original poster's equations as having C-style expressions.
Disclaimer: I over-analyze everything, so try not to be offended if I over-analyze something you wrote.
Shining Arcanine
Gerbil Jedi
 
Posts: 1717
Joined: Wed Jun 11, 2003 11:30 am

Re: Math question...

Postposted on Sat Dec 11, 2010 11:44 am

Shining Arcanine wrote:<A> XOR <A> is a hash function; there is no logical law that states that hash functions must have desirable properties. See the description at Wikipedia:
A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array (cf. associative array).

It may be a hash function by strict definition, but it is not a useful hash function.
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37705
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Math question...

Postposted on Wed Dec 15, 2010 8:36 am

Shining Arcanine wrote:
just brew it! wrote:<A> XOR <A> is not a hash function either, since (as you've pointed out) it always results in zero.

<A> XOR <C> (where C is a known constant) preserves information.

As another interesting example, consider the swapping of two variables without the use of a temporary -- the following sequence will swap the contents of the variables <A> and <B>, and would not be possible if XOR destroyed information:
Code: Select all
<A> := <A> XOR <B>
<B> := <A> XOR <B>
<A> := <A> XOR <B>


<A> XOR <A> is a hash function; there is no logical law that states that hash functions must have desirable properties. See the description at Wikipedia:
A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array (cf. associative array).


http://en.wikipedia.org/wiki/Hash_function

As for XOR, under certain circumstances, XOR destroys information. Under other circumstances, it preserves information. It is like asking whether or not e^(at) and e^(bt) are linearly independent. They are linearly dependent when a = b and linearly independent in all other cases.


jbi was implying that XORing with a known constant does not destroy information, that is a true statement. You were pointing out that if you XOR something with itself you get 0, this is also a true statement, but if your function is f(x) = x XOR C, and you say f(A) = 0, then I know that A = C, the "function" f(x) = x XOR x is identical to the zero function and so isn't in any real sense the XOR function, you are simply describing a property of the zero function.
To understand recursion, you must first understand recursion.
AMM
Minister of Gerbil Affairs
 
Posts: 2010
Joined: Tue Jun 10, 2003 9:12 am
Location: London

Re: Math question...

Postposted on Sun Dec 19, 2010 4:58 am

First things first, I'll admit that my inverse function would not work for "rotate left" in original post but I did prove "left shift" and "rotate left" requires different inverse function (by example).

Now on to why I really want to reply (now, yeah, I didn't feel like replying just to point out the obvious from above), strictly speaking h(x) = 0 is still a hash function albeit it is not useful at all... imagine a hash table with that for index! ;-)

Given the context we are discussing this, this would be more appropriate: http://en.wikipedia.org/wiki/Cryptograp ... h_function

And it would totally fail:

it is infeasible to modify a message without hash being changed,
it is infeasible to find two different messages with the same hash.


Yes, it would not be invertible and it is actually something desirable for cryptographic hash function (preimage resistance) but probably impossible (just because I don't want to prove it) to simultaneously meet the requirement of being a "useful" hash function also.
Lans
Gerbil In Training
 
Posts: 7
Joined: Thu Jun 05, 2008 7:06 pm


Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 2 guests