古典密码-代换密码

对古典密码学中代换密码做个粗浅的了解

代换密码分为单表代换和多表代换

一、单表代换

在单表替换加密中，所有的加密方式几乎都有一个共性，那就是明密文一一对应。所以说，一般有以下两种方式来进行破解

1.凯撒密码

凯撒密码（Caesar）加密时会将明文中的 每个字母 都按照其在字母表中的顺序向后（或向前）移动固定数目（循环移动）作为密文

eg：偏移量为3

明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文：DEFGHIJKLMNOPQRSTUVWXYZABC

根据偏移量的不同，还存在若干特定的恺撒密码名称：

• 偏移量为 10： Avocat （A→K）
• 偏移量为 13： ROT13
• 偏移量为 -5： Cassis （K 6）
• 偏移量为 -6： Cassette （K 7）

加密脚本:

def encrypt_caesar_cipher(plaintext):
    def shift(text, n):
        result = ""
        for char in text:
            if char.isalpha():
                shift = ord(char) + n
                if char.islower():
                    if shift > ord("z"):
                        shift -= 26
                    elif shift < ord("a"):
                        shift += 26
                elif char.isupper():
                    if shift > ord("Z"):
                        shift -= 26
                    elif shift < ord("A"):
                        shift += 26
                result += chr(shift)
            else:
                result += char
        return result

    print("尝试所有可能的位移：")
    for i in range(1, 26):
        print(f"位移 {i}: {shift(plaintext, +i)}")


if __name__ == "__main__":
    plaintext = input("请输入凯撒密码的明文：")
    encrypt_caesar_cipher(plaintext)

解密脚本:

def decrypt_caesar_cipher(ciphertext):
    def shift(text, n):
        result = ""
        for char in text:
            if char.isalpha():
                shift = ord(char) + n
                if char.islower():
                    if shift > ord("z"):
                        shift -= 26
                    elif shift < ord("a"):
                        shift += 26
                elif char.isupper():
                    if shift > ord("Z"):
                        shift -= 26
                    elif shift < ord("A"):
                        shift += 26
                result += chr(shift)
            else:
                result += char
        return result

    print("尝试所有可能的位移：")
    for i in range(1, 26):
        print(f"位移 {i}: {shift(ciphertext, -i)}")


if __name__ == "__main__":
    ciphertext = input("请输入凯撒密码的密文：")
    decrypt_caesar_cipher(ciphertext)

2.Atbash Cipher

埃特巴什码(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

加密例子：

明文：the quick brown fox jumps over the lazy dog
密文：gsv jfrxp yildm ulc qfnkh levi gsv ozab wlt

工具：实用密码学 (practicalcryptography.com)

3.简单替换密码

加密时，每个明文都有自己对应的密文，而且不是简单的移位，是混乱的。这也使得其破解难度要高于凯撒密码

eg:

明文: abcdefghijklmnopqrstuvwxyz
密钥: phqgiumeaylnofdxjkrcvstzwb

a对应p,b对应h

一般用词频分析破解：quipqiup - cryptoquip and cryptogram solver

4.仿射密码

$$
加密函数：E(x) = (ax+b) \mod m
$$

$$
其中,x是明文通过某种数字得到的编码
$$

$$
a,m满足gcd(a,m)=1
$$

$$
m是编码系统中字母的个数
$$

$$
eg:如果以26字母表作为编码系统，则m=26
$$

$$
解密函数：D(x)=a^{-1}(x-b)\mod m
$$

$$
a^{-1}是模m的逆元
$$

二、多表代换

1.Playfair

原理：

1. 选取一串英文字母，除去重复出现的字母，将剩下的字母逐个逐个加入 5 × 5 的矩阵内，剩下的空间由未加入的英文字母依 a-z 的顺序加入。注意，将 q 去除，或将 i 和 j 视作同一字。
2. 将要加密的明文分成两个一组。若组内的字母相同，将 X（或 Q）加到该组的第一个字母后，重新分组。若剩下一个字，也加入 X 。
3. 在每组中，找出两个字母在矩阵中的地方
   • 若两个字母不同行也不同列，在矩阵中找出另外两个字母（第一个字母对应行优先），使这四个字母成为一个长方形的四个角。
   • 若两个字母同行，取这两个字母右方的字母（若字母在最右方则取最左方的字母）
   • 若两个字母同列，取这两个字母下方的字母（若字母在最下方则取最上方的字母）

新找到的两个字母就是原本的两个字母加密的结果。

exp:

以 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

加解密网站：Playfair加密解密_普莱费尔加密解密-ME2在线工具 (metools.info)

2.Polybius

Polybius 密码又称为棋盘密码

密码表长这样

	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

eg: HELLO加密后 23 15 31 31 34

另外有种变表：

	A	D	F	G	X
A	b	t	a	l	p
D	d	h	o	z	k
F	q	f	v	s	n
G	g	j	c	u	x
X	m	r	e	w	y

应用这种密码表的加密方式叫ADFGX加密

eg:HELLO 加密后得到 DD XF AG AG DF

3.Vigenere

维吉尼亚密码（Vigenere）是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。

eg:

明文	S	t	a	r	A	l	l	i	a	n	c	e
密钥	P	o	l	a	r	i	s	P	o	l	a	r

明文：come greatwall
密钥：crypto

先把密钥变成和明文同样长度
明文：comegreatwall
密钥：cryptocryptoc

然后查表，cc作为横纵坐标得到e
加密后的密文为：efkt zferrltzn

解密网站：

未知密钥：My Geocaching Profile.com - Vigenere Cipher Codebreaker

已知密钥：http://planetcalc.com/2468/

[GDOUCTF 2023]1z Classic

import math
from secret import s
s = s.lower()
keyM = [?]
l = len(keyM)
assert(math.gcd(l,26)==1)
for i in range(len(s)):
    print(chr((ord(s[i])*l-97+(keyM[i % l]))%26+97),end="")

#..........

加密可以看错是类似于仿射密码：$y_i = lx_i + k_i\mod 26$

乘上$l^{-1}$得$y_il^{-1} = x_i + k_il^{-1} \mod 26$

这就是标准的维吉尼亚密码了，题目给出$l$和$26$的关系

解题思路是先爆破出$l$，再网站解密

最后l为11

明文为：

flagwowyouareclassicmaster

4.Nihilist

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

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

以关键字 helloworld 为例

关键字导出的密码表如下

	1	2	3	4	5
1	h	e	l	o	w
2	r	d	a	b	c
3	f	g	i/j	k	m
4	n	p	q	s	t
5	u	v	x	y	z

将明文中的每个字母对应横纵坐标就是其密文，例如a加密后是23

5.Hill

希尔密码（Hill）使用每个字母在字母表中的顺序作为其对应的数字，即 A=0，B=1，C=2 等等。然后将明文转化为 n 维向量，跟一个 n × n 的矩阵相乘，再将得出的结果模 26。注意用作加密的矩阵（即密匙）在mod26下必须是可逆的，否则就不可能解码。

只有矩阵的行列式和 26 互质，才是可逆的。

eg:

在线解密工具http://www.practicalcryptography.com/ciphers/hill-cipher/

6.Autokey Cipher

自动密钥密码（Autokey Cipher）也是多表替换密码，与维吉尼亚密码密码类似，但使用不同的方法生成密钥。

自动密钥密码主要有两种，关键词自动密钥密码和原文自动密钥密码。

以关键词自动密钥为例

明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
关键词：CULTURE

以用关键词开始，填充为与明文等长的密钥

明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
关键词：CULTURE THE QUICK BROWN FOX JUMPS OVER THE

和Vigenere同样的码表

加密后的密文为:VBP JOZGD IVEQV HYY AIICX CSNL FWW ZVDP WVK

原文自动密钥密码，应该是密钥和明文一样进行加密

当未知关键词（也就是未知密钥的时候）可以用网站解密http://www.practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-autokey-cipher/