密码学基础学习总结-02

 

密码学基础总结-02这篇文章中我们将介绍古典密码学和完善保密相关知识,古典密码学就是现在没有人用的加密😂,好吧也不能这么说,如果你是为了故意要让别人解密出来,表白啥的是很好的算法,不过在正经加密不要用,会被锤。完善保密是理论上最完美的加密,但是应该用的地方很少。凯撒密码凯撒密码就是移位密码,下面这段解释搬运自维基百科:凯撒密码的替换方法是通过排列明文和密文字母表,密文字母表示通过将明文字母表...

密码学基础总结-02

这篇文章中我们将介绍古典密码学和完善保密相关知识,古典密码学就是现在没有人用的加密😂,好吧也不能这么说,如果你是为了故意要让别人解密出来,表白啥的是很好的算法,不过在正经加密不要用,会被锤。完善保密是理论上最完美的加密,但是应该用的地方很少。

凯撒密码

凯撒密码就是移位密码,下面这段解释搬运自维基百科:

凯撒密码的替换方法是通过排列明文和密文字母表,密文字母表示通过将明文字母表向左或向右移动一个固定数目的位置。例如,当偏移量是左移3的时候(解密时的密钥就是3):

明文字母表:ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表:DEFGHIJKLMNOPQRSTUVWXYZABC

使用时,加密者查找明文字母表中需要加密的消息中的每一个字母所在位置,并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作,得到原来的明文。例如:

明文:THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文:WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ

凯撒密码的加密、解密方法还能够通过同余的数学方法进行计算。首先将字母用数字代替,A=0,B=1,…,Z=25。此时偏移量为n的加密方法即为:

$E_n(x) = (x+n) mod 26$

解密就是:

$D_n(x) = (x - n)mod26$

这个密码广为人知,最早我记得在初中还是高中学概率的时候就学过,因为破解十分容易,大不了遍历一遍所有的26个字母,总能找到,大量密文的情况下,还可以进行频率分析破解,而且本文用汉字书写,这个不好套字母。

单字母替换密码

古典时代的人们一想,移位我也就能移25位,这也太弱了,所以开发了单字母替换算法,这样我总安全了吧,但是实际上还是会被攻击,还是频率攻击,这是难以避免的。

维吉尼亚密码

古典时代,人们又想出来了维吉尼亚密码,这是一种多表密码,下面懒惰的我还是搬运维基百科:

在一个凯撒密码中,字母表中的每一字母都会作一定的偏移,例如偏移量为3时,A就转换为了DB转换为了E……而维吉尼亚密码则是由一些偏移量不同的恺撒密码组成。

为了生成密码,需要使用表格法。这一表格包括了26行字母表,每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的,在过程中会不断地变换。

例如,假设明文为:

ATTACKATDAWN

选择某一关键词并重复而得到密钥,如关键词为LEMON时,密钥为:

LEMONLEMONLE

对于明文的第一个字母A,对应密钥的第一个字母L,于是使用表格中L行字母表进行加密,得到密文第一个字母L。类似地,明文第二个字母为T,在表格中使用对应的E行进行加密,得到密文第二个字母X。以此类推,可以得到:

明文:ATTACKATDAWN
密钥:LEMONLEMONLE
密文:LXFOPVEFRNHR

解密的过程则与加密相反。例如:根据密钥第一个字母L所对应的L行字母表,发现密文第一个字母L位于A列,因而明文第一个字母为A。密钥第二个字母E对应E行字母表,而密文第二个字母X位于此行T列,因而明文第二个字母为T。以此类推便可得到明文。

用数字0-25代替字母A-Z,维吉尼亚密码的加密文法可以写成同余的形式:

$C_i \equiv P_i + K_i (mod26)$

解密方法则能写成:

$P_i \equiv C_i - K_i (mod26)$

这次你不能简单的算频率攻击我了,在这里同一个字母可能被加密成不同的密文,由于这一点,在一段时间内人们还认为这个加密无法被攻破,“完美的加密?”,其实我们任然能够进行唯密文攻击。

卡西斯基试验

在维吉尼亚密码中我们发现,密钥长度我们是不知道的,但是我们可以知道其实密钥也就一个,密钥像滑窗一样进行加密,这个时候由于英文有很多重复的单词,比如the等等,这时候如果我们在一串密文中发现两段相同的密文,两者之间的距离很有可能就是密钥的长度,这时候我们多发现几段,求公因数就可以大致确定密钥长度,这时候,维吉尼亚密码相当于退化成为一个移位密码。

弗里德曼试验

这里也叫重合指数法,继续搬运维基百科:

弗里德曼试验由威廉·F·弗里德曼(William F. Friedman)于1920年代发明。他使用了重合指数(index of coincidence)来描述密文字母频率的不匀性,从而破译密码。$k_p$指目标语言中两个任意字母相同的概率(英文中为0.067),$k_r$指字母表中这种情况出现的概率(英文中为1/26=0.0385),从而密钥长度可以估计为:

其中,观察概率为:

其中,c是指字母表的长度(英文为26),N指文本的长度,$n_1$到$n_c$是指密文的字母频率,为整数。

此方法只是一种估计,会随着文本长度的增加而更为精确。在实践中,会尝试接近此估计的多个密钥长度。 一种更好的方法是将密文写成矩阵形式,其中列数与假定的密钥长度一致,将每一列的重合指数单独计算,并求得平均重合指数。对于所有可能的密钥长度,平均重合指数最高的最有可能是真正的密钥长度。这样的试验可以作为卡西斯基试验的补充。

总之,我们可以用各种方法攻破维吉尼亚密码。

古典密码学带给我们的启示

古典密码学大多保护算法,当算法泄露的时候,很多时候就能破译成功,这是不安全的,人们不能自己拍脑门想一个算法写出来就说是安全的,而是应该开放出来算法,让全世界的人研究攻击,这样没有被攻破,这样才算是安全的加密算法,人们要保护的是密钥。

密码学不能给予字母等等文字来加密,这样很容易被频率攻击攻破,现代密码学基于二进制位的加密,这样是无法进行频率攻击的。

现代密码必须实现同一明文同一密文多次加密,每一次都不一样,这样才能抵抗选择明文攻击。

不过说实在的,后面的对称加密很大程度上还是在做很多古典密码学的样子,在二进制位上做很多替换代换出来的AES,这样讲当然不全面,但是是有这样的影子的,而且人们在分析古典密码学中,发现了一种完全加密的加密方法。

完善加密,无条件安全(Unconditional Security)

回到攻防模型,这时候我们来计算攻击者获胜的概率:

一个加密算法 $(Gen, Enc, Dec)$ 在明文空间$M$上如果是无条件安全的,那么对于$M$的每一种概率分布,其中的每个消息$m$和每个可能出现的密文$c (Pr[C = c] > 0)$,均满足如下条件:

$Pr[M=m C=c] = Pr[M=m]$

我们说这是完善保密的算法,也就是说攻击者知道不知道密文$c$没有关系,反正都是瞎猜,这种极端的情况代表着明文空间和密文空间完全独立,这样攻击者理论上即使有无限的计算资源也无法通过密文恢复明文,那么什么算法能如此的强呢!?

一次一密,也叫一次性密码本,也就是每一次都只用一个密码本生成密文,每个都是独立的,保证密码本安全的情况下,这种密码牢不可破,明文空间和密文空间完全分离,但是相对应的成本非常高。应该在某些很重要的场合才会使用,而且条件严苛。

为什么说这个跟古典密码学有点关系呢?在维吉尼亚密码的分析中,人们逐渐意识到了这个完善保密的道理,事物总是这样演变的。

下一篇文章将进入现代密码学。