2015年认证杯SPSSPRO杯数学建模
B题 替换式密码
原题再现：
历史上有许多密码的编制方法。较为简单的是替换式密码，也就是将文中出现的字符一对一地替换成其它的符号。对拼音文字而言，最简单的形式是单字母替换加密，也就是以每个字母为一个单位，将每个字母替换成另外的字母或者另外的符号。较为复杂的形式是以多个字母为一个单元，整体替换成其它的字符。这个映射方法被称为密码表，拿到密码表的人就能够将密文破译成明文。单字母替换加密是在古代就使用过的一种加密方法，但由于其容易被破解，所以在现代需要加密的场合已经很少使用。
单字母替换加密的破译方法有频率分析等。这种密码和破译方法在小说中也经常提到，例如爱伦·坡的《金甲虫》和柯南·道尔在福尔摩斯系列故事《归来记》中的“跳舞小人”。但当获取的密文篇幅不是很大时，光凭借频率分析是不足以破译全部密文的。往往还要熟知该种语言的人，经过对可能出现的词汇及字母组合进行分析，才能完整地破译密码。
第一阶段问题： 假设明文是由现代通常使用的英语写成的。现在我们获取了一些由单字母加密方法加密的密文。请你建立合理的数学模型，设计一个算法，来自动化地破译密文。并设计一个衡量破译能力的标准，来评价破译算法的破译能力。为了问题简单起见，我们假设密码表仅是针对 26 个字母的，每个单词之间的空格，以及标点符号仍然会保留。在设计算法时，如果需要，可以参考英文语料库的数据，例如免费的 COCA1等相关资料。
整体求解过程概述(摘要)
单字母替换式密码的研究对密码破解有很大的影响，本文研究了简单的单字母替换式密码破译的问题，建立了离散优化模型，首先设计了穷举算法、频率分析算法、字典树 dfs 算法。
对于穷举算法，从所有可能的对应关系中随机选出一种，然后判断其是否为密钥，若是其是所求密钥则得出明文，否则选取其他规则进行进行判断，本文从运算复杂度等因素对该算法进行分析。
对于频率分析算法，根据单字母高频统计表，按照英文构词与语法的统计规则入手，按照明文和密文字母出现频率进行分析，得到频率分析算法解密的正确率为 80%。
对于字典树 dfs 算法，首先利用字典库中的单词构建一棵字典树，在深度优先搜索的同时记录当前搜索确定的单词前缀在字典树中对应的结点，利用该结点新加某字母 x的不可到达字典树已构建好的任一结点的性质，及时剪枝——不再搜索密文下一位字母解密后为某字母 x 的可能性。通过程序测试，当密文篇幅大于 100 单词时，可直接生成结果；当篇幅介于 40-100 时，可生成两个左右的结果，可通过人为直接判别出结果；当密文由不到十个词汇组成时，则根据密文所符合的构词规则会生成几个到几百个不定的结果，此时想要得出合适的明文需要依靠人力完成。然后本文将三种算法通过对不同类型的密文进行对比，得到频率分析算法适合大篇幅的密文，字典树剪枝算法不仅适合求出大篇幅的密文，也可以通过加上少量人工的判断可以求出较短篇幅的密文。
最后，本文假设结合频率分析算法与字典树 dfs 算法，预测对于短篇幅的密文的人工判别的次数将大量减少。
问题分析：
本题是研究单字母替换密码问题，替换规则多种多样，较为常见的如凯撒密码，仿射密码，摩斯密码等，但常见的替换规则均有特殊性，不能代表普遍的替换规则。我们在本题中以随机单字母替换规则建立数学模型，设计算法，并进一步求解。
对于篇幅很大的密文，我们可以用频率分析的方法，根据密文中字母的频率分布推测加密规则。但是当获取的密文篇幅不是很大时，光凭借频率分析是不足以破译全部密文的。往往要经过对可能出现的词汇及字母组合进行分析判断，才能完整地破译密文。单字母替换规则是随机的，一共有 26!种情况，对于随机替换情况需要做一步一步的优化，使得选取随机的方式更为简单，从而达到大大减少运算量的目的。
对于上述建立模型的方法，在设计算法求解过程中，难以避免的是 26 个字母中有少量字母的替换规则出错，尤其是密文篇幅少且单词长度短，构成正确单词的解有多个，导致明文的正确度降低。于是，我们需要对所建立的几个模型进行对比，根据不同算法的不同适用范围对解密方法进行破译能力划分。
此外，本题是个实际问题，现实中需要考虑的因素远远多于题目本身，如何使模型更加贴近实际，并提供有效的单词数据库是本文面临的一大困难，通过查阅大量资料与文献，并进行适当的、合理的假设，对单字母替换密码的解密方式进行研究。
模型假设：
模型假设
假设一：根据题目要求，假设我们得到的密文所用的加密密码表仅针对 26 个字母进行加密，空格与标点仍然保留。
假设二：设计算法时，假设被加密的明文中并没有（或者数量极少）专有名词和奇怪拼写。
假设三：密文没有时效性（即在设计算法时并不考虑运行时间）。
假设说明
对于假设一属于题目要求，为简化算法而存在。
对于假设二、三是为设计算法而提出的，我们可以将其视作密文的一般情况，实际上，假设二、三也符合多数密文的实际状况。对于二三的特殊情况，需要根据实际情况更改单词库和部分规则。
论文缩略图：
全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
部分程序代码：(代码和文档not free)
1 //下文中替换规则 a->b 均指在加密过程中 a 被替换成 b
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <cstdlib>
6 using namespace std;
7 char s[100];
8 FILE *f1;
9 FILE *f2;
10 FILE *f3;
11 #define MAXWN 100000 //密文中单词个数的上限
12 struct node
13 {
14 char lex[30]; //单个单词长度最大为 30
15 int lenn; //该单词的长度
16 int id; //该单词在密文中是第几个出现的
17 int punc; //为 1 表示是标点符号，为 0 表示是单词
18 bool operator<(const node&oth)const//将单词按长度从大到小排序
19 {
20 if (lenn!=oth.lenn) return lenn>oth.lenn;
21 if (strcmp(lex,oth.lex)>0) return 1;
22 else return 0;
23 }
24 } a[MAXWN]; //存密文中单词的数组
25
26 int F[MAXWN];//F[i]存密文中第 i 个单词在从大到小排序后位于第 F[i]个位置，排序后得到，解密
输出密文时用到
27
28 int word_num;//密文中单词总数，由实际从密文文件读入确定
29 int dictionary_num;//字典中单词总数，由实际从字典文件读入确定
30
31 #define MAXTN 1000000//字典树中结点总个数的上限
32 int f[MAXTN][26];//f[i][j]表示若在编号为 i 的结点，再经过一个字母 j，到达的结点的编号
33 int v[MAXTN]; //v[i]=1 表示从根结点出发停留在字典树编号为 i 的结点，顺次经过的字母组
成的单词在之前的字典里
34 int tree_num; //字典树中结点总个数，主要在构建字典树时用到
35 void add(char *s)
36 {
37 int len=strlen(s);
38 int tmp=0; //一开始停留在编号为 0 的根节点
39 for (int i=0; i<len; i++)
40 {
41 if (f[tmp][s[i]-'a']==-1) //如果从 tmp 出发经过字母 s[i]到达的结点还没有新建
42 f[tmp][s[i]-'a']=++tree_num; //新建之，编号为++tree_num
43 tmp=f[tmp][s[i]-'a'];//经过一个字母 s[i],tmp 编号的改变
44
45 v[tmp]=1; //最后停留在编号为 tmp 是一个字典里的单词
46 }
47 int vis[26];//若有加密规则 a->b(0<=a<26,0<=b<26),则 vis[a]=b；vis[a]==-1 表示 a->?(a 被替换成什
么字母当前未知)
48 int ans[26];//若有加密规则 a->b(0<=a<26,0<=b<26),则 ans[b]=a；ans[b]==-1 表示->b(什么字母被替
换成 b 当前未知)
49 int startx,endx;//当前指定的要求解密的单词为从 a[beginx,endx]里所有单词
50 int successful_sol;//成功的方案数
51
52 void print_solution()
53 {
54 fprintf(f3,"=============sol:%d===============\n",successful_sol);
55 /*如果有替换规则 a->b,b->c,c->a,……
56 会输出 a b c
57 | | |
58 v v v
59 b c a
60 */
61 for (int i=0; i<26; i++)
62 fprintf(f3,"%c ",i+'a');
63 fprintf(f3,"\n");
64 for (int i=0; i<26; i++)
65 fprintf(f3,"| ");
66 fprintf(f3,"\n");
67 for (int i=0; i<26; i++)
68 fprintf(f3,"v ");
69 fprintf(f3,"\n");
70 for (int i=0; i<26; i++)
71 if (vis[i]==-1)fprintf(f3,"? ");
72 else fprintf(f3,"%c ",vis[i]);
73 fprintf(f3,"\n\n");
74
75 for (int i=0; i<word_num; i++)
76 {
77 if (a[F[i]].punc==1) //如果是标点符号直接输出标点符号
78 fprintf(f3,"%s",a[F[i]].lex);
79 else //否则对每个字母解密后输出
80 {
81 if (i>0&&a[F[i-1]].punc==0)
82 fprintf(f3," ");
83 for (int j=0; j<a[F[i]].lenn; j++)
84 fprintf(f3,"%c",ans[a[F[i]].lex[j]-'a']+'a');
85 }
86 }
87 fprintf(f3,"\n\n");
88 }
89 void dfs(int x,int y,int tmp)
90 //当前已解密到从第 x 的单词的第 y 位，第 x 个单词解密后停留在字典树的第 tmp 号结点
91 {
92 if (x==endx+1) //第 endx 个单词也解密完成，能找到一种替换规则解密所有被指定的
单词
93 {
94 successful_sol++;
95 print_solution();
96 return;
97 }
98 if (a[x].punc==1)
99 {
100 dfs(x+1,0,0);
101 return;
102 }
103 if (a[x].lenn==y) //解密到第 x 个单词的第 len(x)位，即已知道第 x 个单词各字母由什么字
母加密而来
104 {
105 if (v[tmp]) //如果按这种规则解密后的第 x 个单词是字典中的单词
106 dfs(x+1,0,0); //从第 x+1 个单词的第 0 位开始解密，停留在字典树的 0 号根节点
107 return;
108 }
109 for (int i=0; i<26; i++) //枚举?->单词 x 的第 y 位
110 if (f[tmp][i]!=-1) //强力剪枝
111 //如果单词 x 的前 y-1 位加上 i 构不成任何单词的前缀，则不可能由 i->单词 x 的第
y 位
112 {
113 if (vis[i]==-1&&ans[a[x].lex[y]-'a']==-1)
114 //i->? 并且 ?->单词 x 的第 y 位
115 {
116 vis[i]=a[x].lex[y];
117 ans[a[x].lex[y]-'a']=i; //修改 vis 和 ans
118 dfs(x,y+1,f[tmp][i]); //从第 x 个单词的 y+1 位开始解
密，当前停留结点编号做相应改变
119 vis[i]=-1;
120 ans[a[x].lex[y]-'a']=-1; //还原 vis 和 ans
121 }
122 else if (vis[i]==a[x].lex[y]) //之前就已知 i->单词 x 的第 y 位,与当前枚举 i->单词 x
的第 y 位不冲突
123 {
124 dfs(x,y+1,f[tmp][i]);
125 }
126 }
127 }
128 //-------------------------------------------
129 int left=0,nlen=0;
130 void addword()
131 {
132 s[nlen++]='\0';
133 strcpy(a[word_num].lex,s);
134 a[word_num].lenn=strlen(a[word_num].lex);
135 a[word_num].id=word_num; //在未排序之前，第 i 个产生的单词在密文中的位置为
第 i 个
136 a[word_num].punc=(left==1?1:0);
137 word_num++;
138 left=0;
139 nlen=0;
140 }
141 void read_passage()//从密文文件中读入所有以空白字符隔开的字符串，处理掉标点符号后以单词
形式存入 a 数组
142 {
143 word_num=0;
144 char cc;
145 while (fscanf(f2,"%c",&cc)!=EOF)
146 {
147 if (cc==' '||cc=='\t'||cc=='\n')
148 {
149 if (left==1)s[nlen++]=' ';
150 if (left)addword();
151 }
152 else if (cc>='a'&&cc<='z'||cc>='A'&&cc<='Z')
153 {
154 if (left==1)addword();
155 if (cc<='Z')cc+=32;
156 if (left==0)left=2;
157 s[nlen++]=cc;
158 }
159 else
160 {
161 if (left)addword();
162 if (left==0)left=1;
163 s[nlen++]=cc;
164 }
165 }
166 if (left)addword();
167
168
169 sort(a,a+word_num);
170 for (int i=0; i<word_num; i++)
171 F[a[i].id]=i; //得到 F 数组
172 }
173 //-------------------------------------------
174 void create_trie()
175 {
176
177 memset(f,255,sizeof(f)); //字典树初始化
178 memset(v,0,sizeof(v)); //字典树初始化
179 tree_num=0; //字典树初始化
180
181 //从字典文件读入所有的单词，并构建一棵字典树
182 dictionary_num=0;
183 while (fscanf(f1,"%s",s)!=EOF)
184 {
185 add(s);
186 dictionary_num++;
187 }
188 }
189 int main()
190 {
191 int size = 128 << 20; //G++扩栈语句
192 char *p = (char*)malloc(size) + size; //G++扩栈语句
193 __asm__("movl %0, %%esp\n" :: "r"(p));//G++扩栈语句
194 //如果编译器是 C++，应该注释掉上面三句，并在这个程序#include <cstdio>前加一句
195 //#pragma comment(linker, "/STACK:102400000,102400000")
196 f1=fopen("dic1.txt","r"); //只读方式打开字典文件
197 f2=fopen("text2.txt","r"); //只读方式打开密文文件
198 f3=fopen("ans.txt","w");//只写方式打开解密文文件
199
200 create_trie();
201 read_passage();
202
203 printf("dic=%d word=%d tree=%d\n",dictionary_num,word_num,tree_num);//调试语句
204
205 memset(vis,255,sizeof(vis));
206 memset(ans,255,sizeof(ans));
207 startx=0;
208 endx=word_num-1;
209 dfs(startx,0,0);
210 printf("%d\n",successful_sol);
211 system("pause");
212 }
213
214
