顿搜
飞过闲红千叶，夕岸在哪
类目归类
密码学中的代替与置换技术
10/06
一、单表代替密码
每条消息用一个字母表给出从明文字母到密文字母的映射。单表代替密码较容易被攻破，因为它带有原始字母使用频率的一些统计学特征。
攻击方法可以采用语言的规律：
- 1、频率特征：单个字母的频率特征
- 2、重复特征：双字母组合的频率特征
- 3、连接特征：常用单词拼接的一些规律
解决办法：
- 1、对每个字母提供多种代替（一个明文元素可以用多种密文元素代替），称为同音词。对每个明文元素分配的密文元素的个数与此明文元素的使用频率成一定比例关系，但是，明文中的每个元素仅仅只对密文中的一个元素产生影响，多字母语法模式（比如双字母音节） 仍然残留在密文中。
- 2、对明文中的多个字母一起加密。
- 3、采用多表代替密码。
1、Caesar密码
已知最早的代替密码是由Julius Caesar发明的Caesar密码。它非常简单，就是用字母表中的后面第三个字母代替本身，属于单字母代替密码。容易穷举攻击。
这种移位密码通用表达式为：
- C = E ( k , p) = ( p + k ) mod 26.
- p = D ( k , C ) = ( C - k ) mod 26
2、Playfair密码
最著名的多字母代替密码，他将明文中的双字母音节作为一个单元并将其转换成密文的双字母音节。密钥为一个5*5的矩阵。但它的密文仍然完好地保留了明文语言的大部分结构特征。
二、多表代替密码
对单表代替进行改进，使得在明文消息中采用不同的单表来代替，称之为多表代替密码。
1、Vigenère
是多表代替最著名也是最简单的密码。
通用表达式：
- Ci = ( pi + ki mod m ) mod 26
- pi = ( Ci - ki mod m ) mod 26
破译：能否取得进展将取决于能否判定秘钥词的长度。
1、通过计算重复密文序列间距的公因子，就可猜出秘钥词的长度
2、如果秘钥词的长度为m，那么密码实际上包含了m个单表密码，可以用频率特征对单表密码分析
优化：秘钥词的周期性可以用与明文信息一样长的不重复秘钥词来消除。
2、Hill密码
由数学家Lester Hill 在1929年发明。如果矩阵A有非零的行列式，则这个矩阵的逆Aij-1 = (detA)-1 • (-1)i+j •Dji 。其中Dji是矩阵去除第j行和第i列后的子行列式的值。detA是A的行列式， (detA)-1是detA mod26的逆。将每个字母指定一个数值（a=0，b=1，·······，z=25）。
通用表达式：
- C = E( K , P ) = PK mod 26
- P = D( K , C) = CK-1 mod 26 = PKK-1 = P
优点：它完全隐蔽了单字母频率特征，所用矩阵越大，所隐蔽的频率信息越多，足以抵抗唯密文攻击。一个3*3的矩阵不仅隐蔽了单字母频率特征，还隐蔽了双字母频率特征。
缺点：比较容易被已知明文攻击击破。
3、Vernam密码
其运算时基于二进制数据而非字母。Vernam提出使用连续的磁带，其最终也将循环。所以事实上是使用周期很大的循环密码。
通用表达式：
- ci = pi ⊕ ki
- pi = ci ⊕ ki
改进：使用与明文相同长度的的秘钥对其进行加密，避免了循环。
4、一次一密
Joseph Mauborgne 建议使用与消息一样长的却无重复的随机秘钥来加密消息，而且一个秘钥只对一个消息进行加解密，这就是一次一秘，它是不可攻破的，试试唯一的具有完善保密的密码体制。
一次一密的安全性完全取决于秘钥的随机性。
三、置换
代替是将明文中的字母替换成密文中的字母，而置换是将明文顺序打乱。
