source: trunk/CrypPlugins/KeySearcher/KeyPattern/KeyPattern.cs @ 2010

Last change on this file since 2010 was 2010, checked in by Sven Rech, 11 years ago

new key finding algorithm for KeySearcher

This update is really huge.

File size: 22.6 KB
Line 
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;
18using System.Text;
19using System.Collections;
20using System.IO;
21using System.Numerics;
22using System.Collections.Generic;
23
24namespace KeySearcher.KeyPattern
25{
26    public class KeyPattern
27    {       
28        private string pattern;
29        internal ArrayList wildcardList;
30
31        /// <summary>
32        /// Property for the WildCardKey. Could return null, if the KeyPattern isn't initialized correctly.
33        /// </summary>
34        public string WildcardKey
35        {
36            get
37            {
38                return getWildcardKey();
39            }
40            set
41            {
42                if (!testWildcardKey(value))
43                    throw new Exception("Invalid wildcard key!");
44                setWildcardKey(value);
45            }
46        }
47
48        public KeyPattern(string pattern)
49        {
50            if (!testPattern(pattern))
51                throw new Exception("Invalid pattern!");
52            this.pattern = pattern;
53        }       
54
55        public KeyPattern[] split()
56        {
57            KeyPattern[] patterns = new KeyPattern[2];
58            for (int i = 0; i < 2; i++)
59            {
60                patterns[i] = new KeyPattern(pattern);               
61                patterns[i].wildcardList = new ArrayList();
62            }
63            bool s = false;
64            for (int i = 0; i < wildcardList.Count; i++)
65            {
66                Wildcard wc = ((Wildcard)wildcardList[i]);
67                if (!s && (wc.size() - wc.count()) > 1)
68                {
69                    Wildcard[] wcs = wc.split();
70                    patterns[0].wildcardList.Add(wcs[0]);
71                    patterns[1].wildcardList.Add(wcs[1]);                   
72                    s = true;
73                }
74                else
75                {
76                    patterns[0].wildcardList.Add(new Wildcard(wc));
77                    Wildcard copy = new Wildcard(wc);
78                    if (s)
79                        copy.resetCounter();
80                    patterns[1].wildcardList.Add(copy);
81                }
82            }
83            if (!s)
84                return null;
85            return patterns;
86        }
87
88        public string giveInputPattern()
89        {
90            string res = "";
91            int i = 0;
92            while (i < pattern.Length)
93            {
94                if (pattern[i] != '[')
95                    res += pattern[i];
96                else
97                {
98                    res += '*';
99                    while (pattern[i] != ']')
100                        i++;
101                }
102                i++;
103            }
104            return res;
105        }
106
107        /**
108         * tests, if 'pattern' is a valid pattern.
109         **/
110        public static bool testPattern(string pattern)
111        {
112            int i = 0;
113            while (i < pattern.Length)
114            {
115                if (pattern[i] == '[')
116                {
117                    i++;
118                    while (pattern[i] != ']')
119                    {
120                        if (specialChar(pattern[i]))
121                            return false;
122                        if (pattern[i + 1] == '-')
123                        {
124                            if (specialChar(pattern[i]) || specialChar(pattern[i + 2]))
125                                return false;
126                            i += 2;
127                        }
128                        i++;
129                    }
130                }
131                i++;
132            }
133            return true;
134        }
135
136        private static bool specialChar(char p)
137        {
138            if (p == '-' || p == '[' || p == ']' || p == '*')
139                return true;
140            return false;
141        }
142
143        /**
144         * tests, if 'wildcardKey' matches 'pattern'.
145         **/
146        public static bool testWildcardKey(string wildcardKey, string pattern)
147        {
148            try
149            {
150                int kcount = 0;
151                int pcount = 0;
152                while (kcount < wildcardKey.Length && pcount < pattern.Length)
153                {
154                    if (pattern[pcount] != '[')
155                    {
156                        if (pattern[pcount] != wildcardKey[kcount])
157                            return false;
158                        kcount++;
159                        pcount++;
160                    }
161                    else
162                    {
163                        Wildcard wc1 = new Wildcard(pattern.Substring(pcount, pattern.IndexOf(']', pcount) + 1 - pcount));
164                        while (pattern[pcount++] != ']') ;
165                        Wildcard wc2 = null;
166                        if (wildcardKey[kcount] == '[')
167                        {
168                            wc2 = new Wildcard(wildcardKey.Substring(kcount, wildcardKey.IndexOf(']', kcount) + 1 - kcount));
169                            while (wildcardKey[++kcount] != ']') ;
170                        }
171                        else if (wildcardKey[kcount] != '*')
172                            wc2 = new Wildcard("" + wildcardKey[kcount]);
173
174                        if (!wc1.contains(wc2) && !(wildcardKey[kcount] == '*'))
175                            return false;
176                        kcount++;
177                    }
178                }
179                if (pcount != pattern.Length || kcount != wildcardKey.Length)
180                    return false;
181                return true;
182            }
183            catch (Exception)
184            {
185                return false;
186            }
187        }
188
189        public bool testWildcardKey(string wildcardKey)
190        {
191            return testWildcardKey(wildcardKey, pattern);
192        }
193
194        private void setWildcardKey(string wildcardKey)
195        {         
196            int pcount = 0;
197            wildcardList = new ArrayList();
198            int i = 0;
199            while (i < wildcardKey.Length)           
200            {
201                if (pattern[pcount] == '[')
202                {
203                    if (wildcardKey[i] == '*')
204                    {
205                        Wildcard wc = new Wildcard(pattern.Substring(pcount, pattern.IndexOf(']', pcount) + 1 - pcount));
206                        wildcardList.Add(wc);
207                      }
208                    else if (wildcardKey[i] == '[')
209                    {
210                        Wildcard wc = new Wildcard(wildcardKey.Substring(i, wildcardKey.IndexOf(']', i) + 1 - i));
211                        wildcardList.Add(wc);
212                        while (wildcardKey[++i] != ']') ;
213                    }
214                    else
215                    {
216                        Wildcard wc = new Wildcard("" + wildcardKey[i]);
217                        wildcardList.Add(wc);
218                    }
219                    while (pattern[++pcount] != ']') ;
220                }
221                pcount++;
222                i++;
223            }
224        }
225
226        private string getWildcardKey()
227        {
228            string res = "";
229            int pcount = 0;
230            int wccount = 0;
231
232            // error handling
233            if (wildcardList != null)
234            {
235                while (pcount < pattern.Length)
236                {
237                    if (pattern[pcount] != '[')
238                        res += pattern[pcount];
239                    else
240                    {
241                        res += ((Wildcard)wildcardList[wccount++]).getRepresentationString();
242                        while (pattern[++pcount] != ']') ;
243                    }
244                    pcount++;
245                }
246                return res;
247            }
248            else
249                return null;
250        }
251
252        public BigInteger size()
253        {
254            if (wildcardList == null)
255                return 0;
256            BigInteger counter = 1;
257            foreach (Wildcard wc in wildcardList)
258                counter *= wc.size();
259            return counter;
260        }
261
262        /* used to jump to the next key.         
263         * if nextWildcard == -1, we return false
264         * if nextWildcard == -2, we return true
265         * if nextWildcard == -3, we increase the rightmost wildcard
266         * if nextWildcard >= 0, we increase the wildcard on the position 'nextWildcard'
267         * returns false if there is no key left.
268         */
269        public bool nextKey(int nextWildcard)
270        {
271            if (nextWildcard == -2)
272                return true;
273            if (nextWildcard == -1)
274                return false;
275
276            int wildcardCount;
277            if (nextWildcard == -3)
278                wildcardCount = wildcardList.Count - 1;
279            else
280                wildcardCount = nextWildcard;
281           
282            bool overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
283            while (overflow && (wildcardCount >= 0))
284                overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
285
286            return !overflow;
287        }
288
289        /** used to jump to the next key.
290         */
291        public bool nextKey()
292        {
293            return nextKey(-3);
294        }
295
296        /// <summary>
297        /// Moves the key "add" steps further.
298        /// So, addKey(1) would behave the same as nextKey().
299        /// </summary>
300        /// <param name="add"></param>
301        /// <returns>false, if there are no keys left</returns>
302        public bool addKey(int add)
303        {
304            int i = wildcardList.Count - 1;
305            int carry = add;
306
307            while (carry != 0 && i >= 0)
308            {
309                carry = ((Wildcard)wildcardList[i--]).add(carry);
310            }
311
312            return (i >= 0);
313        }
314
315        public string getKey()
316        {
317            string res = "";
318            int wildcardCount = 0;
319            int i = 0;
320            while (i < pattern.Length)           
321            {
322                if (pattern[i] != '[')
323                    res += pattern[i++];
324                else
325                {
326                    Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
327                    res += wc.getChar();
328                    while (pattern[i++] != ']') ;
329                }               
330            }
331            return res;
332        }
333
334        public string getKey(int add)
335        {
336            string res = "";
337            int div = 1;
338            int wildcardCount = wildcardList.Count - 1;
339            int i = pattern.Length - 1;
340            while (i >= 0)           
341            {
342                if (pattern[i] != ']')
343                    res += pattern[i--];
344                else
345                {
346                    Wildcard wc = (Wildcard)wildcardList[wildcardCount--];
347                    if (add < div)
348                        res += wc.getChar();
349                    else
350                    {
351                        res += wc.getChar((add / div) % wc.size());
352                        div *= wc.size();
353                    }
354                    while (pattern[i--] != '[') ;
355                }
356            }
357            char[] r = res.ToCharArray();
358            Array.Reverse(r);
359            return new string(r);
360        }
361
362        /// <summary>
363        /// Returns the progress of each relevant wildcard.
364        /// </summary>
365        /// <returns></returns>
366        internal int[] getWildcardProgress()
367        {
368            int arraySize = 0;
369            foreach (Wildcard wc in this.wildcardList)
370                if (wc.getLength() > 1)
371                    arraySize++;
372
373            int[] result = new int[arraySize];
374
375            int i = 0;
376            for (int c = 0; c < wildcardList.Count; c++)
377            {
378                if (((Wildcard)this.wildcardList[c]).getLength() > 1)
379                    result[i++] = ((Wildcard)wildcardList[c]).count();
380            }
381
382            return result;
383        }
384
385        /// <summary>
386        /// returns the "movements" of the key, i.e. how each relevant wildcard has to be "rotated" to produce the next key.
387        /// </summary>
388        /// <returns></returns>
389        public KeyMovement[] getKeyMovements()
390        {
391            KeyPattern fullKeyPattern = new KeyPattern(pattern);
392            fullKeyPattern.WildcardKey = pattern;
393
394            int arraySize = 0;
395            foreach (Wildcard wc in this.wildcardList)
396                if (wc.getLength() > 1)
397                    arraySize++;
398
399            KeyMovement[] result = new KeyMovement[arraySize];
400
401            int c = 0;
402            for (int i = 0; i < wildcardList.Count; i++)
403            {
404                if (((Wildcard)this.wildcardList[i]).getLength() > 1)
405                {
406                    result[c] = getWildcardMovement((Wildcard)this.wildcardList[i], (Wildcard)fullKeyPattern.wildcardList[i]);
407                    c++;
408                }
409            }
410
411            return result;
412        }
413
414        /// <summary>
415        /// Compares "wildcard" with "fullwildcard" and returns the movement of "wildcard", i.e. which intervals exists between the elements of "wildcard".       
416        /// </summary>
417        /// <param name="wildcard"></param>
418        /// <param name="fullwildcard"></param>
419        /// <returns>The movements</returns>
420        private KeyMovement getWildcardMovement(Wildcard wildcard, Wildcard fullwildcard)
421        {
422            //check if linear:
423            int a;
424            int b;
425
426
427            int i = 0;
428            while (fullwildcard.getChars()[i] != wildcard.getChars()[0])
429                i++;
430
431            b = i;
432            i++;
433
434            while (fullwildcard.getChars()[i] != wildcard.getChars()[1])
435                i++;
436
437            a = i-b;
438           
439            bool linear = true;
440            for (int c = 0; c < wildcard.getLength(); c++)
441            {
442                if (fullwildcard.getChars()[c * a + b] != wildcard.getChars()[c])
443                {
444                    linear = false;
445                    break;
446                }
447            }
448
449            if (linear)
450            {
451                return new LinearKeyMovement(a, b, wildcard.getLength());
452            }
453
454            //not linear, so just list the intervals:
455            List<int> intervalList = new List<int>();
456
457            for (int c = 0; c < wildcard.getLength(); c++)
458            {
459                for (int x = 0; x < fullwildcard.getLength(); x++)
460                {
461                    if (fullwildcard.getChars()[x] == wildcard.getChars()[c])
462                        intervalList.Add(x);
463                }
464            }
465
466            return new IntervalKeyMovement(intervalList);
467        }
468
469        public KeyPattern(byte[] serializedPattern)
470        {
471            KeyPattern deserializedPattern = Deserialize(serializedPattern);
472            // set deserialized Pattern to actual pattern
473            this.pattern = deserializedPattern.pattern;
474            this.WildcardKey = deserializedPattern.WildcardKey;
475            //this.wildcardList = deserializedPattern.wildcardList;
476            if (deserializedPattern == null)
477                throw new Exception("Invalid byte[] representation of KeyPattern!");
478        }
479
480        /// <summary>
481        /// returns type, key and pattern. If you want to get only the pattern for processing use GetPattern-method!
482        /// </summary>
483        /// <returns></returns>
484        public override string ToString()
485        {
486            if(this.WildcardKey != null)
487                return "Type: KeySearcher.KeyPattern. WildcardKey: '" + this.WildcardKey + "', Pattern: '" + this.pattern + "'";
488            else
489                return "Type: KeySearcher.KeyPattern. KeyPattern isn't initialized correctly, Pattern: '" + this.pattern + "'";
490        }
491
492        /// <summary>
493        /// returns ONLY the pattern as a string!
494        /// </summary>
495        /// <returns></returns>
496        public string GetPattern()
497        {
498            return this.pattern;
499        }
500
501        #region Serialization methods and auxiliary variables
502
503        /* Serialization information:
504         * 1st byte: Byte-Length of the WildCardKey
505         * 2nd - wildcardLen: WildCardKey Byte representation
506         * wildcardLen + 1: Byte-Length of the Pattern
507         * wildcardLen + 2 - wildcardLen+2+patternLen: Pattern Byte representation
508         *  -------------------------------------------------------------
509         * | wildcardkey length | wildcardkey | pattern length | pattern |
510         *  -------------------------------------------------------------  */
511        private Encoding encoder = UTF8Encoding.UTF8;
512
513        /// <summary>
514        /// Serialize all needful information to rebuild the existing pattern elsewhere
515        /// </summary>
516        /// <returns>byte representation of all the needful information of the actual KeyPattern</returns>
517        public byte[] Serialize()
518        {
519            byte[] retByte;
520            string wildcardKey = this.WildcardKey;
521            if (wildcardKey != null && this.pattern != null)
522            {
523                if (testWildcardKey(wildcardKey))
524                {
525                    byte[] byteWildCard = encoder.GetBytes(wildcardKey);
526                    byte[] bytePattern = encoder.GetBytes(pattern);
527                    byte[] byteWildCardLen = BitConverter.GetBytes(byteWildCard.Length);
528                    byte[] bytePatternLen = BitConverter.GetBytes(bytePattern.Length);
529                    MemoryStream memStream = new MemoryStream();
530                    try
531                    {
532                        memStream.Write(byteWildCardLen, 0, byteWildCardLen.Length);
533                        memStream.Write(byteWildCard, 0, byteWildCard.Length);
534                        memStream.Write(bytePatternLen, 0, bytePatternLen.Length);
535                        memStream.Write(bytePattern, 0, bytePattern.Length);
536                        retByte = memStream.ToArray();
537                    }
538                    catch (Exception ex)
539                    {
540                        throw ex;
541                    }
542                    finally
543                    {
544                        memStream.Flush();
545                        memStream.Close();
546                        memStream.Dispose();
547                    }
548                    //retByte = new byte[byteWildCardLen.Length + byteWildCard.Length + bytePatternLen.Length + bytePattern.Length];
549                    //Buffer.BlockCopy(byteWildCardLen, 0, retByte, 0, byteWildCardLen.Length);
550                    //Buffer.BlockCopy(byteWildCard, 0, retByte, byteWildCard.Length, byteWildCard.Length);
551                    //retByte[byteWildCard.Length + 1] = (byte)bytePattern.Length;
552                    //Buffer.BlockCopy(bytePattern, 0, retByte, byteWildCard.Length + 2, bytePattern.Length);
553                }
554                else
555                {
556                    throw (new Exception("Serializing KeyPattern canceled, because WildcardKey and/or Pattern aren't valid. "
557                        + "WildcardKey: '" + wildcardKey + "', Pattern: '" + pattern + "'.\n"));
558                }
559            }
560            else
561            {
562                throw (new Exception("Serializing KeyPattern canceled, because Key and/or Pattern are NULL. WildcardKey: '" + wildcardKey + "'. Pattern: '" + pattern + "'."));
563            }
564            return retByte;
565        }
566
567        /// <summary>
568        /// Deserialize a byte-representation of an KeyPattern object. Returns a full-initialized KeyPattern object.
569        /// </summary>
570        /// <param name="serializedPattern">byte-representation of an keypattern object</param>
571        /// <returns>a full-initialized KeyPattern object</returns>
572        public KeyPattern Deserialize(byte[] serializedPattern)
573        {
574            KeyPattern keyPatternToReturn;
575            string wildcardKey_temp;
576            string pattern_temp;
577
578            MemoryStream memStream = new MemoryStream(serializedPattern);
579            try
580            {
581                /* So i always have the same byte length for int32 values */
582                int iTest = 500;
583                int int32ByteLen = BitConverter.GetBytes(iTest).Length;
584
585                // Wildcard length and value
586                byte[] byteLen = new byte[int32ByteLen];
587                memStream.Read(byteLen, 0, byteLen.Length);
588                byte[] byteWildcard = new byte[BitConverter.ToInt32(byteLen, 0)];
589                memStream.Read(byteWildcard, 0, byteWildcard.Length);
590
591                wildcardKey_temp = encoder.GetString(byteWildcard, 0, byteWildcard.Length);
592
593
594                // Pattern length and value
595                memStream.Read(byteLen, 0, byteLen.Length);
596                byte[] bytePattern = new byte[BitConverter.ToInt32(byteLen, 0)];
597                memStream.Read(bytePattern, 0, bytePattern.Length);
598
599                pattern_temp = encoder.GetString(bytePattern, 0, bytePattern.Length);
600
601            }
602            catch (Exception ex)
603            {
604                throw ex;
605            }
606            finally
607            {
608                memStream.Flush();
609                memStream.Close();
610                memStream.Dispose();
611            }
612
613            //int iWildCardLen = serializedPattern[0];
614            //wildcardKey_temp = encoder.GetString(serializedPattern, 1, iWildCardLen);
615            //int iPatternLen = serializedPattern[iWildCardLen + 1];
616            //pattern_temp = encoder.GetString(serializedPattern, iWildCardLen + 2, iPatternLen);
617
618            keyPatternToReturn = new KeyPattern(pattern_temp);
619            // test extracted pattern and wildcardKey!
620            if (keyPatternToReturn.testWildcardKey(wildcardKey_temp))
621            {
622                keyPatternToReturn.WildcardKey = wildcardKey_temp;
623                return keyPatternToReturn;
624            }
625            else
626            {
627                throw (new Exception("Deserializing KeyPattern canceled, because WildcardKey or Pattern aren't valid. "
628                    + "WildcardKey: '" + wildcardKey_temp + "', Pattern: '" + pattern_temp + "'.\n"));
629            }
630        }
631
632        #endregion
633
634    }
635}
Note: See TracBrowser for help on using the repository browser.