3
$\begingroup$

I had to decrypt two book passages from different books which had both been encrypted using the same one-time-pad, and automate the process at that. I've found a few explanations of how this could be done exploiting XOR to extract the pad, but this was not applicable to our case since the encryption method was different (using a custom-made modulo addition function)

This question is not about coding, but just in case anyone may find it to be relevant, here’s the full encryption code:

from random import randrange
from sys import stdin, stdout
import subprocess
import operator
import re

# Acceptable characters. We will filter out all others.
ALPHABET = ( 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' +
             'abcdefghijklmnopqrstuvwxyz' +
             ' !"#$%\'()*,-./0123456789:;?@[]\n' )
ALPHABET_SIZE = len(ALPHABET)

def purify_file(infile, outfile):
    """Copy one file to another, removing characters not in ALPHABET."""
    with open(outfile, 'w') as out:
        out.write(purify_text(file(infile).read()))

def purify_text(text):
    """Copy text, removing characters not in ALPHABET."""
    ptext = []
    for c in text:
        if c in ALPHABET:
            ptext.append(c)
        elif c == '\n':
            ptext.append(' ')
    return ''.join(ptext)

def random_text(bookfile, size=1000):
    """Return a block of text of length SIZE from a random place in the
bookfile. All carriage returns, linefeeds and multiple spaces are replaced by
a single space.
"""
    wc = subprocess.check_output(["wc", bookfile])
    length = int(wc.split()[1])
    with open(bookfile, 'r') as book:
        book.seek(randrange(length-size))
        return re.sub(r'(\r\n|\s+)', ' ', book.read(size))

def random_text_file(bookfile, rand_file, size=1000):
    """Write a file containing a random block of text of the given size from the
given book file.

    """
    text = random_text(bookfile, size)
    with open(rand_file, 'w') as r:
        r.write(text)

def one_time_pad(length, alphabet=ALPHABET):
    """A random one-time pad."""
    lalph = len(alphabet)
    return ''.join([alphabet[randrange(lalph)] for _n in range(length)])

def otp_encrypt(text, otp=None):
    """Encrypt the text with a given or generated OTP."""
    if not otp:
        otp = one_time_pad(len(text))
    cyphertext = add_modulo_alphabet(text, otp)
    return cyphertext, otp

def otp_decrypt(cyphertext, otp):
    """Decrypt the cyphertext using the one-time pad."""
    return subtract_modulo_alphabet(cyphertext, otp)

def add_modulo_alphabet(s1, s2, alphabet=ALPHABET):
    return combine_modulo_alphabet(s1, s2, alphabet, combiner=operator.add)

def subtract_modulo_alphabet(s1, s2, alphabet=ALPHABET):
    return combine_modulo_alphabet(s1, s2, alphabet, combiner=operator.sub)

def combine_modulo_alphabet(s1, s2, alphabet=ALPHABET, combiner=operator.add):
    return ''.join([alphabet[combiner(alphabet.find(c1),
                                      alphabet.find(c2))
                             % len(alphabet)]
                    for c1, c2 in zip(s1, s2)])

def generate_otp_file(otp_file, size=1000):
    """Generate a file containing a one-time pad of the given size over the
alphabet.

    """
    otp = ''.join([ALPHABET[randrange(ALPHABET_SIZE)]
                   for _n in range(size)])
    with open(otp_file, 'w') as o:
        o.write(otp)

def otp_encrypt_file(plain_file, cypher_file, otp_file):
    """Encrypts contents of plaintext file using a newly generated one-time pad.
Writes cyphertext and OTP to given files in blocks.

    """
    with open(plain_file, 'r') as p:
        plaintext = p.read()
    cyphertext, otp = otp_encrypt(plaintext)
    with open(cypher_file, 'w') as c:
        c.write(cyphertext)
    with open(otp_file, 'w') as o:
        o.write(otp)

def otp_decrypt_file(cypher_file, otp_file, plain_file):
    """Decrypts the cypher_file using the OTP in otp_file and writes the
resulting plaintext to plain_file.

    """
    with open(cypher_file, 'r') as c:
        cyphertext = c.read()
    with open(otp_file, 'r') as o:
        otp = o.read()
    plaintext = subtract_modulo_alphabet(cyphertext, otp)
    with open(plain_file, 'w') as p:
        p.write(plaintext)

def encrypt_with_otp_file(plain_file, otp_file, cypher_file):
    """Encrypts contents of plaintext file using a given one-time pad. Writes
cyphertext to given files.

    """
    with open(plain_file, 'r') as p:
        plaintext = p.read()
    with open(otp_file, 'r') as o:
        otp = o.read()
    cyphertext = add_modulo_alphabet(plaintext, otp)
    with open(cypher_file, 'w') as c:
        c.write(cyphertext)

We ended up with a semi-manual solution - a program which relies on user input for guesses (a sort of crib-dragging) and with which decrypting the text is very time-consuming for the user since the encrypted texts are 1000 characters long.

Is it possible to extract the pad in this case and use it to automate the process, and was there another smarter way of solving this which we've overlooked?

$\endgroup$
1
$\begingroup$

If you have an on-line dictionary of English words, you can automate large portions of the crib dragging task. That is, have the program make guesses that a certain word appears in one plaintext, and see if the other plaintext contains text that also appears in the dictionary.

Of course, you're not likely to be able to automate everything; things such as misspellings, obscure words not in the dictionary, or proper names are likely to cause the above to fail at times (and the procedure will have to account for that). However, it is likely that the above will be able to reveal large sections of the plaintexts; large enough to make clean-up much easier.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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