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

Last change on this file since 1284 was 1284, checked in by weyers, 12 years ago

TranspositionAnalyserQuickWatchPresentation reacts on doubleclick. scaling optmized

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