【密码学】古典密码

Author Avatar
source. 1月 01, 2019
  • 在其它设备中阅读本文章

清醒的人最荒唐。

在本文中, $c_i$ 代表密文(Cipher)的第 $i$ 个字符,$m_i$ 代表明文(Message)的第 $i$ 个字符。

恺撒密码 Caesar cipher

概述

恺撒密码是一种单表代换密码,是仿射密码中的一种特殊情况。这个加密方法是以罗马共和时期恺撒的名字命名的,当年恺撒曾用此方法与其将军们进行联系。

狭义上,恺撒密码特指偏移量为 3 的情况。广义上,恺撒密码可以指所有在字母表上向后(或向前)按照一个固定数目进行偏移的密码。

例如,当偏移量是3的时候,所有的字母A将被替换成D,B变成E,以此类推。

img

算法实现

大写字母 A~Z 或小写字母 a~z 分别对应数字 0~25 。

加密算法

使用 ord() 函数获取字符对应的 ASCII 码,减去 ord('A')ord('a') 即可得到它对应的数字。

最后,加上 ord('A')ord('a') 后调用 chr() 方法即可得到它的密文。

# Encryption
def CaeserEncrypt(m,k):
    k %= 26
    ans = ""
    l = len(m)
    for i in range(l):
        if m[i].isupper():
            ans += chr((ord(m[i])-ord('A')+k)%26+ord('A'))
        elif m[i].islower():
            ans += chr((ord(m[i])-ord('a')+k)%26+ord('a'))
        else:
            ans += m[i]
    return ans

解密算法

解密算法是加密算法的逆运算,与加密算法类似。

# Decryption(normal)
def CaeserDecrypt(c,k):
    k %= 26
    ans = ""
    l = len(c)
    for i in range(l):
        if c[i].isupper():
            ans += chr((ord(c[i])-ord('A')+26-k)%26+ord('A'))
        elif c[i].islower():
            ans += chr((ord(c[i])-ord('a')+26-k)%26+ord('a'))
        else:
            ans += c[i]
    return ans

Q: 为什么要加 26 呢?

A: 因为 $c_i-k$ 有可能小于 0,在很多高级语言(如 C / C++、Java)中,若模运算左操作数小于 0 ,则结果也小于 0。(在 Python 中不加也行)

其他考虑

区分大写字母和小写字母

可以调用函数 isupper(), islower() 函数判断大小写。

大写字母加密/解密后的结果仍是大写字母,小写字母加密/解密后的结果仍是小写字母。

对于字母之外的字符

不做任何处理,密文就是明文,明文就是密文。

攻击方法

因为只有 25 种可能,故可采用穷举(暴力)攻击,给出密文,列出所有可能的明文,最后,根据明文中所包含的标识(如 flag)找出正确的明文。

# Decryption(exhaustive)
def BruteCaesarDecrypt(cipher):
    for i in range(1,26):
        print "k = "+str(i).zfill(2)+": ",
        print CaeserDecrypt(cipher,i)

对主函数的处理

有三种模式,运行程序时,先选择模式。

[E]Encryption [D]Decryption [B]Brute-Attack

为保证程序的健壮性,如输入所有 E 开头的字符串(或单个 E )则选择加密模式,同理,输入所有 D 开头的字符串选择解密模式,输入所有 B 开头的字符串选择穷举攻击模式。

完整代码

#-*- coding:utf-8 -*-
# Classical Cipher: Caesar Cipher

# Encryption
def CaesarEncrypt(m,k):
    k %= 26
    ans = ""
    l = len(m)
    for i in range(l):
        if m[i].isupper():
            ans += chr((ord(m[i])-ord('A')+k)%26+ord('A'))
        elif m[i].islower():
            ans += chr((ord(m[i])-ord('a')+k)%26+ord('a'))
        else:
            ans += m[i]
    return ans

# Decryption(normal)
def CaesarDecrypt(c,k):
    k %= 26
    ans = ""
    l = len(c)
    for i in range(l):
        if c[i].isupper():
            ans += chr((ord(c[i])-ord('A')+26-k)%26+ord('A'))
        elif c[i].islower():
            ans += chr((ord(c[i])-ord('a')+26-k)%26+ord('a'))
        else:
            ans += c[i]
    return ans

# Decryption(exhaustive)
def BruteCaesarDecrypt(cipher):
    for i in range(1,26):
        print "k = "+str(i).zfill(2)+": ",
        print CaesarDecrypt(cipher,i)

# Main function
def main():
    while True:
        op = raw_input("What do you want to do?\n[E]Encryption [D]Decryption [B]Brute-Attack\n").upper()

        if op[0] == "E":
            s = raw_input("Please enter your plaintext:\n\t")
            k = input("Please enter your key(1~25):\n\t")
            # s = "Haha CUMTer~"
            # k = 5
            # ********  Encryption  ********
            print 8*"*"+"  Encryption  "+8*"*"
            Encryption = CaesarEncrypt(s,k)
            print "The Ciphertext is:\n\t"+Encryption
            break

        elif op[0] == "D":
            s = raw_input("Please enter your ciphertext:\n\t")
            k = input("Please enter your key(1~25):\n\t")
            # ********  Decryption  ********
            print 8*"*"+"  Decryption  "+8*"*"
            Decryption = CaesarDecrypt(s,k)
            print "The Plaintext is:\n\t"+Decryption
            break

        elif op[0] == "B":
            # *******  Brute Attack  *******
            s = raw_input("Please enter your ciphertext:\n\t")
            print 7*"*"+"  Brute Attack  "+7*"*"
            BruteCaesarDecrypt(s)
            break
        else:
            continue

if __name__ == '__main__':
    main()

运行结果

加密

例如:明文是 Haha CUMTer~ ,偏移量(key)是 5 , 得到密文 Mfmf HZRYjw~ 。

img

已知 key 解密

例如:密文是 Mfmf HZRYjw~ ,偏移量(key)是 5 , 得到明文 Haha CUMTer~。

img

暴力枚举解密

例如:密文是 Mfmf HZRYjw~ ,不知道偏移量(key),暴力穷举出所有可能,再结合某些标识或使明文在自然语言中有意义,得到明文 Haha CUMTer~ 。

img

安全性分析

即使使用唯密文攻击,恺撒密码也是一种非常容易破解的加密方式。假如攻击者截获一段密文,确定(或猜测)密文使用了这种加密方式,都可以直接尝试使用穷举攻击(因为只有 25 种可能)。假如攻击者确定是使用了某种单表代换密码,也可以先尝试用恺撒密码穷举解密一下,或者结合字符的统计规律(要求截获的密文比较长),从规律中推断出偏移量(但没必要,直接简单粗暴地穷举 25 种可能的密文就好了)。

变体与衍生

有一种叫 ROT13(回转 13 位,rotate by 13)的密码,实际上就是偏移量等于 13 的恺撒密码,因为 13 刚好是英文字母数量 26 的一半,所以解密算法和加密算法完全一样,即对于任意字符,有:

也可以直接查表:

img

ROT13 过去在 net.jokes 新闻组里使用。它被用来隐藏某些可能侮辱到特定读者的笑话、隐晦某个谜题的答案或八卦性的内容。

仿射密码 Affine Cipher

我们前面在说恺撒密码的时候说过,它是仿射密码的一种特殊情况,下面我们来介绍仿射密码。

概述

仿射密码也属于单表代换密码,它使用线性方程加上一个模数。

算法实现

加密算法

前提条件是:$k_1$ 和 26 互素,即下式成立:

假如没有这个前提条件,不同的密文字符可以对应多个明文字符。

判断最大公约数,我们可以使用辗转相除法,我的做法是把它封装成一个函数:

# Greatest Common Divisor(GCD)
def gcd(a,b):
    if a%b == 0:
        return b
    return gcd(b,a%b)

在加密前,我们首先判断这个条件是否成立,若不成立,直接结束程序,打印提示。

# Encryption
def AffineEncrypt(m,k1,k2):
    k2 %= 26
    if gcd(k1,26) != 1:
        print("k1 and 26 are not mutually prime, and encryption fails.")
        return
    l = len(m)
    ans = ""
    for i in range(l):
        if m[i].isupper():
            ans += chr((k1*(ord(m[i])-ord('A'))+k2)%26+ord('A'))
        elif m[i].islower():
            ans += chr((k1*(ord(m[i])-ord('a'))+k2)%26+ord('a'))
        else:
            ans += m[i]
    return ans

解密算法

前提条件和上面说的一样,不然根本无法求逆。同样,在解密前,我们首先判断这个条件是否成立,若不成立,直接结束程序,打印提示。

那么怎么求 $k_1$ 模 26 逆呢,我们可以使用扩展欧几里得算法,同样将它封装成函数,方便以后调用。(这个代码在扩展欧几里得算法的基础上做了一下优化)

# Find mod m reverse of a
def findModReverse(a,m):
    if gcd(a,m)!=1:
        return None
    u1,u2,u3 = 1,0,a
    v1,v2,v3 = 0,1,m
    while v3!=0:
        q = u3//v3
        v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
    return u1%m

那么可以写出如下解密函数:

# Decryption(normal)
def AffineDecrypt(c,k1,k2):
    k2 %= 26
    if gcd(k1,26) != 1:
        print("k1 and 26 are not mutually prime, and decryption fails.")
        return
    k1 = findModReverse(k1,26)
    l = len(c)
    ans = ""
    for i in range(l):
        if c[i].isupper():
            ans += chr((k1*(ord(c[i])-ord('A')+26-k2))%26+ord('A'))
        elif c[i].islower():
            ans += chr((k1*(ord(c[i])-ord('a')+26-k2))%26+ord('a'))
        else:
            ans += c[i]
    return ans

其他考虑

对于大小写字母的区分和字母之外的字符,我们的处理方法和恺撒密码中完全相同。

攻击方法

穷举攻击

通过密文,列举出所有可能的明文(一共 311 种情况),从中找出有特定标识(如 flag )或构成自然语言中有意义的单词或短语的正确明文。

# Decryption(exhaustive)
def BruteAffineDecrypt(c):
    for k1 in range(26):
        if gcd(k1,26) == 1:
            for k2 in range(26):
                print "k1 = "+str(k1).zfill(2),
                print ", k2 = "+str(k2).zfill(2),
                print ": "+AffineDecrypt(c,k1,k2)

统计分析攻击

前提是截获的密文足够长。基础是已知的字符统计规律。

在这里,我们使用面向对象编程(OOP)的思路,新建个类,用于存储各字母出现的次数:

# Table of statistical result
fTbl = "EARIOTNSLCUDPMHGBFYWKVXZJQ"
class Node:
    ch = ''
    cnt = 0
    def __init__(self,ch,cnt):
        self.ch = ch
        self.cnt = cnt
    def __str__(self):
        return self.ch+":\t"+str(self.cnt)
    def __lt__(self,other):
        return self.cnt > other.cnt

为了方便起见,我们对这个算法进行简化,这样得到的是符合一定统计规律得到的明文:

# Decryption(statistical analysis)
def StatisticalAffineDecrypt(c):
    l = len(c)
    ciperCopy = c.lower()
    alphaNum = []
    # Initialize
    for i in range(26):
        t = Node(chr(ord('a')+i),0)
        alphaNum.append(t)
    # Count
    for i in range(l):
        if ciperCopy[i].isalpha():
            alphaNum[ord(ciperCopy[i])-ord('a')].cnt += 1
    # Sort
    alphaNum.sort()
    # Generate Substitution Table
    for k1 in range(26):
        if gcd(k1,26) == 1:
            for k2 in range(26):
                if chr((4*k1+k2)%26+ord('a')) == alphaNum[0].ch:
                    print "k1 = "+str(k1).zfill(2),
                    print ", k2 = "+str(k2).zfill(2)+":"
                    print AffineDecrypt(c,k1,k2)

简单陈述下这个算法,输入为密文,首先,为了方便,将所有英文字母转成为小写;接着,初始化统计表,将各字母的频数都初始化为 0;然后,统计各字母的频数;最后,利用统计规律计算出 $k1,k2$,输出可能的明文。用户需要手动甄选出正确的明文。进一步考虑,我们可以通过调用某些自然语言识别库,从而“全自动”地得到明文,这里我们不深入讨论。

完整代码

#-*- coding:utf-8 -*-
# Classical Cipher: Affine Cipher

# Table of statistical result
fTbl = "EARIOTNSLCUDPMHGBFYWKVXZJQ"
class Node:
    ch = ''
    cnt = 0
    def __init__(self,ch,cnt):
        self.ch = ch
        self.cnt = cnt
    def __str__(self):
        return self.ch+":\t"+str(self.cnt)
    def __lt__(self,other):
        return self.cnt > other.cnt

# Greatest Common Divisor(GCD)
def gcd(a,b):
    if a%b == 0:
        return b
    return gcd(b,a%b)

# Find mod m reverse of a
def findModReverse(a,m):
    if gcd(a,m)!=1:
        return None
    u1,u2,u3 = 1,0,a
    v1,v2,v3 = 0,1,m
    while v3!=0:
        q = u3//v3
        v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
    return u1%m

# Encryption
def AffineEncrypt(m,k1,k2):
    k2 %= 26
    if gcd(k1,26) != 1:
        print("k1 and 26 are not mutually prime, and encryption fails.")
        return
    l = len(m)
    ans = ""
    for i in range(l):
        if m[i].isupper():
            ans += chr((k1*(ord(m[i])-ord('A'))+k2)%26+ord('A'))
        elif m[i].islower():
            ans += chr((k1*(ord(m[i])-ord('a'))+k2)%26+ord('a'))
        else:
            ans += m[i]
    return ans

# Decryption(normal)
def AffineDecrypt(c,k1,k2):
    k2 %= 26
    if gcd(k1,26) != 1:
        print("k1 and 26 are not mutually prime, and decryption fails.")
        return
    k1 = findModReverse(k1,26)
    l = len(c)
    ans = ""
    for i in range(l):
        if c[i].isupper():
            ans += chr((k1*(ord(c[i])-ord('A')+26-k2))%26+ord('A'))
        elif c[i].islower():
            ans += chr((k1*(ord(c[i])-ord('a')+26-k2))%26+ord('a'))
        else:
            ans += c[i]
    return ans

# Decryption(exhaustive)
def BruteAffineDecrypt(c):
    for k1 in range(26):
        if gcd(k1,26) == 1:
            for k2 in range(26):
                print "k1 = "+str(k1).zfill(2),
                print ", k2 = "+str(k2).zfill(2),
                print ": "+AffineDecrypt(c,k1,k2)


# Decryption(statistical analysis)
def StatisticalAffineDecrypt(c):
    l = len(c)
    ciperCopy = c.lower()
    alphaNum = []
    # Initialize
    for i in range(26):
        t = Node(chr(ord('a')+i),0)
        alphaNum.append(t)
    # Count
    for i in range(l):
        if ciperCopy[i].isalpha():
            alphaNum[ord(ciperCopy[i])-ord('a')].cnt += 1
    # Sort
    alphaNum.sort()
    # Generate Substitution Table
    for k1 in range(26):
        if gcd(k1,26) == 1:
            for k2 in range(26):
                if chr((4*k1+k2)%26+ord('a')) == alphaNum[0].ch:
                    print "k1 = "+str(k1).zfill(2),
                    print ", k2 = "+str(k2).zfill(2)+":"
                    print AffineDecrypt(c,k1,k2)

# Main function
def main():
    while True:
        op = raw_input("What do you want to do?\n[E]Encryption [D]Decryption [B]Brute-Attack [S]Statistical-Analysis-Attack\n").upper()

        if op[0] == "E":
            # s = "Haha CUMTer~"
            # k1,k2 = 5,6
            s = raw_input("Please enter your plaintext:\n\t")
            k1 = input("Please enter your k1(gcd(k1,26)=1):\n\t")
            k2 = input("Please enter your k2:\n\t")
            # ********  Encryption  ********
            print 8*"*"+"  Encryption  "+8*"*"
            Encryption = AffineEncrypt(s,k1,k2)
            print "The Ciphertext is:\n\t"+Encryption
            break

        elif op[0] == "D":
            s = raw_input("Please enter your ciphertext:\n\t")
            k1 = input("Please enter your k1(gcd(k1,26)=1):\n\t")
            k2 = input("Please enter your k2:\n\t")
            # ********  Decryption  ********
            print 8*"*"+"  Decryption  "+8*"*"
            Decryption = AffineDecrypt(s,k1,k2)
            print "The Plaintext is:\n\t"+Decryption
            break

        elif op[0] == "B":
            # *******  Brute Attack  *******
            s = raw_input("Please enter your ciphertext:\n\t")
            print 7*"*"+"  Brute Attack  "+7*"*"
            BruteAffineDecrypt(s)
            break
        elif op[0] == "S":
            # ***  Statistical Analysis Attack  ***
            # s = "Pu yfo of oin hvy ufa hrpkpyb, jlar ph hopkk py oin hvy oinan, svo jnjpkk klvbi rfan zfyupgnyo zlkr; pu ovayng of ufvyg iph fjy hilgfj, lmmafmaplon nhzlmn, oin hvy jpkk sn oiafvbi oin inlao,jlar nlzi mklzn snipyg oin zfayna; pu ly fvohoanozing mlkr zlyyfo ulkk svoonaukx, oiny zknyzing jlcpyb larh, bpcny mfjna; pu P zly'o ilcn sapbio hrpkn, po jpkk ulzn of oin hvyhipyn, lyg hvyhipyn hrpkn ofbnoina, py uvkk skffr."
            s = raw_input("Please enter your ciphertext:\n\t")
            print 3*"*"+"  Statistical Analysis Attack  "+3*"*"
            StatisticalAffineDecrypt(s)
            break
        else:
            continue

if __name__ == '__main__':
    main()

运行结果

加密

例如:明文是 Haha CUMTer~ ,$k1$ 是 5 ,$k2$ 是 6,得到密文 Pgpg QCOXan~ 。

img

已知 key 解密

例如:密文是 Pgpg QCOXan~ ,$k1$ 是 5 ,$k2$ 是 6,得到明文 Haha CUMTer~ 。

img

暴力枚举解密

例如:密文是 Pgpg QCOXan~ ,不知道 $k1,k2$,暴力穷举出所有可能,再结合某些标识或使明文在自然语言中有意义,得到明文 Haha CUMTer~ 。

img

统计分析解密

例如解密:

Pu yfo of oin hvy ufa hrpkpyb, jlar ph hopkk py oin hvy oinan, svo jn jpkk klvbi rfan zfyupgnyo zlkr; pu ovayng of ufvyg iph fjy hilgfj, lmmafmaplon nhzlmn, oin hvy jpkk sn oiafvbi oin inlao,jlar nlzi mklzn snipyg oin zfayna; pu ly fvohoanozing mlkr zlyyfo ulkk svoonaukx, oiny zknyzing jlcpyb larh, bpcny mfjna; pu P zly’o ilcn sapbio hrpkn, po jpkk ulzn of oin hvyhipyn, lyg hvyhipyn hrpkn ofbnoina, py uvkk skffr.

的结果是(也需从几种可能的结果结合自然语言有意义的单词或句子):

If not to the sun for smiling, warm is still in the sun there, but we will laugh more confident calm; if turned to found his own shadow, appropriate escape, the sun will be through the heart,warm each place behind the corner; if an outstretched palm cannot fall butterfly, then clenched waving arms, given power; if I can’t have bright smile, it will face to the sunshine, and sunshine smile together, in full bloom.

img

安全性分析

由于$gcd(k_1.26)=1$,所以$k_1$ 有 $φ(26) = 12$ 种取值;$k_2$ 则有 26 种取值,刨除 $k_1=1,k_2=0$ 的情况,密钥空间为 $12×26-1 = 311$ 。对于普通的偏移密码和乘法密码,仿射密码的安全性有很大的改善,但其实依然不够大,即使是使用穷举攻击,也能轻易破解出明文。但是更好的方式是根据统计分析规律(前提是截获的密文足够长)进行攻击。实际上,由于只有两个参数,所以找到两组明文密文对便可计算出两个参数,从而彻底攻破算法。

维吉尼亚密码 Vigenère cipher

概述

维吉尼亚密码是一种简单的多表代换密码,可以看成由一些偏移量不同的恺撒密码组成。

img

算法实现

加密算法

特别要注意的是,若密钥长度小于明文长度,则密钥循环使用,这体现在我们的代码中就是对 $len(key)$ 取模。

# Encryption
def VigenereEncrypt(m,k):
    k = k.upper()
    lm = len(m)
    lk = len(k)
    j = 0
    ans = ""
    for i in range(lm):
        if m[i].isupper():
            ans += chr(((ord(m[i])-ord('A'))%26+(ord(k[j%lk])-ord('A'))%26)%26+ord('A'))
            j += 1
        elif m[i].islower():
            ans += chr(((ord(m[i])-ord('a'))%26+(ord(k[j%lk])-ord('A'))%26)%26+ord('a'))
            j += 1
        else:
            ans += m[i]
    return ans

解密算法

为什么要加 26?因为 $c_i-k_i$ 有可能小于 0 。

# Decryption
def VigenereDecrypt(c,k):
    k = k.upper()
    lc = len(c)
    lk = len(k)
    j = 0
    ans = ""
    for i in range(lc):
        if c[i].isupper():
            ans += chr(((ord(c[i])-ord('A'))%26+26-(ord(k[j%lk])-ord('A'))%26)%26+ord('A'))
            j += 1
        elif c[i].islower():
            ans += chr(((ord(c[i])-ord('a'))%26+26-(ord(k[j%lk])-ord('A'))%26)%26+ord('a'))
            j += 1
        else:
            ans += c[i]
    return ans

其他考虑

对于大小写字母的区分,我们的处理方法和恺撒密码中完全相同。

对于字母之外的字符,他们不使用密钥,也不消耗密钥,这时候,密文就是明文,明文就是密文。

攻击方法

破译维吉尼亚密码的关键在于它的密钥是循环重复的。如果我们知道了密钥的长度,那密文就可以被看作是交织在一起的凯撒密码,而其中每一个都可以单独破解。

多表代换密码体制的分析方法主要分为三步:第一步确定秘钥长度,常用的方法有卡西斯基(Kasiski)测试法和重合指数法(Index of Coincidence);第二步就是确定秘钥,常用的方法是拟重合指数测试法;第三步是根据第二步确定的密钥恢复出明文。

卡西斯基试验

卡西斯基试验是基于类似 the 这样的常用单词有可能被同样的密钥字母进行加密,从而在密文中重复出现。如果将密文中所有相同的字母组都找出来,并计算他们的最大公因数,就有可能提取出来密钥长度信息。

重合指数法

利用随机文本和英文文本的统计概率差别来分析密钥长度。依据:英文中每种单词出现的频率不同。

完整代码

#-*- coding:utf-8 -*-
# Classical Cipher: Vigenère Cipher

# Encryption
def VigenereEncrypt(m,k):
    k = k.upper()
    lm = len(m)
    lk = len(k)
    j = 0
    ans = ""
    for i in range(lm):
        if m[i].isupper():
            ans += chr(((ord(m[i])-ord('A'))%26+(ord(k[j%lk])-ord('A'))%26)%26+ord('A'))
            j += 1
        elif m[i].islower():
            ans += chr(((ord(m[i])-ord('a'))%26+(ord(k[j%lk])-ord('A'))%26)%26+ord('a'))
            j += 1
        else:
            ans += m[i]
    return ans

# Decryption
def VigenereDecrypt(c,k):
    k = k.upper()
    lc = len(c)
    lk = len(k)
    j = 0
    ans = ""
    for i in range(lc):
        if c[i].isupper():
            ans += chr(((ord(c[i])-ord('A'))%26+26-(ord(k[j%lk])-ord('A'))%26)%26+ord('A'))
            j += 1
        elif c[i].islower():
            ans += chr(((ord(c[i])-ord('a'))%26+26-(ord(k[j%lk])-ord('A'))%26)%26+ord('a'))
            j += 1
        else:
            ans += c[i]
    return ans

# Main function
def main():
    while True:
        op = raw_input("What do you want to do?\n[E]Encryption [D]Decryption\n").upper()

        if op[0] == "E":
            s = raw_input("Please enter your plaintext:\n\t")
            k = raw_input("Please enter your key:\n\t")
            # s = "Haha CUMTer~"
            # k = "password"
            # ********  Encryption  ********
            print 8*"*"+"  Encryption  "+8*"*"
            Encryption = VigenereEncrypt(s,k)
            print "The Ciphertext is:\n\t"+Encryption
            break
        elif op[0] == "D":
            s = raw_input("Please enter your ciphertext:\n\t")
            k = raw_input("Please enter your key:\n\t")
            # s = "Wazs YIDWtr~"
            # k = "password"
            # ********  Decryption  ********
            print 8*"*"+"  Decryption  "+8*"*"
            Decryption = VigenereDecrypt(s,k)
            print "The Plaintext is:\n\t"+Decryption
            break
        else:
            continue


if __name__ == '__main__':
    main()

运行结果

加密

例如明文是 Haha CUMTer~ ,密钥是 password,得到密文 Wazs YIDWtr~ 。

img

解密

例如密文是 Wazs YIDWtr~ ,密钥是 password,得到明文 Haha CUMTer~。

img

安全性分析

维吉尼亚密码也被称为“不可破译的密码”(实际上并不是不可破译)。

多表代换密码打破了原语言的字符出现规律,故其分析方法比单表代换密码复杂得多。多表代换密码对比单表代换密码安全性显著提高。但是仍然可以用一些统计分析法破解(具体参看上文攻击方法),但是前提是密文足够长。所以,较短的密文几乎是不可破译的。

希尔密码 Hill cipher

如何求模为26的矩阵的逆?

其中,$(D_{ji})$是去掉第$j$行、第$i$列后矩阵的行列式的值。

回想线性代数中学过的不带模的:

其中,$A^*$为$A$的伴随矩阵,当$A$为二阶时:

模26常用逆元

$a$ $a^{-1}\bmod 26$
1 1
3 9
5 21
7 15
9 3
11 19
15 7
17 23
19 11
21 5
23 17
25 25

1

3 9

5 21

7 15

11 19

17 23

25

本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明来自 ComyDream
本文链接:http://comydream.github.io/2019/01/01/cryptography-classical-cipher/