Verschlüsselungstechniken

Cäsar und Substitutions-Chiffre  

Schon sehr früh war es notwendig, Geheimnisse vor anderen geheimzuhalten. Der erste echte Code ist daher schon dem römischen Feldherrn Julius Cäsar zu verdanken und trägt auch heute noch seinen Namen.

Das Prinzip war einfach: Anstatt geheime Schlüsselzeichen zu verwenden, wurde einfach das zugrundeliegende Alphabet um einige Zeichen verschoben. Ein solches Verfahren (ROT-13, aus "A" wird "N" usw.) wird auch heute noch verwendet, um bei weniger kritischen Texten zu gewährleisten, dass sie nicht gleich jeder ohne Aufwand lesen kann.

Doch so einfach wie das Prinzip ist auch dessen Entschlüsselung. Man braucht lediglich alle 25 möglichen Verschiebungen durchzutesten.

Ein wenig "komplexer" sind da schon die sogenannten Substitutions-/Ersetzungs-Chiffren. Dabei wird beispielsweise jedem Buchstaben ein willkürlicher aber eindeutiger anderer Buchstabe zugeordnet.

Aber auch hier ist die Entschlüsselung recht einfach möglich. In jeder menschlichen Schriftsprache gibt es für das Auftreten bestimmter Buchstaben (oder Buchstabenkombinationen) relative Häufigkeiten. Diese ändern sich offensichtlich nicht, wenn man jeden Buchstaben immer auf denselben Chiffre-Buchstaben abbildet. Ist der Text dabei genügend lang, so lässt er sich damit schnell entschlüsseln.

Um ein solches Verfahren handelt es sich auch bei der XOR-Chiffre, das ich hier als Beispiel erläutern möchte. Dabei wird jedes Zeichen (oder besser der ASCII-Code jedes Zeichens) bitweise mit einem Schlüsselzeichen nach folgender Vorschrift verknüpft:

Das ist ganz einfach mit der folgenden Routine zu lösen:

Public Function XOR_Chiffre _
(Original As String, bKey As Byte) As String

Dim i As Long
Dim bCode As Byte
Dim bResult As Byte

XOR_Chiffre = ""

For i = 1 To Len(Original)
    bCode = Asc(Mid(Original, i, 1))
    bResult = bCode Xor bKey
    XOR_Chiffre = XOR_Chiffre & Chr(bResult)
Next i

End Function

Ein Beispiel für einen Aufruf dieser Routine ist wie folgt:

Print XOR_Chiffre("Morgen geheimes Treffen", 15)
'   B`}hja/hjgjfbj|/[}jiija

Man sieht leicht, dass aus "e" immer "j" und jedes Leerzeichen zu "/" codiert wird. Entschlüsseln kann man den Text nun mittels des folgenden Aufrufs:

Print XOR_Chiffre("B`}hja/hjgjfbj|/[}jiija", 15)
'   Morgen geheimes Treffen

Da hier zum Ver- und Entschlüsseln jeweils derselbe Schlüssel verwendet wird, spricht man von einem symmetrischen Verschlüsselungsverfahren.

Eine Weiterentwicklung - Vigenere  

Schnell wurde es notwendig, Verfahren zu entwickeln, die den gängigen Untersuchungsmethoden standhalten würden. Im 16. Jahrhundert ging der Franzose Blaise de Vigenere dazu über, ein Schlüsselwort zur Chiffrierung zu verwenden. War dieses Schlüsselwort kürzer als der Klartext, so wurde es zur Chiffrierung genügend oft hintereinander geschrieben. Dazu wies Vigenere jedem Buchstaben von A-Z einen Wert 0-25 zu.

Der Wert jedes Buchstaben des Originaltextes wurde dann zu dem Wert des gerade aktuellen Schlüsselbuchstaben addiert. War das Ergebnis dabei größer als 25, so wurde einfach wieder vorne angefangen (26 substrahiert). Diese Addition nennt man mathematisch "Addition modulo 26".

Ein Beispiel für den Schlüssel "baum":

diesertextsollgeheimbleiben
baumbaumbaumbaumbaumbaumbaum
EIYEFRNQYTMAMLAQIECYCLYUCEH

Diese Vorgehensweise war schon so gut, dass es 300 Jahre dauerte, bis von Kasiski und Friedman ein statistisches Verfahren zur Entschlüsselung entwickelt wurde.

Betrachtet man den obigen Schlüsseltext, so sieht man, dass an den Positionen 8 und 16 der Buchstabe "E" auf den Buchstaben "Q" abgebildet wurde. Findet man diese Regelmäßigkeiten genügend häufig, so läßt sich aus der Differenz der jeweiligen Positionen relativ schnell ein Vielfaches der Schlüssellänge bestimmen (16-8 = 8 = 2 * Len("baum")). Hat man so erst einmal die Schlüssellänge bestimmt, so kann man die Schlüsseltext-Segmente wieder anhand von Buchstabenhäufigkeiten weiter untersuchen.

Vernam und das One-Time-Pad  

Im Jahre 1917 baute Gilbert Vernam einen binären Vigenère-Codierer für Fernschreiber. Der Schlüssel bestand in diesem Fall aus einer Folge von zufällig ausgewählten Bits. Aus dieser Bitfolge wurde für die Verschlüsselung eine Teilfolge ausgewählt, die genauso lang war wie der (in seine Bitfolge umgewandelte) Klartext. Die Bits wurden dabei der oben angesprochenen XOR-Verknüpfung unterzogen.

Im von Joseph Maubogne eingeführten One-Time-Pad fand diese Vernam-Chiffre dann ihre Verbreitung und Anwendung. Es beruht auf der Idee, Sender und Empfänger der Nachricht mit einem nahezu unbegrenzten Vorrat an fortlaufenden, echt zufälligen Schlüsseln auszustatten. Diese sollten nur ein einziges Mal vorhanden sein und gebraucht werden.

Und jetzt kommt der Hammer: Dieses Verfahren gilt als das einzig sichere und unknackbare Verfahren. Das Geheimnis dieser Sicherheit liegt im Schlüssel.

Der Schlüssel gewährleistet durch seine echte Zufälligkeit, dass zu einem Originaltext jeder Schlüsseltext gleich wahrscheinlich ist. In diesem Fall kann man davon ausgehen, dass der so erhaltene Schlüsseltext unbrechbar ist. Es gibt keinerlei Regelmäßigkeiten, mittels derer Informationen für die Kryptoanalyse (also für den Versuch, den Schlüsseltext zu knacken bzw. den Schlüssel zu finden) erhalten werden könnten.

Wo liegt dann der Nachteil dieses Verfahrens? Sicherlich zum Einen darin, in wichtigen Situationen (z.B. auf dem Schlachtfeld) genügend Schlüsselmaterial für den Nachrichtenverkehr zur Verfügung zu haben. Zum Zweiten die Übermittlung der Nachricht. Geht dabei nur ein Bit verloren, so verliert der Schlüsseltext offenbar jegliche Aussage. Zum Dritten die Gewinnung des zufälligen Schlüsselmaterials.

Mittels algorithmischer Vorgehensweisen (wie z.B. in der Visual-Basic-Funktion RND) ist dies im gewünschten Sinne nicht möglich, da diese auch Regelmäßigkeiten beinhalten, die ein Sicherheitsrisiko bedeuten. Das folgende Zitat zeigt hingegen, wie man einen echt zufälligen Schlüssel herstellen könnte:

"Wie erzeugt man einen echt zufälligen Schlüssel? [...]Zeichnen Sie auf, was ein unzuverlässiger Geigerzähler während einer Fahrt über holprige Straßen von einer radioaktiven Probe im Fahrzeug misst, und überlagern Sie anschließend diesen Datenstrom mit dem digitalisierten Rauschen eines Wasserfalls sowie dem Blöken eines Schafes: Da gibt jeder Geheimdienst auf." [Zitat:"Abenteuer Kryptologie" von Reinhard Wobst, S.53]

Da das Verfahren so sicher sein kann, hier der passende Code. Für die Güte des Schlüssels muss der Anwender hingegen selber sorgen: ;-)

Public Function Vernam_Chiffre(Original As String, sKey As String) As String
  Dim i As Long
  Dim bCode As Byte
  Dim bKey As Byte
  Dim bResult As Byte

  Vernam_Chiffre = ""

  If Len(Original) <> Len(sKey) Then
    MsgBox "Text und Key haben ungleiche Längen. " & _
    "Verfahren kann nicht angewendet werden."
    Exit Function
  End If

  For i = 1 To Len(Original)
     bCode = Asc(Mid(Original, i, 1))
         bKey = Asc(Mid(sKey, i, 1))
     bResult = bCode Xor bKey
     Vernam_Chiffre = Vernam_Chiffre & Chr(bResult)
  Next i

End Function

Bei den bislang vorgestellten Verfahren handelt es sich um sogenannte Stream-Chiffren, da immer ein Zeichen nach dem anderen behandelt wird. Im folgenden stelle ich mit dem DES ein sogenanntes Block-Chiffre-Verfahren vor, das immer 8 Zeichen gleichzeitig behandelt.

DES  

Ein wahres Wunderwerk eines Chiffrier-Verfahrens ist der 1973 von IBM im Rahmen einer Ausschreibung des amerikanischen Standardisierungs-Instituts (NBS) entwickelte DES. Bei diesem Block-Chiffre werden mehrere als nicht sicher erartete Verfahren hintereinander ausgeführt (Produkt-Chiffre). Damit wurde ohne die Notwendigkeit eines echt zufälligen Schlüssels ein Verfahren erzeugt, das lange Zeit jeglichem Angriff standhielt.

Erst 1998 gelang es, das Verfahren mittels Brute-Force-Attacke zu knacken. Brute-Force bedeutet, dass jeder mögliche Schlüssel aus dem Schlüsselraum "durchprobiert" und der resultierende Originaltext auf Plausibilität überprüft wird.

DES basiert auf einem 56-bit-Schlüssel (eigentlich umfasst der Schlüssel 64 bit, jedes achte bit wird allerdings nicht verwendet). Ein 64-bit-Block des Originaltextes wird zusammen mit dem Schlüssel einer Kombination von Permutationen (Bit-Vertauschungen), XOR, Bit-Verdoppelungen, Aufteilen, Mischen und 8 sogenannten S-Boxen (Substitutions-Tabellen) unterzogen. Es entsteht ein 64-bit Schlüsseltext.

Seit 1998 gilt das Verfahren natürlich dementsprechend nicht mehr als sicher. Stattdessen wird der sogenannte Triple-DES (112 bit) eingesetzt. Im wesentlichen wird dabei das ursprüngliche DES-Verfahren dreimal hintereinander mit zwei unterschiedlichen Schlüsseln ausgeführt.

Im Hitchhacker's Guide to Cryptography von Claus Schönleber wird näher auf das DES-Verfahren eingegangen.

Unsichere DES-Schlüssel

Bei DES gibt es erwiesenermaßen im gesamten verfügbaren Schlüsselraum 64 Schlüssel, die als unsicher angesehen werden können. Bei der Schlüsselgenerierung ist möglichst darauf zu achten, dass diese Schlüssel ausgesondert werden, damit die Sicherheit nicht leidet. Die Möglichkeit, zufällig einen solchen Schlüssel zu erzeugen ist allerdings sehr gering. Sie liegt bei ca. 1 : (2^50).

Salt - Das Salz in der DES-Suppe

In der Unix-Funktion crypt(), die auch bei PHP zum Einsatz kommt und dazu dient, Passworte für den Verzeichnisschutz im Internet zu verschlüsseln, wird auch heutzutage noch das einfache DES-Verfahren verwendet. Allerdings in folgender Abwandlung: Der Funktion können als optionaler Parameter (dem sogenannten "Salt") zwei zusätzliche Zeichen übergeben werden. Diese Zeichen werden dem normalen Schlüssel vorangestellt und dienen zur Variation dieses Schlüssels.

Das so generierte verschlüsselte Passwort wird in einer Datei abgelegt. Zur Authentifikation bei einer Anmeldung wird der Salt aus der Passwortdatei gewonnen und zusammen mit dem eingegebenen Passwort erneut verschlüsselt und erst dann mit dem gespeicherten Passwort verglichen. Sinn der Sache ist, dass in einer Passwort-Datei dasselbe Kennwort mehrfach vorkommen könnte, ohne dass man dies erkennen dürfte - man stelle sich vor, man kenne sein eigenes Passwort und würde auf diese Weise sehen, dass jemand anderes dasselbe Passwort hat ...

Die Funktion crypt() ist auf verschiedenen Systemen häufig leider sehr unterschiedlich implementiert. So kommt neben dem hier angesprochenen DES häufig auch das im folgenden erläuterte MD5-Hash-Verfahren zum Einsatz.

Fingerabdruck zur Kontrolle - MD5

Der MD5-Algorithmus dient zur Erzeugung einer fälschungssicheren Textprüfsumme (auch MAC genannt). Aus einer Nachricht wird anhand der zugrundeliegenden Hash-Funktion ein Hash-Code mit der Länge von 128 Bits bestimmt. Diese Einwegfunktion bildet eine große Menge von Funktionsargumenten möglichst gleichmäßig auf eine vergleichsweise kleine Menge von Funktionswerten ab. Der Hash-Code ist eine Zahl, die auch nur bei der kleinsten Veränderung des Ursprungstextes nicht mehr übereinstimmen würde, d.h. wenn der Empfänger den Hash-Code des Ursprungstextes hat, kann er damit die Unversehrtheit des Inhaltes der Nachricht überprüfen.

Da die Hauptgefahr der Manipulation an einer Nachricht gerade bei der Übermittlung besteht, kann man entweder den Hash-Code über einen sicheren bzw. vertrauenswürdigen dritten Weg übermitteln, was aber den Sinn eines solchen Codes in Frage stellt, da man ja sofort die ganze Nachricht über den dritten Weg transferieren könnte, oder man bedient sich hier Verschlüsselungsverfahren, um den Hash-Code mit der Nachricht fälschungssicher zu kombinieren. Im PHP Manual gibt's mehr zu crypt, Salt und auch MD5.

Public Key  

Ein Wort zur Schlüsselverteilung

Alle bislang vorgestellten schlüsselbasierten Verfahren setzen offenbar voraus, dass der Schlüssel selber auf einem absolut sicheren Übertragungsweg weitergegeben wird. Da dies nicht immer gegeben ist (wie zum Beispiel in E-Mails), werden dann bevorzugt Verfahren eingesetzt, bei denen dies nicht erforderlich ist. Eines davon sind die sogenannten Public-Key-Kryptosysteme.

Asymmetrische Verfahren und digitale Unterschrift

Public-Key-Kryptosysteme basieren auf Verfahren, die immer zwei paarweise zueinandergehörige Schlüssel erzeugen können. Beide Schlüssel passen so zueinander, dass eine Verschlüsselung mit dem einen Schlüssel immer einzig und alleine mit dem zweiten passenden Schlüssel entschlüsselt werden kann. Und zwar wechselweise.

Der eine Schlüssel dieses asymmetrischen Vorgehens wird im allgemeinen als "Private Key" (privater Schlüssel) und der dazu passende als "Public Key" (öffentlicher Schlüssel) verwendet. Was bedeuten jedoch diese Ausdrücke?

Nun, man kann sich leicht denken, dass auf diese Weise für jeden Nutzer des Public-Key-Systems ein solches Schlüsselpaar erzeugt werden kann. Den öffentlichen Schlüssel kann er jedem beliebigen weiteren Nutzer frei zur Verfügung stellen. Daher entfällt an dieser Stelle die sichere Schlüsselübertragung. Den privaten Schlüssel verbirgt er jedoch gut. Wichtig bei einem solchen Verfahren der Schlüsselfindung ist natürlich noch, dass der private Schlüssel nicht aus dem öffentlichen herleitbar sein darf.

Will nun Nutzer1 eine verschlüsselte Nachricht zu Nutzer2 schicken, so verwendet Nutzer1 dazu den öffentlichen Schlüssel von Nutzer2. Nur Nutzer2 kann diesen Text dann mit seinem privaten Schlüssel entschlüsseln.

Da die verschlüsselte Nachricht selber jedoch im allgemeinen nicht über einen absolut sicheren Übertragungsweg geschickt wird, weiß Nutzer2 nicht sicher, ob die Nachricht wirklich von Nutzer1 stammt. Jeder könnte an Stelle von Nutzer1 die Nachricht mit dem öffentlichen Schlüssel von Nutzer2 verschlüsselt haben.

Um nun die Identität von Nutzer1 als Urheber der Nachricht zu gewährleisten, fügt Nutzer1 der Nachricht eine digitale Unterschrift wie folgt hinzu: Er verschlüsselt die Klartext-Nachricht zunächst mit seinem eigenen privaten Schlüssel, und verschlüsselt das Resultat erst dann mit dem öffentlichen Schlüssel von Nutzer2.

Nutzer2 als Empfänger entschlüsselt die Nachricht zuerst mit seinem privaten Schlüssel. Er findet einen Text vor, den er nur mit dem öffentlichen Schlüssel von Nutzer1 entschlüsseln kann. So ist die Identität von Nutzer1 als Absender der Nachricht gewährleistet.

Das gängigste derzeit verwendete Public-Key-System ist PGP (Pretty Good Privacy = Ziemlich gute Privatsphäre), das erst kürzlich von Network Associates übernommen wurde.

Das RSA-Verfahren

Was noch offen bleibt, ist ein Verfahren, mit dem ein solches Schlüsselpaar gebildet werden kann. Die Wissenschaftler Rivest, Shamir und Adleman arbeiteten 1977 fieberhaft an einem solchen Algorithmus. Sprichwörtlich über Nacht kam Rivest schließlich die entscheidende Idee, die darauf basiert, dass das Produkt zweier sehr großer Primzahlen nur mit äußerst hohem Aufwand in seine Faktoren zerlegt werden kann. Als "sehr groß" werden in diesem Fall Primzahlen bezeichnet, die in der Größenordnung von 10^200 - 10^300 liegen.

Für Interessierte: Die mathematische Grundlage von RSA

Dieses als RSA in die Geschichte eingegangene Verfahren arbeitet mit der sogenannten "modularen Exponentiation". Man wählt zwei möglichst große Primzahlen p und q und bildet ihr Produkt N = p * q. Ebenso merkt man sich das Produkt X = (p-1) * (q-1). Desweiteren wählt man sich eine beliebige Zahl e aus. Die beiden Zahlen e und N werden als öffentlicher Schlüssel weitergegeben.

Zum Verschlüsseln wird wie folgt gerechnet: Schlüsseltext = Klartext ^ e (mod N)

Will man das Ergebnis entschlüsseln, so benötigt man die Zahl d, für die gilt: Klartext = Schlüsseltext ^ d (mod N). Diese Zahl d kann man jedoch nur finden, wenn die Zahlen p und q bekannt sind:

Bestimme d so, dass e * d = 1 (mod X) gilt.

Rechnen wir mal ein Beispiel durch. Hierbei wählen wir der Einfachheit halber zwei kleine Primzahlen (p = 17, q = 11). Damit gilt N = p * q = 187 und X = 160. Wir wählen e = 7. Das Paar (7, 187) ist demnach der öffentliche Schlüssel.

Nehmen wir an, wir wollen damit das Zeichen "X" verschlüsseln. Der ASCII-Code von X ist 88. Es gilt:

88 ^ 7 (mod 187) = 11

Zum Entschlüsseln müssen wir zunächst d bestimmen: 7 * d = 1 (mod 160), das gilt z.B. für d = 23.

11 ^ 23 (mod 187) = 88, und das entspricht natürlich wieder "X".

Schlusswort

Wer mehr zu RSA und anderen am MIT entwickelten Kryptoverfahren (RCx, AES und ähnlichen) erfahren möchte, der kann dies auf der Homepage der RSA Laboratories tun.

Ihre Meinung  

Falls Sie Fragen zu diesem Tutorial haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.