介绍了一些古典密码及其弱点,尤以维吉尼亚的词频分析为重。
回到了九零年代。
单表替换加密
凯撒密码
字符的移位
注意点:
-
大小写字母/数字/符号可能会有不同的偏移量
-
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
简单替换密码
随机替换
解决方案:
- http://quipqiup.com/
仿射密码
- 逐位加密:$E(x)=(ax+b)\ (mod\ m)$
- $x$ 表示明文按照某种编码得到的数字
- $a$ 和 $m$ 互质
- $m$ 是编码系统中字母的数目(一般就是26)
- 解密函数是 $D(y)=a^{-1}(y−b)\ (mod\ m)$,其中$a^{-1}$是$a$的逆元
- 若我们知道$y_1,y_2,x_1,x_2$,则可通过$(y_1-y_2)\equiv a(x_1-x_2)\ (mod\ m)$算出 $a$
多表替换加密
Playfair
原理
-
选取一串英文字母,除去重复出现的字母,将剩下的字母逐个逐个加入 5 × 5 的矩阵内,剩下的空间由未加入的英文字母依 a-z 的顺序加入。注意,将 q 去除,或将 i 和 j 视作同一字。
-
将要加密的明文分成两个一组。若组内的字母相同,将 X(或 Q)加到该组的第一个字母后,重新分组。若剩下一个字,也加入 X 。
-
在每组中,找出两个字母在矩阵中的地方。
-
若两个字母不同行也不同列,在矩阵中找出另外两个字母(第一个字母对应行优先),使这四个字母成为一个长方形的四个角。
- 若两个字母同行,取这两个字母右方的字母(若字母在最右方则取最左方的字母)。
- 若两个字母同列,取这两个字母下方的字母(若字母在最下方则取最上方的字母)。
-
-
新找到的两个字母就是原本的两个字母加密的结果。
例子
以 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
工具
- CAP4
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 |
例子
工具/脚本
对密文的五个字符进行排列爆破
- CrypTool
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,按密钥位分别向右平移相应位数
步骤
- 对密钥进行填充使其长度与明文长度一样
- 向右移位字母加密
例子
明文: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) }$
用法
- 猜测密钥长度 $k$,把第 $i+jk$ 位的密文作为一组。这些组中字母频率分布规律应当如普通英文文本一样,有的出现频率大,有的小;而若猜测错误则频率应偏于平均。
- 对于每个子字符串,计算出 $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串中相应比特位不同的数量
- 空格异或任意小写/大写字母对应得到大写/小写字母
- 故加密文本中,分组之后枚举每一组 $i,j$ 位的字符,两层循环进行异或。设对于第 $i$ 位字符,异或得到的字母数为 $n_i$,则对于每一组,$n_i$ 数最多的字符对应的明文可能就是空格,此位 key = c[i] ^ ‘ ‘
代码
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)
工具
例题
-
X - NUCA 2018
# The 26 letters a, b, c, ..., y, z correspond to the integers 0, 1, 2, ..., 25 len(key_a) = m len(key_k) = n c[i] = (p[i] * key_a[i % m] + key_k[i % n]) % 26 # p is plain text, only lowercase letters are refered to. # c is encrypted text
这里的仿射密码有点类似于 Vigenere, 容易想到这样的加密是具有周期性的,故首先可以用 $IndCo()$ 来得到 $lcm(key_a,key_k)$.
然后将密文按周期分成若干个子序列,枚举这些序列对应的 $key$, 并使用 $ChiSquared()$ 判断得到正确的 $key$.
Nihilist
只包含1~5,密文长度偶数
Nihilist 密码又称关键字密码:明文 + 关键字 = 密文。
利用密钥构造棋盘矩阵(类似 Polybius 密码) - 新建一个 5 × 5 矩阵 - 将字符不重复地依次填入矩阵 - 剩下部分按字母顺序填入 - 字母 i 和 j 等价
Hill
Others
手机键盘密码
- 每个数字键上有 3-4 个字母,用两位数字来表示字母,例如:ru 用手机键盘表示就是:7382
- 不可能用 1 开头,第二位数字不可能超过 4
- 也可能就是拼音对应的数字顺序
电脑键盘棋盘
电脑键盘坐标
电脑键盘坐标加密,利用键盘上面的字母行和数字行来加密,例:bye 用电脑键盘 XY 表示就是:351613
电脑键盘 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
培根密码
原理
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 个字符 []()!+)
工具
- JSFuck 在线加密网站
- 控制台直接运行
BrainFuck & Ook!
工具
曲路密码
原理
曲路密码(Curve Cipher)是一种换位密码,需事先约定密钥(也就是曲路路径)。
例子
明文:The quick brown fox jumps over the lazy dog
填入 5 行 7 列表(事先约定填充的行列数)
加密的回路线(事先约定填充的行列数)
密文: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
,密文如下
工具
舞动的小人密码
原理
这种密码出自于福尔摩斯探案集。每一个跳舞的小人实际上对应的是英文二十六个字母中的一个,而小人手中的旗子则表明该字母是单词的最后一个字母,如果仅仅是一个单词而不是句子,或者是句子中最后的一个单词,则单词中最后一个字母不必举旗。
曼彻斯特编码
Others
社工简单密码生成器
- https://www.bugku.com/mima/