Überblick über die Arbeitsweise von PGP

Inhaltsverzeichnis

• Einleitung: Was ist PGP?
• Kryptologie
• Asymmetrische Verfahren
• PGP im Überblick
• IDEA
  • Sicherheit
• RSA
  • Zusammenfassung
  • Sicherheit
• MD5
  • Sicherheit
• Paßphrase
• Fußnoten
• Literaturverzeichnis

Einleitung: Was ist PGP?

PGP steht für „Pretty Good Privacy“¹ und ist ein Verschlüsselungsprogramm. Mit PGP lassen sich Texte aller Art verschlüsseln, um sie vor unerwünschtem Lesen zu schützen.

PGP wurde im Jahre 1990 von Philipp Zimmermann in den USA entwickelt. Zimmermann wurde daraufhin wegen Verstoß gegen das amerikanische Waffenexportgesetz verfolgt, weil das Programm im Sinne des Gesetzes als Munition gilt. Das Vergehen Zimmermanns bestand darin, daß er PGP über das Usenet verbreitet hatte. Die Anklage wurde schließlich fallengelassen (vgl. Mayo; Winkel).

Eine nicht-technische Einführung in PGP bieten Bruckmayr & Krier.

Kryptologie

Die Kryptologie ist die Wissenschaft vom Ver- und Entschlüsseln. Dabei geht es immer darum, daß eine Botschaft vom Sender derart verändert wird, daß sie nur der gewünschte Empfänger verstehen kann. Dies dient als Schutz, falls die Botschaft auf dem Weg vom Sender zum Empfänger jemandem anderen in die Hände fällt. In diesem Fall soll die Verschlüsselung gewährleisten, daß dieser Jemand den Inhalt nicht verstehen kann.

Grundsätzlich lassen sich dabei zwei Arten unterscheiden:

• Die Geheimbotschaft wird so in eine andere „belanglose“ Botschaft eingebunden, daß ein Außenstehender nicht bemerkt, daß überhaupt eine Geheimbotschaft vorhanden ist (Steganographie).
• Die Geheimbotschaft wird so verändert, daß sie für einen Außenstehenden keinen Sinn ergibt (Kryptographie).

Beispiele für steganographische Verschlüsselungen sind Texte, in denen nur jedes n-te (z. B. jedes dritte) Wort „wichtig“ ist; Grashalme auf einem Bild, die durch ihre Längen Morsezeichen anzeigen; Texte, in denen gewisse Worte eine andere Bedeutung haben etc. Bei der kryptographischen Verschlüsselung wird die Botschaft in Teile zerlegt (z. B. Buchstaben, Worte, Blöcke gleicher Länge), die dann durch andere Symbole ersetzt werden. Diese Symbole können, müssen aber keine herkömmlichen Buchstaben sein. Ein einfaches Beispiel ist die Darstellung jedes Buchstaben durch eine bestimmte Zahl, z. B. den ASCII-Code. Cäsar soll angeblich jeden Buchstaben durch den drittnächsten im Alphabet verschlüsselt haben, aus einem A wurde also ein D, aus einem B ein E usw.

Zur Entschlüsselung benötigt der Empfänger zwei Informationen:

• die Methode, nach der verschlüsselt wird (z. B. Weiterrücken im Alphabet, Buchstaben durch Zahlen ersetzen etc.) und
• den Schlüssel (z. B. um wieviel weitergerückt wird, welcher Buchstabe durch welche Zahl verschlüsselt wird etc.)

Asymmetrische Verfahren

Wenn die Ver- und Entschlüsselung mit dem selben Schlüssel funktioniert, heißt die Methode symmetrisch. Das ist z. B. beim Weiterrücken im Alphabet der Fall, weil man dabei mit einer entsprechenden Tabelle sowohl ver- als auch entschlüsseln kann.

Bedeutsamer sind jedoch asymmetrische Verfahren, bei denen man zum Entschlüsseln einen anderen Schlüssel braucht, als zum Verschlüsseln. Das erscheint auf den ersten Blick vielleicht unmöglich, daher ein einfaches Beispiel: Es ist sehr einfach, zu einem Namen die Telefonnummer zu finden (Methode: Ersetzung des Namens durch Zahlen; Schlüssel: Telefonbuch), aber schwierig, zu einer Telefonnummer den dazugehörigen Namen zu finden (mit demselben Telefonbuch!). Dazu braucht man ein anderes Telefonbuch (in dem die Einträge nach Nummern sortiert sind), also einen anderen Schlüssel.

Asymmetrische Verfahren heißen auch Public Key-Systeme, weil jeder Anwender sowohl über einen öffentlichen, als auch über einen (geheimen) privaten Schlüssel verfügt. Will nun jemand eine Botschaft verschicken, so verschlüsselt er sie mit dem öffentlichen Schlüssel des Empfängers und nur dieser kann sie mit seinem privaten Schlüssel entschlüsseln.

Man kann sich die Methode wie einen Aktenkoffer vorstellen: Wer mir etwas schicken will, legt die Botschaft in meinen (öffentlich zugänglichen) Aktenkoffer und verschließt ihn. Den verschlossenen Koffer kann dann nur ich mit meinem Schlüssel öffnen.

Der Vorteil von asymmetrischen Verfahren besteht darin, daß der Austausch von Schlüsseln einfacher wird: Während nämlich bei symmetrischen Verfahren die Schlüssel vor der eigentlichen Kommunikation auf einem sicheren Kanal ausgetauscht werden müssen, kann der Transport der öffentlichen Schlüssel bei asymmetrischen Verfahren auch über unsichere Kanäle erfolgen, schließlich darf den Schlüssel ja jeder sehen.

PGP im Überblick

Mit PGP können einerseits Texte verschlüsselt werden (sodaß sie nur der richtige Empfänger lesen kann), und andererseits kann man damit Texte unterschreiben (sodaß sich jeder vergewissern kann, daß der Text wirklich vom angegebenen Absender kommt und nicht verändert wurde). PGP benutzt dazu die Verschlüsselungsverfahren IDEA, RSA und MD5, auf die ich im folgenden näher eingehe.

IDEA

IDEA² ist ein symmetrisches Verfahren, das von Xuejia Lai und James Massey in Zürich entwickelt wurde. PGP benutzt IDEA zur Verschlüsselung der Botschaft.

IDEA arbeitet mit einer konstanten Schlüssellänge von 128 Bit und verschlüsselt die Botschaft in Blöcken von je 64 Bit. Der Hauptschlüssel wird zuerst in acht Unterschlüssel zu je 16 Bit geteilt, dann wird er um 25 Stellen nach links gerückt und wieder in acht Unterschlüssel geteilt. Das wird sooft wiederholt, bis insgesamt 52 Unterschlüssel generiert wurden.

Dann wird der erste 64 Bit-Block in vier Teile zu je 16 Bit zerlegt. Aus diesen vier Teilen werden mit Hilfe der ersten sechs Unterschlüssel in 14 Rechenschritten vier neue Textblöcke errechnet. Dieses Verfahren wird insgesamt acht mal durchgeführt, wobei in jedem Durchgang mit den vier Ergebnis-Textblöcken des vorigen Durchgangs begonnen wird und die jeweils nächsten sechs Unterschlüssel zur Verschlüsselung verwendet werden. Mit den vier letzten Unterschlüsseln (von 52 wurden erst 48 verwendet) werden die letzten vier Ergebnis-Textblöcke ein weiteres Mal verschlüsselt.

Dann wird der nächste 64 Bit-Block der Botschaft bearbeitet. Am Ende werden alle Ergebnisse aneinandergereiht und ergeben die verschlüsselte Botschaft. Zur Entschlüsselung wird das Verfahren von hinten nach vorne mit invertierten Schlüsseln durchgeführt.

PGP benützt für jede Verschlüsselung einen neuen IDEA-Schlüssel, dieser wird durch einen Zufallsgenerator erzeugt.

Sicherheit

Bis dato ist keine andere Methode als simples Ausprobieren zum Knacken von IDEA bekannt. Da es 2¹²⁸ ~= 3·10³⁸ (300 Sextillionen) verschiedene Schlüssel gibt, braucht ein Computer, der eine Million Schlüssel pro Sekunde ausprobiert³, über 10²⁵ (10 Quadrillionen) Jahre, bis er durch alle Schlüssel durch ist (vgl. Williams; infiNity). Da es jedoch unwahrscheinlich ist, daß ausgerechnet der letzte Schlüssel der passende ist, kann man davon ausgehen, daß es in Wirklichkeit etwas kürzer dauern würde; außerdem können mehrere Computer parallel rechnen, wodurch sich die Rechendauer abermals verringert.

RSA

RSA⁴ ist eines der ersten asymmetrischen Verfahren, es wurde 1978 entwickelt. PGP benutzt RSA zur Verschlüsselung des IDEA-Schlüssels.

Das Verfahren beruht auf der Tatsache, daß es einerseits sehr einfach ist, zwei große Primzahlen miteinander zu multiplizieren (Verschlüsselung), jedoch sehr aufwendig, die entstehende Zahl in ihre beiden Primfaktoren zu zerlegen (Entschlüsselung).

In diesem Sinne spricht man von einer sogenannten Einwegfunktion, das ist eine Funktion, die zwar leicht zu berechnen, jedoch schwer umzukehren ist. Um jedoch für den richtigen Empfänger eine einfache Entschlüsselung zu ermöglichen, verwendet man sogenannte Einwegfunktionen mit Falltüre. Die Falltür ist dabei eine Zusatzinformation, die das Entschlüsseln wesentlich erleichtert. Diese Zusatzinformation ist nur dem richtigen Empfänger bekannt, sie ist sein privater Schlüssel.

Wie wird aber ein zusammenpassendes Schlüsselpaar erzeugt?

Es werden zwei große Primzahlen c und d ausgewählt und daraus m = cd gebildet. Dann wird ein ö gewählt, sodaß ggT(m,ö) = 1, d. h. m und ö sind relativ prim (teilerfremd).

m und ö bilden den öffentlichen Schlüssel. Die als Zahl vorliegende Botschaft b wird folgendermaßen zur Geheimbotschaft v verschlüsselt:
v = bö (mod m)

Als privaten Schlüssel benötigt der Empfänger ein p, sodaß gilt:
(b^ö)^p = b (mod m), also b^öp = b (mod m).

Nun besagt ein Satz, daß das genau dann der Fall ist, wenn öp = 1 (mod (c-1)(d-1)) ⁵. Außerdem wurde bewiesen, daß ein solches p nur dann existiert, wenn ö und m relativ prim sind, daher wurde ö dementsprechend gewählt.

Die Berechnung von p kann mit dem erweiterten Euklidischen Algorithmus leicht erfolgen.

Zusammenfassung

Die Botschaft b (in unserem Fall der 128 Bit lange IDEA-Schlüssel) wird verschlüsselt zu:
v = b^ö (mod m).

p wurde so gewählt, daß (b^ö)^p = b (mod m) gilt, die verschlüsselte Botschaft kann also mittels p wieder entschlüsselt werden.

Der öffentliche Schlüssel enthält ö und m, der private p und m.

Sicherheit

Die bisher effizienteste Methode zum Knacken von RSA beruht auf der Zerlegung von m in seine beiden Primfaktoren c und d. Sind diese bekannt, so kann der private Schlüssel p wie oben leicht berechnet werden.

Bei Verwendung des schnellsten bekannten Algorithmus zur Zerlegung einer Zahl in ihre Primfaktoren (NFS⁶) benötigt ein Computer mit einer Leistung von einer Million Befehlen pro Sekunde ca. 300 Milliarden Jahre, um einen Schlüssel mit 1024 Bit zu zerlegen (vgl. infiNity). Bauer schätzt den Zeitaufwand für eine 300stellige Zahl⁷ selbst bei der für das Jahr 2004 erwarteten Rechenleistung eines Computers auf 62 Milliarden Jahre (vgl. Bauer, 1995, S. 157). Allerdings kann auch hier eine Beschleunigung durch den parallelen Einsatz mehrerer Computer erreicht werden.

Es kann jedoch nicht völlig ausgeschlossen werden, daß in Zukunft bessere Algorithmen zur Zerlegung großer Zahlen gefunden werden, wenngleich dies momentan unwahrscheinlich erscheint.

MD5

MD5⁸ ist eine sogenannte Hash-Funktion⁹ zur Authentifikation von Nachrichten. Das Verfahren berechnet aus einem beliebigem Text einen sogenannten Fingerabdruck mit 128 Bit. Aus dem Fingerabdruck kann selbstverständlich nicht auf den Text geschlossen werden, da bei einer Reduktion auf 128 Bit natürlich ein starker Datenverlust auftritt. Die Bezeichnung Hash-Funktion bedeutet, daß man weder einen Text konstruieren kann, der zu einem vorgegebenen Fingerabdruck paßt, noch zwei Texte mit identischem Fingerabdruck. Es handelt sich also um eine Einwegfunktion.

Zur Authentifikation einer Botschaft berechnet PGP den Fingerabdruck und hängt ihn an den Text an. Der Empfänger kann nun ebenfalls den Fingerabdruck berechnen und ihn mit dem erhaltenen vergleichen. Stimmen die Werte überein, ist der Text „echt“, d. h. er wurde seit dem Abschicken nicht verändert. Das sagt aber noch nichts darüber aus, ob der Text wirklich vom angegebenen Absender kommt, schließlich könnte ja ein „Angreifer“ den echten Text abfangen und ganz durch einen anderen ersetzen.

Um dem vorzubeugen, kann der Absender die Botschaft (inklusive Fingerabdruck) mit seinem privaten Schlüssel verschlüsseln. Dann kann der Text nur mit dem öffentlichen Schlüssel des Absenders entschlüsselt werden. Wichtiger ist nun allerdings der Umkehrschluß: Wenn sich ein Text mit einem öffentlichen Schlüssel entschlüsseln läßt, so muß er mit dem dazugehörigen privaten Schlüssel verschlüsselt worden sein.

Die beiden Schlüssel werden also in umgekehrter Reihenfolge verwendet: der private zum ver-, der öffentliche zum entschlüsseln. Daß das auch funktioniert, folgt aus der Kommutativität der Multiplikation:
(b^ö)^p = b^öp = (b^p)^ö.

MD5 verlängert die Botschaft zuerst solange mit Nullen, bis ihre Länge um 64 Bit weniger als ein Vielfaches von 512 Bit ist. In diesen 64 Bit wird die Länge der ursprünglichen Botschaft eingetragen; es ist also eine maximale Länge von 2⁶⁴ Bit (das sind mehr als zwei Millionen Terabyte) vorgesehen. Dann wird der Text in Blöcken zu je 512 Bit bearbeitet, wovon jeder wiederum in 16 Unterblöcke zu je 32 Bit geteilt wird. An diesen Unterblöcken werden vier Durchgänge zu je 16 Operationen durchgeführt. Als Ergebnis werden vier Blöcke zu je 32 Bit ausgegeben.

Dieses Ergebnis fließt in die Bearbeitung der nächsten 512 Bit der Botschaft ein usw. Das endgültige Ergebnis umfaßt 128 Bit und besteht aus den vier aneinandergereihten 32 Bit-Blöcken, die bei den letzten 512 Bit der Botschaft ausgegeben wurden.

Sicherheit

Um eine Nachricht zu finden, die zu einem vorgegebenen Fingerabdruck paßt, braucht ein Computer, der eine Million Nachrichten pro Sekunde prüft, über 10²⁵ (10 Quadrillionen) Jahre. Wer sich allerdings damit begnügt, zwei Nachrichten mit identischem Fingerabdruck zu finden, braucht mit dem selben Computer nur mehr 585 Jahre zu warten (vgl. infiNity).

Paßphrase

Als zusätzliche Schutzvorkehrung verschlüsselt PGP den privaten Schlüssel sofort nach der Erzeugung mit IDEA und speichert ihn nur in dieser Form ab. Als IDEA-Schlüssel wird der durch MD5 erzeugte Fingerabdruck einer vom Benutzer frei wählbaren Paßphrase verwendet. Diese Paßphrase muß bei jeder Verwendung des privaten Schlüssels eingegeben werden, da er jedesmal neu entschlüsselt werden muß. Wer seine Paßphrase vergißt, muß sich entweder ein neues Schlüsselpaar erzeugen lassen oder eben die „paar“ Jahre warten, bis sein Computer MD5 geknackt hat.

Fußnoten

1. Frei übersetzt: „ziemlich gute Privatsphäre“. >zurück in den Text
2. International Data Encryption Algorithm (internationaler Datenverschlüsselungsalgorithmus). >zurück in den Text
3. Schnelle Pentium-Computer können ein kleines Programm ca. eine Million mal pro Sekunde ausführen. >zurück in den Text
4. Benannt nach seinen Entwicklern Ronald Rivest, Adi Shamir und Leonard Adleman. >zurück in den Text
5. (c-1)(d-1) ist der Wert der Eulerschen phi-Funktion für m. >zurück in den Text
6. Number Field Sieve. >zurück in den Text
7. 1024 Bit entsprechen 309 Dezimalstellen. >zurück in den Text
8. Message-digest 5 (Nachrichten-Abriß 5). >zurück in den Text
9. „Kuddelmuddel-Funktion“. >zurück in den Text

Literaturverzeichnis

• Bauer Friedrich (1995): Entzifferte Geheimnisse — Methoden und Maximen der Kryptologie. Berlin / Heidelberg: Springer-Verlag
• Bruckmayr Christian & Krier Andreas: Datensicherheit und Kryptographie im Internet: Pretty Good Privacy. Ursprüngliche URL: http://www.univie.ac.at/philosophie/facts/krypto.htm
• Candler Brian: Cryptographic Security. Ursprüngliche URL: http://wgc.chem.pu.ru/educate/NATO/brian/crypto.html
• Daschek Stefan (1996): Kryptologie in der Informatik. Unveröffentlichte Fachbereichsarbeit am Bundesgymnasium Wien 13, Fichtnergasse 15
• Eng Asgaut: Cryptographic hash functions. http://www.pvv.org/~asgaut/crypto/thesis/node19.html
• infiNity: PGP Attacks. http://axion.physics.ubc.ca/pgp-attack.html
• Infosec Studies [Hrsg.]: One-Way Hash Functions. Ursprüngliche URL: http://www.cs.nps.navy.mil/curricula/tracks/security/notes/chap05_21.html
• Mayo Sherry: Cryptography and PGP Page. Ursprüngliche URL: http://rschp2.anu.edu.au:8080/crypt.html
• Paschinger Heike (1993): Primzahltheorie und Kryptologie — Von den Primzahlen zum RSA-System. Diplomarbeit an der Formal- und Naturwissenschaftlichen Fakultät der Universität Wien
• Rivest Ronald: The MD5 Message-Digest Algorithm. http://theory.lcs.mit.edu/~rivest/Rivest-MD5.txt
• Trapp Holger: PGP — Pretty Good Privacy. http://www-user.tu-chemnitz.de/~hot/pgp.html
• United Nations Trade Point Development Centre [Hrsg.]: One-Way Hash Functions. Ursprüngliche URL: http://iliad.lib.mq.edu.au:8080/untpdc/eto/associates/gift/hash.html
• Unruh Bill: Cryptography. http://axion.physics.ubc.ca/crypt.html
• Williams Randall: The passphrase FAQ. Version 1.04. http://www.stack.nl/~galactus/remailers/passphrase-faq.html
• Winkel Mike: The story of CRYPTO & PGP. Ursprüngliche URL: http://www1.sr.net/~t100597/pgpindex.htm