crack_vigenere.py

##
 # crack_vigenere.py
 #
 # [email protected]
 #
 # Attempts to crack cipher text either in the source code or in file 7b.txt (depending on the option)
 # which are encrypted in Vigenère Cipher and print the plaintext on the console or to a file 7b_plain.txt.
 ##

import itertools, analysis

en_alphabet = 'abcdefghijklmnopqrstuvwxyz'
dictionary = []
# For checking if the first word is valid, we will load the dictionary. Reduces the user work.
with open('resources/en_dict.txt', 'r') as dictf:
	for line in dictf:
		dictionary.append(line.split('\n')[0].lower())

# Vigenère Cipher Decryption Function
# We need it for checking if we have the right key
# key and cipher_text are all in lowercase
def decrypt(cipher_text, key):
	plaintext = ""

	index_in_key = 0
	for letter in cipher_text:
		# Index of the letter in the alphabet
		alpha_id = en_alphabet.find(letter)
		if alpha_id == -1:
			print("Unidentified letter found in ciphertext. Please provide text-only cipher text.")
			break
		else:
			# Go back key's corresponding letter number of times
			alpha_id -= en_alphabet.find(key[index_in_key])
			# wrap
			alpha_id %= 26

			# The alpha_id'th letter is our plaintext letter
			plaintext += str(en_alphabet[alpha_id])

			# Increment the index of key and wrap around if the length has been reached
			index_in_key += 1
			if index_in_key == len(key):
				index_in_key = 0
	return plaintext

# For a given key length, return string of every 'ith' letter in ciphertext
# ciphertext should all be lowercase
# 1 <= i <= key_len
def subkeys(key_len, i, cipher_text):
	res = ""
	index = i-1
	# Iterate from i-1 to end of ciphertext
	while index < len(cipher_text):
		res += cipher_text[index]
		index += key_len
	# Return the result string of every ith letter from the beginning for a given key_len
	return res

# Attempts to crack cipher_text with keys of length key_len
# Returns plain_text on success, None on failure
def crack(cipher_text, key_len):
	# List of key_len lists of frequency(order in analysis.py) scores
	frequencies = []
	for i in range(1, key_len+1):
		# String of every ith letter in cipher_text
		letter_set_i = subkeys(key_len, i, cipher_text)
		
		# A list of (key, order) tuples. Check the matchOrder() function in analysis.py
		# order is a number (1-14). Higher the number, closer the frequency to English frequency analysis.
		matchOrders = []
		# If the order is high, we will go ahead with it
		for letter in en_alphabet:
			# Each letter is a possible key for the subkey generated above.
			possible_plaintext = decrypt(letter_set_i, letter)
			# Store the letter key for the subkey ciphertext and the order-score from analysis.py in a tuple
			order_key_tup = (analysis.matchOrder(possible_plaintext), letter)
			matchOrders.append(order_key_tup)
		# Sort the list by decreasing order of score
		matchOrders = sorted(matchOrders, key=lambda x: x[0], reverse=True)

		# Only take the top 5 subkeys whose frequency matches most closely to English
		frequencies.append(matchOrders[:5])

	# Every combination of the most likely letters
	for indices in itertools.product(range(5), repeat=key_len):
		likely_key = ""
		for j in range(key_len):
			# Add the letter to the key string
			likely_key += frequencies[j][indices[j]][1]

		# Decrypt ciphertext with the likely_key
		likely_plaintext = decrypt(cipher_text, likely_key)

		# The longest word in the dictionary is pneumonoultr... 45 letters long
		# We are just checking if any word less than the length of 45 from the beginning of the ciphertext
		# happens to be in the dictionary
		for num in range(1, 46):
			possible_word = likely_plaintext[:num]
			if possible_word in dictionary:
				print('Possible key %s:' % (likely_key))
				print(likely_plaintext[:130])
				print()
				print('Please enter y if this is correct, n if wrong:')
				resp = input()

				if resp.strip().lower().startswith('y'):
					return likely_plaintext
		
	# When user responds with n for every output
	return None


# Take the user input for part number
ques = input('Enter the part of question 7 you want to crack (a or b or c): ')
ans = ques.strip().lower()
if ans == 'a':
	cipher_text = 'qivjukosqegnyiytxypshzewjsnsdpeybsuiranshzewjsnsdvusdvozqhasghexhvtdrynjyirlrrnfpekjbsuhucnjyirlrrnfveylrsdgbinjyirlrrnfwilqbsuqlisfqhhzuxytxaewhroxwvasjirxwsltyiytxontzxhjuyljvenivsdtlectpqiypinylwwmdxirosoplrgkrvytxaoswkeywlixivordrytwlewjyynmysyzensdxeqocozkswnpjejomnlzensdqaphcozxrdjuwtfqhnjyirlrrnfjmvjbsuzsreahvgtqraqhxytxhobq'
elif ans == 'b':
	with open('resources/7b.txt', 'r') as cf:
		cipher_text = cf.read()
elif ans == 'c':
	cipher_text = 'hdsfgvmkoowafweetcmfthskucaqbilgjofmaqlgspvatvxqbiryscpcfrmvswrvnqlszdmgaoqsakmlupsqforvtwvdfcjzvgsoaoqsacjkbrsevbelvbksarlscdcaarmnvrysywxqgvellcyluwwveoafgclazowafojdlhssfiksepsoywxafowlbfcsocylngqsyzxgjbmlvgrggokgfgmhlmejabsjvgmlnrvqzcrggcrghgeupcyfgtydycjkhqluhgxgzovqswpdvbwsffsenbxapasgazmyuhgsfhmftayjxmwznrsofrsoaopgauaaarmftqsmahvqecev'
else:
	print('Incorrect input. Please try again.')
cipher_text = cipher_text.lower()
# We know that keys are at most 6 charcters long
max_key_len = 6

# Will store the plain text
plain_text = None

# Try all key lengths till 6 until we get plaintext
for key_len in range(1, max_key_len+1):
	plain_text = crack(cipher_text, key_len)
	if plain_text != None:
		break

if plain_text:
	if ans == 'b':
		print()
		with open('7b_plain.txt', 'w') as pf:
			pf.write(plain_text)
		print('The excerpt from the first chapter of \'Harry Potter and the Methods of Rationality\' which was the plaintext ass along has been written to a text file `7b_plain.txt` in the same folder.\nThe key was `caesar`. Apologies for the number of steps required - it\'s a crude solution.')
	else:
		print()
		print('Full decrypted text: %s' % (plain_text))