密码学简介

简介

基础

密码分析学

密码分析者攻击密码体制的方法：

• 穷举攻击：通过试遍所有的密钥进行破译
  • 对抗：增大密钥的数量
• 统计分析攻击：通过分析密文和明文的统计规律破译
  • 对抗：设法使明文和密文的统计规律不一样
• 解密变换攻击：针对加密变换的数学基础，通过数学求解设法找到解密变换
  • 对抗：选用具有坚实的数学基础和足够复杂的加密算法

根据攻击强度，可以分为：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击，强度越来越强。

安全性：

• 无条件安全：无论截获多少密文，都没有足够信息来唯一确定明文，即对算法的破译不比猜测有优势；
• 计算上安全：使用有效资源对一个密码系统进行分析而未能破译；

古典密码算法

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

单表代替密码
用密码字母表中字母代替明文字母

多表代换密码

在模数 $N$ 下的矩阵乘法中，矩阵 $A$ 只有在满足 $gcd(A_{det}, N) = 1$ 的情况下才有逆矩阵。这是因为在模数 $N$ 下，只有与 $N$ 互质的数才有模 $N$ 下的乘法逆元。如果 $gcd(A_{det}, N) \neq 1$，则 $A$ 的行列式 $A_{det}$ 和模数 $N$ 不互质，因此 $A$ 没有模 $N$ 下的乘法逆元，也就没有逆矩阵。

有限域

例如，$Z_{n}= \{ 0,1,2,\cdots,n-1 \}_{mod\ n}$ 并且加法和乘法都是模 $n$ 的运算，$Z_n$ 的数什么时候有乘法逆元呢？

整数 a 在模 n 乘法下有逆元，当且仅当 a 与 n 互素。

• 所有与 n 互素的元素在模 n 乘法下构成乘法交换群(交换律)
• 1...n-1 都与 n 互素，则 n 为素数
• 所以，对于任何一个素数 p，$Z_p$ 为域，其元素的个数为 p 个。

定义有限域上的多项式 $F[x]$ 和 n 次多项式 $f(x)$，$F[x]/f(x)=\{ r(x) = r_{n-1}x^{n-1} + r_{n-1}x^{n-2}+\cdots+r_1x+r_{0}\ |\ r_{i}\in F, 0\le i \le n-1 \}$ ，加法和乘法都是模 $f(x)$ 的运算，运算是封闭的。那么 $F[x]/f(x)$ 中的多项式什么时候有乘法逆元呢？

$r(x)$ 在模 $f(x)$ 的乘法下有逆元，当且仅当 $r(x)$ 与 $f(x)$ 互素。

• 所有与 $f(x)$ 互素的元素在模 $f(x)$ 的乘法下构成乘法交换群
• 次数比 $f(x)$ 次数低的多项式都与 $f(x)$ 互素，则 $f(x)$ 为不可约多项式
• 对于任意一个首项系数为 1 的不可约多项式，$F[x]/f(x)$ 为域
• 若 $F=Z_p$，则 $F[x]/f(x)$ 中元素的个数为 $p^n$ 个
• 说明：$p^n$ 域的构造方法，首先选取 $Z_p$ 中的一个 n 次不可约多项式，然后构造集合 $F[x]/f(x)=\{ r(x) = r_{n-1}x^{n-1} + r_{n-1}x^{n-2}+\cdots+r_1x+r_{0}\ |\ r_{i}\in F, 0\le i \le n-1 \}$，集合中的加法和乘法运算都为模多项式 $f(x)$ 的运算。

资料

• 中科大-现代密码学

  • 密码学
  • Cryptography_and_Network_Security Principles_and_Practice-5th_edition.pdf
  • 信息论与编码技术

• 电子科技大学-现代密码学

  • 课件(密码 miao)

• 密码学基础文章

附录

群和域

群和域都是抽象代数中的基本概念，它们都是一种代数结构。

群是一个集合 $G$ 和一个二元运算 $\cdot$ 的组合 $(G, \cdot)$，满足以下四个条件：

1. 封闭性：对于任意 $a, b \in G$，$a \cdot b \in G$。
2. 结合律：对于任意 $a, b, c \in G$，$(a \cdot b) \cdot c = a \cdot (b \cdot c)$。
3. 单位元：存在一个元素 $e \in G$，使得对于任意 $a \in G$，$a \cdot e = e \cdot a = a$。
4. 逆元：对于任意 $a \in G$，存在一个元素 $a^{-1} \in G$，使得 $a \cdot a^{-1} = a^{-1} \cdot a = e$。

换句话说，群是一个满足封闭性、结合律、单位元和逆元的代数结构。群中的元素可以是任何东西，例如数字、矩阵、函数等等。群的一个重要性质是它的元素可以进行交换（即满足交换律）或者不可以进行交换（即不满足交换律），分别称为交换群和非交换群。

域是一个集合 $F$ 和两个二元运算 $+$ 和 $\cdot$ 的组合 $(F, +, \cdot)$，满足以下条件：

1. $(F, +)$ 是一个交换群，其中 $0$ 是加法的单位元，对于任意 $a \in F$，存在一个元素 $-a \in F$，使得 $a + (-a) = (-a) + a = 0$。
2. $(F \setminus \{0\}, \cdot)$ 是一个交换群，其中 $1$ 是乘法的单位元，对于任意 $a \in F \setminus \{0\}$，存在一个元素 $a^{-1} \in F \setminus \{0\}$，使得 $a \cdot a^{-1} = a^{-1} \cdot a = 1$。
3. 分配律：对于任意 $a, b, c \in F$，$a \cdot (b + c) = a \cdot b + a \cdot c$ 和 $(a + b) \cdot c = a \cdot c + b \cdot c$。

换句话说，域是一个满足加法和乘法都是交换群，并且满足分配律的代数结构。