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 den folgenden Seiten liefern sie Plädoyers für den Herausforderer ECC (dieser Artikel) bzw. das altbewährte RSA.

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

Elliptische Kurven - schlank und stark

Von Uwe Krieger, Essen

Neue Kryptoalgorithmen bahnen sich ihren Weg: Bei den symmetrischen Verfahren ist mit dem AES ein Nachfolger für DES in Sicht, im Public-Key-Bereich macht sich Elliptic Curve Cryptography (ECC) daran, den RSA als Standardalgorithmus abzulösen.

Im Bereich der symmetrischen Chiffren ist der bekannteste Vertreter der bei IBM entwickelte und Mitte der siebziger Jahre standardisierte DES (Data Encryption Standard). Auch wenn dieser vom Design her immer noch als wegweisend gilt, wird er inzwischen aufgrund seiner zu geringen Schlüssellänge von 56 Bit nicht mehr als sicher angesehen. Schon vor einiger Zeit hat deswegen das externer Link National Institute of Standards and Technology (NIST) in den Vereinigten Staaten die Suche nach einem Nachfolger angestoßen. Die Eckdaten für diesen, unter dem Stichwort AES (Advanced Encryption Standard) geführten Algorithmus setzen neue Maßstäbe für die Sicherheit kryptographischer Verfahren. Anforderungen an Kandidaten für den kommenden Standard sind unter anderem, mit Schlüsseln von 128, 192 und 256 Bit Länge zu arbeiten.

Im Praxiseinsatz sind bisher meist hybride Methoden zu finden, bei denen ein asymmetrischer Mechanismus für den Schlüsselaustausch bzw. die Schlüsselübermittlung verantwortlich ist und nur für die eigentliche Verschlüsselung eine schnelle, symmetrische Chiffre verwendet wird. Eine Kette ist jedoch immer nur so stark wie ihr schwächstes Glied. In einer hybriden Umgebung heißt das, dass die asymmetrischen Algorithmen, wollen sie eine adäquate Sicher heit bieten, den neuen Anforderungen gleichziehen müssen.

Rechnet man die bekannten Angriffsmethoden auf die für Schlüsselübermittlung verwendeten asymmetrischen Verfahren hoch, so kommt man zu nachdenklich stimmenden Ergebnissen: Heute übliche RSA-Schlüssel müssten auf einmal mit 4.096Bit bis weit über 10.000Bit Schlüssellänge kalkuliert werden, um die gleiche Sicherheit wie ein symmetrisches Verfahren mit Schlüssellängen von 128 bis 256 Bit zu erreichen. Diese Zahlen scheinen utopisch - zur Beruhigung kann man nur sagen, dass es im Moment noch keine Veranlassung gibt, einen symmetrischen 256Bit Schlüssel zu wählen. Die Größe der Parameter für das notwendige asymmetrische Verfahren würde dann jedoch in nicht mehr praktikable Bereiche vorstoßen, die Rechenzeit der notwendigen arithmetischen Operationen wäre selbst auf modernen PC-Prozessoren deutlich spürbar - und für den Einsatz in Authentifizierungssystemen nicht mehr tragbar.

Eine Idee: ECC

Neue Wege sollen die träge asymmetrische Kryptographie jedoch beschleunigen. Die bekannteste und attraktivste Methode ist die Verschlüsselung auf der Basis elliptischer Kurven (Elliptic Curve Cryptography, ECC). Es ist eine Klasse hochkomplexer Verfahren, mit deren praktischer Umsetzung die cv cryptovision GmbH befasst ist. Die besonderen Merkmale des Verfahrens liegen in drastisch reduzierten Schlüssellängen, deutlich schnelleren Rechenzeiten und einem vereinfachten Key-Management.

Wirft man einen Blick auf die Standardisierungsbemühungen der letzten Jahre, zeigt sich, dass es sich bei ECC um keine Nischenlösung handelt: In allen Dokumenten (z.B. von ANSI, IEEE oder ISO), die sich mit Public-Key-Verfahren auseinandersetzen, bilden die ECC-Algorithmen ein wesentliches Standbein. Speziell in Deutschland, das 1997 mit dem Signaturgesetz einen Meilenstein zur Verwendung digitaler Signaturen gesetzt hat, kann man zusätzlich auf den zugrunde liegenden Maßnahmenkatalog verweisen. Die Betonung des Gesetzes liegt eindeutig auf dieser Klasse von Verfahren.

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

Mathematische Grundlagen der ECC

Grundlage für den Einsatz von ECC ist das Problem des Diskreten Logarithmus (das DL-Problem). In seiner ursprünglichen Form beruht es auf der Beobachtung, dass bei gegebenem g und x für die Berechnung von y= gx stets ein effizienter Algorithmus vorhanden ist. Die Umkehrung jedoch, d.h. die Berechnung von x für bekanntes y und g ist ungleich schwieriger. ECC-Algorithmen nutzen aus, dass man diesen Umstand auch in anderen Strukturen formulieren kann.

Beispielsweise kann man definieren, was die Summe zweier verschiedener Punkte auf einer elliptischen Kurve sein soll (s.Grafik): Geometrisch veranschaulicht zieht man zur Addition zweier Werte P und Q die Verbindungsgerade durch diese Punkte. Der entstehende Schnittpunkt dieser Geraden mit der Kurve muss dann lediglich noch einmal an der Achse gespiegelt werden, um das Ergebnis R= P + Q zu erhalten. Damit läßt sich auch sinnvoll erklären, was für eine Zahl n der Ausdruck n · P bedeuten soll, nämlich P + P + ... + P + P, also die entsprechend häufige Ausführung einer Addition.

grafische Darstellung der Addition zweier Punkte auf einer elliptischen Kurve

Aus historischen Gründen nennt sich dieses Gruppengesetz auf elliptischen Kurven Addition, ansonsten erhält man aber eine zur Exponentiation vergleichbare Situation: Was beim originalen DL-Problem die Grundlage ist, nämlich die Berechnung der Potenz y = gx, ist in diesem Falle die Berechnung des Vielfachen Y = x · G für einen beliebigen Punkt G auf der Kurve und eine geheim zu haltende Zahl x (zur besseren Unterscheidung wurden hierbei Großbuchstaben für die Bezeichnung von Punkten auf der Kurve und kleine Buchstaben für normale Zahlenwerte verwendet).

Es stehen dabei im Falle von ECC für die Berechnung von Y im Wesentlichen wieder dieselben effizienten Algorithmen zur Verfügung. Für die Berechnung von x mit Kenntnis von Y und G sind allerdings einige aus anderen Strukturen bekannte Verfahren nicht mehr verfügbar. Damit wird das Problem für einen Angreifer schwieriger, und die Parameter können entsprechend kürzer gewählt werden.

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

Diskreter Logarithmus

Wie alle anderen Ansätze zur Konstruktion von Public-Key-Algorithmen basiert auch ECC auf einem allgemein als besonders komplex angesehenen, mathematischen Problem. Während beim RSA-Algorithmus die Faktorisierung (also das Zerlegen einer Zahl in ihre Primfaktoren) die Grundlage der Verschlüsselung ist, begründet sich bei den Algorithmen auf Basis elliptischer Kurven die Sicherheit auf dem so genannten Problem des diskreten Logarithmus (DL-Problem). Es basiert darauf, dass in bestimmten Strukturen die Umkehrung der Exponentiation ab gewissen Größenordnungen der Parameter nicht mehr praktikabel ist. Die mögliche Verwendung dieses Problems innerhalb der Kryptographie ist seit langem bekannt und kann sogar als Ursprung der Public-Key-Verfahren bezeichnet werden: Genau auf dieser Feststellung beruht nämlich der erste veröffentlichte Public-Key-Algorithmus, das 1976 durch Whitfield Diffie und Martin Hellman vorgeschlagene und nach ihnen benannte Verfahren.

Punktegruppe

1985 kamen die zwei Mathematiker Neal Koblitz und V.S. Miller unabhängig voneinander zu der Erkenntnis, dass sich eine schon lange in der Mathematik bekannte und intensiv erforschte Struktur auch kryptographisch nutzen lässt. In der Punktegruppe elliptischer Kurven lässt sich ein Gruppengesetz formulieren, in das sich einerseits alle für das DL-Problem existierenden Protokolle problemlos übertragen lassen, andererseits aber die einem Angreifer üblicherweise zur Verfügung stehenden Möglichkeiten zur Attacke nicht funktionieren. Dies ist sicher auch einer der Gründe, warum die Verschlüsselung der gesamten digitalen Kommunikation des externer Link Informationsverbunds Berlin-Bonn (IVBB) auf diesen Verfahren beruht.

Ein alternativer Algorithmus zu etablierten Verfahren muss heute deutliche Vorteile nachweisen, um bestehen zu können. Noch ist der Stellenwert der Kryptographie der Allgemeinheit unklar, oft besteht Erklärungsbedarf für die Verwendung von asymmetrischen Chiffren. Danach erst zählen stichhaltige Argumente für einen bestimmten Algorithmus.

Diese sind im Falle ECC vorhanden: Der Algorithmus hat, im Vergleich zu RSA, Vorzüge sowohl in Bezug auf Speicherverbrauch als auch bei den Rechenzeiten. Schlüssellängen von 160Bit im Falle von ECC entsprechen der Sicherheit eines bis vor kurzem noch als Standard verwendeten 1024Bit langen RSA-Schlüssels. Für größere Schlüssellängen nehmen die Vorteile von ECC gegenüber RSA noch deutlich zu. Wo man beim RSA über eine Verdoppelung der Schlüssellängen reden muss, reichen bei ECC schon wenige Bit, um eine entsprechend höhere Sicherheit zu erzielen. Grund dafür ist, dass beim RSA-Verfahren zum Angriff auf das zugrunde liegende Problem (die Faktorisierung) bestimmte Methoden zur Verfügung stehen, die dem Angreifer im Falle von ECC fehlen (für Informationen über die Vergleichbarkeit der jeweiligen Parameterlängen siehe [1] und die bereits erwähnten Standards).

Noch vor nicht allzu langer Zeit galten RSA-Schlüssel von 512Bit Länge als sicher. Heute weiß man: Ein Schlüssel dieser Länge ist nicht nur theoretisch angreifbar, die entsprechenden Attacken haben auch in der Praxis schon zum Erfolg geführt. Erst nach diesem Beweis waren die zuständigen Gremien bereit, die Forderungen nach deutlich längeren Schlüsseln zu erfüllen.

Inzwischen zeigen solche Warnungen deswegen auch deutlich früher Wirkung. Jüngstes Beispiel ist der neueste Entwurf des BSI für die im Rahmen des Signaturgesetzes zugelassenen Kryptoalgorithmen [2]). Mit diesem Dokument erhalten RSA-Schlüssel von 1024Bit Länge ihr endgültiges Verfallsdatum: Sie sind als Übergangslösung nur noch bis zum Jahre 2004 verwendbar, als Mindestlänge werden ansonsten 2048Bit festgeschrieben. Zum Vergleich: Für ECC-Algorithmen fordert das gleiche Dokument eine neue Mindestlänge von 192Bit (statt 160Bit).

Smartcards

Speziell bei der Implementierung auf Smartcards kommen die Unterschiede der verschiedenen Schlüssellängen voll zur Geltung. In Smartcards sind größtenteils Prozessoren im Einsatz, die mit 1024Bit RSA-Schlüsseln an der Grenze ihrer Kapazität arbeiten.

Aber selbst im derzeitigen Einsatz sind die Unterschiede gravierend: Ein gängiger Smartcardprozessor benötigt für die Erstellung einer Signatur mit RSA mindestens 500-700ms, die ECC-Implementierung ist nach gerade 100ms am Ziel. Solche Unterschiede werden in Zukunft bei Massenanwendungen, zum Beispiel im Falle von E-Commerce-Applikationen, deutlich spürbar sein.

Auch auf Smartcards ist die Effizienz der Algorithmen nicht das Einzige, worauf man Wert legen sollte. Ein wichtiges Argument ist ebenfalls die sichere Erzeugung kryptographischer Schlüssel. Im Falle von RSA ist für die Erzeugung des Schlüsselpaares ein zeitaufwändiger Primzahltest notwendig, die Durchführung benötigt selbst auf einer schnellen Karte mehrere Minuten. In der Praxis wird deshalb der Schlüssel normalerweise außerhalb der Karte erzeugt und anschließend darauf übertragen. Solange sich der Schlüssel jedoch außerhalb der Karte befindet, ist seine Sicherheit nicht gewährleistet; in diesem Zeitraum lässt er sich verändern oder kopieren.

Schlüsselkapselung

Bei ECC hingegen ist die Situation anders: Hier sind diese geheimen Informationen zu keinem Zeitpunkt außerhalb der Karte sichtbar. Der Grund ist, dass als geheimer Schlüssel eine beliebige Zufallszahl mit der zugrunde liegenden Bitlänge geeignet ist, deren Erzeugung direkt auf der Karte kein Problem darstellt. Die anschließende Berechnung des zugehörigen öffentli chen Schlüssels ist sogar schneller als die Erstellung einer Signatur und damit ebenfalls unproblematisch.

Neben Implementierungen für spezielle Applikationen sind diese Algorithmen demnächst auch für den Massenmarkt verfügbar. Die Firma externer Link Orga bietet für ihre Smartcards inzwischen ECC-Funktionalität mit der neuesten Version ihres Betriebssystems MICARDO an.

Aber auch in neuen Einsatzumgebungen ist das Verfahren denkbar: Anwendungen auf PDAs (Personal Digital Assistants) oder im Mobile-(M-)Commerce sind aufgrund der beschränkten Rechenleistung der Endgeräte besonders auf effiziente Algorithmen angewiesen. Einige namhafte Hersteller entwickeln bereits Anwendungen in dieser Richtung. Beispielgebend sei das E-Sign-Konsortium genannt, in dem hochrangige Anbieter von M-Commerce-Infrastrukturen auf einen einheitlichen Standard für die Signatur von "M-Geschäften" (Bezahlen mit dem Handy) hinarbeiten.

Anwender fragen sich natürlich, mit welchem Aufwand die Verwendung solch einer neuen Technologie verbunden ist. Speziell im Bereich der Kryptographie reduziert sich dies oft auf die Frage, welche unterstützenden Toolkits zur Verfügung stehen. Es ist hier nämlich meist nicht sinnvoll, alle notwendigen Mechanismen selbst zu implemen-tieren. Vielfach ist es besser, auf bewährte Lösungen zurückzugreifen. Zu groß ist ansonsten das Risiko, dass durch eine kleine Unachtsamkeit bei der Implementierung die Sicherheitskette zusammenbricht.

Lösungslieferanten

Aber auch hier zeigt sich, dass die ECC-Algorithmen keine Nischenlösung mehr darstellen: Von verschiedenen Anbietern existieren sowohl komplette Anwendungen auf Basis dieser Verfahren, als auch Bibliotheken, die es einem Entwickler ermöglichen, diese Sicherheitsmechanismen selbst in sein Produkt zu integrieren. Firmen wie die cv cryptovision GmbH engagieren sich speziell im Bereich der geschilderten Verfahren und liefern Lösungen für die verschiedensten Plattformen von Smartcards bis hin zu Großrechnersystemen. Produkte wie die cv act library stellen die verschiedensten Kryptoalgorithmen (symmetrische wie asymmetrische, aber z.B. auch alle gängigen Hashfunktionen) dem Entwickler über ein einfach zu bedienendes Interface zur Verfügung.

Uwe Krieger ist bei der externer Link cv cryptovision GmbH zuständig für den Bereich Kryptoalgorithmen.

Literatur

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