Systematisierung der symmetrischen kryptographischen Verfahren


Ausarbeitung zum Vortrag von Dirk Deters vom 24. April 2002 im Seminar

„Analyse kryptographischer Algorithmen“ (bei M. Schwan, J. Koebler)


I. Einführung


Diese folgenden kurzen Definition sollen die wichtigsten Begriffe erläutern, die in der Ausarbeitung verwendet werden.

Ein Kryptosystem besteht aus sechs Komponenten, die hier nocheinmal kurz vorgestellt werden sollen:

      1. Der Klartextraum K ist eine Teilmenge aller mit Hilfe eines Alphabet A1 erzeugbaren Worte beliebiger Länge. Bei der Erstellung eines Klartextes werden nur Worte aus diesem Klartextraum verwendet.

      2. Das Gegenstück hierzu ist der Chiffreraum C. Auch er ist eine Teilmenge aller aus einem Alphabet erzeugbaren Worte. Das Alphabet, aus dem die Chiffrewörter gebildet werden können bezeichnen wir mit A2.

      3. Des weiteren benötigt man einen Schlüsselraum EK, aus dem man einen Schlüssel wählt, mit dessen Hilfe die Verschlüsselung der Nachrichten stattfindet.

      4. Um diese Nachrichten wieder zu entschlüsseln, wählt man einen Schlüssel aus dem Schlüsselraum DK.

      5. Die Verschlüsselung selbst wird durch eine Funktion E beschrieben, die wir Verschlüsselungsfunktion nennen. Diese ist eine Abbildung aus dem Kreuzprodukt der Menge der Klartexte und der Menge der Schlüssel in die Menge der Chiffretexte.

      6. Die Entschlüsselungsfunktion bezeichnen wir als D. Sie ordnet jedem Paar von Chiffretext und Entschlüsselungsschlüssel einen Klartext zu.

Damit wir diese Definition für unsere Zwecke gebrauchen können muss noch eine entscheidende Bedingung gelten:



  1. Eigenschaften symmetrischer Verfahren


Sowohl bei den symmetrischen, als auch bei den asymmetrischen Verfahren ist der Entschlüsselungsschlüssel vom Verschlüsselungsschlüssel ableitbar. Bei den symmetrischen Verfahren jedoch, ist diese Ableitung sehr leicht möglich. Oft ist der Entschlüsselungsschlüssel einfach nur die Umkehrung des Verschlüsselungsschlüssel.

Weiterhin ist für die Geheimhaltung nötig, daß die Schlüssel geheim sind und nur dem Sender und Empfänger bekannt sind. Man spricht daher auch von „Private-Key“-Verfahren. Um genauer zu sein, muß man sagen, daß die Sicherheit dieser Verfahren allein und ausschließlich auf der Geheimhaltung der Schlüssel basiert.

Diese Schlüssel müssen daher über einen sicheren Kanal vor der geheimen Kommunikation ausgetauscht werden, was dazu führt, daß keine spontane Kommunikation möglich ist.

Man kann weiterhin dritten nicht beweisen, daß ein Sender S eine bestimmte Nachricht an einem Empfänger R geschickt hat, was zu rechtlichen Problemen führt, wenn diese Verfahren für Transaktionen angewendet werden würden, ohne weitere Vorkehrungen zu treffen, die dieses Problem beseitigen.

Die Anzahl der Schlüssel, die benötigt wird ist sehr hoch. Möchten n Partner miteinander kommunizieren und jeder soll mit jedem einen anderen geheimen Schlüssel benutzen, benötigt man

, was zum Beispiel bei n=1000 bedeutet, daß man 499.500 Schlüssel benötigte.

Trotz einiger Nachteile von symmetrischen Verefahren, werden diese in der Praxis sehr häufig angewendet, vor allem wegen der hohen Datendurchsatzrate bei der Ver- und Entschlüsselung und der daraus resultierenden schnellen Verschlüsselung auch längerer Nachrichten.


  1. Grundlegende Verfahren


a) Substitution


Bei der Substitution handelt es sich um eines der ältesten Verfahren zur Verschlüsselung von geheimzuhaltenden Nachrichten. Dabei werden nach verschieden Mustern die Klartextbuchstaben durch andere Zeichen ersetzt. Bei diesem Verfahren behält also jeder Buchstabe seine Position, wird aber durch ein anderes Zeichen ersetzt.

Eines der bekanntesten Beispiele hierfür ist die nach seinem „Erfinder“ benannte Caesar-Chiffre. Caesar verschlüsselte seine Nachrichten dadurch, daß er zwei lateinische Alphabete (im Lateinischen gibt es die Buchstaben J, K, W, Y, Z nicht) untereinander schrieb, wobei er das untere um drei Buchstaben nach rechts einrückte.


A B C D E F G H I L M N O P Q R S T U V X

U V X A B C D E F G H I L M N O P Q R S T


Wollte er nun einen der 22 Buchstaben verschlüsseln, so suchte er diesen in dem oberen Alphabet und ersetze ihn durch den darunter stehenden. Man sieht, daß dieses Verfahren eine einfache Entschlüsselung zulässt, da es ja nur 21 mögliche Schlüssel gibt. Diese Schlüssel alle durchzuprobieren ist leicht möglich.

Eine weitere Methode, einen durch dieses Verfahren verschlüsselten Text zu entschlüsseln, ist, von dem Vorkommen der einzelnen Buchstaben in einem Text der entsprechenden Sprache, auf den kodierten Buchstaben zu schleißen. Dieses Verfahren bezeichnet man als Häufigkeitsanalyse. Wie die folgende Tabelle zeigt, ist das Vorkommen der Buchstaben in einem Text im Deutschen oder Englischen nicht gleichmäßig verteilt. Man kann also bei einem Text, der mittels Substitution verschlüsselt wurde, leicht darauf schließen, daß der am häufigsten vorkommende Buchstabe das e ist und so nach und nach den Chiffretext entschlüsseln (dieses Verfahren war allerdings zu Caesars Zeiten noch nicht bekannt).


Mathematisch wird eine Substitution als Abbildung definiert, wobei A1 und A2 Alphabete sind. Wird jeder Buchstabe immer durch den gleichen substituiert (wie bei der Caesar-Chiffre) spricht man von monoalphabetischen Verfahren. Wird das Vorkommen der einzelnen Buchstaben dadurch verschleiert, daß ein Buchstabe mal durch das eine, mal durch ein anderes Zeichen verschlüsselt wird, spricht man von ployalphabetischer Verschlüsselung. Eines der bekanntesten Verfahren, das diese Art der Verschlüsselung benutzt, ist die Vigenère-Chiffre:

Sender und Empfänger vereinbaren ein beliebiges, nur Ihnen bekanntest Schlüsselwort aus dem Klartextraum. Man schreibt über das Klartextwort das Schlüsselwort so oft, bis die Länge des Klartextes erreicht ist. Jeder Buchstabe des Klartextes wird nun mit Hilfe des über ihm stehenden Schlüsselbuchstaben verschlüsselt. Man ordnet jedem Buchstaben eine natürliche Zahl zu (meist die Stelle, an der er im Alphabet vorkommt, also A = 0, B = 1 usw.) und addiert den Wert des Klartextbuchstaben zu seinem zugehörigen Schlüsselbuchstaben. Das Ergebnis ist Modulo der Länge des Alphabets gerechnet, wieder die Zahl eines Buchstaben. Dieser Buchstabe ist der Schlüsselbuchstabe. Einfacher wird die Verschlüsselung, wenn man das Vigenère-Quadrat zur Hilfe nimmt :



Um einen Klartextbuchstaben zu verschlüsseln geht man dann wie folgt vor:

Man betrachtet die Zeile, in der der zu verschlüsselnde Buchstabe am Anfang steht und in dieser Zeile die Spalte, in der in der ersten Zeile der Schlüsselbuchstabe steht. An dieser Stelle steht der Chiffrebuchstabe. Ein kleines Besipiel zeigt, daß beide Verfahren gleichwertig sind :


Schlüsselwort: V E N U S V E N U S V E N U S V

Klartext: p o l y a l p h a b e t i s c h


Man betrachte, um das erste p z verschlüsseln, die p-te Zeile und die v-te Spalte. Hier steht der Buchstabe k. Genauso kann man zu p (Stelle 15 im Alphabet) v (Stelle 21) addieren und erhält 36, was dem zehnten Buchstaben entspricht, also dem k.

So kann man den gesamten Text verschlüsseln und erhält unabhängig vom verwendeten Algorithmus den Geheimtext KSYSSGTUUTZXVMUC.

Wie schon erwähnt ist hier durch die Häufigkeitsanalyse nicht herauszufinden, welcher Buchstabe für welchen steht, da zum Beispiel das p einmal mit k und das andere mal mit t verschlüsselt wurde.


b) Permutation


Eine weitere Möglichkeit, Texte zu verschlüsseln, ist die Permutation. Hier werden Buchstaben nicht durch andere ersetzt, sonder die Stelle, an der sie stehen, wird im Chiffretext eine andere sein. Bei einem Text der Länge 64 kann zum Beispiel folgende Tabelle der Schlüssel sein :



Um einen Text der Länge 64 zu verschlüsseln, würde man einfach nach diesem Tableau die Anordnung der Buchstaben vertauschen. Der erste Buchstabe im Chiffretext, wäre hier der 58. aus dem Klartext und so weiter.

Eine Permutation ist eine bijektive Abbildung , wobei A die Menge aller möglichen Wörter über einem Alphabet ist. Eine besondere Permutation ist die Bitpermutation. Hier ist A={0,1}n, also die Menge aller Binärworte der Länge n. Die Funktion f ordnet nun jeder Stelle im Chiffretext eine Stelle aus dem Klartext zu. Nach dieser Funktion werden nun die Buchstaben angeordnet.

Ein berühmtest Besipiel für eine Permutation ist die sogenannte Skytale, die um 500 v. Chr. die Regierung von Sparta zur Verschlüsselung ihrer geheimen Nachrichten verwendete. Hierbei handelt ist sich um einen Holzstab (Skytale), um den ein Streifen Pergament, wie in der folgenden Abbildung gezeigt, gewickelt wurde. Der Sender schreibt die Nachricht der Länge des Stabes nach auf den Streifen und wickelt ihn dann ab.


Danach scheint er nur eine sinnlose Aufreihung von Buchstaben zu enthalten, wie zum Beispiel die Folgende :


Die Buchstaben wurden also in Ihrer Anordnung vertauscht. Damit die Nachricht entschlüsselt werden kann benötigt man einen Holzstab mit genau dem gleichen Umfang, wie ihn der Sender besaß. Vermutet jemand, der eine solche Nachricht abgefangen hat, daß der Umfang (in Buchstaben ausgedrückt) fünf beträgt, enthält er folgende sinnlose Nachricht:



Nur der Empfänger, der den richtigen Holzstab mit dem richtigen Umfang (hier 6 Buchstaben) besitzt, kann die Nachricht korrekt entschlüsseln:


Auch heute noch werden Permutationsverfahren in der Kryptographie angewendet, um Nachrichten zu verschlüsseln.


c) Produktchiffre


Bei der Produktchiffre werden beide bisher vorgestellten Verfahren, sowohl die Substitution, also auch die Permutation auf einen Text angewendet, um eine noch größere Sicherheit als nur bei der Permutation zu erreichen. Zeichen werden also durch andere Zeichen dargestellt und dann wird auch noch die Anordnung innerhalb des Textes verändert.

Ein bekannter Vertreter für dieses Verfahren ist der DES-Algorithmus.


  1. Art der Verarbeitung


In der Praxis liegen die zu verschlüsselnden Klartexte in unterschiedlicher Länge vor. Die oben vorgestellten Verschlüsselungsverfahren erwarten jedoch eine Eingabe fester Länge (ein Buchstabe, 64 Zeichen,...). Daher wir der zu verschlüsselnde Klartext in Einheiten fester Länge aufgeteilt. Beim Aufteilen in Blöcke spricht man von Blockchiffren, wenn als Eingabe ein einzelnes Zeichen erwartet wird von Stromchiffren. Die Möglichkeiten, die sich hierbei ergeben, sollen im Folgenden erläutert werden.


a) Blockchiffren


Das folgende Schema verdeutlicht die grundsätzliche Arbeitsweise von Blockchiffren. Ein zu verschlüsselnder Klartext M wird in r Blöcke gleicher, fester Länge von n (z.B. 64 Bit) aufgeteilt. Der letzte Block der Länge k (wobei) wird auf die Länge n aufgefüllt. In den letzten n-k Bit muß die Länge k verschlüsselt werden, um bei der Entschlüsselung klarzustellen, bis wohin der Klartext tatsächlich reichte. Diesen Vorgang des Auffüllens bezeichnet man als Padding.

Ein wichtiges Kennzeichen der Blockchiffren ist, daß jeder der r Blöcke mit der gleichen Funktion verschlüsselt wird; der i-te Chiffretextblock entsteht wie folgt : Ci = E(Mi,K).

Der vollständige Chiffretext entsteht durch die Konkatenation der r Chiffretextblöcke, das heißt

C = C1|C2|C3|........|Cr.

Die Entschlüsselung erfolgt dann durch den Entschlüsselungsschlüssel k' und zwar wieder für jeden Block Ci einzeln, aber mit immer dem gleichen Schlüssel.

Bei der Blockchiffre muß der Klartext vor Beginn der Verschlüsselung bereits vollständig vorliegen, da bereits vor der Verschlüsselung klar sein muß wie viele Blöcke zur Verschlüsselung vorliegen und wie lang jeder einzelne ist. Dieses Verfahren eignet sich daher zum Beispiel zum



Verschlüsseln von Dateien auf der Festplatte oder von E-mails.

Möchte man einen Strom von Zeichen verschlüsseln, der während der Verschlüsselung noch weiter eingeht, verwendet man Stromchiffren, deren Arbeitsweise im Folgenden erläutert wird.



b)Stromchiffren


Kennzeichnend für Stromchiffren ist, daß eine Folge von kleinen Klartexteinheiten mit variierenden

Funktionen verschlüsselt wird, im Gegensatz zu Blockchiffren, die ja wie wir gesehen haben, größere Blöcke als Eingabe erwarten. Eine typische Zeichengröße bei Stromchiffren beträgt ein Bit oder auch ein Byte. Die Stromchiffren gehen von dem sogenannten one-time-pad Verfahren aus, das eine absolut sichere Möglichkeit darstellt, Daten zu verschlüsseln. Angenommen es liegt ein Klartext T vor, der aus den Zeichen t1 bis tk besteht. Ein Schlüssel S, der aus den Zeichen s1 bis sk besteht, wird zufällig generiert. Der Chiffretext C = c1.....ck entsteht nun aus der Verknüpfung aller Klartextzeichen ti mit dem zugehörigen Schlüsselzeichen si mittels der Funktion XOR. Folgende Grafik soll dieses Verfahren kurz verdeutlichen:




t1................tk

c1...............ck

s1...............sk


Wie bereits erwähnt ist dieses Verfahren absolut sicher, es besteht jedoch ein großer Nachteil. Der zu jeder Verschlüsselung eigens erzeugte Schlüssel muß mit dem Empfänger ausgetauscht werden, was einen nicht unerheblichen Aufwand darstellt, vor allem auch, weil dieser Austausch über einen sicheren Kanal erfolgen muß.

Ziel ist es daher das one-time-pad Verfahren zu approximieren. Eine gute Lösung besteht in den sogenannten Pseudozufallsfolgen. Zu einem gegebenen Initialwert wird durch einen vorgegebenen Algorithmus deterministisch eine Pseudozufallsfolge erzeugt, die die Eigenschaften einer echt zufällig erzeugten Folge aufweist. Dieser Algorithmus muß nicht verheimlicht werden, da ein eventueller Codebrecher nur mit dem Initialwert die Pseudozufallsfolge erzeugen könnte. Logischerweise muß daher aber der Austausch des Initialwertes zwischen Sender und Empfänger über einen sicheren Kanal erfolgen. Nachdem sich beide Kommunikationspartner über den Initialwert verständigt haben, kann jeder für sich mit Hilfe des Algorithmus' die Pseudozufallsfolge erzeugen.


Das i-te Klartextzeichen wird dann mit dem i-ten Zeichen der Pseudozufallsfolge durch die Funktion XOR verknüpft; so entsteht das i-te Chiffretextzeichen. Bei der Entschlüsselung wird dann wiederum das i-te Chiffretextzeichen mit dem zugehörigen Schlüsselzeichen verknüpft, wodurch wieder das entprechende Klartextzeichen entsteht.


c) Arbeitsmodi von Blockchiffren


1.)Der ECB-Modus (Electronic Code Book)

Der ECB-Modus stellt die einfachste Betriebsart der Blockchiffren dar und entspricht im Wesentlichen dem unter Punkt IV.a) vorgestellten Verfahren. Das entscheidende Merkmal ist, daß jeder Block mit dem gleichen Schlüssel verschlüsselt wird. Daraus ergeben sich gewisse Vorteile, aber auch entscheidende Nachteile:

Vorteilhaft ist, daß die Chiffretextblöcke in beliebiger Reihenfolge entschlüsselt werden können, da der Entschlüsselungsschlüssel immer der gleiche bleibt. Die Schlüssel, die zu Ver- und Entschlüsselung eines Blocks verwendet werden sind ja nicht von den vorherigen Blöcken abhängig. Weiterhin ist daher bei einer fehlerhaften Übertragung nur der jeweilige Block betroffen, da der Chiffretext nur von dem Klartextblock und dem (festen) Schlüssel abhängt.

Dieser letzte angebliche Vorteil entpuppt sich aber schnell als Nachteil, da bei Modifizierung eines Blockes durch einen Angreifer die Manipulation nicht so einfach bemerkt werden kann, da sie sich nur auf den jeweiligen Block auswirkt. Da bei diesem Verfahren gleiche Klartextblöcke immer durch gleiche Schüsseltextblöcke verschlüsselt werden, kann ein Angreifer einen Chiffretext durch eventuell vorher bereits entschlüsselte Blöcke dechiffrieren. Er könnte daher einen Block Cj aus der Folge entfernen, ihn modifizieren und einen eigenen Block einspielen. Beispielsweise könnte er bei einer Überweisung den Block, in dem der Geldbetrag chiffriert ist, durch einen ihm bekannten Block mit einem anderen Betrag ersetzten. Daher ist dieser Modus überhaupt nur geeignet, wenn man jeden Block mit einem Zeitstempel versieht. Aber auch so ist dieser Modus als relativ unsicher einzustufen.

Andere Modi, machen die Verschlüsselung eines Blockes von den vorher verschlüsselten abhängig, wie die im Folgenden vorgestellten Verfahren zeigen.


  1. Der CBC-Modus (Cipher Block Chaining)

Bei diesem Modus verständigen sich die Kommunikationspartner zunächst über einen Initialwert, der genau die Länge der zu verschlüsselnden Klartextblöcke haben muß.


Mit Hilfe dieses Initialwertes wir der erste Klartextblock M1 verschlüsselt und der Chiffretexblock C1 entsteht. Es gilt also . Alle weiteren Chiffretextblöcke werden erzeugt, indem der Klartextblock mit dem vorangegangen Chiffretexblock verschlüsselt wird, also . Die Entschlüsselung erfolgt dadurch, daß alle Chiffretextblöcke mit dem vorangegangen Block XOR-verknüpft werden (nur der erste mit dem Initialwert) und daraus der entsprechende Klartextblock entsteht, d. h. . Der Vorteil bei dieser Art von Verschlüsselung besteht darin, daß zwei gleiche Klartextblöcke nur durch selben Chiffretextblock verschlüsselt werden, wenn auch die Vorgängerblöcke der Klartextblöcke die gleichen waren, was sehr selten ist. Daher kann man nicht mehr davon ausgehen, daß ein eingespielter Chiffretextblock noch sinnvoll entschlüsselt wird. Somit wird der Fehler wohl bemerkt werden. Ein Übertragungsfehler pflanzt sich also auf den folgenden Chiffretextblock fort, aber auch nur auf den nächsten. Daher wird der CBC-Modus als sicherer angesehen als der ECB-Modus. Allerdings muß man, um einen Block zu entschlüsseln bereits alle vorangegangenen Blöcke entschlüsselt haben. Daher verwendet man dieses Verfahren vor allem bei der Verschlüsselung von Dateien, die meist als Ganze verschlüsselt werden; hier ist ein Zugriff auf einen einzelnen Dateiblock meist nicht nötig.

Will man jedoch erreichen, daß sich ein Fehler auf alle folgenden Blöcke auswirkt, empfehlen sich andere Verfahren.


  1. Der OFB-Modus (Output FeedBack)

Dieser Modus funktioniert so, daß die Kommunikationspartner wiederum vor der Kommunikation einen Initalwert und einen Schlüssel austauschen, der für die Erzeugung einer Blockchiffre verwendete werden soll. Möchte der Empfänger nun einen Klartext mit der Länge k Bit verschlüsseln, so wird zunächst mit Hilfe des Schlüssels für die Blockchiffre und des Initialvektors ein Chiffretext der Länge n generiert (dieses n stellt die Obergrenze für die Länge der auf einmal zu verschlüsselnden Klartexte dar, also die für die Blocklänge). Von der so entstandenen Blockchiffre werden die ersten k Zeichen verwendet und einzeln mit den k Zeichen des Klartextes durch XOR verknüpft und zwar vor der Übertragung. Diese k Zeichen sind nun der Chiffretext der ersten k Zeichen des Klartextes. Diese können nun zu dem Empfänger übertragen werden. Die ersten k Zeichen der Blockchiffre werden nun erneut mit Hilfe des Schlüssels kodiert und ergeben zusammen mit den anderen n-k Zeichen der Blockchiffre die neue, für die nächste Verschlüsselung nötige n Zeichen lange Blockchiffre.


Die Entschlüsselung funktioniert genauso wie die Verschlüsselung, nur daß anstatt des Klartextes der Kryptotext als Eingabe und der Klartext als Ausgabe erfolgt. Es entsteht wieder der Klartext,da die XOR-Funktion eine wichtig Eigenschaft hat. Sei hier a ein Zeichen der Blockchiffre, b ein Klartextzeichen und c ein Chiffrezeichen. Bei der Verschlüsselung entsteht c durch folgende Operation: . Bei der Entschlüsselung liegt wieder das gleiche a vor und es gilt.

Für die Blockchiffre gelten bei diesem Verfahren einige Eigenschaften. Die Blockchiffre wird nur generiert, beim Sender wie beim Empfänger, aber niemals wieder dechiffriert. Sie erzeugt bei Sender und Empfänger den gleichen Zeichenstrom, der jeweils synchron bei Sender und Empfänger eingesetzt werden muß. Würde eine Entschlüsselung asynchron erfolgen, d.h. ein Chiffretextzeichen wird mit Hilfe eines falschen Blockchiffrezeichen entschlüsselt, entstünde ein anderer Text als der Klartext. Keines der nachfolgenden Zeichen würde mehr korrekt entschlüsselt werden. Bei diesem Verfahren jedoch gilt ebenfalls, daß ein Fehler, der nur ein einzelnes Chiffrezeichen verändert (sei es durch einen Übertragungsfehler oder einen Angreifer), sich lediglich auf ein eine Stelle auswirkt und nicht alle nachfolgenden Zeichen beeinflusst. Diese Tatsache erleichtert einem eventuellen Angreifer die Arbeit erheblich.

Der folgende Modus versucht nun, auch dieses Problem zu beseitigen.


  1. Der CFB-Modus (Cipher-Feedback)

Im Prinzip arbeitet dieser Modus genauso, wie der OFB-Modus, nur die k Zeichen, die in der Blockchiffre nach jedem Chiffriervorgang ersetzt werden, hängen hier nicht nur vom Ausgang der Blockchiffre und vom Schlüssel ab, sondern auch von den k Klartextzeichen. Der Eingabeblock der Blockchiffre ist nämlich bei diesem Verfahren identisch mit dem Chiffretextblock, der übertragen wird. Daher setzt sich ein vielleicht auftretender Fehler in allen folgenden Zeichen fort, was eine Manipulation sehr schwer macht, da ein Angreifer beachten muß, daß seine Manipulation nicht nur die gewünschte Stelle verändert, sonder auch alle folgenden und daher wahrscheinlich bemerkt werden wird.





Quellenangabe :



12