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

Last change on this file since 1121 was 1121, checked in by kohnen, 12 years ago
  • deleted setInput-function from IControlEncryption and all Plugins using IControlEncryption
  • some changes at TranspositionAnalyser plugin & Settings
  • new TranspositionAnalyser sample
File size: 27.9 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(false, "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            ProgressChanged(1, 1);
169        }
170
171        public void PostExecution()
172        {
173
174        }
175
176        public void Pause()
177        {
178
179        }
180
181        private Boolean stop;
182        public void Stop()
183        {
184            stop = true;
185        }
186
187        public void Initialize()
188        {
189            this.settings.Analysis_method = 0;           
190        }
191
192        public void Dispose()
193        {
194
195        }
196
197        private void onStatusChanged(IControl sender, bool readyForExecution)
198        {
199           
200        }
201
202        public void OnPropertyChanged(string name)
203        {
204            if (PropertyChanged != null)
205            {
206                PropertyChanged(this, new PropertyChangedEventArgs(name));
207            }
208        }
209
210        private void OnPropertyChange(String propertyname)
211        {
212            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(propertyname));
213        }
214
215        public void process(IControlEncryption sender)
216        {
217            if (input != null)
218            {
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                ArrayList list = null;
295
296
297                //Just for fractional-calculation:
298                PermutationGenerator per = new PermutationGenerator(2);
299                DateTime starttime = DateTime.Now;
300                DateTime lastUpdate = DateTime.Now;
301
302                int max = 0;
303                max = settings.MaxLength;
304                //GuiLogMessage("Max: " + max, NotificationLevel.Info);
305                if (max > 1 && max < 21)
306                {
307                    long size = 0;
308                    for (int i = 2; i <= max; i++)
309                    {
310                        size = size + per.getFactorial(i);
311                    }
312                    size = size * set.Length;
313                    long sum = 0;
314                    for (int i = 1; i <= max; i++)
315                    {
316                        // for every selected bruteforce mode:
317                        for (int s = 0; s < set.Length; s++)
318                        {
319                            switch (set[s])
320                            {
321                                case (0):
322                                    controlMaster.changeSettings("ReadIn", ReadInMode.byColumn);
323                                    controlMaster.changeSettings("Permute", PermutationMode.byColumn);
324                                    controlMaster.changeSettings("ReadOut", ReadOutMode.byColumn);
325                                    break;
326                                case (1):
327                                    controlMaster.changeSettings("ReadIn", ReadInMode.byColumn);
328                                    controlMaster.changeSettings("Permute", PermutationMode.byColumn);
329                                    controlMaster.changeSettings("ReadOut", ReadOutMode.byRow);
330                                    break;
331                                case (2):
332                                    controlMaster.changeSettings("ReadIn", ReadInMode.byRow);
333                                    controlMaster.changeSettings("Permute", PermutationMode.byColumn);
334                                    controlMaster.changeSettings("ReadOut", ReadOutMode.byColumn);
335                                    break;
336                                case (3):
337                                    controlMaster.changeSettings("ReadIn", ReadInMode.byRow);
338                                    controlMaster.changeSettings("Permute", PermutationMode.byColumn);
339                                    controlMaster.changeSettings("ReadOut", ReadOutMode.byRow);
340                                    break;
341                            }
342
343                            per = new PermutationGenerator(i);
344
345                            while (per.hasMore() && !stop)
346                            {
347                                best = list1.Last.Value.value;
348                                int[] key = per.getNext();
349                                byte[] b = new byte[key.Length];
350                                for (int j = 0; j < b.Length; j++)
351                                {
352                                    b[j] = Convert.ToByte(key[j]);
353                                }
354                                byte[] dec = sender.Decrypt(input, b);
355                                if (dec != null)
356                                {
357                                    double val = costMaster.calculateCost(dec);
358                                    if(val.Equals(new Double()))
359                                    {
360                                     return new byte[0];   
361                                    }
362                                    if (costMaster.getRelationOperator() == RelationOperator.LessThen)
363                                    {
364                                        if (val <= best)
365                                        {
366                                            ValueKey valkey = new ValueKey();
367                                            String keyStr = "";
368                                            foreach (int xyz in key)
369                                            {
370                                                keyStr += xyz;
371                                            }
372                                            valkey.decryption = dec;
373                                            valkey.key = keyStr;
374                                            valkey.value = val;
375                                            valuequeue.Enqueue(valkey);
376                                        }
377                                    }
378                                    else
379                                    {
380                                        if (val >= best)
381                                        {
382                                            ValueKey valkey = new ValueKey();
383                                            String keyStr = "";
384                                            foreach (int xyz in key)
385                                            {
386                                                keyStr += xyz;
387                                            }
388                                            valkey.decryption = dec;
389                                            valkey.key = keyStr;
390                                            valkey.value = val;
391                                            valuequeue.Enqueue(valkey);
392                                           
393                                        }
394                                    }
395                                }
396
397                                sum++;
398                                if (DateTime.Now >= lastUpdate.AddMilliseconds(1000))
399                                {   updateToplist(list1);
400                                    showProgress(starttime, size, sum);
401                                    ProgressChanged(sum, size);
402                                    lastUpdate = DateTime.Now;
403                                }
404                            }
405                        }
406                    }
407                    if (list != null)
408                    {
409                        int i = 1;
410                        foreach (string tmp in list)
411                        {
412                            GuiLogMessage("ENDE (" + i++ + ")" + best + ": " + tmp,NotificationLevel.Info);
413                        }
414                    }
415                    else
416                    {
417                        GuiLogMessage("ENDE " + best + ": " + best_text, NotificationLevel.Info);
418                    }
419                    return list1.First.Value.decryption;
420                }
421                else
422                {
423                    GuiLogMessage("Error: Check transposition bruteforce length. Max length is 20!", NotificationLevel.Error);
424                    return null;
425                }
426            }
427            else
428            {
429                GuiLogMessage("Error: No costfunction applied.", NotificationLevel.Error);
430                return null;
431            }
432        }
433
434        private LinkedList<ValueKey> getDummyLinkedList(double best)
435        {
436            ValueKey valueKey = new ValueKey();
437            valueKey.value = best;
438            valueKey.key = "dummykey";
439            valueKey.decryption = new byte[0];
440            LinkedList<ValueKey> list = new LinkedList<ValueKey>();
441            LinkedListNode<ValueKey> node = list.AddFirst(valueKey);
442            for (int i = 0; i < 9; i++)
443            {
444                node = list.AddAfter(node, valueKey);
445            }
446            return list;
447        }
448
449        private void updateToplist(LinkedList<ValueKey> costList)
450        {
451            LinkedListNode<ValueKey> node;
452            while (valuequeue.Count != 0)
453            {
454                ValueKey vk = (ValueKey)valuequeue.Dequeue();
455                if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
456                {
457                    if (vk.value > costList.Last().value)
458                    {
459                        node = costList.First;
460                        int i = 0;
461                        while (node != null)
462                        {
463                            if (vk.value > node.Value.value)
464                            {
465                                costList.AddBefore(node, vk);
466                                costList.RemoveLast();
467                                if (i == 0)
468                                {
469                                    Output = vk.decryption;
470                                }
471                               // value_threshold = costList.Last.Value.value;
472                                break;
473                            }
474                            node = node.Next;
475                            i++;
476                        }//end while
477                    }//end if
478                }
479                else
480                {
481                    if (vk.value < costList.Last().value)
482                    {
483                        node = costList.First;
484                        int i = 0;
485                        while (node != null)
486                        {
487                            if (vk.value < node.Value.value)
488                            {
489                                costList.AddBefore(node, vk);
490                                costList.RemoveLast();
491                                if (i == 0)
492                                {
493                                    Output = vk.decryption;
494                                }
495
496                               // value_threshold = costList.Last.Value.value;
497                                break;
498                            }
499                            node = node.Next;
500                            i++;
501                        }//end while
502                    }//end if
503                }
504            }
505        }
506
507        #endregion
508
509        #region INotifyPropertyChanged Member
510
511        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
512
513        #endregion
514
515        public void ProgressChanged(double value, double max)
516        {
517            if (OnPluginProgressChanged != null)
518            {
519                OnPluginProgressChanged(this, new PluginProgressEventArgs(value, max));
520
521            }
522        }
523       
524        #region cribAnalysis
525        public void cribAnalysis(byte[] crib, byte[] cipher) 
526        {
527
528            if (crib != null && crib != null)
529            {
530                foreach (int c in getKeyLength(crib, cipher))
531                {
532                    GuiLogMessage("Possible Key-Length: " + c, NotificationLevel.Info);
533                }
534            }
535            else { GuiLogMessage("Missing crib or input!",NotificationLevel.Info); }
536        }
537
538        #endregion
539
540        #region
541
542        public ArrayList getKeyLength(byte[] crib, byte[] cipher)
543        {
544           
545            ArrayList keylengths = new ArrayList();
546
547            for (int i = 1; i < crib.Length; i++)
548            {
549                byte[,] cipherM = cipherToMatrix(i, cipher);
550                byte[,] cribM = cribToMatrix(i, crib);
551                int[] analysed = analyse(i, cipherM, cribM);
552
553                for (int j = 0; j < analysed.Length; j++)
554                {
555                   
556                    if (analysed[j] != 0)
557                    {
558                        if (j == analysed.Length - 1)
559                        {
560                            keylengths.Add(i);
561                        }
562                    }
563                    else break;
564                }
565               
566            }
567            return keylengths;
568           
569        }
570
571        byte[,] cribToMatrix(int i, byte[] tmp)
572        {
573            int x = tmp.Length / i;
574            if (tmp.Length % i != 0)
575            {
576                x++;
577            }
578            byte[,] arr = new byte[i, x];
579            int count = 0;
580
581            for (int a = 0; a < x; a++)
582            {
583                for (int b = 0; b < i; b++)
584                {
585                    if (count < tmp.Length)
586                        arr[b, a] = tmp[count++];
587                }
588            }
589            return arr;
590        }
591
592        byte[,] cipherToMatrix(int i, byte[] tmp)
593        {
594            int length = tmp.Length / i;
595            int off = 0;
596            if (tmp.Length % i != 0)
597            {
598                length++;
599                off = (i * length) - tmp.Length;
600            }
601            byte[,] cipherMatrix = new byte[length, i];
602            int pos = 0;
603
604            for (int a = 0; a < i; a++)
605            {
606                for (int b = 0; b < length; b++)
607                {
608                    if (b == length - 1)
609                    {
610                        if (a < off)
611                        {
612                            break;
613                        }
614                    }
615                    cipherMatrix[b, a] = tmp[pos];
616                    pos++;
617                }
618            }
619            return cipherMatrix;
620        }
621
622        int[] analyse(int i, byte[,] cipherMatrix, byte[,] cribMatrix)
623        {
624            int cipherMatrixLength = cipherMatrix.Length / i;
625            int cribMatrixHeight = cribMatrix.Length / i;
626            int[] poscount = new int[i];
627            ArrayList[] def = new ArrayList[i];
628            for (int a = 0; a < i; a++)
629            {
630                def[a] = new ArrayList();
631            }
632
633            byte newchar = new byte();
634            byte emptychar = new byte();
635            int count = 0;
636            for (int a = 0; a < i; a++)
637            {
638                if (!cribMatrix[a, cribMatrixHeight - 1].Equals(emptychar))
639                {
640                    count++;
641                }
642                else
643                {
644                    poscount[a] = -1;
645                }
646            }
647
648            for (int x = 0; x < count; x++)
649            {
650                for (int a = 0; a < i; a++)
651                {
652                    for (int b = 0; b < cipherMatrixLength; b++)
653                    {
654                        if (cribMatrix[x, 0].Equals(cipherMatrix[b, a]))
655                        {
656                            int tmpA = a;
657                            int tmpB = b;
658
659                            for (int y = 1; y < cribMatrixHeight; y++)
660                            {
661                                tmpB++;
662                                if (tmpB == cipherMatrixLength - 1)
663                                {
664                                    if (cipherMatrix[tmpB, tmpA].Equals(newchar))
665                                    {
666                                        tmpB = 0;
667                                        tmpA++;
668                                    }
669                                }
670
671                                if ((tmpB) < cipherMatrixLength)
672                                {
673                                    if (cribMatrix[x, y].Equals(cipherMatrix[tmpB, tmpA]))
674                                    {
675                                        if (y.Equals(cribMatrixHeight - 1))
676                                        {
677                                            poscount[x]++;
678                                            def[x].Add(b);
679                                           
680                                        }
681                                    }
682                                    else
683                                    {
684                                        break;
685                                    }
686                                }
687                            }
688                        }
689                    }
690                }
691            }
692            return poscount;
693        }
694
695        #endregion
696       
697        //hier entsteht eine QUICKWATCH
698        private void showProgress(DateTime startTime, long size, long sum)
699        {
700            LinkedListNode<ValueKey> linkedListNode;
701            if (QuickWatchPresentation.IsVisible && !stop)
702            {
703                DateTime currentTime = DateTime.Now;
704                TimeSpan span = currentTime.Subtract(startTime);
705                int seconds = span.Seconds;
706                int minutes = span.Minutes;
707                int hours = span.Hours;
708                int days = span.Days;
709
710                long allseconds = seconds + 60 * minutes + 60 * 60 * hours + 24 * 60 * 60 * days;
711                if (allseconds == 0) allseconds = 1;
712                long keysPerSec = sum / allseconds;
713
714                long keystodo = (size - sum);
715                long secstodo = keystodo / keysPerSec;
716               
717                //dummy Time
718                DateTime endTime = new DateTime(1970,1,1);
719                try
720                {
721                    endTime = DateTime.Now.AddSeconds(secstodo);
722                }
723                catch
724                {
725
726                }
727
728
729                ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
730                {
731
732                    ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).keysPerSecond.Text = "" + keysPerSec;
733
734                    if (endTime != (new DateTime(1970,1,1)))
735                    {
736                        ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "" + endTime.Subtract(DateTime.Now);
737
738                        ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "" + endTime;
739                    }
740                    else
741                    {
742                        ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "incalculable";
743
744                        ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
745                    }
746                    linkedListNode = list1.First;
747                    ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
748                    int i = 0;
749                    while (linkedListNode != null)
750                    {
751                        i++;
752                        String dec = "";
753                        if (System.Text.Encoding.ASCII.GetString(linkedListNode.Value.decryption).Length > 25)
754                        {
755                            dec = System.Text.Encoding.ASCII.GetString(linkedListNode.Value.decryption).Substring(0, 25) + "...";
756                        }
757                        else
758                        {
759                            dec = System.Text.Encoding.ASCII.GetString(linkedListNode.Value.decryption);
760                        }
761                       
762                        String key = linkedListNode.Value.key;
763                        double round = Math.Round(linkedListNode.Value.value, 2);
764                        String outp = i + ".:" + key + ":" + dec + "(" + round + ")";
765                        ((TranspositionAnalyserQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(outp);
766                        linkedListNode = linkedListNode.Next;
767                    }
768               
769                }
770
771
772                , null);
773               
774            }
775        }
776   
777    }
778
779    public struct ValueKey
780    {
781        public double value;
782        public String key;
783        public byte[] decryption;
784    };
785}
Note: See TracBrowser for help on using the repository browser.