[JoGu]

Kryptologie

Der Koinzidenzindex einer stochastischen Sprache
a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

Definition

Für eine stochastische Sprache M Í S* mit Buchstabenhäufigkeiten ps heißt

kM := kMM = SsÎS ps2

der Koinzidenzindex von M (nach FRIEDMAN).

Deutung: Für unabhängige Texte a, b Î M gleicher Länge ist

k(a,b) » kM

Beispiele. 1.) kS* = 1/n. Im Spezialfall n = 26 ist kS* » 0.0385.

2.) Aus den bekannten Häufigkeitstabellen folgen empirisch die bereits angekündigten Werte

Eigenschaften

Da SsÎS ps = 1, gilt 1/n £ kM £ 1, und zwar

  1. kM = 1/n Û alle ps = 1/n,
  2. kM = 1 Û ein ps = 1, alle übrigen = 0.

Das folgt aus

  1. 1 = (SsÎS ps×1)2 £ SsÎS ps2 × SsÎS 1 = n × SsÎS ps2

    mit Gleichheit Û (ps)sÎS = c×(1)sÎS (als Vektor) Û alle ps gleich Û alle ps = 1/n.

  2. SsÎS ps2 £ SsÎS ps = 1, da 0 £ ps £ 1, also ps2 £ ps,

    mit Gleichheit Û alle ps2 = ps Û alle ps = 0 oder 1.

Anwendungen

1.) Bei polyalphabetischer Substitution ist die Wiederverwendung des gleichen Schlüssels mit hoher Wahrscheinlichkeit erkennbar (egal, ob periodisch oder nicht):

Für verschiedene polyalphabetische Substitutionen f, g ist zu erwarten, dass

k(f(a),g(b)) » 1/n     für a, b Î Sr.

Jetzt ist auch geklärt, dass bei gleicher Substitution

k(f(a),f(b)) = k(a,b) » kM     für a, b Î M.

2.) Sei c ein Geheimtext aus einer polyalphabetischen Verschlüsselung eines Textes a Î M der Periode l. Welche Werte sind für kq(c) zu erwarten?

c =c0… cq-1 ½½ cq… cr-1
c(q) = cr-q… cr-1 ½½ c0… cr-q-1
erwartete Koinzidenzen: q×kM, fallsl|r-q, ½½ (r-q)×kM, fallsl|q,
q×kS* sonst, ½½ (r-q)×kS* sonst.

Daraus ergeben sich folgende erwartete Werte für den Autokoinzidenzindex:

1. Fall, l|r:

[Formel]

2. Fall, l kein Teiler von r:

[Formel]

Insbesondere gilt für q << r:

kq(c) » {    kM,     wenn l|q,
kS*     sonst.

Damit ist auch das im Beispiel beobachtete Autokoinzidenzspektrum erklärt, und die typischen Autokoinzidenzspektren sehen so aus.

Autor: Klaus Pommerening, 6. März 2000; letzte Änderung: 30. November 2004.