Channel Security

Wie Sie die in About Security #66 vorgestellte Substitution brechen können, erfahren Sie in dieser Folge. Außerdem lernen Sie ein weiteres klassisches Verfahren kennen, die Transposition.

Für den Angriff auf die in About Security #66 vorgestellte Substitution werden statistische Verfahren verwendet. Dabei wird ausgenutzt, dass bei der Substitution eine 1-zu-1-Ersetzung erfolgt, sich Besonderheiten des Klartexts also im Geheimtext wiederfinden. Dies trifft insbesondere auf die Häufigkeit von Buchstaben und Buchstabenpaaren zu.

Als Beispiel soll der Text der letzten Woche dienen. Unter Auslassung von Zahlen, Leer- und Satzzeichen und Umwandlung von ä, ö, ü und ß in ae, oe, ue und ss ergeben sich folgende Werte:

Die zehn häufigsten Buchstabenpaare:

Weitere Tabellen mit Buchstabenhäufigkeiten findet man in Internet, z.B. auf den Seiten von Prof. Dr. Pommerening an der Uni Mainz: Zeichenhäufigkeiten in Deutsch. Dort gibt es auch Perl-Programme zum Zählen von Einzelbuchstaben (Online-Version) und Buchstabenpaaren (Online-Version).

Die Entschlüsselung

Der folgende Geheimtext soll entschlüsselt werden:

ZVGQRZFPUYHRFFRYREUNRYGZNAHROEVTRAFQNFNYFEBGORXNAA
GRIRESNUERAQNFMOVZHFRARGRVAHANOFVPUGYVPURFYRFRAIBA
GRKGGRVYRAIREUVAQREGQVRJHEQRQNORVTRJNRUYGJRVYRVARR
EARHGRIREFPUYHRFFRYHATQRFTRURVZGRKGRFJVRQREQRAXYNE
GRKGRETVOGEBGEBGXYNEGRKGXYNEGRKG

Es wird davon ausgegangen, dass eine Substitution verwendet wurde und bekannt ist, das der Klartext in Deutsch geschrieben wurde. Bei der Analyse wird zuerst das häufigste Zeichen im Geheimtext gesucht. In diesem Fall ist dies das 'R'. Vermutlich entspricht dies dem im Deutschen häufigsten Buchstaben 'e'. Zur besseren Unterscheidung verwende ich ab jetzt für Geheimtextzeichen große, für Klartextzeichen kleine Buchstaben. Wenn 'R' dem 'e' entspricht, müssten viele Muster aus 'R' und einem weiteren Zeichen, entsprechend 'en', und 'R' und einem anderen Zeichen, entsprechend 'er', im Geheimtext vorkommen. RE kommt 8-mal vor, RA 6-mal.

Wenn die Annahmen stimmen, sind jetzt drei Zeichen bekannt. Ob RE wahrscheinlicher 'en' oder 'er' entspricht, kann man aufgrund des relativ kurzen Geheimtextes nicht entscheiden, also muss geraten werden.

Versuchen wir es mal mit

 R = e
 A = n
 E = r

Die gefundenen Zeichen können nun im Geheimtext ersetzt werden:

ZVGQeZFPUYHeFFeYerUNeYGZNnHeOrVTenFQNFNYFrBGOeXNnn
GeIerSNUrenQNFMOVZHFeneGeVnHnNOFVPUGYVPUeFYeFenIBn
GeKGGeVYenIerUVnQerGQVeJHrQeQNOeVTeJNeUYGJeVYeVnee
rneHGeIerFPUYHeFFeYHnTQeFTeUeVZGeKGeFJVeQerQenXYNr
GeKGerTVOGrBGrBGXYNrGeKGXYNrGeKG

Als Nächstes kann z.B. nach weiteren häufigen Buchstabenpaaren gesucht werden. Wer möchte, kann es gerne selbst ausprobieren. Eine mögliche Lösung gibt es hier.

Homophone Substitution

Eine Verbesserung der Substitution ist die homophone Substitution. Dabei werden den Klartextzeichen mehrere Geheimtextzeichen zugeordnet, sodass das Geheimtextalphabet aus deutlich mehr Zeichen als das Klartextalphabet besteht. Insbesondere häufigen Zeichen werden mehrere Geheimtextzeichen zugeordnet, sodass im Idealfall im Geheimtext alle Zeichen des Geheimtextalphabets mit der gleichen Häufigkeit vorkommen. Auch dieses Verfahren ist relativ leicht zu brechen. Zum einen ist es sehr anfällig für Klartextangriffe, zum anderen werden die inneren Gesetzmäßigkeiten der Sprache nur mangelhaft verdeckt. Ein weiterer Schwachpunkt ist die Auswahl des Geheimtextzeichens, wenn für ein Klartextzeichen mehrere zur Verfügung stehen. Erfolgt dies nach einer bestimmten Gesetzmäßigkeit, z.B. "immer der Reihe nach", ergeben sich im Geheimtext wieder Regelmäßigkeiten, die die Analyse vereinfachen.

Transposition

Ein weiteres klassisches Verfahren ist die Transposition, d.h. Vertauschung von Zeichen. Dabei werden die Zeichen selbst nicht verändert, nur ihre Position im Text ändert sich. Das einfachste Beispiel dafür ist der so genannte Würfel, bei dem die zu verschlüsselnde Nachricht zeilenweise in ein Rechteck geschrieben und spaltenweise ausgelesen wird. Als Schlüssel dient dabei die Kantenlänge des Rechtecks.

Klartext

D I E S I S T E
I N Z I E M L I
C H B L O E D E
S B E I S P I E 
L F U E R E I N
E T R A N S P O
S I T I O N O D
E R N I C H T

Geheimtext

DICSLESE INHBFTIR EZBEURTN SILIEAII IEOSRNOC SMEPESNH TLDIIPOT EIEENOD

Auch dieses Verfahren ist unsicher. Ein möglicher Angriff wird in der nächsten Folge beschrieben. Außerdem geht es dann um ein weiteres Verschlüsselungsverfahren: Die Polyalphabetische Substitution.

Carsten Eilers

About Security – Übersicht zum aktuellen Thema "Kryptographie – Grundlagen"

• About Security #66: Kryptographie – Substitution
• About Security #67: Kryptographie – Transposition
• About Security #68: Kryptographie – Polyalphabetische Substitution
• About Security #69: Kryptographie – Vernam-Chiffre
• About Security #70: Kryptographie – Feistel-Netzwerke