Hey guys, I thought I'd share some work I did for my Crypto homework. The assignment can be viewed here if you are interested, but I'll go ahead and explain.
Determine the number of keys in an affine cipher over Z_m for m = 29, 99, and 1024. Briefly explain your answers.
Z_m is the set of characters that can be used for members of a cipher key. "m" is the size of the set. The letters of the English alphabet would be Z_26:
{A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z}
An affine cipher has a key like so: (a, b) where both "a" and "b" are characters from Z_m, and "a" must be coprime to "m." I could explain coprime in a bunch of crazy math, but how about I just show you an algorithm to find all the numbers between 1 and "m" that are coprime to m?
# given m is defined for a in range(1, m): # let's find all the possible values for a for x in range(1, m): # the algorithm is that we check all other values up to m if (a*x)%m == 1: # if a and x multiplied together, modulus m, is 1 print(a) # then a is coprime to m
The modulus function can be thought of as a remainder function. 7 modulus 4 is 3, because 7/4 is 1, with remainder 3.
So then the way to find the number of keys is to find the number of possible "a" values, times the number of possible "b" values (and that number is the same as "m").
In Z_26 (English) this number is 312.
Perform cryptanalysis of the following two ciphertexts. The first ciphertext was obtained using an affine cipher, and the second ciphertext was obtained using a substitution cipher. Your goal is to find the plaintexts. Both are in English.
Here are the ciphertexts:
XGKTRDCSSVWRKTGHGVWSCRGHRDGTGYKCXSWFWXGODWVWSSGSSGHJGKQRMOCR DWQRPKXCRMSRTGXERDOCRDWQRCXSWZGXIGIWQTKEGOCRDWQRFGTWSCRMKXHK ZZRDGPCTRQGSWFYKXOCRDWQRDCSPCIGSRDCSVTKCSGODCIDOWQZHJGQXYGKX CXEFZKRRGTMCFCXSITCJGHWPGTDQYKXKSDGSCSJQRKBQSRRTCJQRGRWRDGYG YWTMWFJWKRSOKCXKHWE
ELNQYGEVQKYREMBEELVBHVJNMRBNDYBERMJZMQMDYRNWMGELMEWLNBMKNRGY BDVNGLNYBJFMKKNMRGEYDVNLNVGGEVJJINRFQTCLMJVINVBELNKMGEGYVEVG INRFGVJJFZYRKNYKJNEYCRFMELVGZTBNRMJMJJQYQNBEGKMGEKRNGNBEMBDZ TETRNMJWMFGLMINNPVGENDMJWMFGWVJJNPVGEELNERMJZMQMDYRVMBGCMBJY YXMEMJJELNDVZZNRNBEQYQNBEGSTGEELMEWMFWNCMBJYYXMEMGERNECLYZEL NRYCXFQYTBEMVBGZYRVBGEMBCNELNFCMBGNNLYWKNRQMBNBEMJJELNQYQNBE GVYBWNLMINLNRNYBNMRELELMEYBNQYQNBEZYJJYWGMBYELNRYBNJVXNANMDG YBMGERVBHMBDELMEYBCNMQYQNBEVGHYBNVEVGHYBNZYRNINRWLNBMERMJZMQ MDYRVMBGNNGMCYRKGNMJJLNELVBXGVGELMEELNDNMDKNRGYBVGVBAMDCYBDV EVYBVBELNKMREVCTJMRQYQNBEATEELMEELNGMQNKNRGYBVGSTGEZVBNVBKJN BEFYZYELNRQYQNBEGBYWWLNBVQFGNJZLNMRELMEGYQNAYDFVGDNMDVGVQKJF GLRTHMBDGMFWLMEELNERMJZMQMDYRVMBGGMFMAYTEDNMDKNYKJNWLVCLVGGY VEHYNG
The idea was to decrypt the messages. Shannon's maxim, which says that anyone trying to decrypt a secret message is assumed to know the cryptographic method used, was assumed. Otherwise, I had no other knowledge about the messages!
The following is the (very large) program I used to toy around with the ciphers. You are free to use it!
# The following code is subject to the GNU GPL version 3, which can be found here: http://www.gnu.org/licenses/gpl-3.0.txt # With the exception of the ciphertexts and their respective plaintexts, and included libraries, which are property of their respective owners. # Code written by Andrew Garrett import string import itertools import copy # Setup global vars SUBCI = "ELNQYGEVQKYREMBEELVBHVJNMRBNDYBERMJZMQMDYRNWMGELMEWLNBMKNRGY + \ BDVNGLNYBJFMKKNMRGEYDVNLNVGGEVJJINRFQTCLMJVINVBELNKMGEGYVEVG + \ INRFGVJJFZYRKNYKJNEYCRFMELVGZTBNRMJMJJQYQNBEGKMGEKRNGNBEMBDZ + \ TETRNMJWMFGLMINNPVGENDMJWMFGWVJJNPVGEELNERMJZMQMDYRVMBGCMBJY + \ YXMEMJJELNDVZZNRNBEQYQNBEGSTGEELMEWMFWNCMBJYYXMEMGERNECLYZEL + \ NRYCXFQYTBEMVBGZYRVBGEMBCNELNFCMBGNNLYWKNRQMBNBEMJJELNQYQNBE + \ GMRNMBDELNFCMBJYYXMEMBFQYQNBEELMEVBENRNGEGELNQVEVGSTGEMBVJJT + \ GVYBWNLMINLNRNYBNMRELELMEYBNQYQNBEZYJJYWGMBYELNRYBNJVXNANMDG + \ YBMGERVBHMBDELMEYBCNMQYQNBEVGHYBNVEVGHYBNZYRNINRWLNBMERMJZMQ + \ MDYRVMBGNNGMCYRKGNMJJLNELVBXGVGELMEELNDNMDKNRGYBVGVBAMDCYBDV + \ EVYBVBELNKMREVCTJMRQYQNBEATEELMEELNGMQNKNRGYBVGSTGEZVBNVBKJN + \ BEFYZYELNRQYQNBEGBYWWLNBVQFGNJZLNMRELMEGYQNAYDFVGDNMDVGVQKJF + \ GLRTHMBDGMFWLMEELNERMJZMQMDYRVMBGGMFMAYTEDNMDKNYKJNWLVCLVGGY + \ VEHYNG" AFFCI = "XGKTRDCSSVWRKTGHGVWSCRGHRDGTGYKCXSWFWXGODWVWSSGSSGHJGKQRMOCR + \ DWQRPKXCRMSRTGXERDOCRDWQRCXSWZGXIGIWQTKEGOCRDWQRFGTWSCRMKXHK + \ ZZRDGPCTRQGSWFYKXOCRDWQRDCSPCIGSRDCSVTKCSGODCIDOWQZHJGQXYGKX + \ CXEFZKRRGTMCFCXSITCJGHWPGTDQYKXKSDGSCSJQRKBQSRRTCJQRGRWRDGYG + \ YWTMWFJWKRSOKCXKHWE" SUBKEY = {} for char in string.ascii_uppercase: SUBKEY[char] = '*' AFFKEY = [1,0] # Global vars set up def charFreqInText(key,ctext): '''prints the frequency of each character in a ciphertext''' freqtable = {} for char in string.ascii_lowercase: freqtable[char] = 0 for char in ctext: freqtable[char] += 1 for c in key.keys(): print( str(c), ":", str(key[c]), ":" , str(freqtable[key[c]])) def decryptSubCipher(key,ctext): '''key: in dict form''' newtext = "" for char in ctext: newtext += key[char] return newtext def decryptAffCipher(key,ctext): '''key: in form (a,b)''' newtext = "" for char in ctext: newtext += chr( ( ( ( ord(char) -97 - key[1] ) * computeInverse(key[0]) ) % 26 ) +97 ) return newtext def computeInverse(a,m=26): '''finds inverse of a in mod m via bruteforce''' for x in range(2,m): if (a*x)%m == 1: return x return 1 def manipulateSubKey(cipherchar, plainchar): oldplainchar = SUBKEY[cipherchar] oldcipherchar = '' for cc in SUBKEY: if SUBKEY[cc] == plainchar: oldcipherchar = cc SUBKEY[cipherchar] = plainchar if oldcipherchar != '': SUBKEY[oldcipherchar] = oldplainchar def main(): selection = -1 print("Welcome to the Homework 1 cryptanalysis tool.") while selection != 0: print("Choose an option:") print("0. Exit") print("1. PRINT the current value of the Substitution ciphertext.") print("2. PRINT the current guess of the Substitution cipher key.") print("3. MODIFY the Substituion cipher key.") print("4. ATTEMPT a bruteforce of the Substitution cipher.") print("5. PRINT the current value of the Affine ciphertext.") print("6. PRINT the current guess of the Affine cipher key.") print("7. MODIFY the Affine cipher key.") print("8. ATTEMPT a bruteforce of the Affine cipher.") print("9. PRINT the character frequency of both ciphers.") print("10. FIND the number of possible Affine keys in Z_m.") print("11. LOAD a new Substituition ciphertext.") print("12. LOAD a new Affine ciphertext.\n") selection = input(">> ") print() try: selection = int(selection) except ValueError: selection = -1 if selection == 0: return elif selection == 1: print(decryptSubCipher(SUBKEY,SUBCI),"\n") elif selection == 5: print(decryptAffCipher(AFFKEY,AFFCI),"\n") elif selection == 2: print(SUBKEY,"\n") elif selection == 6: print(AFFKEY,"\n") elif selection == 3: cipherchar = input("Cipher character: ").upper() plainchar = input("Plain character: ").lower() manipulateSubKey(cipherchar, plainchar) print() elif selection == 7: a = int(input("a: ")) b = int(input("b: ")) AFFKEY[0] = a AFFKEY[1] = b print() elif selection == 4: tempKey = SUBKEY.copy() unknownKeys = [] unknownVals = list(string.ascii_lowercase) for k in SUBKEY: if SUBKEY[k] == '*': unknownKeys += k else: unknownVals.remove(SUBKEY[k]) unknownKeys.sort() unknownVals.sort() allKeyPerms = itertools.permutations(unknownKeys) for k in allKeyPerms: for x in range(0,len(unknownVals)): tempKey[k[x]] = unknownVals[x] decryption = decryptSubCipher(tempKey,SUBCI) print("key: " + str(tempKey) + "\n" + decryption + '\n') elif selection == 8: for a in range(1,26): if computeInverse(a) != 1 or a == 1: for b in range(0,26): decryption = decryptAffCipher((a,b),AFFCI) print("key: (" + str(a) +"," + str(b) + ")\n" + decryption + '\n') elif selection == 9: print("Substituion cipher:\n") charFreqInText(SUBKEY,decryptSubCipher(SUBKEY,SUBCI)) print() print("Affine cipher:\n") charFreqInText(AFFKEY,decryptAffCipher(AFFKEY,AFFCI)) print() elif selection == 10: m = int(input("m: ")) c = 0 for a in range(1,m): if computeInverse(a,m) != 1 or a == 1: for b in range(0,m): c += 1 print("The total number of possible keys is:",c,"\n") elif selection == 11 or selection == 12: fname = input("File name with extension, or type * to type the ciphertext: ") buff = "" if fname != "*": fin = open(fname) for line in fin: buff += line.strip().upper() if selection == 11: SUBCI = copy.copy(buff) elif selection == 12: AFFCI = copy.copy(buff) else: if selection == 11: SUBCI = input("Type the Substitution ciphertext here. Whitespace will be stripped. > ").strip().upper() elif selection == 12: AFFCI = input("Type the Affine ciphertext here. Whitespace will be stripped. > ").strip().upper() print() else: print("That was an invalid selection; I am sorry.","\n") main()
I would love to break it down for you all but it's long and messy (quite hacked-together, as most of my Python programs are) so let me just explain it at a high level.
I let you build a key for either cipher and then use the key to decrypt the cipher. If the decryption is right it will look like English. Otherwise it will be gibberish.
You can also at any time attempt a brute-force attack on either cipher. I used to have code that would only print attempts that contained the word "the" in the decryption, but I felt like I didn't want to include that condition in this code. If you're feeling adventurous, why not try to find where you should place the following conditional?
(I love Python. In C that conditional statement is like 10 lines of code, seriously.)
However, the number of possible keys for the substitution cipher is 26!, so it will take any regular computer weeks to brute-force the key from scratch. You have to perform frequency analysis on the text to try to identify common letters, letter pairs, and three-letter words. Needless to say it is really hard to do, and I was up all night solving it. Once you identify several of the letters in the key, you can attempt a brute-force which can be solved in a few hours.
