古典密码
从人能够将信息用笔或者类似的东西记下来之后，记下来的东西不想某些人知道就已经变成常见需求了。密室逃脱或者游戏中的经常能够见到的凯撒密码，那个旋转纸条在笔上然后从上往下读的那种密码（忘了叫啥了）都是古典密码。在不提前告诉加密方式的情况下，往往需要丰富的经验（或者提示）才能有机会解密出来
古典密码概括起来也简单，就是上文两种的高度概括：替换和置换。替换就是双方先约定好一张表，将原来的字符用其他更奇怪的东西做替换，同时也能用这张表反过来找到原字符。替换则是不改变字符，而是通过约定的方式改变顺序。
我们都知道古典密码不安全，毕竟都是老古董了。针对替换密码，我们根据字母出现的频率不同，加上常见词语的识别，可以很快的解密出一般的替换密码。
quipqiup.com 如这个网站，就能够简单的快速解密一般的替换密码
但古代人也不是吃闲饭的 (=ﾟωﾟ)=他们也知道这个方法，也可以用一天或更快的时间解密出来。至此，密码学的猫鼠游戏（主线）就开始了。
不妨思考为什么这个替换密码如此快速能够被破解，除了替换出来的东西太奇怪之外（指中世纪的鬼画符），最主要的原因还是这张表太短了。
一个简单的升级是多表替换密码。思想也非常简单。第一个字符用 A 表，第二个字符用 B 表，第三个字符用 C 表（之后再轮回 A 表）。
这样，攻击者就需要同时解密三个表，工作量增加，而且在不知道有多少个表的情况下字母频率也不管用了。这在消息短的时候已经具备相当好的加密效果了。可是在长消息下，通过暴力暴力暴力地枚举还是有机会解密出来的（不过很明显，这个时候在中世纪的你更想知道的是该怎么拿到表而不是自己傻乎乎地算了）
有人更近一步，觉得“表”这个名字太 low 了，所以把这个东西抽象出来称为密钥。表的使用方式不止一种，则称为加密函数。如此一来，和前后消息组合在一起就构成了抽象的加密四大件 (ゝ∀･)
m（Message）/ plain text （明文）加密前的数据 Enc（Encode）加密函数 ｜ Dec（Decode）解密函数 k（Key）密钥 c（Cipher 密文）加密后的数据
这些是密码学里面的常用的字母标识。我们说一个密码设计上正确，首先要保证就是加密后再解密得到的还得是原文才行嘛，这就可以写成：Dec_k(Enc_k(m))=m （写在下标位置）
此后人们通过设计出越来越复杂的加密函数，让破解变得越发越困难。但机械和电子技术的发展让破解变得越来越容易。就这样双方此消彼长，尔虞我诈，无所不用其极，今天这个算法号称天下第一坚固，明天就有一个论文把它辩得体无完肤……
就这样密码学至今还在发展，此串完结！ᕕ( ᐛ )ᕗ
( ᑭ`д´)ᓀ))д`)：别骗我，那你说这个密码学还有什么意思，我还能脸滚键盘有机会敲出世界上最好的加解密方案的代码呢，那你说这算什么事嘛。
(`ε´ ) 很遗憾，密码学在前几百年就是这么猥琐的。不过后来一旦打起仗来，人们的需求就极大的推动了思考，密码学也就变成了另一番模样，下面才是真正精彩的地方。
一战开始，无线电技术普及极大的改变了战场信息的传递方式，各国开始重视对无线电信息的加密。德军和英军都采用了不同的加密技术来保护军事通信。（不过还都是老一套替换置换啥的，可能高级点罢）。英国设立了专门的破译机构“40 号房间”，雇了一群聪明人来想办法破解，还真让他搞成了几个。
有了这次教训，世界各国开始重视密码学的发展，让和密码学关系最紧密的数学家来研究一下。数学家会啥啊，他们就会阿基米德牛顿那一套公理化体系推理，你冷不丁的丢一个这么稀奇古怪，好像要将智商代入公式一般的脑经急转弯的密码学给他们，能想出啥东西啊？
……还真想出点好东西了
一次一密（One-Time Pad，OTP）
由美国某工程师于 1917 年提出，这玩意一开始出来的时候都没人鸟它，直到大概 25 年之后，香农挖坟挖到它，顺便用他创立的学科证明了这玩意确实某种意义上是无敌的。
都说万物皆数，信息也能表示成数字，而数字最简单的表示形式就是二进制，我们就把这个由 0 和 1 组成的字符串看作 m（Message）。加密函数和解密函数如果是同一个函数就简单了，加密的正确性要求这个函数是一个自身是自身的逆的函数，“异或”这个运算就很不错。既然是异或，那么就要密钥长度和明文一样。可以表示成：Enc_k(m)=k^m ,Dec_k(m)=k^m. 只要双方提前交换好密钥，将要发送的信息每个比特异或上对应位置的密钥发送出去，接收方再用密文异或上密钥就得到了明文。
你说你忘了异或是什么？很简单，异或就是一种“半加法”，1 异或 1 是 0（进位了），其他情况则和普通的加法一样。很明显 a 异或两次 b 的结果一定是 a，因为 2b 的最低位一定是 0。所以异或满足可逆的性质。
如此，我们就整出了“最安全的加密”——一次一密。它有多安全呢？很遗憾，我们此时还不知道安全的定义，发明它的人也不知道，直到二战快结束的时候香农提出了他的想法。我们暂时按下不表，此时我们只需要知道这个是一个“近乎完美”并且“没啥卵用”的加密方法就行了，因为二战要来了，密码学开始作为真正的焦点人物登上历史舞台。我们计算机的祖师爷图灵，马上要出场了。
二战中的密码系统
苏联：老一套多字母替换密码，用多个字母来替换一个字母，后面根据预定的情况不断地变换规则。这些规则可能涉及添加、删除或替换字母。没啥意思不说了
美国：这就有点意思了，电影《风语者》讲的就是这个。纳瓦霍语是一种地球上就那么一点人会说的语言，其语法和发音对于非纳瓦霍人而言也几乎无法学习，他们将常用的军事术语和原始的纳瓦霍词汇对应起来（一对多），然后请活人当编解码器。这么做还真的管用，整个二战期间还没有被破译过。
德国：典型失败案例。采用的是一个名为“enigma”的密码机来加密，长得大概和打字机差不多，按下键盘，加密后的对应字母灯泡就会亮起来。大概的操作方法如下：先用 10 根连接线两头分别插在 26 个洞里（一个洞只能插一根，也就是剩 6 个），然后转动机器上的转盘（转盘上刻度有字母标识，通过密钥可以确定位置）。设定完就可以愉快的敲字了，敲字的时候圆盘会不停的转动。因为转盘与接线的状态很多，所以德国佬很放心，觉得肯定破译不了。知道密码机内部连线泄露给了一个法国情报员也没放在心上。没想到这份情报兜兜转转到了波兰手里，由一名波兰数学家看出端倪了：如果每天的初始设置相同的话，收集大量信息的情况下可以推断出加密机器的内部设置，并逐步破译出加密信息。
英国的情报机构（没错又是他）又招募了一批数学家（图灵也在里面）来破译密码，图灵创新性地提出用机器代替人工的一种可行性方法：炸弹机（Bombe），用来高效率 24 小时无休的破译 enigma。毫无思考能力的机械结构通过巧妙设计，能够完成设定好的计算和逻辑任务，这便是计算机的雏形。
为什么有这么多个状态也会被破译？怎么衡量一个加密系统的安全性？说到底啥是安全？有没有能用数学上的东西来说明一下？这就要说回香农了。我想也不必多介绍这位最牛本科生了，他的毕设就是几个学科的基石，他借用了数学上谁也想不到的工具——概率论来描述信息的传递，当然也能够很好的描述加密这种对信息的二次加工的行为。
因为这个对于密码学来说实在太重要了，所以我不得不展示一些数学的公式来精确的描述其含义。下面我们一步步推导，来看看这个安全定义是怎么产生的 | ω・´)
安全目标一：敌手不能够得到密钥 k。（如 enigma 机的初始信息和机器状态）
这个安全吗？很明显，这完全不是我们想要的安全。试着想一个最幼稚的置换加密：从后往前写。它甚至没有密钥（或者你硬要说这是步长 -1 的栅栏加密也行），但是这安全吗？显然不行嘛。除了特例，也能这么想：如果有某种方法在不得到 k 的情况下就能得到 m，那么何必绕一圈呢，我直接拿到 m 就行了嘛。
安全目标二：给定密文 c，很难恢复整个明文 m
也不大行，如果我需要破译的信息就是敌军攻击的时间，而敌人刚好发送的是“致我最敬爱的上校，如果你能够与我共进晚餐就最好不过了，如果没有时间的话也无妨，顺带一提攻击时间为 1900”，那么你只要解密最后的几个字符就够了。关键在于明文有价值的地方不能简单的假设分布均匀，必须完完整整的保护起来
安全目标三：给定 c，很难恢复任何 m 的字符
看起来不错？其实在特定高性能的要求下这个目标确实是一个不错的妥协方案，但是从密码学的角度来说，它还有十足的漏洞：假设我有两个消息，一个是西部战线发过来的 900，一个是从东部战线发过来的 3000。我知道这个加密方法是：c=m+k，这个时候我确实不知道两个的任何一个的时间（任何一个字符），但是我知道西部战线的时间肯定更小一点，那么我就更有必要去防守西部战线。（假设两个消息共用一个 k）
这里的关键在于恢复字符并不是泄露消息信息的唯一方式，可以通过比较，差分，压缩等方法去对信息进行提取和利用，这里就是密文的大小关系泄露了明文的大小关系，从而泄露了关键信息
安全目标四：不管攻击者已经掌握了什么信息，密文都不应该泄露任何有关底层明文的额外信息
这个看起来没问题吧？确实，没什么问题。只不过这里的额外信息指的是啥呢？我们的香农同学给出了他的见解：
香农提出了两个相当苛刻的要求：（Pr 表示概率）
- 密钥的均匀性：密钥在它能够选取的范围里被选取到概率是相等的，即对于所有密钥 k∈K，有 Pr[K=k]=1 / (K 的大小)
- 唯一映射：知道 m 和 c 的情况下，只存在唯一的 k。这意味着每一个明文都能通过唯一的密钥映射到一个密文上，并且没有两个不同的明文能够产生相同的密文
如果满足上面的加密形式，我们就能够（自行）推导出敌手就无法从 c 中获取关于明文的任何额外信息：写成公式就是 Pr[M=m|C=c]=Pr[M=m] ，这说明了
明文和密文之间没有任何统计关联，密文是啥完全不影响明文是啥
这就是香农给出的关于“信息论安全”的数学定义，也就是我们前面提到的安全目标四。这看起来就强的不行吧，我们来尝试证明一下一次一密的信息论安全性：
我们假设我们能够在与 m 长度一致的随机 01 字符串中均匀随机的选取 k，此时满足第一个要求。m^k=c 等价于 k=c^m ，此时满足第二点，所以满足信息论安全。
信息论安全有多强呢？下面是一个直观理解的例子：有一个方程 x+y=1，x 是明文，那么此时 x 有无限多解，也满足信息论安全。这就是理论上不可破解（实际上也当然不可破解）。国际上的“通电话”用的热线加密用的方法就是这个玩意。
既然信息论安全这么厉害，为什么现在没有广泛应用呢？要达到这种程度的安全，就必须承受相应程度的代价：密钥必须和消息一样长。
这个结论可以从唯一映射要求中推导出来（后文的一切信息都看成二进制串）：因为知道 m 和 c 的情况下，只存在唯一的 k 与之对应，那么只需要固定 c，然后让 m 取不同的值，k 相应的就必须有这么多种不同的取值才能满足需求，这就要求 k 和 m 的长度要一样。
想象一下，如果你要加密一个 1G 的图片，必须事先安全地交换 1G 的密钥才能保证此加密的有效性，这显然是不可接受的。我们日常中习以为常地用一个短一点的密钥去加密长的消息，在这里可能实现吗？
很遗憾，如果密钥长度变小，密文解密的空间就一定会变小，那么就一定导致在得知密文下的明文的概率不同于明文本身的概率，这就不满足我们构想的信息论安全的定义了。
我们使用密码学的名词总结一下：能够达到信息论安全的加密方案称为“完善保密加密”，它的效果是密文的分布和明文的分布是完全没有关系的。
我知道你很急，你已经迫不及待的想引入“没那么安全的安全”的定义了，但你先别急，因为我们还需要再深入研究一下才能走的更远，因为这个安全定义（明文密文分布没有任何统计关联）并不是很好用。我们引入两个更好用的东西：不可区分性和基于若干交互游戏的证明 (Game-based Proof)
不可区分性（IND，indistinguishability）
什么是不可区分？不可区分就是两个本来不同的东西，加工之后没有能力分辨出来哪个是哪个。写成公式就是这样：对于任意给定的 c 和 k，任意两个 m 和 m’ 有 Pr[Enc_k(m)=c] = Pr[Enc_k(m’)=c] 始终成立。这个和之前的公式是等价的，称为“完美不可取分”。
等价的推导可以这么想（可略过）：猜对的概率根据信息论安全的结论都是 1/（k 空间的大小），也就相等了。反推回去也容易，对于所有可能的 m 概率都相等了，总的概率又是 1，所以每种情况的概率刚好就是 1/(m 空间的大小) ，这个结论对于和 c 一点关系都没有，所以 c 的分布与 m 独立。
我们也可以换一种思考方式去思考这个式子：如果我们拿到了 c，去猜测 m 是什么，不管用什么方法去猜，先猜这个或者通过某种计算得到某种猜测的顺序，能够猜正确的概率永远和乱猜是一样的。
敌手最好的方法就是乱猜
这就是不可区分所传达的核心信息。这里谈到了“敌手”，我们有没有办法去规范化、数学化这句话呢？这就到了 Game-base Proof 大显身手的时候了：
我们需要构造基于一个敌手 A（Attacker）的 Game，形式化定义 A 的能力：不能区分密文来自于那个明文的加密，
我们让 A 主动选择两个信息 m0 m1 交给我们，然后我们 roll 一个 r[0,1] 作为 b，再 roll 一个密钥 k 加密对应下标的 m 发送回去（0 就发 m0,1 就发 m1），敌手要猜我们加密的是哪个信息，发送回来另一个 b‘ （挑战），如果猜对了就算 A 赢了。
如果敌手在游戏中获胜的概率严格等于二分之一，则称这个加密方案具有敌手不可取分性。这可以等价于上文的完美不可取分，证明不难读者自证 (` ゥ´ )
Game 中“我们”的角色在密码学领域有一个专有名词，叫做“预言机”（Oracle）。之所以叫这个名字是因为在证明当中它的能力一般都是天花板，没啥限制 ( ﾟ∀。)7” 上文的 Game 规范的流程给我们在现实中的攻击和防守方找到了一个非常有用的数学证明框架，给我们下文更加现实的加密方案铺平了道路。
至此，完善保密加密的部分算是结束了。但是在进入对称加密的世界之前，我们还需要掌握一些必要的知识……
new new