第六讲古典密码算法(置换密码 & 单表代替密码算法 & 多表代替密码算法)

- 日理万妓 2023-03-01 12:56 12阅读 0赞

# 1 置换（Permutation）密码 #

对明文字符或字符组进行位置移动的密码

明文的字母顺序被打乱了，但明文字母本身不变

![20200726141010475.png][] attack at dawn![2020072614114358.png][] ATCADWTAKTAN

天书（ Scytale ）

500 B.C.，斯巴达人在军事上用于加解密

发送者把一条羊皮纸螺旋形地缠在一个圆柱形木棒上，核心思想是置换。

![20200726141321592.png][] 木棒的直径需要保密

# 2 单表代替密码算法 #

## 代替密码 ##

代替(Substitution)密码构造一个或多个密文字母表，然后用密文 字母表中的字母或者字母组来代替明文字母或字母组，各字母或 字母组的相对位置不变，但其本身的值改变了。

代替密码分为单表代替密码和多表代替密码。

**字母与数字的转换**

代替密码算法针对英文字母进行处理。首先将26个字母与 十进制数字中的0~25一一对应，如下表所示。而这里的数的加 法和乘法都定义为模26的加法和乘法。

![2020072614150038.png][]

--------------------

## 单表代替密码可分为 ##

*  加法密码
 *  乘法密码
 *  仿射密码

--------------------

### 单表代替密码——加法密码 ###

![20200726142456699.png][]

Caesar密码就是一种加法密码（k=3）

![20200726142521964.png][]

设明文为：LOVE                      则密文为：ORYH

### 单表代替密码——乘法密码 ###

![20200726142645978.png][]

设**明文为 x = 23** ， **密钥 k=5**

**加密：**![y=kx=5\*23\\equiv 11(mod\\,26)][y_kx_5_23_equiv 11_mod_26]

**解密：**

首先求k=5 模 26逆元，给出两种求逆元方法

（1）欧几里得除法[求逆元方法][Link 1]

用扩展欧几里得除法，![26=5\*5+1,1=26-5\*5][26_5_5_1_1_26-5_5]，于是5模26逆元就是 （-5）mod 26 ![\\equiv][equiv] 21

（2）[欧拉函数φ(n)的计算及欧拉定理][n]

用欧拉定理 ，![k^\{-1\}\\equiv 5^\{\\varphi (26)-1\}\\equiv 5^\{11\} mod 26][k_-1_equiv 5_varphi _26_-1_equiv 5_11_ mod 26]，又因为![5^2\\equiv -1(mod 26)][5_2_equiv -1_mod 26],所以![k^\{-1\}\\equiv 5^\{11\}\\equiv (-1)^5\*5\\equiv -5\\equiv 21(mod 26)][k_-1_equiv 5_11_equiv _-1_5_5_equiv -5_equiv 21_mod 26]

**解密**过程：![x=k^\{-1\}y=21\*11\\equiv 23(mod\\,26)][x_k_-1_y_21_11_equiv 23_mod_26]

### 单表代替密码——仿射密码 ###

![20200726155354285.png][]

仿射密码是乘法密码和加法密码的结合。

设**明文为 x = 23** ， **密钥 a=5 ，b = 1**

**加密：**![y=ax+b=5\*23+1\\equiv 12(mod\\,26)][y_ax_b_5_23_1_equiv 12_mod_26]

**解密：**

首先求k=5 模 26逆元，给出两种求逆元方法

（1）欧几里得除法[求逆元方法][Link 1]

用扩展欧几里得除法，![26=5\*5+1,1=26-5\*5][26_5_5_1_1_26-5_5]，于是5模26逆元就是 （-5）mod 26 ![\\equiv][equiv] 21

（2）[欧拉函数φ(n)的计算及欧拉定理][n]

用欧拉定理 ，![a^\{-1\}\\equiv 5^\{\\varphi (26)-1\}\\equiv 5^\{11\} mod 26][a_-1_equiv 5_varphi _26_-1_equiv 5_11_ mod 26]，又因为![5^2\\equiv -1(mod 26)][5_2_equiv -1_mod 26],所以![k^\{-1\}\\equiv 5^\{11\}\\equiv (-1)^5\*5\\equiv -5\\equiv 21(mod 26)][k_-1_equiv 5_11_equiv _-1_5_5_equiv -5_equiv 21_mod 26]

**解密**过程：![x=a^\{-1\}(y-b)=21\*(12-1)\\equiv 23(mod\\,26)][x_a_-1_y-b_21_12-1_equiv 23_mod_26]

--------------------

# 3 多表代替密码算法 #

![20200726155830497.png][]

![20200726155848839.png][]

![20200726155858151.png][]

补充： [求逆矩阵方法][Link 2]

![20200726155910281.png][]

![20200726155919966.png][]

[20200726141010475.png]: https://img-blog.csdnimg.cn/20200726141010475.png
[2020072614114358.png]: /images/20230208/5b14a141b3f6476fb6a1250f4ea347ce.png
[20200726141321592.png]: /images/20230208/c3e14e2fb6244e9f91201abf59e8bbe7.png
[2020072614150038.png]: /images/20230208/dbbd0e3aa98a4f3fbb7c13636d696eb3.png
[20200726142456699.png]: /images/20230208/15c22d0d90f9447a8793301cfc42284e.png
[20200726142521964.png]: /images/20230208/92331b0b36144df59a40200d27f51a29.png
[20200726142645978.png]: /images/20230208/723198894f6e402c950801a4f5c44783.png
[y_kx_5_23_equiv 11_mod_26]: https://private.codecogs.com/gif.latex?y%3Dkx%3D5*23%5Cequiv%2011%28mod%5C%2C26%29
[Link 1]: https://blog.csdn.net/Drifter_Galaxy/article/details/107593707
[26_5_5_1_1_26-5_5]: https://private.codecogs.com/gif.latex?26%3D5*5&plus;1%2C1%3D26-5*5
[equiv]: https://private.codecogs.com/gif.latex?%5Cequiv
[n]: https://zhuanlan.zhihu.com/p/151756874
[k_-1_equiv 5_varphi _26_-1_equiv 5_11_ mod 26]: https://private.codecogs.com/gif.latex?k%5E%7B-1%7D%5Cequiv%205%5E%7B%5Cvarphi%20%2826%29-1%7D%5Cequiv%205%5E%7B11%7D%20mod%2026
[5_2_equiv -1_mod 26]: https://private.codecogs.com/gif.latex?5%5E2%5Cequiv%20-1%28mod%2026%29
[k_-1_equiv 5_11_equiv _-1_5_5_equiv -5_equiv 21_mod 26]: https://private.codecogs.com/gif.latex?k%5E%7B-1%7D%5Cequiv%205%5E%7B11%7D%5Cequiv%20%28-1%29%5E5*5%5Cequiv%20-5%5Cequiv%2021%28mod%2026%29
[x_k_-1_y_21_11_equiv 23_mod_26]: https://private.codecogs.com/gif.latex?x%3Dk%5E%7B-1%7Dy%3D21*11%5Cequiv%2023%28mod%5C%2C26%29
[20200726155354285.png]: /images/20230208/410114c3ae2649ef9e291eca8f22d841.png
[y_ax_b_5_23_1_equiv 12_mod_26]: https://private.codecogs.com/gif.latex?y%3Dax&plus;b%3D5*23&plus;1%5Cequiv%2012%28mod%5C%2C26%29
[a_-1_equiv 5_varphi _26_-1_equiv 5_11_ mod 26]: https://private.codecogs.com/gif.latex?a%5E%7B-1%7D%5Cequiv%205%5E%7B%5Cvarphi%20%2826%29-1%7D%5Cequiv%205%5E%7B11%7D%20mod%2026
[x_a_-1_y-b_21_12-1_equiv 23_mod_26]: https://private.codecogs.com/gif.latex?x%3Da%5E%7B-1%7D%28y-b%29%3D21*%2812-1%29%5Cequiv%2023%28mod%5C%2C26%29
[20200726155830497.png]: https://img-blog.csdnimg.cn/20200726155830497.png
[20200726155848839.png]: https://img-blog.csdnimg.cn/20200726155848839.png
[20200726155858151.png]: https://img-blog.csdnimg.cn/20200726155858151.png
[Link 2]: https://wenku.baidu.com/view/b0525966f5335a8102d22078.html
[20200726155910281.png]: https://img-blog.csdnimg.cn/20200726155910281.png
[20200726155919966.png]: https://img-blog.csdnimg.cn/20200726155919966.png