密码学 二 之代换密码(英文字母替换加密)
密码学 二 之代换密码(英文字母替换加密)
上一讲中，我们讲移位密码其实是将字母表中的字母一一对应到各数字，然后通过数字平移来进行加密，古典密码学中还有一种比较有名的加密方法，就是将明文中的字母表对应到一套密文的字母表，这种加密方法我们叫 代换密码（substiution cipher） 或叫 替换密码 ，下图就是一个简单的代换密码对应表
上面所说，代换密码其实就是将明文里的字母按照字母表替换成密文里的字母，还是举一个例子，假设现在有一个字符“welcome to china”，根据上面的密码替换表，将明文里面的每个字母依次换成对应的密文，如下：
这样就可以得到密文CXGHBEXQBHTJNW
代换密码的解密非常简单，只要将加密的替换表进行反向操作，这里不再操作
这里可以发现，代换密码主要是要建立起一套明文与密文之间的加密对应的替换关系，只要有这套密码替换表，加、解密就变得很容易
上一讲我们知道，移位密码其实是很好破解的，因为密钥总量一共就26位，只要我们试26次，就一定能试出一个正解的，那么代换密码是也可以通过穷举的方式来破解呢？
我们知道代换密码是把明文的26个字母随机对应密文的26个字母上，也就意味着明文中第一个字母a可以对应到密文中A,B,C,D…Z 26个字母中的任一个，以此类推，我们就可以计算出代换密码的密钥总数为：
像这种一种密码能够使用的所有密钥的集合，叫做 密钥空间（keyspace）
上面的密钥的量非常大，用穷举法来破译几乎是不可能的。
使用穷举法不能破译，但并不能说明就是安全的，我们可以使用 频率分析 来破译代换密码，频率分析就是利用明文中的字母出现频率与密文中的字母的出现频率一致这一特性，
下面是【密码学原理与实践】书中的一个例子，可以参考一下
现假设有一段密文如下，现需将其解密出明文
这种密文的频率分析如下图：
根据 英文字母出现的频率 排序统计，一般的排序是这样的e,t,a,o,I,n,s,h,r,d,l,u,c,m,f,w,y,p,v,b,g,k,j,q,x,z 而且一般英语文章中出现频率最高的的字母是e,这一点基本不会错的。
根据上图所示，字母Z出现的次数是20，远远高于其它密文字母，所以我们可以假设Z-e。其它出现至少10余次的官方字母是C,D,F,J,M,R,Y，我们希望这些字母对应的是
e t a o l n s h r中的一个子集，
我们现在假设了Z-e，现注意一下形如-Z, Z-的两字母组，我们发现出现这种类型的最一般的两字母组是DZ和ZW,各都出现了4次；NZ和ZU出现3次，RZ HZ XZ FZ ZR ZV ZC ZD ZJ各出现2次；又因ZW出现4次，而WZ一次也未出现，同时W比许多其它字母出现的次娄少，所以我们可以假设W-d，又因为DZ出现4次而ZD出现2次，故可猜测D是{r,s,t}中的任一个，具体是哪个还不清楚。
如上面猜测， Z-, D-d，再看看密文并注意到ZRW出现在密文的开始部分，RW后面也出现过，因为R在密文频繁地出现，而nd是一个常见的两字母组，所以我们可以假设R-n作为可能的情况，这样我们便有了如下的形式
接下来我们可以试试N-h，因为NZ是一个常见的两字组而ZN不是一个常见的两字母组，如果这个猜测是正确的，则明文ne-ndhe很可能说明C-a，结合这些收市，我们又进一步有:
现在考虑出现次数高的密文字母M,由前面分析，密文段RNM密钥成nh-，这说明h-是一个词的开头，所以M很可能是一个元音，因为已经使用了a和e,所以猜测M-{i或o}，因为ai是一个比ao出现次数更高的明文组，所以首先猜测M-I，这样就有：
下面需要确定明文o对应的密文，因为为是一个经常出现的字母，所以我们猜测相应的密文字母是D F J Y 中的一个，Y似乎最有可能，否则将得到长元音，即从CFM或CJM中得到aoi,因此假设Y-o。
剩下密文字母中三个最高频率的字母是D F J,我们猜测他们以某种次序解密成r s t， 三字母NMD两次出现说明很可能D-s,对应的明文三字母组为his，HNCMF可能是chair的加密，说明F-r,H-c，同时排除J-t，于是我们有了：
有了上面的提示，就很容易确定出明文，解密明文如下
【密码学原理与实践（第三版）】
【图解密码技术】
#includestdio.h
int main() {
char s[100];
int i=0;
gets(s);
for(; s[i]!='\0'; i++) {
if(s[i]='A' s[i]='Z')
printf("%c",s[i]=='Z'?'A':s[i]+1);
else printf("%c",s[i]);
}
}
举例：周期为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个英文字母进行替换。
加密方式无非是按照一定的数学变换进行加密，比如字母s和e日常出现概率高，那么换过之后的加密字母概率也很高。至于加密的公式，有软件可以专门破解。比如Hill加密，利用逆矩阵取模进行变换。相对来说这些都是比较简单的加密方式，破解多是暴力破解.
如果是凯撒密码，字母置换是整体位移的，那么可以看单个成词的，猜它是I；看3字词，猜它是the。如果是变种凯撒密码，字母置换不是位移而是用码表的，要复杂一点。思路还是词频，比如通过上面两个，可以先猜出3~4个字母，然后代入，代入以后继续根据更长的单词的词频来猜，循环往复，这样全部猜完了看读不读的通。中间可以结合字频，比如英文辅音字母当中C出现的比例高等等。
键盘出现了按键失灵情况：
1、软件原因；
2、键盘串键、短路；
3、硬件故障等原因。
解决方案：
1、开机出现图标时按F2键进入BIOS设置；
2、U盘启动进入PE模式；
3、快速按F8键进入安全模式；
4、用毛刷、镊子、气吹等工具进行简单的清除；
5、键盘曾有浸液史，失灵按键按下后正常弹起；
6、重新安装操作系统。
应该是导电膜损伤了。或者氧化了。
因为文字这么多，就可以从词频入手了。
第一步：
英文字母出现频率
先从baidu上搜索出英文字母词频分布情况：
高频字母：E、 T、A、O、N、I、R、S、H
中频字母：D、L、U、C、M
低频字母：P、F、Y、W、G、B、Y（v？）
稀频字母：J、K、Q、X、Z
第二步：
确定字母e
再统计一个原文中各个字母出现的频率。具体情况我就不列出来了。全部字母1405字，字母X出现了167次，比排名第二的T的133次要高出很多
，几乎可以肯定X＝e。（为了方便替换，在word里将全部大写字母换成小写）。然后，因为Z和S都只出现了一次，于是大胆猜测它们就是x和e
。而且在e破译出来后，有eZ***的词出现，一般英文中ex***的词不少，于是暂定Z～x，S～z。因为x和z出现次数也不多，暂时这么估计也不会
太影响总体。
第三步
从短单词入手
在e取代了X后，观察到全文中有很多‘JPe’这样的词出现，很容易就会想到它们就是‘the’。于是J＝t，P＝h。
再观察只有一个字母的单词，文中出现过3次‘M’和1次‘B’用一个字母作词的情况，这与英文中的‘a’和‘I’作为单词几乎是对应的。鉴
于‘I’在单独作单词时通常在句首，观察M和B的位置，可以得到M=a,B=i。
还有文中的'R情况，根据英文的所有格用法，容易想到R＝s。
第四步
利用已有条件，解决特征单词
因为一眼瞥见了替换后的‘saE’，于是查一下金山词霸，从sad/sap/sat/saw/say中，排除已用字母t的sat，根据词的位置基本可以排除掉形
容词sad，再根据文中还多次出现‘thE’这个词，用w、p或d套用都不能成词，而‘thy’是古英文中‘你’的意思，还可以接受E＝y。
又，在替换后‘iT’多次出现，估计T～f或T～n。根据词频规律以及T在本文中出现的高达133次来看，T不会是低频字母f，所以T＝n。
很多地方的‘anN’使人很容易将N＝d推断出来。
第五步
解决剩下的高词频字母
在出现100次以上的字母中，只剩下C还没有对应，而词频排名第四的o也还没有对应，可以猜想C～o，文中‘CI’这样的词出现多次，估计为‘
of’，而f对应的词频和I出现的次数也相当。因此确定C＝o，I＝f。
高词频还有剩下有r，而文中很多词的后缀是‘-eV’，所以判断V＝r。多个地方验证也还可行。
第六步
逐渐解决剩下的字母
根据后缀‘－inW’来找出W＝g，根据两个‘Yrote’来得到Y＝w，根据‘Hnown’和‘Hing's’来得到H＝k。
剩下的就简单了：G＝l，Q＝p，U＝u，K＝q，A＝c，L＝m，F＝b，D＝v。
最后剩下个O～j。
第七步
验证
发现有的单词出错，出现一次的‘zoints’和‘belshajjar’都不是单词，试着将‘z’和‘j’换一下，就正确了，而且后者是圣经里的名词
，还有古英文的thy和thee。应该没问题了。所以最后O=z，S＝j，再确定前边的Z＝x。就完了。
