抽象代数精解【6】
文章目录
- 简单密码算法
- 模运算数学定义
- 置换
- 移位
- 代换
- 仿射
- 参考文献
简单密码算法
模运算数学定义
模m剩余类集 Z m Z_m Zm
设∀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]可记为 a ‾ \overline {a} a
(2) 对应的商集为Z的模m剩余类集，记作 Z m Z_m Zm
- 环
1、 Z m Z_m Zm 上定义加法和乘法，都具有运算封闭性、符合交换律和结合律。
2、加法有逆元和单位元，乘法只有单位元。
3、加法逆元是 m − a ‾ \overline{m-a} m−a，单位元是 0 ‾ \overline{0} 0 ，加法构成群。
4、乘法单位元是 1 ‾ \overline{1} 1，乘法无逆元，因此就乘法运算只能是半群，乘法构成半群。
5、乘法与加法存在分配律
( a + b ) c = ( a c ) + ( b c ) (a+b)c=(ac)+(bc) (a+b)c=(ac)+(bc)
c ( a + b ) = ( c a ) + ( c b ) c(a+b)=(ca)+(cb) c(a+b)=(ca)+(cb)
因此构成了环。
置换
移位
- 定义移位映射
e k ( x ) = ( x + k ) m o d 26 d k ( y ) = ( y − k ) m o d 26 e k 、 d k 互为逆映射， e k 为加密， d k 为解密。 注意，这里的 e k 、 d k 映射为单射。 e_k(x)=(x+k) \quad mod \quad 26\\ d_k(y)=(y-k) \quad mod \quad 26\\ e_k、d_k互为逆映射，e_k为加密，d_k为解密。 \\注意，这里的e_k、d_k映射为单射。 ek(x)=(x+k)mod26dk(y)=(y−k)mod26ek、dk互为逆映射，ek为加密，dk为解密。注意，这里的ek、dk映射为单射。
设k=3，x为D，则加密结果为G，y为G，解密结果为D。 - 实质上移位也是一种置换。
设X为一个集合，含有n个元素，每个元素对应原文的一个字母（或一个字节），如果是字母则有26个，如果是字节则有256（ 2 8 2^8 28）个。
定义 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))
这里的 φ φ φ就是 e k e_k ek也可以是 d k d_k dk。
移位规定的 φ φ φ就是置换
φ ( x ) = ( x + k ) m o d n k 是秘钥 φ(x)=(x+k) \quad mod \quad n \\ k是秘钥 φ(x)=(x+k)modnk是秘钥
看一个置换
φ = ( 0 1 . . . n − 1 φ ( 0 ) φ ( 1 ) . . . φ ( n − 1 ) ) 定义 s 5 中的 φ ( x ) = ( x + k ) m o d 5 , k = 3 , n = 5 φ = ( 0 1 2 3 4 3 4 0 1 2 ) 置换 φ 为长度为 5 的轮换 φ=\begin{pmatrix} 0 & 1 &...&n-1\\ φ(0) & φ(1)&...&φ(n-1) \end{pmatrix} \\定义s_5中的φ(x)=(x+k) \quad mod \quad 5 ,k=3,n=5 \\ φ=\begin{pmatrix} 0&1 & 2 &3&4\\ 3&4 & 0&1&2 \end{pmatrix} \\置换φ为长度为5的轮换 φ=(0φ(0)1φ(1)......n−1φ(n−1))定义s5中的φ(x)=(x+k)mod5,k=3,n=5φ=(0314203142)置换φ为长度为5的轮换
任意置换 φ ∈ S 26 φ∈S_{26} φ∈S26，对于26个字母来说，即定义了移位运算（移位映射φ）
代换
当然如果在这里指定置换φ函数中每个自变量对应的函数值，即：分段常数函数，就是代换。
26个字母共有 26 ！ 26！ 26！种置换，一个字节共有 256 ！ 256！ 256！种置换。
每种置换构成一个密码表（每个原文以及对应的密文组成）
仿射
φ ( x ) = ( a x + b ) m o d n n 为 26 或 256 φ(x)=(ax+b) \quad mod \quad n \\ \\n为26或256 φ(x)=(ax+b)modnn为26或256
1、加密映射定义如下：
n 为 26 或 256 , 映射为单射 e ( x ) = ( a x + b ) m o d n n为26或256,映射为单射 \\ e(x)=( ax+b)\quad mod \quad n n为26或256,映射为单射e(x)=(ax+b)modn
因为同余方程 a x ≡ b ( m o d m ) 有唯一解的充要条件是 g c d ( a , m ) = 1 ax≡b(mod \quad m)有唯一解的充要条件是gcd(a,m)=1 ax≡b(modm)有唯一解的充要条件是gcd(a,m)=1
所以规定 g c d ( a , n ) = 1 ，即 a 与 n 互素 gcd(a,n)=1，即a与n互素 gcd(a,n)=1，即a与n互素
2、解密映射定义如下：
同余方程 y ≡ a x + b ( m o d n ) a x ≡ y − b ( m o d n ) a − 1 ( a x ) ≡ a − 1 ( y − b ) ( m o d n ) d ( y ) = a − 1 ( y − b ) m o d n n 为 26 或 256 , 映射为单射 同余方程y≡ax+b (mod \quad n) \\ax≡y-b (mod \quad n) \\a^{-1}(ax)≡a^{-1}(y-b) (mod \quad n) \\d(y)=a^{-1}(y-b) \quad mod \quad n \\n为26或256,映射为单射 同余方程y≡ax+b(modn)ax≡y−b(modn)a−1(ax)≡a−1(y−b)(modn)d(y)=a−1(y−b)modnn为26或256,映射为单射
3、密钥为 ( a , b ) a , b ∈ Z n (a,b) \quad a,b∈Z_n (a,b)a,b∈Zn
参考文献
1、《密码学原理与实践（第三版）》
2、《抽象代数》