Chiffrierverfahren

Eine sehr einfache Verschlüsselung erhalten wir, indem wir jedem Buchstaben ein festes Symbol zuordnen. Diese Verfahren heißen monoalphabetisch. Sie sind in der Regel sehr leicht durch Häufigkeitsbetrachtungen zu berechnen. Wesentlich schwieriger ist es, polyalphabetische Geheimtexte zu entschlüsseln. Das sind Texte, bei denen ein Buchstabe mehreren Symbolen entsprechen kann.

Die klassischen Verfahren haben den Nachteil, dass sich Sender und Empfänger über den zu verwendenden Schlüssel verständigen müssen, was eine zusätzliche Unsicherheit bedeutet. Dies entfällt bei den Public-key-Systemen, die seit 1976 entwickelt werden. Das bekannteste unter ihnen, das RSA-Verfahren (nach R. RIVEST, A. SHAMIR und L. ADLEMAN), verwendet die Primfaktorenzerlegung natürlicher Zahlen. Es ist nur so lange sicher, wie es keine wesentlich schnelleren Algorithmen zur Primfaktorenzerlegung gibt als die heute bekannten. Daneben setzt es die Kenntnis genügend vieler großer Primzahlen voraus.

Im folgenden werden einzelne Chiffrierverfahren genauer betrachtet.

1. Cäsar Code (monoalphabetisch)

Beim Verschlüsseln mit dem Cäsar-Code notiert man unter dem Klartextalphabet das Geheimtextalphabet.
Im einfachsten Fall eine Verschiebung um eine bestimmte Anzahl von Stellen. Sender und Empfänger müssen nur die "Verschiebungszahl" vereinbaren. Im folgenden Beispiel wurde das Geheimtextalphabet um 4 Stellen verschoben. Aus dem Buchstaben A wird nun ein E, aus B ein F usw.

Will man z.B. das ist geheim mit der Verschiebezahl 4 verschlüsseln, würde das so aussehen:

Das Cäsarverfahrens kann hier getestet werden:

Das Entschlüsseln ist denkbar einfach. Während beim Verschlüsseln jeder Buchstabe des Klartextes mit der Verschiebezahl addiert wurde, braucht man jetzt nur die Verschiebezahl vom Geheimtext subtrahieren.

Wenn Sie also die verschlüsselte Nachricht HEWMWXKILIMQ erhalten und wissen, dass die Verschiebezahl 4 beträgt, subtrahieren Sie von jedem Buchstaben einfach die Verschiebezahl:

Sie sehen, dieses Verfahren ist nicht besonders sicher. Ein Angreifer müsste maximal nur 25 Möglichkeiten probieren, um den Geheimtext zu entschlüsseln.

Aufgabe

Versuchen Sie folgende Mitteilungen zu entschlüsseln und nennen Sie die Verschiebezahl:

• WJCNEBB EI IKNCAJCNWQAJ
• HRWAPEEHRWLPCO
• PQBHMNZMQ

Das folgende Beispiel ist etwas schwerer. Kleiner Hinweis - es sind drei Wörter:

• SXXSVFGFQQH

Für die Kryptoanalyse könnte Ihnen die folgende Tabelle helfen. Jedem Buchstaben ist seine Position im Alphabet zugeordnet.

Vigenère-Code (polyalphabetisch)

Wenn Sie den Code aus der letzten Aufgabe knacken konnten, hätten Sie Cäsar sicherlich sehr beeindruckt. Er kam jedoch nicht auf die Idee, mehrere Verschiebezahlen in einem Text zu verwenden. Diese Idee hatte aber der französische Diplomat Blaise de Vigenère um 1586.

Sehen wir uns das Beispiel aus der letzten Aufgabe einmal genauer an. Es wurde wieder der Text das ist geheim verschlüsselt. Für das erste Wort wurde die Verschiebezahl 4 verwendet, für das zweite die Verschiebezahl 13 und das letzte Wort wurde mit der Verschiebezahl 2 verschlüsselt.

Ein Text, der auf diese Art verschlüsselt wird, ist viel schwerer zu entschlüsseln, wie Sie vielleicht in der vorangegangenen Aufgabe bemerkt haben.

Richtig schwer wird die Entschlüsselung aber, wenn die Verschiebezahl nicht wortweise wechselt, sondern schon nach jedem Buchstaben.

Wenn wir die gleichen Verschiebezahlen wie vorhin verwenden, sieht das folgendermaßen aus:

Natürlich wird sich das Vigenère Verschlüsselungsverfahren nicht auf drei Verschiebezahlen beschränken. Wenn wir in unserem Beispiel eine Folge von 12 Verschiebezahlen benutzt hätten, wäre sie genauso lang wie der zu verschlüsselnde Text und somit kaum zu entschlüsseln.

Bemerkungen:

• In der Praxis werden anstelle der Verschiebezahlen meist Buchstaben verwendet. Statt der Verschiebezahl 1 würde man den Codebuchstaben A angeben, für die 4 das D, die 26 das Z. So ergibt die Folge von Verschiebezahlen 4/5/19/5/18/20/5/1/7/12/5 das Codewort: desert eagle.

• In der Literatur wird das Vigenère Verschlüsselungsverfahren auch häufig mit Hilfe des Vigenère Quadrats beschrieben statt als mehrfache Anwendung des Caesar Verschlüsselungsverfahren. Dies liegt daran, dass man dieses Quadrat früher als manuelle Hilfe zum Ver- und Entschlüsseln benutzte.

Aufgabe

Verschlüsseln Sie die folgenden Mitteilungen mit dem Codewort ramon.

• Download war erfolgreich.
• Suche Starwars im Tausch gegen Simpsons.

DES  (Data Encryption Standard)

Das DES-Verfahren, das 1976 als amerikanischer Standard entwickelt wurde, wird heute am häufigsten eingesetzt.
Das DES-Verfahren teilt einen Text in 64-Bit-Binärworte, also 8-Byte-Blöcke, und verschlüsselt sie mit einem 56-Bit-Schlüssel.

DES ist eine komplexe Funktion, die auch Permutationen verwendet und mit sechzehn Iterationen ein Ergebnis liefert. Dabei ist der Ausgabewert des einen Schrittes der Eingabewert für den nächsten Schritt, der mit einer Permutation bestimmter Schlüsselbits zuvor verändert wird. Diese Permutationen werden auch Teilschlüssel genannt. Zur Entschlüsselung werden die Teilschlüssel in umgekehrter Reihenfolge verwendet.

Zur Sicherheit von DES

Die Sicherheit dieses Verfahrens ist bislang sehr hoch, da bis heute noch kein Algorithmus veröffentlicht wurde, der den DES knackt. Der DES ist aber nicht unknackbar. Der Angreifer hat heute die Möglichkeit mit leistungsfähigen Rechnern diese Möglichkeiten zu probieren. Es ist daher anzunehmen, dass DES bisher ein guter Verschlüsselungsalgorithmus ist.
Viel größere Bedeutung kommt der Schlüssellänge zu. Bei einer Schlüssellänge von 56 Bit gibt es 2⁵⁶ Schlüssel.

Dreifach-DES

Zur weiteren Erhöhung der Sicherheit entwickelte man den Dreifach-DES, der das DES-Verfahren und verschiedene Schlüssel  k₁ und k₂ verwendet. Dabei wird das DES- Verfahren drei mal hintereinander durchgeführt. Es wird mit k₁ verschlüsselt, mit k₂ entschlüsselt und schließlich mit k₁ wieder verschlüsselt.

Zur Sicherheit von Dreifach-DES

Diese Methode erlaubt es auch, Texte die nach dem ursprünglichen DES-Verfahren verschlüsselt wurden, zu entschlüsseln. Obwohl nur zwei Schlüssel benutzt werden, wird der DES- Algorithmus dreimal angewendet, denn es hat sich herausgestellt, daß man bei nur zweimaliger Anwendung relativ leicht mit einem Frontalangriff die Schlüssel herausfinden kann. Bei drei Iterationen der DES- Funktion ist die effektive Schlüssellänge 112 Bits und damit im Moment relativ sicher.
 

IDEA (International Date Encryption Algorithm)

IDEA ist ein blockorientierter Verschlüsselungsalgorithmus, der 1990 von Xuejia Lai und James Massey entwickelt wurde.
Mit einem Schlüssel von 128 Bit Länge werden Blocks von 64 Bit Länge verschlüsselt. Dabei wird jeder Block achtmal hintereinander und abschließend mit einer Transformation bearbeitet.

Der Algorithmus teilt die 64 Eingabe-Bits in vier 16-Bit-Blöcke auf. In jedem Schritt werden die vier 16-Bit-Blöcke bearbeitet und vier neue 16-Bit- Blöcke erzeugt.

Jede Iteration des IDEA-Algorithmus verwendet drei verschiedene mathematische Operationen, bei denen jeweils zwei 16-Bit-Blöcke auf 16 Bit abgebildet werden. Diese drei Operationen sind:

• bitweises exklusives ODER
• Addition zweier ganzer Zahlen modulo * 2¹⁶ (=65536), die man als vorzeichenlose ganze Zahl behandelt, ebenso wie das Ergebnis. D.h. die Funktion addiert zwei 16-Bit-Zahlen und gibt eine 16-Bit-Zahl aus. Der überlauf im 17. Bit wird "weggeworfen".
• Multiplikation zweier Zahlen modulo  2¹⁶ + 1 (=65537), wobei die Multiplikatoren als vorzeichenlose 16-Bit-Zahlen behandelt werden. Die einzige Ausnahme ist die Folge von 16 Nullen, die 2¹⁶ repräsentiert.

Zur Sicherheit von IDEA

Zusammen ergeben diese drei unterschiedlichen Operationen einen Eingabewert für die komplexe Transformation. Kryptoanalyse ist hier viel schwieriger als bei einem Algorithmus wie DES, der ausschließlich auf einfachen Bit-Masken und Permutationen besteht.

IDEA hat somit einige Vorteile gegenüber DES und sogar im Vergleich zu Dreifach-DES. Erstens macht die Schlüssellänge von 128 Bit einen direkten Angriff fast unmöglich. Zweitens widersteht die innere Struktur von IDEA einer Kryptoanalyse besser. Und schließlich  wurde IDEA so entwickelt, daß Hard- und Softwareimplementationen möglich sind. Bei Vergleichen der Implementationen von IDEA und Dreifach-DES benötigt IDEA weniger Zeit zur Ausführung.

RSA (entwickelt 1977, von Ron Rivest, Adi Shamir und Leonard Adleman)

RSA ist einer der frühesten Algorithmen, die öffentliche Schlüssel verwenden. Der RSA-Algorithmus gilt seitdem als der einzige weitverbreitete und implementierte Ansatz der Verschlüsselung mit öffentlichen Schlüsseln.

Ein nichtmathematisches Beispiel (nach Alfred Beutelspacher)
Vergleichbar ist dieser Algorithmus mit dem Kochen einer geheimen Suppe durch zwei Köche A und B. Beide benutzen die gleiche bekannte Ausgangssuppe. Beide Köche haben jeweils geheime Gewürze. Sogar A kennt die Gewürze von B nicht und umgekehrt. Jeder nimmt zum Beispiel die Hälfte der Ausgangssuppe und fügt seine geheimen Gewürze dazu. Die halbfertigen Suppen werden jetzt ausgetauscht. Sie sind also öffentlich, d. h. jeder könnte sie probieren. Jetzt versetzt B die von A erhaltene Suppe mit seinem Gewürz und A fügt der Suppe von B sein Gewürz hinzu. Nun haben beide die gleiche Suppe mit der richtigen Menge an Gewürzen.

RSA ist eine Verschlüsselungstechnik, bei der Klartext und verschlüsselter Text ganze Zahlen zwischen 0 und n-1 für ein beliebiges n sind. Bei langen Nachrichten wird der Text in einzelne Blöcke aufgeteilt. Jeder dieser Blocks hat eine Länge von log₂n Bit.
Der öffentliche und der dazugehörige geheime Schlüssel sind Funktionsergebnisse einer Funktion über große Primzahlen (wobei ,,groß" hier mindestens 100 bis 200 Stellen bedeutet). Es wird angenommen, daß es ebenso aufwendig ist, aus dem verschlüsselten Text mit Hilfe des öffentlichen Schlüssels den Klartext zu gewinnen, wie die Zerlegung eines Produkts großer Primzahlen zu finden. Um die zwei Schlüssel, den geheimen und den öffentlichen, zu berechnen, nimmt man zwei große Primzahlen p und q, die etwa gleich viele Stellen haben sollten, da dies die Sicherheit erhöht.

Damit berechnet man das Produkt  n=p·q  und  Æ(n)=(p-1)·(q-1).

Nun wählt man eine Zahl e, die anschließend zur Verschlüsselung verwendet wird. Der größte gemeinsame Teiler von e und Æ(n) sollte 1 sein (  ggT(e, Æ(n))=1 ) .

Damit berechnet man den Schlüssel d, der später zur Entschlüsselung verwendet wird:

  e·d=1 mod Æ(n) ,  d=e^-1 · mod Æ(n)

Für d und n gilt auch, dass ihr größter gemeinsamer Teiler 1 ist (ggT(n,e)=1).

Das Zahlenpaar (e,n) bildet den öffentlichen Schlüssel, (d,n)  ist der geheime. Die Primzahlen p und q werden nun nicht mehr benötigt und sollten gelöscht, aber auf keinen Fall veröffentlicht werden.
 

Zur Sicherheit von RSA

Die Sicherheit dieses Algorithmus liegt in der Größe der verwendeten Schlüssel. Um aus dem öffentlichen Schlüssel den geheimen zu berechnen, muß man n in seine Primfaktoren zerlegen. Bei einer Zahl wie 91 mag das noch sehr einfach erscheinen, allerdings wird das bei 2091 (=51·41) schon schwieriger und bei RSA-Schlüsseln mit 200-stelliger Zahl n scheint das unmöglich zu sein.

Damit n geheim bleibt, müssen natürlich auch p und q geheim bleiben. Diese zwei Zahlen können nach der Berechnung des Schlüssels auch gelöscht werden.

Darin liegt aber auch der Nachteil von RSA. Je größer n ist, desto länger ist der verwendete Schlüssel. Die Ver- und Entschlüsselung dauert dadurch lange. Im Vergleich zu IDEA benötigt eine Ver- und Entschlüsselung mit RSA etwa tausendmal soviel Zeit.