前两天买了一本书,书收到的第一件事就去研究目录里面的密码学章节,抛开数学计算的密码学还是挺有意思的,所以请耐心看完本篇文章,我会尽可能写的简单易懂,如果本文章出现了错漏,请给我留言,我将感激不尽。

必须知道的概念

  • 1.1 研究密码编制的科学称为密码编制学
  • 1.2 研究密码破译的科学称为密码分析学
  • 1.3 密码学由以上两者共同组成
  • 1.4 信息安全的CIA三要数

    保密性 confidentiality
    完整性 integrity
    可用性 availability

必须知道的术语

  • 2.1 加密(encryption)
  • 2.2 解密(decryption)
  • 2.3 明文(plaintext)
  • 2.4 密文 (ciphertext)
  • 2.5 加密密钥
  • 2.6 解密密钥

密码体制的五部分

  • 3.1 明文空间 M
  • 3.2 密文空间 C
  • 3.3 密钥空间 K
  • 3.4 加密算法 E
  • 3.5 解密算法 D
  • 3.6 KE就是加密密钥 KD就是解密密钥

下面的公式表示,用KE加密密钥,并且在加密算法E下,加密的明文M,变成了密文C
C=E(M,KE)
下面的公式表示,用KD解密密钥,并且在解密算法D下,解密密文C,得出了明文M。
右边等式里面的变形其实就把上面的公式C的值等价代入
M=D(C,KD)=D(E(M,KE),KD)

如果KD=KE,也就是知道一个加密(解密)密钥的情况下,可以推导出解密(加密)密钥,称为单密钥密码体制,也称作对称密码、传统密码,否则称为双密钥密码体制

当KD不能由KE推出,这样公开KE也不会损害KD的安全,这种密码体制称作公开密钥密码体制,简称公钥密码体制

常见的攻击密码方法

  • 4.1 穷举攻击
  • 4.2 数学分析攻击
  • 4.3 基于物理的攻击
    这里我不想码字啰嗦,余弦精神,懒人思考

常见的攻击密码类型

  • 5.1 仅知密文攻击(ciphertext-only attack)
  • 5.2 已知明文攻击(known-plaintext attack)
  • 5.3 选择明文攻击(chosen-plaintext attack)
  • 5.4 选择密文攻击(chosen-ciphertext attack)

这里先做一个假设,因为密文是加密的,获取也无法查阅对应的明文,所以密文都是公开的

5.1 就是攻击者只拥有密文,对攻击者最:不利的情况

5.2 是攻击者有部分明文和密文,或者可以说攻击者了解明文部分字段的规律性,只有当密码经得起该类型攻击才算是可取

学生的数据库文件字段的规律性
里面一定会有姓名、学号、成绩等字段
成绩的取值范围一般都是0-100之间

5.3 攻击者能够选择明文并且得到对应的密文,常见攻击对象是计算机文件系统和数据库系统,攻击者可以利用有特殊意义的的明文优先尝试,这是对攻击者十分有利的情况

因此平时用的密码尽可能不要使用生日、电话一类的字符,而且尽可能相同密码不要使用在不同情况,以防撞库

5.4 攻击者能够选择密文并且得到对应的明文,也是对攻击者十分有利的情况,攻击对象主要是公开密钥的密码体制,比如数字签名。

密码学认为,一个可靠的密码,它的加密算法需要公开,而且需要有健壮的数学算法作为支撑。

当一个密码,不能被分析者根据可利用的资源进行破译,那么认为是计算机上不可破译的。其实说白了就是一个密码要计算几百年才能有正确答案,那么这个密码就是安全的

  • 古典密码史

    古典密码这东西比较好玩,数学难度不会很大,下面我就用自己的语言叙述一下,感兴趣的人总会有办法深入了解。

  • 凯撒加密法

    背景1:有战争,信息有加密需求
    背景2:能看懂单词的人很少,文盲率高

古罗马的凯撒大帝(Caesar)发明,这里给大家看一张图就一目了然了
这属于是加法密码,明文和密钥之间建立了一一映射的关系
明文A对应的是密文N
明文B对应的是密文O
………
明文Z对应的是啥(此处很尴尬,图片没有展示完整)
偏移量就是Key,上图算法的KEY=13

这里因为字母自有26个,所以限制了密钥长度是0-25这个范围,因为它是经不起频率分析攻击,人脑推敲一下也很轻易得出明文。当代计算机发起穷举攻击,破译是毫秒的事情,但是考虑到算法使用的年代背景,所以凯撒也算是一个成功的心机Boy
举个例子
H明文下等于7,7+key=7+13=20 20 mod 26 =20,密文就是U
0明文下等于14,14+key=14+13=27 27 mod 26 = 1,密文就是B

这里假设A-Z对应到0-25的数字
Module:取余数

可以得到公式C=E(m,k)=(k+m) mod 26

  • monoalphabetic cipher算法

    单字母加密方式,也叫做substitution cipher,替换加密法,其实还是一一映射的使用,对比凯撒加密进步在于,它的映射关系不再是偏移量,只是人为的设计一个对照表
明文 A B C D E L P Z
随机的密钥 H O U S E R X Y

明文是DCBA的话,那么密文就是
SUOH

这里的对应关系是随机产生,假设都是一一对应不重复使用字母的情况下,得出:
这个对应表的第一个字母有26种出现情况
这个对应表的第二个字母有25种出现情况
这个对应表的第N 个字母有27-N种出现的情况
所以推导出了Key的组合可能性是26!(阶乘)
26! = 4.0329146112661 * 1026

思考:
当一个字母并列的重复出现,或者在一段明文里面多次出现,比如文明apple就出现了两次P字母,假设使用上文的对应关系,密文就是HXXRE,这样攻击者统计分析后,也可以得出一份对照表,它是抵挡不住频率攻击的,因为每一个字母出现的频率都不一样。关键点在于明文和密码之间依然存在映射关系,很容易实现反推敲。

  • 维吉尼亚加密算法 Vigenre

    这个算法就解决了上面提出的思考题 ,打破了一一对应的关系。思路是用一个字母对应多个字母,或者多个字母对应一个字母,所以也叫做polyalphabetic cipher算法,多字母加密算法。
  1. 维吉尼亚算法会选取一个Key,可以自己设定值,假设是K6=houser(6位长度)
  2. 把Key的长度拓展到和明文一样长,假设我们的明文是 M=php is the best language(20位长度,空格不计)
  3. 接着K的长度要和M的长度一致,所以K20=houserhouserhouserho(重复自己,得到20位长度的Key)
  4. 这时候把M的第一位和K20的第一位合并,得到ph
  5. M的第二位和K20的第二位合并,得到ho
  6. M的第三位和K20的第三位合并,得到pu
    7.查维吉尼亚表,两个字母分别对应横纵坐标
    查表ph就是w,ho就是v,pu就是j
    此时,明文的PHP就等于密文wvj,方法如上,可以明文全部转换成为密文,这里的两个p对应了不同的密文,是上面提及的算法里面不能实现的。维吉尼亚表是全部人都可拥有的,但是Key只能是约定通讯的人才知道

假设A-Z可以用数字0-25表示
就会得出维吉尼亚的数学表达式
c=(k+m) mod 26
p和h对应的就是15+7=22=w
h和o对应的就是7+14=21=v
p和u对应的就是15+20=35=j=26+9=9

有没有觉得很神奇,虽然提高了分析的难度,但同样的可以使用频率分析的攻击手段对维吉尼亚加密进行攻击,polyalphabetic cipher算法的弱点是key会重复来填充自己的长度,接下来就要介绍下一个算法弥补它,所以学习古典密码是很有意思的逻辑问题,了解古典密码之后再去看看现代密码学,会很有意思。

  • autokey cipher

    它解决了key长度问题,就是密钥不够长,自动让明文的头部开始充当密文,数学公式也是一样的。还是拿上面维吉尼亚的例子,当K6=houser,相对于明文还差14位长度,根据autokey,K20=houserphpisthebestla

    autokey是由维吉尼亚提出的,上文的维吉尼亚算法并不是她提出,相关内容可查阅资料

这样自动化生成Key的好处是在明文传递的时候,不受到Key长度的限制而限制,但是依然存在攻击的漏洞可以破译这种加密,所以引入了下面的算法

  • vernam cipher

    K20=houserphpisthebestla的生成就是由K6加上明文组合,现在我们只保留K6,后面需要的长度用随机数取代,因为和明文没关系,所以健壮性会很高,数学公式还是一样的。

    思考:
    那我为什么不直接随机生产一个K20,最好是一次性使用之后就不再使用,这样还抵挡被统计分析攻击

  • on time pad

    OTP其实就是一次性密钥,但是OTP是可以伪造的,如果密钥不一致,会导致解密出来的内容也会不一样。OTP的好好处也在在暴力破解的情况下,会得到很多组可能正确的明文,增加了密码分析的难度。
    OTP在冷战时期疯狂使用,因为间谍被抓获的时候,只需要提供一个虚假的精心构造的Key,就会使得明文变的不一样。
    实现维吉尼亚算法的Python脚本

    OTP实现的难度在于key只能让接受和发送者知道,而且必须是随机生成的key(不能重复使用)。这样的话就需要发送和接受的明文长度需要一样才行,OTP禁不起已知明文攻击。

    • 好玩的福尔摩斯密码