【笔记】古典密码

代换密码

对于密码体制的五元组$(P, C, K, E, D)$有:

$$ P=C=Z_{26} $$

其中,$K$是由26个数字0,1,2,...,25的所有可能的置换组成;对任意的置换${\pi}{\in}k$,定义:

$$ e_{\pi}(x)=\pi(x)\\ d_{\pi}(x)=\pi^{-1}(x) $$

其中$pi^{-1}$表示置换$\pi$的逆置换
另外需要注明的是,加密函数必须是单射函数
假设有置换规则:
3D8PW7NOSOAU(6EM@UH)8M2.png
则逆置换为:
TIM截图20191225194228.png

几种常见的代换密码

仿射密码

对于密码体制的五元组$(P, C, K, E, D)$有:

$$ P=C=Z_{26}\\ K={(a,b){\in}Z_{26}{\times}Z_{26}:gcd(a,26)=1} $$

对任意的$k=(a,b){\in}K$,$x,y{\in}Z_{26}$,定义:

$$ e_k(x)=(ax+b)mod26\\ d_k(y)=a^{-1}(y-b)mod26 $$

当$a=1$时,又称为移位密码;密钥空间大小${\phi}(26){\times}26=312$
假设有仿射密码密钥$k=(7,3)$,给明文hot进行加解密:
加密函数为$e_k(x)=7x+3$
解密函数为$d_k(y)=7-1(y-3)=15(y-3)=15y-19$
验证$d_k(e_k(x))=dk(7x+3)=15(7x+3)-19 =x+45-19=x$
TIM截图20191225202537.png
字母hot对应的明文数值为7,14,19,分别加密如下:

$$ (7{\times}7+3)mod26=52mod26=0 (7{\times}14+3)mod26=101mod26=23 (7{\times}19+3)mod26=136mod26=6 $$

三个密文值分别为0,23,6,相应的密文为AXG

希尔密码

对于密码体制的五元组$(P, C, K, E, D)$有

$$ P=C=(Z_{26})^m $$

$m$是一个不小于2的正整数,$K$是定义在$Z_{26}$上的$m{\times}m$可逆矩阵的集合;
取密钥$k{\in}K$,$k$为一个$m{\times}m$矩阵,记为$(k_{ij})$,对$x=(x_1,x_2,...,x_m){\in}P, y=(y_1,y_2,...,y_m){\in}C$,定义

$$ e_k(x)=x_k\\ d_k(y)=yk^{-1} $$

其中$k^{-1}$表示$k$的逆矩阵,以上运算均在$Z_{26}$上运行(模26)
假设$m=2$,取密钥

$$ \begin{equation} k={ \left[ \begin{array}{cc} 11&8\\ 3&7 \end{array} \right ]} \end{equation} $$

加密的明文为july,有:

$$ \begin{equation} (9,20){ \left[ \begin{array}{cc} 11&8\\ 3&7 \end{array} \right ]} \end{equation}=(3,4) $$

$$ \begin{equation} (11,24){ \left[ \begin{array}{cc} 11&8\\ 3&7 \end{array} \right ]} \end{equation}=(11,22) $$

因此密文为DELW

维吉尼亚密码

对于密码体制的五元组$(P, C, K, E, D)$有

$$ P=C=K=(Z_{26})^m $$

其中$m$是一个正整数,对任意的$k=(k_1,k_2,...,km){\in}K$,$x=(x_1,x_2,...,x_m){\in}P$,$y=(y_1,y_2,...,y_m){\in}C$,定义:

$$ e_k(x)=(x_1+k_1,x_2+k_2,...,x_m+k_m)\\ d_k(y)=(y_1-k_1,y_2-k_2,...,y_m-k_m) $$

以上运算均在$Z_26$上运行(模26)
1568101-20181220152842905-2108551705.png
假设$m=6$,密钥字为CIPHER,加密明文thiscryptosystemisnotsecure,密钥字对应的数字串为$k=(2,8,15,7,4,17)$
TIM截图20191225233558.png
得到密文 VPXZGIAXIVWPUBTTMJPWIZITWZT

置换密码

  • 加密:将明文字符按照一定的规则移动位置,得到排列错乱的密文,字符本身不变
  • 解密:将密文字符按照相应的逆向规则还原成原来的顺序
  • 密钥:移位规则

对于密码体制的五元组$(P, C, K, E, D)$有

$$ P=C=(Z_{26})^m $$

$m$是一个正整数,$K$是由所有定义在集合$\{1,2,...,m\}$上的置换组成,对任意的密钥(即置换)$\pi$,定义:

$$ e_{\pi}(x_1,x_2....,x_m)=(x_{{\pi}(1)},x_{{\pi}(2)},...,x_{{\pi}(m)})\\ d_{\pi}(y_1,y_2....,y_m)=(y_{{\pi}^{-1}(1)},y_{{\pi}^{-1}(2)},...,y_{{\pi}^{-1}(m)}) $$

设$m=6$,存在置换:
TIM截图20191225234847.png
加密明文 shesellsseashellsbytheseashore
首先将明文字母每六个分为一组: shesel | lsseas | hellsb | ythese | ashore
对每组字母使用加密变换可得 EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS
即密文为 EESLSHSALSESLSHBLEHSYEETHRAEOS

置换密码的特性

置换密码实际上是希尔密码的特殊形式
前例中,等价的希尔密码加密密钥为

$$ \begin{equation} k_{\pi}={ \left[ \begin{array}{cccccc} 0&0&1&0&0&0\\ 0&0&0&0&0&1\\ 1&0&0&0&0&0\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&1&0&0 \end{array} \right ]} \end{equation} $$

加密函数为$e_{\pi}(x)=xK_{\pi}$

$$ \begin{equation} (x_1,x_2,x_3,x_4,x_5,x_6){ \left[ \begin{array}{cccccc} 0&0&1&0&0&0\\ 0&0&0&0&0&1\\ 1&0&0&0&0&0\\ 0&0&0&0&1&0\\ 0&1&0&0&0&0\\ 0&0&0&1&0&0 \end{array} \right ]} \end{equation}=(x_3,x_5,x_1,x_6,x_4,x_2) $$

密码分析

密码分析是通过截获的密文推断出明文甚至密钥的过程
Kerckhoff假设:假定分析者是在已知密码体制(密码算法及其实现的全部详细资料)的前提下来破译
常用的攻击模型

  • 唯密文攻击(Ciphertext-only Attack)
  • 已知明文攻击(Known-plaintext Attack)
  • 选择明文攻击(Chosen-plaintext Attack)
  • 选择密文攻击(Chosen-ciphertext Attack)

唯密文攻击分析

1-2-古典密码-古典密码分析(上).jpg
E出现的频率进高于其他字母,其次为T、A、O、I、N、S、H、R...
许多双字母的固定序列经常出现:TH、HE、IN、ER、AN、RE、ED、ON、ES...
还有一些经常出现的3字母固定序列:THE、ING、AND、HER、ERE、ENT、THA...
根据经验,有些字母不可能组合出现在一个单词中,如果出现可作为单词边界进行分析。

仿射密码的密码分析

仿射密码部分中有$gcd(a,26)=1$意味着a和26互素
首先分析出现频率最高的字符,只需要猜中两个字母的代换,就能解出a和b
假设有仿射密码的密文如下:

FMXVEDKAPHEFRBNDKRXRSREFMORUD
SDKDVSHVUFEDKAPRKDLYEVLRHHRH

分析密文中每个字母的出现频数记录如下:
TIM截图20191226001004.png
以上密文中出现的最大频数的几个密文字母依次是R、D、E、H、K、S、F、V
假设R是e的加密,D是t的加密即$e_k(4)=17,e_k(19)=3$,因为$e_k(x)=ax+bmod26$,得到方程组:

$$ \begin{cases} 4a + b = 17mod26\\ 19a + b = 3mod26 \end{cases} $$

解方程组可知$a=6,b=19$,因为a不满足不26互素的条件,因此猜测错误;
依次,假设K是t的加密,得到$a=3,b=5$,使用此密钥尝试解密得到可阅读的明文为:
algorithms are quite general definitions of arithmetic processes

代换密码的密码分析

先分析频率高的密文,再根据英文单词中的字母组合规律进行分析
假设密文如下:

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTX
CDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCS
ZREXCHZUNMXZNZUCDRJXYYSMRTMEYIFZWDYV
ZVYFZUMRZCRWNZDZJJXZWGCHSMRNMDHNCMFQ
CHZJMXJZWIEJYUCFWDJNZDIR

分析密文中各字母出现的频数
TIM截图20191226002044.png
Z出现的频率进高于其他字母,推测$d_k(Z)=e$
-Z或Z-的双字母中,DZ、ZW出现4次,NZ、ZU出现3次,RZ、HZ、XZ、FZ、ZR、ZV、ZC、ZD、ZJ出现2次,推测$d_k(W)=d$
以W结尾的双字母中,RW出现数次且R也多次出现,推测$d_k(R)=n$
NZ常见,ZN不常见,即$d_k(N)=h$
根据以上猜测得到一些残缺的明文如ne?ndhe(其密文为RZCRWNZ),在英诧字典中搜索不到匹配的单词,猜测?为a,即dk(C)=a
nh(对应密文为RN)不可能出现在一个单词中,因此密文中的RNM解密为nh?,其中h是单词的开头且后面应该是一个元音字母
M在密文中出现的频率很高,因此对应i或o;考虑到ai出现的频率高于ao,推测$d_k(M)=i$
o是较常出现的字母,对应的密文应该是D,F,J,Y中的一个,因为密文中出现了CDM/CFM/CJM这样的组合,推测$d_k(Y)=o$(单词中不会出现aoi)。
密文组合NMD(hi?)多次出现,猜测$d_k(D)=s$
密文组合NCMF(hai?)出现,猜测$d_k(F)=r$
剩下$d_k(J)=t$
密文组合HNCMF(?hair)出现,猜测$d_k(H)=c$

o-r-riend-ro--arise-a-inedhise--t---ass-it
YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ
hs-r-riseasi-d-a-orationhadta-en--ace-hi-e
NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ
he-asnt-oo-in-i-o-redso-e-ore-ineandhesett
NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ
-ed-ac-inhischair-aceti-ted--to-ardsthes-n
XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

最后从英文单词、语法等语言规律猜测其他代换规则,最终得到明文。

Our friend from Paris examined his empty glass with surprise, as if
evaporation had taken place while he wasn’t looking. I poured some
more wine and he settled back in his chair, face tilted up towards the
sun

希尔密码的密码分析

希尔密码较难采用唯密文攻击进行分析。如果能获得一些明密文对,则较容易破解出密钥K。
假设明文friday利用$m=2$的希尔密码加密,得到的密文为PQCFKU
根据字母编码关系可知,$e_k(5,17)=(15,16)$,$e_k(8,3)=(2,5)$,$e_k(0,24)=(10,20)$。由前两个等式可得到矩阵方程:

$$ \begin{equation} { \left[ \begin{array}{cc} 5&17\\ 8&3 \end{array} \right ]}K= { \left[ \begin{array}{cc} 15&16\\ 2&5 \end{array} \right ]} \end{equation} $$

$$ \begin{equation} K=X^{-1}Y={ \left[ \begin{array}{cc} 9&1\\ 2&5 \end{array} \right ]} { \left[ \begin{array}{cc} 15&16\\ 2&5 \end{array} \right ]}= { \left[ \begin{array}{cc} 7&19\\ 8&3 \end{array} \right ]} \end{equation} $$

维吉尼亚密码分析

Tags:none
上一篇
下一篇

添加新评论

已有 2 条评论

 Eltrac 3 星期前 • |

诶,子站逆袭篡位成为主站?(误)
密码学啊,像我这种 base64 都不懂的辣鸡还是等考试结束再了解吧 qwq

 Broca-Phenol 4 星期前 • |

密码呀密码,是password呢!