source: trunk/CrypPlugins/KeySearcher/KeySearcher.cs @ 793

Last change on this file since 793 was 793, checked in by kopal, 12 years ago

KeySearcher - some small speed optimizations

File size: 20.4 KB
Line 
1using System;
2using System.Linq;
3using System.Text;
4using Cryptool.PluginBase.Analysis;
5using Cryptool.PluginBase;
6using System.Windows.Controls;
7using System.ComponentModel;
8using Cryptool.PluginBase.Control;
9using System.Collections;
10using System.Collections.Generic;
11using System.Threading;
12using System.Windows.Threading;
13
14namespace KeySearcher
15{
16    public class KeyPattern
17    {
18        private class Wildcard
19        {
20            private char[] values = new char[256];
21            private int length;
22            private int counter;
23           
24            public Wildcard(string valuePattern)
25            {               
26                counter = 0;
27                length = 0;
28                int i = 1;
29                while (valuePattern[i] != ']')
30                {
31                    if (valuePattern[i + 1] == '-')
32                    {
33                        for (char c = valuePattern[i]; c <= valuePattern[i + 2]; c++)
34                            values[length++] = c;
35                        i += 2;
36                    }
37                    else
38                        values[length++] = valuePattern[i];
39                    i++;
40                }
41            }
42
43            public char getChar()
44            {               
45                return (char)values[counter];
46            }
47
48            public bool succ()
49            {
50                counter++;
51                if (counter >= length)
52                {
53                    counter = 0;
54                    return true;
55                }
56                return false;
57            }
58
59            public int Size()
60            {
61                return length;
62            }
63
64        }
65
66        private string pattern;
67        private string key;       
68        private ArrayList wildcardList;
69
70        public KeyPattern(string pattern)
71        {
72            this.pattern = pattern;
73        }
74
75        public string giveWildcardKey()
76        {
77            string res = "";
78            int i = 0;
79            while (i < pattern.Length)
80            {
81                if (pattern[i] != '[')
82                    res += pattern[i];
83                else
84                {
85                    res += '*';
86                    while (pattern[i] != ']')
87                        i++;
88                }
89                i++;
90            }
91            return res;
92        }
93
94        public bool testKey(string key)
95        {
96            int kcount = 0;
97            int pcount = 0;
98            while (kcount < key.Length && pcount < pattern.Length)
99            {
100                if (pattern[pcount] != '[')
101                {
102                    if (key[kcount] != '*' && pattern[pcount] != key[kcount])
103                        return false;
104                    kcount++;
105                    pcount++;
106                }
107                else
108                {
109                    bool contains = false;
110                    pcount++;
111                    while (pattern[pcount] != ']')
112                    {
113                        if (key[kcount] != '*')
114                        {
115                            if (pattern[pcount + 1] == '-')
116                            {
117                                if (key[kcount] >= pattern[pcount] && key[kcount] <= pattern[pcount + 2])
118                                    contains = true;
119                                pcount += 2;
120                            }
121                            else
122                                if (pattern[pcount] == key[kcount])
123                                    contains = true;
124                        }
125                        pcount++;
126                    }
127                    if (!contains && !(key[kcount] == '*'))
128                        return false;
129                    kcount++;
130                    pcount++;
131                }               
132            }
133            if (pcount != pattern.Length || kcount != key.Length)
134                return false;
135            return true;
136        }
137
138        public double initKeyIteration(string key)
139        {
140            double counter = 1;
141            this.key = key;
142            int pcount = 0;
143            wildcardList = new ArrayList();
144            for (int i = 0; i < key.Length; i++)
145            {
146                if (key[i] == '*')
147                {
148                    Wildcard wc = new Wildcard(pattern.Substring(pcount, pattern.IndexOf(']', pcount) + 1 - pcount));
149                    wildcardList.Add(wc);
150                    counter *= wc.Size();
151                }
152
153                if (pattern[pcount] == '[')
154                    while (pattern[pcount] != ']')
155                        pcount++;
156                pcount++;
157            }
158            return counter;
159        }
160
161        public bool nextKey()
162        {
163            int wildcardCount = wildcardList.Count-1;
164            bool overflow = ((Wildcard)wildcardList[wildcardCount]).succ();
165            wildcardCount--;
166            while (overflow && (wildcardCount >= 0))
167                overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
168            return !overflow;
169        }
170
171        public string getKey()
172        {
173            string res = "";
174            int wildcardCount = 0;
175            for (int i = 0; i < key.Length; i++)
176            {
177                if (key[i] != '*')
178                    res += key[i];
179                else
180                {
181                    Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
182                    res += wc.getChar();
183                }
184            }
185            return res;
186        }
187    }
188   
189    [Author("Thomas Schmid", "thomas.schmid@cryptool.org", "Uni Siegen", "http://www.uni-siegen.de")]
190    //[Author("Sven Rech", "rech@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
191    [PluginInfo(true, "KeySearcher", "Bruteforces a decryption algorithm.", null, "KeySearcher/Images/icon.png")]
192    public class KeySearcher : IAnalysisMisc
193    {
194        private KeyPattern pattern = null;
195        public KeyPattern Pattern
196        {
197            get
198            {
199                return pattern;
200            }
201            set
202            {
203                pattern = value;
204                if ((settings.Key == null) ||((settings.Key != null) && !pattern.testKey(settings.Key)))
205                    settings.Key = pattern.giveWildcardKey();
206            }
207        }
208
209        private bool stop;
210
211        #region IPlugin Members
212
213        public event StatusChangedEventHandler OnPluginStatusChanged;
214
215        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
216
217        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
218
219        private KeySearcherSettings settings;       
220
221        public KeySearcher()
222        {
223            settings = new KeySearcherSettings(this);
224            QuickWatchPresentation = new KeySearcherQuickWatchPresentation();
225        }
226
227        public ISettings Settings
228        {
229            get { return settings; }
230        }
231
232        public UserControl Presentation
233        {
234            get { return null; }
235        }
236
237        public UserControl QuickWatchPresentation
238        {
239            get;
240            private set;
241        }
242
243        public void PreExecution()
244        {
245        }
246
247        public void Execute()
248        {
249        }
250
251        public void process(IControlEncryption sender)
252        {           
253
254            if (sender != null && costMaster != null)
255            {
256                int maxInList = 10;
257                LinkedList<ValueKey> costList = new LinkedList<ValueKey>();
258                ValueKey valueKey = new ValueKey();               
259                if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
260                    valueKey.value = double.MaxValue;
261                else
262                    valueKey.value = double.MinValue;
263                valueKey.key = "dummykey";               
264                LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
265                for (int i = 1; i < maxInList; i++)
266                {
267                    node = costList.AddAfter(node, valueKey);
268                }
269
270                stop = false;
271                if (!Pattern.testKey(settings.Key))
272                {
273                    GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
274                    return;
275                }
276               
277                int bytesToUse = 0;
278                double size = Pattern.initKeyIteration(settings.Key);
279               
280                try
281                {
282                    bytesToUse = CostMaster.getBytesToUse();
283                }
284                catch (Exception ex)
285                {
286                    GuiLogMessage("Bytes to use not valid: " + ex.Message, NotificationLevel.Error);
287                    return;
288                }
289 
290                double keycounter = 0;
291                double doneKeys = 0;
292                LinkedListNode<ValueKey> linkedListNode;
293
294                DateTime lastTime = DateTime.Now;               
295                do
296                {
297                   
298                    try
299                    {
300                        valueKey.key = Pattern.getKey();
301                    }
302                    catch (Exception ex)
303                    {
304                        GuiLogMessage("Could not get next Key: " + ex.Message, NotificationLevel.Error);
305                        return;
306                    }
307
308                    try
309                    {
310                        valueKey.decryption = sender.Decrypt(ControlMaster.getKeyFromString(valueKey.key), bytesToUse);
311                    }
312                    catch (Exception ex)
313                    {
314                        GuiLogMessage("Decryption is not possible: " + ex.Message, NotificationLevel.Error);
315                        return;
316                    }
317               
318                    try
319                    {
320                        valueKey.value = CostMaster.calculateCost(valueKey.decryption);
321                    }
322                    catch (Exception ex)
323                    {
324                        GuiLogMessage("Cost calculation is not possible: " + ex.Message, NotificationLevel.Error);
325                        return;
326                    }
327
328                    if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
329                    {
330                        if(valueKey.value > costList.Last().value){                           
331                            node = costList.First;
332                            while (node != null)
333                            {
334
335                                if (valueKey.value > node.Value.value)
336                                {
337                                    costList.AddBefore(node, valueKey);
338                                    costList.RemoveLast();
339                                    break;
340                                }
341                                node = node.Next;
342                            }//end while
343                        }//end if
344                    }
345                    else
346                    {
347                        node = costList.First;
348                        if (valueKey.value < costList.Last().value)
349                        {
350                            while (node != null)
351                            {
352
353                                if (valueKey.value < node.Value.value)
354                                {
355                                    costList.AddBefore(node, valueKey);
356                                    costList.RemoveLast();
357                                    break;
358                                }
359                                node = node.Next;
360                            }//end while
361                        }//end if
362                    }
363                   
364                    keycounter++;
365                    doneKeys++; 
366                    TimeSpan duration = DateTime.Now - lastTime;
367                    if (duration.Seconds >= 1)
368                    {
369                        ProgressChanged(keycounter, size);
370                       
371                        if (QuickWatchPresentation.IsVisible)
372                        {
373                            lastTime = DateTime.Now;
374                            double time = ((size - keycounter) / doneKeys);
375                            TimeSpan timeleft = new TimeSpan(-1);
376
377                            try
378                            {
379                                if (time / (24 * 60 * 60) <= int.MaxValue)
380                                {
381                                    int days = (int)(time / (24 * 60 * 60));
382                                    time = time - (days * 24 * 60 * 60);
383                                    int hours = (int)(time / (60 * 60));
384                                    time = time - (hours * 60 * 60);
385                                    int minutes = (int)(time / 60);
386                                    time = time - (minutes * 60);
387                                    int seconds = (int)time;
388
389                                    timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
390                                }
391                            }
392                            catch
393                            {
394                                //can not calculate time span
395                            }
396
397                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
398                            {
399                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).keysPerSecond.Text = "" + doneKeys;
400                                if (timeleft != new TimeSpan(-1))
401                                {
402                                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "" + timeleft;
403                                    try
404                                    {
405                                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "" + DateTime.Now.Add(timeleft);
406                                    }catch{
407                                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
408                                    }
409                                }
410                                else
411                                {
412                                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "incalculable :-)";
413                                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
414                                }
415                             
416                                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
417                                linkedListNode = costList.First;
418                                System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
419                                int i=0;
420                                while (linkedListNode != null)
421                                {
422                                    i++;
423                                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value,4) + " = " + linkedListNode.Value.key + " : \"" + 
424                                        enc.GetString(linkedListNode.Value.decryption).Replace("\n","").Replace("\r", "").Replace("\t", "") + "\"");
425                                    linkedListNode = linkedListNode.Next;
426                                }                               
427                            }
428                            , null);
429                        }//end if
430                        doneKeys = 0;
431                    }//end if
432
433                } while (Pattern.nextKey() && !stop);
434
435                if (QuickWatchPresentation.IsVisible)
436                {
437
438                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
439                    {
440                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
441                        linkedListNode = costList.First;
442                        System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
443                        int i = 0;
444                        while (linkedListNode != null)
445                        {
446                            i++;
447                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
448                                enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
449                            linkedListNode = linkedListNode.Next;
450                        }
451                    }
452                    , null);
453                }
454
455                if(!stop)
456                    ProgressChanged(1, 1);
457
458            }//end if
459        }
460
461        public void PostExecution()
462        {
463        }
464
465        public void Pause()
466        {
467        }
468
469        public void Stop()
470        {
471            stop = true;
472        }
473
474        public void Initialize()
475        {
476        }
477
478        public void Dispose()
479        {
480        }
481
482        #endregion
483
484        #region INotifyPropertyChanged Members
485
486        public event PropertyChangedEventHandler PropertyChanged;
487
488        public void OnPropertyChanged(string name)
489        {
490            if (PropertyChanged != null)
491            {
492                PropertyChanged(this, new PropertyChangedEventArgs(name));
493            }
494        }
495
496        #endregion
497
498        private void keyPatternChanged()
499        {
500            Pattern = new KeyPattern(controlMaster.getKeyPattern());
501        }
502
503        private void onStatusChanged(IControl sender, bool readyForExecution)
504        {
505            if (readyForExecution)
506            {
507                this.process((IControlEncryption)sender);
508            }
509        }
510
511        #region IControlEncryption Members
512
513        private IControlEncryption controlMaster;
514        [PropertyInfo(Direction.ControlMaster, "Control Master", "Used for bruteforcing", "", DisplayLevel.Beginner)]
515        public IControlEncryption ControlMaster
516        {
517            get { return controlMaster; }
518            set
519            {
520                if (controlMaster != null)
521                {
522                    controlMaster.keyPatternChanged -= keyPatternChanged;
523                    controlMaster.OnStatusChanged -= onStatusChanged;
524                }
525                if (value != null)
526                {
527                    Pattern = new KeyPattern(value.getKeyPattern());
528                    value.keyPatternChanged += keyPatternChanged;
529                    value.OnStatusChanged += onStatusChanged;
530                    controlMaster = value;
531                    OnPropertyChanged("ControlMaster");
532                   
533                }
534                else
535                    controlMaster = null;
536            }
537        }
538
539        #endregion
540
541        #region IControlCost Members
542
543        private IControlCost costMaster;
544        [PropertyInfo(Direction.ControlMaster, "Cost Master", "Used for cost calculation", "", DisplayLevel.Beginner)]
545        public IControlCost CostMaster
546        {
547            get { return costMaster; }
548            set
549            {
550                costMaster = value;
551            }
552        }
553
554        #endregion
555
556        public void GuiLogMessage(string message, NotificationLevel loglevel)
557        {
558            if (OnGuiLogNotificationOccured != null)
559                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
560        }
561
562        public void ProgressChanged(double value, double max)
563        {
564            if (OnPluginProgressChanged != null)
565            {
566                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
567
568            }
569        }
570
571        private struct ValueKey
572        {
573            public double value;
574            public String key;
575            public byte[] decryption;
576        };
577    }
578}
579
Note: See TracBrowser for help on using the repository browser.