古典密码-代换密码

之前密码都能被计算机通过暴力的方式进行破解,代换密码则包含了足够多的可能秘钥数量,在加密字符及足够多的情况下使得计算机都无法通过暴力算法进行破解。

章节:

  1. 代换密码加解密原理
  2. 代码密码破解原理:单词模式、基于单词模式寻找密钥
  3. 代换密码加解密代码+应用
  4. 代换密码破解代码+应用

1 代换密码加解密原理

简单代换密码的加密原理非常容易理解。简单代换密码将随机排列的字符集作为密钥,密钥和字符集按照排序呈现一一对应的关系,在加密时明文字符按照自己的字符集下标将自己映射到密钥上,从而得到加密字符。

举例说明:

存在26个英语字母的字符集,如下:

将上述字符集随机排列,生成代码密码的密钥,如下:

字符集和密钥则存在如下映射关系:

根据对应关系,对“SEEING IS BELIEVING”进行代换加密,加密过程如下:

“SEEING IS BELIEVING”被加密后的密文为“FIIZCK ZF EITZIDZCK”。

在进行解密工作时,将字符集和密钥的映射关系反过来即可,即解密映射关系如下:

根据上述解密映射关系,对“FIIZCK ZF EITZIDZCK”进行代换解密,过程如下:

成功对密文进行解密后,明文为“SEEING IS BELIEVING”。

2 代换密码破解原理

当字符集为26个英语字母时,可能的密钥数则为26!=403291461126605635584000000个密钥,面对如此巨大的密钥数量暴力破解不再为合适的破解方式。我们可以从代换密码的一些特征入手,来尝试减少需要尝试的密钥数量。

2.1 单词模式

观察密文和密文的关系,明文“SEEING IS BELIEVING”对应的密文为“FIIZCK ZF EITZIDZCK”。从对应关系可以看出明文单词“BELIEVING”对应的密文单词为“EITZIDZCK”;明文单词“BELIEVING”中字母B的数量为1、E为2、L为1、I为2、V为1、N为1、G为1;密文单词“EITZIDZCK”中字母E的数量为1、I为2、T为1、Z为2、D为1、C为1、K为1。

从上述分析中可以发现明文单词和密文单词中字母的重复次数、位置都是相同的。我们将“BELIEVING”单词第一个出现的字母编号为0,第二个出现的字母编号为1,以此类推。那么可以用单词模式“0.1.2.3.1.4.3.5.6”来表示“BELIEVING”单词中字母的位置信息和重复的情况;与之对应的密文单词“EITZIDZCK”也同样可以用单词模式“0.1.2.3.1.4.3.5.6”进行表示。

从上述分析中我们可以发现,代换加密的明文单词和密文单词的单词模式是相同的。

2.2 基于单词模式寻找密钥

既然明文单词和密文单词的单词模式相同,那么对于单词模式为“0.1.2.3.1.4.3.5.6”的密文单词“EITZIDZCK”来说,只有同样满足单词模式为“0.1.2.3.1.4.3.5.6”的可读单词,才有可能是“EITZIDZCK”的明文单词。于是我们可以从常用英语单词中寻找出满足单词模式为“0.1.2.3.1.4.3.5.6”的可读单词作为候选的明文单词。

这些候选的明文单词如下:

  • BELIEVING
  • FANTASTIC
  • INTENSELY
  • RADIATING
  • RADIATION
  • RELIEVING
  • REVIEWING
  • VARIATION

即如上候选明文单词都有可能是密文单词“EITZIDZCK”对应的明文单词。

若密文单词“EITZIDZCK”对应的明文单词是“BELIEVING”,那么E、I、T、Z、D、C、K字母对应的解密字母如下:

若密文单词“EITZIDZCK”对应的明文单词是“FANTASTIC”,那么E、I、T、Z、D、C、K字母对应的解密字母如下:

以此类推通过密文单词“EITZIDZCK”和候选的明文单词,我们可以得到“EITZIDZCK”中E、I、T、Z、D、C、K密文字符对应的可能解密字母,如表 1所示。

对上表中的对应关系进行整理,即仅通过分析“EITZIDZCK”密文单词可以得到如下结果:

  • 密文字母E可能的解密字母为:B、F、I、R、V
  • 密文字母I可能的解密字母为:E、A、N
  • 密文字母T可能的解密字母为:L、N、T、D、V、R
  • 密文字母D可能的解密字母为:I、T、E
  • 密文字母Z可能的解密字母为:V、S、T、W
  • 密文字母C可能的解密字母为:N、I、L、O
  • 密文字母K可能的解密字母为:G、C、Y、N

将上述映射关系添加到26个字母的关系映射字典中,则分析“EITZIDZCK”密文单词后映射关系如下:

{'A': [],
 'B': ['B', 'F', 'I', 'R', 'V'],
 'C': ['N', 'I', 'L', 'O'],
 'D': ['I', 'T', 'E'],
 'E': [],
 'F': [],
 'G': [],
 'H': [],
 'I': ['E', 'A', 'N'],
 'J': [],
 'K': ['H', 'C', 'Y', 'N'],
 'L': [],
 'M': [],
 'N': [],
 'O': [],
 'P': [],
 'Q': [],
 'R': [],
 'S': [],
 'T': ['L', 'M', 'T', 'D', 'V', 'R'],
 'U': [],
 'V': [],
 'W': [],
 'X': [],
 'Y': [],
 'Z': ['V', 'S', 'T', 'W']}

对于密文中其他的每个密文单词通过如上方法都可以得到一个映射关系。例如密文单词“SEEING”,其单词模式为“0.1.1.2.3.4”,在通常英语单词中寻找出满足单词模式为“0.1.1.2.3.4”的可读单词作为候选的明文单词。这些候选的明文单词如下:

ABBEYS ABBOTS ACCENT ACCEPT ACCORD ACCOST ACCRUE ACCUSE ADDERS ADDICT ADDING ADDUCE ADDUCT AFFECT AFFIRM AFFORD AGGIES ALLEYS ALLIED ALLIES ALLOTS ALLOWS ALLOYS ALLUDE ALLURE ANNOYS ANNULI ANNULS APPEND APPLES ARREST ARRIVE ARROWS ASSENT ASSERT ASSIGN ASSORT ASSUME ASSURE ATTEND ATTICS ATTIRE ATTUNE BOOKED BOOKER BOOKIE BOOMED BOOTED BOOTES BOOTHS BOOTLE COOING COOKED COOKIE COOLED COOLER COOLEY COOLIE COOPED COOPER DEEPLY DOOLEY EBBING EFFIGY EFFORT ELLIOT ERRAND ERRANT ERRING FEEBLY FOOLED FOOTED FOOTER GOODBY GOODLY GOOFED HOOKED HOOKER HOOKUP HOOPER HOOTED HOOTER HOOVER HOOVES IMMUNE INNATE ISSUED ISSUER KEEGAN KEENLY LEEWAY LOOKED LOOKER LOOKUP LOOMED LOOMIS LOOPED LOOSED LOOSEN LOOSER LOOTED LOOTER MCCABE MEEKLY MOONED MOONEY MOORED NOODLE OCCULT OCCUPY OCCURS ODDEST ODDITY OFFEND OFFERS OFFICE OFFING OFFSET OSSIFY OTTERS POODLE POOLED POORLY ROOFED ROOKIE ROOMED ROONEY ROOTED SEEING SEEMLY SOONER SOOTHE TOOLED TOOLER TOOMEY ULLMAN UTTERS WEEKLY WOODEN WOOFED WOOFER WOOING WOOLEN

通过密文单词“SEEING”和候选的明文单词,我们可以得到“SEEING”中S、E、I、N、G密文字符对应的可能解密字母,映射关系如下:

{'A': [],
 'B': [],
 'C': [],
 'D': [],
 'E': ['B', 'C', 'D', 'F', 'G', 'L', 'N', 'P', 'R', 'S', 'T', 'O', 'E', 'M'],
 'F': [],
 'G': ['S', 'T', 'D', 'E', 'G', 'M', 'I', 'N', 'R', 'Y', 'P'],
 'H': [],
 'I': ['E', 'O', 'R', 'U', 'I', 'L', 'K', 'M', 'T', 'P', 'A', 'B', 'D', 'F', 'V', 'G', 'N', 'W', 'S'],
 'J': [],
 'K': [],
 'L': [],
 'M': [],
 'N': ['Y', 'T', 'N', 'P', 'R', 'S', 'U', 'C', 'E', 'W', 'D', 'L', 'V', 'G', 'M', 'I', 'H', 'O', 'B', 'A', 'F'],
 'O': [],
 'P': [],
 'Q': [],
 'R': [],
 'S': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'K', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'U', 'W'],
 'T': [],
 'U': [],
 'V': [],
 'W': [],
 'X': [],
 'Y': [],
 'Z': []}

接下来将密文单词 “SEEING”得到的新的映射字典与已有映射字典进行交叉处理。

在已有的映射字典中若某些字符还没有对应的可能字符,则直接将新映射字典中这些字符的映射关系添加到已有映射字典中。即将如下映射关系直接添加到已有字典映射关系中:

'E': ['B', 'C', 'D', 'F', 'G', 'L', 'N', 'P', 'R', 'S', 'T', 'O', 'E', 'M'],
'G': ['S', 'T', 'D', 'E', 'G', 'M', 'I', 'N', 'R', 'Y', 'P'],
'I': ['E', 'O', 'R', 'U', 'I', 'L', 'K', 'M', 'T', 'P', 'A', 'B', 'D', 'F', 'V', 'G', 'N', 'W', 'S'],
'N': ['Y', 'T', 'N', 'P', 'R', 'S', 'U', 'C', 'E', 'W', 'D', 'L', 'V', 'G', 'M', 'I', 'H', 'O', 'B', 'A', 'F'],
'S': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'K', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'U', 'W'],

若在已有的映射字典中和新映射字典中的某些字符都有着映射关系,那么则取它们之间的交集替来换已有的映射字典中原来的映射关系。例如在已有的关系中字符“I”映射关系如下:

'I': ['E', 'A', 'N'],

新的“SEEING”得到的字符“I”的映射关系如下:

'I': ['E', 'O', 'R', 'U', 'I', 'L', 'K', 'M', 'T', 'P', 'A', 'B', 'D', 'F', 'V', 'G', 'N', 'W', 'S'],

则取它们的交集如下,即字符“I”的可能映射字符从3个减少到2个。

'I': ['E', 'N'],

最终,新的已有的映射关系如下:

{'A': [],
 'B': ['B', 'F', 'I', 'R', 'V'],
 'C': ['N', 'I', 'L', 'O'],
 'D': ['I', 'T', 'E'],
 'E': ['B', 'C', 'D', 'F', 'G', 'L', 'N', 'P', 'R', 'S', 'T', 'O', 'E', 'M'],
 'F': [],
 'G': ['S', 'T', 'D', 'E', 'G', 'M', 'I', 'N', 'R', 'Y', 'P'],
 'H': [],
 'I': ['E', 'A',],
 'J': [],
 'K': ['H', 'C', 'Y', 'N'],
 'L': [],
 'M': [],
 'N': ['Y', 'T', 'N', 'P', 'R', 'S', 'U', 'C', 'E', 'W', 'D', 'L', 'V', 'G', 'M', 'I', 'H', 'O', 'B', 'A', 'F'],
 'O': [],
 'P': [],
 'Q': [],
 'R': [],
 'S': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'K', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'U', 'W'],
 'T': ['L', 'M', 'T', 'D', 'V', 'R'],
 'U': [],
 'V': [],
 'W': [],
 'X': [],
 'Y': [],
 'Z': ['V', 'S', 'T', 'W']}

破解代换密码便是对密文中每个密文单词进行如上的过程,当某个字符的映射关系中减少到1个时,那么就可以确定该密文字符对应的明文字符便是映射关系中仅存的这个字符。即使密文字母不能都被成功破解,但也能获得大部分密文字母的映射关系,从而解密出大部分密文。

从破解原理中可知,密文中的密文单词越多,那么映射关系之间出现彼此重叠的可能性就越大,每个密文字符可能的对应字符就越少。即,密文越长,代换密钥越容易被破解。

3. 代换密码加解密代码+应用

加解密代码函数:

def simpleSubTranslate(text,key,mode):
    """
    Args:
        text (str, optional): [加解密字符串].
        key (int, optional): [密钥].
        mode (int, optional): [加解:1,,解密:0].
    """  
    LERTTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    charsA = LERTTERS
    charsB = key
    # 加解密后的字符
    resultText = ""
    if mode == 0:
        charsA,charsB = charsB,charsA
    for itemText in text:
        if itemText.upper() in charsA:
            itemTextIndex = charsA.find(itemText.upper())
            if itemText.isupper():
                resultText += charsB[itemTextIndex].upper()
            else:
                resultText += charsB[itemTextIndex].lower()
        else:
            resultText += itemText
    return resultText

对如下明文进行加密:

There are moments in life when you miss someone so much that you just want to pick them from your dreams and hug them for real! Dream what you want to dream;go where you want to go;be what you want to be,because you have only one life and one chance to do all the things you want to do.May you have enough happiness to make you sweet,enough trials to make you strong,enough sorrow to keep you human,enough hope to make you happy? Always put yourself in others’shoes.If you feel that it hurts you,it probably hurts the other person, too.The happiest of people don’t necessarily have the best of everything;they just make the most of everything that comes along their way.Happiness lies for those who cry,those who hurt, those who have searched,and those who have tried,for only they can appreciate the importance of people.

随机生成密钥,然后加密:

加密后的密文为:

Zyglg xlg iqiguzw ju njag sygu kqr ijww wqigqug wq irvy zyxz kqr erwz sxuz zq tjvd zygi alqi kqrl plgxiw xup yro zygi aql lgxn! Plgxi syxz kqr sxuz zq plgxi;oq syglg kqr sxuz zq oq;fg syxz kqr sxuz zq fg,fgvxrwg kqr yxcg qunk qug njag xup qug vyxuvg zq pq xnn zyg zyjuow kqr sxuz zq pq.Ixk kqr yxcg guqroy yxttjugww zq ixdg kqr wsggz,guqroy zljxnw zq ixdg kqr wzlquo,guqroy wqllqs zq dggt kqr yrixu,guqroy yqtg zq ixdg kqr yxttk? Xnsxkw trz kqrlwgna ju qzyglw’wyqgw.Ja kqr aggn zyxz jz yrlzw kqr,jz tlqfxfnk yrlzw zyg qzygl tglwqu, zqq.Zyg yxttjgwz qa tgqtng pqu’z ugvgwwxljnk yxcg zyg fgwz qa gcglkzyjuo;zygk erwz ixdg zyg iqwz qa gcglkzyjuo zyxz vqigw xnquo zygjl sxk.Yxttjugww njgw aql zyqwg syq vlk,zyqwg syq yrlz, zyqwg syq yxcg wgxlvygp,xup zyqwg syq yxcg zljgp,aql qunk zygk vxu xttlgvjxzg zyg jitqlzxuvg qa tgqtng.

对上面密文进行解密:

4. 代换密码加解密代码+应用

破解代码:

LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def getWordPattern(word):
    word = word.upper()
    nextNum = 0
    letterNums = {}
    wordPattern = []
    for letter in word:
        if letter not in letterNums:
            letterNums[letter] = str(nextNum)
            nextNum += 1
        wordPattern.append(letterNums[letter])
    return '.'.join(wordPattern)
    
def getAllWordPatterns():
    allPatterns = {}
    if os.path.exists('allWordPatterns.json'):
        print("文件‘{}\\allWordPatterns.json’ 存在,加载单词模式字典...".format(os.getcwd()))
        with open('allWordPatterns.json','r+') as file:
            content=file.read()
        allPatterns=json.loads(content)
        print("读取字典成功!")
        return allPatterns
    else:
        print("文件‘{}\\allWordPatterns.json’ 不存在!".format(os.getcwd()))
        if os.path.exists('dictionary.txt'):
            print("文件‘{}\\dictionary.txt’ 存在,生成单词模式字典...".format(os.getcwd()))
            with open('dictionary.txt','r+') as file:
                wordList = file.read().split('\n')
            for word in wordList:
                pattern = getWordPattern(word)
                if pattern not in allPatterns:
                    allPatterns[pattern] = [word]
                else:
                    allPatterns[pattern].append(word)
            with open('allWordPatterns.json','w+') as file:
                file.write(json.dumps(allPatterns))
                print("文件‘{}\\allWordPatterns.json’ 文件生成成功!".format(os.getcwd()))
                print("读取字典成功!")
        return allPatterns
        
def addLettersToMapping(intersectedMap,cipherWordItem,candidate):
    for i in range(len(cipherWordItem)):
        if candidate[i] not in intersectedMap[cipherWordItem[i]]:
            intersectedMap[cipherWordItem[i]].append(candidate[i])

def intersectedMappings(mapA,mapB):
    intersectedMapping = getBlankCipherletterMapping()
    for letter in LETTERS:
        if mapA[letter] == []:
            intersectedMapping[letter] = copy.deepcopy(mapB[letter])
        elif mapB[letter] == []:
            intersectedMapping[letter] = copy.deepcopy(mapA[letter])
        else:
            for mappedLetter in mapA[letter]:
                if mappedLetter in mapB[letter]:
                    intersectedMapping[letter].append(mappedLetter)
    return intersectedMapping

def removeSolvedLettersFromMapping(letterMapping):
    loopAgain = True
    while loopAgain:
        loopAgain = False
        solvedLetters = []
        for cipherletter in LETTERS:
            if len(letterMapping[cipherletter]) == 1:
                solvedLetters.append(letterMapping[cipherletter][0])
        for cipherletter in LETTERS:
            for s in solvedLetters:
                if len(letterMapping[cipherletter]) != 1 and s in letterMapping[cipherletter]:
                    letterMapping[cipherletter].remove(s)
                    if len(letterMapping[cipherletter]) == 1:
                        loopAgain = True
    return letterMapping
    
def getBlankCipherletterMapping():
    intersectedMap = {'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':[]}
    return intersectedMap

# 根据映射关系,将模糊字母用下划线替代
def decryptWithCipherletterMapping(cipherText,resultMap):
    key = ['x'] * len(LETTERS)
    for cipherletter in LETTERS:
        if len(resultMap[cipherletter]) == 1:
            keyIndex = LETTERS.find(resultMap[cipherletter][0])
            key[keyIndex] = cipherletter
        else:
            cipherText = cipherText.replace(cipherletter.lower(),'_')
            cipherText = cipherText.replace(cipherletter.upper(),'_')
    return ''.join(key),cipherText

# 返回映射关系
def hackSimpleSub(message):
    intersectedMap = getBlankCipherletterMapping()
    cipherWordList = re.compile('[^A-Z\s]').sub('',message.upper()).split()
    allPatterns = getAllWordPatterns()
    for cipherWordItem in cipherWordList:

        candidateMap = getBlankCipherletterMapping()
        wordPattern = getWordPattern(cipherWordItem)

        # 当前单词不在单词模式字典中
        if wordPattern not in allPatterns:
            continue

        for candidate in allPatterns[wordPattern]:
            addLettersToMapping(candidateMap,cipherWordItem,candidate)

        intersectedMap = intersectedMappings(intersectedMap,candidateMap)
    resultMap = removeSolvedLettersFromMapping(intersectedMap)
    return decryptWithCipherletterMapping(message,resultMap)

并不能完全破解,只能破解部分,不过已经很好识别了。人为的观察然后填入字母,就可以找到对应关系了。

破解出的明文:

_here are _o_en_s in li_e _hen yo iss so_eone so ch _ha yo_ _s an o pic he ro yo_r rea_s an h_g he or real! _rea ha yo_ an o _rea;go here yo an o go;_e _ha yo_ an o _e,_eca_se yo ha_e only one li_e an_ one chance o _o all _he _hings yo an o _o._ay yo ha_e eno_gh happiness o _a_e yo s_ee_,eno_gh rials _o _a_e yo s_rong,eno_gh sorro_ o _eep yo h__an,eno_gh hope o _a_e yo happy? Al_ays p yo_rsel_ in o_hers’shoes.I_ yo_ eel _ha i_ h_r_s yo_,i_ pro_a_ly h_r_s he o_her person, _oo._he happies o_ people on’ necessarily ha_e he _es o_ e_ery_hing;hey __s a_e _he _os o_ e_ery_hing ha co_es along heir _ay.Happiness lies _or _hose _ho cry,_hose _ho h_r, hose _ho ha_e searche,an_ hose _ho ha_e _rie,or only _hey can apprecia_e _he i_por_ance o people.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注