2
$\begingroup$

There is a one time pad which works as follows: given message "hello" and key "asdfg", it produces "hwoqu". It only works with the 26 english letters. The output is (h(7) + a(0))%26 = h(7), (e(4) + s(18))%26 = w(22) etc.

So I have two ciphertexts created as above using a single key for both ciphertexts. I'm supposed to be able to crack the plain texts without needing access to the key.

What is the procedure to do this?

So far, I've tried XORing the two cipher texts, i.e. for each letter in c1 and c2, convert to its corresponding numeric value and XOR the nth letter of c1 with nth letter of c2, to genate c3.

I'm then supposed to use that with a guess word like "the" by exoring that against c3. This is the part where I'm stuck, I don't know what I'm supposed to be looking for here.

Edit:

So since its a addition rather than a XOR, this is what I wrote:

c1 = "ujhantamawmuzvgkterrykub"
c2 = "bpgxmkymbbpyxmogoehdefgh"

pad encrypt and decrypt:

def oneTimePad(message, code):
    message_out = ""
    for i in range(len(message)):
        
        index = (letters.find(message[i]) + letters.find(code[i]))%26
        message_out+= letters[index]

    return message_out

def otpDecrypt(cipher, key):
    message_out = ""

    for i in range(len(key)):
        index = (letters.find(cipher[i]) - letters.find(key[i]))%26
        message_out+= letters[index]
    return message_out

the cracker:

def padCracker(m1, m2, guess): # m1, m2 list of nums
    m3 = list(map(lambda x, y: (x + y) %26, m1, m2))
    check = [] # m3 + guess mod 26
    guessNum = list(map(lambda c : letters.find(c), guess))
    for i in range(len(m3)-len(guess)+1):
        check = list(map(lambda x, y: (x+y)%26, guessNum, m3[i: i+len(guess)]))
        print(check, end="")
        
        string = ""
        for num in check:
            string += letters[num]

        print(string)       


print(padCracker(m1,m2, "bcd"))

this suggests that c1 starts with "the" and c2 with "and" with key "bcd" but I don't know how to get the rest of the key

$\endgroup$
7
  • 1
    $\begingroup$ Hint: Does the encryption use XOR? What does it use? How does that relate the ciphertexts? $\endgroup$ Oct 25, 2021 at 0:58
  • $\begingroup$ I suppose this doesn't actually use XOR. It just adds key and plaintext letter just like a vigenere cipher. So, what is the procedure to then undo the vigenere cipher, and how do I use the relationship between c1 and c2 to get at the plaintext? $\endgroup$ Oct 25, 2021 at 1:00
  • 1
    $\begingroup$ It adds keystream letter and plaintext letter mod 26. The decryption is the same. The relation to perform the usual two-time-pad attacks (eg crib dragging) is to add the ciphertexts mod 26. crypto.stackexchange.com/questions/59/… has several good answers. $\endgroup$ Oct 25, 2021 at 1:03
  • $\begingroup$ thanks, that helped a lot. So I add the letters of the two ciphertexts because that is what was done during encrpytion, whereas if it had been XORed, I would also do the XOR of the two ciphertexts? If I understand crib dragging correctly, I take a guess word like "the" or "and" or "have", convert it to its numerical value then add each letter to the corresponding letter in the c3, if the result is something readable, then that gives me another potential guess word to then build up what the message is. $\endgroup$ Oct 25, 2021 at 1:20
  • $\begingroup$ Yep. This is basically the same OTP as normal, just with XOR on bits replaced with addition mod 26 on English letters. $\endgroup$ Oct 25, 2021 at 2:47

1 Answer 1

1
$\begingroup$

let $a = c_1 \oplus c_2$ the procedure is to try common bigrams and trigrams on every position of $a$, a trigram includes things like "the", you should note that not everything is crackable considering the readability of the plaintexts, if the two plaintexts were things like ")@#JRDIOHFf", "\$E)#(JRFNIf", you couldn't crack them.

But if the plaintexts are meaningful sentences, such as "the red fox jumped the fence", and "you were not there yesterday",

a[0:3] $\oplus$ "the" would produce "you", since they are both english words with meaning, there is a high possibility that "the" and "you" are the starting values of the two plaintexts.

Python Example that I wrote

m1 = b"the red fox jumped the fence"
m2 = b"you were not there yesterday"
key = b"1398jepfohn43p8nfp3fnvvno02D"
c1 = bytearray(len(m1))
c2 = bytearray(len(m2))

# encrypt m1
for i in range(len(m1)):
    c1[i] = m1[i] ^ key[i]

# encrypt m2
for i in range(len(m2)):
    c2[i] = m2[i] ^ key[i]

# calculate ciphertext1 ^ ciphertext2 to cancel out the key
a = [b""]*len(c1)
for i in range(len(c1)):
    a[i] = c1[i] ^ c2[i]

# calculate the at every position of a
common_trigram = b"the"
length = len(a) - 3 # 3 is the length of common_trigram
tries = [""]*length
a_indexes = [0]*length # indexes of a that corrosponds to the tries
for i in range(length):
    for j in range(3): # 3 is the length of common_trigram
        tries[i] += chr(a[i+j] ^ common_trigram[j])
        a_indexes[i] = i+j-2

# you can check if tries[i] is human readable or not and at what index is it human readable.

print(tries)
print(a_indexes)

# this line of code proves that it calculates it correctly
for i in range(3):
    print(chr(a[a_indexes[19+i]] ^ common_trigram[i])) # 19 is where "yes" is located, a_indexes shows the corrosponding indexes


# as you can see from the output, "the" produces "you" in the beginning and produces "yes" (for YESterday) for m2 when m1 equals "the"
# From this single trigram I learned
m1 = "the"
m2 = "you"
m1[19:22] = "the"
m2[19:22] = "yes"

You then try many other bigrams and trigrams to calculate the potential plaintexts. If you calculate one of them. The other one can be found using

$m_1 = a \oplus m_2$

$m_2 = a \oplus m_1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.