Subversion Repositories Code-Repo

import string, re

# Mapping of letter frequencies
letter_freq = {'A':.082,'B':.015,'C':0.028,'D':.043,'E':.127,'F':.022,'G':.02,'H':.061,\
                'I':.07,'J':.002,'K':.008,'L':.04,'M':.024,'N':.067,'O':.075,'P':.019,'Q':.001,\
                'R':.06,'S':.063,'T':.091,'U':.028,'V':.01,'W':.023,'X':.001,'Y':.02,'Z':.001}
alphabet_length = 26 # Number of letters in the alphabet
alphabet_offset = 65 # Offset of 'A' for ASCII characters
english_IC = 0.065 # IC of english
key_lengths = 10 # Number of key lengths to test
# Encrypted message
input = 'XKJUROWMLLPXWZNPIMBVBQJCNOWXPCCHHVVFVSLLFVXHAZITYXOHULX \
        QOJAXELXZXMYJAQFSTSRULHHUCDSKBXKNJQIDALLPQSLLUHIAQFPBPC \
        IDSVCIHWHWEWTHBTXRLJNRSNCIHUVFFUXVOUKJLJSWMAQFVJWJSDYLJ \
        OGJXDBOXAJULTUCPZMPLIWMLUBZXVOODYBAFDSKXGQFADSHXNXEHSAR \
        UOJAQFPFKNDHSAAFVULLUWTAQFRUPWJRSZXGPFUTJQIYNRXNYNTWMHC'

# letter_freq = {'A':0.7,'B':0.2,'C':0.1}
# alphabet_length = 3
# alphabet_offset = 65
# english_IC = 0.54
# key_lengths = 4
# input = 'ABCBABBBAC'

def calculate_IC(str):
        '''Calculates and returns the IC for a given string'''
        IC = 0
        for letter in letter_freq.keys():
                count = str.count(letter)       # count the frequency of every letter
                IC += float(count * (count-1))/float(len(str) * (len(str)-1))
        return IC

def get_substring(str, keylen):
        '''Returns a list of substrings of an offset of mod keylen'''
        ret = []
        for incr in range(keylen): # Iterate through the positions within each key
                substring = ''
                for char in range(len(str)): # Get every X characters from the input
                        if char % keylen == incr:
                                substring += str[char]
                ret.append(substring)
        return ret

def char_shift(char, x):
        '''Shifts a given character x amount and returns it'''
        i = ord(char) - alphabet_offset
        i += x
        while i < 0:
                i += alphabet_length
        return chr(i + alphabet_offset)

if __name__ == '__main__':
        # input = raw_input("Enter string: ")

        # Remove all whitespace from the input string and convert the string to uppercase
        input_stripped = re.sub('\s', '', input)
        input_stripped = input_stripped.upper()

        # Print out the sample size (length of input)
        sample_size = len(input_stripped)
        print "Sample Size: {0}\n".format(sample_size)

        # Calculate and print out the IC with keys of length 1-9
        print "Index of Coincidence (0.065 = IC of english):"
        freq_avg = dict()
        freq_diff = dict()

        # Create a mapping of IC to key lengths
        for length in range(1,key_lengths):
                avg_IC = 0
                substrings = get_substring(input_stripped, length) # Get a list of substrings
                print "M = {0}:".format(length),
                for str in substrings: # Calculate the average IC of all the substrings
                        IC = calculate_IC(str)
                        avg_IC += IC
                        print "{0:.2}".format(IC),
                print " : {0:.2}".format(avg_IC/length)
                freq_avg[avg_IC/length] = length # Store the key length and resulting IC

        # Create a mapping of |IC - 0.065| to key lengths
        for entry in freq_avg:
                freq_diff[abs(entry - english_IC)] = freq_avg[entry]

        # Sort this mapping and print out the most likely key lengths
        keys = freq_diff.keys()
        keys.sort()
        print "\nThe most likely key lengths are:"
        for entry in keys:
                print "{0} : {1:.3}".format(freq_diff[entry], entry)

        # Using the found keylength, calculate the most likely decrypting key
        print "\nAssuming the key has a length of {0} characters".format(freq_diff[keys[0]])
        key_length = freq_diff[keys[0]]

        # Now we shift each substring and try to find a shift where the IC is closest to 0.065
        print "The most likely key solutions are (read down on the left column):"
        substrings = get_substring(input_stripped, key_length) # First divide the input string by the key length
        key_final = ''

        for substr in substrings:
                freq_avg.clear() # First clear out both frequency dictionaries
                freq_diff.clear()

                # Create a mapping of IC to letters
                for g in range(alphabet_length): # Iterate through each letter + shifted value
                        IC = 0
                        for i in range(alphabet_length): # Iterate through each letter
                                # Calculate the IC using M_g = Sum(i=0-25) : p_i * f_(i+g) / n'
                                IC += float(letter_freq[chr(i+alphabet_offset)] * substr.count(chr((i+g)%alphabet_length + alphabet_offset))) / float(sample_size/key_length)
                        freq_avg[IC] = chr((g)%alphabet_length + alphabet_offset) # Store the letter and calculated IC

                # Create a mapping of |IC - 0.065| to letters
                for entry in freq_avg:
                        freq_diff[abs(entry - english_IC)] = freq_avg[entry]

                # Sort this mapping and print out the key
                keys = freq_diff.keys()
                keys.sort()
                output = ''
                key_final += freq_diff[keys[0]]
                for entry in keys:
                        output += freq_diff[entry] + ' '
                print output
                for i in range(3):
                        print "{0} : {1:.3}  ".format(freq_diff[keys[i]], keys[i])
                print

        # Decode the encrypted message using the key
        key_ind = 0
        output = ''
        for i in range(sample_size):
                output += char_shift(input_stripped[i], 0-ord(key_final[key_ind])-alphabet_offset)
                key_ind += 1
                key_ind %= key_length

        # Print the decoded message
        print "Encryption key: {0}, Decrypted message:".format(key_final)
        print output