Grundbegriffe der Kryptographie

von Peter Marksteiner (Ausgabe 00/3, Oktober 2000)

 

Die Geschichte der Geheimschriften ist fast so lang wie die Geschichte der Schrift - schon Julius Caesar hat Geheimschriften verwendet. In zahlreichen Klassikern der Kriminalliteratur (z.B. bei Edgar Allan Poe oder bei Arthur Conan Doyle) kommen Geheimschriften vor. Verglichen mit heutigen Methoden der Kryptographie sind solche Geheimschriften allerdings kindische Spielereien: Heute ist die Kryptographie ein Industriezweig, der Milliarden umsetzt, viele der besten Mathematiker beschäftigt und die leistungsfähigsten und teuersten Supercomputer einsetzt. Lange Zeit auf Militär und Geheimdienste beschränkt, gehört Kryptographie im Zeitalter des electronic commerce zum Alltag des Geschäftslebens.

Die Grundaufgabe der Kryptographie läßt sich sehr einfach formulieren: Aus einem Klartext (engl. plain text) wird mit Hilfe eines Schlüssels (engl. key) ein verschlüsselter Text (engl. cipher text) erzeugt. Dieser Text wird - heutzutage fast ausschließlich elektronisch - einem Adressaten übermittelt, und niemand außer dem Empfänger, für den die Nachricht bestimmt ist, soll imstande sein, daraus den Klartext wiederherzustellen. Trotz der Bezeichnung plain text sind Kryptisierungsverfahren nicht auf Text-Daten beschränkt: Jede Form von Daten wird binär kodiert und als Folge von Einsen und Nullen dargestellt. Jede solche Folge kann auch als Binärzahl interpretiert werden. Kryptisierungs-Algorithmen können daher ohne Einschränkung der Allgemeinheit nur für die Verschlüsselung von Zahlen definiert werden. Die angewendeten Methoden sind keineswegs geheim - alle Algorithmen sind publiziert und können von allen nachvollzogen werden. Im folgenden werden einige der wichtigsten kryptographischen Verfahren vorgestellt.

Symmetrische Verfahren

Symmetrische Verfahren werden so genannt, weil derselbe Schlüssel sowohl zum Verschlüsseln als auch zum Entschlüsseln dient. Dieser Schlüssel ist einfach eine Zahl. Die meisten symmetrischen Verfahren sind sogenannte block ciphers, d.h. der zu verschlüsselnde Text wird in Blöcke zerlegt und jeder einzelne Block mit dem Schlüssel kryptisiert. Die übliche Länge eines Blocks ist 64 Bit, das entspricht acht Zeichen, wenn der für Text-Daten allgemein gebräuchliche ASCII-Zeichensatz verwendet wird. In der Praxis wird dieses Verfahren etwas modifiziert: Die Blöcke werden zusätzlichen Operationen unterworfen, sodaß identische Blöcke nicht dasselbe Ergebnis bei der Kryptisierung liefern.

Jeder Verschlüsselungs-Algorithmus besteht aus einer wohldefinierten, nicht allzu langen Folge von einfachen arithmetischen und logischen Operationen (Permutationen, Additionen, und/oder etc.). Symmetrische Kryptisierung geht sehr schnell, sodaß auch große Datenmengen in kurzer Zeit ver- und entschlüsselt werden können.

Eine wichtige Kennzahl jedes symmetrischen Algorithmus ist die Länge des Schlüssels: Jede symmetrische Kryptisierung kann (zumindest theoretisch) dadurch geknackt werden, daß alle möglichen Schlüssel durchprobiert werden. Bei einer Länge von 40 Bit gibt es 1 099 511 627 776 mögliche Schlüssel. Schafft man eine Million Schlüssel pro Sekunde (für leistungsfähige moderne Computer ist das durchaus realistisch), braucht man für eine solche Brute Force-Attacke knapp zwei Wochen. Die Vermutung liegt nahe, daß Geheimdienste und ähnliche Organisationen, die sich auf das Knacken von Codes spezialisieren, über wesentlich leistungsfähigere Spezial-Hardware verfügen und dafür höchstens einige Minuten brauchen: Was mit 40 Bit verschlüsselt durch das Netz geschickt wird, kann vermutlich fast in Echtzeit geknackt werden.1) Eine Schlüssellänge von 128 Bit hingegen dürfte auch den besten Code-Knackern mit den schnellsten Computern Kopfzerbrechen bereiten: Selbst wenn man eine Billion (1012) Schlüssel pro Sekunde probieren könnte, würde man mit Brute Force 1019 Jahre brauchen - das ist mehr als eine Milliarde Mal so lang wie das Alter der Erde.

Eine ausreichende Länge des Schlüssels ist für ein sicheres Kryptisierungsverfahren notwendig, aber nicht hinreichend. Der Algorithmus selbst kann Mängel haben, die es ermöglichen, mit verschiedenen Methoden - die wesentlich intelligenter sind als die oben beschriebene Brute Force-Attacke - den Code zu knacken. Kryptographie ist ein sehr aktives Forschungsgebiet: Ständig werden neue Algorithmen erfunden; manche können recht schnell geknackt werden und geraten wieder in Vergessenheit, andere bewähren sich und widerstehen jahrelang allen Attacken. Solche Algorithmen gelten dann allgemein als vertrauenswürdig. Einen strengen Beweis der Sicherheit eines Kryptisierungsverfahrens kann es allerdings nie geben.

Lange Zeit war der Data Encryption Standard (DES) das am weitesten verbreitete symmetrische Verfahren. Heute hat er weitgehend ausgedient, hauptsächlich wegen der bescheidenen Länge seines Schlüssels von 56 Bit, was für heutige Anforderungen viel zu wenig ist. Nur in der Variante des Triple DES (3DES), bei dem im wesentlichen der DES-Algorithmus dreimal hintereinander mit drei verschiedenen Schlüsseln verwendet wird, ist er heute noch in Gebrauch. Von den zahlreichen moderneren symmetrischen Verfahren seien hier drei der wichtigsten erwähnt:

  • IDEA ist eine Entwicklung der Schweizer Firma Ascom und verwendet Schlüssel mit 128 Bit.
  • RC4 war lange Zeit nur der Firma RSA (siehe weiter unten) zugänglich und ist heute mit 128 Bit das Standardverfahren bei Secure HTTP.
  • Blowfish ist "freie Software" - weder der Algorithmus noch die Implementation unterliegen irgendwelchen Lizenz-Beschränkungen. Die Länge des Schlüssels ist variabel bis zu 448 Bit.

Asymmetrische Verfahren

Bei asymmetrischen Verfahren (public-key cryptography) werden verschiedene Schlüssel zum Ver- und Entschlüsseln verwendet. Zum Verschlüsseln dient der public key, der, wie der Name schon sagt, öffentlich bekanntgegeben wird. Zum Entschlüsseln wird der private key benötigt, der von seinem Besitzer sorgfältig verwahrt werden muß und auf den sonst niemand Zugriff haben darf: Sobald jemand anderer den private key kennt, ist er wertlos. Wer eine asymmetrisch verschlüsselte Nachricht verschicken will, muß den public key des Empfängers kennen. Für manche Formen der sicheren Kommunikation benötigen beide Partner einen public key - jeder verschlüsselt mit dem Schlüssel des anderen.

Die meisten asymmetrischen Verfahren beruhen auf folgenden zwei Tatsachen:

  • Es ist sehr leicht festzustellen, ob eine ganze Zahl eine Primzahl ist oder nicht. Selbst bei Zahlen mit mehreren hundert Ziffern (solche werden in der asymmetrischen Kryptographie üblicherweise verwendet) braucht ein Computer dazu nur Sekundenbruchteile.
  • Wenn eine Zahl keine Primzahl ist, hat sie mindestens zwei echte Primfaktoren. Es ist jedoch kein Verfahren bekannt, bei großen Zahlen diese Faktoren auch in sinnvoller Zeit zu finden (von Sonderfällen abgesehen, z.B. wenn einer der Primfaktoren sehr klein ist oder wenn die Zahl sonstige spezielle Eigenschaften hat, die die Faktorisierung erleichtern).

Um ein Schlüsselpaar - public und private key - zu erzeugen, geht man folgendermaßen vor:

  • Man generiert zwei Primzahlen von bestimmter Größe (üblich sind 512 Bit, das entspricht im Dezimalsystem 153 oder 154 Ziffern). Dazu probiert man einfach eine Reihe von Zufallszahlen so lange durch, bis man Primzahlen findet. Die Wahrscheinlichkeit, daß eine beliebige Zahl dieser Größenordnung eine Primzahl ist, beträgt nach dem Primzahlsatz etwa 1/350; man muß also meistens einige hundert Zahlen probieren, sofern man nicht das Verfahren verfeinert und z.B. Zahlen mit kleinen Primfaktoren von vornherein ausschließt. So oder so dauert dieser Vorgang höchstens einige Sekunden.
  • Man bildet das Produkt dieser beiden Primzahlen. Nun kann - wie oben beschrieben - niemand auf der Welt in absehbarer Zeit die beiden Primfaktoren aus dem Produkt rekonstruieren. Das Produkt ist der Hauptbestandteil des public key; die beiden Primfaktoren (die nur derjenige kennt, der sie multipliziert hat) bilden den Hauptbestandteil des private key.

Das bekannteste und mit Abstand am meisten verwendete asymmetrische Verfahren ist die RSA-Methode, so benannt nach den Initialen der Erfinder (Rivest, Shamir, Adleman). Die arithmetischen Operationen, die beim RSA-Verfahren ausgeführt werden (Exponentiation und Restklassenbildung), sind wesentlich aufwendiger als bei symmetrischen Verfahren, weshalb RSA für große Datenmengen ungeeignet ist. Ausführliche Informationen zum RSA-Verfahren und zur Kryptographie im allgemeinen finden Sie unter http://www.rsa.com/; sehr informativ sind vor allem die Frequently Asked Questions.

Kombinierte Verfahren

Während der relativ hohe Rechenaufwand ein Nachteil asymmetrischer Verfahren ist, ist das Hauptproblem bei symmetrischer Kryptisierung der sichere Austausch des Schlüssels: Es muß ein Weg gefunden werden, dem Partner den Schlüssel mitzuteilen, ohne daß er von einem Dritten abgefangen werden kann. In der Praxis wird deshalb fast immer eine Kombination aus symmetrischer und asymmetrischer Kryptisierung verwendet, die die Vorteile beider Methoden vereint: Beim PGP-Verfahren zur Verschlüsselung von eMail (siehe Comment 97/2), beim Secure HTTP-Protokoll zur sicheren Kommunikation mit Webservern (siehe Comment 97/2 und Comment 00/2) und auch bei der Secure Shell (siehe Seite 23). Eine sichere Verbindung mit einem dieser Protokolle wird nach folgender Methode - mit verschiedenen Varianten - durchgeführt: Einer der beiden Partner wählt eine Zufallszahl als Schlüssel für symmetrische Kryptisierung und verschlüsselt diesen Schlüssel mit dem public key des anderen Partners. Der verschlüsselte Schlüssel wird dem Partner mitgeteilt. Für diesen ist das eine "Herausforderung" (challenge) - er muß imstande sein, ihn mit seinem private key zu entschlüsseln. Der Rest der Verbindung zwischen den Partnern wird nach einem symmetrischen Verfahren mit diesem Schlüssel kryptisiert. Generell werden symmetrische Schlüssel nur einmal verwendet (manchmal wird sogar während der Datenübertragung der Schlüssel gewechselt), während asymmetrische Schlüsselpaare jahrelang eingesetzt werden.

Digitale Unterschriften

Vielleicht haben Sie schon einmal eine eMail-Nachricht bekommen, die am Ende die Zeile --BEGIN PGP SIGNATURE-- enthielt, gefolgt von einigen Zeilen mit unverständlichen Buchstaben und Ziffern. Diese unverständlichen Zeichen bilden eine "digitale Unterschrift", mit der sichergestellt werden soll, daß eine Nachricht einerseits nicht verfälscht wurde und andererseits wirklich vom angegebenen Absender stammt. Dies ist z.B. für rechtsverbindliche Unterschriften im elektronischen Zahlungsverkehr unerläßlich. Um ein Dokument digital zu signieren, sind zwei Schritte erforderlich:

  • Im ersten Schritt wird eine hash function des Dokuments berechnet. Der Wert dieser hash function ist sozusagen ein "Fingerabdruck" des Dokuments: Er ist nur vom Dokument und dem verwendeten Algorithmus abhängig, benötigt also keine Zusatzinformationen wie z.B. Schlüssel. Er ist relativ kurz (üblich sind einige hundert Zeichen) und von konstanter Länge, egal wie lang der Text ist. Es gibt verschiedene Hash-Algorithmen, die bekanntesten sind MD5 (Message Digest) und SHA-1 (Secure Hash Algorithm). Ein guter Hash-Algorithmus soll einerseits nicht erlauben, aus dem Wert der hash function Rückschlüsse auf den Originaltext zu ziehen (die Änderung eines einzigen Bits führt zu einem völlig unterschiedlichen Ergebnis); andererseits soll es praktisch unmöglich sein, zwei verschiedene Texte zu finden, bei denen die hash function denselben Wert hat, obwohl man sehr leicht zeigen kann, daß viele solcher Texte existieren. Die Entwicklung von guten Hash-Algorithmen gehört zu den schwierigsten Aufgaben der Kryptogaphie: Immer wieder werden Hash-Algorithmen aus dem Verkehr gezogen, meist weil sie das zweite Kriterium nicht ausreichend erfüllen (so z.B. vor einigen Jahren das MD4-Verfahren).
  • Im zweiten Schritt wird die hash function mit dem private key des Absenders verschlüsselt. Meistens wird dazu das RSA-Verfahren verwendet (allerdings in der umgekehrten Richtung, also mit dem private key zum Verschlüsseln und dem public key zum Entschlüsseln); es gibt aber auch einen eigenen Digital Signature Algorithm (DSA). Die so verschlüsselte hash function ist die digitale Unterschrift, die gemeinsam mit dem Dokument an den Empfänger geschickt wird.

Um eine digitale Unterschrift zu überprüfen, geht der Empfänger eines Dokuments folgendermaßen vor:

  • Die digitale Unterschrift wird mit dem public key des Senders entschlüsselt.
  • Ebenso wie der Sender bestimmt der Empfänger die hash function des Dokuments.
  • Die Ergebnisse dieser beiden Schritte müssen exakt übereinstimmen. Sind sie unterschiedlich, wurde entweder das Dokument verfälscht oder es wurde ein falscher private key zum Signieren verwendet.

Ein fundamentales Problem der public-key cryptography wird allerdings auch mit digitalen Unterschriften nicht gelöst: Es kann keine absolute Garantie für die Authentizität eines Schlüssels geben, irgend jemandem muß man wohl oder übel vertrauen. Wenn die Firma A ihren public key veröffentlicht, gibt es keinen Nachweis, daß tatsächlich die Firma A dahintersteckt - es könnte auch die Firma B sein, die die Geheimnisse der Firma A ausspähen will. A kann sich ihren public key von der Firma C mit einem Zertifikat (d.h. einer digitalen Unterschrift) beglaubigen lassen; nun muß man aber dem public key von C vertrauen, es sei denn, C besorgt sich ein Zertifikat von D, und so weiter ad infinitum. Wie gesagt, absolute Garantie gibt es keine, aber anerkannte Zertifizierungs-Stellen (z.B. jene, die von den großen Browser-Herstellern akzeptiert werden), sind wohl recht vertrauenswürdig.

In Österreich soll das Bundesgesetz über elektronische Signaturen, das am 1. Jänner 2000 in Kraft getreten ist, die Voraussetzungen dafür schaffen, daß "elektronische Signaturen die Rechtswirkungen der Schriftlichkeit entfalten", wie es in der schönen Formulierung des § 4.(2) heißt. In diesem Gesetz ist die Einrichtung von staatlich anerkannten Zertifizierungsstellen vorgesehen. Einige solcher Stellen existieren bereits (z.B. A-Trust), allerdings sind diese Systeme noch nicht sehr ausgereift.

 

1) In den USA ist der Export von "starker" Kryptographie verboten. Beispielsweise verwenden die für den Export zugelassenen Netscape-Versionen Schlüssel mit einer Länge von 128 Bit, von denen aber nur 40 Bit geheim sind - den Rest kennt die US-Regierung.