littleRound 小园香径 - lxy的个人博客

古典加密算法介绍(二)

2019-03-18
littleRound

古典加密算法介绍(二)

前一篇:【古典加密算法介绍(一)】

前言

上一篇中介绍了对称加密的一些基本概念并给出了一些基于置换的基本加密算法。本篇将继续就置换加密中的多字母密码表以及另一类基于换位的古典加密算法做一介绍。

相关算法

维吉尼亚密码(Vigenère Cipher)

  • 基于置换
  • 属于多字母密码表的一种(即在加密过程中使用不同的字母置换的方法)
  • 密钥是字符串
  • 加密过程:拓展密钥(循环反复),转换为数字相加取模并转换回来
  • 解密过程:类似加密,变为密文和密钥的减法
  • 破解方式:通过相同子串的公约数可大致猜出密钥长度(循环节),再对于每个周期同一个位置进行单表置换密码类似的破解即可

Vigenere

维尔南密码(Vernam Cipher)

  • 基于置换
  • 属于多字母密码表的一种
  • 通过一个密钥流生成器(key stream generator)来持续生成二进制密钥(密钥流生成器是通过有限的密钥决定的)
  • 加密过程:将信息转换为二进制,通过将明文与生成密钥进行异或操作来达到加密效果
  • 解密过程:由于异或操作可逆,两边共享生成器,故再进行异或可得到明文
  • 破解方式:由于密钥流生成器信息量有限,其生成的密钥也会在一定长度后重复循环之前的结果,故弱点与维吉尼亚密码相同

Vernam

一次性密码本(One-time Pad or OTP)

  • 基于置换
  • 属于多字母密码表的一种
  • 加密解密过程与维尔南密码类似
  • 维尔南密码中的生成密钥换成预先给好的密码本
  • 密码本长度足够长,不循环使用
  • 由于密钥使用一次就丢弃,所以理论上无法破解

加密解密过程与维尔南密码类似,故不再重复给出图示

栅栏密码(Rail Fence Cipher)

  • 基于换位
  • 方法较为原始,无密钥
  • 加密过程:将原序列奇偶拆分,输出奇数序列+偶数序列
  • 解密过程:序列二分,进行归并
  • 破解方式:重组即可

RF

交换列顺序(permute the order of columns)

  • 基于换位
  • 密钥是一个1-n的排列
  • 加密过程:将原序列按密钥长度切分,每段写在一行上;再按照密钥标明的列顺序写成密文
  • 解密过程:拼回去
  • 破解方式:二连字三连字频率分析的攻击
  • 栅栏密码可以看作交换列顺序的一类特殊情况

permute_col

转轮机(Rotor Machines)

  • 基于置换和换位(密钥换位)
  • 指代一类系统(而非单种)
  • 历史中有机械原型(如恩尼格玛(Enigma)密码机),可参考WIKI资料
  • 加密过程(某种转轮机的一个例子):
    • 转轮机有三个转子,每个转子有26个状态,对应26种单表置换密码(见【古典加密算法介绍(一)】
    • 三个转子依照与操作器由近到远(也就是先计算的较近)分为快、中、慢
    • 任何时刻,转轮机会处于某个状态,加密和解密用的密码机初始状态相同
    • 一个状态指代其三个转子状态组成的唯一元组
    • 当输入一个字母时,按照当前状态依次进行三次单表置换输出一个字母,并使得转轮机进入下一个状态
    • 下一个状态指:快转子向下旋转一次(换成另一种单表)
    • 需要注意的是,快转子每转26次,中转子会转一次;中转子每转26次,慢转子会转一次
    • 将明文一个字母一个字母输入转轮机即可输出密文
  • 解密过程:
    • 构造完全模拟加密转轮机,但单表置换复合结果为加密结果逆解密转轮机
    • 加密转轮机类似,将密文一个字母一个字母输入解密转轮机即可输出明文
  • 破解较为困难,需要亿级别的密文才能进行较为有效的分析

rotor

结语

关于古典加密算法的介绍到这里就结束了。

书中还提到了一些关于隐写术(steganography)的内容,如铅笔描字、隐形墨水、针孔标记、无墨打字、藏头首字母等远古级技巧,虽然十分有趣但在本文讨论范围之外。

对于DES(3DES)、AES等现代投入生产实践的算法,后面有时间再单开专题,如果有人想看的话可以给我发邮件催更,也可以在下方评论区留言(需要小飞机)。


相关文章

评论区(DISQUS)