回到了九零年代。

介绍一些古典密码,尤以维吉尼亚的词频分析为重。

单表替换加密

凯撒密码

字符的移位

注意点:

  1. 大小写字母/数字/符号可能会有不同的偏移量

  2. Keyed Caesar

    • 按照给出的密钥对应偏移。例如:

      密文:s0a6u3u1s0bv1a
      密钥:guangtou
      偏移:6,20,0,13,6,19,14,20
      明文:y0u6u3h1y0uj1u
      

Atbash Cipher

明文: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
密文:Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

简单替换密码

随机替换

解决方案:

仿射密码

多表替换加密

Playfair

原理

  1. 选取一串英文字母,除去重复出现的字母,将剩下的字母逐个逐个加入 5 × 5 的矩阵内,剩下的空间由未加入的英文字母依 a-z 的顺序加入。注意,将 q 去除,或将 i 和 j 视作同一字。

  2. 将要加密的明文分成两个一组。若组内的字母相同,将 X(或 Q)加到该组的第一个字母后,重新分组。若剩下一个字,也加入 X 。

  3. 在每组中,找出两个字母在矩阵中的地方。

    • 若两个字母不同行也不同列,在矩阵中找出另外两个字母(第一个字母对应行优先),使这四个字母成为一个长方形的四个角。

    • 若两个字母同行,取这两个字母右方的字母(若字母在最右方则取最左方的字母)。
    • 若两个字母同列,取这两个字母下方的字母(若字母在最下方则取最上方的字母)。
  4. 新找到的两个字母就是原本的两个字母加密的结果。

例子

以 playfair example 为密匙,得

P L A Y F
I R E X M
B C D G H
K N O Q S
T U V W Z

要加密的讯息为 Hide the gold in the tree stump

HI DE TH EG OL DI NT HE TR EX ES TU MP

就会得到

BM OD ZB XD NA BE KU DM UI XM MO UV IF

工具

Polybius 棋盘密码

密文和明文字符数对应 2:1

常用密码表:

  1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z

例子

linke

工具/脚本

对密文的五个字符进行排列爆破

import itertools

key = []
cipher = ""

for i in itertools.permutations('abcde', 5):
    key.append(''.join(i))

for now_key in key:
    solve_c = ""
    res = ""
    for now_c in cipher:
        solve_c += str(now_key.index(now_c))
    for i in range(0,len(solve_c),2):
        now_ascii = int(solve_c[i])*5+int(solve_c[i+1])+97
        if now_ascii>ord('i'):
            now_ascii+=1
        res += chr(now_ascii)
    if "flag" in res:
        print(now_key,res)

Vigenere 维吉尼亚密码

一系列凯撒密码组成密码表

其实就是 (二维) Keyed Caesar,按密钥位分别向右平移相应位数

维吉尼亚表格

步骤

  1. 对密钥进行填充使其长度与明文长度一样
  2. 向右移位字母加密

例子

明文:come greatwall
密钥:crypto
密文:efkt zfgrrltzn
明文 c o m e g r e a t w a l l
密钥 c r y p t o c r y p t o c

代码

from itertools import cycle
keyword = 'fnxtldpznxpzprdlppdzn'
def Vigenere_dec(ct, k):
    shifts = cycle(alphabet.index(c) for c in k)
    pt = ''
    for c in ct.lower():
        if c not in alphabet: 
            next(shifts)
            pt += c
            continue
        pt += alphabet[(alphabet.index(c) - next(shifts)) % len(alphabet)]
    return pt
plain = Vigenere_dec(cipher, keyword)

破解

破译维吉尼亚密码的关键在于它的密钥是循环重复的。

Kasiski Test

思路:寻找密文序列中重复的片段,列出重复的片段之间相隔的距离,那么密钥长度很大概率上能够整除这些距离。

The Index of Coincidence Test

猜测密钥周期长度

定义

有长度为 $n$ 的字符串 $s$,其 index of coincidence 就是从 $s$ 中随机选取两个字符且这两个字符相同的概率,记作 $IndCo(s)$

公式

设 $N_i$ 为字母 $i$ 在字符串中出现的次数,则:$IndCo(s)={ \sum_{i=0}^{25} {C_{N_i}^2 } \over {C_{len(s)}^2 } }={1\over {n(n-1)} } \sum_{i=0}^{25} {N_i(N_i-1) }$

用法
  1. 猜测密钥长度 $k$,把第 $i+jk$ 位的密文作为一组。这些组中字母频率分布规律应当如普通英文文本一样,有的出现频率大,有的小;而若猜测错误则频率应偏于平均。
  2. 对于每个子字符串,计算出 $IndCo(s_i)$ 的均值,若其越大 (趋近 0.0685) 则密钥长度趋于正确,若越小 (趋近 0.0385) 越像是随机字符串。密文越长,密钥越短,效果越佳。
代码
from string import ascii_lowercase as alphabet
def IndCo(s):
    '''
    Index of Coincidence.
    :param str s: The Substring.
    :return: The index of coincidence of the substring.
    :rtype: float
    '''
    N = len(s)
    frequency = [s.count(c) for c in alphabet]
    return sum(i**2 - i for i in frequency) / (N**2 - N)
def CalKeyLength(s):
    '''
    Calculate the probable key lengths using the index of coincidence method.
    :param str s: The character string to be analysed.
    :return: All the probable key lengths.
    :rtype: list
    '''
    res = []
    for kl in range(2, 100):  # Key length range can be adjusted accordingly.
        subs = [s[i::kl] for i in range(kl)]  # Group into substrings.
        if sum(IndCo(si) for si in subs) / kl > 0.06:
            if all(map(lambda x: kl % x, res)):  # Avoid multiples.
                res.append(kl)
    return res

Trivial Method

若密文序列足够长,则每组子字符串都会呈现出明显的频率分布特征,则子字符串中出现次数最多的秘文字母大概率对应出现次数最多的字母 $e$,则每组偏移量 = 出现次数最多的密文字母 - 字母 $e$

代码
def RecoverKeyword_1(ct, kl):
    '''
    Recover the keyword according to the most frequent letters.
    :param str ct: The ciphertext.
    :param int kl: The key length.
    :return: The recovered keyword.
    :rtype: str
    '''
    keyword = ''
    subs = [ct[i::kl] for i in range(kl)]
    for s in subs:
        frequency = [s.count(c) for c in alphabet]
        most_fqc = max(frequency)
        keyword += alphabet[(frequency.index(most_fqc) - 4) % len(alphabet)]
    return keyword

Nontrivial Method

Chi-squared Statistic

用于猜解解密后的明文是否具有文章的有序特征

感觉像 $IndCo$ 的进阶版本

也就是方差统计,$\delta^2(C,E)=\sum_{i=0}^{25} { (C_i-E_i)^2\over E_i}$,其中 $C_i$ 是字母 $i$ 的出现次数,$E_i$ 是对应的期望出现次数。对每一组字符串尝试 26/52··· 种偏移,根据字母频率表进行偏差计算。

$Chi-squared$ 最小时,极大概率为正确的偏移量

字母频率表

字母频率表

代码1
from string import ascii_lowercase as alphabet
LETTER_FREQUENCY = {  # From https://en.wikipedia.org/wiki/Letter_frequency.
    'e': 0.12702,
    't': 0.09056,
    'a': 0.08167,
    'o': 0.07507,
    'i': 0.06966,
    'n': 0.06749,
    's': 0.06327,
    'h': 0.06094,
    'r': 0.05987,
    'd': 0.04253,
    'l': 0.04025,
    'c': 0.02782,
    'u': 0.02758,
    'm': 0.02406,
    'w': 0.02360,
    'f': 0.02228,
    'g': 0.02015,
    'y': 0.01974,
    'p': 0.01929,
    'b': 0.01492,
    'v': 0.00978,
    'k': 0.00772,
    'j': 0.00153,
    'x': 0.00150,
    'q': 0.00095,
    'z': 0.00074
}
def ChiSquared(s):
    '''
    Calculate the `Chi-squared Statistic`.
    :param str s: The string to be analysed.
    :return: The `Chi-squared Statistic` of the string.
    :rtype: float
    '''
    f = lambda c: LETTER_FREQUENCY[c] * len(s)
    sum = 0
    for c in alphabet:
        if c in LETTER_FREQUENCY :
           sum += (s.count(c) - f(c))**2 / f(c)
    return sum

def RecoverKeyword_2(ct, kl):
    '''
    Recover the keyword according to the `Chi-squared Statistic`.
    :param str ct: The ciphertext.
    :param int kl: The key length.
    :return: The recovered keyword.
    :rtype: str
    '''
    keyword = ''
    subs = [ct[i::kl] for i in range(kl)]
    for s in subs:
        chi_squareds = []
        for shift in range(len(alphabet)):  # Try all possible shifts.
            shifted_s = ''.join(\
                alphabet[(alphabet.index(c) - shift) % len(alphabet)]\
                for c in s)
            chi_squareds.append((shift, ChiSquared(shifted_s)))
        keyword += alphabet[min(chi_squareds, key=lambda x: x[1])[0]]
    return keyword
代码2

这道题是 异或型Vigenere,范围为 ascii 256

明文空间不止小写字母(空格、符号、大写字母等)时,使用Chi-squared Statistic方法,效果不太理想。

我们可以换一个方案:按字母的出现的概率对整个字符串进行评分,每一次尝试解密的结果中每有一个字母就加上对应的权重分,评分越高就说明这个结果越像是普通的英文文本。

from itertools import *
from string import printable
alphabet = list(range(256))
LETTER_FREQUENCY = {
    ' ': 0.25000,
    'e': 0.12702,
    't': 0.09056,
    'a': 0.08167,
    'o': 0.07507,
    'i': 0.06966,
    'n': 0.06749,
    's': 0.06327,
    'h': 0.06094,
    'r': 0.05987,
    'd': 0.04253,
    'l': 0.04025,
    'c': 0.02782,
    'u': 0.02758,
    'm': 0.02406,
    'w': 0.02360,
    'f': 0.02228,
    'g': 0.02015,
    'y': 0.01974,
    'p': 0.01929,
    'b': 0.01492,
    'v': 0.00978,
    'k': 0.00772,
    'j': 0.00153,
    'x': 0.00150,
    'q': 0.00095,
    'z': 0.00074
}
def IndCo(s):
    N = len(s)
    frequency = [s.count(c) for c in alphabet]
    return sum(i**2 - i for i in frequency) / (N**2 - N)
def CalKeyLength(s):
    res = []
    for kl in range(2, 38):
        subs = [s[i::kl] for i in range(kl)]
        if sum(IndCo(si) for si in subs) / kl > 0.06:
            if all(map(lambda x: kl % x, res)):
                res.append(kl)
    return res
def score(s):
    score = 0
    for c in s.lower():
        if c in LETTER_FREQUENCY:
            score += LETTER_FREQUENCY[c]
    return score
def RecoverKey(ct, kl):
    key = b''
    subs = [ct[i::kl] for i in range(kl)]
    for s in subs:
        scores = []
        for xor in range(256):
            xored_s = ''.join(chr(c ^ xor) for c in s)
            if all(c in printable for c in xored_s):
                scores.append((xor, score(xored_s)))
        key += bytes([max(scores, key=lambda x: x[1])[0]])
    return key
def Vigenere_dec(cipher, key):
    keyCircle = cycle(key)
    pt = ''
    for c in cipher:
        pt += chr(c ^ next(keyCircle))
    return pt
def main():
    cipher = ''
    kls = CalKeyLength(cipher)
    print(f"All probable key length: {kls}")
    for kl in kls:
        key = RecoverKey(cipher, kl)
        print(f"Key: {key}")
        print(Vigenere_dec(cipher, key))
if __name__ == '__main__':
    main()

杂谈·拓展

汉明距离

正常英文字母平均距离为 2~3,任意字符平均距离为 4(误差较大)

同一key位 加密的两字符,异或结果也是其明文异或的结果

汉明距离指两个01串中相应比特位不同的数量

代码
import base64
import string


def bxor(a, b):     # xor two byte strings of different lengths
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])


def hamming_distance(b1, b2):
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits


def score(s):
    freq = {}
    freq[' '] = 700000000
    freq['e'] = 390395169
    freq['t'] = 282039486
    freq['a'] = 248362256
    freq['o'] = 235661502
    freq['i'] = 214822972
    freq['n'] = 214319386
    freq['s'] = 196844692
    freq['h'] = 193607737
    freq['r'] = 184990759
    freq['d'] = 134044565
    freq['l'] = 125951672
    freq['u'] = 88219598
    freq['c'] = 79962026
    freq['m'] = 79502870
    freq['f'] = 72967175
    freq['w'] = 69069021
    freq['g'] = 61549736
    freq['y'] = 59010696
    freq['p'] = 55746578
    freq['b'] = 47673928
    freq['v'] = 30476191
    freq['k'] = 22969448
    freq['x'] = 5574077
    freq['j'] = 4507165
    freq['q'] = 3649838
    freq['z'] = 2456495
    score = 0
    string=bytes.decode(s)
    for c in string.lower():
        if c in freq:
            score += freq[c]
    return score


def break_single_key_xor(b1):
    max_score = 0
    english_plaintext = 0
    key = 0

    for i in range(0,256):
        b2 = [i] * len(b1)
        try:
            plaintext = bxor(b1, b2)
            pscore = score(plaintext)
        except Exception:
            continue
        if pscore > max_score or not max_score:
            max_score = pscore
            english_plaintext = plaintext
            key = chr(i)
    return key



text = ''
with open(r" ", "r") as f:
    for line in f:
        text += line
b = base64.b64decode(text)


normalized_distances = []


for KEYSIZE in range(2, 40):
    # 我们取其中前6段计算平均汉明距离
    b1 = b[: KEYSIZE]
    b2 = b[KEYSIZE: KEYSIZE * 2]
    b3 = b[KEYSIZE * 2: KEYSIZE * 3]
    b4 = b[KEYSIZE * 3: KEYSIZE * 4]
    b5 = b[KEYSIZE * 4: KEYSIZE * 5]
    b6 = b[KEYSIZE * 5: KEYSIZE * 6]
    b7 = b[KEYSIZE * 6: KEYSIZE * 7]

    normalized_distance = float(
        hamming_distance(b1, b2) +
        hamming_distance(b2, b3) +
        hamming_distance(b3, b4) +
        hamming_distance(b4, b5) +
        hamming_distance(b5, b6) 
    ) / (KEYSIZE * 5)
    normalized_distances.append(
        (KEYSIZE, normalized_distance)
    )
normalized_distances = sorted(normalized_distances, key=lambda x: x[1])


for KEYSIZE, _ in normalized_distances[:5]:
    block_bytes = [[] for _ in range(KEYSIZE)]
    for i, byte in enumerate(b):
        block_bytes[i % KEYSIZE].append(byte)
    keys = ''

    for bbytes in block_bytes:
        keys += break_single_key_xor(bbytes)
    key = bytearray(keys * len(b), "utf-8")
    plaintext = bxor(b, key)
    print("keysize:", KEYSIZE)
    print("key is:", keys, "n")
    s = bytes.decode(plaintext)
    print(s)

工具

Vigenere

例题

Nihilist

只包含1~5,密文长度偶数

Nihilist 密码又称关键字密码:明文 + 关键字 = 密文。

利用密钥构造棋盘矩阵(类似 Polybius 密码) - 新建一个 5 × 5 矩阵 - 将字符不重复地依次填入矩阵 - 剩下部分按字母顺序填入 - 字母 i 和 j 等价

Hill

hill

Others

手机键盘密码

picture

电脑键盘棋盘

电脑棋盘加密

电脑键盘坐标

电脑键盘坐标加密,利用键盘上面的字母行和数字行来加密,例:bye 用电脑键盘 XY 表示就是:351613

电脑键盘坐标加密

电脑键盘 QWE

用字母表替换键盘上的排列顺序。

computer-qwe

键盘布局加密

简单地说就是根据给定的字符在键盘上的样子来进行加密。

Morse

敲击码

  1  2  3  4  5
1 A  B C/K D  E
2 F  G  H  I  J 
3 L  M  N  O  P
4 Q  R  S  T  U
5 V  W  X  Y  Z

knock

培根密码

原理

a AAAAA g AABBA n ABBAA t BAABA
b AAAAB h AABBB o ABBAB u-v BAABB
c AAABA i-j ABAAA p ABBBA w BABAA
d AAABB k ABAAB q ABBBB x BABAB
e AABAA l ABABA r BAAAA y BABBA
f AABAB m ABABB s BAAAB z BABBB

或以A/B代表1/0,a~z从0~25采用二进制表示。

或:细体为A,粗体为B

工具

栅栏密码

原理

把要加密的明文分成 N 栏,把每组的第 1 个字连起来形成密文。

工具

01248 密码

原理

该密码又称为云影密码,只使用 0,1,2,4,8 四个数字,其中 0 用来表示间隔,其他数字表示相加后的数字 如:28=10,124=7,18=9,再用 1->26 表示 A->Z。

JSFuck

原理

一串特殊的JS编码(只用 6 个字符 []()!+)

工具

BrainFuck & Ook!

工具

曲路密码

原理

曲路密码(Curve Cipher)是一种换位密码,需事先约定密钥(也就是曲路路径)。

例子

明文:The quick brown fox jumps over the lazy dog

填入 5 行 7 列表(事先约定填充的行列数)

qulu-table

加密的回路线(事先约定填充的行列数)

qulu-road

密文:gesfc inpho dtmwu qoury zejre hbxva lookT

列移位加密

原理

换位密码,通过一个简单的规则将明文打乱混合成密文

例子

明文 The quick brown fox jumps over the lazy dog

将明文填入 5 行 7 列表(事先约定填充的行列数,如果明文不能填充完表格可以约定使用某个字母进行填充)

明文

密钥: how are u,按 how are u 在字母表中的出现的先后顺序进行编号,我们就有 a 为 1,e 为 2,h 为 3,o 为 4,r 为 5,u 为 6,w 为 7,所以先写出 a 列,其次 e 列,以此类推写出的结果便是密文:

密钥

密文: qoury inpho Tkool hbxva uwmtd cfseg erjez

猪圈密码

原理

猪圈密码是一种以格子为基础的简单替代式密码,如下:

猪圈密码对照表

猪圈密码还有变种:圣堂武士密码:

圣堂武士密码

例子

明文为 X marks the spot ,密文如下

猪圈密码示例

工具

舞动的小人密码

原理

这种密码出自于福尔摩斯探案集。每一个跳舞的小人实际上对应的是英文二十六个字母中的一个,而小人手中的旗子则表明该字母是单词的最后一个字母,如果仅仅是一个单词而不是句子,或者是句子中最后的一个单词,则单词中最后一个字母不必举旗。

舞动的小人密码

曼彻斯特编码

manchester

Others

1

社工简单密码生成器