Vigenere break

​ 替换密码当中，Vigenere是一种安全性较高运用范围广的密码算法，比赛中也经常出相关的题。本篇通过两道例题系统学习Vigenere及其推广的破解方法。

一.Vigenere原理

​ 实际上是移位密码的推广，每一个明文字符对应的增量不同：

二.基本类型及其破解思路

​ task.py：

from string import ascii_letters
from flag import flag


ctoi = lambda x: ascii_letters.index(x)
itoc = lambda x: ascii_letters[x]

key = flag.strip('NCTF{}')
len_key = len(key)

plaintext = open('plaintext.txt', 'r').read()

plain = ''.join(p for p in plaintext if p in ascii_letters)
cipher = ''.join( itoc( ( ctoi(p) + ctoi( key[i % len_key] ) ) % 52 )  for i,p in enumerate(plain) )

open('ciphertext.txt', 'w').write(cipher)

​ 密文：

nsfAIHFrMuLynuCApeEstxJOzniQuyBVfAChDEznppfAiEIDcyNFBsCjsLvGlDtqztuaHvHbCmuyGNsIMhGlDtbotCoDzDjhyBzHGfHGfoHsuhlssIMvwlixBHHGfDRjoCKrapNIwqNyuxIBACQhtMwCmMCfEBpsrzEuiLGBoMipTkxrznoHfAkqwzvxuzCzDbLyApCGvjpqxkuwpgsLrqsVfCRwzlFmtlyrhuyEiivruFRpCRjkEDrqEqthyGwgsLnQvHmtzwDEznopBpsDOxvgBGIKzurFQxwQxkptutxzmfeLFQoRpJRvrpHxilwqeqMeiiIGBsQpCCvrptAlHsDnuRltmHuCGFpsBcwnsEblsswEPwerNpIADpJRCvwQxrntJltNpfAuFBwRstytoyvcepwtwqNlmmNGFsJjsQvkyvrkrstxJOzniQvNvzdDUdyJzjqzsErqxEjguyFMNwtPjsDwjoDfCdxzvftNGyzKjCEjsDxjqsjGMqFpimGpIADpJRFkovHJlpthyHnpqyBOHhmDMmoosClwiehEzmffOGMvDxDSnnyLuXFlwYEPvosQxCrRxwCpDswHopxDruvEzsOgBsXxDLvvlMpezwpnOOsjrANzHDsLCnoqLCepgtaHNHfpysNHGfOMqkyvlozxHetJGfvNuCGKjIRnoDLAbpyxnJCpqeLxuBCuwCpGpOnkEywrEPrisHrItSiDQgvtLCipyJnDzwtxBnNoKxpWuCxwuiqwDmIJxffIqSGSbzGpqlDnXvNIwqNzoxBrQoXuDRjonsAozzHeBjweTBBypDtIGnvHGDiosItqGvusGrIFzoNRjsyykrExweMvDtsLGItVbAIkxrFnuEyDmuIzxMNBIyziDJfyqLqbmjAtqOEiivnwyNgwCtmzsCgFxIfEMEiiBrFzNgxRdEEKqbHtJltIEmiNzygGfHyknVwnmJtJrxvyewNBSCTsHCnptxHlFiDnJHtohmuyKztHRkvwKxopfImuWFurIGuGRpGCcCDzntlxqevJCfEHLQoXxtIgzEynqEnCgsGztiLnHrBmDQgBEGCephprHJFtiFnHrXpJAqEwvBqlwItECpbvNuuHMvIRAwFKrZtyplMvJttFnSGhuLyuzwsHfyldhcvCjicGJzzztBvrlLBXxjHoDBlcsOGzwEuNWgkCKjdzBweDdHbwuyCHSmtIknezjqDtCeDDnfxBvHuzcDSvmlJAlFxtlIOsfCuyQoXtEJcIEznplrtsEIrtMNuIIFiIRjonsAozzHeBRltgFBMsCjCRjoHAwqpwIiCzzmhjuIsAfHyknTLFXDywevDCtxNvGsRitNtknLrZlqAyIvteeHLNvHovqjoAJxYlgAyvJChsNFBsVbHQwzAGBboyDbuNzsiuGGslbNzglpujrDjxtIvCpyHqWvQjHRokDaBXtihhuyterNFuMzoNRjsyyFepsXsqDouluGmvDqGMdkmDHoprtmrzCfhMuyKztHSrzzKnaEtqeIJCfeNzyRNzDSykyLClrtuoHvCjhyBHwSJHyknTCwbHxweFMzcevySrHelFgxDzntlxptyIJmmNGFsJjsypnLDufpfCdTWlohcHMsCuDEqDzLqbAfGkMDEilyEMvDxpQokosklFyIhuxlsvIHMsKZDSeyFDmkElttxzCpjzGBsFpsBcwEzrkrNBtEJmjkMuyGzjsgvrzMpeExweMvDoxABCBFuDypCHwAjpgJtICpemxaIMNvGCpyEYxlyNAlMvtujIESofpDLKClAmTpBtruMthlNGBsQfIFgxeznopBtruvqfAEvxGQjsGpqzFrqxtHtBTGfvSyCHSmtIknDswalktwFvCfrNFQsQfLykDtFpXCtJntJFuwCqyGHuIGpqzFCepgtnsCpteHquzKXwyvSoAmtlxXwuIEvtNBNvDxxLfyHOqbCjIhuTDfpFGBsSjrIgDDswamtJgxOzmhjuIsAfpRkmvwCQsjCIwvGfmNGIvDshFgGlKBqlssiDBCjkBGHsWuIMooSwAbTxpitrljxuFyqNosRcupLqbCjHtEAJpyLqIIFiIMqSDLjoEjsgyQtokBrLHGfGCuDzxCepiDuwCDiixyyBSntwqEvwnmtyZeuKtujIEGsRitQcsolqbyxweIvtevCtBHzgICtGlJmMwjpsuosbxMqyDQfHQkxrOqbyxDmuwzeCMnSGOmtyuoEGHlFNBeqItgmNFjvNfqCqBDGvbmtsyjCluhyCLsRttBvrpzniwtJtEAxfFOGcDTuIFgnzMpemfrkyIxztIpEsSBGCpDJGDdzsCaHDofxIBMvDbHIgnxwbepBpsBJzlmHtuHLfHMtDzxorysNYEPnpyFqNsKmHFgGlKwqEtDsEMpbxGruBXnDPgWlQkbTBxlBOsfryKNHHntgnvHsCZsDpIIvteKIGSCTsIGeupLhbDLDaxzlexBrHWKmqCqxEzrpmjCcxMthlNBPsQitPgSwDFXEhwyqdHfrNBPsQbCBukEvxtytCtxDDciHpBoMeHFgGpFCXyivoJJyulypuFQpJQgvdzntlqzetvwmeLBOBCjIgoolFBepBplAzoprwruzKuwCykJsAlFssiJosfrMuyGzusMyxzFCetxqiwwCpAHoyoSvEJqyvAwdzqshEMDfXBrHHGfrytBzMBbwxIaHOpeeHqcKzurFgnswAdzfGoKIobrxnLCTosrjoCwFbCjDnBTlcsOGzwUfDPusIGCepwzitNzoxBrLwCfpLfDswBlylIhuxlsvIHMsKxpQrvlQrkrBpsiHzliarNGHonMwBPQnpTyLaIKwbCCAAwSwtPAtlRIvlssfKIyzEFyNvDlxBuupHCqCDxnwOzhvuozCQuwCiywvAfylpntNzxeMBFroiDCdolFmFHfHsEMEpjusLoHeHFgnqsuizkutxzrphxnGvNsHCdEEamfosIsqTloCNuCBFpGBqkyQCetsvTxzEimHtQwSizGfCtKrcEmtyMvyuxItLoAuwCiywvAfylNoKClwiNBFsSuwConzACXyiCoJNlzeHLNvHovghDswHclqAovAEiiSsuzKpuDdEEACpmfsivTzvwuLuBXuwGpqEGCeprlhuIEiiLvxsVbHMxoCKqbrtIovAsfvBBLGDbCBekxwxspwIoCzjpyLvxsNorCvyzLqfDyxmuNsfwuvxbNJAJlEDLFXEhwyqdEimHxczKkJQvGlLleTxpitdrbzyuyFRpBCoyCwxcsjGdEPriLyEyUDuHMooxGAbEnrkuODTlyGICJuwCfyFyqlqkBeYHypxGnxoSzDScxJExopxweIvteMEAIKgvGPAEALqbEmxnwNrprHnMHzsIyiktFcepsplBJqbwOqxsMtwCikGwvblpxsIosfrMuyvDmsFgBsswazzIaDyDbmxVNGQbxLkxraCpDyprJDyhxIEuwMJzLqGeznkHmptICpemxvNrznCLgkCCriwjsmuNsfvynwvDexLoInGjqAtrkuOlohNBIyNvIKABpvqryyxnwClueHqJISjIMpwJznXoIDnJTzvAuANwSJHyknjGDZlsLeqMtueQuCzDPzyARFJAvFuIhEPrirIJsCTstEqxysvfDxNoKMCjhylIIVpCRioEQxrCtLnxJCtiIEuBXuwGpqdznhpuIhqIrjrAnLCTosRjyFyqAtiNoKHpbrCGQvzuNMwClAmVzzGeqGwzeLrHHFpxLikHsHXyDLhuMpBvyLIIQfpJnIrGrkrmDmuvquiLJuFCtHFgkDCnaxjneqCTteCqcADbCRkDEGxFHfHnJGJjrAGIvDsXPgkwDHativoxJxfezGyFVbGBuRFJAvFuCoMdDbmxgBsSixLiCDLjoEnCgiCpseHnHrApJEjDswAqthzeJvyekIGvoBlDLvrpyxaofBcqMCpyMrFxTtIGpDtEnQsjCsxzHbpErxoKmIFgGlQjozzCdyOEjpFFBsFpIFgBzOwezwHervnlXBrHGGfvMvyyACPsjLaLzousGruBCJLyxootjZvGDyyOmfkuANCQbxLnsvwjYlxIaHyTofOpEsStXQyolJClRtsABGEiiJnLsMuHypnxGCepwHaDypwiLLvCCzLCpDzNnolsssJJzevCtBHTosCtDswAlzkDfJCpdeLEIIRfAQqDswHtzzAdDOrfxMBuyDeIMvrpKtfytGaDTEimHtvISJHRwmvsAlFssoDOsffyAwvEpGOwsEwjtsnAeYBzutLrNHXtDymsyyFbEjHpuxtbpFLGMMfrIcxoEHmlsIscTsvrNvHuGbIPgkwDHdlAtmuLFjxynFCSpuNtyEwlqttCiDvHbCvHNWFpIQqkvwmXyDLaOdojhHGwoQfIFqErzRcpqIsEylnrBnJDXbAJqpDMmapsIhuRlzsFqjvNfqCmoALpltsvaHJFohuAxoQpJLfSHsBalrCnuvCceQyCBFJuCnDDGmXxswaFKJjjSBOKzoIRquyGFqsjIrKOsJhIANyMpLUjITLFXDoJsJOsbxMuyzNpzCfCzvjjysxcuOsfAuLMvDltNvqzAwdlwDuDylohuEIIMexLjoCturphDaJvyeeFyaCCJLGurJGDZzzAdLzmfiHGBsQfiFcDDsuiTrvoyIrusNrFzzcDSvSnGDiouGorvmmCNrFzXpJUjkEamfofutuMTxiHGBCLfpLfrzORdzyHisFlohuyFoMeLFcDDuqlzqXmIPAqsMrxHNhDRqxpPCclqAavOpsMArNCTuDDjoCwkrENsoDOqfiFyCyDjIgtolDuvotCtjCluwNHztCptQpDtFCbCjHtCzEpsGHwvQjvFvxzOJizyDfFzzqpyrMDDdxynvJLqfDtCeFNJdlInHoKzHRiEJLqbJmpvuCpsiEryDRbHIkxrEnfqNBgEDyheJCFMLzHCnpHznkTlDbqxvusMpBCNmCCzDdwyqprqeHdEtwOpBoRuJNknBMnpEnDnyIxzsJvHwNoXKgkyzxtotNoKFypAQuuHXpJPgqzAwdEtsoJDwmCIHxCHuiFgkyKFbCnHyEPoprNVNvHozgcwmMCezBsoYFypAcFQszsxRukDLDmtiFuuNEjsHQVwRoIyullvjpEmtruNEpjNuyAAvIFgupwyplxziDBxfeFBNCErJCuDtGwpEtDHuyCpzyBPsQmpQvclLDoofNwyOsulCFYBFmxQjlltnqsfIsyIEimMAyKOjrRwBpznpHwxtyIrTlyJuGOstRvIlxobnytdrPEwiLLACNeAMqutFpxyDLaOJyfxCzyKGfCQjoHwwqEtIhuGlemyFLCNnLyADswqbwqsoMItoxBrIHGfGUkxrVKXDptdCzHieNVNvNvvFvkmGDqlqAtxDDtxOszWIvHRhsyABepiIeBGtokSBOoApJRKntvwqvsDwMCluxBrBsKmIMukJaovzzLaDOEpoHBQHGfIPwDsamlyyznERHieNVNvHozydyFLrqTrHoHMJJxIyxGNnpLAzpGyipfqoKOtuEvBOHzmAgmxzOrpTxDrJJqnmMFyJDsNzqnJaClwipbEPEFzyAIzCTIPcnwsCbCfCdQxvmiSsIFHoHRcxnwRqsnCkYzGfrGvMGSipRiyovjjXfJryxpJxMsOBMzSMpDpNnoEjAlqIJcsxLuBXuwGpqTxHlFiDyEPDueLGGwRtxLioGwAvmtsy

1.Kasiski实验，Ci实验分析key的长度

​ Kasiski实验通过查找相同的子串(3个字符以上)来猜测可能的key的长度。比如两个相同的子串的距离相差8位,那么key的长度应该为8的因子,这样当我们有足够多的数据时就可以基本确定key的长度了。代码来自于https://github.com/ichantzaras/creamcrackerz。

from math import sqrt

def _repeated_seq_pos(text, seq_len):
    seq_pos = {}  # entries of sequence : [positions]
    for i, char in enumerate(text):
        next_seq = text[i:i+seq_len]
        if next_seq in seq_pos.keys():
            seq_pos[next_seq].append(i)
        else:
            seq_pos[next_seq] = [i]
    repeated = list(filter(lambda x: len(seq_pos[x]) >= 2, seq_pos))
    rep_seq_pos = [(seq, seq_pos[seq]) for seq in repeated]
    return rep_seq_pos


def _get_spacings(positions):
    return [positions[i+1] - positions[i] for i in range(len(positions)-1)]


def _get_factors(number):
    factors = set()
    for i in range(1, int(sqrt(number))+1):
        if number % i == 0:
            factors.add(i)
            factors.add(number//i)
    return sorted(factors)


def _candidate_key_lengths(factor_lists, max_key_len):
    all_factors = [factor_lists[lst][fac] for lst in range(len(factor_lists)) for fac in range(len(factor_lists[lst]))]
    # exclude factors larger than suspected max key length
    candidate_lengths = list(filter(lambda x:  x <= max_key_len, all_factors))
    # sort by probability (descending)
    sorted_candidates = sorted(set(candidate_lengths), key=lambda x: all_factors.count(x), reverse=True)
    return sorted_candidates


def find_key_length(cyphertext, seq_len, max_key_len):
    # find repeated sequences and their positions
    rsp = _repeated_seq_pos(text=cyphertext, seq_len=seq_len)
    seq_spc = {}
    for seq, positions in rsp:
        seq_spc[seq] = _get_spacings(positions)
    # calculate spacings between positions of each repeated
    # sequence and factor out spacings
    factor_lists = []
    for spacings in seq_spc.values():
        for space in spacings:
            factor_lists.append(_get_factors(number=space))
    # get common factors by descending frequency,
    # which constitute candidate key lengths
    ckl = _candidate_key_lengths(factor_lists=factor_lists, max_key_len=max_key_len)
    key_len = ckl[0]
    return key_len

​ Ci实验：

​ 重合指数：设一门语言由n个字母组成，每个字母出现的概率为 Pi ，则重合指数是指两个元素随机相同的概率之和，记作 CI =∑ Pi^2 (1<= i <= n)；

​ 经分析，英文中，一段文字是随机的话，CI =0.0385 ；如果这段文字是有意义的，那么 CI=0.065 （约等）。

​ 所以在获得key的长度之后可以通过分组计算CI再取平均值与0.065比较进一步确定key长度。

​ 公式：

$$\sum_{i=1}^{n} \frac{fi(fi-1)}{L(L-1)}$$

​ L 是指长度,f是指相应字符出现的次数。

import string
import processing
import freq_analysis as fa
from sys import maxsize
from const import EN_IC


def _ic(letter_counts):
    numerator = sum([letter_counts[l]*(letter_counts[l]-1) for l in string.ascii_uppercase])
    text_size = sum(occurrences for occurrences in letter_counts.values())
    denominator = text_size*(text_size-1)
    return numerator/denominator


def find_key_length(cyphertext, max_key_len):
    min_diff = maxsize
    key_len = 0
    for candidate_length in range(1, max_key_len + 1):
        groups = processing.get_blocks(text=cyphertext, size=candidate_length)
        columns = processing.get_columns(groups)
        ics = [_ic(letter_counts=fa.get_letter_counts(text=column)) for column in columns]
        delta_bar_ic = sum(ics) / len(ics)
        if EN_IC-delta_bar_ic < min_diff:
            min_diff = EN_IC-delta_bar_ic
            key_len = candidate_length
        print('KEY_LENGTH: ' + str(candidate_length) + '\n')
        print('IC by column: '+str(ics))
        print('delta bar IC: '+str(delta_bar_ic)+'\n')
    return key_len

2.频率分析

​ 通过密钥长度进行分组,如len(key)=8,则可以分成8组,每一组对应的密钥字母是一样的,这样我们就可以通过字母遍历来算出最符合字母频率的情况,这样单个密钥字母就基本确定下来了。即计算明文中的各字母的频率与英文字母中的频率的吻合程度。

import processing
import string
from const import EN_REL_FREQ


def get_letter_counts(text):
    text_upper = text.upper()
    letter_counts = {}
    for index, letter in enumerate(string.ascii_uppercase):
        letter_counts[letter] = text_upper.count(letter)
    return letter_counts


def _get_letter_frequencies(text):
    letter_counts = get_letter_counts(text)
    frequencies = {letter: count/len(text) for letter, count in letter_counts.items()}
    return frequencies


def shift(text, amount):
    shifted = ''
    letters = string.ascii_uppercase
    for letter in text:
        shifted += letters[(letters.index(letter)-amount) % len(letters)]
    return shifted


def _corr(text, lf):
    return sum([(lf[letter]*EN_REL_FREQ[letter]) for letter in text])# 当解密出的明文取到最符合英文字符分布的组合的时候，sum值是最大的


def _find_key_letter(text, lf):
    key_letter = ''
    max_corr = 0
    for count, letter in enumerate(string.ascii_uppercase):
        shifted = shift(text=text, amount=count)
        corr = _corr(text=shifted, lf=lf)
        if corr > max_corr:
            max_corr = corr
            key_letter = letter
    return key_letter


def restore_key(cyphertext, key_len):
    key = ''
    blocks = processing.get_blocks(text=cyphertext, size=key_len)
    columns = processing.get_columns(blocks)
    frequencies = _get_letter_frequencies(text=cyphertext)
    for column in columns:
        key += _find_key_letter(text=column, lf=frequencies)
    return key

3.读取密文，getkey_len,getkey,解密

import kasiski
import ic
import processing
import freq_analysis as fa
from const import (SEQ_LEN, MAX_KEY_LEN)
import string


def _decypher(cyphertext, key):
    letters = string.ascii_uppercase
    shifts = [letters.index(letter) for letter in key]
    blocks = processing.get_blocks(text=cyphertext,size=len(key))
    cols = processing.get_columns(blocks)
    decyphered_blocks = processing.to_blocks([fa.shift(col, shift) for col, shift in zip(cols, shifts)])
    decyphered = ''.join(decyphered_blocks)
    return decyphered


def attack(file, method):
    with open(file) as f:
        cyphertext = f.readlines()
        key_len = 0
        if method == 'kasiski':
            print('Applying kasiski examination\n')
            key_len = kasiski.find_key_length(cyphertext=cyphertext[0], seq_len=SEQ_LEN, max_key_len=MAX_KEY_LEN)
        elif method == 'ic':
            print('Applying index of coincidence examination\n')
            key_len = ic.find_key_length(cyphertext=cyphertext[0], max_key_len=MAX_KEY_LEN)
        key = fa.restore_key(cyphertext[0], key_len)
        decyphered = _decypher(cyphertext[0], key)
        print('Chosen key length: '+str(key_len))
        print('Restored key: '+str(key))
        print('Plaintext: '+str(decyphered))



attack('encrypted/hostiletext.txt', 'kasiski')
#attack('encrypted/hostiletext.txt', 'ic')

​ 实际上，普通的维吉尼亚密码（基于26个数字—字母对or基于ascii字符表）可以直接用集成好的网站直接破解：https://www.guballa.de/vigenere-solver 所以上述题目可以直接用网站梭。

三.维吉尼亚变种类型