Changeset 908


Ignore:
Timestamp:
Nov 27, 2009, 8:30:03 PM (12 years ago)
Author:
Sven Rech
Message:

some keysearcher cleanup

Location:
trunk/CrypPlugins/KeySearcher
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/KeySearcher/KeyPattern.cs

    r906 r908  
    1 using System;
     1/*                             
     2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
     3
     4   Licensed under the Apache License, Version 2.0 (the "License");
     5   you may not use this file except in compliance with the License.
     6   You may obtain a copy of the License at
     7
     8       http://www.apache.org/licenses/LICENSE-2.0
     9
     10   Unless required by applicable law or agreed to in writing, software
     11   distributed under the License is distributed on an "AS IS" BASIS,
     12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13   See the License for the specific language governing permissions and
     14   limitations under the License.
     15*/
     16
     17using System;
    218using System.Collections.Generic;
    319using System.Linq;
  • trunk/CrypPlugins/KeySearcher/KeySearcher.cs

    r905 r908  
    8888        }
    8989
     90        #region code for the worker threads
    9091        private void KeySearcherJob(object param)
    9192        {
     
    288289        }
    289290
     291        #endregion
     292
    290293        public void process(IControlEncryption sender)
    291294        {
    292             if (sender != null && costMaster != null)
    293             {
    294                 int maxInList = 10;
    295                 LinkedList<ValueKey> costList = new LinkedList<ValueKey>();
    296                 ValueKey valueKey = new ValueKey();
    297                 if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
    298                     valueKey.value = double.MaxValue;
    299                 else
    300                     valueKey.value = double.MinValue;
    301                 valueKey.key = "dummykey";
    302                 valueKey.decryption = new byte[0];
    303                 value_threshold = valueKey.value;
    304                 LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
    305                 for (int i = 1; i < maxInList; i++)
    306                 {
    307                     node = costList.AddAfter(node, valueKey);
    308                 }
    309 
    310                 stop = false;
    311                 if (!Pattern.testKey(settings.Key))
    312                 {
    313                     GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
    314                     return;
    315                 }
    316 
    317                 int bytesToUse = 0;
    318 
    319                 try
    320                 {
    321                     bytesToUse = CostMaster.getBytesToUse();
    322                 }
    323                 catch (Exception ex)
    324                 {
    325                     GuiLogMessage("Bytes used not valid: " + ex.Message, NotificationLevel.Error);
    326                     return;
    327                 }
    328 
    329                 LinkedListNode<ValueKey> linkedListNode;
    330 
    331                 KeyPattern[] patterns = new KeyPattern[settings.CoresUsed+1];
    332                 BigInteger size = Pattern.initKeyIteration(settings.Key);
    333                
    334                 if (settings.CoresUsed > 0)
    335                 {
    336                     KeyPattern[] patterns2 = Pattern.split();                   
    337                     patterns[0] = patterns2[0];
    338                     patterns[1] = patterns2[1];
    339                     int p = 1;
    340                     int threads = settings.CoresUsed - 1;
    341                     while (threads > 0)
    342                     {
    343                         int maxPattern = -1;
    344                         BigInteger max = 0;
    345                         for (int i = 0; i <= p; i++)
    346                             if (patterns[i].size() > max)
    347                             {
    348                                 max = patterns[i].size();
    349                                 maxPattern = i;
    350                             }
    351                         KeyPattern[] patterns3 = patterns[maxPattern].split();
    352                         patterns[maxPattern] = patterns3[0];
    353                         patterns[++p] = patterns3[1];
    354                         threads--;
    355                     }
    356                 }
    357                 else
    358                     patterns[0] = Pattern;
    359 
    360                 valuequeue = Queue.Synchronized(new Queue());
    361 
    362                 BigInteger[] doneKeysA = new BigInteger[patterns.Length];
    363                 BigInteger[] keycounters = new BigInteger[patterns.Length];
    364                 BigInteger[] keysleft = new BigInteger[patterns.Length];
    365                 Stack threadStack = Stack.Synchronized(new Stack());
    366                 for (int i = 0; i < patterns.Length; i++)
    367                 {
    368                     WaitCallback worker = new WaitCallback(KeySearcherJob);
    369                     doneKeysA[i] = new BigInteger();
    370                     keycounters[i] = new BigInteger();
    371                     ThreadPool.QueueUserWorkItem(worker, new object[] { patterns, i, doneKeysA, keycounters, keysleft, sender.clone(), bytesToUse, threadStack });
    372                 }
    373                
    374                 //update message:
    375                 while (!stop)
    376                 {
    377                     Thread.Sleep(1000);
    378 
    379                     //update toplist:
    380                     while (valuequeue.Count != 0)
    381                     {
    382                         ValueKey vk = (ValueKey)valuequeue.Dequeue();
    383                         if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
    384                         {
    385                             if (vk.value > costList.Last().value)
    386                             {
    387                                 node = costList.First;
    388                                 while (node != null)
    389                                 {
    390                                     if (vk.value > node.Value.value)
    391                                     {
    392                                         costList.AddBefore(node, vk);
    393                                         costList.RemoveLast();
    394                                         value_threshold = costList.Last.Value.value;
    395                                         break;
    396                                     }
    397                                     node = node.Next;
    398                                 }//end while
    399                             }//end if
    400                         }
    401                         else
    402                         {
    403                             node = costList.First;
    404                             if (vk.value < costList.Last().value)
    405                             {
    406                                 while (node != null)
    407                                 {
    408                                     if (vk.value < node.Value.value)
    409                                     {
    410                                         costList.AddBefore(node, vk);
    411                                         costList.RemoveLast();
    412                                         value_threshold = costList.Last.Value.value;
    413                                         break;
    414                                     }
    415                                     node = node.Next;
    416                                 }//end while
    417                             }//end if
    418                         }
    419                     }
    420 
    421                     BigInteger keycounter = 0;
    422                     BigInteger doneKeys = 0;
    423                     foreach (BigInteger dk in doneKeysA)
    424                         doneKeys += dk;
    425                     foreach (BigInteger kc in keycounters)
    426                         keycounter += kc;
    427 
    428                     if (keycounter > size)
    429                         GuiLogMessage("There must be an error, because we bruteforced too much keys...", NotificationLevel.Error);
    430 
    431                     //Let's determine which thread has the most keys to share:
    432                     if (size - keycounter > 1000)
    433                     {
    434                         maxThreadMutex.WaitOne();
    435                         BigInteger max = 0;
    436                         int id = -1;
    437                         for (int i = 0; i < patterns.Length; i++)
    438                             if (keysleft[i] > max)
    439                             {
    440                                 max = keysleft[i];
    441                                 id = i;
    442                             }
    443                         maxThread = id;
    444                         maxThreadMutex.ReleaseMutex();
    445                     }
    446                                        
    447                     ProgressChanged(Math.Pow(10, keycounter.log(10) - size.log(10)), 1.0);
    448 
    449                     if (QuickWatchPresentation.IsVisible && doneKeys != 0 && !stop)
    450                     {
    451                         double time = (Math.Pow(10, (size - keycounter).log(10) - doneKeys.log(10)));
    452                         TimeSpan timeleft = new TimeSpan(-1);
    453 
    454                         try
    455                         {
    456                             if (time / (24 * 60 * 60) <= int.MaxValue)
    457                             {
    458                                 int days = (int)(time / (24 * 60 * 60));
    459                                 time = time - (days * 24 * 60 * 60);
    460                                 int hours = (int)(time / (60 * 60));
    461                                 time = time - (hours * 60 * 60);
    462                                 int minutes = (int)(time / 60);
    463                                 time = time - (minutes * 60);
    464                                 int seconds = (int)time;
    465 
    466                                 timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
    467                             }
    468                         }
    469                         catch
    470                         {
    471                             //can not calculate time span
    472                         }
    473 
    474                         ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
    475                         {
    476                             ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).keysPerSecond.Text = "" + doneKeys;
    477                             if (timeleft != new TimeSpan(-1))
    478                             {
    479                                 ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "" + timeleft;
    480                                 try
    481                                 {
    482                                     ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "" + DateTime.Now.Add(timeleft);
    483                                 }
    484                                 catch
    485                                 {
    486                                     ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
    487                                 }
    488                             }
    489                             else
    490                             {
    491                                 ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "incalculable :-)";
    492                                 ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
    493                             }
    494 
    495                             ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
    496                             linkedListNode = costList.First;
    497                             System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
    498                             int i = 0;
    499                             while (linkedListNode != null)
    500                             {
    501                                 i++;
    502                                 ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
    503                                     enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
    504                                 linkedListNode = linkedListNode.Next;
    505                             }
    506                         }
    507                         , null);
    508                     }//end if
    509                     doneKeys = 0;
    510                     for (int i = 0; i < doneKeysA.Length; i++)
    511                         doneKeysA[i] = 0;
    512 
    513                     if (!stop && QuickWatchPresentation.IsVisible)
    514                     {
    515 
    516                         ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
    517                         {
    518                             ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
    519                             linkedListNode = costList.First;
    520                             System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
    521                             int i = 0;
    522                             while (linkedListNode != null)
    523                             {
    524                                 i++;
    525                                 ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
    526                                     enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
    527                                 linkedListNode = linkedListNode.Next;
    528                             }
    529                         }
    530                         , null);
    531                     }
    532 
    533                     if (keycounter >= size)
    534                         break;
    535                 }//end while
    536 
    537                 //wake up all sleeping threads:
    538                 while (threadStack.Count != 0)
    539                     ((ThreadStackElement)threadStack.Pop()).ev.Set();
    540             }//end if
     295            if (sender == null || costMaster == null)
     296                return;
     297            bruteforcePattern(Pattern, sender);
     298        }
     299
     300        private void bruteforcePattern(KeyPattern pattern, IControlEncryption sender)
     301        {
     302            int maxInList = 10;
     303            LinkedList<ValueKey> costList = new LinkedList<ValueKey>();
     304            fillListWithDummies(maxInList, costList);
     305
     306            stop = false;
     307            if (!pattern.testKey(settings.Key))
     308            {
     309                GuiLogMessage("Wrong key pattern!", NotificationLevel.Error);
     310                return;
     311            }
     312
     313            int bytesToUse = 0;
     314
     315            try
     316            {
     317                bytesToUse = CostMaster.getBytesToUse();
     318            }
     319            catch (Exception ex)
     320            {
     321                GuiLogMessage("Bytes used not valid: " + ex.Message, NotificationLevel.Error);
     322                return;
     323            }
     324
     325            BigInteger size = pattern.initKeyIteration(settings.Key);
     326            KeyPattern[] patterns = splitPatternForThreads(pattern);
     327
     328            valuequeue = Queue.Synchronized(new Queue());
     329
     330            BigInteger[] doneKeysA = new BigInteger[patterns.Length];
     331            BigInteger[] keycounters = new BigInteger[patterns.Length];
     332            BigInteger[] keysleft = new BigInteger[patterns.Length];
     333            Stack threadStack = Stack.Synchronized(new Stack());
     334            startThreads(sender, bytesToUse, patterns, doneKeysA, keycounters, keysleft, threadStack);
     335
     336            //update message:
     337            while (!stop)
     338            {
     339                Thread.Sleep(1000);
     340
     341                updateToplist(costList);
     342
     343                #region calculate global counters from local counters
     344                BigInteger keycounter = 0;
     345                BigInteger doneKeys = 0;
     346                foreach (BigInteger dk in doneKeysA)
     347                    doneKeys += dk;
     348                foreach (BigInteger kc in keycounters)
     349                    keycounter += kc;
     350                #endregion
     351
     352                if (keycounter > size)
     353                    GuiLogMessage("There must be an error, because we bruteforced too much keys...", NotificationLevel.Error);
     354
     355                #region determination of the thread with most keys
     356                if (size - keycounter > 1000)
     357                {
     358                    maxThreadMutex.WaitOne();
     359                    BigInteger max = 0;
     360                    int id = -1;
     361                    for (int i = 0; i < patterns.Length; i++)
     362                        if (keysleft[i] > max)
     363                        {
     364                            max = keysleft[i];
     365                            id = i;
     366                        }
     367                    maxThread = id;
     368                    maxThreadMutex.ReleaseMutex();
     369                }
     370                #endregion
     371
     372                showProgress(costList, size, keycounter, doneKeys);
     373
     374                #region set doneKeys to 0
     375                doneKeys = 0;
     376                for (int i = 0; i < doneKeysA.Length; i++)
     377                    doneKeysA[i] = 0;
     378                #endregion
     379
     380                if (keycounter >= size)
     381                    break;
     382            }//end while
     383
     384            //wake up all sleeping threads, so they can stop:
     385            while (threadStack.Count != 0)
     386                ((ThreadStackElement)threadStack.Pop()).ev.Set();
    541387
    542388            if (!stop)
    543389                ProgressChanged(1, 1);
     390        }
     391
     392        private void fillListWithDummies(int maxInList, LinkedList<ValueKey> costList)
     393        {
     394            ValueKey valueKey = new ValueKey();
     395            if (this.costMaster.getRelationOperator() == RelationOperator.LessThen)
     396                valueKey.value = double.MaxValue;
     397            else
     398                valueKey.value = double.MinValue;
     399            valueKey.key = "dummykey";
     400            valueKey.decryption = new byte[0];
     401            value_threshold = valueKey.value;
     402            LinkedListNode<ValueKey> node = costList.AddFirst(valueKey);
     403            for (int i = 1; i < maxInList; i++)
     404            {
     405                node = costList.AddAfter(node, valueKey);
     406            }
     407        }
     408
     409        private void showProgress(LinkedList<ValueKey> costList, BigInteger size, BigInteger keycounter, BigInteger doneKeys)
     410        {
     411            LinkedListNode<ValueKey> linkedListNode;
     412            ProgressChanged(Math.Pow(10, keycounter.log(10) - size.log(10)), 1.0);
     413
     414            if (QuickWatchPresentation.IsVisible && doneKeys != 0 && !stop)
     415            {
     416                double time = (Math.Pow(10, (size - keycounter).log(10) - doneKeys.log(10)));
     417                TimeSpan timeleft = new TimeSpan(-1);
     418
     419                try
     420                {
     421                    if (time / (24 * 60 * 60) <= int.MaxValue)
     422                    {
     423                        int days = (int)(time / (24 * 60 * 60));
     424                        time = time - (days * 24 * 60 * 60);
     425                        int hours = (int)(time / (60 * 60));
     426                        time = time - (hours * 60 * 60);
     427                        int minutes = (int)(time / 60);
     428                        time = time - (minutes * 60);
     429                        int seconds = (int)time;
     430
     431                        timeleft = new TimeSpan(days, hours, minutes, (int)seconds, 0);
     432                    }
     433                }
     434                catch
     435                {
     436                    //can not calculate time span
     437                }
     438
     439                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
     440                {
     441                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).keysPerSecond.Text = "" + doneKeys;
     442                    if (timeleft != new TimeSpan(-1))
     443                    {
     444                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "" + timeleft;
     445                        try
     446                        {
     447                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "" + DateTime.Now.Add(timeleft);
     448                        }
     449                        catch
     450                        {
     451                            ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
     452                        }
     453                    }
     454                    else
     455                    {
     456                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).timeLeft.Text = "incalculable :-)";
     457                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).endTime.Text = "in a galaxy far, far away...";
     458                    }
     459
     460                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
     461                    linkedListNode = costList.First;
     462                    System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
     463                    int i = 0;
     464                    while (linkedListNode != null)
     465                    {
     466                        i++;
     467                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
     468                            enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
     469                        linkedListNode = linkedListNode.Next;
     470                    }
     471                }
     472                , null);
     473            }//end if
     474
     475
     476            if (!stop && QuickWatchPresentation.IsVisible)
     477            {
     478
     479                ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
     480                {
     481                    ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Clear();
     482                    linkedListNode = costList.First;
     483                    System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
     484                    int i = 0;
     485                    while (linkedListNode != null)
     486                    {
     487                        i++;
     488                        ((KeySearcherQuickWatchPresentation)QuickWatchPresentation).listbox.Items.Add(i + ") " + Math.Round(linkedListNode.Value.value, 4) + " = " + linkedListNode.Value.key + " : \"" +
     489                            enc.GetString(linkedListNode.Value.decryption).Replace("\n", "").Replace("\r", "").Replace("\t", "") + "\"");
     490                        linkedListNode = linkedListNode.Next;
     491                    }
     492                }
     493                , null);
     494            }
     495        }
     496
     497        private void updateToplist(LinkedList<ValueKey> costList)
     498        {
     499            LinkedListNode<ValueKey> node;
     500            while (valuequeue.Count != 0)
     501            {
     502                ValueKey vk = (ValueKey)valuequeue.Dequeue();
     503                if (this.costMaster.getRelationOperator() == RelationOperator.LargerThen)
     504                {
     505                    if (vk.value > costList.Last().value)
     506                    {
     507                        node = costList.First;
     508                        while (node != null)
     509                        {
     510                            if (vk.value > node.Value.value)
     511                            {
     512                                costList.AddBefore(node, vk);
     513                                costList.RemoveLast();
     514                                value_threshold = costList.Last.Value.value;
     515                                break;
     516                            }
     517                            node = node.Next;
     518                        }//end while
     519                    }//end if
     520                }
     521                else
     522                {                   
     523                    if (vk.value < costList.Last().value)
     524                    {
     525                        node = costList.First;
     526                        while (node != null)
     527                        {
     528                            if (vk.value < node.Value.value)
     529                            {
     530                                costList.AddBefore(node, vk);
     531                                costList.RemoveLast();
     532                                value_threshold = costList.Last.Value.value;
     533                                break;
     534                            }
     535                            node = node.Next;
     536                        }//end while
     537                    }//end if
     538                }
     539            }
     540        }
     541
     542        private void startThreads(IControlEncryption sender, int bytesToUse, KeyPattern[] patterns, BigInteger[] doneKeysA, BigInteger[] keycounters, BigInteger[] keysleft, Stack threadStack)
     543        {
     544            for (int i = 0; i < patterns.Length; i++)
     545            {
     546                WaitCallback worker = new WaitCallback(KeySearcherJob);
     547                doneKeysA[i] = new BigInteger();
     548                keycounters[i] = new BigInteger();
     549                ThreadPool.QueueUserWorkItem(worker, new object[] { patterns, i, doneKeysA, keycounters, keysleft, sender.clone(), bytesToUse, threadStack });
     550            }
     551        }
     552
     553        private KeyPattern[] splitPatternForThreads(KeyPattern pattern)
     554        {
     555            KeyPattern[] patterns = new KeyPattern[settings.CoresUsed + 1];
     556            if (settings.CoresUsed > 0)
     557            {
     558                KeyPattern[] patterns2 = pattern.split();
     559                patterns[0] = patterns2[0];
     560                patterns[1] = patterns2[1];
     561                int p = 1;
     562                int threads = settings.CoresUsed - 1;
     563                while (threads > 0)
     564                {
     565                    int maxPattern = -1;
     566                    BigInteger max = 0;
     567                    for (int i = 0; i <= p; i++)
     568                        if (patterns[i].size() > max)
     569                        {
     570                            max = patterns[i].size();
     571                            maxPattern = i;
     572                        }
     573                    KeyPattern[] patterns3 = patterns[maxPattern].split();
     574                    patterns[maxPattern] = patterns3[0];
     575                    patterns[++p] = patterns3[1];
     576                    threads--;
     577                }
     578            }
     579            else
     580                patterns[0] = Pattern;
     581            return patterns;
    544582        }
    545583
     
    654692        }
    655693
     694        //used for delivering the results from the worker threads to the main thread:
    656695        private struct ValueKey
    657696        {
Note: See TracChangeset for help on using the changeset viewer.