抽象代数精解【9】

置换密码

密码体制

加解密过程

• 令m为一个正整数
  $P=C=(Z_{26}{)}^m,K是定义在集合(1,2,..,m)上的置换组成。$
  $对任意的密钥（即置换）\pi ，定义加密：$
  $e_{\pi }(x_1,x_2,...,x_m)=(x_{\pi (1)},x_{\pi (2)},...,x_{\pi (m)})$
  $定义解密：$
  $d_{\pi }(y_1,y_2,...,y_m)=(y_{{\pi }^{-1}(1)},y_{{\pi }^{-1}(2)},...,y_{{\pi }^{-1}(m)})$
• 对于英文字母26个来说，$$\begin{gathered} Z_{26}够用 \\ 但实际对于一个字节数据来说，需要将运算定义在群Z_{256}中。 \end{gathered}$$

置换

实质是位置置换，不是内容置换，特别注意！！

置换运算

定义

1. P （明文）和 C （密文） 2. 置换运算 （ 1 ） A 是含有 n 个元素的集合 （ 2 ） S n = { π ∣ π 是 A 上的双射 } （ 3 ）将 S n 中的元素称为 n 元置换。 （ 4 ）现在令集合 A = { 1 , 2 , 3 , . . . , n } ，记 I ( P ) 为 P 中元素位置组成的集合， I ( C ) 为 C 中元素的位置组成的集合，则 I ( P ) = I ( C ) = A , 任意置换 π ∈ S n 表示如下： π = ( 1 2 . . . n π ( 1 ) π ( 2 ) . . . π ( n ) ) ( 5 ) S n 中有 n ! 个元素。 1.P（明文）和C（密文） \\2.置换运算 \\（1）A是含有n个元素的集合 \\（2）S_n=\{\pi|\pi是A上的双射\} \\（3）将S_n中的元素称为n元置换。 \\（4）现在令集合A=\{1,2,3,...,n\}，记I(P)为P中元素位置组成的集合，I(C)为C中元素的位置组成的集合，则I(P)=I(C)=A,任意置换\pi \in S_n表示如下： \\\pi=\begin{pmatrix} 1 & 2 & ... & n \\ \pi(1) & \pi(2) & ... & \pi(n) \end{pmatrix} \\(5)S_n中有n!个元素。 1.P（明文）和C（密文）2.置换运算（1）A是含有n个元素的集合（2）Sn​={π∣π是A上的双射}（3）将Sn​中的元素称为n元置换。（4）现在令集合A={1,2,3,...,n}，记I(P)为P中元素位置组成的集合，I(C)为C中元素的位置组成的集合，则I(P)=I(C)=A,任意置换π∈Sn​表示如下：π=(1π(1)​2π(2)​......​nπ(n)​)(5)Sn​中有n!个元素。

置换运算的例子

本例子来自文心一言的自动生成内容
置换运算是一个将集合中的元素按照某种规则重新排列的过程。以下是一个置换运算的例子，以集合 {1, 2, 3} 为例：

集合与置换

考虑集合 S = { 1 , 2 , 3 } S = \{1, 2, 3\} S={1,2,3}，我们想要对这个集合进行置换，即重新排列它的元素。

置换规则

假设我们有一个置换规则，它将集合 $S$ 中的元素按照以下方式重新排列：

• 元素 1 映射到元素 2
• 元素 2 映射到元素 3
• 元素 3 映射到元素 1

这个置换可以用多种方式表示，但最常见的是通过轮换（cycle）或两行表示法（two-line notation）来表示。

两行表示法

两行表示法将原始集合的元素写在上面一行，将置换后的元素写在下面一行，并对齐：

$$\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$$

这表示元素 1 变成了 2，元素 2 变成了 3，元素 3 变成了 1。

轮换表示法

这个置换也可以用一个轮换来表示，即 (1 2 3)。这个轮换表示元素 1 映射到 2，元素 2 映射到 3，元素 3 映射回 1，形成了一个循环。

置换运算的结果

根据这个置换规则，集合 S = { 1 , 2 , 3 } S = \{1, 2, 3\} S={1,2,3} 置换后的新集合是 S ′ = { 2 , 3 , 1 } S' = \{2, 3, 1\} S′={2,3,1}。

置换的性质

• 可逆性：每个置换都是可逆的，即存在一个逆置换可以将集合元素恢复到原始状态。在这个例子中，逆置换也是 (1 2 3)（因为它是一个 3-轮换，且 3 是奇数，所以逆置换是它本身；但在更一般的情况下，逆置换可能是不同的轮换或置换的复合）。
• 复合：两个置换可以复合成一个新的置换。例如，如果我们有另一个置换 (1 3)（将 1 映射到 3，3 映射到 1，2 保持不变），那么它与 (1 2 3) 的复合置换将是 (1 2 3) ∘ (1 3) = (2 3)（因为首先 1 变成 3，然后 3 变成 2，而 2 变成 3 后再变回 3，所以 2 保持不变，但这是一个简化的例子，实际上应该考虑所有元素的映射）。

注意事项

• 置换的复合运算不满足交换律，即 $\sigma \circ \tau$ 不一定等于 $\tau \circ \sigma$（其中 $\sigma$ 和 $\tau$ 是两个置换）。
• 在有限集合上，所有可能的置换构成一个群，称为对称群。在这个例子中，集合 {1, 2, 3} 上的对称群 $S_3$ 包含 6 个元素：恒等置换、两个 2-轮换（即对换）和三个 3-轮换。

分组

设原文为"abcdefghij"
分组，因为m=5，所以5个字符为一组，以便下一步将每个组内部的位置进行重排，具体如下：
（1） abcde
（2） fghij

加解密

• 加密
  $$\begin{gathered} 设m=5，密钥为置换\pi \\ \pi =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 4& 1& 5& 3\end{array}\right) \end{gathered}$$
  abcde=> caebd
  fghij=>hfjgi
• 解密 $${\pi }^{-1}=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 1& 5& 2& 4\end{array}\right)$$
  caebd=>abcde
  hfjgi=>fghij

理论基础

置换密码（Permutation Cipher），又称为换位密码（Transposition Cipher），其工作原理主要基于重新排列明文中的字符或字节的顺序来生成密文，而不改变这些字符或字节本身的内容。以下是置换密码工作的详细过程：

1. 准备工作

• 选择密钥：密钥是置换密码中用于指导字符重新排列的关键信息。密钥可以是数字序列、字母序列或其他形式的标识符，具体形式取决于所使用的置换密码算法。
• 确定分组：根据密钥或算法的要求，将明文分成若干组或块。这些组或块的大小可以是固定的，也可以是可变的，具体取决于算法的设计。

2. 置换过程

• 字符排列：在每个组或块内，按照某种特定的置换规则（通常由密钥决定）重新排列字符的顺序。这些规则可能涉及列置换、行置换、矩阵置换等多种方式。
• 生成密文：根据置换后的字符顺序，重新组合成密文。在密文中，字符的内容保持不变，但它们的顺序已经发生了改变。

3. 置换密码的具体实现方式

• 列置换：将明文按列写入一个矩阵中，然后根据密钥指定的列顺序重新排列这些列，最后按行或按列读出以形成密文。
• 行置换：与列置换类似，但将明文按行写入矩阵，并根据密钥指定的行顺序进行重排。
• 矩阵置换：将明文中的字符按照某种规则（如密钥指定的顺序）填充到一个矩阵中，然后根据密钥提供的顺序重新组合矩阵中的字符，以形成密文。

4. 安全性分析

• 单次置换的局限性：单次置换后的密文往往保留了原始明文的某些统计特性（如字符频率分布），这使得它相对容易被破解。因此，单次置换的安全性较低。
• 多次置换的增强：为了提高安全性，可以对同一明文进行多次置换。每次置换都可以使用不同的算法或密钥，以进一步打乱字符的顺序并增加破解的难度。

5. 置换密码的应用

• 置换密码在古典密码学中有着广泛的应用，如历史上的栅栏密码等。
• 在现代密码学中，置换密码的概念仍然被用于某些加密算法中，但通常作为加密过程的一部分而非唯一手段。

综上所述，置换密码通过重新排列明文中的字符顺序来生成密文，其工作原理简单而有效。然而，为了确保加密的安全性，通常需要结合其他加密方法共同使用。

代换密码

代换密码（Substitution Cipher），又称为代替密码或替代密码，是密码学中的一种基本加密方法。它通过替换明文中的字符（如字母、数字或符号）来生成密文，从而保障信息的安全性。代换密码的加密过程通常涉及一个代换表（也称为密钥），该表定义了明文字符与密文字符之间的映射关系。

代换密码的工作原理

1. 建立代换表：首先，根据密钥信息（可能是数字、字母序列或其他形式的标识符）建立一个代换表。这个表定义了如何将明文中的每个字符替换为密文中的对应字符。

2. 加密过程：在加密过程中，将明文中的每个字符依次通过代换表进行查找和替换，生成密文。这个过程中，明文字符的内容发生了改变，但它们的顺序保持不变。

3. 解密过程：解密是加密的逆过程。在解密时，使用相同的代换表（即密钥）将密文中的每个字符替换回明文中的对应字符，从而恢复出原始信息。

代换密码的类型

代换密码可以分为两大类：单表代换密码和多表代换密码。

1. 单表代换密码：

   • 单表代换密码是指对明文消息中出现的同一个字母，在加密时都使用同一固定的字母来代换，不管它出现在什么地方。
   • 常见的单表代换密码包括凯撒密码（Caesar Cipher），它将明文中每个字母都按照字母表顺序向后（或向前）移动若干个位置来生成密文。
   • 优点：实现简单，易于理解。
   • 缺点：安全性较低，容易受到频率分析等攻击。

2. 多表代换密码：

   • 多表代换密码是指明文消息中出现的同一个字母，在加密时不是完全被同一固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。
   • 常见的多表代换密码包括维吉尼亚密码（Vigenère Cipher）和Playfair密码。维吉尼亚密码是一种典型的多表密码，它使用一个密钥字符串对明文进行加密，每个明文字符都与密钥字符串中对应位置的字符结合进行加密。Playfair密码则是一种基于两字母组的代替密码，它使用一个5阶方阵作为密钥，根据一定的规则对明文中的字母对进行加密。
   • 优点：能够更好地抵抗统计密码分析，提高加密的安全性。
   • 缺点：如果密钥长度较短或重复使用，仍然可能受到攻击。

代换密码的应用

代换密码在密码学历史上有着广泛的应用，从古典密码学时期的各种代换密码算法，到现代密码学中的某些加密算法（如某些对称加密算法中的S盒设计），都可以看到代换密码的影子。此外，代换密码也是密码学教学和研究中的一个重要内容，它有助于人们理解密码学的基本原理和加密方法。

结论

代换密码是一种基于字符替换的加密方法，它通过代换表将明文中的字符替换为密文中的对应字符来生成密文。代换密码可以分为单表代换密码和多表代换密码两大类，它们在安全性、实现复杂度和应用场景等方面各有特点。在实际应用中，可以根据需要选择合适的代换密码算法来保护信息的安全性。

代换与置换的区别

置换密码（Permutation Cipher）和代换密码（Substitution Cipher）是密码学中的两种基本加密方法，它们在加密原理、实现方式和安全性方面存在明显的区别。

加密原理

• 置换密码：通过重新排列明文中的字符或字节的顺序来生成密文，而不改变这些字符或字节本身的内容。其核心在于改变字符的位置，而非内容。
• 代换密码：通过替换明文中的字符（如字母、数字或符号）来生成密文。每个明文字符都被映射到密文中的另一个字符，而字符的顺序保持不变。

实现方式

• 置换密码：
  • 常见的实现方式包括列置换、行置换和矩阵置换等。
  • 明文被分成若干组或块，然后根据密钥或算法的要求重新排列这些组或块中的字符顺序。
• 代换密码：
  • 通过建立代换表（也称为密钥）来实现加密。
  • 明文中的每个字符都在代换表中查找对应的密文字符，并进行替换。

安全性

• 置换密码：
  • 单次置换可能保留了原始明文的某些统计特性（如字符频率分布），因此相对容易被识别和分析。
  • 通过多次置换或与其他加密方法结合使用，可以显著提高安全性。
• 代换密码：
  • 单表代换密码的安全性较低，容易受到频率分析等攻击。
  • 多表代换密码通过引入更多的变换规则，提高了安全性，但仍需注意密钥的管理和安全性。

应用场景

• 置换密码：由于其实现简单且易于理解，常用于教学或演示目的。在需要较高安全性的场合，通常与其他加密方法结合使用。
• 代换密码：在历史上有着广泛的应用，如凯撒密码等。在现代密码学中，代换密码的思想仍然被用于某些加密算法中（如对称加密算法中的S盒设计）。

总结

置换密码和代换密码在加密原理、实现方式和安全性方面存在明显的区别。置换密码通过重新排列字符顺序来加密，而代换密码则通过替换字符来加密。在实际应用中，可以根据需要选择合适的加密方法或结合使用多种加密方法来提高信息的安全性。

置换集合概述

下面内容来自文心一言的自动生成内容
置换集合是一个数学概念，尤其在集合论、抽象代数以及组合数学中有重要的应用。以下是对置换集合的详细解释：

一、定义

1. 集合的置换：集合的置换是指从集合到其自身的双射（即一一映射），也就是说，集合中的每一个元素都唯一地映射到集合中的另一个元素，且没有元素被遗漏。
2. 有限集合的置换：对于有限集合X，其置换的个数恰好是X中元素个数的阶乘（n!），其中n是集合X中元素的个数。

二、表示法

1. 矩阵表示法：在有限集的情况下，可以利用矩阵符号将自然排序写在第一列，而将置换后的排序写在第二列来表示置换。
2. 轮换分解：另一种表示方法是借由置换的相继作用描述，这被称为“轮换分解”。轮换是将集合中的一些元素循环移位，而保持其他元素不变。

三、特殊置换

1. 对换：长度为二的轮换称为对换，即只交换两个元素的位置，而保持其他元素不变。
2. 奇置换与偶置换：根据置换可以分解为偶数个还是对数个对换，置换被分为奇置换和偶置换。

四、应用

1. 对称群：集合X的全体置换构成一个群，称为X上的对称群，记为S_X。当X={1,2,…,n}时，常用S_n来记S_X，并称之为n个字母上的对称群。
2. 计算机科学：在计算机学科中，置换的概念被用于各种算法和数据结构中，特别是在处理排列、组合和排序问题时。

五、实例

考虑集合X={1,2,3}，其置换有6个，分别是：

• 123（恒等置换）
• 132
• 213
• 231
• 312
• 321

这些置换可以看作是集合X中元素的一种重排方式。

六、结论

置换集合是数学中的一个基本概念，它描述了集合中元素位置互换的可能性。在有限集合的情况下，置换的个数是有限的，并且与集合中元素的个数密切相关。置换的概念在抽象代数、组合数学以及计算机科学等领域都有广泛的应用。

哈希HASH

基础

• 带密钥的HASH族
  满足以下条件的四元组$X,Y,K,H$
  X:所有可能消息的集合
  Y：所有可能的消息摘要或认证标签构成的有限集
  K：密钥空间，所有可能的密钥构成的有限集
  $\forall k\in K,HASH函数h_K\in H,h_k:X\to Y$

理论

概述

hash 函数是一种将任意长度的输入（通常称为“消息”或“键值”）通过某种算法转换成固定长度输出（通常是一个较小的数值）的过程。这个固定长度的输出被称为“哈希值”或“散列值”。hash 函数在计算机科学中有广泛的应用，包括但不限于数据加密、数据索引、快速查找、错误检测、数据去重等领域。

hash 函数的主要特性：

1. 确定性：相同的输入必定产生相同的输出。
2. 单向性：通常很难（理想情况下是不可能）从哈希值推导出原始输入值。
3. 碰撞抵抗性：理想情况下，不同的输入产生相同输出的可能性极低（但并非绝对不可能）。
4. 高效性：计算哈希值的过程应当快速高效。

常见的 hash 函数：

• MD5：一种广泛使用的哈希函数，产生128位（16字节）的哈希值。但由于其存在碰撞问题，已不推荐用于安全相关的场合。
• SHA（Secure Hash Algorithm）：包括多个版本，如SHA-1、SHA-2（包括SHA-256、SHA-512等）、SHA-3等。SHA-1产生的哈希值是160位（20字节），而SHA-256产生的是256位（32字节）的哈希值。SHA系列函数因其较高的安全性被广泛用于安全领域。
• CRC（Cyclic Redundancy Check）：虽然CRC主要用于错误检测而非安全目的，但它也可以看作是一种哈希函数。它通过多项式除法来计算哈希值，常用于文件传输或存储中检测数据是否损坏。
• BLAKE2：一种快速的加密哈希函数，旨在改进现有哈希函数的性能，同时保持高安全性。

应用场景：

• 密码存储：存储密码的哈希值而非明文密码，即使数据库被泄露，攻击者也难以直接获取密码。
• 数据完整性校验：通过计算文件的哈希值来验证文件在传输或存储过程中是否被篡改。
• 快速查找：通过哈希表实现快速的数据查找、插入和删除操作，哈希表使用哈希函数将键值映射到表的索引位置。

注意事项：

• 不同的哈希函数适用于不同的场景，选择时应根据具体需求进行。
• 尽量避免使用已被证明存在安全漏洞的哈希函数，如MD5和SHA-1（在安全性要求较高的场合）。
• 考虑到哈希碰撞的可能性，虽然很低，但在设计系统时仍需考虑其潜在影响。

MD5

MD5（Message-Digest Algorithm 5，消息摘要算法第5版）是一种广泛使用的散列函数，能够产生一个128位的散列值（通常以32个十六进制数表示），主要用于确保信息传输的完整性和一致性。以下是MD5算法过程的详细描述：

一、初始化

1. 设置初始值：MD5算法使用四个32位的缓存变量（或称为幻数）A、B、C、D，这些变量在算法开始前被初始化为特定的整数值。按照RFC 1321标准，这些初始值在十六进制下表示为：
   • A = 0x67452301
   • B = 0xEFCDAB89
   • C = 0x98BADCFE
   • D = 0x10325476

二、填充消息

1. 计算填充长度：计算输入消息的长度（以位为单位）对512求余的结果。如果余数不等于448，则需要进行填充，使得填充后的总长度对512求余的结果为448。
2. 填充操作：
   • 在消息末尾首先填充一个1。
   • 然后填充0，直到长度满足上述条件。
   • 最后，在消息的末尾附加上64位（8字节）的消息原始长度（也是以位为单位），这样消息的总长度就变为(N+1)*512。

三、分组处理

1. 分组：将填充后的消息按512位（64字节）进行分组，每个分组再被划分为16个32位的子分组（即M0到M15）。
2. 循环处理：对每个分组执行四轮（共64步）的复杂非线性操作，每一轮使用不同的非线性函数（F、G、H、I）和常量，以及左移操作。

四、四轮运算

四轮运算中，每一轮都使用特定的非线性函数和常量，以及左移操作来更新A、B、C、D这四个变量。每轮运算包含16个步骤，每个步骤都涉及当前变量、上一个步骤的输出、当前子分组以及一个常量。以下是四轮运算的简要描述：

• 第一轮：使用函数F和特定的常量，进行16次操作。
• 第二轮：使用函数G和另一组常量，进行16次操作。
• 第三轮：使用函数H和另一组常量，进行16次操作。
• 第四轮：使用函数I和最后一组常量，进行16次操作。

五、输出结果

1. 连接变量：四轮运算完成后，将A、B、C、D这四个32位变量按顺序连接起来，形成一个128位的散列值。
2. 表示散列值：这个128位的散列值通常以32个十六进制数的形式表示，每个十六进制数占4位。

注意事项

• MD5算法是一种单向加密算法，即只能对明文进行加密生成散列值，而不能通过散列值逆向得到明文。
• 尽管MD5算法在数据加密和安全校验方面有着广泛的应用，但由于其存在哈希碰撞的问题，即不同的输入可能产生相同的输出，因此在安全性要求较高的场合，已逐渐被SHA-2和SHA-3等更安全的算法所取代。

以上信息基于MD5算法的原理和广泛认可的文档（如RFC 1321）进行描述，确保了准确性和权威性。

参考文献

1.《密码学原理与实践（第三版）》
2. 文心一言