8.2.5. Asymmetrische Kryptosysteme und digitale Signaturen

Bei den bisher diskutierten symmetrischen Kryptosystemen galt im wesentlichen folgendes:

Bei den asymmetrischen Kryptosystemen verhält sich die Sache nun anders. Es werden immer zwei unterschiedliche Schlüssel verwendet: einer für die Ver- und der andere für die Entschlüsselung. Beide können nicht auseinander berechnet werden, zumindest nicht in vertretbarer Zeit und mit vertretbarem Aufwand.

Aus diesem Grunde ist es möglich und gängige Praxis, den zur Chiffrierung genutzten Schlüssel zu veröffentlichen. Daraus resultiert die Bezeichnung öffentlicher Schlüssel bzw. Public Key. Deshalb spricht man auch von Public-Key-Algorithmen oder Public-Key-Kryptographie und im Englischen analog von public key algorithms oder public key cryptography (manchmal mit PKC abgekürzt).

Der für die Dechiffrierung benötigte Schlüssel ist dagegen geheimzuhalten. Er trägt die Bezeichnung privater Schlüssel bzw. Private Key. Manchmal wird in der Literatur auch vom geheimen Schlüssel gesprochen. Dies wollen wir aber nicht tun, um Verwechslungen mit symmetrischen Verfahren auszuschließen.

Es ergibt sich folgendes Bild:

Asymmetrische Kryptosysteme ermöglichen die interessante (und im Vergleich zu symmetrischen Verfahren neuartige) Situation, daß beliebige Beteiligte Nachrichten mit einem öffentlichen Schlüssel chiffrieren können, wobei die Dechiffrierung nur dem Inhaber des zugehörigen privaten Schlüssels gelingt.

Das bedeutet, zwei (evtl. einander völlig unbekannte) Personen oder auch Rechner können ohne vorherigen sicheren Austausch eines gemeinsam genutzten geheimen Schlüssels sofort vertraulich miteinander kommunizieren. Jeder Teilnehmer benötigt lediglich den öffentlichen Schlüssel des anderen Partners, dessen Beschaffung keinen sicheren Kanal erfordert, da er eben nicht geheim ist.

Die Schlüsselverteilung stellt sich also vergleichsweise einfach dar. Allerdings gibt es auch hier ein nicht zu unterschätzendes Problem: Man muß zuverlässig feststellen können, daß ein Key tatsächlich dem vermeintlichen Eigentümer gehört. Zur Gewährleistung der Authentizität der öffentlichen Schlüssel werden, wie Sie das von PGP her kennen, Zertifikate (certificates) verwendet.

Die Public-Key-Technologie gestattet es prinzipiell, für eine Nachricht eine digitale Signatur (digital signature), mitunter auch elekronische Unterschrift genannt, zu erzeugen. Die Grundidee könnte man in Analogie zum oben dargestellten Ablauf bei der Ver- und Entschlüsselung so veranschaulichen:

Digitale Signaturen werden mit dem privaten Schlüssel generiert und mit dem öffentlichen Schlüssel verifiziert, d.h., bezogen auf die Ver- und Entschlüsselung vertauschen die beiden Keys ihre Rollen.

Derartige Unterschriften eignen sich zur Kontrolle der Integrität sowie Authentizität einer Nachricht. Anders als MACs können sie jedoch von jedem geprüft werden, da man nicht den zum Signieren verwendeten Key benötigt. Außerdem läßt sich eindeutig feststellen, wer der Urheber einer Nachricht ist, da nur derjenige die Signatur erstellen kann, der den privaten Schlüssel kennt. Allen anderen gelingt dies nicht. Bei MACs dagegen kennen und nutzen beide Partner denselben Schlüssel, so daß auch beide für beliebige Nachrichten korrekte kryptographische Prüfsummen errechnen können und somit als Autor in Frage kommen.

Wir hatten bereits bei der Diskussion der Einweg-Hashfunktionen darauf hingewiesen, daß man im Normalfall nicht die Nachricht selbst, sondern deren Hashwert signiert. Hauptgrund ist die dadurch erreichbare wesentlich höhere Effizienz, da man immer nur relativ kleine Datenmengen mit den im Vergleich zu symmetrischen Verfahren extrem langsamen Public-Key-Algorithmen verschlüsseln muß. Es gibt noch weitere Vorteile:

Man unterscheidet zwei Arten von Signaturverfahren:
  1. Signaturverfahren mit Anhang, bei denen die Unterschrift nur dann verifiziert werden kann, wenn die Nachricht explizit vorliegt, also dem Verifizierer bekannt ist. Es ist hierbei möglich, den Hashwert statt der Originalnachricht zu unterschreiben.

  2. Signaturverfahren mit Nachrichtenrückgewinnung, bei denen die Nachricht aus der Signatur berechnet werden kann und daher in dieser nicht explizit enthalten sein muß. Natürlich muß man hierbei immer die Originalnachricht unterschreiben, da die Hashfunktion nicht invertierbar ist.

Ob man für ein Signaturverfahren zur Verhinderung von Fälschungen eine kollisionsresistente Einweg-Hashfunktion benötigt, hängt davon ab, ob die zu signierende Nachricht von einem Angreifer vollständig bestimmt werden kann. Sofern er diese Möglichkeit hat, ist die Kollisionsresistenz der verwendeten Einweg-Hashfunktion erforderlich, da es dem Angreifer sonst relativ leicht gelingen kann, unter Ausnutzung von Kollisionen zwei unterschiedliche, inhaltlich weitgehend durch ihn bestimmte Nachrichten mit identischem Hashwert zu erzeugen. Sobald ihm sein Opfer eine dieser beiden Nachrichten unterschrieben hat, verfügt er automatisch über dessen gültige Unterschrift für die zweite Nachricht, die das Opfer nie vorher gesehen und so auch nicht signiert hat.

Falls dagegen ein Teil der Nachricht vom Signierenden bestimmt wird, reicht die 2nd-preimage resistance der Einweg-Hashfunktion aus. Dies wird im folgenden Zitat aus einem News-Artikel von Markus G. Kuhn [http://www.cl.cam.ac.uk/~mgk25/] illustriert:

Dass man fuer digitale Unterschriften Kollisionsresistenz einer Hashfunktion braucht halte ich fuer ein weit verbreitetes Missverstaendnis. Die Einwegeigenschaft sollte ausreichen wenn man gesetzlich alle Hash preimages als unterschrieben ansieht. Nur der Unterschreiber kann Kollisionen ausnutzen, also muss das nur zu seinem Nachteil ausgelegt werden und schon braucht man keine Kollisionsresistenz mehr. Man muss dann nur sicherstellen, dass man keinen Text unterschreibt den man nicht selbst erstellt hat, aber das laesst sich ja durch Hinzufuegen von ein paar Zufallsbits an den Anfang eines Textes bevor man unterschreibt vermeiden.

Historie

Die Public-Key-Kryptographie stellt ein noch recht junges Gebiet dar. Als ihre Erfinder gelten Whitfield Diffie und Martin Hellman sowie unabhängig von beiden auch Ralph Merkle.

Diffie schrieb, daß das neue Konzept im Mai 1976 als Kind zweier Probleme geboren wurde: dem Schlüsselverteilungsproblem sowie dem Signaturproblem. Die Entdeckung bestand nicht in einer Lösung, sondern in der Erkenntnis, daß beide Probleme, die auf Grund ihrer Definition unlösbar erschienen, überhaupt lösbar sind und gemeinsam gelöst werden.

Diffie und Hellman präsentierten ihr Konzept zuerst auf der Nacional Computer Conference im Jahre 1976 und publizierten einige Monate später (im November 1976) den klassischen und epochemachenden Artikel New Directions in Cryptography, der seinen Titel ganz zu Recht trägt. Merkles erste Veröffentlichung zu diesem Thema erschien, bedingt durch einen sehr zähen Publikationsprozeß, erst 1978.

Es gilt allerdings mittlerweile als ziemlich sicher, daß der NSA und ähnlichen Organisationen die der PKC zugrunde liegende Idee schon eher bekannt war. Dazu gab es aber lange Zeit wie so oft keine frei zugänglichen Publikationen, da sich das Mitteilungsbedürfnis der Geheimdienste und bestimmter staatlicher Behörden sehr stark in Grenzen hält. Einige Informationen dazu wurden von Steve Bellovin auf der Seite The Prehistory of Public Key Cryptography [http://www.research.att.com/~smb/nsam-160/] zusammengetragen.

In den dort erwähnten, im Dezember 1997 veröffentlichten Papieren der CESG (Communications-Electronics Security Group, eine britische Regierungsbehörde [http://www.cesg.gov.uk/]) schreibt der mittlerweile verstorbene CESG-Mitarbeiter James H. Ellis, daß er bereits in den 60er Jahren die Idee der Public Key Cryptography (PKC) entwickelt hatte, damals unter der Bezeichnung Non-Secret Encryption (NSE). Im Januar 1970 publizierte er im (geheimen) CESG-Report The Possibility of Secure Non-Secret Digital Encryption sein Existence Theorem, also den Nachweis, daß es NSE bzw. PKC überhaupt geben kann. Aus anderen CESG-Reports geht hervor, daß die CESG das Prinzip der bis heute breit genutzten asymmetrischen Verfahren Diffie-Hellman (1976) und RSA (1978) bereits einige Jahre vor deren Veröffentlichung in der akademischen Gemeinde kannte.

Diese Papiere der CESG stehen unter dem URL http://www.cesg.gov.uk/about/nsecret.htm öffentlich zur Verfügung.

Praxisrelevanz und Sicherheit

Seit 1976 sind zahlreiche Public-Key-Verfahren vorgeschlagen worden. Viele von ihnen haben sich als unsicher erwiesen. Von den verbleibenden, als sicher eingestuften Systemen ist ein Großteil nicht praktikabel, weil entweder der Schlüssel zu groß oder das Chiffrat wesentlich länger als der Klartext ist.

Nur sehr wenige Algorithmen sind sowohl sicher als auch in der Praxis brauchbar. Einige von ihnen können nur zur Schlüsselverteilung genutzt werden. Andere dienen der Verschlüsselung und mit einigen Erweiterungen auch zur Schlüsselverteilung. Wiederum andere gestatten nur die Erstellung digitaler Signaturen.

Nach Aussagen von Schneier gibt es lediglich 3 Systeme, die sich sowohl zur Verschlüsselung als auch für digitale Signaturen vernünftig verwenden lassen: RSA, ElGamal und Rabin. Sie sind alle relativ langsam, d.h., sie benötigen zur Ver -und Entschlüsselung von Daten viel mehr Zeit als symmetrische Kryptosysteme, so daß man sie in der Regel nicht für die Chiffrierung großer Datenmengen einsetzt bzw. einsetzen kann. Secret-Key-Verfahren sind meist mindestens 1000 Mal schneller als asymmetrische Algorithmen.

Um die Abläufe zu beschleunigen, kombiniert man in der Praxis sehr häufig symmetrische und asymmetrische Algorithmen. Das Resultat wird als hybrides Kryptosystem bezeichnet. Dabei obliegt die Verschlüsselung der Nachrichten einer symmetrischen Chiffre. Der geheime Key, meist Sitzungsschlüssel oder Session Key genannt, wird zufällig gewählt und mit Hilfe eines Public-Key-Systems chiffriert, um ihn sicher verteilen zu können. Der asymmetrische Algorithmus läßt sich zusätzlich vorteilhaft zur Authentifizierung der Partner sowie der von ihnen versendeten Sitzungsschlüssel einsetzen.

Ein weiterer Grund für die Nutzung hybrider Systeme ist die Anfälligkeit der Public-Key-Verfahren gegen Chosen-plaintext-Attacken. Wenn ein Kryptoanalytiker weiß, aus welcher Menge M der zu einem Chiffrat C gehörende Klartext P stammt, kann er P bestimmen, indem er alle Elemente von M der Reihe nach mit dem öffentlichen und ihm daher zugänglichen Schlüssel chiffriert, bis C als Ergebnis entsteht.

Damit ist natürlich nur der Klartext, nicht der Private Key gebrochen worden. Handelt es sich bei P um einen zufällig gewählten, meist nur für relativ kurze Zeit genutzten Sitzungsschlüssel, so ist die genannte Attacke nicht praktikabel, da M zu viele Elemente hat (z.B. 2128 für IDEA-Keys).

Die Sicherheit von Public-Key-Verfahren basiert allgemein auf einem schwer, d.h. selbst mit enormer Rechenleistung nur in sehr langer Zeit zu lösenden mathematischen Problem.

Wie Diffie 1988 feststellte, wurden bzw. werden vor allem die folgenden drei schweren Probleme genutzt:

  1. Rucksackproblem (knapsack problem): Hierbei handelt es sich um eine Optimierungsaufgabe. Aus einer gegebenen Menge voneinander verschiedener Zahlen ist eine Untermenge derart zu bestimmen, daß die Summe ihrer Elemente einer bestimmten vorgegebenen Zahl N entspricht. Die benötigte Rechenzeit steigt im allgemeinen zirka exponentiell mit der Anzahl der Elemente der Ausgangsmenge.

    Das Problem begegnet einem auch im täglichen Leben, z.B. beim Packen eines Rucksacks (deshalb auch der Name). Dessen Volumen ist fest vorgegeben. Man versucht nun, den Rucksack optimal zu füllen, d.h., ohne Platz zu verschenken diejenigen Gegenstände einzupacken, die in der Summe am wertvollsten (was auch immer das bedeuten mag) sind. Eine solche Aufgabe kann unterschiedlich viele Lösungen haben, natürlich auch gar keine.

  2. Berechnung des diskreten Logarithmus (discrete logarithm), auch als diskretes Logarithmusproblem bezeichnet: Gegeben seien eine Primzahl p sowie zwei natürliche Zahlen g und M, beide kleiner als p. Es ist eine nichtnegative ganze Zahl x kleiner als p zu finden, so daß
    gx mod p = M
    gilt. Der Operator mod wird modulo gesprochen. Die Modulo-Arithmetik spielt in der Kryptologie eine relativ große Rolle. Deshalb wollen hier kurz darauf eingehen. Für zwei natürliche Zahlen a und b bezeichnet
    a mod b
    den Rest, den man bei der Division von a durch b erhält. Dieser Wert ist ganzzahlig und liegt immer im Bereich von 0 bis b-1. Bsp.:
    2 mod 3 = 5 mod 3 = 29 mod 3
    Man sagt auch, die Zahlen 2, 5 und 29 sind kongruent modulo 3.

    Anmerkung für mathematisch Interessierte:

    Die für die Kryptologie relevante Berechnung des diskreten Logarithmus erfolgt immer über endlichen algebraischen Strukturen (Gruppen, Ringe, Körper). Sehr oft handelt es sich dabei um sog. Galoisfelder (benannt nach dem französischen Mathematiker Evariste Galois). Das sind endliche Körper, deren Elementeanzahl stets eine Primzahlpotenz pn (p Primzahl, n natürlich Zahl) ist. In der englischsprachigen Literatur finden wir deshalb vielfach die Begriffe Galois field, prime field bzw. etwas allgemeiner finite field.

    Galoisfelder, auch als Galois-Körper bzw. Primkörper bezeichnet, werden bei n=1 durch GF(p) und bei n>1 durch GF(pn) symbolisiert. Der in runden Klammern angegebene Ausdruck wird Charakteristik genannt.

    Zu GF(p) gehören die ganzen Zahlen von 0 bis p-1. Alle Operationen erfolgen modulo p. Addition, Subtraktion, Multiplikation und Division (außer durch Null) sind wohldefiniert. Bis auf die Null hat jede Zahl ein eindeutiges inverses Element. Dies würde nicht gelten, wenn p keine Primzahl wäre. Es gelten das Kommutativ-, Assoziativ- sowie Distributiv-Gesetz. Bei der Division gibt es keine Rundungsfehler, was für die Kryptologie sehr wichtig ist. Um die Logarithmenberechnung hinreichend schwer zu gestalten, wählt man p sehr groß.

  3. Faktorisierung (factoring): N sei ein gegebenes Produkt zweier Primzahlen. M, C, d, e, x und y seien natürliche Zahlen kleiner als N. Es ist eine der folgenden Aufgaben zu lösen:

Das erste Public-Key-Verfahren, das die Verschlüsselung von Daten gestattete, war das von Ralph Merkle und Martin Hellman entwickelte und 1978 erstmals öffentlich vorgestellte Merkle-Hellman knapsack cryptosystem, oft nur knapsack cryptosystem genannt. Es basiert darauf, daß sich aus einer einfach zu lösenden Knapsack-Aufgabe (dem sog. superincreasing knapsack), die als privater Schlüssel dient, ein schwer zu lösendes Problem konstruieren läßt, das man als öffentlichen Schlüssel nutzt. Der Private Key stellt eine Falltür (trapdoor, vgl. auch Einwegfunktionen mit Falltür) für die schwere Aufgabe dar, so daß eine Dechiffrierung mittels des Schlüssels einfach möglich ist. Daher spricht man bei diesem Schema auch vom trapdoor knapsack.

Zur Verschlüsselung von Daten kann und sollte man den Knapsack-Algorithmus mehrfach anwenden. Merkle war allerdings so von seinem System überzeugt, daß er jedem 100 Dollar anbot, der es schafft, eine einzelne Iteration des Systems zu brechen. Dies gelang Adi Shamir 1982 unter Verwendung von am Mathematischen Zentrum in Amsterdam kurz zuvor entwickelten Methoden, wofür er von Merkle die 100 Dollar kassierte.

Ähnliche Resultate wurden später auch von anderen Kryptologen publiziert. Einer von ihnen, Len Adleman, hatte sogar ein Programm für seinen Apple II geschrieben, mit dessen Hilfe er 1982 auf der Crypto Conference in Santa Barbara das Brechen einer am ersten Konferenztag allen Teilnehmern gestellten Knapsack-Aufgabe parallel zu seinem Vortrag live demonstrierte.

Merkles Vertrauen in sein Verfahren war dadurch allerdings noch nicht erschüttert worden. Er erhöhte die Prämie im November 1982 auf 1000 Dollar für jeden, dem das Brechen eines Knapsacks mit mehreren Iterationen gelingt. Zwei Jahre später mußte er dieses Geld an Ernie F. Brickell bezahlen, der auf einer Cray-1 ein Knapsack-System mit 40 Iterationen und 100 Elementen in ca. 1 Stunde gebrochen hatte.

Das 1984 vorgestellte Chor-Rivest Knapsack-Kryptosystem ist das einzige, das über viele Jahre sicher war (dafür ist der Rechenaufwand relativ hoch). Alle anderen konnten mehr oder minder schnell gebrochen werden. Daher betrachtet man heute Knapsacks nicht mehr ernsthaft als eine Basis für Public-Key-Verfahren.

Anwendungsgebiete

Typische Anwendungen der Public-Key-Kryptographie haben wir weiter oben schon gesehen. Wie die folgende Zusammenfassung zeigt, kann man vom Grundsatz her mit asymmetrischen Verfahren auch all das tun, was sich mit symmetrischen Verfahren erreichen läßt. Wegen des schon erwähnten Geschwindigkeitsnachteils beschränkt man sich aber in der Regel darauf, nur diejenigen Aufgaben mit Public-Key-Systemen zu lösen, die sich mit symmetrischen Verfahren nicht bzw. nicht gut bewerkstelligen lassen.

Ausgewählte asymmetrische Algorithmen

Zu den für die heutige Praxis relevanten asymmetrischen Verfahren gehören die folgenden:

Diffie-Hellman

Das erste öffentlich bekannt gewordene Public-Key-Kryptosystem wird nach seinen Erfindern als Diffie-Hellman-Schlüsselaustausch bezeichnet. Manchmal nennt man dieses Schema auch exponentieller Schlüsselaustausch oder einfach nur Diffie-Hellman bzw. kurz DH. Whitfield Diffie und Martin Hellman beschrieben es im Jahre 1976 in dem schon erwähnten Artikel New Directions in Cryptography. Es hat noch heute praktische Bedeutung.

Anders als RSA oder ElGamal eignet sich Diffie-Hellman weder zum Ver- und Entschlüsseln von Nachrichten noch für digitale Signaturen. Es läßt sich dafür aber, worauf der Name schon hindeutet, effizient für den sicheren Austausch eines geheimen Schlüssels über einen öffentlichen Kanal (Telefon, Rechnernetz, Zeitung, ...) einsetzen, ohne daß man dazu ein gemeinsames Geheimnis benötigt.

Die Sicherheit des Verfahrens basiert auf der Schwierigkeit der Berechnung diskreter Logarithmen in einem endlichen Körper, konkret im Galoisfeld GF(p). Diffie-Hellman benötigt zwei öffentliche Parameter, die vorab festzulegen sind und von mehreren Nutzern gemeinsam verwendet werden können:

Man nennt g meist Generator, Erzeuger oder Primitivwurzel modulo p. Wir können auch so sagen: Für jede Zahl b von 1 bis p-1 existiert ein i aus dem geschlossenen Intervall [0, p-2], so daß

b = g i mod p.
gilt.

Es ist sehr wichtig, p hinreichend groß zu wählen, da bei zu kleinen Werten die diskrete Logarithmierung und damit das Brechen des betreffenden Systems möglich ist. Brian LaMacchia und Andrew Odlyzko äußerten sich in ihrem 1989 veröffentlichten Paper Computation of Discrete Logarithms in Prime Fields [ftp://ftp.cert.dfn.de/pub/docs/crypt/field.ps.gz] dazu wie folgt:

"... even 512-bit primes appear to offer only marginal security ...".
Die beiden Autoren hatten in diesem Artikel zuvor einen Algorithmus beschrieben, der es ihnen in relativ kurzer Zeit gestattete, den diskreten Logarithmus der beim Secure RPC von Sun verwendeten 192 Bit langen öffentlichen Diffie-Hellman-Schlüssel zu berechnen und so den Private Key zu bestimmen.

Es empfiehlt sich daher heute, für p Primzahlen mit deutlich mehr als 512 Bit zu verwenden. Zusätzlich sollte gelten, daß auch (p-1)/2 eine Primzahl ist. Als guter Hinweis für die Länge von p könnten die bei dem kryptographischen Werkzeug GNU Privacy Guard (GNUPG) [http://www.d.shuttle.de/isil/gnupg/] verwendeten Schlüssellängen dienen, da diese nach oben durch die Länge von p begrenzt werden. In der Version 0.4.1 finden wir folgende Werte:

Der Generator g kann im Gegensatz zu p auch sehr klein sein. Es gibt keinen Grund, den kleinstmöglichen Wert (oft eine einziffrige Zahl) nicht zu verwenden.

Die Bestimmung von g und p ist zwar relativ rechenaufwendig, man sollte allerdings trotzdem von Zeit zu Zeit neue Werte wählen. Gelingt es nämlich einem Angreifer, eine (wenn auch sehr große und mit enormem Aufwand zu berechnende) Tabelle der diskreten Logarithmen modulo p für ein ganz bestimmtes p zu erstellen, kann er alle privaten Schlüssel, deren zugehörige öffentliche Schlüssel mit dem betreffenden Diffie-Hellman-Schema erzeugt wurden, und damit natürlich alle ausgetauschen gemeinsamen Schlüssel ermitteln. Beim RSA wäre ein ähnlicher Angriff deutlich weniger effektvoll, da er nur einen einzigen privaten Schlüssel (einer Person bzw. eines Rechners) beträfe.

Anton und Berta erzeugen nach folgendem Protokoll einen gemeinsamen Schlüssel:

  1. Anton wählt eine zufällige, große natürliche Zahl d als privaten Schlüssel und berechnet den öffentlichen Schlüssel D :
    D = g d mod p
  2. Berta wählt eine zufällige, große natürliche Zahl e als privaten Schlüssel und berechnet den öffentlichen Schlüssel E :
    E = g e mod p
  3. Beide Partner tauschen die öffentlichen Schlüssel aus. Danach verfügt Anton über E und Berta über D.

  4. Anton berechnet k = E d mod p

  5. Berta berechnet k' = D e mod p

  6. Als Resultat ensteht bei beiden Partnern ein gemeinsamer Schlüssel:
    KAB = k = E d mod p = (g e)d mod p = (g ed) mod p = (g de) mod p = (g d)e mod p = D e mod p = k'
Fremde, die die Konversation zwischen Anton und Berta mithören, sind nicht in der Lage, KAB zu berechnen, da sie keinen der privaten Schlüssel d und e kennen. Sie könnten nun versuchen, einen Private Key aus dem zugehörigen Public Key zu bestimmen. Dazu müßten sie allerdings den diskreten Logarithmus des öffentlichen Schlüssels ermitteln, was bei hinreichend großen Schlüsseln in der Regel nicht gelingen dürfte.

Es wäre prinzipiell möglich, daß jemand ein im Vergleich zur diskreten Logarithmierung einfacheres Verfahren findet, das es ihm gestattet, KAB direkt aus D und E abzuleiten. Bisher ist allerdings trotz intensiver Suche kein solcher Weg bekannt geworden. Andererseits konnte auch noch nicht allgemeingültig gezeigt werden, daß das Diffie-Hellman-Problem, d.h. die Bestimmung des gemeinsamen Schlüssels ohne Kenntnis der Private Keys, sowie das diskrete Logarithmusproblem gleich schwierig sind. Es ist aber in mehreren Spezialfällen gelungen, die vermutete Äquivalenz des zur Lösung der beiden Probleme erforderlichen Rechenaufwandes zu zeigen.

Im Vergleich zur diskreten Logarithmierung ist deren Umkehroperation, also die diskrete Exponentiation, relativ leicht und damit schnell realisierbar. Sie stellt daher bei geeigneter Wahl von g und p einen guten Kandidaten für eine Einwegfunktion dar.

Da keine Authentifizierung der Partner stattfindet, ist das Diffie-Hellman-Verfahren gegen einen aktiven Angriff anfällig, der in der englischsprachigen Literatur oft als man-in-the-middle attack bezeichnet wird.

Nehmen wir an, Cäsar, der "Mann in der Mitte", kann die zwischen Anton und Berta über ein Rechnernetz ausgetauschten Nachrichten beliebig verändern, weil sie einen von Cäsar verwalteten Router passieren. Dann gelingt es ihm, sich gegenüber einem Partner als der jeweils andere auszugeben und mit beiden je einen gemeinsamen geheimen Schlüssel auszutauschen: KAC mit Anton und KBC mit Berta. Nun kann Cäsar nachfolgend die gesamte Kommunikation mitlesen oder auch verändern. Kommt z.B. eine Nachricht von Anton, entschlüsselt er sie mit KAC, verändert oder liest sie, chiffriert sie danach mit KAB und sendet sie an Berta weiter.

Diesem Problem läßt sich sehr einfach durch die Verwendung zertifizierter öffentlicher Schlüssel begegnen. Damit kann jeder Teilnehmer überprüfen, ob ein bestimmter Schlüssel wirklich dem vermeintlichen Partner gehört. Man erreicht dadurch die für die gesamte Public-Key-Kryptograhie ganz wichtige zuverlässige Bindung eines öffentlichen Schlüssels an einen bestimmten Identifikator (Name, Bezeichnung). Für eine Verteilung der Zertifikate eignen sich Directory-Systeme, z.B. DNS oder X.500. Der Ablauf sieht dann so aus:

RSA

Schon kurz nach Ralph Merkles Knapsack wurde 1978 das erste voll ausgereifte asymmetrische Kryptosystem vorgestellt, das sowohl die Verschlüsselung als auch die Erstellung digitaler Signaturen gestattet: RSA. Diese drei Buchstaben stehen für die drei Wissenschaftler Ronald L. Rivest, Adi Shamir und Leonard M. Adleman, die den Algorithmus im April 1977 entwickelten. Sie hatten, wie Diffie 10 Jahre später in seinem Artikel The First Ten Years of Public-Key Cryptography bemerkte, entdeckt, wie ein einfaches Stück klassischer Zahlentheorie benutzt werden konnte, um ein praxistaugliches asymmetrisches Kryptosystem zu konstruieren. Ihr Verfahren stellt den wohl spektakulärsten Einzelbeitrag zur Public-Key-Kryptographie dar.

RSA ist der populärste Algorithmus seiner Art, der bis heute vielen Jahren intensivster Kryptoanalyse standgehalten hat. Besonders interessant erscheint in diesem Zusammenhang der Fakt, daß RSA wesentlich einfacher zu verstehen und zu implementieren ist als die meisten anderen öffentlich bekannt gewordenen Public-Key-Verfahren. Wir werden uns deshalb in einem eigenen Abschnitt etwas ausführlicher damit auseinandersetzen.

ElGamal

Der Kryptologe Taher ElGamal hat 1984 in seiner Dissertation Cryptography and logarithms over finite fields sowie 1985 in einem Artikel mit dem Titel A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms ein nach ihm benanntes Kryptosystem vorgestellt, das sowohl zur Erstellung digitaler Signaturen als auch zur Verschlüsselung geeignet ist. Anders als RSA verwendet ElGamal für das Signieren und Chiffrieren zwei unterschiedliche Algorithmen.

ElGamal wurde nicht patentiert, unterlag allerdings (zumindest in den USA) bis zum 29. April 1997 dem bis zu diesem Datum gültigen Patent für das Diffie-Hellman-Verfahren. Mit dem Ablauf dieses Patents ist das Interesse an ElGamal erkennbar gestiegen, da man dieses Kryptosystem nun ganz legal ohne Lizenzgebühren nutzen kann. In neueren kryptographischen Protokollen und Werkzeugen wird es zunehmend genutzt.

Um einen Eindruck vom Prinzip des ElGamal-Verfahrens zu gewinnen, seien nachfolgend die wichtigsten Punkte überblicksartig dargestellt:

  1. ElGamal-Signaturschema

    öffentlicher Schlüssel:

    Tripel (p, g, y) mit
    p "geeignete" große Primzahl (empfohlen: mindestens 768 Bit)
    g Generator mod p (analog Diffie-Hellman)
    y = g x mod p

    privater Schlüssel:
    x mit 0 < x < p-1

    Signieren:
    M zu signierende Nachricht bzw. in der Regel deren mittels einer Einweg-Hashfunktion berechneter Hashwert
    k zufällig gewählt, 0 < k < p-1, k und p-1 müssen teilerfremd sein
    a = g k mod p
    b = k-1(M - xa) mod (p-1)

    Das Zahlenpaar (ab) ist die Signatur. Der Zufallswert k ist geheimzuhalten. k-1 ist das inverse Element (die Inverse) zu k und läßt sich mit Hilfe des Erweiterten Euklidischen Algorithmus (s. euklid.htm) bestimmen. Etwas detaillierter werden wir diese Frage im Abschnitt RSA erörtern.

    Verifikation einer Signatur:

    Eine Signatur wird akzeptiert, wenn folgendes gilt:

    • 0 < a < p
    • 0 < b < p
    • y aa b mod p = g M mod p

  2. ElGamal-Verschlüsselung

    öffentlicher Schlüssel:

    Tripel (p, g, y) mit
    p "geeignete" große Primzahl (empfohlen: mindestens 768 Bit)
    g Generator mod p (analog Diffie-Hellman)
    y = g x mod p

    privater Schlüssel:
    x mit 0 < x < p-1

    Verschlüsselung:
    M zu chiffrierende Nachricht
    k zufällig gewählt, 0 < k < p-1
    a = g k mod p
    b = y kM mod p

    Das Zahlenpaar (ab) ist das Chiffrat. Es ist doppelt so lang wie der Klartext, was allerdings nicht ins Gewicht fällt, wenn man nur kurze Nachrichten (typischerweise Schlüssel für symmetrische Kryptosysteme) chiffriert. Der Zufallswert k ist wieder geheimzuhalten.

    Entschlüsselung:

    M = b/a x mod p

    Die Division durch a x entspricht der Multiplikation mit dem inversen Element a-x. Dieses kann sehr leicht durch den Ausdruck a p-1-x berechnet werden, da folgendes gilt:

    a p-1-x = a p-1 a-x = (g k) p-1 a-x = (g p-1)k a-x = 1k a-x = a-x (mod p)
    g p-1 hat den Wert 1, weil g ein Generator mod p ist.

Die Primzahl p sowie der Generator g können generell für mehrere Nutzer identisch sein, müssen allerdings immer sehr sorgfältig gewählt werden. Details dazu sind in der Literatur zu finden.

ElGamal benötigt für jeden Signatur- und Verschlüsselungsvorgang einen neuen Wert k. Dieser ist echt zufällig zu wählen. Sollte einem Angreifer ein bestimmtes k zusammen mit einer damit verschlüsselten bzw. signierten Nachricht in die Hände fallen, so kann er den privaten Schlüssel x seines Opfers ermitteln. Sofern der Angreifer zwei verschiedene Nachrichten besitzt, die mit demselben k verschlüsselt bzw. signiert wurden, kann er k und anschließend x bestimmen.

Zwischen ElGamal und Diffie-Hellman besteht ein relativ enger Zusammenhang. Bei beiden Verfahren werden die öffentlichen Schlüssel auf dieselbe Weise aus den privaten Schlüsseln berechnet. Die Sicherheit von ElGamal beruht daher auch auf dem diskreten Logarithmusproblem sowie dem Diffie-Hellman-Problem. Bei der ElGamal-Verschlüsselung wird de facto mittels Diffie-Hellman der Sitzungsschlüssel

y k = g xk = a x (mod p)
ausgetauscht und die Nachricht durch Multiplikation mit diesem Sitzungsschlüssel (y kM mod p) chiffriert. Beutelspacher schreibt dazu wörtlich: Das ElGamal-Verschlüsselungsschema kann als Variante des Diffie-Hellman-Schemas mit eingebautem Verschlüsselungsalgorithmus aufgefaßt werden. Er weist auch darauf hin, daß man statt der Multiplikation mit dem Sitzungsschlüssel auch andere Verschlüsselungsfunktionen verwenden könnte.

DSA

RSA ist de facto der internationale Standard. Dennoch wurde in den USA durch das NIST am 19. Mai 1994 für die Erstellung digitaler Unterschriften ein anderer offizieller Standard verabschiedet: der Digital Signature Algorithm (DSA). Dieser nutzt SHA-1 als Hashfunktion und ist in der bereits erwähnten NIST FIPS PUB 186 Digital Signature Standard (kurz DSS) [http://csrc.nist.gov/fips/fips186.ps] beschrieben.

DSA kann als Modifikation des ElGamal-Signaturverfahrens sowie des 1991 von Claus P. Schnorr vorgestellten Schnorr-Signaturverfahrens angesehen werden. Das ElGamal-Signaturschema stellt die Basis für eine Reihe von Signaturverfahren dar, unter ihnen DSA und Schnorr. Letzteres ist eine Weiterentwicklung von ElGamal, die speziell für die Implementierung auf Chipkarten entworfen wurde. Bei allen drei basiert die Sicherheit auf dem Problem des diskreten Logarithmus. Die mathematischen Zusammenhänge sind schwieriger zu fassen als bei RSA. Sie sollen uns hier nicht weiter beschäftigen.

Eine erste Version von DSA war bereits im August 1991 angekündigt worden. Daraufhin brach eine heftige Debatte los, und von vielen Seiten, speziell von Unternehmen, die schon enorme Investitionen in RSA getätigt hatten, kamen starke Kritiken und Beschwerden. Die Firma RSA Data Security, Inc. (RSADSI), die viel Geld mit dem Verkauf von RSA-Lizenzen verdient, führte die Kritiker aus verständlichen Gründen an. Sie wollte natürlich ihren Algorithmus als Standard festgeschrieben sehen. Hier folgt eine im wesentlichen von Schneier übernommene Liste der vorgebrachten Argumente mit einigen Kommentaren:


© Holger Trapp, 1.7.1999