[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.

Idealerweise werden die öffentlichen Schlüssel in einem öffentlichen Adressenverzeichnis (»Directory«) zur allgemeinen Verfügung gestellt. [Siehe auch Zertifikate]

Das RSA-Verfahren

Die Sicherheit des RSA

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 x^e 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

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.