Prinzipien

Definitionen

Zum formalen Ansatz der Kryptologie ist ein Satz von Definitionen notwendig. Es sei an dieser Stelle - vorbeugend - nicht verschwiegen, daß kryptographische und kryptanalytische Untersuchungen rasch in mathematisch-algebraische Untiefen führen.

Definition: Ein Alphabet A ist eine endliche Menge von Symbolen.Ein Zeichenvorrat ist dasselbe wie ein Alphabet.Ein String s (eine Zeichenkette) ist eine endliche Folge von Zeichen aus einem Alphabet.Ist A ein Alphabet, dann bezeichne A* die Menge aller Strings über A.Ist s ein String, dann bezeichne |s| (bzw. #s) seine Länge.Der String der Länge 0 heißt Leerstring und wird mit e bezeichnet.Die Menge aller nichtleeren Strings A+ ist A* \ {e}.

Der Zeichenvorrat V, mit dessen Hilfe der Klartext formuliert wird, ist das Klartextvokabular oder der Klartextzeichenvorrat. Der Zeichenvorrat W, mit dessen Hilfe der Geheimtext formuliert wird, wird als Geheimtextvokabular oder Geheimtextzeichenvorrat genannt. Andere Bezeichnungen für W sind Code oder Chiffre. Die Zeichen w Î W heißen Sigel oder Codezeichen.

Die Kryptologie betrachtet eine Klartextnachricht, die in einem Alphabet V verfaßt ist. Durch eine geeignete Relation X, die Chiffrierung oder Verschlüsselung, wird diese Nachricht in eine Folge von Zeichen aus dem Alphabet W abgebildet:

   X: V* ® W*

In der Regel wird X injektiv definiert, es gilt also Linkseindeutigkeit:

   (x ® z) Ù (y ® z) Þ (x = y) mit x, y Î V, z Î W

Oft wird gewünscht, X als Abbildung zu vereinbaren, und zwar so, daß eine eindeutige Umkehrabbildung existiert. Die Festlegung der Relation kann durch Auflistung erzeugt werden, entzieht sich aber aus praktischen Gründen oft der vollständigen Aufschreibung. Man bevorzugt eine induktive Festlegung der Abbildungsvorschrift, die in der Praxis algorithmisch einfach durchführbar ist. Falls keine eindeutige Umkehrabbildung existiert, können sowohl die befugte wie auch die unbefugte Entschlüsselung erschwert werden.

Es sei klargestellt, daß überabzählbar unendlich viele Abbildungen der genannten Art existieren.

Für weitere Details und Definitionen sei auf Bauer, Kryptologie verwiesen.

Im folgenden wird die Konvention verwendet, Klartext durch normale Nichtproportional-Schrift in Kleinbuchstaben darzustellen: klartext Geheimtexte werden durch fette Nichtproportional-Schrift in Großbuchstaben wiedergegeben: GEHEIMTEXT.

 Substitution, Caesar-Verschlüsselung

Die Caesar-Verschlüsselung benutzt ein verschobenes Alphabet zum Chiffrieren. Hier ist das Alphabet um 3 Zeichen verschoben:

   abcdefghijklmnopqrstuvwxyz
   XYZABCDEFGHIJKLMNOPQRSTUVW

Beispiel für eine Caesar-Chiffre:

   freude am fahren
   COBRAB XJ CAEOBK

Allgemein versteht man unter Substitution die Zuordnung von Einzelzeichen des Klartextes zu Einzelzeichen des Geheimtextes. Im speziellen Fall der Caesar-Chiffre wird von einer monoalphabetischen Substitution gesprochen, da nur ein einziges Alphabet für die Abbildung auf den Geheimtext verwendet wird. Monoalphabetische Substitution kann im allgemeinen Fall auch durch eine beliebige, bijektive Zuordnung der Zeichen zwischen Klartext- und Geheimtext-Alphabet stattfinden.

Die bekannte "Freimaurer-Chiffre" ist ein Beispiel für eine Substitutionschiffre, die angeblich auch heute noch außerhalb des Klassenzimmers verwendet wird.

Es stellte sich bald heraus, daß monoalphabetische Substitutionschiffren durch eine statistische Analyse des Geheimtextes leicht zu brechen waren. Bereits frühzeitig wurden von Trithemius, Vigenère und anderen Chiffren ersonnen, die nach jedem Einzelschritt das zur Verschlüsselung verwendete Alphabet um ein Zeichen verschoben. Verfahren dieser Art werden als polyalphabetische Substitution bezeichnet. Dem Klartextalphabet wird eine Anzahl von verschobenen Alphabeten, nicht notwendigerweise 26 gegenübergestellt. Ein Beispiel mit vier Alphabeten:

     Klartextalphabet:   abcdefghijklmnopqrstuvwxyz 
 Geheimtextalphabete 
 ...für 1. Schritt   ZABCDEFGHIJKLMNOPQRSTUVWXY 
 ...für 2. Schritt   YZABCDEFGHIJKLMNOPQRSTUVWX 
 ...für 3. Schritt   XYZABCDEFGHIJKLMNOPQRSTUVW 
 ...für 4. Schritt   WXYZABCDEFGHIJKLMNOPQRSTUV 

Nach dem 4. Zeichen wird wieder mit dem ersten Alphabet begonnen:

   freude am fahren
   EPBQCC XI EAENDL

Zur Vereinfachung dieser Vorgehensweise erdachten sich Alberti und andere sogenannte Ziffernscheiben (Cipher wheels). Sie enthalten auf runden Scheiben zwei Alphabete in kreisförmiger Anordnung, wobei nach jedem Chiffrierschritt die eine Scheibe um je ein Zeichen weitergedreht wird. Wheatstone - richtig! der mit der Brücke! - erfand eine solche Vorrichtung in Taschenuhrform, die auf Tastendruck mechanisch die eine Ziffernscheibe weiterschaltete. Ein solches Vorgehen bietet bessere Sicherheit als die einfache monoalphabetische Substitution, jedoch ist die Sicherheit trügerisch. In jedem Falle ist es sinnvoller, die Zeichen der verwendeten Alphabete in sich zufällig anzuordnen, anstatt sie systematisch aufzuschreiben.

Klassisch ist die polyalphabetische Substitution, die ein Schlüsselwort verwendet. Das Schlüsselwort hat den Vorteil, daß man es sich leicht merken kann und daß es einfach austauschbar ist. Die Grundidee der Verwendung des Schlüsselwortes bei polyalphabetischen Verfahren besteht darin, daß das Schlüsselwort die Anordnung bzw. Auswahl der Schlüsselalphabete vorgibt.

Ein geringfügig angepaßtes Beispiel von Smith, Codes and Ciphers:

Gegeben sei das Schlüsselwort shipwreck. Die Buchstaben werden alphabetisch geordnet und abgezählt:

   cehikprsw
   123456789

Anschließend wird zugeordnet:

   shipwreck
   834697215

Die zu verschlüsselnde Nachricht sei is there safety in numbers. Im folgenden Schritt wird der Klartext unter den Schlüssel geschrieben:

   834697215
   istheresa
   fetyinnum
   bers

Die Zeichen, die in der ersten Spalte stehen, werden durch ein um 8 Zeichen verschobenes Alphabet codiert; i also durch Q, f durch N und b durch J. Wenn die gesamte Nachricht verschlüsselt wurde, ergibt sich:

   834697215
   QVXNNYGTF
   NHXERUPVR
   JHVY

Der Geheimtext lautet also: QVXNN YGTFN HXERU PVRJH VY.

Bei dieser Vorgehensweise wurden insgesamt neun Alphabete zur Verschlüsselung genutzt.

Die Gefahr bei der Verwendung von Schlüsselwörtern, egal welches Verfahren benutzt wird, liegt darin, daß naheliegende, leicht erratbare Schlüsselwörter verwendet werden. Begriffe wie "Heimat", "Vaterland", "patrie" mögen zwar wesentlich zur Motivation der kämpfenden Truppe beitragen; als Schlüssel taugen sie nicht. Bereits einer der Argentis (er arbeitete für die päpstliche Nuntiatur) berichtet, einen Schlüssel innerhalb kurzer Zeit schlicht erraten zu haben: "IN PRINCIPIO ERAT VERBUM".

 Polygraphische Substitution

Verfahren, die im Chiffrierschritt mehr als ein Zeichen des Klartextes verwenden, werden als polygraphische Verfahren bezeichnet. Am häufigsten sind polygraphische Substitutionen, also Substitutionsverfahren, die z.B. je zwei benachbarte Zeichen des Klartextes betrachten ("Bigrammsubstitution"). Bereits Porta (vgl. Bauer) ersann 1563 eine Bigrammchiffre, die 400 phantasievoll erdachte Zeichen des Geheimtextalphabets aufwies. Durch die hohe Anzahl von unterschiedlichen Zeichen des Geheimtextalphabetes war die Verwendung dieses Verfahrens gewiß mühevoll.

Praktikabler ist die Anordnung von Bigrammen aus unserem Standardalphabet V in Form einer Matrix. Die bijektive Abbildung ist also V2 ® V2:

     a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  ...
 a   XZ KJ YJ HP PL EL VB CI DW XN ZL YP VN HH CC ...
 b   LP QT HE RS UR CR ZH GV WC HL YN KT WT MC KH ...
 c   DX MN AO NH SF GI WL MN AH GR BZ HS ZU YM WU ...
 d   KM YZ RY FT TR CR XE JK NY PO GJ JR PE MO VB ...
 e   QU HP QG JQ YQ OB SA NL PX OP VS AF XK XR UQ ...
 ...   ... 

Diese spezielle Matrix ist involutorisch, also z.B. ao ® CC, cc ® AO.

Auf die involutorische Abbildung kann verzichtet werden, was aber die Dechiffrierarbeit erschwert. Die Aufstellung einer solchen Matrix erfordert gute Arbeit, damit Buchstabenhäufigkeiten nivelliert werden. Ideal ist, wenn in jeder Zeile und in jeder Spalte der Matrix jedes Zeichen des Alphabetes genau einmal als erstes bzw. zweites Zeichen auftritt. Anordnungen wie die nächste sind allerdings untauglich, da sie keine echte Bigramm-Substitution darstellt:

   AA AB AC AD ...
   BA BB BC BD ...
   CA CB CC CD ...
   DA DB DC DD ...

 Transposition

Mit Transposition wird allgemein das Verfahren bezeichnet, die Reihenfolge von Zeichen im Klartext zu vertauschen, um den Geheimtext zu erzeugen. Die primitivsten Transpositionsverfahren beruhen darauf, einen Klartext als Ganzes oder wortweise rückwärts aufzuschreiben:

   freude am fahren
   NERHAF MA EDUERF komplett revertiert (Krebs)
   EDUERF MA NERHAF wortweise revertiert

Verfahren dieser Art sind für ernsthafte Verschlüsselungen ungeeignet, zumal es Wörter und Sätze (Palindrome) gibt, die bzgl. der Revertierung invariant sind:

Der Autor erinnert sich an dieser Stelle des genial-köstlichen Doppelschüttlers (also eines Schüttelreims, der schwierigerweise doppelt zweizeilig verschüttelt ist) von N.N.:

   Das Kino hat folgenden dringenden Zweck:
   Daß ein Mann die Billets der Drängenden zwick'
   Man sich in die Reihen, die zwängenden drück'
   und sieht auf der Leinwand bezwingenden Dreck.

Verfahren wie Palindrome oder Schüttelreime fallen eher in die Kategorie "Sprachspielerei", nicht aber in die Kryptologie.

Die klassische Methode der Transposition beruht darin, den Text in Gruppen von Buchstaben aufzuteilen und dann in anderer Reihenfolge zu lesen, also erst alle 1., dann 2. 3. usw. Zeichen. (siehe "Skytale"):

   freude am fahren
   FREUD EAMFA HREN gruppiert
   FEHRA REMEU FNDA permutiert

Eine Verschlüsselung dieser Art offenbart bereits bei einfachen statistischen Untersuchungen, in welcher Originalsprache der Klartext verfaßt wurde. Aus diesem Grunde werden oft kombinierte Verfahren eingesetzt (s. Abschnitt 4.5). Einfache Transpositionschiffren bieten genausowenig Sicherheit wie das Caesar-Verfahren. Besser ist hingegen die Blätterteigmethode. Sie basiert darauf, mehrfache Transpositionsschritte unterschiedlicher Länge durchzuführen. Die Längen der Transpositionsschritte sollten auf jeden Fall teilerfremde Zahlen sein, also z.B. 3, 5, 7. Die Verwendung von Längen wie 5, 10, 15 machen unter Umständen einen Teil der Chiffrierung rückgängig, so daß hier eine complication illusionaire vorliegt.

   to be or not to be that is the question
   TOB EOR NOT TOB ETH ATI STH EQU EST ION gruppiert auf 3
   TENTE ASEEI OOOOT TTQSO BRTBH IHUTN vertauscht und gruppiert auf 5
   TAOTB IESOT RHNEO QTUTE OSBTE ITOHN vertauscht und gruppiert auf 5

Die Jargonbezeichnung "Blätterteig" geht darauf zurück, daß hier - ähnlich wie bei der Blätterteigherstellung - der Text mehrfach "gefaltet" und wieder "ausgerollt" wird.

 Gemischte Verfahren

Gemischte Verfahren versuchen die Schwächen der Substitution bzw. der Transposition zu vermeiden, indem mehrere Substitutions- und Permutationsschritte abwechselnd verwendet werden. Vorsicht ist geboten, wenn Verfahren nacheinander angewendet werden (Überchiffrierung), da diese die Verfahrensklasse der Gesamtverschlüsselung ändert und unter Umständen den vermeintlich besonders sicheren Geheimtext zu einem Glücksfall für den unbefugten Entzifferer macht.

Es sei nochmals an die polyalphabetische Substitution mithilfe eines Schlüsselwortes angeknüpft. Ein vorheriges Beispiel lieferte

   834697215
   QVXNNYGTF
   NHXERUPVR
   JHVY

An diese Substitution kann nun ein Transpositionsschritt angeschlossen werden. Zweckmäßig ist das Auffüllen des vorläufigen Geheimtextes mit Blendern:

   QVXNN YGTFN HXERU PVRJH VYXYZ

Die angefügten Zeichen XYZ sind Blender, die lediglich dazu dienen, den Text auf eine durch 5 teilbare Anzahl von Zeichen zu ergänzen und darüberhinaus den unbefugten Dechiffrierer irrezuführen. Nach der Transposition mit Zyklenlänge 5 ergibt sich:

   QYHPV VGXVY XTERX NFRJY NNUHZ


Stand: 09.10.2002 / hp@hp-gramatke.de
 HPs Home      Kryptologie/Home