July 18, 2019

Cryptopals Challenges: #5

Cryptopals Challenges: #5

In this challenge we are asked to implement a repeating key xor system.  This is similar to the previous challenges, except instead of a single character a string of characters is used.  The method of a repeating key xor is best shown by example.

plaintext ⊕ ice =
(p ⊕ i + l ⊕ c + a ⊕ e) + (i ⊕ i + n ⊕ c + t ⊕ e )+ (e ⊕ i + x ⊕ c + t ⊕ e)

As you can see, the plaintext is essentially broken into blocks of the length of the key.  The nth character in each plaintext block is xored against the nth character in the key.  These blocks are then concatenated together to form the ciphertext.

The approach to this problem can vary from person to person.  My solution uses the divmod() function in python to compute the quotient and remainder of the (plaintext, key) pair.  I then repeat the key a quotient amount of times, adding the bytes needed for the remainder.  This is illustrated through the following example:

plaintext: This_Is_A_Message (length 17 bytes)
key: ICE (length 3 bytes)

divmod(17, 3) = (5,2)

Repeat the key 5 times: ICEICEICEICEICE
Append the first two bytes: ICEICEICEICEICEIC

In code:

def RepeatingXOR(text, key):
    quotient, remainder = divmod(len(text), len(key))
    return xor_bytes(text, bytes(key * quotient + key[:remainder])).hex()

Then implement a standard xor function for byte strings:

def xor_bytes(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])

The zip() function takes iterables and returns an iterator of the tuple.  This associates values with other values:

a = [1,2,3]
b = [one, two, three]
zip(a,b) = {(1, one), (2, two), (3,three)}

With those two functions we are finished!  Running the program shows the expected output is identical to the output given by RepeatingXor().