广州网站整站优化,广州建站外包公司历史长,做网站可以做哪些方面的,Seo建设网站的步骤2015年认证杯SPSSPRO杯数学建模
B题 替换式密码
原题再现#xff1a; 历史上有许多密码的编制方法。较为简单的是替换式密码#xff0c;也就是将文中出现的字符一对一地替换成其它的符号。对拼音文字而言#xff0c;最简单的形式是单字母替换加密#xff0c;也就是以每个…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 nodeoth)const//将单词按长度从大到小排序
19 {
20 if (lenn!oth.lenn) return lennoth.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 lenstrlen(s);
38 int tmp0; //一开始停留在编号为 0 的根节点
39 for (int i0; ilen; i)
40 {
41 if (f[tmp][s[i]-a]-1) //如果从 tmp 出发经过字母 s[i]到达的结点还没有新建
42 f[tmp][s[i]-a]tree_num; //新建之编号为tree_num
43 tmpf[tmp][s[i]-a];//经过一个字母 s[i],tmp 编号的改变
44
45 v[tmp]1; //最后停留在编号为 tmp 是一个字典里的单词
46 }
47 int vis[26];//若有加密规则 a-b(0a26,0b26),则 vis[a]bvis[a]-1 表示 a-?(a 被替换成什
么字母当前未知)
48 int ans[26];//若有加密规则 a-b(0a26,0b26),则 ans[b]aans[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 i0; i26; i)
62 fprintf(f3,%c ,ia);
63 fprintf(f3,\n);
64 for (int i0; i26; i)
65 fprintf(f3,| );
66 fprintf(f3,\n);
67 for (int i0; i26; i)
68 fprintf(f3,v );
69 fprintf(f3,\n);
70 for (int i0; i26; i)
71 if (vis[i]-1)fprintf(f3,? );
72 else fprintf(f3,%c ,vis[i]);
73 fprintf(f3,\n\n);
74
75 for (int i0; iword_num; i)
76 {
77 if (a[F[i]].punc1) //如果是标点符号直接输出标点符号
78 fprintf(f3,%s,a[F[i]].lex);
79 else //否则对每个字母解密后输出
80 {
81 if (i0a[F[i-1]].punc0)
82 fprintf(f3, );
83 for (int j0; ja[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 (xendx1) //第 endx 个单词也解密完成能找到一种替换规则解密所有被指定的
单词
93 {
94 successful_sol;
95 print_solution();
96 return;
97 }
98 if (a[x].punc1)
99 {
100 dfs(x1,0,0);
101 return;
102 }
103 if (a[x].lenny) //解密到第 x 个单词的第 len(x)位即已知道第 x 个单词各字母由什么字
母加密而来
104 {
105 if (v[tmp]) //如果按这种规则解密后的第 x 个单词是字典中的单词
106 dfs(x1,0,0); //从第 x1 个单词的第 0 位开始解密停留在字典树的 0 号根节点
107 return;
108 }
109 for (int i0; i26; i) //枚举?-单词 x 的第 y 位
110 if (f[tmp][i]!-1) //强力剪枝
111 //如果单词 x 的前 y-1 位加上 i 构不成任何单词的前缀则不可能由 i-单词 x 的第
y 位
112 {
113 if (vis[i]-1ans[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,y1,f[tmp][i]); //从第 x 个单词的 y1 位开始解
密当前停留结点编号做相应改变
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,y1,f[tmp][i]);
125 }
126 }
127 }
128 //-------------------------------------------
129 int left0,nlen0;
130 void addword()
131 {
132 s[nlen]\0;
133 strcpy(a[word_num].lex,s);
134 a[word_num].lennstrlen(a[word_num].lex);
135 a[word_num].idword_num; //在未排序之前第 i 个产生的单词在密文中的位置为
第 i 个
136 a[word_num].punc(left1?1:0);
137 word_num;
138 left0;
139 nlen0;
140 }
141 void read_passage()//从密文文件中读入所有以空白字符隔开的字符串处理掉标点符号后以单词
形式存入 a 数组
142 {
143 word_num0;
144 char cc;
145 while (fscanf(f2,%c,cc)!EOF)
146 {
147 if (cc ||cc\t||cc\n)
148 {
149 if (left1)s[nlen] ;
150 if (left)addword();
151 }
152 else if (ccaccz||ccAccZ)
153 {
154 if (left1)addword();
155 if (ccZ)cc32;
156 if (left0)left2;
157 s[nlen]cc;
158 }
159 else
160 {
161 if (left)addword();
162 if (left0)left1;
163 s[nlen]cc;
164 }
165 }
166 if (left)addword();
167
168
169 sort(a,aword_num);
170 for (int i0; iword_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_num0; //字典树初始化
180
181 //从字典文件读入所有的单词并构建一棵字典树
182 dictionary_num0;
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 f1fopen(dic1.txt,r); //只读方式打开字典文件
197 f2fopen(text2.txt,r); //只读方式打开密文文件
198 f3fopen(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 startx0;
208 endxword_num-1;
209 dfs(startx,0,0);
210 printf(%d\n,successful_sol);
211 system(pause);
212 }
213
214全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可
