Kryptologie » Beschreibung unterschiedlicher Verfahren

Warnung: Dieser Text aus dem Jahre 2005 ist ungenau und teilweise veraltet oder falsch.

Einweg-Verschlüsselung

Einweg-Verschlüsselung heißt, dass eine beliebig große Quellmenge auf eine bestimmte Zielmenge abgebildet wird. Aus der Zielmenge soll sich die Quellmenge nicht effektiv zurückrechnen lassen, die gesamte Zielmenge soll sich total verändern wenn nur ein einzelnes Zeichen in der Quellmenge verändert wird und es soll möglichst wenig Kollisionen, d. h. mehrere Quellmengen mit der selben Zielmenge geben. Die Zielmenge nennt man Hash bzw. Prüfsumme. Das im Moment meistverwendete Format dafür ist der MD5-Algorithmus, welcher 32 Hex-Stellen erzeugt. Der MD5-Algorithmus gilt mittlerweile als unsicher, als Ersatz wird SHA-1 empfohlen (von der NSA mitentwickelt, zeigt mittlerweile auch leichte Schwächen…).

Beispiele

TypTextHash
MD5 Franz jagt im komplett verwahrlosten Taxi quer durch Bayern 3cca2b2aa1e3b5b3b5aad99a8529074
MD5 franz jagt im komplett verwahrlosten Taxi quer durch Bayern 4679e94e07f9a61f42b3d7f50cae0aef
SHA-1 The quick brown fox jumps over the lazy dog 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
SHA-1 The quick brown fox jumps over the lazy cog de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3

Brechen der Einweg-Verschlüsselung.

Aus dem Hash lässt sich - wenn wir davon ausgehen, dass der Algorithmus fehlerfrei ist - die Quellmenge nicht zurückrechnen, schon allein weil es unendlich viele Quellmengen mit dem gleichen Hash gibt. Die Einweg-Verschlüsselung wird oft zum Speichern von Passwörtern benutzt: Bei der ersten Eingabe des Passwortes wird dieses einweg-verschlüsselt gespeichert, bei der späteren Überprüfung des Passwortes wird das erneut eingegebene ebenfalls einweg-verschlüsselt und mit dem gespeicherten Hash verglichen. Wenn ein Angreifer die Passwortdatei stiehlt, hat er nur die Hashs, und kann das eigentliche Passwort daraus nicht ermitteln.
Es gibt aber natürlich schon eine Möglichkeit: Den Zufall. Ein durchschnittlicher PC schafft ca. 3 Millionen zufällige Test-Kombinationen pro Sekunde. Das funktioniert so, dass er einfach eine beliebige Zeichenkette erzeugt, den Hash davon mit dem zu knackenden vergleicht und dann das Ergebnis ausgibt. Dieses Verfahren nennt man Brute Force (engl. "Rohe Gewalt").

Alternativ kann man ein Brute Force-Programm laufen lassen, und alle Kombinationen in einer Datenbank aufzeichnen - d. h. es werden Passwörter und die zugehörigen Hashs erstellt. Die resultierende Liste (deren Erstellung äußerst lang braucht) ist unheimlich groß, meistens sehr unvollständig. Wenn man aber einen Hash hat, der in der Liste vorkommt, kann man das zugehörige Passwort innerhalb von wenigen Sekunden ermitteln.

Sichere Passwortwahl

Ein sicheres Passwort muss deshalb darauf ausgelegt sein, Brute Force-Attacken möglichst lange zu widerstehen. Deshalb sollte es möglichst lang sein und viele verschiedene Zeichen verwenden, d. h. Zahlen, Buchstaben in Groß- und Kleinschreibung als auch Sonderzeichen.
Die benötigte Maximalzeit um ein Passwort zu knacken errechnet sich aus
Anzahl der verwendeten ZeichenPasswortlänge * (1/Kombinationen pro Sekunde)
Wenn wir z. B. ein 6 Zeichen langes Passwort haben, das aus Zahlen und Buchstaben (Groß als auch Kleinschreibung) besteht und unser Computer 3 Millionen Kombinationen pro Sekunde prüfen kann, würde die Rechnung 626*(1/3000000)=5h lauten. Bei 5 Zeichen wären es nur 5 Minuten, bei 8 Zeichen schon 2 Jahre. Die benötigte Zeit steigt also exponentiell. (Zu beachten ist, dass die angegebenen Zeiten eine Maximalzeit darstellen, mit einer Wahrscheinlichkeit von 50% wird nur die halbe Zeit benötigt.)

Monophone Verschlüsselung

Monophone Verschlüsselung heißt, dass einfach ein Zeichen durch ein anderes ersetzt wird. Ein anderes Wort dafür ist Substitution. Wenn ich z. B. alle Zeichen in einem Text um eins verschiebe, also statt A B und statt C D verwende, Z dann wieder zu A wird usw. habe ich eine Cäsar-Verschiebung (online ausprobieren!), eine einfache monophone Verschlüsselung. Monophone Verschlüsselungen sind relativ leicht zu knacken, da sie gegen Häufigkeitsanalysen sehr anfällig sind. Wenn man nämlich die Sprache des zu entschlüsselnden Textes kennt, kann man die Zeichen zählen, und deren Prozentsatz mit den Prozentsätzen der Normalverteilung vergleichen. Sowohl im Deutschen (17%) als auch im Englischen (13%) ist das "e" der häufigste Buchstabe. Wenn dann auffällt, dass ein Zeichen ähnlich häufig wie das "e" im Durchschnitt vorkommt, kann man davon ausgehen, dass eben dieses "e" mit dem Zeichen ersetzt wurde. Erschweren lässt sich diese Häufigkeitsanalyse durch sinnlose Zeichen, die nur verwirren sollen, oder Zeichen die ein vorheriges rückgängig machen. Umso mehr nach dem selben System verschlüsselte Texte vorhanden sind, umso besser lassen sich diese mit der Häufigkeitsanalyse knacken.
Ein Tool zur Häufigkeitsanalyse und eine Übersicht der durchschnittlichen statistischen Verteilung gibts hier.

Polyalphabetische Verschlüsselung

Polyalphabetische Verschlüsselung heißt, dass mehrere verschiedene Ersatz-Alphabete zur Substitution verwendet werden, die nacheinander durchwechseln. Ein Beispiel dafür ist die Vignère-Verschlüsselung. Bei dieser werden 26 Alphabete erzeugt, die alle immer um ein Zeichen verschoben sind. Diese werden untereinander geschrieben, als Spaltennamen wird das normale Alphabet von A bis Z verwendet:

abc...
BCD...
CDE...
.
.
.
.
.
.
.
.
.
 

Möchte man jetzt einen Text "PENETRATIONSPREISPOLITIK" verschlüsseln, und hat als Schlüsselwort "POLY", verschlüsselt man den ersten Buchstaben mit der Zeile der Tabelle, in der in der Spalte "a" der Buchstabe "P" steht, geht dann in die Spalte "p" und verwendet den entsprechenden Buchstaben für den verschlüsselten Text. Bei dem darauffolgendem "E" wird in der Zeile mit dem "O" am Anfang mit Spalte "e" nachgesehen, und der Buchstabe dort ausgewählt. So macht man das ganze "POLY" mit dem "PENE" durch, bei dem "TRATIONSPREISPOLITIK" wird das "POLY" dann einfach wiederholt, also "POLYPOLYPOLYPOLYPOLYPOLY".
Aber auch die Vignère-Verschlüsselung lässt sich knacken. Es ist nicht unwahrscheinlich dass eine sich wiederholende Zeichenkette im verschlüsselten Text vorkommt. Zählt man den Abstand zwischen zwei gleichen Zeichenketten, dann werden die Teiler dieses Abstandes genommen. Beträgt der Abstand z. B. 20 Zeichen, sind die ganzzahligen Teiler 1, 2, 4, 5, 10 und 20. 1 ist Blödsinn, dann wäre es ja nur eine monoalphabetische Verschlüsselung. 2 ist fraglich, weil das ein sehr kurzes Schlüsselwort wäre. Um sicher zu gehen sollten weitere sich wiederholende Zeichenketten gefunden werden, um die Anzahl der möglichen Teiler einzuschränken. Wenn man z. B. die Abstände 5, 20, 95 und 120 hat ist der einzige gemeinsame Teiler 5. Dann kennt man die Länge des Schlüsselwortes. Jetzt lässt sich eine Häufigkeitsanalyse durchführen: Jeder fünfte Buchstabe wird einbezogen. Anschließend noch eine Häufigkeitsanalyse um ein Zeichen verschoben, und dann noch dreimal... Das funktioniert allerdings nur wenn der Text ausreichend lang ist.

Homophone Verschlüsselung

Die homophone Verschlüsselung ist monoalphabetisch, und ordnet einem Buchstaben mehrere Ersatz-Zeichen zu. Und zwar genau so viele, wie dieses Zeichen im Anzahl-Verhältnis zu den anderen einnimmt, d. h. für das "e" z. B. 17 Ersatz-Zeichen, für das "n" 10, für das "i" 8, für das "a" 7, für das "z" 1 usw. Das macht eine "normale" Häufigkeitsanalyse unmöglich, da im Bestfall jedes Zeichen 1% einnimmt. Die homophone Verschlüsselung kann durch Häufigkeitsanalyse von Zeichenketten, also z. B. Silben durchgeführt werden. Im Deutschen sind die häufigsten Doppelbuchstaben "ss", "nn", "ll", "ee" und "rr".

RSA

Das RSA-Kryptosystem ist assymetrisch. Es funktioniert wie folgt: Jeder User hat einen öffentlichen und einen privaten Schlüssel, den öffentlichen darf jeder wissen, den privaten nur der User selbst. Der private Schlüssel besteht aus zwei teilerfremden Primzahlen, p und q. Öffentlich ist eine Zahl e größer 1, die ebenfalls teilerfremd zu p und q ist. Weiterhin ist N = p * q öffentlich. Nehmen wir p = 17, q = 11, e = 7 und somit N = 187 an. Der private Dechiffrierschlüssel d lässt sich aus e * d = 1 MOD ((p-1)*(q-1)) ermittlen. Mittels des euklidischen Algorithmus lässt sich daraus nämlich d = 23 errechnen.
Wenn jetzt ein anderer User den Text M als Geheimtext C verschicken möchte, wendet er die Formel C = Me MOD N an, wenn wir als Text nur die Zahl 88 nehmen, gibt das 887 MOD 187 = 11. Dieser User schickt jetzt seinen Geheimtext C = 11 also an den Empfänger, dessen Daten für die Verschlüsselung verwendet wurden.
Dieser kann dann mit der Formel M = Cd MOD N den ursprünglichen Text zurückrechnen, in unserem Fall also 1123 MOD 187 = 88.
Zusammengefasst haben wir gerade gezeigt, dass sich sehr einfach eine Verschlüsselung realisieren lässt, die es erlaubt, die Entschlüsselung nur mit dem privaten Schlüssel eines Users möglich zu machen, obwohl man selbst nur dessen öffentlichen kennt. PGP basiert auf RSA und sollte deswegen selbst für Großrechner nahezu unknackbar sein. Jedes wichtige Mail-Programm bietet PGP/GPG-Support an, auch lokale Dateien lassen sich komfortabel verschlüsseln. Instant-Messaging-Clients wie Psi, Gaim oder Kopete bieten ebenfalls GPG-Verschlüsselung an.

© 2009 Julian von Mendel (http://derjulian.net) | Datum: 16.12.2018