Cracking The Vigenere Cipher

In order to crack “Vigenere Cipher” under the circumstance that the key length can be only 3, 4 or 5, I used frequency analysis to find possible keys and compared the Euclidean distance of all candidate keys calculated with “Relative frequencies of letters in the English language” to find correct key length and then the correct key.

My code follows the steps below:

1. Preparation

        public static string bigfile=null;   // complete file 
        public static int[] keylength = {3,4,5}; // keylength
        public static string filename="sample.txt"; //file name
        public static Dictionary<char, double> normalfre = new Dictionary<char, double>();
        normalfre.Add(‘E‘, 0.12072);                            // standard language frequence pair
        normalfre.Add(‘T‘, 0.09056);
        normalfre.Add(‘A‘, 0.08167);
        normalfre.Add(‘O‘, 0.07507);
        normalfre.Add(‘I‘, 0.06966);
        normalfre.Add(‘N‘, 0.06749);
        normalfre.Add(‘S‘, 0.06327);
        normalfre.Add(‘H‘, 0.06094);

First, I established a Dictionary called “normalfre” to describe the “Relative frequencies of letters in the English language” found on the internet [http://en.wikipedia.org/wiki/Letter_frequency]. It is used to compare with the frequency we got from the original text.

And candidate “keylength” is {3,4,5}. “filename” is “sample.txt”.

2. Import file

 static void readfile(string filename) 
 {
        bigfile=File.ReadAllText(filename);
        }

Use function "ReadAllText" to get original string.

3.  Find the key length

static int determinkeylength() {
            Dictionary<int, double> avera = new Dictionary<int, double>();                          // store average distance and key length

            for (int j = 0; j < 3; j++)
            {
                List<string> text = divideByKeylength(keylength[j], bigfile);       // divide file into keylength part and write into string[]

                List<double> distances = new List<double>();
                //determine key
                for (int i = 0; i < keylength[j]; i++)
                {
                    Dictionary<char, double> frequences = new Dictionary<char, double>();
                    frequences = frequencyAnalysis(text[i]);
                    double maxfre = frequences.Values.Max();
                    char maxChar = frequences.Keys.Where(c => frequences[c] == maxfre).LastOrDefault();

                    // find frequence table
                    Dictionary<char, double> kd = findKeyDistance(frequences);
                    double mindist = kd.Values.Min();
                    char key = kd.Keys.Where(c => kd[c] == mindist).LastOrDefault();
                    distances.Add(mindist);        
                                                                                  //find possible key and it‘s distance with normal language frequences
                }

                avera.Add(j + 3, distances.Sum() / keylength[j]);
                // System.Console.WriteLine("Average dis:{0}",avera[j]);          // calculate average for determine key length
            }
            double minn = avera.Values.Min();
            int finalkeylength = avera.Keys.Where(c => avera[c] == minn).LastOrDefault();
            //System.Console.WriteLine(finalkeylength);
            return finalkeylength;
        
        }
    }

4. Divide text by key length

static List<string> divideByKeylength(int keylen, string originalText) {

            List<string> dividedfile = new List<string>();
            StringBuilder[] sb = new StringBuilder[keylen];

            for (int i = 0; i < keylen; i++)
                sb[i] = new StringBuilder();

            for (int i = 0; i < originalText.Length; i++) 
                sb[i % keylen].Append(originalText[i]);

            foreach (var item in sb)
                dividedfile.Add(item.ToString());
            
            return dividedfile;
        }

5. Frequency analysis for each divided text

 static Dictionary<char, double> frequencyAnalysis(string dividedfile) { 
            Dictionary < char, double > fretable = new Dictionary < char, double > ();
            double filelength = dividedfile.Length;
            for (int i = 0; i < filelength; i++)
            {
                char key = dividedfile[i];
                if (fretable.Keys.Contains(key))
                    fretable[key] = fretable[key] + 1/filelength;
                else
                    fretable[key] = 1/filelength;
            }
            return fretable;
        }

6. Calculate Euclidean distance between our result with normal English language letter frequency

 static Dictionary<char, double> frequencyAnalysis(string dividedfile) { 
            Dictionary < char, double > fretable = new Dictionary < char, double > ();
            double filelength = dividedfile.Length;
            for (int i = 0; i < filelength; i++)
            {
                char key = dividedfile[i];
                if (fretable.Keys.Contains(key))
                    fretable[key] = fretable[key] + 1/filelength;
                else
                    fretable[key] = 1/filelength;
            }
            return fretable;
        }

7.  Key is the candidate key with minimum Euclidean distance

时间: 02-16

Cracking The Vigenere Cipher的相关文章

CTF中那些脑洞大开的编码和加密

0x00 前言 正文开始之前先闲扯几句吧,玩CTF的小伙伴也许会遇到类似这样的问题:表哥,你知道这是什么加密吗?其实CTF中脑洞密码题(非现代加密方式)一般都是各种古典密码的变形,一般出题者会对密文进行一些处理,但是会给留一些线索,所以写此文的目的是想给小伙伴做题时给一些参考,当然常在CTF里出现的编码也可以了解一下.本来是想尽快写出参考的文章,无奈期间被各种事情耽搁导致文章断断续续写了2个月,文章肯定有许多没有提及到,欢迎小伙伴补充,总之,希望对小伙伴们有帮助吧! 0x01 目录 1 2 3

密码学基础知识(三)古典密码

说完了前面那些,想起个事,本系列依据内容主要来自<现代密码学>马春光编著.我就是学这本书的. 好了,古典密码就是古时候的密码,哈哈,逗你玩的,shannon的保密系统的通信理论发表前的都是古典密码,会在密码学简史中介绍这位牛人的. 学习古典密码学的意义:学习设计原理和分析方法 古典密码也是,俩门派:置换和代换,顾名思义,一个是换了个原来有的,一个是换了个原来没有的.学术点讲就是前者明文和密文空间一样,后者 不一样.你要是问我啥是明文空间和密文空间啊,我就呵呵.是M 和 C.m明文的集合,c密文

《Cracking the Coding Interview》——第16章:线程与锁——题目5

2014-04-27 20:16 题目:假设一个类Foo有三个公有的成员方法first().second().third().请用锁的方法来控制调用行为,使得他们的执行循序总是遵从first.second.third的顺序. 解法:你应该想到了用lock的方法类阻塞,不过这里面有个概念问题使得直接用ReentrantLock不能通过编译(对于一个锁对象,不同在A线程中锁定,又在B线程中解锁,不允许这样的归属关系),可以用Semaphore来达到相同的目的.请看下面的代码. 代码: 1 // 16

《Cracking the Coding Interview》——第16章:线程与锁——题目3

2014-04-27 19:26 题目:哲学家吃饭问题,死锁问题经典模型(专门用来黑哲学家的?). 解法:死锁四条件:1. 资源互斥.2. 请求保持.3. 非抢占.4. 循环等待.所以,某砖家拿起一只筷子后如果发现没有另一只了,就必须把手里这只筷子放下,这应该是通过破坏"请求保持"原则来防止死锁产生,请求资源失败时,连自己的资源也进一步释放,然后在下一轮里继续请求,直到成功执行. 代码: 1 // This is the class for chopsticks. 2 import j

《Cracking the Coding Interview》——第16章:线程与锁——题目2

2014-04-27 19:14 题目:如何测量上下文切换的时间? 解法:首先,上下文切换是什么,一搜就知道.对于这么一个极短的时间,要测量的话,可以通过放大N倍的方法.比如:有A和B两件事,并且经常一起发生,每件只需要花几纳秒.如果你把A事件连续做几百万次,而B时间只做了几次,这样就能排除B事件对于测量的影响.如果总时间S = mA + nB.当m >> n 时,A≈S / m.下面的测量方法类似于打乒乓球,在主线程和副线程间互相传递一个令牌,这个令牌可以是变量.管道之类的用于通信的工具.与

《Cracking the Coding Interview》——第16章:线程与锁——题目1

2014-04-27 19:09 题目:线程和进程有什么区别? 解法:理论题,操作系统教材上应该有很详细的解释.我回忆了一下,写了如下几点. 代码: 1 // 16.1 What is the difference between process and thread? 2 Answer: 3 Process: 4 1. Basic element of resource allocation in the operating system. 5 2. Possesses independent

poj 2159 D - Ancient Cipher 文件加密

Ancient Cipher Description Ancient Roman empire had a strong government system with various departments, including a secret service department. Important documents were sent between provinces and the capital in encrypted form to prevent eavesdropping

Caesars Cipher

让上帝的归上帝,凯撒的归凯撒. 下面我们来介绍风靡全球的凯撒密码Caesar cipher,又叫移位密码. 移位密码也就是密码中的字母会按照指定的数量来做移位. 一个常见的案例就是ROT13密码,字母会移位13个位置.由'A' ? 'N', 'B' ? 'O',以此类推. 写一个ROT13函数,实现输入加密字符串,输出解密字符串. 所有的字母都是大写,不要转化任何非字母形式的字符(例如:空格,标点符号),遇到这些特殊字符,跳过它们. 这是一些对你有帮助的资源: String.charCodeAt

BZOJ 1031: [JSOI2007]字符加密Cipher 后缀数组

1031: [JSOI2007]字符加密Cipher Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 6014  Solved: 2503[Submit][Status][Discuss] Description 喜欢钻研问题的JS同学,最近又迷上了对加密方法的思考.一天,他突然想出了一种他认为是终极的加密办法 :把需要加密的信息排成一圈,显然,它们有很多种不同的读法.例如下图,可以读作: JSOI07 SOI07J OI07JS I07JSO 0