密码学备忘录-古典密码与现代密码简介

1. 古典密码

1. 置换密码
2. 代换密码
3. 乘积密码

2. 置换密码 Permutation Cipher

• 根据一定的规则重新排列明文，以便打破明文的结构特性。

3. 代换密码 Substitution Cipher

• 基本方法:建立一个代换表，加密时将明文字符通过查表代换为对应的密文字符。
• 代换表就是密钥。

3.1. 单表代换密码(Monoalphabetic Cipher)

凯撒密码（Caesar[ˈsiːzə(r)] Cipher）

原理: 将每个字母用其后的第三个字母替换。

• $E_n(x)=(x+n)mod26$
• $D_n(x)=(x-n)mod26$

x是letter，n是shift number

凯撒密码的问题：

• 密钥空间太少导致的brute force search
  • 唯密文攻击（知道Cipher algorithm）
• 如果不是通过简单位移而是密码本代换那密钥空间会大很多（26!），破解主要采用词频分析

单表代换密码的问题：

• 在密钥空间较小的情况下，采用暴力破解方式
• 在密文长度足够长的时候，所有单表代换密码都难以经受语言特性的统计攻击(language characteristics),因为，单表代换保持明文的统计特性不变。
  • Language Redundancy and English Letter Frequencies
  • 没有掩盖明文不同字母出现的频率，出现频率最高的密文字母很可能对应于出现频率最高的明文字母。
• 当密钥空间足够大，而密文长度足够短的情况下，破解较为困难

3.2. 多表代换密码(Polyalphabetic Cipher)

多表代换密码是以两个以上代换表依次对明文消息的字母进行代换的加密方法

• Playfair密码
• 维吉尼亚密码(Vigenère)
  • 与单表代换的区别：一个字母可以被加密成不同的密文
  • 破译维吉尼亚密码的关键在于它的密钥是循环重复的。 如果我们知道了密钥的长度，那密文就可以被看作是交织在一起的凯撒密码，而其中每一个都可以单独破解
    • Kasiski Method卡西斯基试验：密钥相同、出现明密文重复段对应

      两个 DYDUXRMH 的出现相隔了 18 个字母。因此，可以假定密钥的长度是 18 的约数，即长度为 18、9、6、3 或 2。而两个 NQD 则相距 20 个字母，意味着密钥长度应为 20、10、5、4 或 2。取两者的交集，则可以基本确定密钥长度为 2

对于多表替换加密来说，加密后的字母几乎不再保持原来的频率，所以我们一般只能通过寻找算法实现对应的弱点进行破解。

3.3. 一次一密 one-time pad cipher

之所以叫做一次性密码本，是因为加密所用的密钥是一次性的，即密钥只会使用一次，不会出现因为密钥泄露导致之前的加密内容被解密。 即使密钥被泄露了，也只会影响一次通信过程

4. 乘积密码 Product cipher

• 多个加密技术的叠加
• 乘积密码是构造现代密码的基本技术之一。
• 转轮机
  • 密钥空间$26^3$

4.1. 恩格玛机(enigma machine)

• RotI : the definition of the permutation (on letter codes) of Enigma rotor I
  RotIinv — it is the inverse of the rotor I permutation
• RefB — it is the definition of the (involutive) permutation of Enigma reflector B
• A one-rotor Enigma passes a letter through the rotor, through the reflector, and back through the rotor. EnigmaGuts as the set of replacements that express these.

ReplaceAll[ReplaceAll[lettercodes,RotI],RotIinv]

• Enigma works by not only permuting letters as we have seen, but my moving the rotors too

Enigma1[x ,n ] := Mod[((ReplaceAll[Mod[x+n,26,1],EnigmaGuts])-n),26,1]
Table[Enigma1[1,n],fn,0,25,1g]

• You see that it takes lettercode x, displaces it by n, applies the EnigmaGuts permutation to it, and displaces it back (i.e. by -n this time)

EnigmaMachine[text_, key_] :=MapThread[Enigma1,
{text, Table[Mod[n, 26, 1],
{n, Mod[key, 26, 1],
Mod[key, 26, 1] + Length[text] - 1, 1}]}];

• key就是初始位置设定，bombe就是来破解找出key的
• cribs: short sections of plaintext thought to be somewhere in the ciphertext
  • 所谓Crib，指的是一段猜测出来的明文与密文中字母的一一对应关系

总结

• 主要工作原理
  • 一个单转子的Enigma将一个字母通过转子，通过反射器，再通过转子传回，由此形成映射
• 主要破解原理
  • He developed the idea of cribbing, i.e. guessing that a certain word or phrase would occur, and then using that insight to break the cypher
  • The number of cycles and their lengths is independent of the plugboard
  • “No-self-encrpt” property

5. 现代密码(公钥密码)

-对称密码, Symmetric Cipher Model

• 1949年Shannon (1916-2001)发表了《保密系统的信息理论》
  • 这篇文章产生了信息论
• 实现
  • DES
  • AES
  • RC4
• 特性
  • 单密钥密码
    • 加解密同密钥
  • 加密速度快
  • 密钥分配难
  • 身份认证难

Y = E(K,X)
X = D(K,Y)

• 非对称加密（Asymmetric Cryptography)
  • 1976年Diffie和Hellman发表了《密码学的新方向》

6. 参考

• 密码学简介 - CTF Wiki