Page 1 of 2 12 LastLast
Results 1 to 15 of 24

Math Help - Question about XOR and Addition mod in one equation?

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    13

    Question about XOR and Addition mod in one equation?

    its an extremely long cryptography equation for encoding messages, i've been working on it for the last two hours, and everytime i come to a conclusion close to this:

    (C⊞K)⊕(V⊞K) = 0
    i know both C and V, now i need to know K, what can i do? i don't really know how to interact with the XOR and the addition mod togather
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Well, you can take it this way:

    If (C\otimes K)\oplus(V\otimes K)=0, then it must be that both C\otimes K=0 and V\otimes K=0.

    Also, note that the XOR function is its own inverse. That is,

    a\otimes a=0. Moreover, if a\otimes b=c, then you can left-multiply by a as follows:

    a\otimes(a\otimes b)=a\otimes c

    (a\otimes a)\otimes b=a\otimes c (associativity of XOR)

    0\otimes b=a\otimes c

    b=a\otimes c.

    Hence, you must have

    V\otimes(V\otimes K)=V\otimes 0=V

    K=V.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Note: first post was entirely incorrect. Sorry about that.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    Posts
    13
    i know that XOR is its own inverse, however, in there there are 2 operators ... and one of the is an addition mod

    okay, if this is too far fetched, is it possible to solve this :
    (C+K)⊕(V+K) = 0
    + : Addition
    ⊞ : Modular Addition
    ⊕ : XOR
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    Posts
    13
    no problem mate, i appreciate you trying to help, i'll take whatever i can get
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Did you check my edited post # 2?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2008
    Posts
    13
    ok how about this:

    i didnt really think enough about the 0, and i see where your going at, i should have mentioned earlier that this is the equation:
    P = (C⊟K )⊕(V⊟K )

    ⊟ : Modular Subtraction
    ⊕ : XOR
    the right hand side was quite long but i can simplify it to a 64 bit block P, now i need to tell K (which is the key)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Define modular subtraction. If it's subtraction modulo 2 (as in normal boolean logic), then it is the same as addition modulo 2. Is that correct?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2008
    Posts
    13
    subtraction modulo 2^64

    also all of the variables here are blocks of 64 bit data
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    And the XOR is bitwise XOR?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2008
    Posts
    13
    yes, bitwise xor . i apologize for not being more specific
    Follow Math Help Forum on Facebook and Google+

  12. #12
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Well, let's assume a distributive property:

    (C-K)\oplus(V-K)=(C\oplus V)-(C\oplus K)-(K\oplus V)+(K\oplus K)=(C\oplus V)-(C\oplus K)-(K\oplus V).

    Here you can see that I've got an inverse for the modular subtraction, which is modular addition.

    Then P-(C\oplus V)=-K\oplus(C+V), or

    (C\oplus V)-P=K\oplus(C+V), and hence

    (C+V)\oplus((C\oplus V)-P)=K.

    This is probably too simple-minded, but maybe it'll give you an idea. What do you think?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Oct 2008
    Posts
    13
    i am not really certain the the distributive property works here, and that is precisely the problem, i have nothing to work on here ... how about this:
    given these two equations, do you think there is a different approach to solve for X,Y:
    X=(V⊟Y)⊕P
    X=(D⊟Y)⊕P

    again, all data here are 64 bit data, ⊕ is bitwise XOR, and ⊟ is subtraction mod 2^64
    Follow Math Help Forum on Facebook and Google+

  14. #14
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Hmm. A preliminary computation yields that we don't have the distributive property. At least, not exactly. Take A = 1010_{2}, B = 0011_{2}, C = 0001_{2}. Then

    A\otimes(B-C)=A\otimes(0010_{2})=1000_{2}, whereas

    (A\otimes B)-(A\otimes C)=1001_{2}-1011_{2}=-2_{10}=14_{10}=1110_{2}\not=1000_{2}.

    I think I'm out of my league now. Let me ask some of our gurus for help. Perhaps undefined or emakarov could help out.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by hamzeeco View Post
    ok how about this:

    i didnt really think enough about the 0, and i see where your going at, i should have mentioned earlier that this is the equation:
    P = (C⊟K )⊕(V⊟K )

    ⊟ : Modular Subtraction
    ⊕ : XOR
    the right hand side was quite long but i can simplify it to a 64 bit block P, now i need to tell K (which is the key)
    Interesting discussion on this thread, and I certainly don't claim to be an expert on any of this, but I see a problem that I'll explain by example.

    Consider 6-bit data, where our operations are mod 2^6.

    Let C = 101010
    Let V = 011110

    Now consider K1 = 001000 and K2 = 000010

    So

    A1 = C - K1 = 100010
    B1 = V - K1 = 010110

    P1 = A1 XOR B1 = 110100

    A2 = C - K2 = 101000
    B2 = V - K2 = 011100

    P2 = A2 XOR B2 = 110100

    So as you can see two different values of K yielded the same P. From this I am led to believe that we cannot determine K in general without guesswork.

    Quote Originally Posted by Ackbeet View Post
    Let me ask some of our gurus for help. Perhaps undefined or emakarov could help out.
    Didn't see this until after I made my post. Very flattered but I think guru is too strong of a word in my case!
    Last edited by undefined; October 18th 2010 at 02:15 PM. Reason: typos, misinterpretation of what K is
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. equation involving addition of powers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 28th 2011, 08:56 PM
  2. Question on Vector Addition
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: January 30th 2011, 06:14 AM
  3. Addition Formula Question
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: January 13th 2011, 10:28 AM
  4. Addition Formulas - Question
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: November 22nd 2009, 09:10 PM
  5. Vector Addition Question
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 29th 2009, 06:28 PM

Search Tags


/mathhelpforum @mathhelpforum