2015年认证杯SPSSPRO杯数学建模
B题 替换式密码
原题再现：
历史上有许多密码的编制方法。较为简单的是替换式密码，也就是将文中出现的字符一对一地替换成其它的符号。对拼音文字而言，最简单的形式是单字母替换加密，也就是以每个字母为一个单位，将每个字母替换成另外的字母或者另外的符号。较为复杂的形式是以多个字母为一个单元，整体替换成其它的字符。这个映射方法被称为密码表，拿到密码表的人就能够将密文破译成明文。单字母替换加密是在古代就使用过的一种加密方法，但由于其容易被破解，所以在现代需要加密的场合已经很少使用。
单字母替换加密的破译方法有频率分析等。这种密码和破译方法在小说中也经常提到，例如爱伦·坡的《金甲虫》和柯南·道尔在福尔摩斯系列故事《归来记》中的“跳舞小人”。但当获取的密文篇幅不是很大时，光凭借频率分析是不足以破译全部密文的。往往还要熟知该种语言的人，经过对可能出现的词汇及字母组合进行分析，才能完整地破译密码。
第二阶段问题： 在密码的实际使用中，我们获取的密文往往是经过各种干扰的。例如密文不完整，或者在通信传输的过程中，密文存在被丢失、添加和篡改字符的可能。为简单起见，我们假设密文是通过一个带有噪声干扰的信道传输的。在通信过程中，每个字符经过信道传输的结果都属于如下四种情形之一：
1. 该字符在传输过程中被丢失，其概率为 p1；
2. 该字符本身正常传输，在其之后添加了一个随机字符，其概率为 p2；
3. 该字符在传输过程中被篡改为一个随机字符，其概率为 p3；
4. 该字符正常传输，其概率为 1 − p1 − p2 − p3。
在加密后，单词之间的间隔和标点符号全部被删去。请你改进之前的破译算法，使其能够在这种带有干扰的条件下完成破译工作，并推广对破译能力的评价指标，使其能应用于这种带有干扰的条件。
整体求解过程概述(摘要)
密码学起源于数千年以前，长期以来出现了许多密码的编制方法，较为简单的是替换式密码。对拼音文字而言，最简单的形式是单字母替换加密，也就是以每个字母为一个单位，将每个字母替换成另外的字母或者另外的符号。基于对文献的查找和分析，我们最后要得到的明文是英文语料库中的词语，而第二阶段的题目中明确提出加密后，每个单词之间的空格，以及标点符号都会被删除，并且我们获取的密文是通过一个带有噪声干扰的信道传输的，在通信过程中存在增删改的情况，而我们需要改进第一阶段中破解密文的方法，使其能在带有干扰的条件下完成破译工作。那我们就要针对不同的情况，建立不同的模型，以便在不同情况下得到密文对应的明文。
在第二阶段，我们将分以下几种情况进行讨论：
1. 我们获取了一段通过噪声干扰信道传输的密文，通过定性和定量分析得到干扰不会影响密文中字母出现频率，在改进第一阶段算法的基础上我们对没有标点和空格的密文进行了结构化处理，依次采用字母频率分析、高频字母结构化处理、任意文章同步推演和结构化单词间隔划分，尽可能多的找到密文-明文对应关系，以便于实现被干扰密码的破解。
2. 我们获取了一段有干扰的密文，欲找到使密文被读成明文最大的条件概率。可利用贝叶斯公式并且省掉一个常数项，等价变换为破译的密文即为明文的可能性乘以明文为有意义信息的可能性，得到概率。做出两个假设：（1）明文字母为马尔科夫链，也就是说，后一个字母只由前一个字母决定。（2）不同时刻的接收信号只由发送信号决定。根据独立输出假设，可以得到A的密文长度次幂种组合，那么我们就可以很容易利用算法 Viterbi 找出上面式子的最大值，进而找出要识别的明文。
3. 我们获取了一段密文，在假设可以最大限度地排除干扰破解密文的情况下，首先初步判断它能不能被直接破译，如果能直接破译，说明在通信过程中没有受到干扰，此时我们将采用 DES 算法破译由古典密码衍生出的分组密码。我们的每一种方法都配有相关实例，以便于推广对破译能力的评价指标。
问题分析：
对拼音文字而言，最简单的形式是单字母替换加密，也就是以每个字母为一个单位，将每个字母替换成另外的字母或者另外的符号。基于对文献的查找和分析，我们的最后要得到的明文是英文语料库中的词语，而我们需要对不完整，或者在通信传输的过程中，被丢失、添加和篡改字符的密码找到破解的方法，打个比方来说，明文就像锁在屋子里面的宝贝，密钥是打开屋子所需要的钥匙，而密文是外面的人，我们就是要从众多相似钥匙中做出判断，找到打开屋子真正的钥匙，拿到屋子里面的宝贝。那我们就要针对可能出现的钥匙，建立不同的模型，以便在不同情况下得到密文对应的明文。
在第二阶段，我们将分以下几种情况进行讨论：
1) 由于通信信道噪声干扰的存在，我们在获取了一段密文之后，首先通过定性和定量分析找出干扰（增删改）对字母统计的影响，分析过后得到干扰并不会影响字母统计，于是我们的模型就是在第一阶段的基础上进行改进。由于题目中明确提出加密后单词之间的空格和标点都会被删去，所以这个模型更注重于结构化，依次对密文进行：字母频率分析、高频字母的结构化处理、任意文章进
行同步推演、结构化单词间隔划分、部分密码表试解密并循环推算，尽可能的
找出更多的明密文对应关系，以便于最后破解带干扰的密文。
2) 我们获取了一段有干扰的密文，欲找到使密文被读成明文最大的条件概率。可利用贝叶斯公式并且省掉一个常数项，等价变换为破译的密文即为明文的可能性乘以明文为有意义信息的可能性，得到概率。做出两个假设：（1）明文字母为马尔科夫链，也就是说，后一个字母只由前一个字母决定。（2）不同时刻的接收信号只由发送信号决定。根据独立输出假设，可以得到A的密文长度次幂种组合，那么我们就可以很容易利用算法 Viterbi 找出上面式子的最大值，进而找出要识别的明文。
3) 我们获取了一段密文，在假设可以最大限度地排除干扰破解密文的情况下，首先初步判断它能不能被直接破译，如果能直接破译，说明在通信过程中没有受到干扰，此时我们将采用 DES 算法破译由古典密码衍生出的分组密码。
模型假设：
1. 由于英文语料库中包含大量信息，我们建立的模型所定义的明文只是语料库里面的一部分信息；
2. 我们所选取的语料库中的信息有一定的代表性，在模型的推广中能起作用；
3. 能最大限度地排除干扰破解密文得到合理化的明文；
4. 索引所花时间在控制范围和接受范围内；
5. 明文、密文一一对应；
论文缩略图：
全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
部分程序代码：(代码和文档not free)
char aticle[5000];
char cipher[5000];
char randomarticle[5000];
//函数声明区
int readcipher();
int preparecipher();
int creatcipher();
int letterfrequency();
int findwordsstructure();
int RandomArticleStructure();
int RandomArticleletterfrequency();
int Useletterfrequency(char somewords[]);
int Usefindwordsstructure(char usearticle,char letter,int m,int n);
int AddBlankCipher();
int Trydecipher();
//函数区
int preparecipher()//准备密文，去标点空格，全变大写
{
char ch;
int i=0;
int k=0;//忘记这个 k，用 i 弄错了好多次
FILE *fp=fopen("a.txt","r");//打开文件
if(!fp)
{
printf("can't open file\n");
return -1;
}
ch= fgetc(fp);
while(!feof(fp))
{
if((ch>='a'&&ch<='z')){
aticle[k]=ch-32;
k++;
}
else if((ch>='A'&&ch<='Z')){
aticle[k]=ch;
k++;
}
i++;
ch= fgetc(fp);
}
aticle[k]='\0';
printf("这段密文有%d 个字母\n",k);
printf("%s",aticle);
printf("\n");
fclose(fp);
return 0;
}
//创建密文
int creatcipher()//创建密文，去标点空格
{
char ch;
int i=0;
FILE *fp=fopen("cipher.txt","w");
if(!fp)
{
printf("can't open file\n");
return -1;
}
fprintf(fp,aticle);
fclose(fp);
return 0;
}
//读获取的密文
int readcipher()//读获取的密文
{
char ch;
int i=0;
FILE *fp=fopen("gotcipher.txt","r");//打开文件
if(!fp)
{
printf("can't open file\n");
return -1;
}
ch= fgetc(fp);
while(!feof(fp))
{
cipher[i]=ch;
i++;
ch= fgetc(fp);
}
cipher[i]='\0';
printf("需要破译的密文为\n\n");
printf("%s\n",cipher);
printf("\n");
printf("这段密文有%d 个字母\n\n",i);
fclose(fp);
return 0;
}
//各个字母在密文中出现的频率
int letterfrequency(){
char ch;
int i;
int j;
int k;
int sum=0;
int charactertimes[30];
int characternum=0;
for(j=0;j<26;j++)
charactertimes[j]=0;
//字母计算频数概率
for(i=0;cipher[i]!='\0';i++){
ch=cipher[i];
characternum++;
if((ch>='A'&&ch<='Z')){
charactertimes[ch-65]++;}
}
printf("密文中总共有字母%d 个\n\n",characternum);
//之前这里 25 数组越界
for(j=0;j<26;j++){
printf("密文中字母%c 出现的次数%d\n",j+65,charactertimes[j]);
sum=sum+charactertimes[j];
}
printf("\n\n\n");
printf("这些字母出现的次数之和为%d\n\n",sum);
printf("这些字母分别出现的概率为\n\n");
for(j=0;j<26;j++){
printf("密文中字母%c 出现的概率为%6.2f%%\n",j+65,100*(charactertimes[j])/(float)sum);
}
return 0;
}
//找到密文中出现频率高的字母对应的频率高的结构结构
int findwordsstructure()
{
char wordstructureR[300][10];
char sortwordstructureR[300][10];
char sortwordstructureNum[300];
char replaceword[10];
int i=0;
int j=0;
int k=0;
int structurenum=0;
int changeline=0;
int before3;
int before2;
int before1;
int behind3;
int behind2;
int behind1;
char ch;
int characternum=0;
for(i=0;cipher[i]!='\0';i++){
ch=cipher[i];
characternum++;
}
int state=0;
//printf("%d\n",characternum);
//printf("%s\n",cipher);
printf("密文中形如**R 的结构有\n\n");
for(i=5;i<characternum-5;i++){
ch=cipher[i];
//这里本来应该是等于的写成了赋值
if(ch=='R'){
changeline++;
before3=i-3;
before2=i-2;
before1=i-1;
behind3=i+3;
behind2=i+2;
behind1=i+1;
printf(" %c%c%c ",cipher[before2],cipher[before1],cipher[i]);
replaceword[0]=cipher[i-2];
replaceword[1]=cipher[i-1];
replaceword[2]=cipher[i];
replaceword[3]='\0';
//printf("0000%s\n",replaceword);
//**R 型的单词全部存进了 wordstructureR
strcpy(wordstructureR[structurenum],replaceword);
structurenum++;
if(changeline%5==0)
printf("\n");
}
}
/*for(i=0;i<structurenum;i++)
printf("wordstructureR %s \n",wordstructureR[i]);*/
printf("\n\n");
//按字母顺序输出 wordstructureR 中的单词
//printf("按字母排序后的单词单词\n");
//sortwordstructureR 里面储存了排序后的单词
printf("按字母顺序输出的**R 的结构的结构\n");
k=0;
for(i='A';i>='A'&&i<='Z';i++){
for(j=0;j<structurenum;j++){
if((wordstructureR[j][0]==i)){
state=1;
printf("%s ",wordstructureR[j]);
strcpy(sortwordstructureR[k++],wordstructureR[j]);}
}
if(state==1){
puts("\n");
state=0;
}
}
printf("密文中总共有%d 个**R 结构的单词\n\n",structurenum);
/*for(i=0;i<structurenum;i++)
printf("sortwordstructureR %s \n",sortwordstructureR[i]);*/
//用 sortwordstructureNum 记录每个**R 单词出现的次数，下标相对应，重复的记在第一次出现
的位置
for(i=0;i<structurenum;i++){//初始化
sortwordstructureNum[i]=0;
}
//后面的每一个和前面做比较，发现相同，前面加 1，发现不同，自己加 1
//state 为 0 表示没加，等于 1 表示加了
state=0;
sortwordstructureNum[0]=1;
for(i=1;i<structurenum;i++){
for(j=0;j<i;j++){
if(strcmp(sortwordstructureR[i],sortwordstructureR[j])==0){
sortwordstructureNum[j]++;
state=1;
break;
}
else
state=0;
}
if(state==0){
sortwordstructureNum[i]++;
state=1;
}
}
for(i=0;i<structurenum;i++){
if(sortwordstructureNum[i]!=0)
printf(" 第 %3d 号 位 置 的 结 构 %s 出 现 了 %3d 次
\n",i,sortwordstructureR[i],sortwordstructureNum[i]);
}
//出现频率比较高的单词结构
printf("\n 出现频率比较高的**R 结构\n\n");
for(i=0;i<structurenum;i++){
if((sortwordstructureNum[i]!=0)&&(sortwordstructureNum[i]>=4))
printf(" 第 %3d 号 位 置 的 结 构 %s 出 现 了 %3d 次
\n",i,sortwordstructureR[i],sortwordstructureNum[i]);
}
return 0;
}
//和随便网上找的文章做对比
int RandomArticleStructure()
{
char ch;
int i=0;
int k=0;//忘记这个 k，用 i 弄错了好多次
FILE *fp=fopen("randomarticle.txt","r");//打开文件
if(!fp)
{
printf("can't open file\n");
return -1;
}
ch= fgetc(fp);
while(!feof(fp))
{
if((ch>='a'&&ch<='z')){
randomarticle[k]=ch-32;
k++;
}
else if((ch>='A'&&ch<='Z')){
randomarticle[k]=ch;
k++;
}
i++;
ch= fgetc(fp);
}
randomarticle[k]='\0';
printf("这段随意找的文章有%d 个字母\n",k);
printf("%s",randomarticle);
printf("\n");
fclose(fp);
return 0;
}
int RandomArticleletterfrequency(){
char ch;
int i;
int j;
int k;
int sum=0;
int charactertimes[30];
int characternum=0;
for(j=0;j<26;j++)
charactertimes[j]=0;
//字母计算频数概率
for(i=0;randomarticle[i]!='\0';i++){
ch=randomarticle[i];
characternum++;
if((ch>='A'&&ch<='Z')){
charactertimes[ch-65]++;}
}
printf("这段随意找的文章中总共有字母%d 个\n",characternum);
//之前这里 25 数组越界
for(j=0;j<26;j++){
printf("这段随意找的文章中字母%c 出现的次数%d\n",j+65,charactertimes[j]);
sum=sum+charactertimes[j];
}
printf("这些字母出现的次数之和为%d\n",sum);
for(j=0;j<26;j++){
printf(" 这段随意找的文章中字母 %c 出现的概率
为%6.2f%%\n",j+65,100*(charactertimes[j])/(float)sum);
}
return 0;
}
int Useletterfrequency(char somewords[]){
char ch;
int i=0;
int j;
int k;
int sum=0;
int charactertimes[30];
int characternum=0;
FILE *fp=fopen("frequency.txt","w");
if(!fp)
{
printf("can't open file\n");
return -1;
}
for(j=0;j<26;j++)
charactertimes[j]=0;
//字母计算频数概率
for(i=0;somewords[i]!='\0';i++){
ch=somewords[i];
characternum++;
;