古典密码学 | 紫炁のBLOG

~~主要记录密码编码学与网络安全-第七版的部分课后习题详解~~

仿射 Caesar 密码的密钥 $[a,b]$ 共有 311 种合法取值
== $12\times 26-1$ 种，需要去除 $a=1,b=0$ 的平凡解==
【证明题】对于乘法代替密码，当且仅当 $𝑔𝑐𝑑(𝑘, 𝑝) = 1$ 时， $𝐸_𝑘$ 才是一一映射。
1）==(必要性) $\Rightarrow$ ==
若 $𝑔𝑐𝑑(𝑘, 𝑝) = 1$ ，下证 $E_k$ 为一一映射：
单射：对任意 $i,j,k \in Z_p,i\neq j$ 都有 $jk \not\equiv ik\ (\bmod p)$ 否则由消去律有 $x_1=x_2$ ,与 $x_1,x_2$ 的选取不符，故 $E_k$ 为单射；

满射：对任意 $y \in Z_p$ ，由加密公式有 $y \equiv kx\ (\bmod p)$ ,又 $𝑔𝑐𝑑(𝑘, 𝑝) = 1$ 所以 $k^{-1}\bmod p$ 存在，因此存在 $x \equiv k^{-1}y\ (\bmod p)\in Z_p$ ，故 $E_k$ 为满射。
综上， $E_k$ 为一一映射。
2）==(充分性) $\Leftarrow$ ==
若 $E_k$ 为一一映射，则 $E_k$ 的逆映射 $D_k$ 也为一一映射，对任意 $y \in Z_p$ ，由加密公式 $y \equiv kx\ (\bmod p)$ ,必有 $k^{-1}\bmod p$ 存在，即存在 $ku \equiv 1\ (\bmod p)$ ，即存在 $u,v$ 满足 $uk+vp=1$ ,因此 $(k,p)=1$

(1) basilisk to leviathan blake is contact

string="thesnowlaythickonthestepsandthesnowflakesdr
        ivenbythewinlookedblackintheheadlightsofthecars"
list1=list(string)
lists=list(set(list1))
lists.sort(key=list1.index)
key="".join(lists)

C="SIDKHKDM AF HCRKIABIE SHIMC KD LFEAILA"
for i in range(ord('a'), ord('z')+1):
   if chr(i) not in lists:
      key+=chr(i)

for i in range(len(C)):
   if(C[i]==' '):
      print(' ',end="")
   else:
      print(key[(ord(C[i].lower())-ord('a'))],end="")

助记词去重并将剩余字母顺序排列得到对照表key，然后替换即可
(2) 虽然单表代替密码有大于56位DES的密钥空间，但仍不安全，可以基于英文语言规律破译，统计密文中的词频，与英语中的字母频率对照，密文越长一般破译精确度越高。
(3) 尽量涵盖所有字母，使密钥中保持原来顺序的字符串较少。

(1) 分组:mu,st,se,ey,ou,ov,er,ca,do,ga,nw,es,tc,om,in,ga,to,nv,ex
密文：UZTBDLGZPNNWLGTGTUEROVLDBDUHFPERHWQSRZ
(2) 密文：UZTBDLGZPNNWLGTGTUEROVLDBDUHFPERHWQSRZ

L A R G E

S T B C D

F H I/J K M

N O P Q U

V W X Y Z

(3) 两个矩阵加密得到的密文一样。通过观察发现可以第一个矩阵通过行列变化得到第二个矩阵。因为通过行列变化不影响Playfair规则下的替换，推广结论为若两个密钥生成的Playfair矩阵可以通过一定行列变化相互转换则其加密同一明文得到相同密文。

(4) 5x5矩阵共有25!种排列，其中每个元素有25个位置可以放，固定其余字母随其一起移动，即每个元素有25种等效矩阵，计算得：

$\begin{aligned} \frac{25!}{25}=24!&=620,448,401,733,239,439,360,000\\ &\approx 2^{79} \end{aligned}$
(1) Hill密码加密: $C=M K \bmod 26$
加密过程：将明文两两分组与数字对应如：me et对应 $(13,5)(5,20)$ 计算:
$\left(\begin{array}{ll}13 & 5\end{array}\right)\left(\begin{array}{ll}9 & 4 \\ 5 & 7\end{array}\right) \bmod 26=\left(\begin{array}{ll}142 & 87\end{array}\right) \bmod 26=\left(\begin{array}{ll}12 & 9\end{array}\right)=\left(\begin{array}{ll}L & I\end{array}\right)$
$\left(\begin{array}{ll}5 & 20\end{array}\right)\left(\begin{array}{ll}9 & 4 \\ 5 & 7\end{array}\right) \bmod 26=\left(\begin{array}{ll}145 & 160\end{array}\right) \bmod 26=\left(\begin{array}{ll}15 & 4\end{array}\right)=\left(\begin{array}{ll}O & D\end{array}\right)$
类似计算可得最终密文为LIOD LI EN SYNK

(2) 求解：

$\operatorname{det}\left(\begin{array}{ll} 9 & 4 \\ 5 & 7 \end{array}\right) \bmod 26=43$

$\left(\begin{array}{ll}9 & 4 \\ 5 & 7\end{array}\right)^{-1} \bmod 26=23\left(\begin{array}{cc}7 & -4 \\ -5 & 9\end{array}\right) \bmod 26=\left(\begin{array}{cc}5 & 12 \\ 15 & 25\end{array}\right)$
即 $K^{-1}=\left(\begin{array}{cc}5 & 12 \\ 15 & 25\end{array}\right)$
验证: $\left(\begin{array}{ll}12 & 9 \\ 15 & 4\end{array}\right)\left(\begin{array}{cc}5 & 12 \\ 15 & 25\end{array}\right) \bmod 26=\left(\begin{array}{cc}13 & 5 \\ 5 & 20\end{array}\right)=\left(\begin{array}{cc}m & e \\ e & t\end{array}\right)$

(3) 对于一个 $m \times m$ 的 Hill 密码, 假如有 $m$ 个明密文对, 每个长度都是 $m$ , 定义 $\boldsymbol{P}_{\mathrm{j}}=$ $\left(p_{1 j} \mathrm{p}_{1 j} \cdots p_{m j}\right)$ 和 $\boldsymbol{C}_{\mathrm{j}}=\left(c_{1 j} c_{1 j} \cdots c_{m j}\right)$ , 使得对每个 $\boldsymbol{C}_j$ 和 $\boldsymbol{P}_j \boldsymbol{K}(1 \leqslant j \leqslant m)$ 都有 $\boldsymbol{C}_j=\boldsymbol{P}_j \boldsymbol{K}$ , 其中 $\boldsymbol{K}$ 是末知的矩阵形密钥。现在定义两个 $m \times m$ 的矩阵 $\boldsymbol{X}=\left(p_{i j}\right)$
和 $\boldsymbol{Y}=\left(c_{i j}\right)$ 。那么我们可以得出矩阵等式 $\boldsymbol{Y}=\boldsymbol{X} \boldsymbol{K}$ , 若 $\boldsymbol{X}$ 可逆, 则可得 $\boldsymbol{K}=$
$\boldsymbol{X}^{-1} \boldsymbol{Y}$ 。若 $\boldsymbol{X}$ 不可逆, 那么可以另找 $\boldsymbol{X}$ 和对应的 $\boldsymbol{Y}$ , 直至得到一个可逆的 $\boldsymbol{X}$ 。简而言之通过明密文矩阵容易算出密钥 $\boldsymbol{K}$ ，因为加密过程是线性的。

(4) 分别构建nxn的明密文矩阵，如果明文矩阵可逆，则可计算密钥矩阵
(1) 密文为：pbvwetlxozr
(2) 密文为：beokjdmsxzpmh
(3) 密钥为：zewdwptftvmie
(1) $7*13*13*13*13=142805$
(2) $7*13*13*13*13=142805$
(3) $13*13*13*13=28561$
(4) $10*13*13*13*13=285610$
(5) $2*26*26*2=2704$
(6) $2^4*(13*13-1)*13$
(7) 13的倍数： $37648$
(8) 26的倍数： $23530$
(9) $26^4-285610-37648+23530=157248$

L	A	R	G	E
S	T	B	C	D
F	H	I/J	K	M
N	O	P	Q	U
V	W	X	Y	Z