维吉尼亚密码

 1 # Vigenere Cipher (Polyalphabetic Substitution Cipher)
 2 # http://inventwithpython.com/hacking (BSD Licensed)
 3 
 4 import pyperclip
 5 
 6 LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
 7 
 8 def main():
 9     # This text can be copy/pasted from http://invpy.com/vigenereCipher.py
10     myMessage = """Alan Mathison Turing was a British mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine. Turing is widely considered to be the father of computer science and artificial intelligence. During World War II, Turing worked for the Government Code and Cypher School (GCCS) at Bletchley Park, Britain's codebreaking centre. For a time he was head of Hut 8, the section responsible for German naval cryptanalysis. He devised a number of techniques for breaking German ciphers, including the method of the bombe, an electromechanical machine that could find settings for the Enigma machine. After the war he worked at the National Physical Laboratory, where he created one of the first designs for a stored-program computer, the ACE. In 1948 Turing joined Max Newman's Computing Laboratory at Manchester University, where he assisted in the development of the Manchester computers and became interested in mathematical biology. He wrote a paper on the chemical basis of morphogenesis, and predicted oscillating chemical reactions such as the Belousov-Zhabotinsky reaction, which were first observed in the 1960s. Turing's homosexuality resulted in a criminal prosecution in 1952, when homosexual acts were still illegal in the United Kingdom. He accepted treatment with female hormones (chemical castration) as an alternative to prison. Turing died in 1954, just over two weeks before his 42nd birthday, from cyanide poisoning. An inquest determined that his death was suicide; his mother and some others believed his death was accidental. On 10 September 2009, following an Internet campaign, British Prime Minister Gordon Brown made an official public apology on behalf of the British government for "the appalling way he was treated." As of May 2012 a private member's bill was before the House of Lords which would grant Turing a statutory pardon if enacted."""
11     myKey = 'ASIMOV'
12     myMode = 'encrypt' # set to 'encrypt' or 'decrypt'
13 
14     if myMode == 'encrypt':
15         translated = encryptMessage(myKey, myMessage)
16     elif myMode == 'decrypt':
17         translated = decryptMessage(myKey, myMessage)
18 
19     print('%sed message:' % (myMode.title()))
20     print(translated)
21     pyperclip.copy(translated)
22     print()
23     print('The message has been copied to the clipboard.')
24 
25 
26 def encryptMessage(key, message):
27     return translateMessage(key, message, 'encrypt')
28 
29 
30 def decryptMessage(key, message):
31     return translateMessage(key, message, 'decrypt')
32 
33 
34 def translateMessage(key, message, mode):
35     translated = [] # stores the encrypted/decrypted message string
36 
37     keyIndex = 0
38     key = key.upper()
39 
40     for symbol in message: # loop through each character in message
41         num = LETTERS.find(symbol.upper())
42         if num != -1: # -1 means symbol.upper() was not found in LETTERS
43             if mode == 'encrypt':
44                 num += LETTERS.find(key[keyIndex]) # add if encrypting
45             elif mode == 'decrypt':
46                 num -= LETTERS.find(key[keyIndex]) # subtract if decrypting
47 
48             num %= len(LETTERS) # handle the potential wrap-around
49 
50             # add the encrypted/decrypted symbol to the end of translated.
51             if symbol.isupper():
52                 translated.append(LETTERS[num])
53             elif symbol.islower():
54                 translated.append(LETTERS[num].lower())
55 
56             keyIndex += 1 # move to the next letter in the key
57             if keyIndex == len(key):
58                 keyIndex = 0
59         else:
60             # The symbol was not in LETTERS, so add it to translated as is.
61             translated.append(symbol)
62 
63     return ''.join(translated)
64 
65 
66 # If vigenereCipher.py is run (instead of imported as a module) call
67 # the main() function.
68 if __name__ == '__main__':
69     main()

 1 # Frequency Finder
 2 # http://inventwithpython.com/hacking (BSD Licensed)
 3 
 4 
 5 
 6 # frequency taken from http://en.wikipedia.org/wiki/Letter_frequency
 7 englishLetterFreq = {'E': 12.70, 'T': 9.06, 'A': 8.17, 'O': 7.51, 'I': 6.97, 'N': 6.75, 'S': 6.33, 'H': 6.09, 'R': 5.99, 'D': 4.25, 'L': 4.03, 'C': 2.78, 'U': 2.76, 'M': 2.41, 'W': 2.36, 'F': 2.23, 'G': 2.02, 'Y': 1.97, 'P': 1.93, 'B': 1.29, 'V': 0.98, 'K': 0.77, 'J': 0.15, 'X': 0.15, 'Q': 0.10, 'Z': 0.07}
 8 ETAOIN = 'ETAOINSHRDLCUMWFGYPBVKJXQZ'
 9 LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
10 
11 
12 
13 def getLetterCount(message):
14     # Returns a dictionary with keys of single letters and values of the
15     # count of how many times they appear in the message parameter.
16     letterCount = {'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 0, 'L': 0, 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0, 'S': 0, 'T': 0, 'U': 0, 'V': 0, 'W': 0, 'X': 0, 'Y': 0, 'Z': 0}
17 
18     for letter in message.upper():
19         if letter in LETTERS:
20             letterCount[letter] += 1
21 
22     return letterCount
23 
24 
25 def getItemAtIndexZero(x):
26     return x[0]
27 
28 
29 def getFrequencyOrder(message):
30     # Returns a string of the alphabet letters arranged in order of most
31     # frequently occurring in the message parameter.
32 
33     # first, get a dictionary of each letter and its frequency count
34     letterToFreq = getLetterCount(message)
35 
36     # second, make a dictionary of each frequency count to each letter(s)
37     # with that frequency
38     freqToLetter = {}
39     for letter in LETTERS:
40         if letterToFreq[letter] not in freqToLetter:
41             freqToLetter[letterToFreq[letter]] = [letter]
42         else:
43             freqToLetter[letterToFreq[letter]].append(letter)
44 
45     # third, put each list of letters in reverse "ETAOIN" order, and then
46     # convert it to a string
47     for freq in freqToLetter:
48         freqToLetter[freq].sort(key=ETAOIN.find, reverse=True)
49         freqToLetter[freq] = ''.join(freqToLetter[freq])
50 
51     # fourth, convert the freqToLetter dictionary to a list of tuple
52     # pairs (key, value), then sort them
53     freqPairs = list(freqToLetter.items())
54     freqPairs.sort(key=getItemAtIndexZero, reverse=True)
55 
56     # fifth, now that the letters are ordered by frequency, extract all
57     # the letters for the final string
58     freqOrder = []
59     for freqPair in freqPairs:
60         freqOrder.append(freqPair[1])
61 
62     return ''.join(freqOrder)
63 
64 
65 def englishFreqMatchScore(message):
66     # Return the number of matches that the string in the message
67     # parameter has when its letter frequency is compared to English
68     # letter frequency. A "match" is how many of its six most frequent
69     # and six least frequent letters is among the six most frequent and
70     # six least frequent letters for English.
71     freqOrder = getFrequencyOrder(message)
72 
73     matchScore = 0
74     # Find how many matches for the six most common letters there are.
75     for commonLetter in ETAOIN[:6]:
76         if commonLetter in freqOrder[:6]:
77             matchScore += 1
78     # Find how many matches for the six least common letters there are.
79     for uncommonLetter in ETAOIN[-6:]:
80         if uncommonLetter in freqOrder[-6:]:
81             matchScore += 1
82 
83     return matchScore

 1 # Vigenere Cipher Dictionary Hacker
 2 # http://inventwithpython.com/hacking (BSD Licensed)
 3 
 4 import detectEnglish, vigenereCipher, pyperclip
 5 
 6 def main():
 7     ciphertext = """Tzx isnz eccjxkg nfq lol mys bbqq I lxcz."""
 8     hackedMessage = hackVigenere(ciphertext)
 9 
10     if hackedMessage != None:
11         print('Copying hacked message to clipboard:')
12         print(hackedMessage)
13         pyperclip.copy(hackedMessage)
14     else:
15         print('Failed to hack encryption.')
16 
17 
18 def hackVigenere(ciphertext):
19     fo = open('dictionary.txt')
20     words = fo.readlines()
21     fo.close()
22 
23     for word in words:
24         word = word.strip() # remove the newline at the end
25         decryptedText = vigenereCipher.decryptMessage(word, ciphertext)
26         if detectEnglish.isEnglish(decryptedText, wordPercentage=40):
27             # Check with user to see if the decrypted key has been found.
28             print()
29             print('Possible encryption break:')
30             print('Key ' + str(word) + ': ' + decryptedText[:100])
31             print()
32             print('Enter D for done, or just press Enter to continue breaking:')
33             response = input('> ')
34 
35             if response.upper().startswith('D'):
36                 return decryptedText
37 
38 if __name__ == '__main__':
39     main()

  1 # Vigenere Cipher Hacker
  2 # http://inventwithpython.com/hacking (BSD Licensed)
  3 
  4 import itertools, re
  5 import vigenereCipher, pyperclip, freqAnalysis, detectEnglish
  6 
  7 LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  8 SILENT_MODE = False # if set to True, program doesn't print attempts
  9 NUM_MOST_FREQ_LETTERS = 4 # attempts this many letters per subkey
 10 MAX_KEY_LENGTH = 16 # will not attempt keys longer than this
 11 NONLETTERS_PATTERN = re.compile('[^A-Z]')
 12 
 13 
 14 def main():
 15     # Instead of typing this ciphertext out, you can copy & paste it
 16     # from http://invpy.com/vigenereHacker.py
 17     ciphertext = """Adiz Avtzqeci Tmzubb wsa m Pmilqev halpqavtakuoi, lgouqdaf, kdmktsvmztsl, izr xoexghzr kkusitaaf. Vz wsa twbhdg ubalmmzhdad qz hce vmhsgohuqbo ox kaakulmd gxiwvos, krgdurdny i rcmmstugvtawz ca tzm ocicwxfg jf "stscmilpy" oid "uwydptsbuci" wabt hce Lcdwig eiovdnw. Bgfdny qe kddwtk qjnkqpsmev ba pz tzm roohwz at xoexghzr kkusicw izr vrlqrwxist uboedtuuznum. Pimifo Icmlv Emf DI, Lcdwig owdyzd xwd hce Ywhsmnemzh Xovm mby Cqxtsm Supacg (GUKE) oo Bdmfqclwg Bomk, Tzuhvif'a ocyetzqofifo ositjm. Rcm a lqys ce oie vzav wr Vpt 8, lpq gzclqab mekxabnittq tjr Ymdavn fihog cjgbhvnstkgds. Zm psqikmp o iuejqf jf lmoviiicqg aoj jdsvkavs Uzreiz qdpzmdg, dnutgrdny bts helpar jf lpq pjmtm, mb zlwkffjmwktoiiuix avczqzs ohsb ocplv nuby swbfwigk naf ohw Mzwbms umqcifm. Mtoej bts raj pq kjrcmp oo tzm Zooigvmz Khqauqvl Dincmalwdm, rhwzq vz cjmmhzd gvq ca tzm rwmsl lqgdgfa rcm a kbafzd-hzaumae kaakulmd, hce SKQ. Wi 1948 Tmzubb jgqzsy Msf Zsrmsv'e Qjmhcfwig Dincmalwdm vt Eizqcekbqf Pnadqfnilg, ivzrw pq onsaafsy if bts yenmxckmwvf ca tzm Yoiczmehzr uwydptwze oid tmoohe avfsmekbqr dn eifvzmsbuqvl tqazjgq. Pq kmolm m dvpwz ab ohw ktshiuix pvsaa at hojxtcbefmewn, afl bfzdakfsy okkuzgalqzu xhwuuqvl jmmqoigve gpcz ie hce Tmxcpsgd-Lvvbgbubnkq zqoxtawz, kciup isme xqdgo otaqfqev qz hce 1960k. Bgfdny'a tchokmjivlabk fzsmtfsy if i ofdmavmz krgaqqptawz wi 1952, wzmz vjmgaqlpad iohn wwzq goidt uzgeyix wi tzm Gbdtwl Wwigvwy. Vz aukqdoev bdsvtemzh rilp rshadm tcmmgvqg (xhwuuqvl uiehmalqab) vs sv mzoejvmhdvw ba dmikwz. Hpravs rdev qz 1954, xpsl whsm tow iszkk jqtjrw pug 42id tqdhcdsg, rfjm ugmbddw xawnofqzu. Vn avcizsl lqhzreqzsy tzif vds vmmhc wsa eidcalq; vds ewfvzr svp gjmw wfvzrk jqzdenmp vds vmmhc wsa mqxivmzhvl. Gv 10 Esktwunsm 2009, fgtxcrifo mb Dnlmdbzt uiydviyv, Nfdtaat Dmiem Ywiikbqf Bojlab Wrgez avdw iz cafakuog pmjxwx ahwxcby gv nscadn at ohw Jdwoikp scqejvysit xwd "hce sxboglavs kvy zm ion tjmmhzd." Sa at Haq 2012 i bfdvsbq azmtmd'g widt ion bwnafz tzm Tcpsw wr Zjrva ivdcz eaigd yzmbo Tmzubb a kbmhptgzk dvrvwz wa efiohzd."""
 18     hackedMessage = hackVigenere(ciphertext)
 19 
 20     if hackedMessage != None:
 21         print('Copying hacked message to clipboard:')
 22         print(hackedMessage)
 23         pyperclip.copy(hackedMessage)
 24     else:
 25         print('Failed to hack encryption.')
 26 
 27 
 28 def findRepeatSequencesSpacings(message):
 29     # Goes through the message and finds any 3 to 5 letter sequences
 30     # that are repeated. Returns a dict with the keys of the sequence and
 31     # values of a list of spacings (num of letters between the repeats).
 32 
 33     # Use a regular expression to remove non-letters from the message.
 34     message = NONLETTERS_PATTERN.sub('', message.upper())
 35 
 36     # Compile a list of seqLen-letter sequences found in the message.
 37     seqSpacings = {} # keys are sequences, values are list of int spacings
 38     for seqLen in range(3, 6):
 39         for seqStart in range(len(message) - seqLen):
 40             # Determine what the sequence is, and store it in seq
 41             seq = message[seqStart:seqStart + seqLen]
 42 
 43             # Look for this sequence in the rest of the message
 44             for i in range(seqStart + seqLen, len(message) - seqLen):
 45                 if message[i:i + seqLen] == seq:
 46                     # Found a repeated sequence.
 47                     if seq not in seqSpacings:
 48                         seqSpacings[seq] = [] # initialize blank list
 49 
 50                     # Append the spacing distance between the repeated
 51                     # sequence and the original sequence.
 52                     seqSpacings[seq].append(i - seqStart)
 53     return seqSpacings
 54 
 55 
 56 def getUsefulFactors(num):
 57     # Returns a list of useful factors of num. By "useful" we mean factors
 58     # less than MAX_KEY_LENGTH + 1. For example, getUsefulFactors(144)
 59     # returns [2, 72, 3, 48, 4, 36, 6, 24, 8, 18, 9, 16, 12]
 60 
 61     if num < 2:
 62         return [] # numbers less than 2 have no useful factors
 63 
 64     factors = [] # the list of factors found
 65 
 66     # When finding factors, you only need to check the integers up to
 67     # MAX_KEY_LENGTH.
 68     for i in range(2, MAX_KEY_LENGTH + 1): # don't test 1
 69         if num % i == 0:
 70             factors.append(i)
 71             factors.append(int(num / i))
 72     if 1 in factors:
 73         factors.remove(1)
 74     return list(set(factors))
 75 
 76 
 77 def getItemAtIndexOne(x):
 78     return x[1]
 79 
 80 
 81 def getMostCommonFactors(seqFactors):
 82     # First, get a count of how many times a factor occurs in seqFactors.
 83     factorCounts = {} # key is a factor, value is how often if occurs
 84 
 85     # seqFactors keys are sequences, values are lists of factors of the
 86     # spacings. seqFactors has a value like: {'GFD': [2, 3, 4, 6, 9, 12,
 87     # 18, 23, 36, 46, 69, 92, 138, 207], 'ALW': [2, 3, 4, 6, ...], ...}
 88     for seq in seqFactors:
 89         factorList = seqFactors[seq]
 90         for factor in factorList:
 91             if factor not in factorCounts:
 92                 factorCounts[factor] = 0
 93             factorCounts[factor] += 1
 94 
 95     # Second, put the factor and its count into a tuple, and make a list
 96     # of these tuples so we can sort them.
 97     factorsByCount = []
 98     for factor in factorCounts:
 99         # exclude factors larger than MAX_KEY_LENGTH
100         if factor <= MAX_KEY_LENGTH:
101             # factorsByCount is a list of tuples: (factor, factorCount)
102             # factorsByCount has a value like: [(3, 497), (2, 487), ...]
103             factorsByCount.append( (factor, factorCounts[factor]) )
104 
105     # Sort the list by the factor count.
106     factorsByCount.sort(key=getItemAtIndexOne, reverse=True)
107 
108     return factorsByCount
109 
110 
111 def kasiskiExamination(ciphertext):
112     # Find out the sequences of 3 to 5 letters that occur multiple times
113     # in the ciphertext. repeatedSeqSpacings has a value like:
114     # {'EXG': [192], 'NAF': [339, 972, 633], ... }
115     repeatedSeqSpacings = findRepeatSequencesSpacings(ciphertext)
116 
117     # See getMostCommonFactors() for a description of seqFactors.
118     seqFactors = {}
119     for seq in repeatedSeqSpacings:
120         seqFactors[seq] = []
121         for spacing in repeatedSeqSpacings[seq]:
122             seqFactors[seq].extend(getUsefulFactors(spacing))
123 
124     # See getMostCommonFactors() for a description of factorsByCount.
125     factorsByCount = getMostCommonFactors(seqFactors)
126 
127     # Now we extract the factor counts from factorsByCount and
128     # put them in allLikelyKeyLengths so that they are easier to
129     # use later.
130     allLikelyKeyLengths = []
131     for twoIntTuple in factorsByCount:
132         allLikelyKeyLengths.append(twoIntTuple[0])
133 
134     return allLikelyKeyLengths
135 
136 
137 def getNthSubkeysLetters(n, keyLength, message):
138     # Returns every Nth letter for each keyLength set of letters in text.
139     # E.g. getNthSubkeysLetters(1, 3, 'ABCABCABC') returns 'AAA'
140     #      getNthSubkeysLetters(2, 3, 'ABCABCABC') returns 'BBB'
141     #      getNthSubkeysLetters(3, 3, 'ABCABCABC') returns 'CCC'
142     #      getNthSubkeysLetters(1, 5, 'ABCDEFGHI') returns 'AF'
143 
144     # Use a regular expression to remove non-letters from the message.
145     message = NONLETTERS_PATTERN.sub('', message)
146 
147     i = n - 1
148     letters = []
149     while i < len(message):
150         letters.append(message[i])
151         i += keyLength
152     return ''.join(letters)
153 
154 
155 def attemptHackWithKeyLength(ciphertext, mostLikelyKeyLength):
156     # Determine the most likely letters for each letter in the key.
157     ciphertextUp = ciphertext.upper()
158     # allFreqScores is a list of mostLikelyKeyLength number of lists.
159     # These inner lists are the freqScores lists.
160     allFreqScores = []
161     for nth in range(1, mostLikelyKeyLength + 1):
162         nthLetters = getNthSubkeysLetters(nth, mostLikelyKeyLength, ciphertextUp)
163 
164         # freqScores is a list of tuples like:
165         # [(<letter>, <Eng. Freq. match score>), ... ]
166         # List is sorted by match score. Higher score means better match.
167         # See the englishFreqMatchScore() comments in freqAnalysis.py.
168         freqScores = []
169         for possibleKey in LETTERS:
170             decryptedText = vigenereCipher.decryptMessage(possibleKey, nthLetters)
171             keyAndFreqMatchTuple = (possibleKey, freqAnalysis.englishFreqMatchScore(decryptedText))
172             freqScores.append(keyAndFreqMatchTuple)
173         # Sort by match score
174         freqScores.sort(key=getItemAtIndexOne, reverse=True)
175 
176         allFreqScores.append(freqScores[:NUM_MOST_FREQ_LETTERS])
177 
178     if not SILENT_MODE:
179         for i in range(len(allFreqScores)):
180             # use i + 1 so the first letter is not called the "0th" letter
181             print('Possible letters for letter %s of the key: ' % (i + 1), end='')
182             for freqScore in allFreqScores[i]:
183                 print('%s ' % freqScore[0], end='')
184             print() # print a newline
185 
186     # Try every combination of the most likely letters for each position
187     # in the key.
188     for indexes in itertools.product(range(NUM_MOST_FREQ_LETTERS), repeat=mostLikelyKeyLength):
189         # Create a possible key from the letters in allFreqScores
190         possibleKey = ''
191         for i in range(mostLikelyKeyLength):
192             possibleKey += allFreqScores[i][indexes[i]][0]
193 
194         if not SILENT_MODE:
195             print('Attempting with key: %s' % (possibleKey))
196 
197         decryptedText = vigenereCipher.decryptMessage(possibleKey, ciphertextUp)
198 
199         if detectEnglish.isEnglish(decryptedText):
200             # Set the hacked ciphertext to the original casing.
201             origCase = []
202             for i in range(len(ciphertext)):
203                 if ciphertext[i].isupper():
204                     origCase.append(decryptedText[i].upper())
205                 else:
206                     origCase.append(decryptedText[i].lower())
207             decryptedText = ''.join(origCase)
208 
209             # Check with user to see if the key has been found.
210             print('Possible encryption hack with key %s:' % (possibleKey))
211             print(decryptedText[:200]) # only show first 200 characters
212             print()
213             print('Enter D for done, or just press Enter to continue hacking:')
214             response = input('> ')
215 
216             if response.strip().upper().startswith('D'):
217                 return decryptedText
218 
219     # No English-looking decryption found, so return None.
220     return None
221 
222 
223 def hackVigenere(ciphertext):
224     # First, we need to do Kasiski Examination to figure out what the
225     # length of the ciphertext's encryption key is.
226     allLikelyKeyLengths = kasiskiExamination(ciphertext)
227     if not SILENT_MODE:
228         keyLengthStr = ''
229         for keyLength in allLikelyKeyLengths:
230             keyLengthStr += '%s ' % (keyLength)
231         print('Kasiski Examination results say the most likely key lengths are: ' + keyLengthStr + '\n')
232 
233     for keyLength in allLikelyKeyLengths:
234         if not SILENT_MODE:
235             print('Attempting hack with key length %s (%s possible keys)...' % (keyLength, NUM_MOST_FREQ_LETTERS ** keyLength))
236         hackedMessage = attemptHackWithKeyLength(ciphertext, keyLength)
237         if hackedMessage != None:
238             break
239 
240     # If none of the key lengths we found using Kasiski Examination
241     # worked, start brute-forcing through key lengths.
242     if hackedMessage == None:
243         if not SILENT_MODE:
244             print('Unable to hack message with likely key length(s). Brute forcing key length...')
245         for keyLength in range(1, MAX_KEY_LENGTH + 1):
246             # don't re-check key lengths already tried from Kasiski
247             if keyLength not in allLikelyKeyLengths:
248                 if not SILENT_MODE:
249                     print('Attempting hack with key length %s (%s possible keys)...' % (keyLength, NUM_MOST_FREQ_LETTERS ** keyLength))
250                 hackedMessage = attemptHackWithKeyLength(ciphertext, keyLength)
251                 if hackedMessage != None:
252                     break
253     return hackedMessage
254 
255 
256 # If vigenereHacker.py is run (instead of imported as a module) call
257 # the main() function.
258 if __name__ == '__main__':
259     main()