source: trunk/CrypPlugins/VigenereAutokeyAnalyser/VigenereAutokeyAnalyser.cs @ 1644

Last change on this file since 1644 was 1644, checked in by nolte, 12 years ago

added a report output to visualize all found keys

File size: 23.4 KB
Line 
1/* HOWTO: Change year, author name and organization.
2   Copyright 2010 Your Name, University of Duckburg
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16using System;
17using System.Collections.Generic;
18using System.Linq;
19using System.Text;
20using Cryptool.PluginBase;
21using System.ComponentModel;
22using Cryptool.PluginBase.IO;
23using Cryptool.PluginBase.Miscellaneous;
24using System.Windows.Controls;
25using Cryptool.PluginBase.Analysis;
26
27namespace Cryptool.Plugins.VigenereAutokeyAnalyser
28{
29    [Author("Dennis Nolte", "nolte@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
30    [PluginInfo(false, "VigenereAutokeyAnalyser", "Ciphertext-only attack on VigenereAutoKey encryption", null, "VigenereAutokeyAnalyser/icon.png")]
31
32    public class VigenereAutokeyAnalyser : IStatistic
33    {
34        #region Private Variables
35
36        private readonly VigenereAutokeyAnalyserSettings settings = new VigenereAutokeyAnalyserSettings();
37        private String ciphertext = "";                             //The cipher to be analysed
38        private int modus;                                          //The modus to work with (Autokey or Vigenere)
39        private String alphabet;                                    //The alphabet to be used
40        private String key;                                         //One probable key
41        private double IC;                                          //One probable index of coincidence
42        private String completeplain;                               //One probable mixed up plaintext
43
44        private String textkorpus;                                  //Alternative to the predetermindet Frequencys in Languages
45        private String report = "";                                 //A report of all analysed keys (Optional output string)
46
47        private int maxkeylength;                                   //The maximum keylength we search for
48        private int keylength;                                      //One probable keylength
49        private int assumedkeylength;                               //The keylength delivered by the autokorrelation
50        private int language;                                       //Frequencys we work with
51        private double cSofS;                                       //One probable Ciphercolumn Sum of Squares
52        private int maxfactor;                                      //One probable multiple of the keylength
53       
54        //Frequency Section
55        private double[] OF = new double[255];                      //Observed Frequency for a ciphercolumn or completeplain
56        private double[] EF;                                        //Expected Frequency due to the expected language
57
58        //Reminder Section
59        private String finalkey;                                    //The solution
60        private double finalIC;                                     //The IC for the solution
61        private double sumofsquares;                                //The Sum of Squares for the best solution
62
63        #endregion
64
65        #region Data Properties
66
67        /// <summary>
68        /// The input for the ciphertext
69        /// </summary>
70        [PropertyInfo(Direction.InputData, "Cipher Input", "Enter your cipher here", "", true, false, DisplayLevel.Beginner, QuickWatchFormat.Text, null)]
71        public String InputCipher
72        {
73            get
74            {
75                return ciphertext;
76            }
77            set
78            {
79                this.ciphertext = value;
80                OnPropertyChanged("InputCipher");
81            }
82        }
83
84        /// <summary>
85        /// The input for the textkorpus (optional)
86        /// </summary>
87        [PropertyInfo(Direction.InputData, "Textkorpus Input", "Enter your sample text here or choose a language from the task-pane", "", false, false, DisplayLevel.Beginner, QuickWatchFormat.Text, null)]
88        public String InputKorpus
89        {
90            get
91            {
92                return textkorpus;
93            }
94            set
95            {
96                this.textkorpus = value;
97                OnPropertyChanged("InputKorpus");
98            }
99        }
100
101        /// <summary>
102        /// The assumed keylength from the autokorrelation plugin (optional)
103        /// </summary>
104        [PropertyInfo(Direction.InputData, "Keylength Input", "Enter the assumed keylength from the autokorrelationfunction here", "", false, false, DisplayLevel.Beginner, QuickWatchFormat.Text, null)]
105        public int InputKeylength
106        {
107            get
108            {
109                return assumedkeylength;
110            }
111            set
112            {
113                this.assumedkeylength = value;
114                OnPropertyChanged("InputKeylength");
115            }
116        }
117
118        /// <summary>
119        /// The output for the key
120        /// </summary>
121        [PropertyInfo(Direction.OutputData, "Key Output", "The most probable autokey for the analysed ciphertext", "", DisplayLevel.Beginner)]
122        public String OutputKey
123        {
124            get
125            {
126                return finalkey;
127            }
128            set
129            {
130                this.finalkey = value;
131                OnPropertyChanged("OutputKey");
132            }
133        }
134
135        /// <summary>
136        /// The output for the statistic
137        /// </summary>
138        [PropertyInfo(Direction.OutputData, "Report Output", "A text with all analysed keys and their IC values", "", DisplayLevel.Beginner)]
139        public String OutputStatistic
140        {
141            get
142            {
143                return report;
144            }
145            set
146            {
147                this.report = value;
148                OnPropertyChanged("OutputStatistic");
149            }
150        }
151
152        #endregion
153
154        #region IPlugin Members
155
156        public ISettings Settings
157        {
158            get { return settings; }
159        }
160
161        public UserControl Presentation
162        {
163            get { return null; }
164        }
165
166        public UserControl QuickWatchPresentation
167        {
168            get { return null; }
169        }
170
171        public void PreExecution()
172        {
173        }
174
175        public void Execute()
176        {
177//START------------------------------------------------------------------------------------------------------------
178//Preparations for the Analyse-------------------------------------------------------------------------------------           
179           
180            ProgressChanged(0, 1);
181
182            alphabet = settings.AlphabetSymbols;                //initialising the alphabet as given by the user       
183
184            if (InputCipher != null)
185            {
186                ciphertext = InputCipher;                       //initialising the ciphertext
187                ciphertext = prepareForAnalyse(ciphertext);     //and prepare it for the analyse (-> see private methods section)
188            }
189           
190
191            report = "The analysed key(s) and their IC(s): \n"; //initialise the headline of the report
192
193            modus = settings.Modus;                             //initialise which modus is used
194            language = settings.Language;                       //initialise which language frequencys are expected
195
196            finalIC = 0.0;                                      //initialise the highest index of coincidence to be found among all tests
197
198            if (textkorpus != null)                             //1)  if there's a textkorpus given us it to calculate the expected frequency...
199            {                                                   //    (-> see private methods section)
200                textkorpus = prepareForAnalyse(textkorpus);
201                EF = observedFrequency(textkorpus);
202            }
203            else                                                //OR
204            {
205                EF = expectedFrequency(language);               //2) just use the expected frequency from the guessed language
206            }                                                   //    (-> see private methods section)
207
208
209
210
211//-----------------------------------------------------------------------------------------------------------------
212//Analyse----------------------------------------------------------------------------------------------------------
213//-----------------------------------------------------------------------------------------------------------------
214
215
216            if (InputKeylength != 0)                            //1) if the autokorrelation function has provided an assumed
217            {                                                   //   keylength break the AutokeyCipher with it...
218                assumedkeylength = InputKeylength;
219                breakVigenereAutoKey(assumedkeylength);
220            }
221            else                                                //OR
222            {
223                maxkeylength = (ciphertext.Length / 40) + 1;    //2) Brute force the keylength up to (ciphertext.length / 40)
224                for (int d = 1; d <= maxkeylength; d++)
225                {
226                    breakVigenereAutoKey(d);                    //"BREAK VIGENERE AUTO KEY(KEYLENGTH)" IS THE MAIN METHODE IN FINDING THE KEY FOR A GIVEN KEYLENGTH
227                }                                               //(-> see private methods section)
228            } 
229           
230           
231
232            OutputKey = finalkey;                               //sending the key via output
233            OnPropertyChanged("OutputKey");
234
235            OutputStatistic = report;
236            OnPropertyChanged("OutputStatistic");
237
238            ProgressChanged(1, 1);
239       
240        }
241
242//EXECUTE END------------------------------------------------------------------------------------------------------
243
244        public void PostExecution()
245        {
246        }
247
248        public void Pause()
249        {
250        }
251
252        public void Stop()
253        {
254        }
255
256        public void Initialize()
257        {
258        }
259
260        public void Dispose()
261        {
262        }
263
264        #endregion
265
266        #region Private Methods
267
268//GET IC---------------------------------------------------------------------------------------------------------------------------------
269
270        /// <summary>
271        /// Calculate the index of coincidence which is required for the sum of squares analyse
272        /// </summary>
273        private double getIC(String completeplain)
274        {
275            OF = observedFrequency(completeplain);
276            IC = 0;
277
278            for (int x = 0; x < alphabet.Length; x++)
279            {
280                IC = IC + (OF[alphabet[x]] * OF[alphabet[x]]) / (1.0 / alphabet.Length);
281            }
282
283
284            return IC;
285        }
286
287
288//---------------------------------------------------------------------------------------------------------------------------------------
289//PREPARE PART---------------------------------------------------------------------------------------------------------------------------
290
291        /// <summary>
292        /// Remove spaces and symbols not provided by the alphabet from the text
293        /// </summary>
294        private String prepareForAnalyse(String c)
295        {
296            String prepared = "";
297
298            c = c.ToUpper();
299
300            for (int x = 0; x < c.Length; x++)
301            {
302                if (getPos(c[x]) != -1)
303                {
304                    prepared += c[x];
305                }
306            }
307            return prepared;
308        }
309
310
311
312//---------------------------------------------------------------------------------------------------------------------------------------
313//SUM OF SQUARES-------------------------------------------------------------------------------------------------------------------------
314
315        /// <summary>
316        /// The shifted coloumn with the least som of squares is most probable shifted by the correct letter.
317        /// This letter is part of the key we want to find
318        /// </summary>
319        private double getSumOfSquares(String c, int s)
320        {
321            String shifted = "";
322            shifted = getShift(c, s);                           //"autokey shift" the whole column by the probable key-letter
323
324           
325            OF = observedFrequency(shifted);                    // calculate the observed frequency of the shift
326
327
328            double sum = 0;
329            double help;
330
331            for (int letter = 0; letter < alphabet.Length; letter++)                        //Calculate the sum of squares
332            {
333                help = (EF[alphabet[letter]] / 100) - OF[alphabet[letter]];
334
335                sum = sum + (help * help);
336
337            }
338
339            return sum;
340        }
341
342//---------------------------------------------------------------------------------------------------------------------------------------
343//LETTER TO NUMBER----------------------------------------------------------------------------------------------------------------------
344
345        /// <summary>
346        /// Convert a the letter to an int-value that resembles his position in the given alphabet
347        /// </summary>
348        private int getPos(char c)
349        {
350            int pos = -1;
351            for (int i = 0; i < alphabet.Length; i++)
352            {
353                if (alphabet[i] == c)
354                {
355                    pos = i;
356                }
357            }
358            return pos;
359        }
360
361//---------------------------------------------------------------------------------------------------------------------------------------
362//SHIFT PART-----------------------------------------------------------------------------------------------------------------------------
363
364        /// <summary>
365        /// Choose the decryption rule
366        /// </summary>
367        private String getShift(String c, int s)
368        {
369            String shifted ="";
370
371            switch (modus)
372            {
373                case 0: shifted = getAutoShift(c,s);                    //1) Decrypt the column with Autokey
374                        break;
375                                                                        //OR
376                case 1: shifted = getCaesarShift(c,s);                 
377                        break;                                          //2) Decrypt the column with Normal-Vigenere
378
379                default: shifted = getAutoShift(c,s); 
380                         break;
381            }
382
383            return shifted;
384
385        }
386
387        /// <summary>
388        /// "Autokey shift" the given column by the probable key-letter
389        /// </summary>
390        private String getAutoShift(String c, int s)
391        {
392            String shifted = "";
393            int gotcha = s;
394
395            for (int x = 0; x < c.Length; x++)
396            {
397
398                gotcha = (getPos(c[x]) - gotcha + 26) % 26;
399                shifted += alphabet[gotcha];
400            }
401
402            return shifted;
403
404        }
405
406        /// <summary>
407        /// "Caesar shift" the given column by the probable key-letter (Used for the optional NORMAL-Vigenere Modus)
408        /// </summary>
409        private String getCaesarShift(String c, int s)
410        {
411            String shifted = "";
412            int gotcha = 0;
413
414            for (int x = 0; x < c.Length; x++)
415            {
416
417                gotcha = (getPos(c[x]) - s + 26) % 26;
418                shifted += alphabet[gotcha];
419            }
420
421            return shifted;
422
423        }
424
425
426//---------------------------------------------------------------------------------------------------------------------------------------       
427//FREQUENCY ANALYSE PHASE----------------------------------------------------------------------------------------------------------------
428
429        /// <summary>
430        /// Calculate the letter frequency of a provided text
431        /// </summary>
432        private double[] observedFrequency(String c)
433        {
434            double[] book = new double[255];                   //book resembles an ASCII Table and remembers a symbol with his ASCII value
435
436            //count the symbols and add 1 in their ASCII Position
437            for (int x = 0; x < c.Length; x++) 
438            {
439                book[(int)c[x]]++;
440            }
441
442            //calculate the frequency by dividing through the textlength
443            for (int y = 0; y < book.Length; y++) 
444            {
445                book[y] = book[y] / c.Length;
446            }
447
448            return book;
449        }
450
451
452        /// <summary>
453        /// Set the expected letter frequency of a language
454        /// </summary>
455        private double[] expectedFrequency(int l)
456        {
457            double[] book = new double[255];                   //"ASCII-book" remembers the alphabet letters
458            double[] languagefrequency;
459
460            //switch to the expected language and set its frequency
461            switch (l)
462            {
463                case 0: //English
464                    languagefrequency = new double[] { 8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 6.094, 6.966, 0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929, 0.095, 5.987, 6.327, 9.056, 2.758, 0.978, 2.360, 0.150, 1.974, 0.074 };
465                    break;
466                case 1: //German
467                    languagefrequency = new double[] { 6.51, 1.89, 3.06, 5.08, 17.40, 1.66, 3.01, 4.76, 7.55, 0.27, 1.21, 3.44, 2.53, 9.78, 2.51, 0.79, 0.02, 7.00, 7.27, 6.15, 4.35, 0.67, 1.89, 0.03, 0.04, 1.13 };
468                    break;
469                case 2: //French
470                    languagefrequency = new double[] { 7.636, 0.901, 3.260, 3.669, 14.715, 1.066, 0.866, 0.737, 7.529, 0.545, 0.049, 5.456, 2.968, 7.095, 5.378, 3.021, 1.362, 6.553, 7.948, 7.244, 6.311, 1.628, 0.114, 0.387, 0.308, 0.136 };
471                    break;
472                case 3: //Spain
473                    languagefrequency = new double[] { 12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, 0.70, 6.25, 0.44, 0.01, 4.97, 3.15, 6.71, 8.68, 2.51, 0.88, 6.87, 7.98, 4.63, 3.93, 0.90, 0.02, 0.22, 0.90, 0.52 };
474                    break;
475                default: //English
476                    languagefrequency = new double[] { 8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 6.094, 6.966, 0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929, 0.095, 5.987, 6.327, 9.056, 2.758, 0.978, 2.360, 0.150, 1.974, 0.074 };
477                    break;
478            }
479
480            //set the frequency for the letters in the alphabet
481            for (int c = 0; c < 26; c++)
482            {
483                book[(int)alphabet[c]] = languagefrequency[c];
484            }
485
486            return book;
487        }
488
489
490//-----------------------------------------------------------------------------------------------------------------------------------------
491//CALCULATION PART: BREAKAUTOKEY METHODE (MOST IMPORTANT METHODE)--------------------------------------------------------------------------
492
493        /// <summary>
494        /// Find the key for a given keylength using "Least Sum of Squares" attack
495        /// </summary>
496        private void breakVigenereAutoKey(int d)
497        {
498                completeplain = "";                             //initialising completeplain,
499                key = "";                                       //key,
500                keylength = d;                                  //keylength
501                maxfactor = ciphertext.Length / keylength;      //and maxfactor
502
503                //for all coloumns in a possible keylength
504                for (int column = 0; column < keylength; column++)
505                {
506                    String ciphercolumn = "";                   //coloumn is reseted
507                    char probablekeychar = 'A';                 //probablekeychar is reseted
508                    sumofsquares = 99999999999.99999999999;     //the sum of squares is reseted
509
510                    //A new coloumns is calculated through  c1 , c1 + d , c1 + 2d , c1 + 3d etc.
511                    for (int i = 0; i <= maxfactor; i++)
512                    {
513                        if (column + i * keylength < ciphertext.Length)
514                        {
515                            ciphercolumn += ciphertext[column + i * keylength];
516                        }
517                    }
518
519                    ciphercolumn = ciphercolumn.ToUpper();
520
521                    //for this coloumn the Sum Of Squares is calculated for each shift key...
522                    for (int shift = 0; shift < alphabet.Length; shift++)
523                    {
524                        cSofS = getSumOfSquares(ciphercolumn, shift);
525
526                        //...and compared so the correct one having the least sum can be found
527                        if (cSofS < sumofsquares)
528                        {
529                            sumofsquares = cSofS;
530                            probablekeychar = alphabet[shift];
531                        }
532
533
534                    }
535
536                    completeplain += getShift(ciphercolumn, getPos(probablekeychar)); //remembers a decrypted cipher
537                    key += probablekeychar;                                           //remembers the probable key letter of this decryption
538
539                }
540
541
542                IC = getIC(completeplain);                              //calculate the IC(index of coincidence)
543
544                report += key + " : " + IC + "\n";                      //the report               
545
546                //the decrypted cipher with the highest index of coincidence was decrypted with the correct key
547                if (IC > finalIC)
548                {
549                    finalIC = IC;                                       //remember the IC
550                    finalkey = key;                                     //remember the key
551                }
552
553                ProgressChanged((((double)d) / maxkeylength), 1);       
554        }
555
556//-----------------------------------------------------------------------------------------------------------------------------------------
557 
558       
559       
560        #endregion
561
562        #region Event Handling
563
564        public event StatusChangedEventHandler OnPluginStatusChanged;
565
566        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
567
568        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
569
570        public event PropertyChangedEventHandler PropertyChanged;
571
572        private void GuiLogMessage(string message, NotificationLevel logLevel)
573        {
574            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(message, this, logLevel));
575        }
576
577        private void OnPropertyChanged(string name)
578        {
579            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
580        }
581
582        private void ProgressChanged(double value, double max)
583        {
584            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
585        }
586
587        #endregion
588    }
589}
Note: See TracBrowser for help on using the repository browser.