Ignore:
Timestamp:
Jul 20, 2009, 3:05:05 PM (13 years ago)
Author:
Danail Vazov
Message:

Added algorithm for internal key length analysis and the respective setting for switching between internal and external analysis of the key length.

Location:
trunk/CrypPlugins/VigenereAnalyser
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/VigenereAnalyser/VigenereAnalyser.cs

    r388 r390  
    2424    public class VigenereAnalyser:IStatistic
    2525    {
     26        public string cipherText;
     27        public double sequenceIC;
     28        public int RC_keyLength;
    2629        public int shiftKey = 0;
    2730        private double[] elf;
     
    129132            }
    130133            int textLength=0;
    131             List<int> observedFrequencies = new List<int>();
     134            List<double> observedFrequencies = new List<double>();
    132135            freqStats.ForEach(delegate(Stats s)
    133136            {
     
    139142                char []check =new char[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    140143                int l = 0;
     144                int c = 0;
     145               
    141146                for (int t = 0; t <= check.Length - 1;t++ )
    142147                {
    143                        
    144                         if (l <= freqStats.Count - 1)
    145                         {
    146                             Stats r = freqStats.ElementAt(l);
    147                             if (check[t] == r.letter)
    148                             {
    149                                 observedFrequencies.Add(r.absoluteFrequency);
    150                                 l++;
    151                             }
    152                             else
    153                             {
    154                                 observedFrequencies.Add(0);
    155                             }
     148
     149                    if (c <= freqStats.Count - 1)
     150                    {
     151                       
     152                        Stats r = freqStats.ElementAt(c);
     153                        if (check[t] == r.letter)
     154                        {
     155                            observedFrequencies.Add(r.relativeFrequency);
     156                            l++;
     157                            c++;
    156158                        }
    157159                        else
    158160                        {
    159                             observedFrequencies.Add(0);
    160                         }
    161                 }
    162             }
    163             List<double> correctedFrequencies = new List<double>();
    164             foreach (double d in expectedFrequencies)
    165             {   
    166                 correctedFrequencies.Add((d / 100) * textLength);
    167             }
    168             double [] eFrequencies = correctedFrequencies.ToArray();
    169             //int[] oFrequencies = observedFrequencies.ToArray();
     161                            observedFrequencies.Add(0.0);
     162                            l--;
     163                        }
     164                    }
     165                    else
     166                    {
     167                        observedFrequencies.Add(0.0);
     168                    }
     169                }
     170            }
    170171            double [] chiStats = new double[26];
    171             foreach (int f in observedFrequencies)
     172            for (int y = 0; y <= observedFrequencies.Count - 1;y++)
    172173            {
    173174                double chi = 0;
    174175                double chiS = 0;
    175                 int g = observedFrequencies.IndexOf(f);
    176176                for (int j = 0; j <= 25; j++)
    177177                {
    178                     int n = g + j;
    179                     if (n == 25||n>25)
     178                    int n = y + j;
     179                    if (n > 25)
    180180                    {
    181181                        n = n - 25;
    182182                    }
    183                     chi = observedFrequencies[n];
     183                    chi = observedFrequencies[n]-expectedFrequencies[y];
    184184                    chiS = Math.Pow(chi, 2);
    185                     chiS = chiS / eFrequencies[g];
     185                    chiS = chiS / expectedFrequencies[y];
    186186                    chiStats[j] += chiS;
    187187                }
    188             }
     188               
     189
     190            }
     191            shiftKey = 0;
     192            int b=0;
     193            foreach (double k in chiStats)
     194            {
     195                 if (chiStats[b]<chiStats[shiftKey] )
     196                 {
     197                     shiftKey = b;
     198                 }
     199                 b++;
     200             }
     201             return shiftKey;
     202
     203
     204        }
     205
     206        private double seqIC (int d)
     207        {
     208            int j=0;
     209            char[] cText = cipherText.ToCharArray();
     210            int n = cText.Length;
     211            int[] freq = new int[26];
     212            int length = 0;
     213            double[] IC = new double[d];
     214            double sum,sum1;
     215            char checkChar = 'a';
     216            for (int i = 0; i < d; i++)
     217            {
     218                for(int y=0;y<=freq.Length-1;y++)
     219                {
     220                    freq[y] = 0;
     221                }
     222                j=1;
     223                int index=d*(j-1)+i;
     224                do
     225                {
     226                    freq[cText[index]-checkChar]+=1;
     227                    j++;
     228                }
     229                while((index=d*(j-1)+i)<n);
     230                length = j-1;
     231                sum = 0.0;
     232                for (int f = 0; f < 26; f++)
     233                {
     234                    sum += freq[f] * (freq[f] - 1);
     235                }
     236                IC[i] = sum / (length*(length-1));
     237               
     238            }
     239            sum1 = 0.0;
     240            for (int k = 0; k < d; k++)
     241            {
     242               sum1 += Math.Pow((IC[k] - 0.066), 2);
     243            }
     244            return sequenceIC = Math.Sqrt((sum1 / d));
    189245           
    190             foreach (double k in chiStats)
    191             {   
    192                 shiftKey=Array.IndexOf(chiStats , k);
    193                 for (int l = Array.IndexOf(chiStats, k) + 1; l < chiStats.Length; l++)
    194                 {
    195                     if (chiStats[l]<chiStats[shiftKey] )
    196                     {
    197                         shiftKey = l;
    198                     }
    199                 }
    200                
    201             }
    202             return shiftKey;
    203 
    204 
     246           
     247        }
     248        private int RCtest()
     249        {
     250            int max_keyLength = 30;
     251            double check;
     252            double max_diff = 0.002;
     253            RC_keyLength = 1;
     254            double min_keyLength=seqIC(1);
     255            for (int i = 2; i <max_keyLength; i++)
     256            {
     257                 check = seqIC(i);
     258                 if (min_keyLength-check>max_diff)
     259                 {
     260                     RC_keyLength = i;
     261                     min_keyLength = check;
     262                 }
     263            }
     264            return RC_keyLength;
    205265        }
    206266        #endregion
     
    367427           if (kasiskiInput != null)
    368428           {
    369                 //double [] elf;
     429                //take care of settings first...
    370430                switch (settings.ELF)
    371431                {
     
    377437                   default: elf = new double[26] { 8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 6.094, 6.966, 0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929, 0.095, 5.987, 6.327, 9.056, 2.758, 0.978, 2.360, 0.150, 1.974, 0.074 }; break;
    378438                }
     439               
    379440                if (vigToCaes==null)
    380441                {   
     
    384445                    string workstring2 = "";
    385446                    //int probableKeylength=0;
    386                     //Convert the cipher text into a format suitable for analysing i.e. remove all non-plaintext characters.
     447                    //Convert the cipher text into a format suitable for analysing i.e. remove all non-plaintext characters. //TO DO alphabet input...
    387448                   
    388449                    string strValidChars = new string(validchars);
     
    399460                    workstring2 = workstring1.ToString(); // Now copy workstring1 to workstring2. Needed because workstring1 can not be altered once its built
    400461                    workstring2 = workstring2.ToLower();
    401                     string cipherText = workstring2;
    402                     //Start analysing the keylenghts proposed by the Friedman and Kasiski tests, and find the most propbable keylength.
    403                     int[] primes = new int[] { 5  ,    7  ,   11   ,  13   ,  17  ,   19 ,    23  ,   29 ,
     462                    cipherText = workstring2;
     463                    if (settings.internalKeyLengthAnalysis == 1)
     464                    {
     465                        RCtest();
     466                        probableKeylength = RC_keyLength;
     467
     468                    }
     469                    if (settings.internalKeyLengthAnalysis == 0)
     470                    {
     471                        //Start analysing the keylenghts proposed by the Friedman and Kasiski tests, and find the most propbable keylength.
     472                        int[] primes = new int[] { 5  ,    7  ,   11   ,  13   ,  17  ,   19 ,    23  ,   29 ,
    404473                31   ,  37  ,   41 ,    43  ,   47  ,   53}; //Basic Array of prime numbers...replace with a primes generator or some sieve algorithm???
    405                     int biggestSoFar = 0;
    406                     int biggestSoFarIndex = 0;
    407                     int z = 0;
    408                     //Now we initialize an empty jagged array in which plausable keylengths with their respective probabilities will be stored
    409                     int[][] proposedKeylengths =
     474                        int biggestSoFar = 0;
     475                        int biggestSoFarIndex = 0;
     476                        int z = 0;
     477                        //Now we initialize an empty jagged array in which plausable keylengths with their respective probabilities will be stored
     478                        int[][] proposedKeylengths =
    410479                {
    411480                 new int[] {0,0,0,0,0,0,0,0,0,0,0},
     
    413482   
    414483                };
    415                     //Fill up the array
    416                     for (int j = kasiskiFactors.Length - 1; j >= 0; j--)
    417                     {
    418                         if (kasiskiFactors[j] > biggestSoFar)
    419                         {
    420                             biggestSoFar = kasiskiFactors[j];
    421                             biggestSoFarIndex = j;
    422                             proposedKeylengths[0][z] = j;
    423                             proposedKeylengths[1][z] = kasiskiFactors[j];
    424                             z++;
    425 
    426                         }
    427                     }
    428                     //The resulting array contains some plausible keylengths and some not so plausible keylengths.
    429                     //The variable "biggestSoFarIndex" contains the most common factor, hence most plausible keylength. Problem - biggestSoFarIndex is 2...
    430 
    431                     //After the most common factor is found check if this factor is a prime number. If yes - job done, this is indeed the key length.
    432                     foreach (int s in primes)
    433                     {
    434                         if (s == biggestSoFarIndex)
    435                         {
    436                             probableKeylength = biggestSoFarIndex;
    437                             goto Massages;
    438                         }
    439                     }
    440                     //In case the most common factor is not prime...well tough luck. We'll have to make some assumptions...
    441                     //First of all let's sort out unprobable keylengths.
    442                     double check1 = 0.55 * biggestSoFar;
    443                     int check = Convert.ToInt32(check1);
    444                     for (int r = 0; r <= proposedKeylengths[0].Length - 1; r++)
    445                     {
    446                         if (proposedKeylengths[1][r] < check)
    447                         {
    448                             proposedKeylengths[0][r] = 0;
    449                             proposedKeylengths[1][r] = 0;
    450                         }
    451 
    452                     }
    453                     //The unprobalbe keylengths are now replaced with zeroes.
    454                     //Get rid of the zeroes...
    455                     ArrayList factors = new ArrayList();
    456                     ArrayList count = new ArrayList();
    457                     for (int d = 0; d <= proposedKeylengths[0].Length - 1; d++)
    458                     {
    459                         if (proposedKeylengths[0][d] != 0)
    460                         {
    461                             factors.Add(proposedKeylengths[0][d]);
    462                             count.Add(proposedKeylengths[1][d]);
    463                         }
    464                     }
    465                     //The dynamic arrays "factors" and "count" now contain only the most prorbale keylengths and their respective probability.
    466                     //For ease of access convert the dynamic arrays in to normal ones
    467                     int[] factors1 = (int[])factors.ToArray(typeof(int));
    468                     int[] count1 = (int[])count.ToArray(typeof(int));
    469                     int a = factors1.Length;
    470                     //Now check the difference in probability between the most common and most uncommon factors
    471                     double smallestCount = count1[0]; //c# does not implicitly convert between int and double, hence two new variables are needed
    472                     double biggestCount = count1[a - 1];
    473                     double controlValue = smallestCount / biggestCount;
    474                     //Now can make some assumptions...
    475                     if (a > 3)
    476                     {
    477                         if (factors1[0] % factors1[a - 1] == 0 && factors1[0] % factors1[a - 2] == 0 && factors1[0] % factors1[a - 3] == 0 && controlValue > 0.65)
     484                        //Fill up the array
     485                        for (int j = kasiskiFactors.Length - 1; j >= 0; j--)
     486                        {
     487                            if (kasiskiFactors[j] > biggestSoFar)
     488                            {
     489                                biggestSoFar = kasiskiFactors[j];
     490                                biggestSoFarIndex = j;
     491                                proposedKeylengths[0][z] = j;
     492                                proposedKeylengths[1][z] = kasiskiFactors[j];
     493                                z++;
     494
     495                            }
     496                        }
     497                        //The resulting array contains some plausible keylengths and some not so plausible keylengths.
     498                        //The variable "biggestSoFarIndex" contains the most common factor, hence most plausible keylength. Problem - biggestSoFarIndex is 2...
     499
     500                        //After the most common factor is found check if this factor is a prime number. If yes - job done, this is indeed the key length.
     501                        foreach (int s in primes)
     502                        {
     503                            if (s == biggestSoFarIndex)
     504                            {
     505                                probableKeylength = biggestSoFarIndex;
     506                                goto Massages;
     507                            }
     508                        }
     509                        //In case the most common factor is not prime...well tough luck. We'll have to make some assumptions...
     510                        //First of all let's sort out unprobable keylengths.
     511                        double check1 = 0.55 * biggestSoFar;
     512                        int check = Convert.ToInt32(check1);
     513                        for (int r = 0; r <= proposedKeylengths[0].Length - 1; r++)
     514                        {
     515                            if (proposedKeylengths[1][r] < check)
     516                            {
     517                                proposedKeylengths[0][r] = 0;
     518                                proposedKeylengths[1][r] = 0;
     519                            }
     520
     521                        }
     522                        //The unprobalbe keylengths are now replaced with zeroes.
     523                        //Get rid of the zeroes...
     524                        ArrayList factors = new ArrayList();
     525                        ArrayList count = new ArrayList();
     526                        for (int d = 0; d <= proposedKeylengths[0].Length - 1; d++)
     527                        {
     528                            if (proposedKeylengths[0][d] != 0)
     529                            {
     530                                factors.Add(proposedKeylengths[0][d]);
     531                                count.Add(proposedKeylengths[1][d]);
     532                            }
     533                        }
     534                        //The dynamic arrays "factors" and "count" now contain only the most prorbale keylengths and their respective probability.
     535                        //For ease of access convert the dynamic arrays in to normal ones
     536                        int[] factors1 = (int[])factors.ToArray(typeof(int));
     537                        int[] count1 = (int[])count.ToArray(typeof(int));
     538                        int a = factors1.Length;
     539                        //Now check the difference in probability between the most common and most uncommon factors
     540                        double smallestCount = count1[0]; //c# does not implicitly convert between int and double, hence two new variables are needed
     541                        double biggestCount = count1[a - 1];
     542                        double controlValue = smallestCount / biggestCount;
     543                        //Now can make some assumptions...
     544                        if (a > 3)
     545                        {
     546                            if (factors1[0] % factors1[a - 1] == 0 && factors1[0] % factors1[a - 2] == 0 && factors1[0] % factors1[a - 3] == 0 && controlValue > 0.65)
     547                            {
     548                                probableKeylength = factors1[0];
     549                            }
     550                            else { probableKeylength = factors1[1]; }
     551                        }
     552                        if (a == 3)
     553                        {
     554                            if (factors1[0] % factors1[a - 1] == 0 && factors1[0] % factors1[a - 2] == 0 && controlValue > 0.75)
     555                            {
     556                                probableKeylength = factors1[0];
     557                            }
     558                            if (factors1[0] % factors1[a - 2] == 0 && factors1[0] % factors1[a - 1] != 0 && controlValue > 0.6)
     559                            {
     560                                probableKeylength = factors1[0];
     561                            }
     562
     563                        }
     564                        if (a == 2)
     565                        {
     566                            if (factors1[0] % factors1[a - 1] == 0 && controlValue > 0.75)
     567                            {
     568                                probableKeylength = factors1[0];
     569                            }
     570
     571                        }
     572                        if (a == 1)
    478573                        {
    479574                            probableKeylength = factors1[0];
    480575                        }
    481                         else { probableKeylength = factors1[1]; }
    482                     }
    483                     if (a == 3)
    484                     {
    485                         if (factors1[0] % factors1[a - 1] == 0 && factors1[0] % factors1[a - 2] == 0 && controlValue > 0.75)
    486                         {
    487                             probableKeylength = factors1[0];
    488                         }
    489                         if (factors1[0] % factors1[a - 2] == 0 && factors1[0] % factors1[a - 1] != 0 && controlValue > 0.6)
    490                         {
    491                             probableKeylength = factors1[0];
    492                         }
    493 
    494                     }
    495                     if (a == 2)
    496                     {
    497                         if (factors1[0] % factors1[a - 1] == 0 && controlValue > 0.75)
    498                         {
    499                             probableKeylength = factors1[0];
    500                         }
    501 
    502                     }
    503                     if (a == 1)
    504                     {
    505                         probableKeylength = factors1[0];
    506                     }
    507576                    //Now that we've made some rudimentary decission making, let's check if it has payed off...
    508                 Massages:
    509                     if (Math.Abs(probableKeylength - friedmanKey) < 1)
    510                     {
    511                         ShowStatusBarMessage("Analysed proposed keylengths. The derived keylength is the correct value." + "" + "Derived keylength is:" + probableKeylength.ToString(), NotificationLevel.Info);
    512                     }
    513                     if (Math.Abs(probableKeylength - friedmanKey) > 1 && Math.Abs(probableKeylength - friedmanKey) < 2)
    514                     {
    515                         ShowStatusBarMessage("Analysed proposed keylengths. The derived keylength is probably the correct value" + "" + "Derived keylength is:" + probableKeylength.ToString(), NotificationLevel.Info);
    516                     }
    517                     if (Math.Abs(probableKeylength - friedmanKey) > 2 && Math.Abs(probableKeylength - friedmanKey) < 3)
    518                     {
    519                         ShowStatusBarMessage("Analysed proposed keylengths. The derived keylength may not be the correct value." + "" + "Derived keylength is:" + probableKeylength.ToString(), NotificationLevel.Info);
    520                     }
    521                     if (Math.Abs(probableKeylength - friedmanKey) > 3)
    522                     {
    523                         ShowStatusBarMessage("Analysed proposed keylengths. Friedman or Kasiski test provided a value that was wrong. A manual analysis may be needed to confirm the derived keylength." + "" + "Derived keylength is:" + probableKeylength.ToString(), NotificationLevel.Info);
     577                    Massages:
     578                        if (Math.Abs(probableKeylength - friedmanKey) < 1)
     579                        {
     580                            ShowStatusBarMessage("Analysed proposed keylengths. The derived keylength is the correct value." + "" + "Derived keylength is:" + probableKeylength.ToString(), NotificationLevel.Info);
     581                        }
     582                        if (Math.Abs(probableKeylength - friedmanKey) > 1 && Math.Abs(probableKeylength - friedmanKey) < 2)
     583                        {
     584                            ShowStatusBarMessage("Analysed proposed keylengths. The derived keylength is probably the correct value" + "" + "Derived keylength is:" + probableKeylength.ToString(), NotificationLevel.Info);
     585                        }
     586                        if (Math.Abs(probableKeylength - friedmanKey) > 2 && Math.Abs(probableKeylength - friedmanKey) < 3)
     587                        {
     588                            ShowStatusBarMessage("Analysed proposed keylengths. The derived keylength may not be the correct value." + "" + "Derived keylength is:" + probableKeylength.ToString(), NotificationLevel.Info);
     589                        }
     590                        if (Math.Abs(probableKeylength - friedmanKey) > 3)
     591                        {
     592                            ShowStatusBarMessage("Analysed proposed keylengths. Friedman or Kasiski test provided a value that was wrong. A manual analysis may be needed to confirm the derived keylength." + "" + "Derived keylength is:" + probableKeylength.ToString(), NotificationLevel.Info);
     593                        }
     594                        factors1 = null;
    524595                    }
    525596                    //Now we have a good idea of the keylength used to encrypt the ciphertext recived on the stringInput.
     
    546617                    //Furthermore the vigenerToCaesar is allready sorted in such a way that the index of each element coresponds to the position of its respective shift key in the whole key.
    547618                    vigToCaes = vigenereToCaesar;
    548                     factors1 = null;
     619                   
    549620                   
    550621                }
     
    581652                        probableKeyword[f]=tempKey[0];
    582653                        tempKey = null;
     654                        //probableKeyword[f] = chiList.ElementAt(f);
    583655                    }
    584656                    keyList = null;
  • trunk/CrypPlugins/VigenereAnalyser/VigenereAnalyserSettings.cs

    r388 r390  
    1414        #region ISettings Members
    1515        private int elf = 0;
     16        public int internalKeyLengthAnalysis = 0;
    1617        private bool hasChanges = false;
    17         [ContextMenu("Letter Frequency", "Select the language to be analysed", 2, DisplayLevel.Beginner, ContextMenuControlType.ComboBox, null, new String[] { "English", "German", "French", "Spanish", "Italian", "Portugeese" })]
    18         [TaskPane("Letter Frequency", "Select the language to be analysed", null, 2, false, DisplayLevel.Experienced, ControlType.ComboBox, new String[] { "English", "German", "French", "Spanish", "Italian", "Portugeese" })]
     18        [ContextMenu("Expected Letter Frequency of a language", "Select the Null hypothesis for the Chi-square statistic", 2, DisplayLevel.Beginner, ContextMenuControlType.ComboBox, null, new String[] { "English", "German", "French", "Spanish", "Italian", "Portugeese" })]
     19        [TaskPane("Expected Letter Frequency of a language", "Select the Null hypothesis for the Chi-square statistic", null, 2, false, DisplayLevel.Experienced, ControlType.ComboBox, new String[] { "English", "German", "French", "Spanish", "Italian", "Portugeese" })]
    1920        public int ELF // Expected Letter Frequencies
    2021        {
     
    2526                this.elf = (int)value;
    2627                OnPropertyChanged("ELF");
     28            }
     29        }
     30        [ContextMenu("Method of keylength analysis", "Select the internal or external method for analysis of the keylength", 2, DisplayLevel.Beginner, ContextMenuControlType.ComboBox, null, new String[] { "Use Kasiski and Friedman tests (external)","Use Regression-Covariance test (internal)" })]
     31        [TaskPane("Method of keylength analysis", "Select the internal or external method for analysis of the keylength", null, 2, false, DisplayLevel.Experienced, ControlType.ComboBox, new String[] { "Use Kasiski and Friedman tests (external)", "Use Regression-Covariance test (internal)" })]
     32        public int InternalKeyLengthAnalysis
     33        {
     34            get { return this.internalKeyLengthAnalysis; }
     35            set
     36            {
     37                if (((int)value) != internalKeyLengthAnalysis) hasChanges = true;
     38                this.internalKeyLengthAnalysis = (int)value;
     39                OnPropertyChanged("internalKeyLengthAnalysis");
    2740            }
    2841        }
Note: See TracChangeset for help on using the changeset viewer.