Vigenere Cipher密码解码.doc

Vigenere Cipher解密一、实验任务Vigenere Cipher加密密文如下：KVNIICWZSNOHUNXQGMRNAHUVWPTBWBPKVYPTBASHRZVIIWIBCGJSGEYGFMOAKBTBJKMAQEGSQJIJHTRGJSFRXTNBVFVCORWGENSIKRRAXVAIHNNZZRRCKMQEGOGRHGJCOYKVNIICWZSNOHUNXQGMRNACAGLGKMRUKZYFSHZMCEIWNGLGLWBFQTSBVOXZGYCJRFEPWBVRUCAFSHYWFZGFFYEXXWKAGFFJMNEJSNDZRGSUBBRBYBGBKGMPSECHGUIVTJZRQTOESVAMFUQCQVLCOMOQTSNZXJTBCAGRNLIXXVHUGGGNXGHNAVUGVFWKIXWNUHNGIUPMZGGFVAKYBBVGJSUREVHNWALIFGMEXAKRNHREMPZEWGJHURLGTBCSQDCEIULQCAYWYYFGMZOAUTBEQGWQBGQOABEUBACSHFRRHQFIBQLIFGMEX请写出详细解密过程。二、Vigenere加密与解密Vigenere加密为单表代换密码，其加密过程可表述为：设m是一个正整数，定义P=C=K=(Z26)m,对任意的密钥K=(k1,k2,km),定义eKx1,x2,xm=(x1+k1,x2+k2,xm+km)和dKy1,y2,ym=(y1-k1,y2-k2,ym-km)为Vigenere加密和解密过程，以上所有运算都在(Z26)m上进行。三、Vigenere密文的破译Vigenere解密首先在于确定密钥长度m，意大利的乔瓦尼波塔于1602年首先发现Vigenere明/密文中重复字母串的距离正好是密钥长度的倍数，这一现象称为“合拍”现象。由此出发，产生的确定m长度常用方法有两种：方法一是Kasiski测试法；方法二是重合指数法。重码分析法思路认为间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大。但此时需要注意真重复与偶然重复，需要剔除偶然重复，取真重复距离的因数作为密钥长度m。Kasiski测试法思路是对一份用周期性多表密码加密的密文，确定其中所有的重复出现的字母串，计算他们之间的距离，并对这些距离进行因子分解，出现频率较高的因子很可能是密钥的长度。两种方法本质思想是相同的，具有异曲同工之妙。本文将采用Kasiski测试法破译上述密文。根据密文，可以统计重复字母序列及其之间的距离（统计代码见附件），一部分列表如下，重复字母串位置距离素数因子分解KVNIICWZSNOHUNXQGMRNA0 1301302*5*13LIFGMEX350 430802*2*2*2*5PTB25 3493*3GJS49 3392902*5*29QEG68 118502*5*5CAG151 288137137GLG153 173202*2*5FSH163 203402*2*2*5CEI168 3822142*107QTS180 279993*3*11GFF210 220102*5TBC286 376902*3*3*5FGM394 432382*19SN8 281273273HU11 3713602*2*2*3*3*5NX13 3032902*5*29QG15 404389389GM16 4334173*139MR17 1571402*2*5*7RN18 359341341NA19 3072882*2*2*2*2*3*3TB26 4013753*5*23WB28 1961682*2*2*3*7KV31 130993*3*11上述密文重复字符串中，部分是由于偶然因素导致重复的，直觉判断可知长度较长字符串偶然重复概率极低，因此首先认为字符串KVNIICWZSNOHUNXQGMRNA、LIFGMEX为真重复，其最大公约数为10。进一步观测，可以发现大多数重复序列的距离都包含因数10。下面从概率角度考虑，密文字符串发生重复的概率。设y是一个长度为n密文，即y=y1y2ym,其中yi是密文字母，求从中抽到两个相同字母的概率是多少？为此,设NA为字母A在这份密文中的频数,设NB为字母B在这份密文中的频数,依此类推。 从n个密文字母中抽取两个字母的方式有Cn2=n(n-1)/2，而其中NA个A组成一对A的方式有CNA2=NA(NA-1)/2，于是从y中抽到两个字母都为A的概率为NA(NA -1)/n(n-1)，因此，从y中抽到两个相同字母的概率为:i=AZNi(Ni-1)n(n-1),这个数据称为这份密文的重合指数,记为IC。根据概率论中的大数定律，如果y是用单表加密的，那么当n较大时，IC很可能接近于0.0687。现在选取m=10，将密文一行一行写在有10列的表格里，对各列计算相应重合指数IC，最后求取平均IC，可得0.070855，接近理论值0.0687。根据上述分析判断确定密钥长度为10。下图是将密文按列统计各字母出现频数及计算各列IC结果。接下来是确定具体的密钥K=(k1,k2k10)。现令f0,f1f25分别表示字符串yi(1i10)中字母A，BZ出现的频数，字符串yi长度为ni，则26个字母在yi中出现频率为f0ni,f1nif25ni考虑到字符串yi是由对应的待加密的明文子集中的字母移动ki个位置所得的，因此移动后的概率分布为fkini,f1+kinif25+kini假设0g25，定义Mg=i=025pifi+gni如果g=ki，类似前面重合指数的讨论，应该有Mgi=025pi2=0.065如果gki，则Mg一般小于0.065。根据上表求得结果，进一步可求得Mg如下图所示，由结果推得密钥很可能是K=（2,14,13,13,4,2,19,8,14,13），对于字母是CONNECTION。根据密钥解密后明文是：I have a dream that one day this nation will rise up live up to the true meaning of its creed:“we hold these truths to be self-evident that all men are created equal.” I have a dream that one day on the red hills of Georgia, the sons of former slaves and the sons of former slave owners will be able to sit down together at the table of brotherhood. I have a dream that one day even the state of Mississippi, a state sweltering with the heat of injustice ,sweltering（闷热的） with the heat of oppression will be transformed into an oasis(绿洲) of freedom and justice.四、总结Vigenere密码作为一个多表代换密码，相对于单表代换密码而言安全性更高，破解难度也更高。但是对于密钥已定的Vigenere密码来说，仍可以通过唯密文攻击来实现破解，关键在于密钥长度m的确定。而正由于密钥长度的有限性，在面对长篇幅明文时，密文中就会暴露出重复字符串，这些重复密文字符串则就提供了密钥的长度信息。进一步，借助于重合指数加以判定，就可以推测出加密密钥的长度，最终破解密码。附：全部重复字母序列查找结果查找重复字符串的代码：#include#include#include#define MAX 1024/定义?密文?最?大长度typedef struct distancechar* p;int length;/字?符?串?长度int index;/字?符?串?在密文?中D位?置?int d;/距离?DIS;/同?一?个?重?复字?符?串?，?只?计?算?第一?个?与?最?后一?个?重?复字?符?串?距离?DIS GetDis(char*,char*,int);char* copystring(char*,int,int);bool IsPart(char*,char*);void main()char *s;char *filename=程超?_EncyrptedFile.dat;FILE *fp;if(!(fp=fopen(filename,r)printf(无T法打开a文?件t！?);return ;s=(char*)malloc(sizeof(char)*MAX);int i=0;while(!feof(fp)&(i=MAX-2)fscanf (fp,%c,s+i);i+;if(ip=NULL;dis-d=0;dis-index=0;dis-length=0;/当检测a到?元a素?的?length为a0时，?认?为a结束?元a素?for(i=len/2;i=2;i-) for(int j=0;jlength!=0) if(IsPart(dis0.p,(dis+l)-p)& strcmp(dis0.p,(dis+l)-p)!=0& dis0.index=(dis+l)-index& dis0.index+dis0.lengthindex+(dis+l)-length& dis0.index+dis0.d=(dis+l)-index+(dis+l)-d& dis0.index+dis0.d+dis0.lengthindex+(dis+l)-d+(dis+l)-length) | (strcmp(dis0.p,(dis+l)-p)=0& dis0.index+dis0.d=(dis+l)-index+(dis+l)-d& dis0.index+dis0.d+dis0.lengthindex+(dis+l)-d+(dis+l)-length) Is0=true;break; l+; if(!Is0) if(dis0.length!=0) *(dis+k)=dis0;k+; (dis+k)-p=NULL;(dis+k)-d=0;(dis+k)-index=0;(dis+k)-length=0; /输?出?过y程DIS* dis1=dis; printf(字?符?串? 位?置? 距离?n); while(dis1-length!=0) printf(%s,dis1-p); /对?应|补1足?空?格? for(i=0;ilength;i+) printf( ); printf(%d %d,dis1-index,dis1-index+dis1-d); /求两?个?数y字?长度+1 int ll=1; int index1=dis1-index; int index2=dis1-index+dis1-d; if(index1=0) ll+=1; else while(index1!=0) ll+=1; index1=index1/10; if(index2=0) ll+=1; else while(index2!=0) ll+=1; index2=index2/10; /对?应|补1足?空?格? for(i=0;id); dis1+; free(dis); free(s); s=NULL; int lll; scanf(%d,&lll); return ;DIS GetDis(char* s,char* p,int index) int len=strlen(s);int len0=strlen(p); DIS dis;if(len=0|len0=0)printf(出?现?空?的?数y组！?);dis.length=0;dis.d=0;dis.index=0;dis.p=NULL;return dis;if(strlen(s)strlen(p) printf(会出?现?越?界?错误！?);dis.length=0;dis.d=0;dis.index=0;dis.p=NULL;return dis;int i;int d=0;bool Is=false;for(i=0;ilen-len0+1;i+) if(strcmp(p,copystring(s,len0,i)=0)d=i+len0;Is=true;if(Is) dis.length=len0;dis.d=d;dis.index=index;dis.p=p; return dis;else dis.length=0; dis.d=0;dis.index=0; dis.p=NULL;return dis;/将?字?符?串?某3段?取?出?/length为a取?出?长度，?i为a起e始?位?置?char* copystring(char* s,int length,int i)char* p;p=(char*)malloc(sizeof(char)*(length+1);if(int)strlen(s+i)length) printf(会出?现?越?界?错误！?);return NULL; int j;for(j=0;j=len2) p1=s1;p2=s2;N=len1;n=len2; else p1=s2;p2=s1;N=len2;n=len1; for(int i=0;iN-n+1;i+) if(strcmp(p2,copystring(p1,n,i)=0) return true; return false;确定密钥长度后，通过重合指数进行判定，及用于判定密钥的代码#include#include#include#include#define MAX 1024/定义?密文?最?大长度void main() char *s;char *filename=程超?_EncyrptedFile.dat;FILE *fp;if(!(fp=fopen(filename,r)printf(无T法打开a文?件t！?);return ;s=(char*)malloc(sizeof(char)*MAX);int i=0;while(!feof(fp)&(i=MAX-2)fscanf (fp,%c,s+i);i+;if(i=MAX-2) *(s+i-1)=0;else *(s+MAX-1)=0;fclose(fp);int len=strlen(s);int a1027;for(int i=0;i10;i+)for(int j=0;j27;j+)aij=0;for(int i=0;ilen;i+)int j=i%10;char ch=*(s+i);int k=ch-A;ajk+=1;aj26+=1; double ic10;for(int i=0;i10;i+)ici=0.0;for(int i=0;i10;i+)for(int j=0;j26;j+)ici+=(double)(aij*(aij-1)/(ai26*(ai26-1); /1111111 char* outfile=result.txt;FILE* fp0;if(!(fp0=fopen(outfile,w)printf(无T法打开a文?件t！?);return ;fprintf(fp0,%s,频数y );for(int i=1;i=10;i+)fprintf(fp0,%d%s,i, );fprintf(fp0,%c,n);for(int j=0;j26;j+)fprintf(fp0,%c%s,A+j, );for(int i=0;i10;i+)fprintf(fp0,%d%s,aij, );fprintf(fp0,%c,n);fprintf(fp0,%s,IC );double sum=0.0;for(int i=0;i10;i+)sum+=ici/10;fprintf(fp0,%lf%s,ici, );fprintf(fp0,%c,n);fprintf(fp0,%s%lf,平?均IC是?:,sum); fclose(fp0);/2222222 char* out=outfile.txt;FILE* fp1;if(!(fp1=fopen(out,w)printf(无T法打开a文?件t！?);return ;for(int i=0;ilen;i+)fprintf(fp1,%c,*(s+i);if(i%10=9) fprintf(fp1,%c,n);fclose(fp1);/3333333char* outname=outMg.txt;FILE* fp2;if(!(fp2=fopen(outname,w)printf(无T法打开a文?件t！?);return ;double p26;p0=0.082;p1=0.015;p2=0.028;p3=0.043;p4=0.127;p5=0.022;p6=0.020;p7=0.061;p8=0.070;p9=0.002;p10