Symmetrische Verschlüsselung ist wunderbar, wenn Alice & Bob einen gemeinsamen Schlüssel haben. Aber wie sollen die beiden einen Schlüssel vereinbaren, wenn sie nur einen unsicheren Übertragungskanal haben? Wie können sie verhindern, dass Eve ihre Nachricht abhört?

Mögliche Lösungen:

• einen sicheren Kanal etablieren, z.B. einen vertrauenswürdigen Kurier
• andere?

• Du darfst beliebig viele Vorhängeschlösser und Truhen verwenden.

Lösung:

Im Internet senden wir nur ungern Schlösser um die Welt. Stattdessen nutzen wir ein mathematisches Verfahren, das ähnliche Eigenschaften hat:

• die Durchführung der Funktion in eine Richtung (= Verschliessen des Schlosses) ist schnell.
• die Umkehrung der Funktion (= Entschlüsseln) ist sehr schwierig, ausser man kennt den geheimen Schlüssel

Die meistgenutzte Funktion ist die Primzahl-Faktorisierung:

• die Multiplikation von zwei Zahlen ist einfach
• die Faktorisierung einer grossen Zahl in ihre Primfaktoren ist sehr schwierig

Probiere es aus:

Wie lange hast du, um die Zahl 2881 in seine Primfaktoren zu zerlegen?

Wie lange für

145906768007583323230186939349070635292401872375357164399581 871019873438799005358938369571402670149802121818086292467422 828157022922076746906543401224889672472407926969987100581290 103199317858753663710862357656510507883714297115637342788911 463535102712032765166518411726859837988672111837205085526346 618740053?

Entscheidend für die Sicherheit: Das Problem der Primzahl-Faktorisierung ist NP-Vollständig. Wird die Schlüssellänge verdoppelt, so wird die Faktorisierung nicht nur doppelt so schwierig, auch nicht viermal so schwierig, sondern exponentiell schwieriger. Das heisst, dass sich die Schwierigkeit jedesmal verdoppelt, wenn auch die Zahl nur um eine einzige Stelle anwächst. Wenn du dich an das exponentielle Wachstum der Covid-Infektionen erinnerst, weisst du, dass damit sehr schnell riesengrosse Werte erreicht werden.

Die Mathematik hinter der asymmetrischen Verschlüsselung lassen wir zur Seite. Wir merken uns nur, dass es zum Verschlüsseln reicht, die grosse Zahl zu kennen, aber für die Entschlüsselung deren Primfaktoren bekannt sein müssen.

Die asymmetrische Verschlüsselung beruht darauf, dass jeder Teilnehmer ein Schlüsselpaar (key pair) erzeugt: den geheimen Schlüssel (private key) und den öffentlichen Schlüssel (public key). Weil für die Entschlüsselung ein anderer Schlüssel notwendig ist, heisst das Verfahren asymmetrisch.

Alice verwendet nun Bobs öffentlichen Schlüssel (= ein offenes Vorhängeschloss), um ihre Nachricht zu verschlüsseln. Sie sendet die verschlüsselte Nachricht an Bob, der als einziger den geheimen Schlüssel hat und die Nachricht entziffert.

Fragen

Wie weiss Alice, dass sie wirklich Bobs öffentlichen Schlüssel hat?

Was passiert, wenn Bob seinen geheimen Schlüssel verliert?

Wie kann Alice eine Nachricht an Bob und Charlie senden?