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

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

Enhanced the VigenereAutokeyAnalyser with a Presentation

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