信安数学基础学习
若
a
a
a 是
b
b
b 的倍数则记为
b
?
∣
?
a
b\ |\ a
b?∣?a
一个比较不熟的定理
若
a
?
∣
?
b
a\ |\ b
a?∣?b，
b
?
∣
?
a
b\ |\ a
b?∣?a 则
a
=
±
b
a=\pm b
a=±b
欧几里得除法
先证存在性，再证唯一性
因为
q
q
q与
q
1
q_{1}
q1?都是整数，所以它们相差的绝对值大于等于
1
1
1，所以
∣
b
(
q
?
q
1
)
∣
≥
b
\lvert b(q-q_{1})\rvert \geq b
∣b(q?q1?)∣≥b
根据
r
r
r与
r
1
r_{1}
r1?的范围可知
∣
r
1
?
r
∣
<
b
\lvert r_{1} - r \rvert < b
∣r1??r∣<b，所以与
b
(
q
?
q
1
)
=
r
1
?
r
b(q-q_{1})=r_{1}-r
b(q?q1?)=r1??r矛盾。
密码学原理与实践学习
仿射密码
移位密码和仿射密码是代换密码的一种特殊形式。仿射密码加密函数定义为
e
(
x
)
=
(
a
x
+
b
)
m
o
d
26
e(x)=(ax+b)mod26
e(x)=(ax+b)mod26
a
,
b
∈
Z
a,b \in\mathbb Z
a,b∈Z26，当
a
=
1
a=1
a=1，就是移位密码
为了解密，要保证仿射函数是一个单射函数，也就是
a
x
≡
y
(
m
o
d
26
)
ax\equiv y(mod26)
ax≡y(mod26)中一个
x
x
x对应一个
y
y
y，一个
x
x
x不能对应多个
y
y
y，一个
y
y
y不能对应多个
x
x
x。
书中写假设存在
a
x
1
≡
a
x
2
(
m
o
d
26
)
ax_{1}\equiv ax_{2}(mod26)
ax1?≡ax2?(mod26)，我先这样理解，就是说如果两个
P
\mathcal{P}
P（不知道是否一样）经过同种加密后他们的
C
\mathcal{C}
C一样，推出
x
1
≡
x
2
(
m
o
d
26
)
x_{1}\equiv x_{2}(mod26)
x1?≡x2?(mod26)这个结论，这两个
P
\mathcal{P}
P在
Z
Z
Z26中位置相同，即两个
P
\mathcal{P}
P一样。达到证明它是单射函数的目的。
单纯在数学上说就是假设
a
x
1
≡
a
x
2
(
m
o
d
26
)
ax_{1}\equiv ax_{2}(mod26)
ax1?≡ax2?(mod26)（把
x
1
x_{1}
x1?当已知，
x
2
x_{2}
x2?当未知）没有唯一解，即
x
1
≠
x
2
x_{1}\neq x_{2}
x1??=x2?，但是推出
x
1
≡
x
2
(
m
o
d
26
)
x_{1}\equiv x_{2}(mod26)
x1?≡x2?(mod26)与前面矛盾，所以只有唯一解。
取
a
x
≡
y
(
m
o
d
26
)
ax\equiv y(mod26)
ax≡y(mod26)中
a
x
ax
ax第
i
i
i个值为
a
x
i
ax_{i}
axi?，由上面有唯一解证明知不存在
a
x
i
ax_{i}
axi?与
a
x
j
ax_{j}
axj?在
Z
\mathbb Z
Z26中位置相同（如果相同，
a
x
i
≡
a
x
2
(
m
o
d
26
)
ax_{i}\equiv ax_{2}(mod26)
axi?≡ax2?(mod26)中，
x
2
x_{2}
x2?可以取
x
i
x_{i}
xi?和
x
j
x_{j}
xj?，就与唯一解矛盾，所以
x
2
x_{2}
x2?只能取
x
i
x_{i}
xi?）最后得到上面的证明。
下面重新叙述这个命题（定理）
