Untitled

import timeit

#LFSR1: x[1,i] =  x[1,i-2] + [x1,i-5]
def lfsr1(bin_str):
    if(bin_str[-2] == bin_str[-5]):
        return '0'
    return '1'

#LFSR2: x[2,i] =  x[2,i-1] + [x1,i-7]
def lfsr2(bin_str):
    if(bin_str[-1] == bin_str[-7]):
        return '0'
    return '1'

#LFSR3: x[3,i] =  x[3,i-2] + [x1,i-11]
def lfsr3(bin_str):
    if(bin_str[-2] == bin_str[-11]):
        return '0'
    return '1'


def f(x1,x2,x3):
    otp = ""
    for i in range(0, len(x1)):
        if(x2[i] == '0'):
            otp += str(x3[i])
        else:
            otp += str(x1[i])
    return otp

def decipher_geffe(k1,k2,k3, length=10):
    while(len(k1) < length):
        k1 += lfsr1(k1)
    while (len(k2) < length):
        k2 += lfsr2(k2)
    while (len(k3) < length):
        k3 += lfsr3(k3)
    secret_message = f(k1,k2,k3)
    return secret_message

def xor_strings(str1, str2):
    if(len(str1) != len(str2)):
        print("different length of strings; cannot perform XOR")
        return -1

    xor = ""
    for i in range(0, len(str1)):
        if(str1[i] == str2[i]):
            xor += '0'
        else:
            xor += '1'

    return xor

geffe = '01100111011111111001100011111010101011100111101100011111100100111000111010010110111110110110111010000000011000100110111011001110000110010111010010011000101110001000000101011101011101011110111111110110110111001000100000100011101000000011110010110110100011100101100100111011011111011000100010111010110011101001001111100100100011000111011110001001011111010110011101010011010111010010000010000001000100001101010111010011100100011111010111111011100011000011000001111000101110100110101100011111000110010011100010101100011110101001101000101010101001001111111101101110110111010010110010010111100111111110000000010001010011101000001010010101111000111101100000000111111111010100111010010000110011000111111101011010001001110101101010101101101100101101011101000010011111110010001010101000101011111101110000100101110001110111010011101101110011000111000110000001010111101100000011000111100110101100111010000000111010110111101110000001010100110111000010001111000001110110100000101110010101111110001110010101000100100011000010010100001100001111010110101001111111100110010110110010010000001000110000011010101010100011010111100011100011100001011110111110110111010100010100001010101111101111010011011010101111011111110100100010110110111001101100010100001101101000111100111011101011110010001011010001110000000111000011010011000111000101011100101100001011100011011110110001100001000111011101010101011010101011100100110010001111110001011000011011000100011111001100100110110001100110001000100101100101101010010100010011001111111101010001000111110110100011000000001011000000001101111001000000011011000011001001000001000001100010100110100101111001010101100110111011111001100100101101011110011011101100010110111100110100111110000010000101100011010111000000100111110100111011110001101001011000010101111111001111010001000101001110110000000101001111011010010011010100001101110000110011010101001001011100100110100010010011010111100101110001110000110111001011100100011100101111110111100110111111011110111110111101110010111000101001011101011000110011111011001000110001101010110100100011011010000110011111101000010010111010111010110000010011010000011110111100101110010010001100001010110110100101111000011001011101100010100011111001001011010101111111010101010110101000100101011011110000111100000101011100011110010000110010100000010100100011001000000100101010000011110111000100111010011000100000111001001011000011001011010100001010000001101111001001100100011101111001111101000010011010011111100110001111111011100101111000101010111000110010001000011010011101100000001101010000001101101000100111101000001110111001110100101110001100001110111110101110101111011110000010001100111101101011100101011000001101010101010110000111100010101101011110001000010001111100100101110110110010011110110010011001010001101100101011000001011101010001010110000010101111111100000111100111110010111101001010110000000100101000101111110111011110101110101010111100101000111101000101011000101100110000010000011010101000011001101110111110100111011111011001101001011001100000111011101110'

alphabet = "abcdefghijklmnopqrstuvwxyz"
letter_to_ix = {letter:idx for idx, letter in enumerate(alphabet)}
ix_to_letter = {v: k for k, v in letter_to_ix.items()}

letter_to_binary = {}
num_of_bits = 5

#letter_to_binary needs to have all letters written with five bits
for key in letter_to_ix:
    ix = letter_to_ix[key]
    #letter_to_binary[key] = format(ix, 'b')
    bnry = format(ix, 'b')
    x = bnry[::-1]  # this reverses an array.
    while len(x) < num_of_bits:
        x += '0'
    bnry = x[::-1]
    letter_to_binary[key] = bnry

binary_to_letter = {v: k for k, v in letter_to_binary.items()}

start = timeit.default_timer()


known_plaintext = 'cryptography'
known_ciphertext = ''

for c in known_plaintext:
    known_ciphertext += letter_to_binary[c]
#print(letter_to_binary)
#print("k_c", len(known_ciphertext))
#print(known_ciphertext,"len =", len(known_ciphertext))

first_bits = geffe[0:len(known_ciphertext)]
#print(first_bits)
xored_bits = xor_strings(first_bits, known_ciphertext)
#print(xored_bits)

#LFSR1: x[1,i] =  x[1,i-2] + [x1,i-5]
#LFSR2: x[2,i] =  x[2,i-1] + [x1,i-7]
#LFSR3: x[3,i] =  x[3,i-2] + [x1,i-11]
gen1_bits = 5; gen2_bits = 7; gen3_bits = 11
keys1 = []; keys2 = []; keys3 = []

'''attack on LFSR1'''
for i in range(1, 2**gen1_bits):
    bnry = format(i, 'b')
    x = bnry[::-1]  # this reverses an array.
    while (len(x) < gen1_bits):
        x += '0'
    bnry = x[::-1]

    while(len(bnry) < len(xored_bits)):
        new_bit = lfsr1(bnry)
        bnry += new_bit

    matches = 0
    for j in range (0, len(bnry)):
        if(bnry[j] == xored_bits[j]):
            matches += 1

    if(matches >= 7.5*len(xored_bits)/10):
        keys1.append(bnry)


'''attack on LFSR3'''
for i in range(1, 2 ** gen3_bits):
    bnry = format(i, 'b')
    x = bnry[::-1]  # this reverses an array.
    while (len(x) < gen3_bits):
        x += '0'
    bnry = x[::-1]

    while (len(bnry) < len(xored_bits)):
        new_bit = lfsr3(bnry)
        bnry += new_bit

    matches = 0
    for j in range(0, len(bnry)):
        if (bnry[j] == xored_bits[j]):
            matches += 1

    if (matches >= 7.5 * len(xored_bits) / 10):
        keys3.append(bnry)


'''attack on LFSR2 / final attack'''
for i in range(1, 2**gen2_bits):
    bnry = format(i, 'b')
    x = bnry[::-1]  # this reverses an array.
    while (len(x) < gen2_bits):
        x += '0'
    bnry = x[::-1]

    while (len(bnry) < len(xored_bits)):
        new_bit = lfsr2(bnry)
        bnry += new_bit

    k2 = bnry
    generated_bits = None
    for k1 in keys1:
        for k3 in keys3:
            generated_bits = f(k1,k2,k3)
            if(generated_bits == xored_bits):
                keys2.append(k2)


secret_message = ""
decryption_key = None
for k1 in keys1:
    for k2 in keys2:
        for k3 in keys3:
            #all keys as of now are of equal length
            while(len(k1) < len(geffe)):
                k1 += lfsr1(k1); k2 += lfsr2(k2); k3 += lfsr3(k3)

            decryption_key = decipher_geffe(k1,k2,k3, len(geffe))

secret_message =  xor_strings(geffe, decryption_key)

for i in range(0, len(secret_message), 5):
    c = secret_message[i: i+5]
    curr_letter = binary_to_letter[c]
    print(curr_letter, end='')

stop = timeit.default_timer()
print('\nRUNNING TIME:', stop - start, 'sec')

print("key1:", keys1[0][0:gen1_bits], "key2:", keys2[0][0:gen2_bits], "key3:", keys3[0][0:gen3_bits])