MSTR Cat

Blockchain/Niveau I · Geld/1.2 Der Weg der Cypherpunks/Lektion 1

Public-Key-Kryptografie: Diffie-Hellman und RSA

Das Geheimnis, das man teilt, ohne sich zu treffen, und die Signatur, die Eigentum beweist

MaterialienEin Rechner oder eine Tabellenkalkulation, die modulare Arithmetik verarbeiten kannDer Diffie-Hellman-Artikel (1976)

Neugier

  1. Wie können zwei Fremde sich auf einen geheimen Schlüssel einigen, während alle anderen zuhören?
  2. Warum ist das Multiplizieren zweier großer Primzahlen trivial, aber die Bestimmung dieser Primzahlen aus ihrem Produkt nahezu unmöglich?
  3. Was bedeutet es, etwas zu besitzen, wenn Besitz durch die Fähigkeit zu signieren definiert ist?

Erkunden

  1. Vor 1976 erforderte sichere Kommunikation ein gemeinsames Geheimnis, das über einen vertrauenswürdigen Kanal ausgetauscht werden musste. Fing ein Angreifer diesen Schlüssel ab, war der gesamte nachfolgende Datenverkehr kompromittiert. Whitfield Diffie und Martin Hellman schlugen in „New Directions in Cryptography“ (IEEE Transactions on Information Theory, November 1976) eine Lösung vor. Zwei Parteien konnten mithilfe modularer Exponentiation über einen offenen Kanal ein gemeinsames Geheimnis ableiten. Die Mathematik funktioniert nur in eine Richtung: Vorwärts ist sie leicht zu berechnen, ohne die private Eingabe lässt sie sich jedoch praktisch nicht umkehren.
  2. Ralph Merkle entwickelte zwischen 1974 und 1975 ähnliche Rätsel und veröffentlichte sie 1978. Eine Partei veröffentlichte viele kleine verschlüsselte Rätsel; die andere löste ein zufällig gewähltes davon und verwendete seinen Inhalt als Schlüssel. Der Vorsprung war nur quadratisch: Bei n Rätseln leisteten die beiden Parteien etwa n Arbeitseinheiten, ein Lauscher etwa n². Bei Diffie-Hellman wächst der Abstand mit der Schlüssellänge, und wenn für jede Sitzung neue Schlüsselpaare verwendet werden, legt ein späteres Leak langfristiger Schlüssel den früheren Datenverkehr nicht offen.
  3. Ron Rivest, Adi Shamir und Leonard Adleman entwickelten RSA 1977 am MIT. Martin Gardner beschrieb das System in seiner Kolumne im Scientific American vom August 1977, noch bevor der formelle Artikel in Communications of the ACM (Februar 1978) erschien. RSA beruht auf der Schwierigkeit, das Produkt zweier großer Primzahlen in seine Faktoren zu zerlegen. Es ermöglichte digitale Signaturen: Ein privater Schlüssel signiert Daten, und der zugehörige öffentliche Schlüssel verifiziert sie, ohne das Geheimnis des Signierenden preiszugeben.
  4. James Ellis entwickelte beim GCHQ um 1969 die „nicht-geheime Verschlüsselung“ und hielt sie 1970 schriftlich fest; Clifford Cocks leitete 1973 ein RSA-äquivalentes System her; Malcolm Williamson leitete 1974 ein Diffie-Hellman-äquivalentes Verfahren her. Diese Entdeckungen blieben bis 1997 als geheim eingestuft. Die parallele Entwicklung zeigt, dass die mathematischen Grundlagen bereits Anfang der 1970er-Jahre ausgereift waren, ihre Verbreitung aber erst nach der offenen Veröffentlichung durch akademische Forscher einsetzte. Geheime Arbeit schafft keine öffentliche Infrastruktur.
  5. Rivest, Shamir und Adleman erhielten 2002 den Turing Award, Diffie und Hellman 2015. Für Bitcoin ist das entscheidend: Eigentum ist nicht mehr an physischen Besitz oder Bankunterlagen gebunden, sondern an die Fähigkeit, mit einem privaten Schlüssel eine gültige Signatur zu erzeugen. Bitcoin verwendet statt RSA Elliptische-Kurven-Kryptografie auf Basis von secp256k1, doch die Grundstruktur bleibt dieselbe. Ein Nutzer beweist die Kontrolle über seine Mittel, indem er Transaktionen signiert; das Netzwerk verifiziert dies über die öffentlichen Schlüssel, ohne die privaten jemals zu sehen.
  6. Gehen Sie Diffie-Hellman mit kleinen Zahlen durch. Einigen Sie sich öffentlich auf eine Primzahl p = 23 und eine Basis g = 5. Alice wählt einen geheimen Wert a = 6 und sendet 5^6 mod 23 = 8. Bob wählt b = 15 und sendet 5^15 mod 23 = 19. Alice berechnet 19^6 mod 23 = 2; Bob berechnet 8^15 mod 23 = 2. Beide besitzen nun das Geheimnis 2, obwohl nur 23, 5, 8 und 19 über den offenen Kanal gingen. Reale Systeme verwenden Zahlen mit Hunderten von Stellen, bei denen es praktisch unmöglich ist, a oder b aus den öffentlichen Werten zu ermitteln.

Kernfakten

  • Diffie und Hellman veröffentlichten ihr Schlüsselaustauschprotokoll im November 1976.
  • RSA wurde 1977 am MIT entwickelt und im Februar 1978 in den Communications of the ACM veröffentlicht.
  • Beim GCHQ entwickelten James Ellis, Clifford Cocks und Malcolm Williamson zwischen etwa 1970 und 1974 Public-Key-Verfahren – unabhängig von den späteren amerikanischen Arbeiten.
  • Die Arbeiten des GCHQ zur Public-Key-Kryptografie wurden 1997 freigegeben.
  • Die Sicherheit von RSA beruht auf der Schwierigkeit, das Produkt zweier großer Primzahlen zu faktorisieren.
  • Eigentum an Bitcoin ist durch die Fähigkeit definiert, mit einem privaten Schlüssel zu signieren.

Übung neun, sechs, drei, eins

9SammelnNennen Sie 9 kryptografische Primitive oder Protokolle aus dem Zeitraum 1970–2008. Geben Sie jeweils den Erfinder, das Jahr und die zentrale mathematische Eigenschaft an.
6GruppierenGruppieren Sie die 9 in 6 Kategorien: Schlüsselaustausch, digitale Signaturen, Hashing, symmetrische Verschlüsselung, Authentifizierung oder sonstige.
3VerdichtenReduzieren Sie die 6 Gruppen auf 3 Gründe, warum asymmetrische Kryptographie dezentralisierte Systeme ermöglicht hat.
1KristallisierenSchreiben Sie 1 Satz darüber, was ein privater Schlüssel beweist und warum das den Begriff des Eigentums verändert.

Faktcheck

Datumsangaben, Zahlen und Behauptungen wurden mit den unten aufgeführten veröffentlichten Quellen abgeglichen.

In der interaktiven Akademie öffnen →

EN PT ES ZH JA KO RU FR MS