vigenere密码破解

Vigenere密码破解 By Toby QQ:2314692412 欢迎共同爱好者加QQ交流。 介绍： 单表代替密码的安全性不高，一个原因是一个明文字母只由一个密文字母代替。可以利用频率分析来破译。故产生了更为安全的多表代换密码，即构造多个密文字母表，在密钥的控制下用以一系列代换表依次对明文消息的字母序列进行代换。Vigenere是著名的多表代替密码。 用Python对vigenere密码进行自动化破解。 这只是Python版本，numpy版本算法更加优越，耗时更少。 程序测试截图 源码 import itertools,re import vigenereCipher,pyperclip,freqAnalysis,detectEnglish LETTERS='ABCDEFGHIJKLMNOPQRSTUVWXYZ' SILENT_MODE=False #if set to True,program does not print attempts NUM_MOST_FREQ_LETTERS=3 #attempts this many letters per subkey MAX_KEY_LENGTH=16 #will not attempt keys longer than this NONLETTERS_PATTERN=re.compile('[^A-Z]') fo=open('test.txt','r') ciphertext=fo.read() def main(ciphertext): hackedMessage=hackVigenere(ciphertext) if hackedMessage!=None: print hackedMessage else: print 'failed to hack encryption' def findRepeatSequencesSPacings(message): # Goes through the message and finds any 3 to 5 letter sequences # that are repeated. Returns a dict with the keys of the sequence and # values of a list of spacings (num of letters between the repeats). # Use a regular expression to remove non-letters from the message. message=NONLETTERS_PATTERN.sub('',message.upper()) #compile a list of seqLen-letter sequences found in the message seqSpacings={}  #keys are sequences,values are list of int spacings for seqLen in range(3,6): for seqStart in range(len(message)-seqLen+1): #Determine what the sequence is, and store it in seq seq=message[seqStart:seqStart+seqLen] #look for this sequence in the rest of the message for i in range(seqStart+seqLen,len(message)-seqLen+1): if message[i:i+seqLen]==seq: #found a repeated sequence if seq not in seqSpacings: seqSpacings[seq]=[] #initialize blank list #append the spacing distance between the repeated sequence and the original sequence seqSpacings[seq].append(i-seqStart) return seqSpacings ''' >>> findRepeatSequencesSPacings('appffkjfdfappfdsf') {'APPF': [10], 'APP': [10], 'PPF': [10]} >>>  >>> findRepeatSequencesSPacings('PPQCQPPQ') # test for details message is: PPQCQPPQ len(message) is: 8 seqLen is: 3 seqStart is: 0 seq is: PPQ i is: 3 message[i:i + seqLen] is: CQP i is: 4 message[i:i + seqLen] is: QPP i is: 5 message[i:i + seqLen] is: PPQ found repeat seqStart is: 1 seq is: PQC i is: 4 message[i:i + seqLen] is: QPP i is: 5 message[i:i + seqLen] is: PPQ seqStart is: 2 seq is: QCQ i is: 5 message[i:i + seqLen] is: PPQ seqStart is: 3 seq is: CQP seqStart is: 4 seq is: QPP seqStart is: 5 seq is: PPQ seqLen is: 4 seqStart is: 0 seq is: PPQC i is: 4 message[i:i + seqLen] is: QPPQ seqStart is: 1 seq is: PQCQ seqStart is: 2 seq is: QCQP seqStart is: 3 seq is: CQPP seqStart is: 4 seq is: QPPQ seqLen is: 5 seqStart is: 0 seq is: PPQCQ seqStart is: 1 seq is: PQCQP seqStart is: 2 seq is: QCQPP seqStart is: 3 seq is: CQPPQ the_seqSpacings is : {'PPQ': [5]} ''' def getUsefulFactors(num): # Returns a list of useful factors of num. By "useful" we mean factors # less than MAX_KEY_LENGTH + 1. For example, getUsefulFactors(144) # returns [2, 72, 3, 48, 4, 36, 6, 24, 8, 18, 9, 16, 12] if num<2: return[]  #numbers less than 2 have no useful factors factors=[]    # the list of factors found #when finding factors, you only need to check the integers up to MAX_KEY_LENGTH for i in range(2,MAX_KEY_LENGTH+1):  #do not test 1 if num%i==0: factors.append(i) factors.append(int(num/i)) if 1 in factors: factors.remove(1) return list(set(factors)) ''' >>> getUsefulFactors(144) [16, 2, 3, 4, 6, 72, 9, 12, 48, 8, 18, 24, 36] ''' def getItemAtIndexOne(x): return x[1] def getMostCommonFactors(seqFactors): #first,get a count of how many times a factor occurs in seqFactors. factorCounts={} #seqFactors keys are sequences,values are lists of factor of the spacing seqFactors has a value like: {'GFD': [2, 3, 4, 6, 9, 12, # 18, 23, 36, 46, 69, 92, 138, 207], 'ALW': [2, 3, 4, 6, ...], ...} for seq in seqFactors: factorList=seqFactors[seq] for factor in factorList: if factor not in factorCounts: factorCounts[factor]=0 factorCounts[factor]+=1   #two for circles to creat factorCounts dictionary #second,put the factor and its count into a tuple,and make a list of these tuples so we can sort them factorsByCount=[] for factor in factorCounts: #exclude factors large than MAX_KEY_LENGTH if factor<=MAX_KEY_LENGTH: # factorsByCount is a list of tuples: (factor, factorCount) # factorsByCount has a value like: [(3, 497), (2, 487), ...] factorsByCount.append((factor,factorCounts[factor])) #sort the list by the factor count. factorsByCount.sort(key=getItemAtIndexOne,reverse=True) return factorsByCount ''' >>> seqFactors={'GFD': [2, 3, 4, 6, 9, 12, 18, 23, 36, 46, 69, 92, 138, 207], 'ALW': [2, 3, 4, 6,]} >>> getMostCommonFactors(seqFactors) [(2, 2), (3, 2), (4, 2), (6, 2), (9, 1), (12, 1)] ''' def kasiskiExamination(ciphertext): # Find out the sequences of 3 to 5 letters that occur multiple times # in the ciphertext. repeatedSeqSpacings has a value like: # {'EXG': [192], 'NAF': [339, 972, 633], ... } repeatedSeqSpacings=findRepeatSequencesSPacings(ciphertext) #see getMostCommonFactors() for a description of seqFactors. seqFactors={} for seq in repeatedSeqSpacings:  # to loop every seq seqFactors[seq]=[]           #to creat a empty list for every seq for spacing in repeatedSeqSpacings[seq]: seqFactors[seq].extend(getUsefulFactors(spacing)) # See getMostCommonFactors() for a description of seqFactors. factorsByCount=getMostCommonFactors(seqFactors) # Now we extract the factor counts from factorsByCount and # put them in allLikelyKeyLengths so that they are easier to # use later. allikelyKeyLengths=[] for twoIntTuple in factorsByCount: allikelyKeyLengths.append(twoIntTuple[0]) return allikelyKeyLengths ''' >>> fo=open('test.txt','r') >>> ciphertext=fo.read() >>> kasiskiExamination(ciphertext) [3, 2, 6, 4, 12, 8, 9, 16, 5, 11, 10, 15, 7, 14, 13] >>>  ''' def getNthSubkeysLetters(n,keyLength,message): # Returns every Nth letter for each keyLength set of letters in text. # E.g. getNthSubkeysLetters(1, 3, 'ABCABCABC') returns 'AAA' #      getNthSubkeysLetters(2, 3, 'ABCABCABC') returns 'BBB' #      getNthSubkeysLetters(3, 3, 'ABCABCABC') returns 'CCC' #      getNthSubkeysLetters(1, 5, 'ABCDEFGHI') returns 'AF' # Use a regular expression to remove non-letters from the message. message=NONLETTERS_PATTERN.sub('',message) i=n-1 letters=[] while i>>  >>> message='ABCABCABC' >>> getNthSubkeysLetters(1,3,message) 'AAA' >>> getNthSubkeysLetters(2,3,message) 'BBB' >>> getNthSubkeysLetters(3,3,message) 'CCC' ''' def attemptHackWithKeyLength(ciphertext, mostLikelyKeyLength): # Determine the most likely letters for each letter in the key. ciphertextUp = ciphertext.upper() # allFreqScores is a list of mostLikelyKeyLength number of lists. # These inner lists are the freqScores lists. allFreqScores = [] for nth in range(1, mostLikelyKeyLength + 1): nthLetters = getNthSubkeysLetters(nth, mostLikelyKeyLength, ciphertextUp) # freqScores is a list of tuples like: # [(, ), ... ] # List is sorted by match score. Higher score means better match. # See the englishFreqMatchScore() comments in freqAnalysis.py. freqScores=[] for possibleKey in LETTERS: decryptedText=vigenereCipher.decryptMessage(possibleKey,nthLetters) keyAndFreqMatchTuple=(possibleKey,freqAnalysis.englishFreqMatchScore(decryptedText)) freqScores.append(keyAndFreqMatchTuple) #sort by match score freqScores.sort(key=getItemAtIndexOne,reverse=True) allFreqScores.append(freqScores[:NUM_MOST_FREQ_LETTERS]) if not SILENT_MODE: for i in range(len(allFreqScores)): # use i + 1 so the first letter is not called the "0th" letter print 'possible letters for letter %s of the key:' %(i+1) for freqScore in allFreqScores[i]: print '%s ' %freqScore[0] print # Try every combination of the most likely letters for each position in the key. for indexes in itertools.product(range(NUM_MOST_FREQ_LETTERS),repeat=mostLikelyKeyLength): # Create a possible key from the letters in allFreqScores possibleKey='' for i in range(mostLikelyKeyLength): possibleKey+=allFreqScores[i][indexes[i]][0] if not SILENT_MODE: print 'Attempting with key: %s' %(possibleKey) decryptedText=vigenereCipher.decryptMessage(possibleKey,ciphertextUp) if detectEnglish.isEnglish(decryptedText): # set the hacked ciphertext to the original casing origCase= [] for i in range(len(ciphertext)): if ciphertext[i].isupper(): origCase.append(decryptedText[i].upper()) else: origCase.append(decryptedText[i].lower()) decryptedText=''.join(origCase) # Check with user to see if the key has been found. print('Possible encryption hack with key %s:' % (possibleKey)) print(decryptedText[:200]) # only show first 200 characters print() print('Enter D for done, or just press Enter to continue hacking:') response = input('> ') if response.strip().upper().startswith('D'): return decryptedText # No English-looking decryption found, so return None. return None ''' allFreqScores [[('A', 8), ('L', 5), ('M', 5)], [('S', 8), ('N', 5), ('O', 5)], [('V', 9), ('I', 7), ('Z', 4)]] possible letters for letter 1 of the key: A  L  M  possible letters for letter 2 of the key: S  N  O  possible letters for letter 3 of the key: V  I  Z  indexes is: (0, 0, 0) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: ASV indexes is: (0, 0, 1) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: ASI indexes is: (0, 0, 2) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: ASZ indexes is: (0, 1, 0) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: ANV indexes is: (0, 1, 1) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: ANI indexes is: (0, 1, 2) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: ANZ indexes is: (0, 2, 0) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: AOV indexes is: (0, 2, 1) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: AOI indexes is: (0, 2, 2) allFreqScores[i][indexes[i]] is: ('A', 8) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: AOZ indexes is: (1, 0, 0) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: LSV indexes is: (1, 0, 1) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: LSI indexes is: (1, 0, 2) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: LSZ indexes is: (1, 1, 0) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: LNV indexes is: (1, 1, 1) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: LNI indexes is: (1, 1, 2) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: LNZ indexes is: (1, 2, 0) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: LOV indexes is: (1, 2, 1) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: LOI indexes is: (1, 2, 2) allFreqScores[i][indexes[i]] is: ('L', 5) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: LOZ indexes is: (2, 0, 0) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: MSV indexes is: (2, 0, 1) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: MSI indexes is: (2, 0, 2) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('S', 8) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: MSZ indexes is: (2, 1, 0) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: MNV indexes is: (2, 1, 1) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: MNI indexes is: (2, 1, 2) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('N', 5) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: MNZ indexes is: (2, 2, 0) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('V', 9) Attempting with key: MOV indexes is: (2, 2, 1) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('I', 7) Attempting with key: MOI indexes is: (2, 2, 2) allFreqScores[i][indexes[i]] is: ('M', 5) allFreqScores[i][indexes[i]] is: ('O', 5) allFreqScores[i][indexes[i]] is: ('Z', 4) Attempting with key: MOZ ''' def hackVigenere(ciphertext): # First, we need to do Kasiski Examination to figure out what the # length of the ciphertext's encryption key is. allLikelyKeyLengths = kasiskiExamination(ciphertext) if not SILENT_MODE: keyLengthStr = '' for keyLength in allLikelyKeyLengths: keyLengthStr += '%s ' % (keyLength) print('Kasiski Examination results say the most likely key lengths are: ' + keyLengthStr + '\n') for keyLength in allLikelyKeyLengths: if not SILENT_MODE: print('Attempting hack with key length %s (%s possible keys)...' % (keyLength, NUM_MOST_FREQ_LETTERS ** keyLength)) hackedMessage = attemptHackWithKeyLength(ciphertext, keyLength) if hackedMessage != None: break # If none of the key lengths we found using Kasiski Examination # worked, start brute-forcing through key lengths. if hackedMessage == None: if not SILENT_MODE: print('Unable to hack message with likely key length(s). Brute forcing key length...') for keyLength in range(1, MAX_KEY_LENGTH + 1): # don't re-check key lengths already tried from Kasiski if keyLength not in allLikelyKeyLengths: if not SILENT_MODE: print('Attempting hack with key length %s (%s possible keys)...' % (keyLength, NUM_MOST_FREQ_LETTERS ** keyLength)) hackedMessage = attemptHackWithKeyLength(ciphertext, keyLength) if hackedMessage != None: break return hackedMessage # If vigenereHacker.py is run (instead of imported as a module) call # the main() function. if __name__ == '__main__': main(ciphertext) ''' >>>  Kasiski Examination results say the most likely key lengths are: 3 2 6 4 12 8 9 16 5 11 10 15 7 14 13  Attempting hack with key length 3 (27 possible keys)...