One Time Pad algorithm for encryption and decryption

Question

I have written my own one time pad algorithm for encryption and decryption, but I would like to listen to your opinions about its correctness and eventually how could I improve it. My idea was to keep it readable, but not so bad in terms of performance. I have also written some tests.

Here's the code:

from random import choice
import string


def convert_to_bits(s):
    """Converts string s to a string containing only 0s or 1s,
    representing the original string."""
    return "".join(format(ord(x), 'b') for x in s)


def gen_random_key(n):
    """Generates a random key of bits (with 0s or 1s) of length n"""
    k = []
    for i in range(n):
        k.append(choice(["0", "1"]))
    return "".join(k)


def xor(m, k):
    """Given strings m and k of characters 0 or 1,
    it returns the string representing the XOR
    between each character in the same position.
    This means that m and k should be of the same length.

    Use this function both for encrypting and decrypting!"""
    r = []
    for i, j in zip(m, k):
        r.append(str(int(i) ^ int(j)))  # xor between bits i and j
    return "".join(r)


if __name__ == "__main__":
    ls = []

    for i in range(100):
        for i in range(100):
            ls.append(choice(string.ascii_letters))

        s = "".join(ls)

        bits = convert_to_bits(s)
        key = gen_random_key(len(bits))
        cipher = xor(bits, key)
        original = xor(key, cipher)

        if original != bits:
            raise Exception("Something wrong with the implementation...")

Answer 1

I have a few suggestions regarding performance:

Choosing between 2 things n times is slow, especially when factoring in the fact that you are appending to an array n times.

I would take advantage of the random module's getrandbits method like so:

def gen_random_key(n):
"""Generates a random key of bits (with 0s or 1s) of length n"""
return bin(getrandbits(n))[2:].zfill(n)

A full explanation:

• bin produces a binary string from an integer
• getrandbits(n) produces an integer from n random bits
• [2:] cuts out the '0b' that is put at the start of the string by bin
• .zfill(n) pads the resulting string with 0's to force a length of n

With shorter strings you won't notice the performance difference but with a larger string the speed difference is immense.

I used timeit to get the following timings on my machine:

10000 bits, called 100 times: 1.12 seconds vs 0.003 seconds

100000 bits, called 100 times: 11.5 seconds vs 0.003 seconds

As you can see, my method is orders of magnitudes faster.

---

For xor, you can use a similar approach:

def xor(m, k):
"""Given strings m and k of characters 0 or 1,
it returns the string representing the XOR
between each character in the same position.
This means that m and k should be of the same length.

Use this function both for encrypting and decrypting!"""
a = int(m, base=2)
b = int(k, base=2)
return bin(a ^ b)[2:].zfill(len(m))

---

Now ignoring that, let's discuss your general approach.

You convert a string of characters into a string of 0's and 1's. This is actually wasteful, as you are multiplying your memory usage immensely. The reason is that most characters take many bits to store. Thus, you are replacing one character with many 0 or 1 characters. Assuming pure ASCII, you might be using up to 7x the memory, and it will be quite a bit worse with arbitrary Unicode characters.

There's also another issue. Once you have your ciphertext, there isn't really a good way to recover the original string. Sure you can get the original bits back, but how do you know which how many or which bits correspond to which letter? You could solve this with padding, but that is an ugly solution that wastes even more memory.

Instead I propose the following solution:

Generate a string of characters (ASCII is fine, doesn't really matter too much) as a key. The key should have the same number of characters as the string. Then xor the ord of the characters in the same spot and make a new character with the result (by using chr). Join all these characters to form the cipher text.

My version of this (without comments/tests) is this:

def gen_key(string):
    return "".join(choice(string.printable) for _ in s)

def encrypt(string, key):
    return "".join(chr(ord(i) ^ ord(j)) for (i, j) in zip(string, key))

def decrypt(ciphertext, key):
    return encrypt(ciphertext, key)

Answer 2

You should use generator comprehensions instead of appending all the time.

def xor(m, k):
    return "".join(str(int(i) ^ int(k)) for i, j in zip(m, k))

def gen_random_key(n):
    return "".join(choice(["0", "1"]) for _ in range(n))

Also be careful with the name xor, as there is also operator.xor that it could conceivably be confused with.

Also note that when you don't care about the iteration variable's name, just use an underscore (_).

You could have slightly better names too - num_bits vs n as the parameter to gen_random_key

If you're actually going to write tests, write full unit tests and don't put them into the if __name__ == '__main__' block. Also make sure you cover the obvious cases at the very least - an empty string, a short string, a long string, as well as some tests that it fails when you expect it to. Additionally, if you're testing that the implementation is correct you should either assert or raise AssertionErrors.