跳转至

传统密码技术

置换密码

又被称为换位密码，它根据一定规则中心排列明文

  • 特点：保持明文的所有字符不变，只是利用置换打乱了明文字符的位置和次序
  • 常见置换密码
    • 列置换密码
    • 周期置换密码：将明文P按照固定的长度m分组，然后对每组按1，2，……，m的某个置换重排位置从而得到密文C

列置换密码

加密过程

将明文P以设定的固定分组宽度n按行写出，即每行有n个字符。若明文长度不是n的整数倍，则不足部分用双方约定的方式填充，如双方约定用空格代替空缺处字符，不妨设最后得字符矩阵为\([M]_{m\times n}\)

按某一置换\(\sigma\)交换列的位置次序得到字符矩阵\([M_P]_{m\times n}\)

将矩阵\([M_P]_{m\times n}\)按照列1，2，……，n的顺序读出得到密文序列C

若要解密，则使用加密所用置换的逆置换\(\sigma^{-1}\)交换列次序，再按行的顺序依次读出矩阵\([M]\)

周期置换密码

将明文串P按固定长度n分组，然后对每组中的子串按1，2，……，n的某个置换重排位置从而得到密文C。其中密钥\(\sigma\)设定了每个分组中子串位置置换的方法。解密时同样对密文C按长度n分组，并 按\(\sigma\)的逆置换\(\sigma^{-1}\)把每组子串重新排列位置从而得到明文P。

比如有字符串S=hello world!，按照固定长度3分组，得到S'=(hel)(lo )(wor)(ld!)"，按照\(\sigma=(132)\)进行置换，得到S"=lhe lorwo!ld

代换密码

按照一个明文字母是否总是被一个固定的字符代换进行划分：

  • 单表代换密码
    • 对明文消息中出现的同一个字母，在加密时都使用同一固定的字母来代换，不管它出现在什么地方。
  • 多表代换密码
    • 明文消息中出现的同一个字母，在加密时不是完全被同一固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。

单表密码-仿射密码

  • 明文P=密文C=\(Z_{26}\)
  • 加密：\(E_k(m)\equiv am+b \mod n=c\)
  • 解密：\(D_k(c)=a^{-1}(c-b)\mod n = m\)
  • 密钥\(K=\{(a,b):a,b\in Z_{26}并且\text{gcd}(a,n)=1,n=26\}\)

多表密码-维吉尼亚

多表代换密码指的是利用多个单表代替密码构成的密码体制，载明文进行加密的过程中依照密钥轮流使用多个单表代替密码

  • \(M=(m_1,m_2,\dots,m_n)\quad K=(k_1,k_2,\dots,k_d)\quad C=(c_1,c_2,\dots ,c_n)\)
  • 加密变换：\(E_{ki}(m_{i+td})=m_{i+td}+k_i\mod n\)

多表密码-希尔密码

加密函数定义为

\[(c_1,c_2,\dots ,c_n)\equiv (p_1,p_2,\dots, p_n)\left[\begin{matrix} k_{11}&k_{12}&\dots& k_{1n}\\ k_{21}&k_{22}&\dots &k_{2n}\\ \dots& \dots & \dots&\dots\\ k_{n1}&k_{n2}&\dots &k_{nn}\\ \end{matrix}\right](\mod 26 )\]

其中密钥矩阵需要保证为一非奇异矩阵，且满足(det(k),26)=1

Enigma

从19世纪20年代，人们开始发明各种机械加密设备用来处理数据的加解密。起初普遍使用的是转轮机和转轮加密算法。

转轮密码机是由一个用于输入的键盘和一组转轮组成，每个轮转上有26个字母的任意组合。转轮之间由齿轮进行连接，当一个轮转转动时，可以将一个字母转化成为另一个字母。

  • 组成结构：
    • 键盘：输入明文
    • 接线板：单表代换
    • 转轮：多表代换
    • 反射器：它的静态性使得加密机也可以作为解密机
    • 每日密码：密钥加密密钥
    • 通信密码：类似会话密钥

传统密码的分析与破译

单表代换密码分析（频率）

  • E，有概率大约0.120。
  • T，A，O，I，N，S，H，- R，每个有概率在0.06～0.09间。
  • D，L，每个有概率大约0.04。
  • C，U，M，W，F，G，Y，P，B，每个有概率在0.015～0.023之间。
  • V，K，J，X，Q，Z，每个概率少于0.01。

当考虑位置特性时，字母A，I和H一般不作为单词的结尾，而E，N和R出现在起始位置比出现在结束位置的概率更小，字母T，O和S出现在单词前后位置的概率基本相同。

频率分析法

  • 首先统计密文中每个字母出现的频率，确定其对应的范围(一般而言，出现频率最高的字母对应的应该是e)
  • 再辅以字母组合、位置特殊性以及连续的同一字母等特性，容易确定明文字母与密文字母的对应关系。
  • 密文越长越容易破解

多表代换密码分析（重合指数）

Hill密码分析（明文-密文对）

所谓明文-密文对分析法是指攻击者不仅获得若干密文，而且还得到这些密文对应的明文，通过若干明文-密文对以分析出密钥的方法。

假设攻击者已经知道正在使用的希尔密码的密钥长度为n，并且知道至少n个不同的明文-密文对，则可以通过构建方程求解密钥矩阵

\[\left[\begin{matrix} k_{11}&k_{12}&\dots& k_{1n}\\ k_{21}&k_{22}&\dots& k_{2n}\\ \dots& \dots & \dots&\dots\\ k_{n1}&k_{n2}&\dots& k_{nn}\\ \end{matrix}\right]=\left(\left[\begin{matrix} p_{11}&p_{12}&\dots& p_{1n}\\ p_{21}&p_{22}&\dots& p_{2n}\\ \dots&\dots&\dots&\dots\\ p_{n1}&p_{n2}&\dots& p_{nn}\\ \end{matrix}\right]^{-1}\times\left[\begin{matrix} c_{11}&c_{12}&\dots& c_{1n}\\ c_{21}&c_{22}&\dots& c_{2n}\\ \dots&\dots&\dots&\dots\\ c_{n1}&c_{n2}&\dots& c_{nn}\\ \end{matrix}\right]\right)(\mod 26)\]

单表替换密码快速破解（原理未知）：https://quipqiup.com/