the homework of cryptographic 2013, NCTU

crypto_hw1.py

#!/usr/bin/env python3

import operator

# build the alphabet frequency table according to the sequence
def freq_count(seq):
    freq = { chr(i+ord('A')) : 0 for i in range(26) }
    for i in seq:
        freq[i] += 1
    return freq


# return a pair of the max elements and it's index:
#     (it's index, max element)
def list_index_max(list_):
    return max(enumerate(list_), key=operator.itemgetter(1))


# dump the frequency table for debugging
def dump_freq(freq):
    for i in range(26):
        print(chr(i+ord('A')) + ":" + str(freq[chr(i+ord('A'))]), end=', ')


# calculate the Ic formula
def cal_Ic(N, freq):
    s = 0
    for i in range(26):
        s += freq[chr(i+ord('A'))] * (freq[chr(i+ord('A'))] - 1)
    return s / (N * (N-1))


# happy go
def gogo(ciphertext):
    # from all Ic in m = 1..20, determine the correct m (key length)
    all_Ic = []
    for m in range(1, 21):
        part = int(len(ciphertext) / m)
        Ic_list = []

        # mean of the Ic sequences by different shifts
        for shift in range(m):
            subtext = ""
            for i in range(part):
                subtext += ciphertext[m*i+shift]
            freq_sub = freq_count(subtext)
            Ic_list += [cal_Ic(len(subtext), freq_sub)]
        all_Ic += [(sum(Ic_list) / float(len(Ic_list)))]

    # the index of max Ic is the key length
    this_m, max_Ic = list_index_max(all_Ic)
    this_m += 1

    # alphabet frequency table from the teacher's slide
    p = [.082, .015, .028, .043, .127, .022, .020,
         .061, .070, .002, .008, .040, .024,
         .067, .075, .019, .001, .060, .063,
         .091, .028, .010, .023, .001, .020, .001]

    # now we divide the ciphertext into n' parts
    n_prime = int(len(ciphertext) / this_m)

    key = ""
    # as each digit (shift) in the key
    for shift in range(this_m):
        subtext = ""
        for i in range(n_prime):
            subtext += ciphertext[this_m*i+shift]
        freq_sub = freq_count(subtext)
        collect = []

        # try g as 0..25 to find the max quantity Mg()
        for g in range(26):
            s = 0
            for i in range(26):
                s += p[i]*freq_sub[chr((i+g)%26+ord('A'))]
            s /= n_prime
            collect += [s]

        # here, we get this digit of the key
        index, value = list_index_max(collect)
        key += chr(index+ord('A'))

    print(key)


    # decrypt part
    key_count = 0
    for ch in ciphertext:
        #print("\n{} - {}".format(ch, key[key_count]))
        t_ch = ord(ch) - ord(key[key_count])
        t_ch = t_ch if t_ch >= 0 else (t_ch + 26)
        print(chr(t_ch + ord('A')), end='')
        key_count += 1
        key_count %= len(key)



try:
    ciphertext = input()
    gogo(ciphertext)
except:
    print("input error @_@?")



"""
test1
KERWXAETHMJTVORLNTRGIDRKEAVYUTTKOOOGWAZCMCHAOJNFQSALTFLVIOJECGFBZGZPVKENTHMJSKQWYGMTNKPDJQVCBYWEOSOCCPIERCCHAEJADYZMSNKFNZIELFLLQDUYCLTSXNZACMVFFUCUYNBFQSBLJVYVXOSTHCDDWOLAWHFUECZGLQYRQHXRVOFQDGZWIRQNTUECKAVVYRQCMIAHPPHIAPKGCZSJENYFNWGCFTKSGRZLYTGXVMUTRGAYBDQXGRLDMHRRPVSUHNVGHVHEIDRQJJQNLWXWNSMMJVAPSYSAENLEFSVVVYCDGLLPLPLWXJZQQHDLTSYLKGWCBBHVRWLQZQKNVDIYOBTSMOMNGISHBNTHTQGVDAWMDMHRSEGDTOCJYQEEGOHPABWCEBSKAJWZLVMJHLJARIAHTQSCLQSGDZRNPSWTZGYEUGHTRWSYLPSRGCCXDVNSGKTAHVYCWHBWSCTMYCERDWRNWAGUBMTVQLBTUHTQDMXVWMDMAADOMFBXQIETMSGEGGWEGPUCGAEOENYEMTNZLSLOBNLDLMJJVUPLBBRYZMBZGZQCHWNPZNMTSTJGCZEEAYBKWFINPXMEETSCKMSTKGHMSJIEFOMSMSMSBEFBCGFOMUDYCRGBOORZQFIJYCWMHCSFGXWYZRWMHRICQLZGPXKXGDFTSCAZKVFPXXSGEWJMALJRRIAEZODRAUHQIRPGTGHTLYQFNZDTBSAOEUZILYVFPOEOUEUZILYVKPDEBFTR


test2
BPVYWHBPTNKERVAYTWJCLUNAGVEYIAENPBQDVXXXKFNXBFNSTGGYCJGJXZQJRUMQJWAGOYTKUGPYPLBWMNJWYKMNNWTKKFYGEGTLGVEKWCPYPNHUMKBGOYTQBPXCPLUGOCNDNIXWCDYGWBGJYKMNNWEGWLKVVPZBQGQQGYOGEPBHIDVVMFGJRFKCFAAIAIQVNUDYFZRTFIVZRTBZUZREHONVTQMIXAFKMBGJTTTHFEBVAYTSFKMBCVOGXHCOUKEYUAAEXNJWLFLYGFRCVBQLUGKNJSGUTAQGQKWYCZRTFIVZRTLUKVFQMBGQCCVEGVNPBWGTNUDYVXBTECVLYGKYFJVFBHIZBQWNQLNMXNQZRTZLCFQOHNJWEYAYPLUGUUUCRVPUUJRCWSVZRNBNVDRIBLNHHVHHJWETXXEDBCDUPVXKLMGVUGKGQLUGKAQGQDRYTWZGFVGJTQLNTSVIANVGTTTHFENUAIWKRJXLOGGJXLESHVBIPWQFHHVVNYWFGSYQGAVZRYTSCFQREYCKRFHHVLNNDNQKGTTHIWEUMBGOBQWMCJRFTHIWEQNMFGAVPITJLOHGOQFCBXNAGVEYTWQTBXKFTJHIFAYNUYESEGYONTHVPBGFYKMNNWEGWLKVVPZBQGQPHNKURFLIOWYQOYNQSNHQGJFKGNJWJQHXUKUGYITYBVAYTHEQFCUWGQAYTEBVAYTKUGICECRFTZGOJCMWJWQVAYDMGVXLHDVGLZNAGCUIWLSQKUYZVNXFKKGGGYFLBVAYHJBILWTGNMBHISAFMBGFCKVEGVNHXQOGEGECVLYGKYFJVFBHIZBQWQCKRPCIAAAIMBGONTFMWEZGKXCQFQFOEZGJTNUZRFBXPLAQMCEWNFTLMKUCWIYSCRKICUUKGAQMGQYNJWSQKYULOGACPVUGK



CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE


"""