XOR decryption

  • Python
  • Thread starter Arman777
  • Start date
  • #1
1,911
149
I come across a problem where I should decipher a text of ASCII codes using a encryption key consists of three lower case characters. And I know that the plain text should contain english words.

I searched online sources but I still didnt understand how should I approach the problem. Any help would be appriciated.

my understading is that first I should try to find the 3 letter encryption key by using that after the decryption that text will look like english ? . Also How does the XOR function will work in this case ?
 
  • Like
Likes YoungPhysicist

Answers and Replies

  • #2
12,499
6,286
Is this a problem from cicada 3301?

 
  • Like
Likes YoungPhysicist and Arman777
  • #3
1,911
149
Sadly not. Its a Project Euler question. It was 59 I guess
 
  • #4
1,996
276
You can decrypt xor encryption by Xoring with the same values.

to encrypt: encrypted(i) = message(i) xor key(i)
to decrypt: message(i) = encrypted(i) xor key(i)

You really don't have to know anything about the english language, you just have to know what the most frequently used character in nearly every ASCII text is.



 
  • Like
Likes YoungPhysicist
  • #5
1,911
149
how can I code xor ? is it some kind of a sum process ?
For example here my code
Python:
import itertools
file = open("cipher.txt","r")
A = []
for line in file:
    y = line.split(",")
    Encrypt = [int(e) for e in y]

B = [chr(i) for i in range(32,127)]

low_let = [i for i in range(97,123)]

h = list(itertools.combinations(low_let, 3))
Now I ll try to make random keys I guess like using the h list and I ll sum the key number and the encryptied mssg and the result will be message ?
 
  • #6
1,996
276
You can use this to encrypt/decrypt
Code:
s = [79,59,12,2,79,35]   #truncated, there were 1201 numbers

key = "abc"

result = ""
for i in range(len(s)):
    result += chr(s[i] ^ ord(key[i%3]))
print (result)
You could try all the keys, there are only 17576 of them. You will need some way to recognize if the output is english text. With ascii text, you might perhaps just check if all the ascii codes are printable. If the problem was harder, it might be necessary to download lists of english words, or letter frequency tables and check wich of the decryptions contains the most words.

You can do it in a much simpler way tough.I wote only 2 lines of python for it.
 
  • Like
Likes Arman777
  • #7
DavidSnider
Gold Member
500
141
Breaking repeated key xor is pretty easy, especially when you know the key length

So when the keylength is 3 you'll want to make 3 arrays and take every nth byte of the ciphertext and put it in the right bucket:
ex.: "abcdefghijklmnopqrstuvwxyz" -> "adgjmpsvy", "behknqtwz", "cfilorux"

Then you can crack each part as if it were encrypted with only a single character key, reducing the search space by a lot

After you xor the array against a single character create a character frequency histogram for the resulting block and compare the difference against an english plaintext (use a histogram of moby dick or something)

The difference is the score, pick the one with the least difference and that is probably the key for that array.

Then just repeat for each array and then reassemble back in order
 
  • Like
Likes Arman777
  • #8
1,911
149
I dont think I can do letter freq thing. I am not that much a good coder.
 
  • #9
1,911
149
I wrote something like this so far
Python:
import itertools
import string
file = open("cipher.txt","r")
for line in file:
    y = line.split(",")
    Dec = [int(e) for e in y]

low_case = string.ascii_lowercase

h = list(itertools.combinations_with_replacement((low_case),3))

def test2(n):
    if "this" in n:
        return True

for i in range(len(h)):
    key = h[i]
    result = ""
    for f in range(len(Dec)):
        result += chr(Dec[f] ^ ord(key[f%3]))
    if test2(result) == True:
        print(result)
I am stuck at the test part. I am not sure what to do now..or how can I do that word freq thing.

Also thanks for the code part that you shared it was really helpful for me to understand the idea. I wrote like a 20 line code for the XOR operator (I used ^ but I didnt know I could have done it just for 1 line). Also key[i%3] part is amazing and appending strings like that. I didnt know how to use those but I learned now.

Edit: I did the printible thing but it didnt change much
 
  • #11
1,996
276
I am stuck at the test part. I am not sure what to do now..or how can I do that word freq thing.
The test part is fine. The problem is that itertools.combinations_with_replacement only produces sorted keys. you need itertools.product.
(for some reason you need repeat = 3 as the second argument of product() instead of just 3).
You'll get your decryption with a few random ones that happen to contain"this".
 
  • Like
Likes Arman777
  • #12
1,911
149
The test part is fine. The problem is that itertools.combinations_with_replacement only produces sorted keys. you need itertools.product.
(for some reason you need repeat = 3 as the second argument of product() instead of just 3).
You'll get your decryption with a few random ones that happen to contain"this".
I am kind of confused about why I have to change it like that ?

I find it :)
Python:
import itertools
import string
from itertools import product

file = open("cipher.txt","r")
for line in file:
    y = line.split(",")
    Dec = [int(e) for e in y]

low_case = string.ascii_lowercase

h = list(itertools.product((low_case),repeat = 3))

def test2(n):
    if "this" in n and "the" in n:
        return True

for i in range(len(h)):
    key = h[i]
    result = ""
    for f in range(len(Dec)):
        result += chr(Dec[f] ^ ord(key[f%3]))
    if test2(result) == True:
        print(result)
I also add "the" condition.
 
  • #13
rbelli1
Gold Member
988
377
I am not that much a good coder.
Keep doing these exercises and that will be less and less true.

BoB
 
  • Like
Likes jedishrfu
  • #14
12,499
6,286
I agree. However this thread is now quite old and the discussion is lost to time so I’ll close it.
 
  • Like
Likes rbelli1

Related Threads on XOR decryption

  • Last Post
Replies
21
Views
1K
Replies
6
Views
8K
Replies
13
Views
1K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
5
Views
659
Top