Home > Kryptographie > Asymmetrische Kryptographie
Kryptographie
Bisher haben wir uns nur mit Verfahren beschäftigt, die nach dem folgenden Schema arbeiten:
Alice übermittelt Bob eine Botschaft, die mit einem bestimmten Schlüssel verschlüsselt ist. Die Übertragung erfolgt über einen unsicheren Kanal – denn stände den Beiden ein sicherer Kanal zur Verfügung, bedürften sie auch keiner Verschlüsselung. Das heißt, sie nehmen durchaus in Kauf, dass möglicherweise ein Lauscher die Kommunikation abhört, hoffen aber, dass er die Verschlüsselung nicht brechen kann (wenn das Passwort gut gewählt ist und eine sichere Chiffrierung verwendet wird, sinkt die Wahrscheinlichkeit drastisch, dass er die Botschaft tatsächlich in annehmbarer Zeit – falls überhaupt – brechen kann). Wenn alles gut geht, erhält Bob die Nachricht und ist dann hoffentlich in der Lage, die Botschaft mit Hilfe des vorher vereinbarten Schlüssels zu entschlüsseln. Aber genau dort lauert das Problem: Alice und Bob verfügen lediglich über einen unsicheren Kanal. Der Schlüssel muss unbedingt geheim bleiben, die Übertragung also über einen sicheren Weg erfolgen. Allerdings sind Kanäle dieser Art äußerst rar. Die Beiden könnten sich ja irgendwo treffen und dort einen geeigneten Schlüssel vereinbaren. Aber das geht nun mal nicht immer. Ein Beispiel: Alice wohnt in Deutschland, Bob in Amerika, sie schicken sich gegenseitig E-Mails. Wie soll das Problem in diesem Fall gelöst werden? Sie können sich schließlich nicht so "ohne Weiteres" treffen, das erfordert schon etwas mehr Planung und kostet zudem auch noch recht viel Geld. Und vielleicht wollen sie das auch gar nicht. Es müsste eine andere Möglichkeit geben, sich auf sicherem Wege E-Mails zu schicken: Bob entschlüsselt die Nachricht mit einem anderen Schlüssel, d. h., die Schlüssel zur Ver- und Entschlüsselung sind nicht identisch. Diese Art von Kryptographie nennt man asymmetrische Kryptographie. Sie kommt in vielen E-Mail-Verschlüsselungs-Programmen zum Einsatz, von denen Ihnen wohl eines geläufig sein sollte: Pretty Good Privacy, kurz PGP. Wenn nicht, macht nix, auf der offiziellen Webseite gibt's mehr Informationen.
Also. Zurück zu unserer Ausgangssituation: Alice möchte Bob eine verschlüsselte Nachricht schicken. Diesmal verschlüsselt sie die Daten jedoch nicht wie gewohnt mit einem bereits festgelegten Schlüssel, sondern mit Bobs öffentlichem Schlüssel. Bob selbst hat seinen eigenen, nichtöffentlichen (privaten) Schlüssel. Nur mit diesem gelingt es ihm, die verschlüsselten Daten zu lesen. Bob hat also zwei Schlüssel: einen öffentlichen (public key) und einen privaten, geheimen (private key). Aufgrund dieses Konzepts bezeichnet man asymmetrische Kryptographie häufig auch als Public-Key-Kryptographie.
Ja, es gibt Algorithmen für die Public-Key-Verschlüsselung. Der erste dieser Art wurde in den Siebzigern von Ralph Merkle und Martin Hellman entwickelt. Da er auf dem sog. Rucksackproblem basiert, heißt er sinnigerweise Rucksackalgorithmus (engl. knapsack algorithm). Dieses Problem beschreibt Schneier folgendermaßen: Gegeben ist eine Reihe von Objekten von unterschiedlichem Gewicht. Ist es möglich, einige dieser Objekte so in einen Rucksack zu packen, dass dieser ein vorgegebenes Gesamtgewicht erreicht? Ein kleines Beispiel:
Klartext: 1 1 1 0 0 1 Rucksack: 1 5 6 11 14 20 Chiffretext: 1 + 5 + 6 + 20 = 32
Erläuterung: Ist das Klartextbit eine "1", so bedeutet dies, dass das Objekt mit in den Rucksack eingepackt wird. Eine "0" bedeutet entsprechend das Gegenteil. Man erhält nun den Chiffretext, in dem wir die Zahlen, die durch eine "1" als "im Rucksack enthalten" markiert sind, addieren. Alle anderen Zahlen werden ignoriert. Im obigen Beispiel ergibt sich als Gesamtgewicht der Wert 32.
Das Verfahren funktioniert nun wie folgt: Wir erzeugen eine Rucksackfolge mit der sog. Superincreasing-Eigenschaft. Das bedeutet, dass jede Zahl in der Folge größer als die Summe der vorherigen ist. Ein Beispiel für solch eine Folge ist {2, 3, 6, 13, 27, 52}. Mit Hilfe modularer Arithmetik wird daraus eine "normale" Rucksackfolge generiert: Jedes einzelne Glied in der Folge wird mit einer Zahl n modulo m multipliziert, wobei m (der Modul) größer als die größte Zahl in der Folge und n keine gemeinsamen Teiler mit dem Modul haben sollte. Aus 2 wird so die Zahl 62 (2 · 31 mod 105), aus 3 die Zahl 93 (3 · 31 mod 105) usw. erzeugt. Die normale Rucksackfolge lautet {62, 93, 81, 88, 102, 37}; sie stellt den öffentlichen Schlüssel dar. Die Rucksackfolge mit der Superincreasing-Eigenschaft ist der private Schlüssel.
Zur Verschlüsselung einer binären Nachricht wird diese in Blöcke, deren Länge der Anzahl der Elemente im Rucksack entspricht, zerlegt. Wie oben beschrieben werden die Zahlen der Rucksackfolge, welche durch den Klartextblock mit einer "1" markiert sind, addiert. Die Summe bildet den Chiffretext. Die Nachricht "101101" wird z. B. verschlüsselt zu
Klartext: 1 0 1 1 0 1 Rucksack: 62 93 81 88 102 37 Chiffretext: 62 + 81 + 88 + 37 = 268
Der Empfänger kennt sowohl den privaten Schlüssel (die ursprüngliche Rucksackfolge) als auch die Parameter m und n. Zur Entschlüsselung der Nachricht muss zunächst n−1 so bestimmt werden, dass n(n−1) mod m = 1. Er multipliziert jeden Chiffretextwert mit n−1 mod m und erhält die Klartextwerte mit Hilfe des privaten Rucksacks. In unserem Fall ist n−1 61, also müssen die einzelnen Werte des Chiffretextes mit 61 modulo 105 multipliziert werden. Bezogen auf unser Beispiel mit dem Chiffretextwert 268 ergibt sich der Wert 73 aus der Rechnung 268 · 61 mod 105. Das heißt:
Rucksack: 2 3 6 13 27 52 gesucht: ? ? ? ? ? ? = 73 Klartext: 1 0 1 1 0 1
Es werden also die Glieder in der Folge gesucht, die addiert den Wert 73 ergeben. Dieses Problem kann dank der Superincreasing-Eigenschaft glücklicherweise schnell gelöst werden: Man nimmt die größte Zahl der Folge und vergleicht sie mit dem Gesamtgewicht. Ist das Gesamtgewicht größer als diese Zahl, so kommt sie nicht in den Rucksack. Ist das Gesamtgewicht größer oder gleich dieser Zahl, wird die Zahl eingepackt. Man reduziert nun das Gesamtgewicht um diesen Wert und fährt mit der nächstkleineren Zahl fort, bis alle Werte der Folge überprüft sind. Erreicht das Gesamtgewicht die Zahl 0, so gibt es eine Lösung, andernfalls nicht. Für unser Beispiel mit dem Gesamtgewicht 73 gilt: 73 ist größer als 52 (die größte Zahl der Rucksackfolge), also ist 52 im Rucksack enthalten. Das Gesamtgewicht wird nun um den Wert 52 verringt. Das verbleibende Gewicht von 21 ist nicht größer als der nächstgrößere Wert der Folge (27), also befindet sich 27 nicht im Rucksack, sehr wohl aber die 13 als nächste Zahl. Die nachfolgenden Rechnungen zeigen, dass auch 6 und 2 im Rucksack enthalten sind. Als Endgewicht ergibt sich 0, also gibt es eine Lösung (73 − 52 − 13 − 6 − 2 = 0).
In der Praxis: Rucksäcke mit nur sechs Elementen reichen natürlich nicht aus, um ein gewisses Maß an Sicherheit zu bieten. Echte Rucksäcke sollten mindestens 250 Elemente enthalten, deren Werte zwischen 200 und 400 Bit lang sein sollte; die Länge des Moduls sollte zwischen 100 und 200 Bit liegen. Die Werte sollten mit einem Zufallsgenerator erzeugt werden. Leider ist das Rucksack-Kryptosystem nicht sicher. Shamir zeigte 1979, dass Rucksäcke unter gewissen Umständen geknackt werden können, was jedoch noch keine allgemeine Kryptoanalyse zuließ. 1983 dann zeigten Shamir und Zippel Schwachpunkte in der Transformation auf, welche die Rekonstruktion des Rucksacks mit der Superincreasing-Eigenschaft aus dem normalen Rucksack ermöglichte. Es gibt eine ganze Reihe von Rucksack-Varianten, die jedoch fast ausnahmslos kryptoanalysiert wurden (es besteht wenig Hoffnung für die wenigen Ausnahmen, dass sie weitere Kryptoanalysen bestehen). Benutzen Sie keines dieser Verfahren.
Kurz nach der Veröffentlichung des Rucksack-Algorithmus erschien der von Ron Rivest, Adi Shamir und Leonard Adleman entworfene und nach ihren Namen benannte RSA-Algorithmus. RSA ist wohl das populärste aller Public-Key-Verfahren und hat schon einige Jahre intensiver Kryptoanalyse überstanden. Dadurch konnte man die Sicherheit des Algorithmus bisher zwar weder beweisen noch widerlegen, trotzdem bestärkt dies das Vertrauen in das Verfahren. Ich möchte Ihnen diesen Algorithmus im folgenden Kapitel etwas näher bringen, aber aufgepasst: Es wird mathematisch. Wenn Sie das nicht die Bohne interessiert, "blättern" Sie doch einfach weiter.
 Zurück |
nach oben |
 |
 Übersicht |
Weiter  |
Letzte Änderung: 25.03.2002
© 2002 by Christian Thöing