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

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

Added a description for the Vigenere Autokey Analyser...

File size: 24.9 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;
26using VigenereAutokeyAnalyser;
27using System.Windows.Threading;
28using System.Threading;
29using System.Windows.Input;
30
31namespace Cryptool.Plugins.VigenereAutokeyAnalyser
32{
33    [Author("Dennis Nolte", "nolte@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
34    [PluginInfo(false, "VigenereAutokeyAnalyser", "Ciphertext-only attack on VigenereAutoKey encryption", "VigenereAutokeyAnalyser/DetailedDescription/Description.xaml", "VigenereAutokeyAnalyser/icon.png")]
35
36    public class VigenereAutokeyAnalyser : IStatistic
37    {
38        #region Private Variables
39
40        private readonly VigenereAutokeyAnalyserSettings settings;
41        private AutokeyPresentation quickWatchPresentation;         //The Quickwatch to be used
42
43        private String ciphertext = "";                             //The cipher to be analysed
44        private int modus;                                          //The modus to work with (Autokey or Vigenere)
45        private String alphabet;                                    //The alphabet to be used
46        private String key;                                         //One probable key
47        private double IC;                                          //One probable index of coincidence
48        private String completeplain;                               //One probable mixed up plaintext
49
50        private String textkorpus;                                  //Alternative to the predetermindet Frequencys in Languages
51
52        private int maxkeylength;                                   //The maximum keylength we search for
53        private int keylength;                                      //One probable keylength
54        private int assumedkeylength;                               //The keylength delivered by the autokorrelation
55        private int language;                                       //Frequencys we work with
56        private double cSofS;                                       //One probable Ciphercolumn Sum of Squares
57        private int maxfactor;                                      //One probable multiple of the keylength
58       
59        //Frequency Section
60        private double[] OF = new double[255];                      //Observed Frequency for a ciphercolumn or completeplain
61        private double[] EF;                                        //Expected Frequency due to the expected language
62
63        //Reminder Section
64        private String finalkey;                                    //The solution
65        private double finalIC;                                     //The IC for the solution
66        private double sumofsquares;                                //The Sum of Squares for the best solution
67
68        #endregion
69
70        #region Data Properties
71
72        /// <summary>
73        /// The input for the ciphertext
74        /// </summary>
75        [PropertyInfo(Direction.InputData, "Cipher Input", "Enter your cipher here", "", true, false, DisplayLevel.Beginner, QuickWatchFormat.Text, null)]
76        public String InputCipher
77        {
78            get
79            {
80                return ciphertext;
81            }
82            set
83            {
84                this.ciphertext = value;
85                OnPropertyChanged("InputCipher");
86            }
87        }
88
89        /// <summary>
90        /// The input for the textkorpus (optional)
91        /// </summary>
92        [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)]
93        public String InputKorpus
94        {
95            get
96            {
97                return textkorpus;
98            }
99            set
100            {
101                this.textkorpus = value;
102                OnPropertyChanged("InputKorpus");
103            }
104        }
105
106        /// <summary>
107        /// The assumed keylength from the autokorrelation plugin (optional)
108        /// </summary>
109        [PropertyInfo(Direction.InputData, "Keylength Input", "Enter the assumed keylength from the autokorrelationfunction here", "", false, false, DisplayLevel.Beginner, QuickWatchFormat.Text, null)]
110        public int InputKeylength
111        {
112            get
113            {
114                return assumedkeylength;
115            }
116            set
117            {
118                this.assumedkeylength = value;
119                OnPropertyChanged("InputKeylength");
120            }
121        }
122
123        /// <summary>
124        /// The output for the key
125        /// </summary>
126        [PropertyInfo(Direction.OutputData, "Key Output", "The most probable autokey for the analysed ciphertext", "", DisplayLevel.Beginner)]
127        public String OutputKey
128        {
129            get
130            {
131                return finalkey;
132            }
133            set
134            {
135                this.finalkey = value;
136                OnPropertyChanged("OutputKey");
137            }
138        }     
139
140        #endregion
141
142        #region IPlugin Members
143
144        public VigenereAutokeyAnalyser()
145        {
146            settings = new VigenereAutokeyAnalyserSettings();
147            quickWatchPresentation = new AutokeyPresentation();
148            quickWatchPresentation.SelectedIndexChanged += new MouseButtonEventHandler(quickWatchPresentation_SelectedIndexChanged);
149        }
150
151        public ISettings Settings
152        {
153            get { return settings; }
154        }
155
156        public UserControl Presentation
157        {
158            get { return quickWatchPresentation; }           
159        }
160
161        public UserControl QuickWatchPresentation
162        {
163            get { return quickWatchPresentation; }
164        }
165
166        public void PreExecution()
167        {
168        }
169
170        public void Execute()
171        {
172//START------------------------------------------------------------------------------------------------------------
173//Preparations for the Analyse-------------------------------------------------------------------------------------           
174           
175            ProgressChanged(0, 1);
176
177            quickWatchPresentation.Clear();
178           
179            alphabet = settings.AlphabetSymbols;                //initialising the alphabet as given by the user       
180
181            if (InputCipher != null)
182            {
183                ciphertext = InputCipher;                       //initialising the ciphertext
184                ciphertext = prepareForAnalyse(ciphertext);     //and prepare it for the analyse (-> see private methods section)
185            }                       
186
187            modus = settings.Modus;                             //initialise which modus is used
188            language = settings.Language;                       //initialise which language frequencys are expected
189            finalIC = 0.0;                                      //initialise the highest index of coincidence to be found among all tests
190
191            if (textkorpus != null)                             //1)  if there's a textkorpus given us it to calculate the expected frequency...
192            {                                                   //    (-> see private methods section)
193                textkorpus = prepareForAnalyse(textkorpus);
194                EF = observedFrequency(textkorpus);
195            }
196            else                                                //OR
197            {
198                EF = expectedFrequency(language);               //2) just use the expected frequency from the guessed language
199            }                                                   //    (-> see private methods section)
200
201
202//-----------------------------------------------------------------------------------------------------------------
203//Analyse----------------------------------------------------------------------------------------------------------
204//-----------------------------------------------------------------------------------------------------------------
205
206
207            if (InputKeylength != 0)                            //1) if the autokorrelation function has provided an assumed
208            {                                                   //   keylength break the AutokeyCipher with it...
209                lock (this)                                     //   IMPORTANT: This is a critical Area and has to be used by only one thread
210                {
211                    assumedkeylength = InputKeylength;
212                    breakVigenereAutoKey(assumedkeylength);
213                }
214            }
215            else                                                //OR
216            {
217                maxkeylength = (ciphertext.Length / 40) + 1;    //2) Brute force the keylength up to (ciphertext.length / 40)
218                for (int d = 1; d <= maxkeylength; d++)
219                {
220                    breakVigenereAutoKey(d);                    //"BREAK VIGENERE AUTO KEY(KEYLENGTH)" IS THE MAIN METHODE IN FINDING THE KEY FOR A GIVEN KEYLENGTH
221                }                                               //(-> see private methods section)
222            }
223
224            quickWatchPresentation.selectIndex((finalkey.Length) - 1);
225
226            OutputKey = finalkey;                               //sending the key via output
227            OnPropertyChanged("OutputKey");
228
229            ProgressChanged(1, 1);
230       
231        }
232
233//EXECUTE END------------------------------------------------------------------------------------------------------------
234
235        public void PostExecution()
236        {
237        }
238
239        public void Pause()
240        {
241        }
242
243        public void Stop()
244        {
245        }
246
247        public void Initialize()
248        {
249        }
250
251        public void Dispose()
252        {
253        }
254
255        #endregion
256
257        #region Private Methods
258
259//GET IC---------------------------------------------------------------------------------------------------------------------------------
260
261        /// <summary>
262        /// Calculate the index of coincidence which is required for the sum of squares analyse
263        /// </summary>
264        private double getIC(String completeplain)
265        {
266            OF = observedFrequency(completeplain);
267            IC = 0;
268
269            for (int x = 0; x < alphabet.Length; x++)
270            {
271                IC = IC + (OF[alphabet[x]] * OF[alphabet[x]]) / (1.0 / alphabet.Length);
272            }
273
274            return IC;
275        }
276
277
278//---------------------------------------------------------------------------------------------------------------------------------------
279//PREPARE PART---------------------------------------------------------------------------------------------------------------------------
280
281        /// <summary>
282        /// Remove spaces and symbols not provided by the alphabet from the text
283        /// </summary>
284        private String prepareForAnalyse(String c)
285        {
286            String prepared = "";
287            c = c.ToUpper();
288
289            for (int x = 0; x < c.Length; x++)
290            {
291                if (getPos(c[x]) != -1)
292                {
293                    prepared += c[x];
294                }
295            }
296
297            return prepared;
298        }
299
300
301
302//---------------------------------------------------------------------------------------------------------------------------------------
303//SUM OF SQUARES-------------------------------------------------------------------------------------------------------------------------
304
305        /// <summary>
306        /// The shifted coloumn with the least som of squares is most probable shifted by the correct letter.
307        /// This letter is part of the key we want to find
308        /// </summary>
309        private double getSumOfSquares(String c, int s)
310        {
311            String shifted = "";
312            shifted = getShift(c, s);                           //"autokey shift" the whole column by the probable key-letter
313           
314            OF = observedFrequency(shifted);                    // calculate the observed frequency of the shift
315
316            double sum = 0;
317            double help;
318
319            for (int letter = 0; letter < alphabet.Length; letter++)                        //Calculate the sum of squares
320            {
321                help = (EF[alphabet[letter]] / 100) - OF[alphabet[letter]];
322
323                sum = sum + (help * help);
324
325            }
326
327            return sum;
328        }
329
330//---------------------------------------------------------------------------------------------------------------------------------------
331//LETTER TO NUMBER----------------------------------------------------------------------------------------------------------------------
332
333        /// <summary>
334        /// Convert a the letter to an int-value that resembles his position in the given alphabet
335        /// </summary>
336        private int getPos(char c)
337        {
338            int pos = -1;
339
340            for (int i = 0; i < alphabet.Length; i++)
341            {
342                if (alphabet[i] == c)
343                {
344                    pos = i;
345                }
346            }
347            return pos;
348        }
349
350//---------------------------------------------------------------------------------------------------------------------------------------
351//SHIFT PART-----------------------------------------------------------------------------------------------------------------------------
352
353        /// <summary>
354        /// Choose the decryption rule
355        /// </summary>
356        private String getShift(String c, int s)
357        {
358            String shifted ="";
359
360            switch (modus)
361            {
362                case 0: shifted = getAutoShift(c,s);                    //1) Decrypt the column with Autokey
363                        break;
364                                                                        //OR
365                case 1: shifted = getCaesarShift(c,s);                 
366                        break;                                          //2) Decrypt the column with Normal-Vigenere
367
368                default: shifted = getAutoShift(c,s); 
369                         break;
370            }
371
372            return shifted;
373
374        }
375
376        /// <summary>
377        /// "Autokey shift" the given column by the probable key-letter
378        /// </summary>
379        private String getAutoShift(String c, int s)
380        {
381            String shifted = "";
382            int gotcha = s;
383
384            for (int x = 0; x < c.Length; x++)
385            {
386
387                gotcha = (getPos(c[x]) - gotcha + 26) % 26;
388                shifted += alphabet[gotcha];
389            }
390
391            return shifted;
392
393        }
394
395        /// <summary>
396        /// "Caesar shift" the given column by the probable key-letter (Used for the optional NORMAL-Vigenere Modus)
397        /// </summary>
398        private String getCaesarShift(String c, int s)
399        {
400            String shifted = "";
401            int gotcha = 0;
402
403            for (int x = 0; x < c.Length; x++)
404            {
405                gotcha = (getPos(c[x]) - s + 26) % 26;
406                shifted += alphabet[gotcha];
407            }
408
409            return shifted;
410
411        }
412
413
414//---------------------------------------------------------------------------------------------------------------------------------------       
415//FREQUENCY ANALYSE PHASE----------------------------------------------------------------------------------------------------------------
416
417        /// <summary>
418        /// Calculate the letter frequency of a provided text
419        /// </summary>
420        private double[] observedFrequency(String c)
421        {
422            double[] book = new double[255];                   //book resembles an ASCII Table and remembers a symbol with his ASCII value
423
424            //count the symbols and add 1 in their ASCII Position
425            for (int x = 0; x < c.Length; x++) 
426            {
427                book[(int)c[x]]++;
428            }
429
430            //calculate the frequency by dividing through the textlength
431            for (int y = 0; y < book.Length; y++) 
432            {
433                book[y] = book[y] / c.Length;
434            }
435
436            return book;
437        }
438
439
440        /// <summary>
441        /// Set the expected letter frequency of a language
442        /// </summary>
443        private double[] expectedFrequency(int l)
444        {
445            double[] book = new double[255];                   //"ASCII-book" remembers the alphabet letters
446            double[] languagefrequency;
447
448            //switch to the expected language and set its frequency
449            switch (l)
450            {
451                case 0: //English
452                    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 };
453                    break;
454                case 1: //German
455                    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 };
456                    break;
457                case 2: //French
458                    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 };
459                    break;
460                case 3: //Spain
461                    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 };
462                    break;
463                default: //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            }
467
468            //set the frequency for the letters in the alphabet
469            for (int c = 0; c < 26; c++)
470            {
471                book[(int)alphabet[c]] = languagefrequency[c];
472            }
473
474            return book;
475        }
476
477//-----------------------------------------------------------------------------------------------------------------------------------------     
478//QUICKWATCH PART--------------------------------------------------------------------------------------------------------------------------
479
480        /// <summary>
481        /// Show the results in the Presentation
482        /// </summary>
483        private void showResult(String key, double IC)
484        {
485                ResultEntry entry = new ResultEntry();
486                entry.Key = key;
487                entry.IC = IC.ToString();
488
489                quickWatchPresentation.Add(entry);
490        }
491
492//-----------------------------------------------------------------------------------------------------------------------------------------
493//PRESENTATION UPDATE----------------------------------------------------------------------------------------------------------------------
494
495        void quickWatchPresentation_SelectedIndexChanged(object sender, MouseButtonEventArgs e)
496        {
497            ListView lv = sender as ListView;
498            if (lv != null)
499            {
500                ResultEntry rse = lv.SelectedItem as ResultEntry;
501
502                if (rse != null)
503                {
504                    OutputKey = rse.Key;
505                    OnPropertyChanged("OutputKey");
506                }
507            }
508        }
509
510//-----------------------------------------------------------------------------------------------------------------------------------------
511//CALCULATION PART: BREAKAUTOKEY METHODE (MOST IMPORTANT METHODE)--------------------------------------------------------------------------
512
513        /// <summary>
514        /// Find the key for a given keylength using "Least Sum of Squares" attack
515        /// </summary>
516        private void breakVigenereAutoKey(int d)
517        {
518                completeplain = "";                             //initialising completeplain,
519                key = "";                                       //key,
520                keylength = d;                                  //keylength
521                maxfactor = ciphertext.Length / keylength;      //and maxfactor
522
523                //for all coloumns in a possible keylength
524                for (int column = 0; column < keylength; column++)
525                {
526                    String ciphercolumn = "";                   //coloumn is reseted
527                    char probablekeychar = 'A';                 //probablekeychar is reseted
528                    sumofsquares = 99999999999.99999999999;     //the sum of squares is reseted
529
530                    //A new coloumns is calculated through  c1 , c1 + d , c1 + 2d , c1 + 3d etc.
531                    for (int i = 0; i <= maxfactor; i++)
532                    {
533                        if (column + i * keylength < ciphertext.Length)
534                        {
535                            ciphercolumn += ciphertext[column + i * keylength];
536                        }
537                    }
538
539                    ciphercolumn = ciphercolumn.ToUpper();
540
541                    //for this coloumn the Sum Of Squares is calculated for each shift key...
542                    for (int shift = 0; shift < alphabet.Length; shift++)
543                    {
544                        cSofS = getSumOfSquares(ciphercolumn, shift);
545
546                        //...and compared so the correct one having the least sum can be found
547                        if (cSofS < sumofsquares)
548                        {
549                            sumofsquares = cSofS;
550                            probablekeychar = alphabet[shift];
551                        }
552
553
554                    }
555
556                    completeplain += getShift(ciphercolumn, getPos(probablekeychar)); //remembers a decrypted cipher
557                    key += probablekeychar;                                           //remembers the probable key letter of this decryption
558
559                }
560
561                IC = getIC(completeplain);                              //calculate the IC(index of coincidence)
562                showResult(key, IC);                                    //show the results
563                                               
564                //the decrypted cipher with the highest index of coincidence was decrypted with the correct key
565                if (IC > finalIC)
566                {
567                    finalIC = IC;                                       //remember the IC
568                    finalkey = key;                                     //remember the key                                     
569                }
570
571                ProgressChanged((((double)d) / maxkeylength), 1);       
572        }
573
574//-----------------------------------------------------------------------------------------------------------------------------------------       
575
576        #endregion
577
578        #region Event Handling
579
580        public event StatusChangedEventHandler OnPluginStatusChanged;
581
582        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
583
584        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
585
586        public event PropertyChangedEventHandler PropertyChanged;
587
588        private void GuiLogMessage(string message, NotificationLevel logLevel)
589        {
590            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(message, this, logLevel));
591        }
592
593        private void OnPropertyChanged(string name)
594        {
595            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
596        }
597
598        private void ProgressChanged(double value, double max)
599        {
600            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
601        }
602
603        #endregion
604    }
605}
Note: See TracBrowser for help on using the repository browser.