前言

前几天在用wireshark的时候，突然对密码学来了兴趣，所以在看有关的书籍（说不定以后能够派的上用处）。然后顺带写点笔记分享给大家。

一、术语

括号里面的中文全部是用google tranlate翻译过来的。懒得上百度去查中文术语了

Plaintext（纯文本）与Ciphertext（密文）分别是加密之前的文本和加密之后的文本。

Encryption scheme （加密方案）：由3个部分组成——Key generation algorithm G, Encryption algorithm E, 以及 Decryption algorithm D.

Key generation algorithm （密钥生成算法）：一个基于概率分布来生成 key 的算法。

Encryption algorithm （加密算法）：输入plaintext 和key ，输出ciphertext ，但算法本身不要求是derministic（即，输入相同的m和k，可以输出不同的c）

Decryption algorithm（解密算法）：输入ciphertext 和key ，输出plaintext 。从实际出发，我们要求算法是derministic（不然，A可以从一个加密的文本中解密出apple，B可以从相同的文本中解密出banana，就很奇怪）

二、Frequency Analysis（频率分析）

无论是英文还是中文，都有一个频繁出现的字母和单词。从这个角度出发，我们就可以破译一些用传统加密方式（比如说caesar cipher）加密的文本。

从Wikipedia给出的数据来看（https://en.wikipedia.org/wiki/Letter_frequency），英文中最常用的几个字母为a, e, i, o；所以我们如果手里拿到一个用caesar cipher加密的文本的话（通过字母位移来加密文本的一个古老的方法），我们可以统计一下文本里面每个文字出现的次数和比率，然后试着和a, e, i, o对应，然后我们就可以顺藤摸瓜找到位移量，也就是我们的key，然后我们就能成功解密我们的文本了。

三、Perfect secrecy

Perfect secrecy如它的名字一样，我们的密码破译者如果只有ciphertext c的话，是从我们的c里面获得任何我们加密算法的信息的。用公式表达就是

也就是，对于一个ciphertext c，任何plaintext m都有相等的概率被加密为c

很明显，我们的caesar cipher不满足这个条件，假设我们手里有密文ABC，那么不论我们的key是什么，我们的原文都不可能是BBB，但我们的原文有可能是BCD（如果我们的key k=1的话），故:

所以不满足我们的perfect secrecy

四、One Time Pad

One time pad的加密方式非常简单，对于我们长度为d的plaintext , 我们通过G生成一个与m同等长度的key , 然后我们通过一个bitwise的xor运算得到我们的ciphertext ，

这里有一段自己写的python代码来作为演示：

key和code都太长了，我就不列出来了，感兴趣的可以自己运行一遍上面的代码。

这里针对我们的plaintext m我们的key k只使用一次，每当我们换一个新的m的时候，我们也要重新生成一个新的k。

这个One time pad满足我们的perfect secrecy，在此就不证明了，而是举一个非常简单的例子：

五、Shannon's perfect secrecy theorem

Shannon perfect secrecy theorem给出了，如果某个encryption scheme具备perfect secrecy，那么它必定满足，这里K代表key space（我们所有可能的key的集合），M代表message space（我们所有可能的plaintext的集合）。具体证明过程参见这个slide的第28页（https://www3.cs.stonybrook.edu/~omkant/L02-short.pdf）

后记

密码学还是挺有意思的。今天先写这么多。

参考资料：

Jonathan Katz, Yehuda Lindell - Introduction to Modern Cryptography

（在文中已注明引用地址的内容将不再重复列在这里）

THE END.