Reverse known XOR encryption algorithm

Question

I have XOR encryption and decryption algorithm, and its working, like this code

    int Encryption(int A)
    {
        E = (A ^ KEY) + (KEY ^ KEY2);
        return E;
    }
    int Decryption(int E)
    {
        A = (E - (KEY ^ KEY2)) ^ KEY;
        return A; 
    }

my problem is, how to get KEY and KEY2 if I know encryption value and decryption value Example: for Encryption value 0x53 it should have decryption value 0x47 for Encryption value 0x5E it should have decryption value 0x4C for Encryption value 0x61 it should have decryption value 0x49

Note I try to recover my KEY and KEY2 for my lost note

Thanks

Answer 1

Note: I will assume the encryption and decryption arithmetic are all done modulo 256.

Since you're encrypting and decrypting individual bytes with two 8-bit keys, the key space of this cipher is 256 times larger than the message space. That means there are 256 possible combinations of K and K2 for each (A,E) pair.

Specifically, if A = (E - (KEY ^ KEY2)) ^ KEY, then KEY2 = (E - (A ^ KEY)) ^ KEY. Using this formula for a given (A,E) pair, you can easily iterate through all 256 values of KEY and obtain the corresponding value of KEY2. Repeat this process for each pair of plaintext/ciphertext characters, and calculate the intersection of all the resulting sets of (KEY,KEY2) pairs. With a sufficient number of characters in the plaintext and ciphertext, that should give you a unique result.

I know you tagged this question as c#, but it's easier to do this sort of thing in Python. The following code probably isn't very efficient, but it doesn't matter because we're only dealing with a toy cipher here.

def retrieve_keys(plain,cipher):
    # Initialize set with all 65536 possible key pairs
    key_pairs = set([(x,y) for x in range(256) for y in range(256)])
    # Intersect this set with the set of 256 possible key pairs for
    # each plaintext/ciphertext pair
    for i in range(len(plain)):
        a, e = ord(plain[i]), ord(cipher[i])
        s = set([])
        # if a = (e - (key ^ key2)) ^ key, then key2 = (e - (a ^ key)) ^ key
        for key in range(256):
            s.add((key, ((e - (a ^ key)) % 256) ^ key))
        key_pairs = key_pairs.intersection(s)
    # Print out the remaining set of possible key pairs
    for kp in key_pairs:
        print "KEY=%d, KEY2=%d" % kp

# Example (should output "KEY=117, KEY2=80" and "KEY=245, KEY2=80"):
plaintext  = "Hello world, this is a test"
ciphertext = "b5>>?z'?,>6~z&BA+zA+z9z&5+&"
retrieve_keys(plaintext,ciphertext)

---

EDIT: The following C# code was suggested by Eric Lippert:

foreach (var kp in 
  Enumerable.Range(0, plain.Length).Aggregate(
    ( from x in Enumerable.Range(0, 256) 
      from y in Enumerable.Range(0, 256) 
      select new { x, y }).ToList(), 
    (pairs, i) => pairs.Intersect(
      from x in Enumerable.Range(0, 256) 
      select new { x, y = 
        ((cipher[i] - (plain[i] ^ x)) % 256) ^ x }).ToList()))
  Console.WriteLine(kp);