Management und Wissen

Kryptoalgorithmen

----------Anfang Textkasten----------

Public-Key - Wer macht das Rennen?

RSA vs. ECC

Welche Algorithmen und mathematischen Prinzipien werden in Zukunft die Public-Key-Kryptographie dominieren? Ist der RSA-Algorithmus noch zeitgemäß oder erfordern Fortschritte in der Computertechnik und neue Anwendungsgebiete andere Verfahren für die Verschlüsselung und digitale Signatur? Die Redaktion hat zwei Experten gebeten, aus ihrer Sicht Vor- und Nachteile der Kontrahenten zu schildern. Auf diesen und den vorigen Seiten liefern sie Plädoyers für den Herausforderer ECC bzw. das altbewährte RSA (dieser Artikel).

----------Ende Textkasten----------

Der RSA-Algorithmus - bewährte Qualität

Von Norbert Olbrich, Offenbach

Sichere Kommunikation durch Krypto-Algorithmen? Na klar. Doch auf welches Pferd soll man setzen? Neben erwiesener Sicherheit und hoher Performance müssen auch Offenheit für künftige Veränderungen sowie Interoperabilität mit bestehenden Lösungen gewährleistet sein.

Selbst für den Mathematiker stellt sich bei der Auswahl eines Kryptoalgorithmus die Frage, für welche Verschlüsselungstechnologie er sich heute entscheiden kann, ohne morgen auf flexible Reaktionsmöglichkeiten zu verzichten. Der Markt bringt zwangsläufig Veränderungen mit sich, und ebenso müssen sicherheitsrelevante Erkenntnisse berücksichtigt werden.

Zur Auswahl stehen verschiedene grundlegende Verfahren wie symmetrische und asymmetrische Verschlüsselung und digitale Signaturen - die nächsten Fragen gelten dem konkreten Algorithmus bzw. dem zugrunde liegenden mathematischen Problem (diskreter Logarithmus oder Faktorisierung), aber auch dem technischen Umfeld: Einbettung in Public Key Infrastrukturen, Nutzung von Krypto-SmartCards oder Handheld Devices (z.B. Palmtops oder Handys) mit begrenzter Rechenleistung usw.

Zu den weltweit bekanntesten Verschlüsselungsalgorithmen gehört seit 1978 der RSA-Algorithmus, benannt nach seinen drei Entwicklern Rivest, Shamir und Adleman. Er ist der erste vollständige PKI-Algorithmus, der sowohl eine asymmetrische Verschlüsselung als auch eine digitale Signatur erlaubt. "RSA" steht häufig allein als Synonym für dieses asymmetrische Verschlüsselungsverfahren, allerdings auch für die Firma RSA Security.

Fakten, Fakten, Fakten

Auch heute muss der RSA-Algorithmus den Vergleich mit Herausforderern wie der Elliptic Curve Cryptography (ECC) keineswegs scheuen. Natürlich gilt es dabei je nach den Anforderungen der Kunden abzuwägen - eine absolute Aussage ist kaum möglich. Einige Schlaglichter:

Durchschaubare Technik: Der RSA- Algorithmus ist ausgereifter, da das Faktorierungsproblem ("Integere Faktorisierung") verständlicher ist als das der ECC zu Grunde liegende mathematische Problem (Elliptic Curve Discrete Logarithms). Dies führt zu einem höheren Grundvertrauen in die Sicherheit des RSA-Algorithmus. In jüngster Zeit ist allerdings auch eine gestiegene Marktakzeptanz von ECC zu beobachten.

Schlüssellängen: ECC ist kompakter in Bezug auf die Schlüsselgröße, verschlüsselten Daten und auch Signaturen. Jedoch ist das nur von Bedeutung, wenn die Menge der kryptographischen Daten die Hauptbelastung eines Systems ausmacht. Wenn beispielsweise Zertifikate an sich durch Protokolldaten bereits sehr groß sind, hilft eine Reduzierung der Schlüsselgröße relativ wenig, insbesondere bei Krypto-SmartCards wo der Hauptzweck darin besteht, Schlüssel zu erzeugen, zu speichern und zur Verfügung zu stellen.

Je nach Verfahren sind heute Schlüssellängen von 128, 192, 1024, 2048 Bit oder auch höhere Werte als sicher anzusehen. Ein Vergleich der absoluten Schlüssellängen ist dabei nicht möglich, da die Vergrößerung des Schlüssels in verschiedenen Verfahren verschiedene Steigerungen der Sicherheit bewirkt. Mathematisch gesehen könnte man mit beliebig hohen Werten arbeiten. Ab einem gewissen Punkt bedeutet eine Steigerung der Schlüssellänge aber angesichts der Leistungsgrenzen verfügbarer Computersysteme keine weitere Steigerung der praktischen Sicherheit. Eine Grenze wird letztendlich aber nur durch die Prozessorleistung gesetzt, was vor allem beim Einsatz in mobilen Geräten entscheidend sein kann.

Geschwindigkeit: In ECC sind Private-Key-Operationen (Signatur/Entschlüsselung) generell schneller als bei RSA. Der Geschwindigkeitsvorteil kommt jedoch nur zum Tragen, wenn die Kosten für neu anzuschaffende Kryptographie zu vernachlässigen oder die Zeitvorteile für den Anwender deutlich sichtbar sind.

Die RSA Private-Key-Operationen können zudem durch die neue Multi-Prime-Technologie (s.u.) wesentlich beschleunigt werden: um den Faktor zwei oder mehr in Abhängigkeit von der Anzahl der Primzahlen und dem Implementierungs-Aufkommen. Die Sicherheit von Multi-Prime basiert dabei weiterhin auf der integeren Faktorisierung und profitiert vom jahrezehntelangen Studium dieses Problems.

Multi-Prime

Diese Erweiterung des RSA-Algorithmus bietet RSA Security in Kooperation mit der Compaq Computer Corporation besonders Herstellern von Wireless-Produkten an, um die nötige Sicherheit mit gleichzeitiger High-Speed-Performance in tragbaren Geräten wie Mobiltelefonen oder Pocket-PCs implementieren zu können.

RSA nutzt traditionell zwei Primzahlen, um einen langen Schlüssel zu formen. Das MultiPrime-Verfahren, das von Compaq entwickelt und patentiert wurde, arbeitet hingegen mit drei oder mehr Primzahlen und nutzt außerdem den chinesischen Restsatz sowie möglicherweise Parallelverarbeitung , um mehr Leistung mit Hilfe von "kleineren" mathematischen Operationen zu erreichen. Dabei bleibt das Verfahren aber weitestgehend kompatibel zu bestehenden RSA-Infrastrukturen.

Die RSA Public-Key-Operationen (Signaturprüfung/Verschlüsselung) sind geschwindigkeitsmäßig ohnehin mit ECC vergleichbar. In vielen Protokollen und Anwendungen laufen auf der Client-Seite vorrangig Public-Key-Operationen. Somit verhalten sich weniger leistungsfähige Clients (wie z.B. Handhelds) bei beiden Technologien identisch.

Bis zu 100-mal schneller ist allerdings die ECC-Schlüsselgenerierung im Vergleich zur Berechnung von RSA-Schlüsseln, was vorteilhaft ist, wenn für jede Transaktion neue Schlüssel generiert werden müssen, aber kaum zum Tragen kommt, wenn nur sehr selten ein neues Signaturschlüsselpaar benötigt wird. Die Erzeugung der ECC Domain Parameter (z.B. Elliptische Kurven) ist wiederum langsamer als die RSA-Schlüsselerzeugung, jedoch wird sie nur einmal für jede Gemeinschaft von Anwendern (Domain) benötigt.

Interoperabilität: Bei RSA-Implementierungen ist es einfacher, Interoperabilität zu gewährleisten, da sie weniger komplex sind als ECC.

RSA hat zudem einen entscheidenden Vorsprung, was die Verbreitung angeht - gerade für Internetanwendungen eine Grundvoraussetzung, aber ebenso angesichts der Verfügbarkeit spezieller Krypto-Hardware und des Know-hows in Firmen von Bedeutung.

Auch in der "drahtlosen Infrastruktur" ist der RSA-Algorithmus derzeit beherrschend: RSA und ECC werden zwar beide unterstützt, der Druck der Interoperabilität zu bestehenden Systemen (z.B. beim Einsatz in Certificate Authorities, Servern, Browsern usw.) verstärkt jedoch das Interesse am RSA-Algorithmus, etwa beim Einsatz von SSL auf "Handheld Devices", die mit jeder Generation mehr Performance bieten.

Ein Umschwenken auf ECC in dieser Umgebung zöge massive und durchgreifende Veränderungen nach sich. Beim Einsatz von Multi-Prime-RSA zur Geschwindigkeitssteigerung werden lediglich lokale Veränderungen für den Anwender des mit Multi-Prime erzeugten privaten Schlüssels benötigt. Diese Veränderung ist an keiner anderen Stelle sichtbar.

Darüber hinaus ist ECC spürbar patentbelastet: Nicht patentierte Varianten sind hier die Ausnahme, während das klassische RSA - abgesehen von MultiPrime - lediglich einem einzigen US-Patent unterliegt, das zudem im September 2000 ausläuft.

RSA vs. RSA

Versteht man unter RSA statt des Algorithmus die Firma RSA Security, schließen sich RSA und ECC zudem nicht aus: RSA Security liefert beispielsweise Entwicklern mit dem BSAFE Toolkit verschiedene Verschlüsselungstechnologien für die Integration in deren Software. Darunter fallen Zufallszahlengeneratoren, PKCS-Interfaces, Memory-Kontrollfunktionen und offene APIs genauso wie symmetrische Kryptographie, der RSA-Algorithmus und Elliptic Curve Cryptosystems (ECC).

Auch RSA Security's eigene "schlüsselfertige" Anwendungen zur Authentifizierung (RSA SecurID) und Public Key Infrastruktur (RSA Keon) basieren auf BSAFE. RSA Security sieht es als Firmenphilosophie an, lediglich als Technologielieferant die verschiedenen kryptographischen Verfahren in einem Paket zur Verfügung zu stellen. Der Kunde soll entscheiden, welche Technologie für ihn am besten ist, um seine spezielle Aufgabenstellung zu lösen.

Dabei kommen übrigens nicht nur US-Entwicklungen und US-Forscher zu Wort: RSA Security betreibt eigene Krypto-Laboratorien außer in den USA auch in Schweden und Australien, um den unterschiedlichen lokalen Anforderungen, die aus den verschiedenen Regionen kommen, gerecht werden zu können.

Norbert Olbrich ist Pre-Sales-Manager Deutschland/Österreich/Schweiz bei der externer Link RSA Security GmbH.

© SecuMedia-Verlags-GmbH, D-55205 Ingelheim,
KES 4/2000, Seite 30