Personal computing discussed
Moderators: renee, SecretSquirrel, just brew it!
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.
arsenhazzard wrote:edit: SNM's solution is the kind I went with first, but here's the 'linear algebra' approach
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
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.
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
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
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
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 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).
Shining Arcanine wrote:At a glance, it looked like a hash function, which lacks the property of bijection.
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> := <A> XOR <B>
<B> := <A> XOR <B>
<A> := <A> XOR <B>
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.
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 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).
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.
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.
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).
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.
it is infeasible to modify a message without hash being changed,
it is infeasible to find two different messages with the same hash.