【密码学】古典密码 | ComyDream Studio

【密码学】古典密码

source. 1月 01, 2019

清醒的人最荒唐。

在本文中， $c_i$ 代表密文（Cipher）的第 $i$ 个字符，$m_i$ 代表明文（Message）的第 $i$ 个字符。

恺撒密码 _{Caesar cipher}

概述

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

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

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

算法实现

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

加密算法

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

$c_i=(m_i+k)\mod 26$

最后，加上 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

解密算法

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

$m_i = (c_i-k+26)\mod 26$

# 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~ 。

已知 key 解密

例如：密文是 Mfmf HZRYjw~ ，偏移量（key）是 5 ，得到明文 Haha CUMTer~。

暴力枚举解密

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

安全性分析

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

变体与衍生

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

$ROT_{13}(ROT_{13}(m))=m$

也可以直接查表：

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

仿射密码 _{Affine Cipher}

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

概述

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

算法实现

加密算法

$c_i=(k_1·m_i+k_2)\mod26$

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

$gcd(k_1,26)=1$

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

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

# 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

解密算法

$m_i=k_1^{-1}·(c_i-k_2)\mod26$

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

那么怎么求 $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~ 。

已知 key 解密

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

暴力枚举解密

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

统计分析解密

例如解密：

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.

安全性分析

由于$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}

概述

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

算法实现

加密算法

$c_i=(m_i+k_i)\mod26$

特别要注意的是，若密钥长度小于明文长度，则密钥循环使用，这体现在我们的代码中就是对 $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

解密算法

$m_i=(c_i+26-k_i)\mod26$

为什么要加 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~ 。

解密

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

安全性分析

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

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

希尔密码 Hill cipher

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

$[A^{-1}]_{ij}=(\det A)^{-1}(-1)^{i+j}(D_{ji})$

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

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

$A^{-1}=\frac{1}{|A|}A^*$

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

$A^*= \begin{bmatrix} d & -b\\ -c & a \end{bmatrix}$

模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

3 9

5 21

7 15

11 19

17 23

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

恺撒密码 Caesar cipher

概述

算法实现

加密算法

解密算法

其他考虑

区分大写字母和小写字母

对于字母之外的字符

攻击方法

对主函数的处理

完整代码

运行结果

加密

已知 key 解密

暴力枚举解密

安全性分析

变体与衍生

仿射密码 Affine Cipher

概述

算法实现

加密算法

解密算法

其他考虑

攻击方法

穷举攻击

统计分析攻击

完整代码

运行结果

加密

已知 key 解密

暴力枚举解密

统计分析解密

安全性分析

维吉尼亚密码 Vigenère cipher

概述

算法实现

加密算法

解密算法

其他考虑

攻击方法

卡西斯基试验

重合指数法

完整代码

运行结果

加密

解密

安全性分析

希尔密码 Hill cipher

模26常用逆元

恺撒密码 _{Caesar cipher}

仿射密码 _{Affine Cipher}

维吉尼亚密码 _{Vigenère cipher}