古典密码学中的维吉尼亚加密及Python算法实现

维吉尼亚密码是CTF的Crypto中一种常见的古典密码。 该方法最早记录在吉奥万·巴蒂斯塔·贝拉索( Giovan Battista Bellaso)于1553年所著的书《吉奥万·巴蒂斯塔·贝拉索先生的密码》

介绍

维吉尼亚密码(Vigenère Cipher)是在单一恺撒密码的基础上扩展出多表代换密码,根据密钥(当密钥长度小于明文长度时可以循环使用)来决定用哪一行的密表来进行替换,以此来对抗字频统计。

  • 加密算法:例如密钥的字母为[d],明文对应的字母[b]。根据字母表的顺序[d]=4,[b]=2,那么密文就是[d]+[b]-1=4+2-1=5=[e],因此加密的结果为[e]。解密即做此逆运算。
  • 加密公式:密文 = (明文 + 密钥) Mod 26 - 1
  • 解密公式:明文 = [26 + (密文 - 密钥)] Mod 26 + 1

你也可以通过查询密码表的方法来进行加密

例如若选取”CULTURE”作密钥,对以下明文进行加密:
THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG

加密过程:如果第一行为明文字母,第一列为密钥字母,那么明文字母[T]列和密钥字母[C]行的交点就是密文字母[V],以此类推,得到对应关系如下:

1
2
3
密钥:CUL TUREC ULTUR ECU LTURE CULT URE CULT URE  
明文:THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文:VBP JOZGM VCHQE JQR UNGGW QPPK NYI NUKR XFK

破解

(1) 已知密钥加解密

你可以通过Python的pycipher模块来进行加解密,如果提示没有这个模块可通过pip install pycipher命令安装。(有关pycipher的更多参考

1
2
3
4
5
>>>from pycipher import Vigenere
>>>Vigenere('CULTURE').encipher('THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG')
'VBPJOZGMVCHQEJQRUNGGWQPPKNYINUKRXFK'
>>>Vigenere('CULTURE').decipher('VBPJOZGMVCHQEJQRUNGGWQPPKNYINUKRXFK')
'THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG'

在线加解密传送门

(2) 未知密钥加解密

在未知密钥的情况下,可以通过词频统计进行爆破。参考《维吉尼亚密码分析》这篇文章,破解维吉尼亚密码第一步是确定密钥长度,该文章介绍了使用重合指数算法来确定密钥长度,在确定密钥长度后就可以尝试确定密钥,通常我们可以使用卡方检验来找到每个字母的偏移量。

代码实现

(1) 加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def vegenere_enc(plaintext, key):
'''
维吉尼亚加密算法
plaintext: 明文
key: 密钥
'''
ascii = 'abcdefghijklmnopqrstuvwxyz'.upper()
plaintext = plaintext.upper()
key = key.upper()
keylen = len(key)
ptlen = len(plaintext)
ciphertext = ''
i = 0
count = 0
while i < ptlen:
if (plaintext[i].isalpha()):
j = i % keylen
k = ascii.index(key[j])
m = ascii.index(plaintext[i])
ciphertext += ascii[(m + k) % 26]
count += 1
else:
ciphertext += plaintext[i]
i += 1
return ciphertext

(2) 解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def vegenere_dec(ciphertext, key):
'''
维吉尼亚解密算法
ciphertext: 密文
key: 密钥
'''
ascii = 'abcdefghijklmnopqrstuvwxyz'
ciphertext = ciphertext.lower()
key = key.lower()
keylen = len(key)
ctlen = len(ciphertext)
plaintext = ''
i = 0
count = 0
while i < ctlen:
if(ciphertext[i].isalpha()):
j = count % keylen
k = ascii.index(key[j])
m = ascii.index(ciphertext[i])
if m < k:
m += 26
plaintext += ascii[m - k]
count += 1
else:
plaintext += ciphertext[i]
i += 1
return plaintext

(3) 已知明文密文破解密钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def find_key(plaintext, ciphertext):
'''
plaintext: 明文
ciphertext: 密文
'''
row = []
for i in range(26):
row.append(chr(ord('a') + i))
table = {} # 密码表
for i in range(26):
table.setdefault(row[i], [])
value = []
for j in range(26):
value.append(row[(i + j) % 26])
table[row[i]] += value

ciphertext = ciphertext.lower()
plaintext = plaintext.lower()
key = ''
for i in range(len(ciphertext)):
for r in row:
if plaintext[i] == r:
for j in range(26):
if table[r][j] == ciphertext[i]:
key += chr(ord('a') + j)

return key

此方法得到的key具有重复性,需要人为找到重复的部分为最终密钥。举例,如将以下参数传入:

1
2
plaintext = "the quick brown fox jumps over the lazy dog"  
ciphertext = "VBP JOZGM VCHQE JQR UNGGW QPPK NYI NUKR XFK"

则返回的密钥为:

1
key = "culturecultureculturecultureculture"

所以重复部分”culture”即为最终密钥。