2a. Kryptographische Basistechniken
2a.3 Asymmetrische Verschlüsselung
[Public Key Cryptography, PKC]
Die Idee der asymmetrischen Verschlüsselung
E und D sind zueinander inverse mathematische Verfahren,
so dass D aus E nicht bestimmbar ist.
Analogie/bildliche Vorstellung: Schnappschlossverfahren
- Zum »Einschließen« (Ausführen von E) braucht man nur die
Information, wem die Kiste gehört
(öffentliches Verfahren, repräsentiert durch öffentlichen
Schlüssel).
- Zum »Aufschließen« (Ausführen von D) braucht man den Schlüssel,
und den hat nur der Besitzer (privater, geheimer Schlüssel).
Erfinder:
Whitfield
Diffie und
Martin
Hellman 1976:
New
directions in Cryptography.
Beim britischen Geheimdienst ca. 1970, bei der NSA möglicherweise
schon in den 60er-Jahren.
Eigenschaften
- Jede Teilnehmerin A (= »Alice«) hat einen öffentlichen und einen
privaten Schlüssel.
- Mit dem öffentlichen Schlüssel von A kann jeder verschlüsseln.
- Mit dem privaten Schlüssel kann nur A selbst entschlüsseln.
- Der private Schlüssel ist ein absolutes Geheimnis von A,
er kann sogar als Identitätsnachweis dienen.
Achtung: Konstruktionsbedingt ist ein Angriff mit gewähltem Klartext
(= Probeverschlüsselung) immer möglich.
Idealerweise werden die öffentlichen Schlüssel in einem öffentlichen
Adressenverzeichnis (»Directory«) zur allgemeinen Verfügung gestellt.
[Siehe auch Zertifikate]
Andere asymmetrische Verfahren
- Merkle/Hellman - basierend auf dem Tornister-Problem (»knapsack problem«);
in Spezialfäll gebrochen, z. B. von Shamir.
- ElGamal - basierend auf diskretem Logarithmus
(in endlichen Körpern).
- McEliece - basierend auf Decodier-Problem für Goppa-Codes.
- LUC (Peter Smith 1993) - ähnlich RSA, Bildung der Lucas-Folge
mod n = pq aus 2 und m.
- MNLN (Müller, Nöbauer, Lidl, Nöbauer) - wie RSA, aber
das Polynom xe durch
»Dickson-Polynom« ersetzt.
- Elliptische-Kurven-Verfahren (Miller, Koblitz)
- wie ElGamal,
aber die multiplikative Gruppe des endlichen Körpers
durch elliptische Kurve über diesem ersetzt.
(ECC = Elliptic Curve Cryptography).
- Probabilistische Chiffrierung (Blum, Goldwasser, Micali).
Asymmetrische Verschlüsselung - Vor- und Nachteile
+ | Jeder Teilnehmer hat ein persönliches
Geheimnis, das er mit niemandem teilen muss. |
+ | Keine geheime Übermittlung nötig. |
+ | Spontane Kommunikation jederzeit möglich,
ideal für offene Kommunikationssysteme. |
+ | Zahl der nötigen Schlüssel wächst linear mit
der Zahl der Teilnehmer (bei symmetrischer Verschlüsselung
quadratisch). |
+ | Grundlage vieler kryptographischer
Protokolle. |
- | Probeverschlüsselung möglich;
Verfahren muss gegen Angriff mit ausgewähltem Klartext
resistent sein. |
- | Alle bekannten Verfahren sind sehr langsam
(Faktor 10 000 verglichen mit symmetrischen). |
- | Benötigte Schlüssellänge groß
(Faktor 20 bis 40 verglichen mit symmetrischen). |
- | Schlüsselverwaltung bringt Komplikationen:
öffentliche Schlüssel müssen authentisch sein ===>
Zertifikats-Infrastruktur
nötig. (PKI = »Public Key Infrastructure«) |
Weitere Eigenschaften
- Langsame Verfahren, geeignet für kleine Datenmengen.
- Z. B. Übermittlung von (symmetrischen) »Sitzungsschlüsseln«
(---> »hybride
Verschlüsselung«).
- Software: ca 2 Kbit/sec.
- Stand der Technik: RSA oder
DH mit 2048-Bit-Schlüsseln
(Rivest/Shamir/Adleman, Diffie/Hellman).
- Alternative Verfahren: ECC (»Elliptic Curve Cryptography«)
– kürzere Schlüssel, weniger Speicherplatz, höherer Rechenaufwand.
Sicherheit der Standard-Verfahren (RSA/DH)
- Es gibt einen Angriff, der schneller ist als die vollständige Suche:
Z. B. Faktorisierung des »Moduls« bei RSA.
- Schlüssellänge n sicher, wenn man n-Bit-Zahlen nicht
in Primfaktoren zerlegen kann.
- Sicherheitsgrenze heute: 2048 Bit.
- Auf Chipkarten meist noch 1024-Bit-Schlüssel, mittelfristig zu
schwach!
- Achtung: Bei hybriden [s. 2b] Verfahren müssen beide Schlüssellängen
stimmen!
Schlüssellängen für ECC
- Keine subexponenziellen Kryptoanalysemethoden bekannt.
- Wesentlich kleinere Schlüssellängen (bis auf weiteres) sicher
[NIST: 2 x Länge für symmetrische Verfahren]:
- 160 Bit kurzfristig,
- 220 Bit mittelfristig,
- 256 Bit langfristig.
- Geeignet in ressourcen-schwachen Umgebungen,
- z. B. Chipkarten.
- Vom BSI bevorzugt.
Vorlesung Datenschutz und Datensicherheit
Autor: Klaus Pommerening, 31. März 1999;
letzte Änderung: 8. Juni 2004
E-Mail an Pommerening »AT« imbei.uni-mainz.de.