代换密码与置换密码(替换密码和置换密码)
代换密码与置换密码(替换密码和置换密码)
代换密码（substitution cipher)：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。
置换密码(permutation cipher)，又称换位密码（transposition cipher)：明文的字母保持相同，但顺序被打乱了。
在侦探与反侦探的过程中，人们为了守住秘密或保持神秘感，都会采用加密的方式进行。随着人们解密技术的进步，加密方式也变得越来越复杂和离奇，在历史上就曾出现过许多神奇的密码，他们的离奇让专家们至今还束手无策。
网络配图
十二宫杀手密码
1969 年 7 月 31 日，三家报社各自收到了一封密文的三分之一，密文的作者就是大名鼎鼎的十二宫杀手。十二宫杀手要求这三家报社把密文发表在报纸上，否则他将在当周周末再次杀人。三家报社只好照做。这个密文共有 408 个符号，以后大家都习惯称它为 408 密文(408-cipher)。408 密文是十二宫杀手的第一封密信。一个星期后，一位教师和他的妻子破解了这篇密文。大卫·芬奇的电影《十二宫杀手》完整地记述了这一事件。
408 密文用的是最简单的字母替换法，所不同的是一个字母可能对应多个符号。这种加密方法可以很好地防止字频破解法，因为你可以让常用的字母对应更多的符号，保证每个符号出现的次数大致相等。不过，破解这样的密码也不是完全没有突破口，“字母 Q 后面一定是 U”等英文特点能提供不少线索。这种一对多的替换加密方法就叫做同音替换法(Homophonic Substitution Cipher)。
同年 11 月 8 日，十二宫杀手又寄出了一篇密文。这篇密文有 340 个字符，被称作 340 密文。与 408 密文不同的是，虽然大家都相信 340 密文同样使用的是同音替换加密，但直到现在 340 密文也没有解开。
CIA 的雕塑密码
1990 年，美国艺术家吉姆·桑伯恩(Jim Sanborn)花费 25 万美元，创作了一个刻满密码的雕塑作品——Kryptos。这个雕塑作品现在坐落于弗吉尼亚 CIA 的广场内。
网络配图
丹·布朗的悬疑小说《失落的符号》里提到了这个雕塑密码，无疑让这个密码再度名声大噪。整个密码分为四个部分。前三个部分已被破译，其中第一、二部分是多表替换密码(polyalphabetic substitution)，第三部分是置换密码(transposition cipher)。尽管 2010 年 11 月桑伯恩本人给出了一点提示，但目前第四部分仍然没有被解决。
D'Agapeyeff 密码
1939 年，地图学专家 Alexander D'Agapeyeff 出版了一本名为 Codes and Ciphers 的密码学普及读物。在文章末尾的“难题挑战”部分，D'Agapeyeff 自己编写了一段很难的密码，目前还没有人破解出来。不过，后来 D'Agapeyeff 本人居然把加密过程给忘了，于是这段密码就变成了一个永久的谜。
比尔密码
梦想自己能得到一张藏宝地图，上演一段破译密码探寻宝藏的传奇故事?你的机会来了。据说，在 1820 年，一个叫做托马斯·杰斐逊·比尔(Thomas Jefferson Beale)的人在弗吉尼亚贝德福县的某个地方埋藏了大量的宝藏，随后把装有三封密信的盒子交给了一个名叫罗伯特·莫里斯(Robert Morriss)的旅店老板代为保管，之后就永久地消失了。莫里斯死前把盒子里的三份密文交给了他的朋友。这位朋友把这段故事连同密码全文一道印成了小册子，宝藏之谜就这样流传了下来。
网络配图
1885 年出现的一本小册子。上述所有故事都出自这本小册子里，其真实性不得而知。利用《独立宣言》作为密钥，可以破解出第二份密码。第二份密码中详细记录了所藏宝藏的数量，现在看来至少值 6500 万美金。这份密文中还说到，宝藏的埋藏地点详细地记在了第一份密码内，而第三份密码里则记录着宝藏的原主人。虽然各方神圣都把五花八门的手段试了个遍，但到目前为止，剩下的两份密码都还没被破解。不过，也有一些人对整个故事进行了理性的分析，认为比尔密码不过是一场骗局。
Dorabella 密码
1897 年，英国作曲家爱德华·艾尔加(Edward Elgar)给挚友多拉小姐(Miss Dora Penny)留下了一封信。这封信上写着 87 个歪歪扭扭的符号，里面明显藏着艾尔加想对多拉小姐说的话。多拉本人一直没能读懂这封信。1937 年，多拉出版了自己的回忆录，将这份密码公之于众。这个密码直到现在仍未被破解。
这些神奇的密码，到底采用了什么样的加密方式?符号学家们、解密专家们至今还无法确定，它们已经成为了一个谜。
举例：周期为e的换位将明文字母划分。
换位密码就是一种早期的加密方法，与明文的字母保持相同，区别是顺序被打乱了。
古典密码：
从远古到1949年香农发表《保密系统的通信理论》，这期间人类所使用的密码均称为古典密码，本文主要介绍三种古典密码，分别为置换密码，代换密码和轮换密码。
置换密码（又称为换位密码）：
是指明文中各字符的位置次序重新排列得到密文的一种密码体制。
特点:保持明=文中所有的字符不变，只是利用置换打乱明文字符的位置和次序。
置换定义：有限集X上的运算σ：X→X，σ是一个双射函数，那么称σ为一个置换。
即任意x∈X,存在唯一的x’∈X，使得σ(x)=x’。
解密的时候会用到逆置换σ’,即任意x’∈X,存在唯一的x∈X，使得σ’(x’)=x且满足σσ’=I。
对置换有了一个基本的认识之后我们来谈一下置换密码，置换密码有两种，一种为列置换密码，一种为周期置换密码。
列置换密码：
列置换密码，顾名思义，按列换位并且按列读出明文序列得到密文，具体加密步骤如下：
将明文p以固定分组长度m按行写出nxm阶矩阵（若不m倍数，空余部分空格补充）。
按（1,2,3…m）的置换σ交换列的位置,σ为密钥。
把新得到的矩阵按列的顺序依次读出得到密文c。
解密过程如下：
将密文c以固定的长度n按列写成nxm阶矩阵。
按逆矩阵σ’交换列的位置。
把矩阵按着行依次读出为明文。
周期置换：
周期变换密码是将明文P按固定长度m分组，然后对每组的字符串按置换σ重新排列位置从而得到密文。
周期排列与列排列思想是一致的，只不过列排列是以矩阵的形式整列换位置，而周期是在分组以后对每组分别变换。懂得列排列就可以很容易地理解周期排列。
代换密码（又称为替代密码）：
就是讲明文中的每个字符替代成密文中的另一个字符，替代后的各个字母保持原来的位置，在对密文进行逆替换就可以恢复出明文。
代换密码有分为单表代换密码和多表代换密码。
单表代换密码我们分别介绍凯撒密码和仿射密码。
凯撒密码：
凯撒密码依据凯撒密码代换表对26个英文字母进行替换。
1.古典密码编码方法归根结底主要有两种，即替换密码和置换密码。
（1）一种是将明文字符替换成一些其他的字符，形成密文，称“替换密码”。其本质：不变的是字符的位置，变化的是字符。
（2）一种是将原有的明文字符的顺序打乱，形成密文，称“（位）置（变）换密码”。其本质：不变的是字符本身，变化的是位置。
2.替换密码：
（1）凯撒密码
基本思路：将明文中的字符移动一定的位数（k）来实现加密和解密，也就是明文中的所有字符都在字符表上进行k偏移，形成密文。
（2） 乘法密码：
基本思路：使用采样的方式进行加密，将明文字符串的每个字符，每隔k位算出字符并排列起来形成密文。
（3）仿射密码：
基本思路：明文中所有字符按照（ax + b）mod 26进行计算，得到密文。
（4）维吉尼亚密码：
基本思路：使用字符串作为密钥，并把密钥与明文进行对应，依次重复密钥，直至与明文的长度相同。
3.置换密码：
（1）栅栏密码
基本思路：先将明文中的字符分成N个一组，再将每组的第1个字符组合，每组的第2个字符组合，依次类推，直到第N个字符组合，最后再将所有字符全部连接起来，形成密文。这里N称为栏。
置换密码、替代密码不是公开密码。从远古到1949年香农发表《保密系统的通信理论》，这期间人类所使用的密码均称为古典密码，并不是公开密码。
1、置换密码又叫换位密码，它根据一定的规则重新排列明文，以便打破明文的结构特性。置换密码的特点是保持明文的所有字符不变，只是利用置换打乱了明文字符的位置和次序。
2、替代密码又称为代换密码，就是讲明文中的每个字符替代成密文中的另一个字符，替代后的各个字母保持原来的位置，在对密文进行逆替换就可以恢复出明文。代换密码有分为单表代换密码和多表代换密码，单表代换密码我们分别介绍凯撒密码和仿射密码。
