本篇文章将对古典密码中使用到的基本加解密运算进行总结,并展示个别加减密运算的简单例题,从而使读者更加容易理解古典密码中的基本加减密运算的原理。
文章目录
前言
首先引入密码学中的几个基本定义:
M:明文空间,明文的集合
C:密文空间,密文的集合
K:密钥空间(也称密钥的数量),密钥的集合
E:加密变换的集合,使明文加密生成密文的算法
D:解密变换的集合,使密文解密生成明文的算法
单表密码体制:明文字母对应的密文字母在密文中保持不变。(浅显一点就是相同的字母加密以后的字母也为相同的)
多表密码体制:明文中不同位置的同一明文字母在密文中对应的密文字母不同。(相同的字母在不同的位置加密以后的字母极大可能不同)
Z
q
=
{
0
,
1
,
2
,
.
.
.
,
q
−
1
}
,
Z
q
∗
=
{
k
∈
Z
q
∣
g
c
d
(
k
,
q
)
=
1
}
Z_q=\{0,1,2,...,q-1\},Z_q^*=\{k\in Z_q \vert gcd(k,q)=1 \}
Zq={0,1,2,...,q−1},Zq∗={k∈Zq∣gcd(k,q)=1},其中
g
c
d
(
k
,
q
)
=
1
gcd(k,q)=1
gcd(k,q)=1表示k与q互素。
例如:
Z
26
=
{
0
,
1
,
2
,
.
.
.
,
25
}
Z_{26}=\{0,1,2,...,25\}
Z26={0,1,2,...,25}则
Z
26
∗
=
{
1
,
3
,
5
,
7
,
9
,
11
,
15
,
17
,
19
,
21
,
23
,
25
}
Z_{26}^*=\{1,3,5,7,9,11,15,17,19,21,23,25\}
Z26∗={1,3,5,7,9,11,15,17,19,21,23,25} 即由与26互素的数组成的
一、单表古典密码中的基本加减密运算
1.加法密码
设
X
=
Y
=
Z
q
,
K
=
Z
q
.
X=Y=Z_q,K=Z_q.
X=Y=Zq,K=Zq.对任意
m
∈
X
,
k
∈
K
m \in X,k \in K
m∈X,k∈K
加密算法:
c
=
E
k
(
m
)
=
(
m
+
k
)
m
o
d
q
c=E_k(m)=(m+k) mod \ q
c=Ek(m)=(m+k)mod q 解密算法:
m
=
D
k
(
c
)
=
(
c
−
k
)
m
o
d
q
m=D_k(c)=(c-k) mod \ q
m=Dk(c)=(c−k)mod q 加密密钥和解密密钥:k
密钥量:q
例题: m=4,k=5,q=26,则加密
c
=
(
4
+
5
)
m
o
d
26
=
9
c=(4+5) mod\ 26=9
c=(4+5)mod 26=9;若改为m=23,则
c
=
(
23
+
5
)
m
o
d
26
=
28
m
o
d
26
=
2
c=(23+5) mod\ 26=28 mod\ 26=2
c=(23+5)mod 26=28mod 26=2
解密
m
=
(
9
−
5
)
m
o
d
26
=
4
m=(9-5) mod\ 26=4
m=(9−5)mod 26=4;
m
=
(
2
−
5
)
m
o
d
26
=
−
3
m
o
d
26
=
26
−
3
=
23
m=(2-5) mod\ 26=-3\ mod\ 26=26-3=23
m=(2−5)mod 26=−3 mod 26=26−3=23。(分别对应上面的加密过程)
注意:此处运用了模运算,基本上密码学中都会用到模运算,如有不懂可去搜查模运算的知识点。
2.乘法密码
设
X
=
Y
=
Z
q
,
K
=
Z
q
∗
.
X=Y=Z_q,K=Z_q^*.
X=Y=Zq,K=Zq∗.对任意
m
∈
X
,
k
∈
K
m \in X,k \in K
m∈X,k∈K
加密算法:
c
=
E
k
(
m
)
=
k
m
m
o
d
q
c=E_k(m)=km \ \ mod \ q
c=Ek(m)=km mod q 解密算法:
m
=
D
k
(
c
)
=
k
−
1
c
m
o
d
q
m=D_k(c)=k^{-1}c \ \ mod \ q
m=Dk(c)=k−1c mod q 加密密钥和解密密钥:k
密钥量:
φ
(
q
)
\varphi(q)
φ(q),(Euler函数:小于q且与q互素的非负整数的个数)
例题: m=4,k=5,q=26,则加密
c
=
(
5
∗
4
)
m
o
d
26
=
20
c=(5*4) mod\ 26=20
c=(5∗4)mod 26=20;
解密
m
=
(
5
−
1
∗
20
)
m
o
d
26
=
21
∗
20
m
o
d
26
=
(
−
5
)
∗
(
−
6
)
m
o
d
26
=
30
m
o
d
26
=
4
m=(5^{-1}*20) mod\ 26=21*20 mod\ 26=(-5)*(-6) mod\ 26=30 mod\ 26=4
m=(5−1∗20)mod 26=21∗20mod 26=(−5)∗(−6)mod 26=30mod 26=4
**注意:此处的
5
−
1
5^{-1}
5−1指的是5的逆元,在模运算的情况下应为
5
∗
x
≡
1
m
o
d
26
5*x\equiv1\ mod\ 26
5∗x≡1 mod 26 解得 x=21**
小tips: 此处
K
=
Z
q
∗
K=Z_q^*
K=Zq∗是因为要使
k
−
1
k^{-1}
k−1存在
3.仿射密码
设
X
=
Y
=
Z
q
,
K
=
{
(
k
1
,
k
2
)
∣
k
1
∈
Z
q
,
k
2
∈
Z
q
∗
}
.
X=Y=Z_q,K=\{(k_1,k_2)\vert k_1 \in Z_q,k_2 \in Z_q^*\}.
X=Y=Zq,K={(k1,k2)∣k1∈Zq,k2∈Zq∗}.对任意
m
∈
X
,
k
=
(
k
1
,
k
2
)
∈
K
m \in X,k=(k_1,k_2) \in K
m∈X,k=(k1,k2)∈K
加密算法:
c
=
E
k
(
m
)
=
k
1
+
k
2
m
m
o
d
q
c=E_k(m)=k_1+k_2m \ \ mod \ q
c=Ek(m)=k1+k2m mod q 解密算法:
m
=
D
k
(
c
)
=
k
2
−
1
(
c
−
k
1
)
m
o
d
q
m=D_k(c)=k_2^{-1}(c-k_1) \ \ mod \ q
m=Dk(c)=k2−1(c−k1) mod q 加密密钥和解密密钥:
(
k
1
,
k
2
)
(k_1,k_2)
(k1,k2)
密钥量:
q
∗
φ
(
q
)
q*\varphi(q)
q∗φ(q)
加法密码和乘法密码是仿射密码的特例
例题:
m
=
7
,
k
1
=
1
,
k
2
=
3
,
q
=
26
m=7,k_1=1,k_2=3,q=26
m=7,k1=1,k2=3,q=26,则加密
c
=
(
1
+
3
∗
7
)
m
o
d
26
=
22
c=(1+3*7) mod\ 26=22
c=(1+3∗7)mod 26=22;
解密
m
=
(
3
−
1
∗
(
22
−
1
)
)
m
o
d
26
=
9
∗
21
m
o
d
26
=
189
m
o
d
26
=
7
m=(3^{-1}*(22-1)) mod\ 26=9*21 mod\ 26=189 mod\ 26=7
m=(3−1∗(22−1))mod 26=9∗21mod 26=189mod 26=7
ps:
3
−
1
=
9
3^{-1}=9
3−1=9
4.置换密码
设
X
=
Y
=
Z
q
,
K
为
Z
q
X=Y=Z_q,K为Z_q
X=Y=Zq,K为Zq上全体置换的集合。对任意
m
∈
X
,
k
=
σ
∈
K
m \in X,k=\sigma \in K
m∈X,k=σ∈K
加密算法:
c
=
E
k
(
m
)
=
σ
(
m
)
m
o
d
q
c=E_k(m)=\sigma(m) mod \ q
c=Ek(m)=σ(m)mod q 解密算法:
m
=
D
k
(
c
)
=
σ
−
1
(
m
)
m
o
d
q
m=D_k(c)=\sigma^{-1}(m) mod\ q
m=Dk(c)=σ−1(m)mod q加密密钥和解密密钥:
σ
\sigma
σ(一个置换)
密钥量:
q
!
q!
q!
因为置换就是简单地将明文字符对应成相应的密文字符,故此处就不写例题了。
二、多表古典密码中的基本加减密运算
1.简单加法密码
设
X
n
=
Y
n
=
Z
q
n
,
K
=
Z
q
n
.
X^n=Y^n=Z_q^n,K=Z_q^n.
Xn=Yn=Zqn,K=Zqn.对任意
m
=
(
m
1
,
m
2
,
.
.
.
,
m
n
)
∈
X
n
,
k
=
(
k
1
,
k
2
,
.
.
.
,
k
n
)
∈
K
m=(m_1,m_2,...,m_n) \in X^n,k=(k_1,k_2,...,k_n) \in K
m=(m1,m2,...,mn)∈Xn,k=(k1,k2,...,kn)∈K
加密算法:
c
=
E
k
(
m
)
=
(
m
1
+
k
1
,
m
2
+
k
2
,
.
.
.
,
m
n
+
k
n
)
c=E_k(m)=(m_1+k_1,m_2+k_2,...,m_n+k_n)
c=Ek(m)=(m1+k1,m2+k2,...,mn+kn) 解密算法:
m
=
D
k
(
c
)
=
(
c
1
−
k
1
,
c
2
−
k
2
,
.
.
.
,
c
n
−
k
n
)
m=D_k(c)=(c_1-k_1,c_2-k_2,...,c_n-k_n)
m=Dk(c)=(c1−k1,c2−k2,...,cn−kn) 加密密钥和解密密钥:
(
k
1
,
k
2
,
.
.
.
,
k
n
)
(k_1,k_2,...,k_n)
(k1,k2,...,kn)
密钥量:
q
n
q^n
qn
2.简单乘法密码
设
X
n
=
Y
n
=
Z
q
n
,
K
=
(
Z
q
∗
)
n
.
X^n=Y^n=Z_q^n,K=( Z_q^*)^n.
Xn=Yn=Zqn,K=(Zq∗)n.对任意
m
=
(
m
1
,
m
2
,
.
.
.
,
m
n
)
∈
X
n
,
k
=
(
k
1
,
k
2
,
.
.
.
,
k
n
)
∈
K
m=(m_1,m_2,...,m_n) \in X^n,k=(k_1,k_2,...,k_n) \in K
m=(m1,m2,...,mn)∈Xn,k=(k1,k2,...,kn)∈K
加密算法:
c
=
E
k
(
m
)
=
(
k
1
m
1
,
k
2
m
2
,
.
.
.
,
k
n
m
n
)
c=E_k(m)=(k_1m_1,k_2m_2,...,k_nm_n)
c=Ek(m)=(k1m1,k2m2,...,knmn) 解密算法:
m
=
D
k
(
c
)
=
(
k
1
−
1
c
1
,
k
2
−
1
c
2
,
.
.
.
,
k
n
−
1
c
n
)
m=D_k(c)=(k_1^{-1}c_1,k_2^{-1}c_2,...,k_n^{-1}c_n)
m=Dk(c)=(k1−1c1,k2−1c2,...,kn−1cn) 加密密钥和解密密钥:k
密钥量:
φ
(
q
)
n
\varphi (q)^n
φ(q)n
因为多表的加法密码和乘法密码与单表的极其相似,区别就在于多表是每一个分量就会给一个算法去进行加密
例如: 设分量长度为3,
k
1
=
3
,
k
2
=
5
k_1=3,k_2=5
k1=3,k2=5,则
c
1
=
3
∗
m
1
m
o
d
26
,
c
2
=
5
∗
m
2
m
o
d
26
c_1=3*m_1\ mod26,c_2=5*m_2\ mod26
c1=3∗m1 mod26,c2=5∗m2 mod26分别对应不同的k,以此可以类推至n项
3.简单仿射密码
设
X
n
=
Y
n
=
Z
q
n
,
K
=
{
(
<
k
11
,
k
21
>
,
<
k
12
,
k
22
>
,
.
.
.
,
<
k
1
n
,
k
2
n
>
)
∣
k
1
i
∈
Z
q
,
k
2
i
∈
Z
q
∗
,
1
≤
i
≤
n
}
.
X^n=Y^n=Z_q^n,K=\{(<k_{11},k_{21}>,<k_{12},k_{22}>,...,<k_{1n},k_{2n}>)\vert k_{1i}\in Z_q,k_{2i}\in Z_q^*,1\le i\le n\}.
Xn=Yn=Zqn,K={(<k11,k21>,<k12,k22>,...,<k1n,k2n>)∣k1i∈Zq,k2i∈Zq∗,1≤i≤n}.
对任意
m
=
(
m
1
,
m
2
,
.
.
.
,
m
n
)
∈
X
n
,
k
=
(
<
k
11
,
k
21
>
,
<
k
12
,
k
22
>
,
.
.
.
,
<
k
1
n
,
k
2
n
>
)
∈
K
m=(m_1,m_2,...,m_n) \in X^n,k=(<k_{11},k_{21}>,<k_{12},k_{22}>,...,<k_{1n},k_{2n}>)\in K
m=(m1,m2,...,mn)∈Xn,k=(<k11,k21>,<k12,k22>,...,<k1n,k2n>)∈K
加密算法:
c
=
E
k
(
m
)
=
(
k
11
+
k
21
m
1
,
k
12
+
k
22
m
2
,
.
.
.
,
k
1
n
+
k
2
n
m
n
)
c=E_k(m)=(k_{11}+k_{21}m_1,k_{12}+k_{22}m_2,...,k_{1n}+k_{2n}m_n)
c=Ek(m)=(k11+k21m1,k12+k22m2,...,k1n+k2nmn) 解密算法:
m
=
(
k
21
−
1
(
c
1
−
k
11
)
,
k
22
−
1
(
c
2
−
k
12
)
,
.
.
.
,
k
2
n
−
1
(
c
n
−
k
1
n
)
)
m=(k_{21}^{-1}(c_1-k_{11}),k_{22}^{-1}(c_2-k_{12}),...,k_{2n}^{-1}(c_n-k_{1n}))
m=(k21−1(c1−k11),k22−1(c2−k12),...,k2n−1(cn−k1n)) 加密密钥和解密密钥:
(
(
k
11
,
k
21
)
,
(
k
12
,
k
22
)
,
.
.
.
,
(
k
1
n
,
k
2
n
)
)
((k_{11},k_{21}),(k_{12},k_{22}),...,(k_{1n},k_{2n}))
((k11,k21),(k12,k22),...,(k1n,k2n))
密钥量:
q
n
φ
(
q
)
n
q^n\varphi (q)^n
qnφ(q)n
例题: 已知多表仿射密码的加密密钥为(2,1),(3,3),则
c
1
=
2
+
m
1
m
o
d
26
,
c
2
=
3
+
3
∗
m
2
m
o
d
26
c_1=2+m_1\ mod26,c_2=3+3*m_2\ mod26
c1=2+m1 mod26,c2=3+3∗m2 mod26 以此可以类推至n项
4.简单置换密码
设
X
n
=
Y
n
=
Z
q
n
,
K
=
{
(
k
1
,
k
2
,
.
.
.
,
k
n
)
∣
k
i
是
Z
q
上的置换
,
1
≤
i
≤
n
}
.
X^n=Y^n=Z_q^n,K=\{(k_1,k_2,...,k_n)\vert k_i是Z_q上的置换,1\le i\le n\}.
Xn=Yn=Zqn,K={(k1,k2,...,kn)∣ki是Zq上的置换,1≤i≤n}.对任意
m
=
(
m
1
,
m
2
,
.
.
.
,
m
n
)
∈
X
n
,
k
=
(
k
1
,
k
2
,
.
.
.
,
k
n
)
∈
K
m=(m_1,m_2,...,m_n) \in X^n,k=(k_1,k_2,...,k_n) \in K
m=(m1,m2,...,mn)∈Xn,k=(k1,k2,...,kn)∈K
加密算法:
c
=
E
k
(
m
)
=
(
k
1
(
m
1
)
,
k
2
(
m
2
)
,
.
.
.
,
k
n
(
m
n
)
)
c=E_k(m)=(k_1(m_1),k_2(m_2),...,k_n(m_n))
c=Ek(m)=(k1(m1),k2(m2),...,kn(mn)) 解密算法:
m
=
D
k
(
c
)
=
(
k
1
−
1
(
c
1
)
,
k
2
−
1
(
c
2
)
,
.
.
.
,
k
n
−
1
(
c
n
)
)
m=D_k(c)=(k_1^{-1}(c_1),k_2^{-1}(c_2),...,k_n^{-1}(c_n))
m=Dk(c)=(k1−1(c1),k2−1(c2),...,kn−1(cn)) 加密密钥和解密密钥:
(
k
1
,
k
2
,
.
.
.
,
k
n
)
(k_1,k_2,...,k_n)
(k1,k2,...,kn)
密钥量:
(
q
!
)
n
(q!)^n
(q!)n
5.换位密码
设
X
n
=
Y
n
=
Z
q
n
,
K
为
{
1
,
2
,
.
.
.
,
n
}
.
X^n=Y^n=Z_q^n,K为\{1,2,...,n\}.
Xn=Yn=Zqn,K为{1,2,...,n}.上的全体置换的集合,对任意
m
=
(
m
1
,
m
2
,
.
.
.
,
m
n
)
∈
X
n
,
k
=
σ
∈
K
m=(m_1,m_2,...,m_n) \in X^n,k=\sigma \in K
m=(m1,m2,...,mn)∈Xn,k=σ∈K
加密算法:
c
=
E
k
(
m
)
=
(
m
σ
(
1
)
,
m
σ
(
2
)
,
.
.
.
,
m
σ
(
n
)
)
c=E_k(m)=(m_{\sigma(1)},m_{\sigma(2)},...,m_{\sigma(n)})
c=Ek(m)=(mσ(1),mσ(2),...,mσ(n)) 解密算法:
m
=
D
k
(
c
)
=
(
c
σ
−
1
(
1
)
,
c
σ
−
1
(
2
)
,
.
.
.
,
c
σ
−
1
(
n
)
)
m=D_k(c)=(c_{\sigma^{-1}(1)},c_{\sigma^{-1}(2)},...,c_{\sigma^{-1}(n)})
m=Dk(c)=(cσ−1(1),cσ−1(2),...,cσ−1(n)) 加密密钥和解密密钥:
σ
\sigma
σ
密钥量:
n
!
n!
n!
简而言之就是将其对应的位置全部打乱顺序
123
σ
\sigma
σ312
第一个明文字符到第三个位置上去,第二个铭文字符到第一个位置上去,第三个明文字符到第二个位置上去。
结束语
第一篇有关密码学的文章就写到这里,希望能对读者们起到一定的作用。
如果存在错误欢迎在评论区指出,可以多多交流哇,大家一起进步,嘿嘿。
版权归原作者 努力敲代码的小盆友 所有, 如有侵权,请联系我们删除。