凯撒密码计算过程图（凯撒密码计算公式）
凯撒密码计算过程图（凯撒密码计算公式）
学号：16030140019
姓名: 莫益彰
【嵌牛导读】：凯撒密码是一种简单的加密方法，即将文本中的每一个字符都位移相同的位置。如选定位移3位：
原文：a b c
密文：d e f
由于出现了字母频度分析，凯撒密码变得很容易破解，因此人们在单一恺撒密码的基础上扩展出多表密码，称为“维吉尼亚”密码。
【嵌牛鼻子】密码学，计算机安全。
【嵌牛提问】维吉尼亚怎么破解，8位维吉尼亚是否可破？维吉尼亚算法的时间复杂度？
【嵌牛正文】
维吉尼亚密码的加密
维吉尼亚密码由凯撒密码扩展而来，引入了密钥的概念。即根据密钥来决定用哪一行的密表来进行替换，以此来对抗字频统计。假如以上面第一行代表明文字母，左面第一列代表密钥字母，对如下明文加密:
TO BE OR NOT TO BE THAT IS THE QUESTION
当选定RELATIONS作为密钥时，加密过程是：明文一个字母为T，第一个密钥字母为R，因此可以找到在R行中代替T的为K，依此类推，得出对应关系如下：
密钥:RE LA TI ONS RE LA TION SR ELA TIONSREL
明文:TO BE OR NOT TO BE THAT IS THE QUESTION
密文:KS ME HZ BBL KS ME MPOG AJ XSE JCSFLZSY
图解加密过程:
在维吉尼亚（Vigenère）的密码中，发件人和收件人必须使用同一个关键词（或者同一文字章节），这个关键词或文字章节中的字母告诉他们怎么样才能前后改变字母的位置来获得该段信息中的每个字母的正确对应位置。
维吉尼亚密码的破解
维吉尼亚密码分解后实则就是多个凯撒密码，只要知道密钥的长度，我们就可以将其分解。
如密文为：ABCDEFGHIJKLMN
如果我们知道密钥长度为3，就可将其分解为三组：
组1：A D G J N
组2：B E H K
组3：C F I M
分解后每组就是一个凯撒密码，即组内的位移量是一致的，对每一组即可用频度分析法来解密。
所以破解维吉尼亚密码的关键就是确定密钥的长度。
确定密钥长度
确定密钥长度主要有两种方法，Kasiski 测试法相对简单很多，但Friedman 测试法的效果明显优于Kasiski 测试法。
Kasiski 测试法
在英文中，一些常见的单词如the有几率被密钥的相同部分加密，即原文中的the可能在密文中呈现为相同的三个字母。
在这种情况下，相同片段的间距就是密文长度的倍数。
所以我们可以通过在密文中找到相同的片段，计算出这些相同片段之间的间距，而密钥长度理论上就是这些间距的公约数。
然后我们需要知道重合指数（IC, index of coincidence）的概念。
重合指数表示两个随机选出的字母是相同的的概率，即随机选出两个A的概率+随机选出两个B的概率+随机选出两个C的概率+……+随机选出两个Z的概率。
对英语而言，根据上述的频率表，我们可以计算出英语文本的重合指数为
P(A)^2 + P(B)^2+……+P(Z)^2 = 0.65
利用重合指数推测密钥长度的原理在于，对于一个由凯撒密码加密的序列，由于所有字母的位移程度相同，所以密文的重合指数应等于原文语言的重合指数。
据此，我们可以逐一计算不同密钥长度下的重合指数，当重合指数接近期望的0.65时，我们就可以推测这是我们所要找的密钥长度。
举例来说，对密文ABCDEABCDEABCDEABC
首先测试密钥长度=1，对密文ABCDEABCDEABCDEABC统计每个字符出现的次数：
A: 4 B: 4 C: 4 D:3 E:3
那么对于该序列的重合指数就为：(4/18)^2 + (4/18)^2 + (4/18)^2 +(3/18)^2 +(3/18)^2 != 0.65
然后测试密钥长度=2，将密文ABCDEABCDEABCDEABC分解为两组：
组1：A C E B D A C E B
组2：B D A C E B D A C
我们知道如果密钥长度真的是2，那么组1，组2都是一个凯撒密码。对组1组2分别计算重合指数。
如果组1的重合指数接近0.65，组2的重合指数也接近0.65，那么基本可以断定密钥长度为2。
在知道了密钥长度n以后，就可将密文分解为n组，每一组都是一个凯撒密码，然后对每一组用字母频度分析进行解密，和在一起就能成功解密凯撒密码。
上文已经说到，自然语言的字母频度是一定的。字母频度分析就是将密文的字母频度和自然语言的自然频度排序对比，从而找出可能的原文。
直接把每个字母往后推三位
出来的就是密文了
即
明文：COMPUTERSYSTEM
密文：FRPSXWHUVBVWHP
而解密时 只需要把密文每个字母前推3位（推三位这是标准的凯撒密码 加密时不一定推三位 这时只要统计各字母出现的频率便很容易解开）
这里有方法，自己看吧，比较多，呵呵
[凯撒介绍]
凯撒密码（kaiser）是罗马扩张时期朱利斯"凯撒（Julius Caesar）创造的，用于加密通过信使传递的作战命令。它将字母表中的字母移动一定位置而实现加密。
[加密原理]
凯撒密码的加密算法极其简单。其加密过程如下：
在这里，我们做此约定：明文记为m，密文记为c，加密变换记为E(k1,m)（其中k1为密钥），解密变换记为D(k2,m)（k2为解密密钥）（在这里k1=k2,不妨记为k）。凯撒密码的加密过程可记为如下一个变换：
c≡m+k mod n （其中n为基本字符个数）
同样，解密过程可表示为：
m≡c+k mod n （其中n为基本字符个数）
对于计算机而言，n可取256或128，m、k、c均为一个8bit的二进制数。显然，这种加密算法极不安全，即使采用穷举法，最多也只要255次即可破译。当然，究其本身而言，仍然是一个单表置换，因此，频率分析法对其仍是有效的。
[加密算法]
我们预定义基本字符个数为 #define MAX 128
凯撒加密函数可以表示为
[Copy to clipboard]
CODE:
char cipher(char plain_char, int key)
{
return (plain_char + key) % MAX;
};
凯撒解密函数：
[Copy to clipboard]
CODE:
char decipher(char cipher_char, int key)
{
return (cipher_char - key + MAX) % MAX;
};
加密后，原所有的ASCII码偏移key位，解密则移回key位。
如果要对一个文本文件进行加密，则只要依次逐个字符逐个字符地读取文本文件，进行加密后，逐个字符逐个字符写入密文文本文件中，即可：
[Copy to clipboard]
CODE:
FILE *fp_plaintext;
FILE *fp_ciphertext;
char plain_char;
... ...
while((plain_char=fgetc(fp_plaintext))!=EOF)
{
fputc(cipher(plain_char,key),fp_ciphertext);
}
对文件的解密也同样方法。
[破解原理]
一篇包含字符的英文文章，其各ASCII码字符出现，都有一定的频率，下面是对Google上随意搜索到的英文文章进行分析的结果，见表：
QUOTE:
=================================================
FileName : 01.txt
[1] 32: times:204
[2] 101:e times:134
[3] 116:t times:91
[4] 105:i times:87
[5] 111:o times:77
[6] 108:l times:75
[7] 97:a times:75
[8] 110:n times:69
[9] 10:
times:67
[10] 115:s times:63
=================================================
FileName : php.si.source.txt
[1] 32: times:576
[2] 101:e times:162
[3] 115:s times:153
[4] 110:n times:141
[5] 114:r times:138
[6] 105:i times:135
[7] 10:
times:134
[8] 116:t times:129
[9] 42:* times:116
[10] 111:o times:103
=================================================
FileName : work.txt
[1] 32: times:51322
[2] 101:e times:30657
[3] 116:t times:23685
[4] 97:a times:19038
[5] 111:o times:17886
[6] 105:i times:16156
[7] 110:n times:15633
[8] 114:r times:15317
[9] 115:s times:15226
[10] 104:h times:12191
=================================================
FileName : 02.txt
[1] 32: times:299
[2] 101:e times:217
[3] 110:n times:136
[4] 105:i times:133
[5] 111:o times:124
[6] 116:t times:116
[7] 97:a times:110
[8] 115:s times:98
[9] 114:r times:92
[10] 108:l times:82
=================================================
FileName : 03.txt
[1] 45:- times:404
[2] 32: times:394
[3] 101:e times:237
[4] 116:t times:196
[5] 114:r times:173
[6] 97:a times:163
[7] 105:i times:161
[8] 110:n times:153
[9] 111:o times:142
[10] 115:s times:129
=================================================
FileName : 04.txt
[1] 32: times:326
[2] 101:e times:179
[3] 116:t times:106
[4] 105:i times:101
[5] 111:o times:96
[6] 110:n times:94
[7] 97:a times:92
[8] 115:s times:78
[9] 100:d times:61
[10] 114:r times:60
=================================================
FileName : 05.txt
[1] 32: times:441
[2] 101:e times:191
[3] 111:o times:151
[4] 116:t times:120
[5] 97:a times:112
[6] 110:n times:108
[7] 105:i times:91
[8] 114:r times:84
[9] 117:u times:79
[10] 115:s times:79
有此分析可知，一篇英文文章中，出现较高频率的两个字符是 ' ' (空格) 和 'e'，而且它们的ASCII码分别是32和101，差值是69。
既然凯撒密码利用的是单表替换的一种简单加密算法，所以，我们的主角， ' ' 和 'e' ，在解密后，依然会保持相同的ASCII码差值，69。
|c1 - c2| = |'e' - ' '| = |101 - 32| = 69
|m1 - m2| = | ((c1 + k) mod 256)-((c2 + k) mod 256)| = |c1 - c2| = |'e' - ' '| = 69
现在可以得到破解凯撒密码的原理了，我们统计一片经过凯撒加密的密文字符信息，在出现频率较高的字符里面寻找差值是69的2个字符，这两个必定是 ' ' 和 'e' 字符的加密字符，计算偏移量（既密钥key），通过解密运算，还原出明文。
[破解算法]
任何一片英文加密后的密文，我们统计出所有字符的个数：
[Copy to clipboard]
CODE:
#define MAX 128
... ...
FILE *fp_ciphertext;
char cipher_char;
int i; //密文文件长度，包含多少字符
unsigned int size_file=0; //申明num数组，存储各个ASCII字符在密文中出现的个数
num[MAX];
... ...
for(i = 0;i MAX; i++) //初始化num数组中的值
num[i] = 0;
... ...
while((cipher_char=fgetc(fp_ciphertext))!=EOF)
{
num[cipher_char]++;
size_file++;
}
统计出现最多次数的字符，定义#define GETTOP 10，统计最多的前10位字符：
[Copy to clipboard]
CODE:
//统计前10位
#define GETTOP 10
... ...
int temp,i,j;
int maxascii[GETNUM]; //申明maxascii数组，存储统计出的概率前10位的字符ascii码
int maxtimes[GETNUM]; //申明maxtimes数组，存储统计出的概率前10位的字符的出现次数
... ...
for(i=0;iGETTOP;i++)
{
temp=0; //临时变量temp里面来存储出现最多次数的字符的ascii码
for(j=1;jMAX;j++) //依次比较所有的字符次数，获得最多字符的ascii码
{
if(num[j]=num[temp])
temp=j;
}
maxascii[i]=temp; //把出现最多次数字符的ascii存储到相应的maxascii数组中
maxtimes[i]=num[temp]; //把最多次数字符的出现次数存储到相应的maxtimes数组中
num[temp]=0; //把最多次数字符的次数赋值成0，
//进行循环运算，同样的算法，第二次循环得到的值，肯定是出现第二多的字符
//避免了对256或128个字符进行排序的复杂运算
//当年我用汇编编写成绩排序的程序时，也用这套排序算法:-)
}
找出出现最多字符中，ASCII码差别是69的两个字符，计算出密钥key的长度：
[Copy to clipboard]
CODE:
for(i=0;iGETTOP;i++)
{
for(j=0;jGETTOP;j++)
{
if((max[i]-max[j])==69)
{
key=(max[j] - 32 + MAX ) % MAX;
printf("Key : %d\n",key);
break;
}
}
}
既然得到了密钥长度，算完成了对凯撒密码的破解了，那就进行解密吧，大功告成！
恩~ 你都给了明文和密钥…不知道你还要什么方法啊？
如果你不知道凯撒，可以去百度一下，我给你简单说一下吧~
英文26个字母（不分大小写）可以由数字01~26来代替（有人也用00~25来代替，不过不常见~）
凯撒全称叫凯撒位移加密法，顾名思义啊~
比如A是01，你用n=4加密之后就是01+4=05，05在字母表里是E，所以A加密之后就是E~
CHINA用n=4加密之后就是GLMRI~ 明白没？
对了，需要说明一下，上面举的例子是字母表向右移动4位，n=4也可以理解为向左移动4位，那么CHINA加密之后就变成YDEJW~ 不过不用担心，一般情况下都是向右移的，当然也不排除某些变态向左移（强烈鄙视这种人！！！）…
恩~ 废话说了好多，给你密文吧~说明一下，我是用01~26和右移的方法加密的~
Glmri Girwvep Vehms erh XZ Yrmzivwmxc~ 完毕~（我加的有点快，不保证全对，你自己检查一下哈~）
再补一句，字母表可以循环用的，比如Z用完了就回到ABC…，这时候A就相当于27~ 明白否？
嘿嘿… 我腹黑一下下~ 如果你想用密码去虐一个人的脑细胞的话，推荐你用00~25和左移的方法，保证他能死至少一半的脑细胞~
嘿嘿嘿嘿……
举例：周期为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个英文字母进行替换。
