Decrypt binary sequence with random binary key. What's wrong with my script?

Question

(Updated Below)

Attempting a problem from linear-algebra text Coding the Matrix by Philip Klein. Running into problems brute-forcing the ciphertext binary sequence against all possible keys. Problem 1.5.1, page 57:

An 11-symbol message has been encrypted as follows. Each symbol is represented by a number between 0 and 26 (A maps to 0, B to 25, space to 26.) Each number is represented by a five-bit binary sequence (0 maps to 00000, 26 to 11010). Finally, the resulting sequence of 55 bits is encrypted using a flawed version of the one-time pad: the key is not 55 bits but 11 copies of the same sequence of 5 random bits. The ciphertext is: '10101', '00100', '10101', '01011', '11001', '00011', '01011', '10101', '00100', '11001', '11010'

Goal is to figure out the plaintext. Issues I'm having are: One, my decoder function produces several 5-digit binary that are above int 26. This function is supposed to attempt the ciphertext binary sequence against every possible 5 digit binary sequence (the key) up to int 26, to produce every possible plaintext sequence. Two, am I supposed to use the Galois Field to ensure each binary sequence remains, well, binary? (1 + 1 = 0 and not 2) Any suggestions? I am attempting to learn linear-algebra (and improve upon my limited python abilities,) by using Klein's interesting text. It is rather difficult... Thank you!

import string

# The Cipher-text
Y = ['10101', '00100', '10101', '01011', '11001', '00011', '01011', '10101', '00100', '11001', '11010']


def trans(bit): # convert the bits into int
    x = ''.join(map(str, bit))
    return int(x, 2)


def decoder(cipher): # Try the ciphertext against each possible 5 bit sequence (up to 11010)
    pos_seq = ["".join("{0:05b}".format(x)) for x in range(27)]
    attempt = []
    for i in pos_seq:
        for j in cipher: # Add ciphertext binary to every possible binary 'key'.
            temp = [(int(i[0])+int(j[0])),(int(i[1])+int(j[1])),(int(i[2])+int(j[2])),
                    (int(i[3])+int(j[3])), (int(i[4])+int(j[4]))]
            attempt.append(temp)
    for i in range(len(attempt)): # Galois Field, 'two' becomes 'one'
        for k in attempt[i]:
            if k == 2:
                attempt[i][attempt[i].index(k)] = 0
    return attempt


new_list = decoder(Y)

decoded = [trans(i) for i in new_list] # translate each 5 digit sequence into int

alph = list(string.ascii_lowercase) # alphabet plus a space
alph.append(' ')

decoded2 = [alph[x] for x in decoded] # Translate int to letter or space

print(decoded2)

Update

Thanks to Dafang Cao and jason, I've edited the code as follows, and found the plaintext: eve is evil

1. Increased range in decoder function to 32
2. (Still have to wrap my head around GF(2) and XOR, including Dafang's use of x ^ y & mask)
3. Sliced the list returned by decoder into 11-item lists using

chunks = [decoded[x:x+11] for x in range(0, len(decoded), 11)]

*as the cipher-text is made up of 11 'symbols'

4. Mapped above list to the lambda function used by Dafang:

def decode(encoded):
    y = []
    for i in encoded:
        if i < 27:
            y.append(i)
    return ''.join(map(lambda x: alph[x], y))

for i in chunks:
    decoded2 = decode(i)
    print(decoded2)

Answer 1

There are 32 possible values using 5 bits. Knowing that valid values are 0-26, any decrypted value above 26 is a tell-tale sign that the key is not the key used in encryption. When brute forcing, you can skip the key as soon as you encounter such a value. In fact, I think that is how you are supposed to eliminate incorrect keys.

Meanwhile, it's not stated that the key is no greater than 26. You should try all 32 combinations.

Re. Galois Field, computer processors are naturally binary. You can take advantage of bit-wise operations like XOR to make the code faster. In fact, XOR is the add operation in GF(2). You can add 2 vectors in GF(2) using x ^ y & mask. When not dealing with GF(2), you can use modulo operator after an addition to "wrap" values into valid range x + y % n.

import string

# The Cipher-text
Y = ['10101', '00100', '10101', '01011', '11001', '00011', '01011', '10101', '00100', '11001', '11010']
# Parse to binary value
y = list(map(lambda v: int(v, 2), Y))

max_val = 32
alphabet_size = 26

# decrypt([0b11111, ...]) = [(key=0b1111, decrpyted=[0b11111, ...]), ...]
def decrypt(encrypted):
    possible_keys = range(max_val)
    attempt = []
    for key in possible_keys:
        decrypted = []
        for symbol in encrypted:
            # XOR is equivalent to Add in GF(2)
            # If not GF(2), add then wrap around using modulo
            v = symbol ^ key & (max_val - 1)
            print('v = %d' % v)
            if v > alphabet_size:
                break
            decrypted.append(v)
        if len(decrypted) < len(encrypted):
            print('bad key %d' % key)
            continue
        print('good key %d' % key)
        attempt.append((key, decrypted))
    return attempt

# alphabet plus a space
alph = list(string.ascii_lowercase)
alph.append(' ')
def decode(encoded):
    return ''.join(map(lambda x: alph[x], encoded))

results = decrypt(y)

for (key, encoded) in results:
    decoded = decode(encoded)
    print(decoded)

Answer 2

Alternative method:

# First establish the letter -> binary code:
digits = set(range(2))
base = 2
alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
'T', 'U', 'V', 'W', 'X', 'Y', 'Z', ' ']
binary_code = {a*base**4 + b*base**3 + c*base**2 + d*base**1 + e*base**0:str(a)+str(b)+str(c)+str(d)+str(e) for a in digits
                          for b in digits
                          for c in digits
                          for d in digits
                          for e in digits if a*base**4 + b*base**3 + c*base**2 + d*base**1 + e*base**0 <= 26}
letters_to_binary = {k:v for v,k in zip(alphabet,binary_code.values())}

# Now because this one-time pad is flawed, we can make a list of all possible keys - there are only 32
# These are all the 5 bit binary numbers
keys = {str(a)+str(b)+str(c)+str(d)+str(e) for a in digits for b in digits
                        for c in digits
                        for d in digits
                        for e in digits}

# We can then apply each key to the cyphertext under 
# Galois Field 2 addition - GF(2), and see which of 
# the resulting messages is most sensical

cyphertext = ['10101', '00100', '10101', '01011', '11001', '00011', '01011', '10101', '00100', '11001', '11010']
results = {}
for key in keys:
    message = ''
    for text in cyphertext:
        decoded = ''
        for num, t in zip(key, text):
            # The following if else implements GF(2) 
            # addition
            if (int(num) == 1 and int(t) == 0) or (int(num) == 0 and int(t) == 1):
                decoded = decoded + '1'
            else:
                decoded = decoded + '0'
        if decoded not in letters_to_binary:
            continue
        else:
            message = message + letters_to_binary[decoded]
    results[key] = message

print(results)
# From printing the results, using a key of 10001 results in a message of 'EVE IS EVIL', no other messages make sense.
# Thus the key is 10001

Answer 3

Late to the party but I thought this one might be straight forward:

message = [0b10101, 0b00100, 0b10101, 0b01011, 0b11001, 0b00011, 
0b01011, 0b10101, 0b00100, 0b11001, 0b11010]

keys = list(range(0b00000, 0b100000))

letters = ['a', 'b', 'c', 'd', 'e', 
'f', 'g', 'h', 'i', 'j', 'k', 'l',
'm', 'n', 'o', 'p', 'q', 'r', 's', 
't', 'u', 'v', 'w', 'x', 'y', 'z', ' ']

for k in keys:
    decrypted = ""
    possible = True
    for m in message:
        if(m^k in range(len(letters))):
            decrypted += letters[m^k]
        else:
            possible = False
            break
    if(possible):
        print(str(k) + ": " + decrypted)

Answer 4

Take a look at this solution, precisely at code 17. I think it is short and simple. Eve is Evil!

Regards!

message = [0b10101,0b00100,0b10101,
           0b01011,0b11001,0b00011,
           0b01011,0b10101,0b00100,
           0b11001,0b11010]
           
codes = range(0b00000,0b100000)
L = {i-65:chr(i) for i in range(65,91)}
L[26] = ' '

for code in codes:
    print(code, bin(code), ''.join([L[(l^code)%27] for l in message]))

Answer 5

cyph = [21, 4, 21, 11, 25, 3, 11, 21, 4, 25, 26]
alphabet = 'abcdefghijklmnopqrstuvwxyz '
for cc in range(1, 32):
    print(cc, ''.join([(alphabet[(x^cc)]) \
              for x in cyph if (x^cc) < len(alphabet)]))

Inspired by @Gabriel Simões