Reinhard: MIC (mutual index of coincidence)

Guten Abend,

ich versuche gerade zu verstehen, wie die MIC-Formel angewendet wird. Das Zitat stammt von hier. Es dreht sich um Abschnitt 2.2

„2.2 Determining the Keyword
We employ a new technique suggested by Dan Velleman[6] which uses mutual index of coincidence (MIC) in a very smart fashion.

The mutual index of coincidence of x and s, denoted MIC(x,s), is defined to be the probability that two random elements, one from each, are identical. Let x is a string of standard source language e.g. English. Let string x has length l and frequency distribution $$ r_1,r_2,...,r_n $$ where n is the size of the alphabet e.g. 26. Clearly, for large l, probability distributions of n letters $$ r_i/l $$ will be similar to the standard probability distributions $$ p_i $$ of the source language. Now, let string y has length l' and frequency distribution $$ r'_1,r'_2,...,r'_n $$. Then,

$$ \displaystyle MIC (x,s) = \frac{\sum\nolimits_{i=1}^n r_i r'i}{ll'} \simeq \frac{\sum\nolimits{i=1}^n p_i r'_i}{l'} $$

Suppose $$ s_1,s_2,..,s_m $$ be the m substrings of the ciphertext s. Each of these substrings are obtained by shift encryption of the unknown plaintext. Though plaintext is unknown at the moment, its probability distribution and therefore its IC is known. Consider, substring $$ s_j\ (1 \le j \le m) $$ is encrypted by unknown key $$ k_j $$. Suppose we shift $$ s_j $$ by $$ b\ (1 \le b \le n) $$ and obtain n different $$ s_j^b $$ each of which corresponds to a decryption with a different key value. If $$ s_j $$ has frequency distribution $$ r''_1,r''_2,...,r''_n $$ and length l'', then

$$ \displaystyle MIC (x, s_j^b) \simeq \frac{\sum\nolimits_{i=1}^n p_i r''_{i-b}}{l''} $$

It is expected that $$ MIC (x,s_j^b) \simeq IC(source\ language) $$ if b is the additive inverse of the correct key modulo n; otherwise we obtain a much smaller MIC value. For instance if n = 26, and maximum MIC value for a substring is obtained when b = 5, then the probable key for that substring is −5 mod 26 = 21. For the example ciphertext our prediction is m = 6. So, we divide the ciphertext into 6 substrings, and we shift each substring by one, two, up to 26 and compute the MIC values shown in Figure2. By simply selecting the maximum MIC value for each substring we get a probable keyword, in our example it is crypto. To see whether the keyword we have obtained is correct we decrypt the ciphertext discovering[4] a passage from Tanenbaum[12].“

So: Wie berechnet man nun den MIC? In der Tabelle bei String 1 Shift 26 (Key A) soll nun 0,0314 rauskommen.

var language = {
    en : {
        //Buchstabenhäufigkeiten A-Z in %
        frequencies : [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],
        ic : 0.0655
    }
};
function MICtest(str, lang, len)
{
//str (String) : komplettes Kryptogramm
//lang (String) : Sprachkürzel (hier: 'en')
//len (Number) : Anzahl der Spalten in die das Kryptogramm zerteilt wird
lang = language[lang];
var substrings = [],
    frequencyDistribution = [],
    sum = 0;
//substring-Spalten bilden
for (var i = 0; i < len; i++)
  substrings[i] = [];
for (var i = 0, l = str.length; i < l; i++)
  substrings[i % len].push(str[i]);
//Soweit ich verstanden habe geht es nun so weiter: Buchstaben zusammenzählen und durch Gesamtlänge teilen
//Im folgenden nur noch für den 1. Substring
for (var i = 0; i < 26; i++)
  frequencyDistribution[i] = 0;
//_alp (Array) : beinhalten das Alphabet ['A', 'B',...,'Z']
for (var i = 0, l = substrings[0].length; i < l; i++)
  frequencyDistribution[_alp.indexOf(substrings[0][i])]++;
for (var i = 0; i < 26; i++)
  frequencyDistribution[i] /= substrings[0].length;
//Nun Summe bilden (ober Teil des Bruchstrichs  - 2. Formel!)
for (var i = 0; i < 26; i++)
  sum += lang.frequencies[i] * frequencyDistribution[i];
//Zuletzt alles durch die Substring Länge teilen
sum /= substrings[0].length;
console.log(sum); //~0,064

Nun ist 0,064 ganz sicher nicht 0,0314. Ich hoffe jemand kann mir sagen was ich nicht berücksichtigt habe. Oder besser: ein To-Do-Plan in welcher Reihenfolge ich was machen soll.

Reinhard


Wenn es so weiter geht, sollte der Forumsgeist mal ein 'Kryptologie'-Tag hinzufügen :-)

akzeptierte Antworten

  1. hii,

    ich würde mir schritt für schritt alles anzeigen lassen. zunächst einmal, ob du wirklich die richtigen substrings ausgewählt hast. substring1 wäre etwa WJPOUVP... usw.

    als nächstes zählst du die häufigkeiten der zeichen für jeden substring durch, also A(1)=1 usw. auch das alles anzeigen lassen und prüfen.

    dann würde ich rechnen (a*A(i)+b*B(i)+...+z*Z(i))/l(i), wobei a,b,...,z die relativen häufigkeiten der zugeh. buchstaben sind, i der jeweilige index des substrings und l(i) dessen länge. ohne jz das ergebnis gleich zu bewerten, würde ich dann fortfahren mit den shifts, also
    (a*B(i)+b*C(i)+...+z*A(i))/l(i)
    (a*C(i)+b*D(i)+...+z*B(i))/l(i) usw. berechnen.

    auch hier würde ich sicherheitshalber einige werte händisch berechnen und prüfen.

    die so erzeugte tabelle würde ich dann mit der tabelle im text vergleichen.

    bye trunx

    --
    Die Standard-Antwort: "Bitte benutze die Forum-Suche!" macht die Forum-Suche kaputt, weil die Suche dann nämlich genau vor allem diese dämliche Standard-Antwort, also Müll liefert. Sinnvoller ist stattdessen folgende Standard-Antwort: "Dieses Thema wurde schon vielfach im Forum besprochen, siehe z.B. <a>hier</a> oder <a>da</a> oder benutze die Forum-Suche z.B. mit den Stichworten 'Stichwort1 Stichwort2'." Danke.
    1. Hey,

      ich würde mir schritt für schritt alles anzeigen lassen. zunächst einmal, ob du wirklich die richtigen substrings ausgewählt hast. substring1 wäre etwa WJPOUVP... usw.

      var substrings = [];
      //len == 6
      for (var i = 0; i < len; i++)
        substrings[i] = [];
      for (var i = 0, l = str.length; i < l; i++)
        substrings[i % len].push(str[i]);
      

      positiv.

      als nächstes zählst du die häufigkeiten der zeichen für jeden substring durch, also A(1)=1 usw. auch das alles anzeigen lassen und prüfen.

      //Häufigkeiten des 1. Substrings
      var frequencyDistribution = [];
      for (var i = 0; i < 26; i++)
        frequencyDistribution[i] = 0;
      for (var i = 0, l = substrings[0].length; i < l; i++)
        frequencyDistribution[_alp.indexOf(substrings[0][i])]++;
      

      positiv.

      $$ \displaystyle MIC (x, s_j^b) \simeq \frac{\sum\nolimits_{i=1}^n p_i r''_{i-b}}{l''} $$

      (Die Formel)

      dann würde ich rechnen (a*A(i)+b*B(i)+...+z*Z(i))/l(i), wobei a,b,...,z die relativen häufigkeiten der zugeh. buchstaben sind, i der jeweilige index des substrings und l(i) dessen länge.

      Ich steh auf dem Schlauch.. Was heißt "zugeh."? Was berechnest du damit? Und: wo bist du gerade bei der Formel?

      ohne jz das ergebnis gleich zu bewerten, würde ich dann fortfahren mit den shifts, also
      (a*B(i)+b*C(i)+...+z*A(i))/l(i)
      (a*C(i)+b*D(i)+...+z*B(i))/l(i) usw. berechnen.

      Wie jetzt, erst „(a*A(i)+b*B(i)+...+z*Z(i))/l(i)“ und dann „(a*B(i)+b*C(i)+...+z*A(i))/l(i)“? Wie kommst du darauf? Und selbes wie oben: was berechnest du damit?

      So, das $$ l'' $$ in der Formel ist jetzt die Länge des Substrings (substrings[0].length == 49), $$ p_i $$ ist die Buchstabenhäufigkeit der betreffenden Sprache (z.B. Englisch) - aber wie sieht $$ p_i $$ aus? Ist $$ p_i $$ bei A nun 8.167 oder 0.08167? - und was ist $$ r''_{i-b} $$ ? bzw. wenn $$ r'' $$ die zuvor gezählten Buchstabenhäufigkeiten des Substrings sind (Format: 2|4|0|9|3|...) was ist b?

      Wäre toll wenn wir die MIC Formel mal für den 1. Substring durchgehen könnten.
      Substring[0] : WJPOUVPTQVJGCAEGGVGVQQGCKVNRQVIEGPWVOCUCCEVRJJVKD
      Buchstabenhäufigkeit : 1 0 5 1 3 0 6 0 1 4 2 0 0 1 2 3 4 2 0 1 2 9 2 0 0 0

      |A|1 |B|0 |C|5 |D|1 |E|3 |F|0 |G|6 |H|0 |I|1 |J|4 |K|2 |L|0 |M|0 |N|1 |O|2 |P|3 |Q|4 |R|2 |S|0 |T|1 |U|2 |V|9 |W|2 |X|0 |Y|0 |Z|0

      Reinhard

      1. hallo reinhard,

        dann würde ich rechnen (a*A(i)+b*B(i)+...+z*Z(i))/l(i), wobei a,b,...,z die relativen häufigkeiten der zugeh. buchstaben sind, i der jeweilige index des substrings und l(i) dessen länge. Ich steh auf dem Schlauch.. Was heißt "zugeh."? Was berechnest du damit? Und: wo bist du gerade bei der Formel?

        das sind die häufigkeiten der buchstaben in der englischen sprache (bei dir die werte in language['en']['frequencies']), also a=8.167%=0.08167=p(1), b=1.492%=0.01492=p(2) usw.

        ohne jz das ergebnis gleich zu bewerten, würde ich dann fortfahren mit den shifts, also
        (a*B(i)+b*C(i)+...+z*A(i))/l(i)
        (a*C(i)+b*D(i)+...+z*B(i))/l(i) usw. berechnen.
        Wie jetzt, erst „(a*A(i)+b*B(i)+...+z*Z(i))/l(i)“ und dann „(a*B(i)+b*C(i)+...+z*A(i))/l(i)“? Wie kommst du darauf? Und selbes wie oben: was berechnest du damit?

        das ist das shiften...

        Wäre toll wenn wir die MIC Formel mal für den 1. Substring durchgehen könnten.
        Substring[0] : WJPOUVPTQVJGCAEGGVGVQQGCKVNRQVIEGPWVOCUCCEVRJJVKD
        Buchstabenhäufigkeit : 1 0 5 1 3 0 6 0 1 4 2 0 0 1 2 3 4 2 0 1 2 9 2 0 0 0

        ok. a*A(1)+b*B(1)+...+z*Z(1)=0.08167*1+0+...+0 = ?
        das ganze durch l(1)=49 dividieren.
        dann a*B(1)+b*C(1)+...+z*A(1) = 0+0.01492*5+...+0.00074*1 = ?
        auch wieder durch 49 dividieren.
        usw. also a*C(1)+..., a*D(1)+..., ... das ist eben das shiften, also das verschieben, denn du weisst ja nicht ob sich hinter dem A aus dem kryptogramm wirklich das a oder b oder c und und verbirgt, deshalb setzt du JEDES zeichen mal an die entsprechende stelle. das musst du halt konsequent durchziehen (und unter den im englischen 26 ergebnissen am ende den jeweils größten für jeden substring heraus suchen).

        bye trunx

        --
        Die Standard-Antwort: "Bitte benutze die Forum-Suche!" macht die Forum-Suche kaputt, weil die Suche dann nämlich genau vor allem diese dämliche Standard-Antwort, also Müll liefert. Sinnvoller ist stattdessen folgende Standard-Antwort: "Dieses Thema wurde schon vielfach im Forum besprochen, siehe z.B. <a>hier</a> oder <a>da</a> oder benutze die Forum-Suche z.B. mit den Stichworten 'Stichwort1 Stichwort2'." Danke.
        1. ergänzung (multiplikation ist skalarmultiplikation):
          (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)*(1 0 5 1 3 0 6 0 1 4 2 0 0 1 2 3 4 2 0 1 2 9 2 0 0 0)/4900 = 0.03135.. = 0.0314
          der wert ist also korrekt.

          --
          Die Standard-Antwort: "Bitte benutze die Forum-Suche!" macht die Forum-Suche kaputt, weil die Suche dann nämlich genau vor allem diese dämliche Standard-Antwort, also Müll liefert. Sinnvoller ist stattdessen folgende Standard-Antwort: "Dieses Thema wurde schon vielfach im Forum besprochen, siehe z.B. <a>hier</a> oder <a>da</a> oder benutze die Forum-Suche z.B. mit den Stichworten 'Stichwort1 Stichwort2'." Danke.
        2. Hey trunx,

          das sind die häufigkeiten der buchstaben in der englischen sprache (bei dir die werte in language['en']['frequencies']), also a=8.167%=0.08167=p(1), b=1.492%=0.01492=p(2) usw.

          Wäre toll wenn wir die MIC Formel mal für den 1. Substring durchgehen könnten.
          Substring[0] : WJPOUVPTQVJGCAEGGVGVQQGCKVNRQVIEGPWVOCUCCEVRJJVKD
          Buchstabenhäufigkeit : 1 0 5 1 3 0 6 0 1 4 2 0 0 1 2 3 4 2 0 1 2 9 2 0 0 0 ok. a*A(1)+b*B(1)+...+z*Z(1)=0.08167*1+0+...+0 = ?
          das ganze durch l(1)=49 dividieren.
          dann a*B(1)+b*C(1)+...+z*A(1) = 0+0.01492*5+...+0.00074*1 = ?
          auch wieder durch 49 dividieren.
          usw. also a*C(1)+..., a*D(1)+..., ...

          Toll! Hab mir gerade was zusammen geschrieben und das läuft ziemlich gut. Die Abweichungen meiner Werte von denen in der Tabelle sind minimal. Liegt wohl daran, dass die Buchstabenhäufigkeiten (Englisch), die ich nutze, sich bei vielen Buchstaben geringfügig unterscheidet. Den Hochpunkt bei C bekomme ich aber auch raus.

          Danke! Ich feier dich gerade :-)

          Reinhard

          1. :)

            --
            Die Standard-Antwort: "Bitte benutze die Forum-Suche!" macht die Forum-Suche kaputt, weil die Suche dann nämlich genau vor allem diese dämliche Standard-Antwort, also Müll liefert. Sinnvoller ist stattdessen folgende Standard-Antwort: "Dieses Thema wurde schon vielfach im Forum besprochen, siehe z.B. <a>hier</a> oder <a>da</a> oder benutze die Forum-Suche z.B. mit den Stichworten 'Stichwort1 Stichwort2'." Danke.