source: trunk/CrypPlugins/TranspositionAnalyser/TranspositionAnalyser.cs @ 1105

Last change on this file since 1105 was 1105, checked in by kohnen, 12 years ago
  • functional QuickWatch
File size: 26.5 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 Cryptool.PluginBase.Miscellaneous;
10using System.Collections;
11using System.Windows.Threading;
12using System.Threading;
13using System.Collections.Generic;
14
15
16
17namespace TranspositionAnalyser
18{
19
20    [Author("Daniel Kohnen, Julian Weyers, Simon Malischewski, Armin Wiefels", "kohnen@cryptool.org, weyers@cryptool.org, malischewski@cryptool.org, wiefels@cryptool.org", "Universität Duisburg-Essen", "http://www.uni-due.de")]
21    [PluginInfo(true, "Transposition Analyser", "Bruteforces the columnar transposition.", "TranspositionAnalyser/Description/TADescr.xaml" , "TranspositionAnalyser/Images/icon.png")]
22    public class TranspositionAnalyser : IAnalysisMisc
23    {
24        private enum ReadInMode { byRow = 0, byColumn = 1 };
25        private enum PermutationMode { byRow = 0, byColumn = 1 };
26        private enum ReadOutMode { byRow = 0, byColumn = 1 };
27        private byte[] crib;
28        private byte[] input;
29        private Queue valuequeue;
30        LinkedList<ValueKey> list1;
31
32        TranspositionAnalyserSettings settings;
33        #region Properties
34        [PropertyInfo(Direction.InputData, "Input", "Input data for Analysis", "", true, false, DisplayLevel.Beginner, QuickWatchFormat.Text, null)]
35        public Byte[] Input
36        {
37            get
38            {
39                return this.input;
40            }
41
42            set
43            {
44                this.input = value;
45                OnPropertyChange("Input");
46               
47            }
48        }
49
50        [PropertyInfo(Direction.InputData, "Crib", "Crib input", "Crib for Analysis", false, false, DisplayLevel.Beginner, QuickWatchFormat.Text, null)]
51        public Byte[] Crib
52        {
53            get
54            {
55                return this.crib;
56            }
57
58            set
59            {
60                this.crib = value;
61                OnPropertyChange("Crib");
62            }
63        }
64
65
66
67        #endregion
68        /// <summary>
69        /// Constructor
70        /// </summary>
71        public TranspositionAnalyser()
72        {
73            settings = new TranspositionAnalyserSettings();
74            QuickWatchPresentation = new TranspositionAnalyserQuickWatchPresentation();
75        }
76
77        private IControlEncryption controlMaster;
78        [PropertyInfo(Direction.ControlMaster, "Control Master", "Used for bruteforcing", "", false, false, DisplayLevel.Beginner,QuickWatchFormat.None,null)]
79        public IControlEncryption ControlMaster
80        {
81           
82            get { return controlMaster; }
83            set
84            {
85               // value.OnStatusChanged += onStatusChanged;
86                controlMaster = value;
87                OnPropertyChanged("ControlMaster");
88               
89            }
90        }
91
92        private IControlCost costMaster;
93        [PropertyInfo(Direction.ControlMaster, "Cost Master", "Used for cost calculation", "", false, false, DisplayLevel.Beginner, QuickWatchFormat.None, null)]
94        public IControlCost CostMaster
95        {
96            get { return costMaster; }
97            set
98            {
99                costMaster = value;
100            }
101        }
102
103        private byte[] output;
104        [PropertyInfo(Direction.OutputData, "Output", "output", "", DisplayLevel.Beginner)]
105        public byte[] Output
106        {
107            get
108            {
109                return this.output;
110            }
111            set
112            {
113                this.output = value;
114                OnPropertyChanged("Output");
115            }
116        }
117
118        public void GuiLogMessage(string message, NotificationLevel loglevel)
119        {
120            if (OnGuiLogNotificationOccured != null)
121                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(message, this, loglevel));
122        }
123
124        #region IPlugin Member
125
126        public event Cryptool.PluginBase.StatusChangedEventHandler OnPluginStatusChanged;
127
128        public event Cryptool.PluginBase.GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
129
130        public event Cryptool.PluginBase.PluginProgressChangedEventHandler OnPluginProgressChanged;
131
132        public ISettings Settings
133        {
134            get { return settings; }
135        }
136
137
138
139        public UserControl Presentation
140        {
141            get { return null; }
142        }
143
144        public UserControl QuickWatchPresentation
145        {
146            get;
147            private set;
148        }
149
150        public void PreExecution()
151        {
152           
153        }
154
155        public void Execute()
156        {
157           
158
159            if (this.input != null)
160            {
161                if (this.ControlMaster != null && this.input != null)
162                    this.process(this.ControlMaster);
163                else
164                {
165                    GuiLogMessage("You have to connect the Transposition Plugin to the Transpostion Analyzer Control!", NotificationLevel.Warning);
166                }
167            }
168        }
169
170        public void PostExecution()
171        {
172
173        }
174
175        public void Pause()
176        {
177
178        }
179
180        private Boolean stop;
181        public void Stop()
182        {
183            stop = true;
184        }
185
186        public void Initialize()
187        {
188            this.settings.Analysis_method = 0;           
189        }
190
191        public void Dispose()
192        {
193
194        }
195
196        private void onStatusChanged(IControl sender, bool readyForExecution)
197        {
198           
199        }
200
201        public void OnPropertyChanged(string name)
202        {
203            if (PropertyChanged != null)
204            {
205                PropertyChanged(this, new PropertyChangedEventArgs(name));
206            }
207        }
208
209        private void OnPropertyChange(String propertyname)
210        {
211            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(propertyname));
212        }
213
214        public void process(IControlEncryption sender)
215        {
216            if (input != null)
217            {
218                sender.setInput(input);
219                switch (this.settings.Analysis_method)
220                {
221                    case 0: Output = costfunction_bruteforce(sender); GuiLogMessage("Starting Brute-Force Analysis", NotificationLevel.Info); break;
222                    case 1: GuiLogMessage("Starting Analysis with crib", NotificationLevel.Info); cribAnalysis(this.crib, this.input); break;
223
224                }
225            }
226            else
227            {
228                GuiLogMessage("No Input!", NotificationLevel.Error);
229            }
230           
231           
232        }
233
234        private int[] getBruteforceSettings()
235        {
236            int[] set;
237            int sum = 0;
238            if (settings.ColumnColumnColumn) sum++;
239            if (settings.ColumnColumnRow) sum++;
240            if (settings.RowColumnColumn) sum++;
241            if (settings.RowColumnRow) sum++;
242
243            if (sum > 0)
244            {
245                set = new int[sum];
246                int count = 0;
247                if (settings.ColumnColumnColumn)
248                {
249                    set[count] = 0;
250                    count++;
251                }
252                if (settings.ColumnColumnRow)
253                {
254                    set[count] = 1;
255                    count++;
256                }
257                if (settings.RowColumnColumn)
258                {
259                    set[count] = 2;
260                    count++;
261                }
262
263                if (settings.RowColumnRow)
264                {
265                    set[count] = 3;
266                    count++;
267                }
268                return set;
269            }
270            else
271            {
272                return null;
273            }
274
275        }
276
277        private byte[] costfunction_bruteforce(IControlEncryption sender)
278        {
279            valuequeue = Queue.Synchronized(new Queue());
280            int[] set = getBruteforceSettings();
281            stop = false;
282            if (sender != null && costMaster != null && set != null)
283            {
284                GuiLogMessage("start", NotificationLevel.Info);
285                double best = Double.MinValue;
286               
287                if (costMaster.getRelationOperator() == RelationOperator.LessThen)
288                {
289                    best = Double.MaxValue;
290                }
291
292                list1 = getDummyLinkedList(best);
293                String best_text = "";
294                byte[] best_bytes = null;
295                ArrayList list = null;
296
297
298                //Just for fractional-calculation:
299                PermutationGenerator per = new PermutationGenerator(2);
300                DateTime starttime = DateTime.Now;
301                DateTime lastUpdate = DateTime.Now;
302
303                int max = 0;
304                max = settings.MaxLength;
305                //GuiLogMessage("Max: " + max, NotificationLevel.Info);
306                if (max > 1 && max < 21)
307                {
308                    long size = 0;
309                    for (int i = 2; i <= max; i++)
310                    {
311                        size = size + per.getFactorial(i);
312                    }
313                    size = size * set.Length;
314                    long sum = 0;
315                    for (int i = 1; i <= max; i++)
316                    {
317                        // for every selected bruteforce mode:
318                        for (int s = 0; s < set.Length; s++)
319                        {
320                            switch (set[s])
321                            {
322                                case (0):
323                                    controlMaster.changeSettings("ReadIn", ReadInMode.byColumn);
324                                    controlMaster.changeSettings("Permute", PermutationMode.byColumn);
325                                    controlMaster.changeSettings("ReadOut", ReadOutMode.byColumn);
326                                    break;
327                                case (1):
328                                    controlMaster.changeSettings("ReadIn", ReadInMode.byColumn);
329                                    controlMaster.changeSettings("Permute", PermutationMode.byColumn);
330                                    controlMaster.changeSettings("ReadOut", ReadOutMode.byRow);
331                                    break;
332                                case (2):
333                                    controlMaster.changeSettings("ReadIn", ReadInMode.byRow);
334                                    controlMaster.changeSettings("Permute", PermutationMode.byColumn);
335                                    controlMaster.changeSettings("ReadOut", ReadOutMode.byColumn);
336                                    break;
337                                case (3):
338                                    controlMaster.changeSettings("ReadIn", ReadInMode.byRow);
339                                    controlMaster.changeSettings("Permute", PermutationMode.byColumn);
340                                    controlMaster.changeSettings("ReadOut", ReadOutMode.byRow);
341                                    break;
342                            }
343
344                            per = new PermutationGenerator(i);
345
346                            while (per.hasMore() && !stop)
347                            {
348                                best = list1.Last.Value.value;
349                                int[] key = per.getNext();
350                                byte[] b = new byte[key.Length];
351                                for (int j = 0; j < b.Length; j++)
352                                {
353                                    b[j] = Convert.ToByte(key[j]);
354                                }
355                                byte[] dec = sender.Decrypt(b, b.Length);
356                                if (dec != null)
357                                {
358                                    double val = costMaster.calculateCost(dec);
359                                    if(val.Equals(new Double()))
360                                    {
361                                     return new byte[0];   
362                                    }
363                                    if (costMaster.getRelationOperator() == RelationOperator.LessThen)
364                                    {
365                                        if (val <= best)
366                                        {
367                                            ValueKey valkey = new ValueKey();
368                                            String keyStr = "";
369                                            foreach (int xyz in key)
370                                            {
371                                                keyStr += xyz;
372                                            }
373                                            valkey.decryption = dec;
374                                            valkey.key = keyStr;
375                                            valkey.value = val;
376                                            valuequeue.Enqueue(valkey);
377                                        }
378                                    }
379                                    else
380                                    {
381                                        if (val >= best)
382                                        {
383                                            ValueKey valkey = new ValueKey();
384                                            String keyStr = "";
385                                            foreach (int xyz in key)
386                                            {
387                                                keyStr += xyz;
388                                            }
389                                            valkey.decryption = dec;
390                                            valkey.key = keyStr;
391                                            valkey.value = val;
392                                            valuequeue.Enqueue(valkey);
393                                           
394                                        }
395                                    }
396                                }
397
398                                sum++;
399                                if (DateTime.Now >= lastUpdate.AddMilliseconds(1000))
400                                {   updateToplist(list1);
401                                    showProgress(starttime, size, sum);
402                                    ProgressChanged(sum, size);
403                                    lastUpdate = DateTime.Now;
404                                }
405                            }
406                        }
407                    }
408                    if (list != null)
409                    {
410                        int i = 1;
411                        foreach (string tmp in list)
412                        {
413                            GuiLogMessage("ENDE (" + i++ + ")" + best + ": " + tmp,NotificationLevel.Info);
414                        }
415                    }
416                    else
417                    {
418                        GuiLogMessage("ENDE " + best + ": " + best_text, NotificationLevel.Info);
419                    }
420                    return list1.First.Value.decryption;
421                }
422                else
423                {
424                    GuiLogMessage("Error: Check transposition bruteforce length. Max length is 20!", NotificationLevel.Error);
425                    return null;
426                }
427            }
428            else
429            {
430                GuiLogMessage("Error: No costfunction applied.", NotificationLevel.Error);
431                return null;
432            }
433        }
434
435        private LinkedList<ValueKey> getDummyLinkedList(double best)
436        {
437            ValueKey valueKey = new ValueKey();
438            valueKey.value = best;
439            valueKey.key = "dummykey";
440            valueKey.decryption = new byte[0];
441            LinkedList<ValueKey> list = new LinkedList<ValueKey>();
442            LinkedListNode<ValueKey> node = list.AddFirst(valueKey);
443            for (int i = 0; i < 10; i++)
444            {
445                node = list.AddAfter(node, valueKey);
446            }
447            return list;
448        }
449
450        private void updateToplist(LinkedList<ValueKey> costList)
451        {
452            LinkedListNode<ValueKey> node;
453            while (valuequeue.Count != 0)
454            {
455                ValueKey vk = (ValueKey)valuequeue.Dequeue();
456                if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
457                {
458                    if (vk.value > costList.Last().value)
459                    {
460                        node = costList.First;
461                        while (node != null)
462                        {
463                            if (vk.value > node.Value.value)
464                            {
465                                costList.AddBefore(node, vk);
466                                costList.RemoveLast();
467                               // value_threshold = costList.Last.Value.value;
468                                break;
469                            }
470                            node = node.Next;
471                        }//end while
472                    }//end if
473                }
474                else
475                {
476                    if (vk.value < costList.Last().value)
477                    {
478                        node = costList.First;
479                        while (node != null)
480                        {
481                            if (vk.value < node.Value.value)
482                            {
483                                costList.AddBefore(node, vk);
484                                costList.RemoveLast();
485                               // value_threshold = costList.Last.Value.value;
486                                break;
487                            }
488                            node = node.Next;
489                        }//end while
490                    }//end if
491                }
492            }
493        }
494
495        #endregion
496
497        #region INotifyPropertyChanged Member
498
499        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
500
501        #endregion
502
503        public void ProgressChanged(double value, double max)
504        {
505            if (OnPluginProgressChanged != null)
506            {
507                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
508
509            }
510        }
511       
512        #region cribAnalysis
513        public void cribAnalysis(byte[] crib, byte[] cipher) 
514        {
515
516            if (crib != null && crib != null)
517            {
518                foreach (int c in getKeyLength(crib, cipher))
519                {
520                    GuiLogMessage("Possible Key-Length: " + c, NotificationLevel.Info);
521                }
522            }
523            else { GuiLogMessage("Missing crib or input!",NotificationLevel.Info); }
524        }
525
526        #endregion
527
528        #region KeyLengthAnalysis
529
530        public ArrayList getKeyLength(byte[] crib, byte[] cipher)
531        {
532           
533            ArrayList keylengths = new ArrayList();
534
535            for (int i = 1; i < crib.Length; i++)
536            {
537                byte[,] cipherM = cipherToMatrix(i, cipher);
538                byte[,] cribM = cribToMatrix(i, crib);
539                int[] analysed = analyse(i, cipherM, cribM);
540
541                for (int j = 0; j < analysed.Length; j++)
542                {
543                   
544                    if (analysed[j] != 0)
545                    {
546                        if (j == analysed.Length - 1)
547                        {
548                            keylengths.Add(i);
549                        }
550                    }
551                    else break;
552                }
553               
554            }
555            return keylengths;
556           
557        }
558
559        byte[,] cribToMatrix(int i, byte[] tmp)
560        {
561            int x = tmp.Length / i;
562            if (tmp.Length % i != 0)
563            {
564                x++;
565            }
566            byte[,] arr = new byte[i, x];
567            int count = 0;
568
569            for (int a = 0; a < x; a++)
570            {
571                for (int b = 0; b < i; b++)
572                {
573                    if (count < tmp.Length)
574                        arr[b, a] = tmp[count++];
575                }
576            }
577            return arr;
578        }
579
580        byte[,] cipherToMatrix(int i, byte[] tmp)
581        {
582            int length = tmp.Length / i;
583            int off = 0;
584            if (tmp.Length % i != 0)
585            {
586                length++;
587                off = (i * length) - tmp.Length;
588            }
589            byte[,] cipherMatrix = new byte[length, i];
590            int pos = 0;
591
592            for (int a = 0; a < i; a++)
593            {
594                for (int b = 0; b < length; b++)
595                {
596                    if (b == length - 1)
597                    {
598                        if (a < off)
599                        {
600                            break;
601                        }
602                    }
603                    cipherMatrix[b, a] = tmp[pos];
604                    pos++;
605                }
606            }
607            return cipherMatrix;
608        }
609
610        int[] analyse(int i, byte[,] cipherMatrix, byte[,] cribMatrix)
611        {
612            int cipherMatrixLength = cipherMatrix.Length / i;
613            int cribMatrixHeight = cribMatrix.Length / i;
614            int[] poscount = new int[i];
615            ArrayList[] def = new ArrayList[i];
616            for (int a = 0; a < i; a++)
617            {
618                def[a] = new ArrayList();
619            }
620
621            byte newchar = new byte();
622            byte emptychar = new byte();
623            int count = 0;
624            for (int a = 0; a < i; a++)
625            {
626                if (!cribMatrix[a, cribMatrixHeight - 1].Equals(emptychar))
627                {
628                    count++;
629                }
630                else
631                {
632                    poscount[a] = -1;
633                }
634            }
635
636            for (int x = 0; x < count; x++)
637            {
638                for (int a = 0; a < i; a++)
639                {
640                    for (int b = 0; b < cipherMatrixLength; b++)
641                    {
642                        if (cribMatrix[x, 0].Equals(cipherMatrix[b, a]))
643                        {
644                            int tmpA = a;
645                            int tmpB = b;
646
647                            for (int y = 1; y < cribMatrixHeight; y++)
648                            {
649                                tmpB++;
650                                if (tmpB == cipherMatrixLength - 1)
651                                {
652                                    if (cipherMatrix[tmpB, tmpA].Equals(newchar))
653                                    {
654                                        tmpB = 0;
655                                        tmpA++;
656                                    }
657                                }
658
659                                if ((tmpB) < cipherMatrixLength)
660                                {
661                                    if (cribMatrix[x, y].Equals(cipherMatrix[tmpB, tmpA]))
662                                    {
663                                        if (y.Equals(cribMatrixHeight - 1))
664                                        {
665                                            poscount[x]++;
666                                            def[x].Add(b);
667                                           
668                                        }
669                                    }
670                                    else
671                                    {
672                                        break;
673                                    }
674                                }
675                            }
676                        }
677                    }
678                }
679            }
680            return poscount;
681        }
682
683        #endregion
684       
685        //hier entsteht eine QUICKWATCH
686        private void showProgress(DateTime startTime, long size, long sum)
687        {
688            LinkedListNode<ValueKey> linkedListNode;
689            if (QuickWatchPresentation.IsVisible && !stop)
690            {
691                DateTime currentTime = DateTime.Now;
692                TimeSpan span = currentTime.Subtract(startTime);
693                int seconds = span.Seconds;
694                int minutes = span.Minutes;
695                int hours = span.Hours;
696                int days = span.Days;
697
698                long allseconds = seconds + 60 * minutes + 60 * 60 * hours + 24 * 60 * 60 * days;
699                if (allseconds == 0) allseconds = 1;
700                long keysPerSec = sum / allseconds;
701
702                long keystodo = (size - sum);
703                long secstodo = keystodo / keysPerSec;
704                DateTime endTime = DateTime.Now.AddSeconds(secstodo);
705
706
707                ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
708                {
709
710                    ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).keysPerSecond.Text = "" + keysPerSec;
711
712
713                    ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "" + endTime.Subtract(DateTime.Now);
714
715                    ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "" + endTime;
716                    //((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).listbox.Clear();
717                    linkedListNode = list1.First;
718                    ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
719                    int i = 0;
720                    while (linkedListNode != null)
721                    {
722                        i++;
723
724                        String dec = System.Text.Encoding.ASCII.GetString(linkedListNode.Value.decryption).Substring(0, 25) + "...";
725                        String key = linkedListNode.Value.key;
726                        String value = linkedListNode.Value.value + "";
727                        String outp = i+".:" + key + ":" + dec + "(" + value +")";
728                        ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(outp);
729                        linkedListNode = linkedListNode.Next;
730                    }
731               
732                }
733
734
735                , null);
736               
737            }
738        }
739   
740    }
741
742    public struct ValueKey
743    {
744        public double value;
745        public String key;
746        public byte[] decryption;
747    };
748}
Note: See TracBrowser for help on using the repository browser.