设想这样一个场景:

你现在坐在教室的一角, 而长达两个小时的课堂才刚刚开始. 你攒了一肚子怪话迫不及待地想要和教室对角的哥们分享, 于是你决定写纸条. 不幸的是, 纸条的传送路线并不安全——这条路线上有准备偷窥你的纸条的同学, 还有在教室里游走, 随时准备没收纸条的老师.

事情看起来很棘手, 对吗?

不幸的是, 这是自文字出现以来所有尝试秘密传递信息的人所共同面对的困境. 为了保证信息被安全且保密地传输, 人们开始使用密码¹. 研究如何将可读的信息(称为"明文")通过某种手段变为不可读的信息(称为"密文"²)的学科就是密码学.³.

本文中加密算法通常用$E(x)$表示, 解密算法用$D(x)$表示

0x01 古典密码

.1 Scytale密码

古典密码的历史可上溯到约公元前500年, 由斯巴达人所编制的Scytale密码⁴. 斯巴达人把长条纸螺旋形地斜绕在一个多棱棒上, 将文字沿棒的水平方向从左到右书写,写一个字旋转一下, 写完一行再另起一行从左到右写, 直到写完. 取下纸带后, 纸条上的文字消息杂乱无章、无法理解, 这就是密文, 但将它绕在另一个同等尺寸的棒子上后, 就能看到原始的消息. 这是可考的最早的密码技术.

.2 凯撒密码

凯撒密码是一种最简单且广为人知的线性映射密码, 传说是由古罗马将领尤利乌斯·凯撒所发明. 其原理是将明文中的所有字母都在字母表上向后或向前按照一个固定数目(也就是通常所说的密钥, 叫做偏移量, 记作$n$)进行移动. 例如, 当$n=2$时, 所有A将被替换成B, Y将被换成Z.
不难看出, 其加解密的公式为(记密文为$x$):

$E_n(x) = (x+n) mod 26$

$D_n(x) = (x-n) mod 26$

其缺陷在于可使用的偏移量并不足够大或足够小, 即$n_{max}=25, n_{min}=-25$, 因而可以通过穷举法轻易破解. 即使不使用穷举法, 也可以通过频率分析或特征单词分析等方法进行破解.

实例

明文: SHINE
偏移量$n$: 2
密文: TIJOF

.3 维吉尼亚密码

维吉尼亚密码是使用一系列凯撒密码组成密码字母表的线性映射加密算法. 其使用若干个字母作为密钥, 词组中每一个字母都作为移位替换密码密钥确定一个替换表, 维吉尼亚密码循环的使用每一个替换表完成明文字母到密文字母的变换, 最后所得到的密文字母序列即为加密得到的密文.

实例

记明文为$K$, 其长度为$len(K)$, 密钥为$key$.
设明文为PERASPERA, 密钥为ADASTRA.
首先循环密钥直到其长度与明文相同⁵:

$len(K) = len(key_1+key_2+key_3+...)$

即ADASTRAAD, 然后用字母在字母表中对应的位置替换字母, A在字母表中是第1位, D在字母表中是第4位...以此类推, 然后根据每位密钥的位置, 将其作为偏移量对对应位置的明文进行凯撒加密.
得到的结果是: PHRSLGERD
一般, 特征单词分析等方法对维吉尼亚密码仍然有效. 此外, 还有一些无密钥破解的方法, 如:http://atomcated.github.io/Vigenere/

.4 栅栏密码

栅栏密码是一种移位密码. 其加密原理是将明文分为每$k$个字符一组, 然后将每组字符依序连接, 得到密文.

实例

ADASTRAPERASPREA, $k=3$
分组后的结果是: ADA|STR|APE|RAS|PRE|A
取每组第一个字母得到ASARPA, 取第二个得到DTPAR, 取第三个得到ARESE, 从而得到密文ASARPADTPARARESE.

.5 列序法

列序法, 顾名思义, 就是将原本按行排列的明文转为按序排列.

实例

明文: spectrophoto, 列数为4
+---+---+---+---+
| s | p | e | c |
+---+---+---+---+
| t | r | o | p |
+---+---+---+---+
| h | o | t | o |
+---+---+---+---+
按列得出的密文是sthproeotcpo.

.6 Enigma密码机

Enigma是一种使用多表代换的密码学, 二战期间在德国开发. 它通过不断改变明文和密文的字母映射关系, 对明文字母们进行着连续不断的换表加密操作.

.7 小结

不难看出, 这一时期的密码学更像是一门艺术, 其核心手段是代换和置换. 代换是指明文中的每一个字符被替换成密文中的另一个字符, 接收者对密文做反向替换便可恢复出明文; 置换是密文和明文字母保持相同, 但顺序被打乱.⁶

0x02 近代密码学

密码形成一门新的学科是在20世纪70年代，这是受计算机科学蓬勃发展刺激和推动的结果。快速电子计算机和现代数学方法一方面为加密技术提供了新的概念和工具，另一方面也给破译者提供了有力武器。计算机和电子学时代的到来给密码设计者带来了前所未有的自由，他们可以轻易地摆脱原先用铅笔和纸进行手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。

Arthur Scherbius于1919年设计出了历史上最著名的密码机—德国的Enigma机,，在二次世界大战期间， Enigma曾作为德国陆、海、空三军最高级密码机。Enigma机使用了3个正规轮和1个反射轮。这使得英军从1942年2月到12月都没能解读出德国潜艇发出的信号。转轮密码机的使用大大提高了密码加密速度，但由于密钥量有限，到二战中后期时，引出了一场关于加密与破译的对抗。首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的Enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父——图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分密码本，获得密钥，以及进行选择明文攻击等等手段，破解出相当多非常重要的德军情报。

这一阶段真正开始源于香农在20世纪40年代末发表的一系列论文，特别是1949年的《保密系统通信理论》，把已有数千年历史的密码学推向了基于信息论的科学轨道。近代密码发展中一个重要突破是“数据加密标准”（DES）的出现。DES密码的意义在于，首先，其出现使密码学得以从政府走向民间，其设计主要由IBM公司完成，国家安全局等政府部门只是参与其中，最终经美国国家标准局公开征集遴选后，确定为联邦信息处理标准。其次，DES密码设计中的很多思想（Feistel结构、S盒等），被后来大多数分组密码所采用。再次，DES出现之后，不仅在美国联邦部门中使用，而且风行世界，并在金融等商业领域广泛使用。

0x03 现代密码学

1976 年，美国密码学家提出“公钥密码”概念。此类密码中加密和解密使用不同的密钥，其中，用于加密的叫做公钥，用于解密的为私钥。1977年，美国麻省理工学院提出第一个公钥加密算法RSA算法，之后ElGamal、椭圆曲线、双线性对等公钥密码相继被提出，密码学真正进入了一个新的发展时期。一般来说，公钥密码的安全性由相应数学问题在计算机上的难解性来保证，以广为使用的RSA算法为例，它的安全性是建立在大整数素因子分解在计算机上的困难性，如，对于整数22，我们易于发现它可以分解为2和11两个素数相乘，但对于一个500位的整数，即使采用相应算法，也要很长时间才能完成分解。

好了, 现在我们已经介绍完传纸条时比较实用的技巧和密码学的发展历史了, 现在该来点我喜欢的东西了--

.1 同余!

同余定理是数论中的重要概念:

给定一个正整数m，如果两个整数$a$和$b$满足$(a-b)$能够被$m$整除，即$\frac{(a-b)}{m}$得到一个整数，那么就称整数$a$与$b$对模$m$同余，记作$a\equiv b (mod m)$

Exegesis

1: 用于登录、认证的"密码"实际上叫做口令(token或password). 对于密码, 一个简明易懂的定义是"按照'你知, 我知, 他不知'原则编制出用于传输的信息".
2: 通常而言, 密文可通过某种手段转化为明文, 但也不尽然. 例如, SHA256等哈希算法就是不可逆的加密算法.
3: 显而易见的是, 密码的首要目的是隐藏信息的涵义而不是隐藏信息的存在.
4: 又称"塞塔密码""滚筒密码".
5: 如果不能理解的话, 这一步实际上是在这样进行:
想象将密文无限重复. 即: ADASTRA|ADASTRA|ADASTRA|ADASTRA... , 然后从头开始截取长度与明文长度相等的字符串, 得到ADASTRAAD.
6: 其实把这些密码放上来纯粹是为了好玩...