Public-Key Kryptographie
- Public-Key Verschlüsselung - Hybride Kryptosysteme - Sicherheit von Public-Key Verfahren - Der RSA-Algorithmus
Public-Key Verschlüsselung
Selbst mit dem besten und schnellsten Krypto-Algorithmus bleibt das Problem der Schlüsselübertragung vom Sender zum Empfänger bestehen. Es muss erst ein "sicherer" Kanal zur Übertragung des Schlüssels gefunden werden, was in der Praxis nahezu unmöglich ist. Daher ist auch die One Time Pad (kurz OTP) Variante der Vigenère ähnlichen Verfahren, zwar eine prinzipiell unknackbare Methode, aber so gut wie nie praktikabel, da der Schlüssel erst sicher übertragen werden muss. Genau hier greifen die Public-Key Algorithmen und bieten eine praktikable Lösung für dieses Problem: Sender und Empfänger besitzen nicht den selben Schlüssel (wie bei den symmetrischen Verschlüsselungsverfahren), sondern ein Schlüssel ist öffentlich und der zweite nur dem Besitzer bekannt. Public-Key Verfahren werden daher auch als asymmetrische Verfahren bezeichnet. Die Schlüssel treten also paarweise auf, der eine wird als Chiffrier- schlüssel der andere als Dechiffrierschlüssel bezeichnet. Das entscheidende ist nun, dass es nicht möglich ist aus Chiffrier- oder Deschiffrierschlüssel den jeweils anderen Schlüssel zu bestimmen. Mathematisch wird dies durch sog. Einwegfunktion mit Hintertür realisiert, dabei ist die Verschlüsselung die mathematisch 'einfache' Richtung, die mit Hilfe des öffentlichen Schlüssels, dem Chiffrier- schlüssel, durchgeführt wird. Jeder kann mit diesem Schlüssel beliebige Nachrichten verschlüsseln. Die Entschlüsselung jedoch ist die mathematisch 'schwierige' Richtung. Diese Richtung muss so 'schwer' sein, dass sie nur mit der Hilfe des privaten Schlüssels, dem Deschiffierschlüssel, möglich ist, nicht aber durch Computer in einem bestimmten (möglichst großen) Zeitraum. Prinzipiell ist jedoch auch der 'schwierige' Weg mathematisch berechenbar, jedoch muss der Aufwand größer sein als ein Brute Force Angriff. Eine Übertragung einer Nachricht sieht dann folgendermaßen aus: 1. Typ1 sendet Typ2 seinen öffentlichen Schlüssel. 2. Typ2 chiffriert die Nachricht für Typ1 mit dem öffentlichen Schlüssel von Typ1 und sendet die chiffrierte Nachricht an Typ1. 3. Typ1 dechiffriert die Nachricht mit seinem privaten Schlüssel. ...und es muss nichts "geheim" übertagen werden, das Problem der symmetrischen Verfahren tritt nicht auf.
Hybride Kryptosysteme
Ein Nachteil dieses Verfahrens ist, dass es langsam ist. Dagegen sind symmetrische Algorithmen in aller Regel etwa 1000 mal schneller, so auch DES[Hardware] im Vergleich zu RSA[Hardware] (DES[Software] ist 'nur' etwa 100 mal schneller als RSA[Hardware]). Ein weiterer Nachteil ist die möglichkeit eines Chosen-Plaintext Angriff, daher wird in der Praxis meist eine Variante des einfachen Public-Key- Verfahrens eingesetzt: Es wird hier nicht direkt mit dem öffentliche Schlüssel chiffriert, sondern mit einem Sitzungsschlüssel, der mit Hilfe eines symmetrischen (daher schnellen) Algorithmus erzeugt wurde. Mit dem werden dann die Nachrichten verschlüsselt und der Sitzungsschlüssel wird mit dem öffentlichen Schlüssel des Empfängers chiffriert übertragen. Eine Übertragung des Sitzungsschlüssel sieht dann folgendermaßen aus: 1. Typ1 sendet Typ2 seinen öffentlichen Schlüssel. 2. Typ2 generiert einen zufälligen Sitzungsschlüssel, chiffriert ihn mit dem öffentlischen Schlüssel von Typ1 und schickt ihn so an Typ1. 3. Typ1 dechiffriert Typ2 Nachricht mit seinem privaten Schlüssel und erhält den Sitzungsschlüssel. 4. Nun können weitere Nachrichten mit gleichem Sitzungsschlüssel chiffriert werden.
Sicherheit von Public-Key Verfahren
Der RSA-Algorithmus
RSA ist das mit Abstand populärste Public-Key-Verfahren, es wurde 1978 von seinen Erfindern Ron Rivest, Adi Shamir und Leonard Adlerman erfunden und nach ihnen benannt [Abstract RSA78]. Es ist ein relativ einfacher Algorithmus und war bis September 2000 patentiert. Jetzt ist er ohne Lizenzgebühren frei verwendbar. Der Algorithmus besteht aus zwei Teilen: Der eigentlichen Verschlüsselung und der wichtigen Schlüsselerzeugung. Die Schlüsselerzeugung 1. Wähle zufällig zwei große Primzahlen p und q mit einer Länge zwischen 384 und 512 Bit. 2. Berechne n = pq (n hat dann eine Länge von 512 bis 1024 Bit) 3. Wähle eine kleine ungerade natürliche Zahl e, die zu phi(n) = (p - 1)(q - 1) relativ prim ist, d.h es gilt ggT(e, phi(n)) = 1. 4. Berechne d als Lösung der Gleichung ed = 1 mod phi(n). d existiert und ist eindeutig bestimmt, man schaue in ein Mathematikbuch für den Beweis. d kann mit Hilfe des erweiterten Euklidischen Algorithmus berechnet werden. d und n sind ebenfalls relativ prim zueinander. 5. Das Paar P = (e, n) ist der öffentliche Schlüssel. 6. Das Paar S = (d, n) ist der private Schlüssel. Hinweis: p und q werden nicht mehr benötigt, dürfen allerdings auch nicht bekannt gegeben werden! Die Verschlüsselung Man zerlege die Nachricht M in Blöcke, die kleiner als n sind (bei binären Daten wird die größe Zweierpotenz, die kleiner als n ist gewählt. Die Verschlüsselung sieht dann so aus: E(M) = M^e mod n Die Enschlüsselung eines Chiffretext C: D(C)) = C^d mod n dies ist möglich da: C^d = (M^e)^d = M^(ed) = M^(k(p-1)(q-1) + 1) = MM^(k(p-1)(q-1)) = M * 1 = M; alles mod n Das bedeutet E und D sind invers zueinander! Sicherheit speziell von RSA Man sieht daher, dass RSA auf der mathematischen Schwierigkeit beruht, große Zahlen in ihre Primfaktoren zu zerlegen. Bemerkenswert ist, dass die Primfaktor- zerlegung gleichzeitig der bisher effizienteste Angriff auf RSA ist. Es wurde allerdings immer noch nicht Bewiesen, dass die Sicherheit von RSA auf dem Problem der Primfaktorzerlegung beruht, es ist daher theorisch möglich, dass es einen einfacheren Angriff gibt C ohne d aus e und n M zu berechnen. Wie schon gesagt ist es natürlich sehr wichtig, dass p und q unbekannt bleiben und nicht zu erraten sind. p und q müssen daher möglichst zufällig aus einer möglichst großen Menge von Primzahlen gewählt werden. Hier ein Beweis der zeigt, dass offenbar die Primfaktorzerlegung nicht der effizienteste Angriff auf RSA ist: <news:slrnat4eo7.p0.lutz%40taranis.iks-jena.de>, daher basiert RSA auf der 'praktischen Unmöglichkeit der diskreten Logarithmen in endlichen zusammengesetzen Ringen'. Lutz Donnerhacke in: <news:slrnasvrlj.pd.lutz@taranis.iks-jena.de>