Kryptografie

Klassische Kryptografie

 aufwärts

Symmetrische Verschlüsselung

Ein Sender möchte einem Empfänger eine geheime Nachricht übermitteln. Dabei soll sicher­gestellt werden, dass nur der legitime Empfänger Kenntnis vom Inhalt der Nachricht erhält, aber kein un­berechtigter Dritter, der die Nachricht abfängt oder abhört.

Die klassische Kryptografie löst dieses Problem dadurch, dass der Sender den Klartext m mithilfe einer zusätzlichen Information, des Schlüssels k, in einen Geheimtext c umcodiert (chiffriert, ver­schlüsselt). Mithilfe des Schlüssels kann den Geheimtext wieder ent­schlüsselt (dechiffriert) und der Klartext zurück­gewonnen werden.

Voraus­setzungen für eine geheime Übermittlung sind also, dass

  1. der Empfänger den Schlüssel kennt, den der Sender verwendet hat,
  2. niemand sonst den Schlüssel kennt,
  3. es ohne Kenntnis des Schlüssels unmöglich oder zumindest außer­ordentlich schwierig ist, den Klartext zurück­zugewinnen.

Die Schwierig­keiten liegen darin, dass Sender und Empfänger

  1. einen gemeinsamen Schlüssel vereinbaren müssen, bevor sie geheime Botschaften austauschen können,
  2. den Schlüssel geheimhalten müssen und
  3. ein sicheres Verschlüsselungs­verfahren finden müssen.

Das folgende Bild 1 zeigt schematisch die Ver­schlüsselung eines Klartextes m durch einen Algorithmus f mit Schlüssel k. Der Klartext und der Schlüssel sind geheim, der Algorithmus und der erzeugte Geheimtext c sind im Prinzip öffentlich zugänglich. Um den Geheimtext wieder zu dechiffrieren, muss der Empfänger den Algorithmus f und den Schlüssel k kennen, um einen ent­sprechenden Entschlüsselungs­algorithmus fk' anwenden zu können.

Bild 1: Verschlüsseln und Entschlüsseln
Bild 1: Verschlüsseln und Entschlüsseln

Monoalphabetische Verschlüsselung

Sei A ein Alphabet; im Folgenden sei A das Alphabet der 26 Buchstaben A, ..., Z. Die einfachste Form der Ver­schlüsselung besteht darin, jeden Buchstaben des Alphabets durch einen bestimmten anderen Buchstaben zu ersetzen. Dies bezeichnet man als mono­alphabetische Ver­schlüsselung.

Caesar-Chiffre

Gegeben sei der Klartext ABENDZEIT. Bei der Caesar-Chiffre wird jeder Buchstaben des Klartextes durch z.B. den übernächsten Buchstaben im Alphabet ersetzt (gemäß der alpha­betischen Reihenfolge und zyklisch, d.h. auf Z folgt wieder A). Das Ergebnis ist der Geheimtext CDGPFBGKV.

Mathematisch entspricht diese Ver­schlüsselung einer buchstaben­weisen "Addition" des Textes CCCCCCCCC zum Klartext. Werden die Buchstaben entsprechend der alpha­betischen Reihenfolge von 0 bis 25 nummeriert, so ergibt sich die Summe zweier Buchstaben aus der Summe dieser Nummern modulo 26.

ABENDZEIT
+CCCCCCCCC
=CDGPFBGKV

Der Empfänger kann aus dem Geheimtext den Klartext wieder zurück­gewinnen. Er muss dazu wissen, mit welchem Algorithmus die Ver­schlüsselung vorgenommen wurde (hier: Addition), und er muss den Schlüssel C kennen. Durch Umkehrung des Ver­schlüsselungsalgorithmus (hier: Subtraktion) unter Verwendung des richtigen Schlüssels ergibt sich wieder der Klartext.

CDGPFBGKV
CCCCCCCCC
=ABENDZEIT

Mithilfe einer Chiffrier­scheibe, die auf den Schlüssel, also z.B. auf C eingestellt wird, lassen sich in sehr bequemer Weise Texte chiffrieren und wieder dechiffrieren [Beu 97].

Übungs­beispiel

(Java-Applet zur Veranschaulichung des Chiffriervorgangs mit einer Chiffrierscheibe)

Kryptanalyse

Die Ent­schlüsselung des Geheimtextes ohne Kenntnis des Schlüssels bezeichnet man als Kryptanalyse.

Im einfachsten Fall gelingt die Kryptanalyse durch Ausprobieren aller Möglich­keiten. Im Falle der Caesar-Chiffre gibt es nur 26 verschiedene Schlüssel. Woher will man aber wissen, dass k = C und der Klartext ABENDZEIT, nicht jedoch k = D und der Klartext ZADMCYDHS ist? Dies liegt offenbar an der Redundanz der natürlichen Sprache. In natürlicher Sprache sind nicht alle Zeichen­folgen gleich wahrscheinlich, sondern die Zeichenfolge ABENDZEIT ist z.B. sehr viel wahrscheinlicher als ZADMCYDHS.

Hieraus ergibt sich ein Ansatzpunkt, um komplizierter ver­schlüsselte Texte zu entziffern. Wählt man für den Algorithmus f anstelle einer Verschiebung um i Symbole im Alphabet eine beliebige Permutation des Alphabets, so gibt es hierfür 26! ungefähr gleich 1026 Möglich­keiten; diese lassen sich nicht mehr alle ausprobieren. Aber aufgrund der Tatsache, dass in deutschen Klartexten E der häufigste Buchstabe ist, findet man sehr schnell f(E), nämlich den häufigsten Buchstaben im Geheimtext. Der nächst­häufigste Buchstabe ist N, dann folgen I, S, R, A, T. Hat man die Ent­sprechungen dieser Buchstaben gefunden, so kann man den Klartext meist schon erraten (A_EN__EIT).

Kann für die Kryptanalyse lediglich der Geheimtext herangezogen werden, wird dies als

ciphertext-only-attack

bezeichnet. Ist die Situation gegeben, dass auch ein Teil des Klartextes bekannt ist, so ist dies eine

known-plaintext-attack

Häufig ist es auch möglich, den Klartext zu erraten. So ist es z.B. wahrscheinlich, dass in einem militärischen Text das Wort "Befehl" vorkommt oder dass eine private E-Mail mit "Hallo" anfängt.

Im Falle der Caesar-Chiffre genügt die Kenntnis eines einzigen Klartext­zeichens zusammen mit dem ent­sprechenden Geheimtext­zeichen, um den Schlüssel k bestimmen zu können. Bei Ver­schlüsselung mit einer beliebigen Permutation benötigt man einen Klartext, in dem die wichtigsten Buchstaben mindestens einmal vorkommen. Dann kann man die Zuordnung zu den ent­sprechenden Geheimtext­zeichen ermitteln. Die restlichen Buchstaben ergeben sich aus dem Sinn­zusammen­hang.

Polyalphabetische Verschlüsselung

One-Time-Pad

Werden bei der Ver­schlüsselung die Buchstaben des Klartextes nicht immer durch denselben Buchstaben ersetzt, also beispiels­weise A nicht immer durch C, sondern mal durch Z, mal durch E, mal durch B usw., so ist eine statistische Analyse nach obigem Muster nicht möglich. Eine solche Ver­schlüsselung, bei der die Chiffrier­scheibe bei jedem Textzeichen neu eingestellt wird, bezeichnet man als poly­alphabetische Ver­schlüsselung. Der Schlüssel ist die Folge der Buchstaben, auf die die Chiffrier­scheibe eingestellt wird. Der Geheimtext ergibt sich durch Addition von Klartext und Schlüssel.

ABENDZEIT
+TXEDUBNHW
=TYIQXARPP

Ist der Schlüssel eine gleich­verteilte Zufallsfolge von Buchstaben, so ist dieses Verschlüsselungs­verfahren sogar absolut sicher. Dies liegt daran, dass es genausoviele mögliche Schlüssel wie mögliche Klartexte gibt, jeder Schlüssel gleich­wahr­scheinlich ist und somit auch jeder aus dem Geheimtext rekonstruierte Klartext gleich­wahr­scheinlich ist. Niemand kann sagen, ob der Schlüssel TXEDUBNHW oder YKREPHYPI war. Im einen Falle wird der Geheimtext TYIQXARPP zu ABENDZEIT ent­schlüsselt, im anderen Fall zu VORMITTAG.

Die Ver­schlüsselung durch Addition einer Zufallsfolge heißt Vernam-Chiffre oder One-Time-Pad.

Warum beschäftigt man sich überhaupt noch mit anderen Chiffrier­verfahren, wenn doch ein absolut sicheres Verfahren bekannt ist? Der Nachteil des One-Time-Pad ist, dass der Schlüssel genauso lang wie der Klartext sein muss. Ferner muss der Schlüssel eine echte Zufallsfolge sein, und jeder Schlüssel darf auch nur ein einziges Mal verwendet werden, denn sonst wäre eine known-plaintext-attack möglich. Daher ist das Verfahren für die Praxis im allgemeinen nicht geeignet.

Um dieses Problem zu umgehen, wird in einer ganzen Reihe von Verfahren versucht, mit kurzen Schlüsseln auszukommen, aus denen auf systematische Weise längere Schlüssel gewonnen werden. Dies geht allerdings auf Kosten der Sicherheit der Verfahren.

Vigenère-Chiffre

Eine Methode ist, einen periodischen Schlüssel zu verwenden, der durch fortgesetzte Aneinander­reihung eines kurzen Wortes entsteht, z.B. des Wortes ZEBRA. (Im obigen Übungs­beispiel lassen sich auch Wörter als Schlüssel eingeben). Diese Art der Ver­schlüsselung wird Vigenère-Chiffre genannt.

ABENDZEIT
+ZEBRAZEBR
=ZFFEDYIJK

Auch bei diesem Verfahren wird z.B. das E mal auf F und mal auf I abgebildet, so dass eine einfache statistische Analyse nicht zum Ziel führt.

Dennoch ist bei periodischen Schlüsseln eine statistische Kryptanalyse möglich; bei einem Schlüssel­wort der Länge 2 beispiels­weise müssen 2 Statistiken erhoben werden – eine für die ungeraden und eine für die geraden Positionen des Geheimtextes, denn diese jeweils für sich sind ja mono­alphabetisch ver­schlüsselt. Die Länge des Schlüssel­wortes wird durch Ausprobieren ermittelt.

Im folgenden Übungs­beispiel werden bei Drücken der Schaltfläche "Statistik" nacheinander Schlüssel­wortlängen von 1, 2, 3 usw. ausprobiert. Die richtige Länge s ist gefunden, wenn die Wahr­schein­lich­keitsverteilungen der Buchstaben an den Positionen i·s+1, i·s+2, ..., i·s+s des Geheimtextes jeweils die typische Wahr­schein­lich­keitsverteilung der deutschen Sprache aufweisen. In Form von Diagrammen wird die Häufigkeit der Buchstaben des Geheimtextes an den ent­sprechenden Positionen dargestellt. Der jeweils häufigste Buchstabe entspricht dann dem E. Hieraus lässt sich die jeweilige Verschiebung und damit das Schlüssel­wort berechnen. Ist das richtige Schlüssel­wort gefunden, wird durch Drücken der Schaltfläche "OK" der Geheimtext dechiffriert.

Übungs­beispiel

(Java-Applet zum Entziffern des Geheimtextes ESMXEMHFIBDJFYLDVHJVHSEORLKIFZNGIJKEM...)

Eine andere Möglichkeit ist eine known-plaintext-attack, indem nach einem Wort gesucht wird, das wahrscheinlich im Klartext vorkommt, z.B. nach dem Wort BEFEHL. An jeder möglichen Position wird auf den Schlüssel zurück­gerechnet. Durch Drücken der Taste ">" wird das Suchwort um eine Position weiter­geschoben. Die richtige Position ist gefunden, wenn sich ein periodischer Schlüssel ergibt, wie hier in diesem Beispiel AZEBRA (Voraus­setzung ist, dass das Suchwort länger ist als das Schlüssel­wort).

Übungs­beispiel

(Java-Applet zum Entziffern des Geheimtextes ESMXEMHFIBDJFYLDVHJVHSEORLKIFZNGIJKEM...)

Aus diesem Beispiel wird deutlich, dass ein "kryptisch" aussehender Geheimtext noch lange keine Gewähr dafür bietet, dass er nicht womöglich sogar relativ leicht zu entziffern ist. Auch wenn zur Ver­schlüsselung anstelle einfacher Ver­schiebungen beliebige Permutationen verwendet werden, ist die Kryptanalyse nicht wesentlich schwieriger.

Produkt-Chiffre

Die Periode des Schlüssels lässt sich verlängern, indem der Schlüssel in Teil­schlüssel der Länge 2, 3, 5, 7, 11, ... zerlegt wird und der Klartext nacheinander mit diesen Teil­schlüsseln ver­schlüsselt wird. Dies ist gleich­bedeutend damit, dass aus den Teil­schlüsseln zunächst ein Produkt­schlüssel gewonnen wird, mit dem dann der Klartext ver­schlüsselt wird. Die Periode des Produkt­schlüssels ist das Produkt der Teil­schlüssellängen, die Schlüssel­länge selbst ist aber nur gleich der Summe der Teil­schlüssellängen. Bereits mit einem Schlüssel der Länge 77 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 lässt sich ein Produkt­schlüssel der Periode 107 erzeugen.

Beispiel:  Der Schlüssel sei WOISTREVAL, Teil­schlüssel sind WO, IST und REVAL.

Der Produkt­schlüssel hat die Periode 30; er errechnet sich wie folgt:

WOWOWOWOWOWOWOWOWOWOWOWOWOWOWO
+ISTISTISTISTISTISTISTISTISTIST
+REVALREVALREVALREVALREVALREVAL
=VKKWZYIBPHFLZGANSCERGAJHPXTROS
Autokey-Verfahren

Die Idee beim Autokey-Verfahren ist, einen kurzen Schlüssel durch den Klartext selbst zu verlängern.

Beispiel:  Der Schlüssel sei ARGO.

EINGEHEIMTEXT
+ARGOEINGEHEIM
=EZTUIPROQAIFF

Es ist klar, dass dieses Verfahren gegenüber einer known-plaintext-attack extrem unsicher ist. Aber auch durch statistische Analyse des Geheimtextes lässt sich der Klartext rekonstruieren. Der am häufigsten vorkommende Buchstabe im Geheimtext (im obigen Beispiel das I) entspricht an den meisten Positionen der Kombination E / E. Ist die Länge s des Schlüssels bekannt, so lässt sich ausgehend von diesen Positionen jedes s-te Klartext­zeichen ent­schlüsseln (im Beispiel E_N_E_E_M_E_T).

Summen-Verfahren

Eine Modifikation des Autokey-Verfahrens besteht darin, jeden Klartext­buchstaben durch die Summe der s vorher­gehenden Buchstaben und des Buchstabens selber zu verschlüsseln. Dadurch sollen die unter­schiedlichen Buchstaben­häufigkeiten über einen Bereich der Länge s+1 gemittelt werden, so dass eine statistische Analyse nichts ergibt. Die s vorher­gehenden Buchstaben des ersten Klartext­buchstabens werden wiederum durch einen Schlüssel der Länge s gebildet.

Beispiel:  Der Schlüssel sei KEY.

EINGEHEIMTEXT
+YEINGEHEIMTEX
+EYEINGEHEIMTE
+KEYEINGEHEIMT
=QOXFFEVXFRRGN

Anhand des Schemas wird deutlich, dass jeweils zwei aufeinander­folgende Buchstaben des Geheimtextes c durch Summation fast derselben Buchstaben des Klartextes m gebildet werden – nur ein Buchstabe ist jeweils anders. Es ist ci+1 = ci – mi-s + mi+1. Jedes Geheimtext­zeichen hängt also in Wirklichkeit nur von zwei Klartext­zeichen ab. Somit ist wiederum eine statistische Analyse wie beim einfachen Autokey-Verfahren möglich: Ist ci+1 = ci, so ist mi-s = mi+1. Die Wahr­schein­lich­keit dafür, dass zwei bestimmte Klartext­buchstaben gleich sind, ist am höchsten, wenn diese gleich E sind. Wird die Länge des Schlüssels richtig erraten, so lässt sich im obigen Beispiel aufgrund der Geheimtext­zeichen FF und RR der Klartext E_N_E_E_M_E_T rekonstruieren.

Enigma

Wenn die Periode des Schlüssels sehr lang wird, ist eine Entzifferung schwierig oder sogar unmöglich. Das Problem liegt jedoch darin, dass sehr lange Schlüssel in der Praxis schwer zu handhaben sind. Als Lösung wird versucht, einen langen Schlüssel aus einem kurzen Schlüssel zu erzeugen, aber nicht durch bloße Aneinander­reihung des kurzen Schlüssels, sondern auf kompliziertere Art und Weise.

In der im Zweiten Weltkrieg verwendeten deutschen Ver­schlüsselungsmaschine Enigma befinden sich drei Rotoren, die sich ähnlich wie ein Kilometer­zähler bei jedem Buchstaben weiterdrehen. In jedem Rotor ist eine Permutation des Alphabets fest verdrahtet. Die Permutationen aller drei Rotoren sind hinter­einandergeschaltet. Auf diese Weise entsteht eine sehr große Zahl unter­schiedlicher Permutationen, und jedes Symbol des Klartextes wird mit einer anderen Permutation ver­schlüsselt. Als Parameter dieses Verschlüsselungs­verfahrens war lediglich die Anfangs­stellung der Rotoren zu übermitteln, dieser Parameter stellte den täglich wechselnden kurzen Schlüssel dar.

Lediglich aus Kenntnis des Geheimtextes ist dieser Code nicht zu ent­schlüsseln. Das Problem ist jedoch, dass nicht nur der Schlüssel, sondern insbesondere die Rotoren geheim­zuhalten sind, die die Systematik der Erzeugung des langen Schlüssels enthalten. Außerdem ist dieses Verschlüsselungs­verfahren nicht gegenüber einer known-plaintext-attack sicher. Tatsächlich wurde die Enigma sowohl von den Polen als auch von den Engländern recht bald geknackt.

Pseudozufallsfolgen

Die zuletzt erwähnten Verfahren kranken alle daran, dass aus einem relativ kurzen Schlüssel in systematischer Weise ein langer Schlüssel generiert wird. Gelingt es, die Systematik der Schlüssel­erzeugung zu durchschauen, so ist der lange Schlüssel nicht sicherer als der kurze Schlüssel.

Nur wenn der lange Schlüssel keinerlei Systematik unterliegt, wie dies beim One-Time-Pad der Fall ist, ist das Verfahren absolut sicher. Wie bereits erwähnt, ist der Nachteil dieses Verfahrens, dass ein sehr langer Schlüssel notwendig ist. Naheliegend ist daher die Idee, anstelle der beim One-Time-Pad verwendeten Zufallsfolge eine Pseudo­zufalls­folge zu verwenden. Sender und Empfänger verwenden denselben Zufalls­zahlengenerator. Sie brauchen nur den Startwert des Zufalls­zahlengenerators zu vereinbaren und können somit beide dieselbe Zufallsfolge erzeugen. Das Problem des Austauschs eines langen Schlüssels entfällt also.

Allerdings enthält eine Pseudo­zufalls­folge, auch wenn sie zufällig aussieht, eine sehr starke Systematik, nämlich die des Zufalls­zahlengenerators. Schon wenige Zeichen des Klartextes zusammen mit dem ent­sprechenden Geheimtext reichen möglicher­weise aus, um diese Systematik zu durchschauen und alle weiteren und alle vorher­gehenden Zufalls­zeichen zu erzeugen. Diese scheinbar geringfügige Abwandlung eines perfekten Verschlüsselungs­verfahrens (Pseudo­zufalls­zahlen anstelle echter Zufalls­zahlen) führt also zu einem extrem unsicheren Verfahren (siehe Erzeugung von Zufallsbits).

Literatur

[Beu 97]A. Beutelspacher: Geheimsprachen. C.H. Beck (1997)
[Wel 88]D. Welsh: Codes and Cryptography. Oxford University Press (1988)

 

Weiter mit:   up

 

homeH.W. Lang   Fachhochschule Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 12.02.2001   Updated: 26.06.2015
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot:

Web- und Softwaretechnologie

Ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien...

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Und ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten IT-Sicherheit, Mobile Computing und Human-Computer Interaction...

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnologie

Wirtschaftsinformatik