Andrew Burgess

Based off of tutorial by Howard M. Heys

import pprint

"""
input  0 1 2 3 4 5 6 7 8 9 A B C D E F
output 8 4 2 1 C 6 3 D A 5 E 7 F B 9 0
"""

inp = ["0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"]
out = ["1000", "0100", "0010", "0001", "1100", "0110", "0011", "1101", "1010", "0101", "1110", "0111", "1111", "1011", "1001", "0000"]

# S-Box from Heys tutorial
#out = ["1110", "0100", "1101", "0001", "0010", "1111", "1011", "1000", "0011", "1010", "0110", "1100", "0101", "1001", "0000", "0111"]

def check_bits(inbits, outbits):
    total = 0

    for x in range(len(inp)):
        r = 0
        for a in inbits:
            r ^= int(inp[x][a])
        for b in outbits:
            r ^= int(out[x][b])
        if r == 0:
            total += 1
    return total

def linear_approximation():
    result = []
    for i in range(len(inp)):
        row = []
        for j in range(len(inp)):
            inbits = []
            outbits = []
            for x in range(len(inp[i])):
                if inp[i][x] == "1":
                   inbits.append(x)
            for x in range(len(inp[j])):
                if inp[j][x] == "1":
                   outbits.append(x)

            row.append(check_bits(inbits, outbits) - 8)
        result.append(row)
    return result


if __name__ == '__main__':
    pp = pprint.PrettyPrinter()
    pp.pprint(linear_approximation())

This program brute force tests the Miller-Rabin algorithm to determine error probabilities. For the assignment, we ran it from 101,000 to 102,000. The program runs in about 25 minutes.

import sys, time

#Runs the algorithm for some values n and a. m and k are already calculated
def miller_rabin(n, a, m, k):
	#pow(x, y, z) = x^y mod z
	b = pow(a, m, n)
	#b is congruent to 1 (mod n)
	if b == 1:
		return (True, n, a, m, k, b) #Prime

	for i in xrange(0, k):
		#b is congruent to -1 (mod n)
		if b == n - 1:
			return (True, n, a, m, k, b) #Prime
		else:
			b = (b * b) % n

	return (False, n, a, m, k, b) #Composite

#Performs the overall loop and saves the data to a file
def miller_time():
	start = time.clock()
	f = open("stats.txt", "a")
	for n in xrange(101000, 102001):
		print n
		primes = 0
		composites = 0

		m = n - 1
		k = 0

		#Calculate k and m
		while m %  2 == 0:
			m >>= 1
			k += 1

		for a in xrange(1, n):
			ret = miller_rabin(n, a, m, k)
			if ret[0]:
				primes += 1
			else:
				composites += 1
		f.write("n=" + str(n) + ", Primes=" + str(primes) + ", Composites=" + str(composites) + ", Error=" + str(1.0 * primes / (primes + composites)))
		f.write("\n")
	f.close()
	end = time.clock()
	t = end - start
	print str(t) + " seconds"

#Sorts and then displays errors for the dataset
def stats():
	f = open("stats.txt", "r")
	data = []
	for line in f:
		n = int(line.split(",")[0].split("=")[1])
		p = int(line.split(",")[1].split("=")[1])
		c = int(line.split(",")[2].split("=")[1])
		e = float(line.split(",")[3].split("=")[1])

		data.append((n, p, c, e))

	data.sort(key=lambda x: x[3])

	for e in data:
		print e

#Command input
while True:
	cmd = raw_input("Enter command: ")
	if cmd == "it's miller time":
		miller_time()
	elif cmd == "stats":
		stats()
	elif cmd == "exit" or cmd == "quit":
		break

This python program can be used to do some analysis on a Vigenère cipher and then try to decrypt it with a given key

Usage:

#:> python vigenere.py
Enter command: ioc 4
0.0663865546218
0.0719887955182
0.072268907563
0.06918767507
AVERAGE: 0.0699579831933
Enter command: split 4
hgofttubjastbsfsnzaauftfvaabvvacavygluegzflfeyfbonyjvgflavnzghpgyhhzsvfnpauftxnfaaata
dvowchcioqpvicrwqdokpowcgocrbbrdrrwvcwocoohipwofcgzbgogmbgrccgctcqgowbfbazhhamrrourqh
smwemsalflvxrpmrlmqmsrvjsqjseklcmyxeywalwjsksxwcyqxmrkmesmvrreyyjlxvpwsxsmgmywsspamsv
fkaefkqgmgaqycvvsgslqvdzoskelssansqllvfaadssoalslsglgghjjlqggufdkugqdseagysfjzoogafmq
Enter command: key noes
uponthisbasisiamgoingtoshowyouhowabunchofbrightyoungfolksdidfindachampionamanwit
hboysandgirlsofhisownamanofsodominatingandhappyindividualitythatyouthisdrawntohi
masisaflytoasugarbowlitisastoryaboutasmalltownitisnotagossipyyarnnorisitadrymono
tonousaccountfullofsuchcustomaryfillinsasromanticmoonlightcastingmurkyshadowsdow
nalongwindingcountryroad

'''
	vigenere.py
	Andrew Burgess (andrew@deceptacle.com)
	Corey Greenhawk

	Can be used to do some analysis on a ciphertext encoded with a Vigenere cipher and attempt to decrypt

	The function "cheat" is used because the ciphertext was said to be from "Gadsby" by Ernest Vincent Wright
	Due to this information, it can be found that the plaintext would not contain the letter 'e'
	"cheat" takes advantage of this by removing potential key letters that would result in 'e' as the
	decrypted plaintext

	"cheat_brute" does some further trimming by removing decrypted plaintexts that contain way too many 'x's
	or 'z's (guessed amount, but seemed reasonable). This leaves a file with a much smaller possible set
	of potential plaintexts which can be quickly scanned to find the key
'''

'''
	Guessed keylength of 4 based on results from Index of Coincidence calculations
'''

#Block length of at most 6

cipher = "hdsfgvmkoowafweetcmfthskucaqbilgjofmaqlgspvatvxqbiryscpcfrmvswrvnqlszdmgaoqsakmlupsqforvtwvdfcjzvgsoaoqsacjkbrsevbelvbksarlscdcaarmnvrysywxqgvellcyluwwveoafgclazowafojdlhssfiksepsoywxafowlbfcsocylngqsyzxgjbmlvgrggokgfgmhlmejabsjvgmlnrvqzcrggcrghgeupcyfgtydycjkhqluhgxgzovqswpdvbwsffsenbxapasgazmyuhgsfhmftayjxmwznrsofrsoaopgauaaarmftqsmahvqecev"
#cipher = "lxfopvefrnhr" 	#Decryptes to "attackatdawn" Key is "lemonlemonle"

base = {} #Used for the base alphabet
for x in range(0, 26):
	base[chr(97 + x)] = 0

def split_string(length, s):
	substrings = []
	p = 0 #Passes
	for x in range(1, length + 1):
		substrings.append("")
		i = 0 + p
		while i  4:
			return

	if "z" in cnt:			#drop out way too many z's in the text
		if cnt["z"] > 8:
			return
	f.write("KEY: " + key)
	f.write("\n")
	f.write(decrypt(key))
	f.write("\n\n")

while True:
	'''	Commands:
		ioc 		Calculates index of coincidence for the keylength
		key 			Attempts to decrypt using the given key
		split 	Splits the ciphertext into the substrings used in IOC
		cheat 	Basically brute forces an answer using the provided keylength
	'''
	command = raw_input("Enter command: ")

	if (command.split(" ")[0] == "ioc"):
		ioc(int(command.split(" ")[1]))
	elif (command.split(" ")[0] == "key"):
		print decrypt(command.split(" ")[1])
	elif (command.split(" ")[0] == "split"):
		s = split_string(int(command.split(" ")[1]), cipher)
		for x in s:
			print x
	elif (command.split(" ")[0] == "cheat"):
		cheat(int(command.split(" ")[1]))
	elif (command == "exit"):
		break;

Solves a cipher text encrypted with the Affine cipher using two guessed cipher/plaintext pairs Usage:

#:> python affine.py
Trying with two characters...

First character (CIPHER=plain): I=a
Second character (CIPHER=plain): H=f
Guess is: a = 5, b = 8
affinecipher

'''
	Affine Cipher Decryptor
	Andrew Burgess (andrew@deceptacle.com)

	Using two guessed cipher/plaintext character pairs, guesses a key and shows the decrypted text
'''

cipher = "IHHWVCSWFRCP"		#Cipher text to crack (becomes affinecipher when solved)

'''
	Extended Euclidean Algorithm implementation.

	First number returned is the multiplicative inverse for u if v is the base
	Third number determines whether u and v are actually coprime. Should be 1 if they are
'''
def eea(u, v):
	u1 = 1
	u2 = 0
	u3 = u
	v1 = 0
	v2 = 1
	v3 = v
	while v3 != 0:
		q = u3 / v3
		t1 = u1 - q * v1
		t2 = u2 - q * v2
		t3 = u3 - q * v3
		u1 = v1
		u2 = v2
		u3 = v3
		v1 = t1
		v2 = t2
		v3 = t3
	return u1, u2, u3

'''
	Decrypts a character based on the alpha/beta values of the algorithm
'''
def decrypt(key, shift, char):
	v = eea(key, 26)

	return chr(((v[0]) * ((ord(char) - 65) - shift) % 26) + 97)

'''
	Guesses a key/shift pair based on a CIPHER=plaintext combo

	Input Example:
		First character: Y=e
		Second character: N=j

	Returns a pair of integers. The first is the key, and the second is the shift
'''
def guess_key(key1, key2):
	p = ord(key1.split("=")[1]) - 97
	r = ord(key1.split("=")[0]) - 65
	q = ord(key2.split("=")[1]) - 97
	s = ord(key2.split("=")[0]) - 65

	d = (p - q) % 26
	dinv = eea(d, 26)[0]

	a = (dinv * (r - s)) % 26
	b = (dinv * (p * s - q * r)) % 26

	return a, b

'''
	Loop to allow multiple guesses without needing to restart the program
'''
while True:
	print "Trying with two characters..."
	print
	key1 = raw_input("First character (CIPHER=plain): ")
	key2 = raw_input("Second character (CIPHER=plain): ")

	a, b = guess_key(key1, key2)

	print "Guess is: a = " + str(a) + ", b = " + str(b)

	message = ""
	for c in cipher:
		message = message + decrypt(a, b, c)

	print message
	raw_input()