替代密码

Caesar密码

Caesar密码是最早的替代密码，其方法很简单，即对每个字母用字母表中它之后第3个字母代替它

其加密、解密的一般形式分别为 $C=E(k,p)=(p+k)\mod 26$ 和 $p=D(k,C)=(C-k)\mod 26$

其中k表示字母在字母表中位移的位数

单表代替密码

单表代替密码即建立大小相同的明文字符集合到密文字符集合的一一映射，Caesar密码就是一种特殊的单表代替密码

显然具有$n$个元素的字符集合可以定义出$n!$种不同的加密

单表代替密码可以抵御穷举攻击，但却可以被统计频率攻击轻松攻破

假设我们已知明文语言为英语，那么我们可以统计出如图所示的字母出现频率
假设截获的密文长度足够，则可根据其字符频率很容易的分析出明文

alphabet_freq

Playfair密码

应对单表代替密码统计频率攻击的一种方法是对明文中多个字母一起加密

Playfair算法基于密钥词构造一个5×5的字母矩阵，构造方法为按从左到右、从上到下的顺序，先填充密钥词，再按顺序填充其他字母，其中I、J视为同一个字母

以密钥词monarchy为例，构造的矩阵如下

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

加密时，先将明文字母两两分组，如果某组中两个字母相同，则在其中插入一个其他字母，例如明文balloon分组后为ba、lx、lo、on

对于落在矩阵中同一行的字母对，分别用其右边的字母代替，例如AR用RM代替

对于落在矩阵中同一列的字母对，分别用其下面的字母代替，例如OV用HO代替

对于其他情况，假设字母对前后两个字母分别落在$(x_1,y_1)$和$(x_2,y_2)$处，则分别用$(x_1, y_2)$处和$(x_2,y_1)$处的字母代替，即“对角互换”，例如HS用BP代替

Playfair的安全性

针对Playfair密码的统计频率攻击相对更困难，但仍然是可行

我们可以选择大量明文，进行字母计数，计数结果除以频率最高的字母(e)的出现次数，可获得所有字母的相对频率曲线，然后根据Playfair密码获得对应的密文，同样计数并处以明文频率最高的字母(e)的出现次数获得相对频率曲线

如果明文的统计频率信息被完全隐藏，那么频率曲线应该是一条水平的线，如图所示，Playfair的频率曲线比明文相对更水平，但仍暴露出可以分析的频率信息

playfair_freq

Hill密码

Hill密码是另一种多字母代替密码

Hill密码的密钥是$m\times m$的可逆矩阵$K$，其逆矩阵为$K^{-1}\mod 26$
加密过程将明文每连续$m$个数字分为一组，记为$P=(p_1,p_2,…,p_m)$
则密文为$C=(c_1,c_2, …,c_m)=PK\mod 26$
相应的解密过程为$P=CK^{-1}\mod 26$

Hill密码完全隐藏了单字母的频率信息，且密钥矩阵越大，隐藏的多字母频率信息越多

然而Hill密码容易被已知明文攻击破解
设密钥矩阵大小为$m\times m$，若攻击者拥有$m$个明密文对$P_1,P_2,…,P_m$和$C_1,C_2,…,C_m$
令其组成矩阵$X=(P_1,P_2,…,P_m)^T$和$Y=(C_1,C_2,…,C_m)^T$，则有$Y=XK\mod 26$
若$X$可逆，则可直接计算出密钥矩阵$K=X^{-1}Y\mod 26$

Vigenere密码

应对单表代替密码统计频率攻击的另一种方法是对多表代替，即对明文采用多个不同的单表代替

Vigenere密码是最出名和简单的多表代替密码

Vigenere指定一个密钥词，并将其转换成对应的数字0~25，记为 $K=k0, k_1, …,k{m-1}$
记明文序列为$P=p0,p_1,…,p{n-1}$，密文序列为$C=c0,c_1,…,c{n-1}$，假设$m\leq n$
其加密方程为$ci=(p_i+k{i\mod m})\mod 26$，解密则为$pi=(c_i-k{i\mod m})\mod 26$

容易看出，Vigenere就是由m个不同的Caesar密码组成

Vigenere的安全性

Vigenere密码隐藏了字母的频率信息，但仍未完全屏蔽明文的结构特征
若明文中两个相同字串之间的距离是密钥长度的整数倍，那么这两个子串对应的密文相同
如果密文信息量足够大，可以很容易通过统计确定密钥长度
已知密钥长度后，通过对密文字符分组就可以使用单表代替的频率统计攻击了

应对这种攻击的一种方法是将明文接在密钥词后，使得密钥长度$m=n$
然而这个方案也是易受攻击的，因为密钥和明文有相同频率特征

Vernam密码与一次一密

从上述古典密码的讨论来看，安全的加密必须有一个和明文毫无统计关系且和它一样长的密钥

Vernam密码加密基于二进制数据，且密钥循环周期很长
其加密形式为$c_i=p_i\oplus k_i$，解密为$p_i=c_i \oplus k_1$

然而尽管周期很长，其终究是有限的，统计分析仍然是可以进行的

一次一密基于朴素的思想，每次使用与消息一样长且无重复的随机密钥进行加密
次一密的安全性完全取决于密钥的随机性

然而一次一密也存在其难点，即大规模随机密钥的产生问题和密钥分配与保护问题

置换密码

栅栏密码是最经典的置换密码

栅栏密码将消息按行写成矩阵，打乱列次序后再按列读出

zhalan

单纯的置换密码很容易被攻击，只要将密文排成矩阵，配合双/三音节字母频率分析处理列的位置即可
多次置换则会相对安全很多，重构比较困难