替换密码算法

A. 替代密码的替代密码的分类

根据密码算法加解密时使用替换表多少的不同，替代密码又可分为单表替代密码和多表替代密码。
单表替代密码的密码算法加解密时使用一个固定的替换表。单表替代密码又可分为一般单表替代密码、移位密码、仿射密码、密钥短语密码。
多表替代密码的密码算法加解密时使用多个替换表。 多表替代密码有弗吉尼亚密码、希尔(Hill)密码、一次一密钥密码、Playfair密码。 单表替代密码对明文中的所有字母都使用一个固定的映射（明文字母表到密文字母表）。设A={a0, a1,…, an-1}为包含了n个字母的明文字母表；
B={b0, b1,…, bn-1} 为包含n个字母的密文字母表，单表替代密码使用了A到B的映射关系：f：A→B， f ( ai )= bj
一般情况下，f 是一一映射，以保证加密的可逆性。加密变换过程就是将明文中的每一个字母替换为密文字母表的一个字母。而单表替代密码的密钥就是映射f或密文字母表。经常密文字母表与明文字母表的字符集是相同的，这时的密钥就是映射f。下面给出几种典型的单表替代密码。
⒈一般单表替代密码
一般单表替代密码的原理是以26个英文字母集合上的一个置换π为密钥，对明文消息中的每个字母依次进行变换。可描述为：明文空间M和密文空间C都是26个英文字母的集合，密钥空间K={π：Z26→Z26|π是置换}，是所有可能置换的集合。
对任意π∈K，定义:
加密变换：eπ(m)=π(m)=c
解密变换：dπ(c) = π-1(c)=m， π-1是π的逆置换。
例：设置换π的对应关系如下：
a b c d e f g h i j k l m n o p q r s t u v w x y z
q w e r t y u i o p a s d f g h j k l z x c v b n m
试用单表替代密码以π为密钥对明文消息message加密，然后写出逆置换 ，并对密文解密。
解：以π为密钥用单表替代密码对明文消息message加密，所得
密文消息为： π(m) π(e) π(s) π(s) π(a) π(g) π(e)=dtllqut
一般单表替代密码算法特点：
▲密钥空间K很大，|K|=26!=4×10^26 ，破译者穷举搜索计算不可行，1微秒试一个密钥，遍历全部密钥需要1013 年。
▲移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间。
密钥π不便记忆。
▲针对一般替换密码密钥π不便记忆的问题，又衍生出了各种形式单表替代密码。
⒉移位密码
明文空间M、密文空间C都是和密钥空间K满足，即把26个英文字母与整数0，1，2，…，25一一对应。
加密变换，E={E:Z26→Z26, Ek (m) = m + k (mod26)| m∈M, k∈K }
解密变换，D={D:Z26→Z26, Dk (c) = c－k (mod26)| c∈C, k∈K }
解密后再把Z26中的元素转换英文字母。
显然，移位密码是前面一般单表替代密码的一个特例。当移位密码的 密钥k=3时，就是历史上着名的凯撒密码（Caesar）。根据其加密函数特 点，移位密码也称为加法密码。
⒊仿射密码
仿射密码也是一般单表替代密码的一个特例，是一种线性变换。仿射密码的明文空间和密文空间与移位密码相同，但密钥空间为 K={(k1，k2)| k1，k2∈Z26，gcd(k1，26)=1}
对任意m∈M，c∈C，k = (k1，k2)∈K，定义加密变换为 c = Ek (m) = k1 m +k2 (mod 26)
相应解密变换为： m = Dk (c) = k1 (c－k2) (mod 26)
其中，K1 k1=1mod26 。很明显，k1=1时即为移位密码，而k2=1则称为乘法密码。
⒋密钥短语密码
选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，就可构造出一个字母替代表。当选择上面的密钥进行加密时，若明文为“china”，则密文为“yfgmk”。显然，不同的密钥可以得到不同的替换表，对于明文为英文单词或短语的情况时，密钥短语密码最多可能有26!=4×1026个不同的替换表。 单表替代密码表现出明文中单字母出现的频率分布与密文中相同， 多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现 的频率分布，每个映射是简单替代密码中的一对一映射多表替代密码将 明文字母划分为长度相同的消息单元，称为明文分组，对明文成组地进 行替代，同一个字母有不同的密文，改变了单表替代密码中密文的唯一 性，使密码分析更加困难。
多表替代密码的特点是使用了两个或两个以上的替代表。着名的维吉尼亚密码和Hill密码等均是多表替代密码。
⒈维吉尼亚密码
维吉尼亚密码是最古老而且最着名的多表替代密码体制之一，与位移密码体制相似，但维吉尼亚密码的密钥是动态周期变化的。
该密码体制有一个参数n。在加解密时，同样把英文字母映射为0－25的数字再进行运算，并按n个字母一组进行变换。明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合，因此可表示
加密变换定义如下：
设密钥 k=(k1,k2,…,kn), 明文m=(m1,m2,…,mn), 加密变换为：
Ek(m)=(c1,c2,…,cn),
其中ci(mi + ki)(mod26)，i =1,2,…,n
对密文 c=(c1,c2,…,cn), 解密变换为：
Dk(c)=(m1,m2,…,mn), 其中 mi=(ci －ki)(mod26)，i =1,2,…,n
⒉希尔（Hill）密码
Hill密码算法的基本思想是将n个明文字母通过线性变换，将它们转换为n个密文字母。解密只需做一次逆变换即可。
⒊一次一密密码（One Time Pad）
若替代码的密钥是一个随机且不重复的字符序列，这种密码则称为一次一密密码，因为它的密钥只使用一次。该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为电报通信设计的一种密码，所以又称为Vernam密码。Vernam密码在对明文加密，前首先将明文编码为（0，1）序列，然后再进行加密变换。
设m=(m1 m2 m3 … mi …)为明文,k=(k1 k2 k3 … ki …)为密钥,其中mi,ki ∈(0,1), i≥1, 则加密变换为： c=(c1 c2 c3 … ci …) ,其中ci = mi Å ki , i≥1,
这里为模2加法（或异或运算）
解密变换为：
m=(m1 m2 m3 … mi …) ,其中mi = ci Å ki , i≥1,
在应用Vernam密码时，如果对不同的明文使用不同的随机密钥，这时Vernam密码为一次一密密码。由于每一密钥序列都是等概率随机产生的，敌手没有任何信息用来对密文进行密码分析。香农（Claude Shannon）从信息论的角度证明了这种密码体制在理论上是不可破译的。但如果重复使用同一个密钥加密不同的明文，则这时的Vernam密码就较为容易破译。
若敌手获得了一个密文c=(c1 c2 c3 … ci …) 和对应明文m=(m1 m2 m3 … mi …) 时，就很容易得出密钥 k=(k1 k2 k3 … ki …) ，其中ki = ciÅ mi，i≥1。 故若重复使用密钥，该密码体制就很不安全。
实际上Vernam密码属于序列密码，加密解密方法都使用模2加，这使软
硬件实现都非常简单。但是，这种密码体制虽然理论上是不可破译的，然而
在实际应用中，真正的一次一密系统却受到很大的限制，其主要原因在于该
密码体制要求：
① 密钥是真正的随机序列；
② 密钥长度大于等于明文长度；
③ 每个密钥只用一次（一次一密）。
这样，分发和存储这样的随机密钥序列，并确保密钥的安全都是很因难
的；另外，如何生成真正的随机序列也是一个现实问题。因此，人们转而寻
求实际上不对攻破的密码系统。
⒋Playfair密码
Playfair密码是一种着名的双字母单表替代密码，实际上Playfair密码属于一种多字母替代密码，它将明文中的双字母作为一个单元对待，并将这些单元转换为密文字母组合。替代时基于一个5×5的字母矩阵。字母矩阵构造方法同密钥短语密码类似，即选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中剩下的字母依次从左到右、从上往下填入矩阵中，字母I，j占同一个位置。

B. 希尔密码原理

希尔密码（Hill Cipher）是运用基本矩阵论原理的替换密码，由Lester S. Hill在1929年发明。每个字母当作26进制数字：A=0, B=1, C=2... 一串字母当成n维向量，跟一个n×n的矩阵相乘，再将得出的结果MOD26。

中文名
希尔密码
外文名
Hill Cipher
原理
基本矩阵论
类别
替换密码
提出者
Lester S. Hill
快速
导航
产生原因

原理

安全性分析

例子
简介
希尔密码是运用基本矩阵论原理的替换密码，由Lester S. Hill在1929年发明。
每个字母当作26进制数字：A=0, B=1, C=2... 一串字母当成n维向量，跟一个n×n的矩阵相乘，再将得出的结果模26。
注意用作加密的矩阵（即密匙）在必须是可逆的，否则就不可能解码。只有矩阵的行列式和26互质，才是可逆的。
产生原因
随着科技的日新月异和人们对信用卡、计算机的依赖性的加强，密码学显得愈来愈重要。密码学是一门关于加密和解密、密文和明文的学科。若将原本的符号代换成另一种符号，即可称之为广义的密码。狭义的密码主要是为了保密，是一种防止窃文者得知内容而设的另一种符号文字，也是一般人所熟知的密码。
使用信用卡、网络账号及密码、电子信箱、电子签名等都需要密码。为了方便记忆，许多人用生日、电话号码、门牌号码记做密码，但是这样安全性较差。
为了使密码更加复杂，更难解密，产生了许多不同形式的密码。密码的函数特性是明文对密码为一对一或一对多的关系，即明文是密码的函数。传统密码中有一种叫移位法，移位法基本型态是加法加密系统C=P+s(mod m)。一般来说，我们以1表示A，2表示B，……，25表示Y，26表示Z，以此类推。由于s=0时相当于未加密，而0≤s≤m-1（s≥m都可用0≤s≤m-1取代），因此，整个系统只有m-1种变化。换言之，只要试过m-1次，机密的信息就会泄漏出去。
由此看来，日常生活中的密码和传统的密码的可靠性较差，我们有必要寻求一种容易将字母的自然频度隐蔽或均匀化，从而有利于统计分析的安全可靠的加密方法。希尔密码能基本满足这一要求。
原理
希尔加密算法的基本思想是，将d个明文字母通过线性变换将它们转换为d个密文字母。解密只要作一次逆变换就可以了，密钥就是变换矩阵本身。[1]
希尔密码是多字母代换密码的一种。多字母代换密码可以利用矩阵变换方便地描述，有时又称为矩阵变换密码。令明文字母表为Z，若采用L个字母为单位进行代换，则多码代换是映射f：Z→Z。若映射是线性的，则f是线性变换，可以用Z上的L×L矩阵K表示。若是满秩的，则变换为一一映射，且存在有逆变换K。将L个字母的数字表示为Z上的L维矢量m，相应的密文矢量c，且mK=c，以K作为解密矩阵，可由c恢复出相应的明文c·K=m。
在军事通讯中，常将字符（信息）与数字对应（为方便起见，我们将字符和数字按原有的顺序对应，事实上这种对应规则是极易被破解的）：
abcde…x y z
12345…242526
如信息“NOSLEEPPING”对应着一组编码14,15,19,12,5,5,16,16,9,14,7。但如果按这种方式直接传输出去，则很容易被敌方破译。于是必须采取加密措施，即用一个约定的加密矩阵K乘以原信号B，传输信号为C=KB（加密），收到信号的一方再将信号还原（破译）为B=KC。

C. 凯撒密码为一种替换密码，此题的加密过程为先进行base64编码，再进行移

在密码学中，恺撒密码（或称恺撒加密、恺撒变换、变换加密）是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。
恺撒密码的加密、解密方法还能够通过同余的数学方法进行计算。首先将字母用数字代替，A=0，B=1，...，Z=25。此时偏移量为n的加密方法即为： E(x) = (x + n) mod 26.
解密就是：
D(x) = (x - n) mod 26.
显而易见，一旦确定了某两个字母的对应关系（即n的值），这种移位密码很容易被破解。
因此，为了使密码有更高的安全性，单字母替换密码就出现了。
明码表:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
密码表:T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
但是这种加密方式依然可以破解，根据字母使用频度表，分析密文中的字母频率，将其对照即可破解。
不仅如此，凯撒加密对加密数据也是有要求的，一般情况下，它只支持对基本的英文字母进行加密，如果对中文等亚太地区的文字进行加密，结果可想而知，你的隐私将毫无保留的出现在众人面前。有人说，我们可以扩展这个算法，使它支持所有的文字，这么做是可行的，如果采用同余式的方式实现，代码几乎不怎么需要改动，只要字符集本身是Unicode就可以了。但是这种加密的安全性很难满足应用的要求。如果采用单字母替换的方式，程序将需要构建两个巨大的字符数组去保存他们的映射关系，而且扩展性也不好，当然也是不可行的。这样看来，凯撒加密岂不是一无是处了，其实对于一般的应用，凯撒加密还是足以应付的，只要我们对它稍作改进。

D. 为什么说加法密码、乘法密码、仿射密码、置换密码、Hill密码以及Vigenere密码

加法密码就是真典密码学中的恺撒密码格式是：密文=(明文+密钥)mod26,剩法密码是恺撒密码发展出来，格式是：密文=明文x实钥mon26；置换密码就是在简单的纵行换位密码中，明文以固定的宽度水平的写在一张图表纸上，密文按垂直方向读出，解密就是密文按相同的宽度垂直的写在图表纸上，然后水平的读出明文。希尔密码（Hill Cipher）是运用基本矩阵论原理的替换密码，由Lester S. Hill在1929年发明。每个字母当作26进制数字：A=0, B=1, C=2... 一串字母当成n维向量，跟一个n×n的矩阵相乘，再将得出的结果MOD26；Vigenere是恺撒密码演变而来。使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。
有兴趣可以了解一下古典密码学，这里面都有。

E. 替换式密码的谐音替换法

早期的加密中，为增加替换式密码应付频率分析攻击的强度，有时会采用“谐音”来改变明文字母频率。在这种加密算法中，明文字母可以映射到多个密文符号。通常情况下，频率最高的明文符号（如E）会比低使用频率的字母（如X）有更多的谐音符号，使频率分布更为平坦，让分析更困难。
但亦因此，只是字母之间互相替换就会造成不够分配，从而有了好几种不同的解决方法。其中最简单的方式可以算是用1-0共10个数字作为某些字母的替换。另一种方法则是将现有的字母分开成原字母配以简单的变化、大写、小写、上下倒转的字母、镜像文字（左右倒转）等。虽然更为艺术化，却不代表一定更安全，其中一些谐音替换法全部使用新发明的奇特符号来代表字母。
一种有趣的变化名为命名密码法（英语：nomenclator）。此加密法有许多不同的版本，之间的区别来自其前缀。而该前缀来自宣读来访贵宾称号的公职人员名字。这种密码结合一个小型密码本（英语：Codebook）组成一个大型的谐音替换表。在此密码中，常用单词会按密码本加密，余下字母则按另一本密码本加密，两者符号最后在密文中混起来，以减低简易替换密码中被破解的风险。路易十四所使用的密码是罗西诺尔家族（英语：Rossignols）创立的伟大密码，该密码直至法国王室废止后百年才被破解。
15世纪早期至18世纪后期，命名密码是外交文件及间谍最常使用的加密，然而其中大多数仍然使用加密性能较差的命名密码。虽然由十六世纪中叶开始政府情报机构的密码分析员就破解部分命名密码法，但使用者通常的反应仅仅是加大谐音替换表。十八世纪后期，谐音替换系统开始消亡之时，一些命名密码已有高达5万个符号。
然而，并非所有命名密码法都已被破解。直到今天，仍然不时有新的命名密码被破解的新闻。
比尔密码是另一个谐音替换法的例子。这个故事指在1819年至1821年期间由一个加密文本来隐藏美国独立宣言中所述的宝藏。在这里，每个密文字符由一个数字替换。数字代表着独立宣言中第几个字的第一个字母。独立宣言中许多字的首字母都是一样的，而密文数字能是其中任何一个，例如正文中第二和第六个字都是“I”开头，即“I”既可以是2，又可以是6。而解读仅仅就是把密文中的数字（如代数X），放到独立宣言中查找（第X个字的首字母）。
斯塔尔则描述了另一个谐音替换密码，其密码是第一次尝试在电脑的数据库上加密。在斯塔尔的方法中，无论是明文还是密文都是以二进制字符串存储，因此谐音的数量可以非常大，使得频率分析比平常更为困难。
书本式加密（英语：Book cipher）与散列板都是谐音替换密码的一种。

F. 替换式密码的多表替换加密

在1467年，多表替换密码由莱昂·巴蒂斯塔·阿尔伯蒂以圆碟的形式首次描述。约翰尼斯·特里特米乌斯所着的《隐写术》（古希腊文：Steganographia）中介绍了一种表格（古希腊文：tableau）（见下；15世纪已完成但很久以后才出版）。1563年，乔瓦尼·巴蒂斯塔·德拉波尔塔（英语：Giovanni_Battista_della_Porta）在《书写中的隐蔽字符》（古希腊文：De FurtivisLiterarum Notis）描述了一个更复杂的混合字母版本。
在一个多表替换密码中，会使用多个字母作为密码。为了加快加密或解密速度，所有的字母通常写在一张表格上，密码学上称作tableau。这种表格通常是26×26，因为这样才能放下全部26个英文字母。填充表格及选择下次使用的字母的方法，就是不同多字母替换密码之间的定义。多字母替换密码比单字母更难打破，因为其替换可能性多，密文要较长才可。
其中最着名的一种为吉奥万·巴蒂斯塔·贝拉索于1585年推出的维吉尼亚密码。它于1863年之前一直未被破解。法国人称它作“不能破译的密码”（法语：le chiffre indéchiffrable）。（此密码曾被误以为由布莱斯·德·维吉尼亚所创，所以才叫作维吉尼亚密码。）
维吉尼亚密码中，表格的第一行只需直接填上26个字母，然后以握帆空下每一行的字母都是向左偏移一格。（这叫作表格横移，数学上每一列同余26。）要用这种密码需要使用一个关键字来作为密钥。关键字每次用完就再次重复。假设关键字是“CAT”，明文的第一个字由“C”加密，第二个字由“A”加密，第三个则由“T”加密，然后再回到C加密，一直重复。然后按照右边的密码表加密，例如BALL用CAT作关键字时会加密至DAEN，可见即使是同一个“L”亦会加密至另一个字母。现实中，维吉尼亚密码的关键字非常长。
1863年，弗里德里希·卡西斯基（英语：FriedrichKasiski）少校发明了一种方法（在克里米亚战争前已由查尔斯·巴贝奇秘密并独立地发明），使得可以计算维吉尼亚密码中关键字的长度。这种方法需要较长的密文，因为其运作依靠找出常见的字（如THE）使用相同关键字（如ABC）的数量，因此段瞎，极短的密文难以用此办法找出。
因此，即使在轿兆今天，如果在表格中使用混合表加密，或关键字是随机的，维吉尼亚密码理论上亦难以破解。但由于实际上很难用到这些方法，维吉尼亚密码的使用越来越少。
其他着名的多字母替换加密包括：
格兰示菲特密码 - 与维吉尼亚密码相似，但由于整个密码只使用10个单元，因此关键字长度有限，很容易被破解。博福特密码 - 这实际上就是维吉尼亚密码，除“tabula”改为向后偏移一格，数学上是等式为：密文=键－明文。博福特密码属于对等加密，即加密算法与解密算法相同。自动密钥密码 - 它的密钥开头是一个关键词，之后则是明文的重复，以避免周期函数。运动密钥密码，关键词从某些文章或名句中取出，因此可以非常长。
现代的流密码中可以看出，现代的多表替换加密都努力改进流密钥，使其尽可能的长及不可预知。