source: trunk/CrypPlugins/AutokorrelationFunction/AutokorrelationFunction.cs @ 1697

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

Created a description for the autocorrelation function.

File size: 12.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 System.Windows.Media;
27using Cryptool.PluginBase.Utils.Graphics.Diagrams.Histogram;
28
29namespace Cryptool.Plugins.AutokorrelationFunction
30{
31    [Author("Dennis Nolte", "nolte@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
32    [PluginInfo(false, "AutokorrelationFunction", "Calculates the Autokorrelation of a cipher", "AutokorrelationFunction/DetailedDescription/Description.xaml", "AutokorrelationFunction/icon.png")]
33
34    public class AutokorrelationFunction : IStatistic
35    {
36        #region Private Variables
37
38        private readonly AutokorrelationFunctionSettings settings;
39        private AutocorrelationPresentation presentation;
40
41        private String cipher = "";                                     //The cipher to be analysed
42        private int probablelength = 0;                                 //estimated keylength
43        private double probablekorr = -999999.999999;                   //initialized probable korrelation of the length
44        private String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";         //used alphabet
45        private double same;                                            //Found same letter counter
46        private double average;                                         //Holds the average value of the found matches
47        private double[] ak;                                            // Autokorrelation Values
48        private double[] top;
49        private HistogramElement bar;                                   
50        private HistogramDataSource data;
51
52        #endregion
53
54        #region Data Properties
55
56        /// <summary>
57        /// The input for the ciphertext
58        /// </summary>
59        [PropertyInfo(Direction.InputData, "Cipher Input", "Enter your cipher here", "", true, false, DisplayLevel.Beginner, QuickWatchFormat.Text, null)]
60        public String InputCipher
61        {
62            get
63            {
64                return cipher;
65            }
66            set
67            {
68                this.cipher = value;
69                OnPropertyChanged("InputCipher");
70            }
71        }
72
73        /// <summary>
74        /// The output for the found shift value (most probable keylength)
75        /// </summary>
76        [PropertyInfo(Direction.OutputData, "Keylength Output", "The most probable keylength for the analysed ciphertext", "", DisplayLevel.Beginner)]
77        public int OutputLength
78        {
79            get
80            {
81                return probablelength;
82            }
83            set
84            {
85                this.probablelength = value;
86                OnPropertyChanged("OutputLength");
87            }
88        }
89
90        #endregion
91
92        #region IPlugin Members
93
94        public AutokorrelationFunction()
95        {
96            settings = new AutokorrelationFunctionSettings();
97            presentation = new AutocorrelationPresentation();
98            HistogramElement bar = new HistogramElement(0, 0, "");
99            data = new HistogramDataSource();
100
101        }
102        public ISettings Settings
103        {
104            get { return settings; }
105        }
106
107        public UserControl Presentation
108        {
109            get { return presentation; }
110        }
111
112        public UserControl QuickWatchPresentation
113        {
114            get { return presentation; }
115        }
116
117        public void PreExecution()
118        {
119        }
120
121        public void Execute()
122        {
123
124//START------------------------------------------------------------------------------------------------------------
125//Preparations for the Analyse-------------------------------------------------------------------------------------
126           
127            ProgressChanged(0, 1);
128
129            cipher = InputCipher;                               //initialising the ciphertext
130            cipher = prepareForAnalyse(cipher);                 //and prepare it for the analyse (-> see private methods section)
131
132            ak = new double[cipher.Length];                     //initialise ak[]...there are n possible shifts where n is cipher.length
133
134            presentation.histogram.SetBackground(Brushes.Beige);              //sets the background colour for the quickwatch
135            presentation.histogram.SetHeadline("Autocorrelation matches");    //sets its title
136
137//-----------------------------------------------------------------------------------------------------------------
138//Analyse----------------------------------------------------------------------------------------------------------
139//-----------------------------------------------------------------------------------------------------------------             
140
141            //for each possible shift value...
142                    for(int t=0; t<cipher.Length; t++)
143                    {
144                            same=0;
145                       
146                //...calculate how often the letters match...
147                            for(int x=0; x<cipher.Length-t;x++)
148                            {
149                                    if(cipher[x] == cipher[x+t])
150                                    {
151                                            same++;
152                                    }
153                            }
154
155                try
156                {
157                    //...and save the count for the matches at the shift position
158                    ak[t] = same;
159                }
160                catch
161                {
162                }
163                    }
164
165            average = averageMatch(ak);                         //find the average value of matches
166            data.ValueCollection.Clear();
167
168            //for all observed shifts...
169                    for(int y=1;y<ak.Length;y++)
170                    {             
171                //find the one with the highest match count...
172                            if(ak[y] > probablekorr)
173                            {
174                                    probablekorr = ak[y];
175                    probablelength = y;                 //...and remember this shift value
176                            }
177                    }
178
179            //find the top 13 matches...
180            if (ak.Length > 11)
181            {
182                ak = findTopThirteen(ak);
183            }
184
185            for (int y = 1; y < ak.Length; y++)
186            {
187                if (ak[y] > -1)                         //Adds a bar into the presentation if it is higher then the average matches
188                {
189                    bar = new HistogramElement(ak[y], ak[y], "" + y);
190                    data.ValueCollection.Add(bar);
191                }
192            }
193
194            presentation.histogram.SetHeadline("Highest match count " + probablekorr + " with shift: " + probablelength);
195
196            if(data != null)
197            {
198                presentation.histogram.ShowData(data);
199            }
200
201            OutputLength = probablelength;              //sending the keylength via output
202            OnPropertyChanged("OutputLength");         
203                   
204
205
206            ProgressChanged(1, 1);
207
208//EXECUTE END------------------------------------------------------------------------------------------------------
209       
210        }
211
212        public void PostExecution()
213        {
214        }
215
216        public void Pause()
217        {
218        }
219
220        public void Stop()
221        {
222            presentation.histogram.SetBackground(Brushes.LightGray);
223        }
224
225        public void Initialize()
226        {
227        }
228
229        public void Dispose()
230        {
231        }
232
233        #endregion
234
235        #region Private Methods
236
237//PREPARE PART---------------------------------------------------------------------------------------------------------------------------
238
239        /// <summary>
240        /// Remove spaces and symbols not provided by the alphabet from the text
241        /// </summary>
242        private String prepareForAnalyse(String c)
243        {
244            String prepared = "";
245
246            c = c.ToUpper();
247
248            for (int x = 0; x < c.Length; x++)
249            {
250                if (getPos(c[x]) != -1)
251                {
252                    prepared = prepared + c[x];
253                }
254            }
255            return prepared;
256        }
257
258
259//---------------------------------------------------------------------------------------------------------------------------------------
260//LETTER TO NUMBER----------------------------------------------------------------------------------------------------------------------
261
262        /// <summary>
263        /// Convert a the letter to an int-value that resembles his position in the given alphabet
264        /// </summary>
265        private int getPos(char c)
266        {
267            int pos = -1;
268            for (int i = 0; i < alphabet.Length; i++)
269            {
270                if (alphabet[i] == c)
271                {
272                    pos = i;
273                }
274            }
275            return pos;
276        }
277
278
279//---------------------------------------------------------------------------------------------------------------------------------------
280//AVERAGE MATCHES COUNT------------------------------------------------------------------------------------------------------------------
281
282        /// <summary>
283        /// Calculates the average value for all matches in the autokorrelation
284        /// </summary>
285        private double averageMatch(double[] ak)
286        {
287            double average = 0;
288
289            for (int y = 0; y < ak.Length; y++)
290            {
291                average += ak[y];
292            }
293
294            average = average / ak.Length;
295
296            return average;
297        }
298
299//---------------------------------------------------------------------------------------------------------------------------------------
300//FIND TOP 13----------------------------------------------------------------------------------------------------------------------------
301
302        private double[] findTopThirteen(double[] ak)
303        {
304            double[] top = ak;
305            int thrownaway = 0;
306
307            for(int match=0; match < probablekorr; match++)
308            {
309                for(int x=0;x<ak.Length;x++)
310                {
311                    if(top[x] == match)
312                    {
313                        top[x] = -1;
314                        thrownaway++;
315                    }
316                    if(thrownaway == (ak.Length)-13)
317                    {
318                        return top;
319                    }
320
321                }
322            }
323            return top;
324        }
325
326
327
328
329
330//---------------------------------------------------------------------------------------------------------------------------------------
331
332        #endregion
333
334        #region Event Handling
335
336        public event StatusChangedEventHandler OnPluginStatusChanged;
337
338        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
339
340        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
341
342        public event PropertyChangedEventHandler PropertyChanged;
343
344        private void GuiLogMessage(string message, NotificationLevel logLevel)
345        {
346            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(message, this, logLevel));
347        }
348
349        private void OnPropertyChanged(string name)
350        {
351            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
352        }
353
354        private void ProgressChanged(double value, double max)
355        {
356            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
357        }
358
359        #endregion
360    }
361}
Note: See TracBrowser for help on using the repository browser.