抽象代数精解【6】

简单密码算法

模运算数学定义

模m剩余类集$Z_m$
设∀a,b∈Z（整数），m为正整数
m|b-a ，称a R b
R满足反身性、对称性、传递性
1、R为同余关系，也是Z的一个等价关系。
2、记为a≡b(mod m)，即： a同余于b，模m。
3、[a]为整数集Z的一个模m剩余类
(1) [a]可记为$\overline{a}$
(2) 对应的商集为Z的模m剩余类集，记作$Z_m$

• 环
  1、$Z_m$ 上定义加法和乘法，都具有运算封闭性、符合交换律和结合律。
  2、加法有逆元和单位元，乘法只有单位元。
  3、加法逆元是$\overline{m-a}$，单位元是$\overline{0}$ ，加法构成群。
  4、乘法单位元是$\overline{1}$，乘法无逆元，因此就乘法运算只能是半群，乘法构成半群。
  5、乘法与加法存在分配律
  $(a+b)c=(ac)+(bc)$
  $c(a+b)=(ca)+(cb)$
  因此构成了环。

置换

移位

• 定义移位映射
  $$\begin{gathered} e_k(x)=(x+k)mod26 \\ {d}_k(y)=(y-k)mod26 \\ {e}_k、d_k互为逆映射，e_k为加密，d_k为解密。 \\ 注意，这里的e_k、d_k映射为单射。 \end{gathered}$$
  设k=3，x为D，则加密结果为G，y为G，解密结果为D。
• 实质上移位也是一种置换。

设X为一个集合，含有n个元素，每个元素对应原文的一个字母（或一个字节），如果是字母则有26个，如果是字节则有256（$2^8$）个。
定义 S n = { φ ∣ φ 是 X 上的双射 } 称 s n 中的元素为 n 元置换。 令集合 X = { 1 , 2 , 3 , . . . , n } ，任意置换 φ ∈ S n ，可表示为如下形式 φ = ( 1 2 . . . n φ ( 1 ) φ ( 2 ) . . . φ ( n ) ) 此处也可设 X = { 0 , 1 , 2 , 3 , . . . , n − 1 } φ = ( 0 1 . . . n − 1 φ ( 0 ) φ ( 1 ) . . . φ ( n − 1 ) ) 定义S_n=\{φ|φ是X上的双射\}\\ 称s_n中的元素为n元置换。\\ 令集合 X=\{1,2,3,...,n\} ，任意置换φ∈S_n，可表示为如下形式\\ φ=\begin{pmatrix} 1 & 2 &...&n\\ φ(1) & φ(2)&...&φ(n) \end{pmatrix} \\此处也可设 X=\{0,1,2,3,...,n-1\} \\ φ=\begin{pmatrix} 0 & 1 &...&n-1\\ φ(0) & φ(1)&...&φ(n-1) \end{pmatrix} 定义Sn​={φ∣φ是X上的双射}称sn​中的元素为n元置换。令集合X={1,2,3,...,n}，任意置换φ∈Sn​，可表示为如下形式φ=(1φ(1)​2φ(2)​......​nφ(n)​)此处也可设X={0,1,2,3,...,n−1}φ=(0φ(0)​1φ(1)​......​n−1φ(n−1)​)
这里的$\phi$就是$e_k$也可以是$d_k$。
移位规定的$\phi$就是置换
$$\begin{gathered} \phi (x)=(x+k)modn \\ k是秘钥 \end{gathered}$$
看一个置换
$$\begin{gathered} \phi =\left(\begin{array}{cccc}0& 1& ...& n-1\\ \phi (0)& \phi (1)& ...& \phi (n-1)\end{array}\right) \\ 定义s_5中的\phi (x)=(x+k)mod5,k=3,n=5 \\ \phi =\left(\begin{array}{ccccc}0& 1& 2& 3& 4\\ 3& 4& 0& 1& 2\end{array}\right) \\ 置换\phi 为长度为5的轮换 \end{gathered}$$
任意置换$\phi \in S_{26}$，对于26个字母来说，即定义了移位运算（移位映射φ）

代换

当然如果在这里指定置换φ函数中每个自变量对应的函数值，即：分段常数函数，就是代换。
26个字母共有$26！$种置换，一个字节共有$256！$种置换。
每种置换构成一个密码表（每个原文以及对应的密文组成）

仿射

$$\begin{gathered} \phi (x)=(ax+b)modn \\ n为26或256 \end{gathered}$$
1、加密映射定义如下：
$$\begin{gathered} n为26或256,映射为单射 \\ e(x)=(ax+b)modn \end{gathered}$$
因为同余方程$ax\equiv b(modm)有唯一解的充要条件是gcd(a,m)=1$
所以规定$gcd(a,n)=1，即a与n互素$
2、解密映射定义如下：
$$\begin{gathered} 同余方程y\equiv ax+b(modn) \\ ax\equiv y-b(modn) \\ {a}^{-1}(ax)\equiv a^{-1}(y-b)(modn) \\ d(y)=a^{-1}(y-b)modn \\ n为26或256,映射为单射 \end{gathered}$$
3、密钥为$(a,b)a,b\in Z_n$

参考文献

1、《密码学原理与实践（第三版）》
2、《抽象代数》