Montag, 1. M�rz 2010


Topthema

Donnerstag, 10. August 2006 | Topthema

About Security #67: Kryptographie — Transposition

(Link zum Artikel: http://www.entwickler.de/php/kolumnen/030632)

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:

N E U ! Security aktuell
T�glich aktuelle Security-Infos!

Buchstabe Anzahl H�ufigkeit (%)      Buchstabe Anzahl H�ufigkeit (%)
e 667 16,55      o 117 2,90
s 323 8,02      g 103 2,56
i 310 7,69      b 83 2,06
t 306 7,59      z 62 1,54
n 299 7,42      k 61 1,51
r 254 6,30      w 53 1,32
a 230 5,71      p 46 1,14
d 210 5,21      f 43 1,07
h 187 4,64      v 42 1,04
l 154 3,82      y 34 0,84
u 152 3,77      x 30 0,74
c 138 3,43      j 6 0,15
m 119 2,95      q 0 0,00

Die zehn h�ufigsten Buchstabenpaare:

Buchstabenpaar Anzahl
en 131
er 124
ch 122
te 87
de 80
ei 79
es 65
nd 65
ie 62
st 61

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).

About Security: Die komplette Serie
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.

Wenn Sie Fragen oder Themenvorschl�ge haben, k�nnen Sie diese gerne an die angegebene E-Mail-Adresse senden oder im Security-Forum einbringen!

Carsten Eilers

About Security � �bersicht zum aktuellen Thema "Kryptographie � Grundlagen"

Kommentare

Folgende Links könnten Sie auch interessieren