Schlüssel Mystery Cache

Die meisten bekannten und von Geocachern verwendeten Chiffren sind symmetrische Verschlüsselungsverfahren. D.h. es existiert ein zwischen Sender und Empfänger vereinbarter, geheimer Schlüssel, mit dem die Nachricht verschlüsselt und auch wieder entschlüsselt werden kann. Als einfaches Beispiel bildet bei der Cäsar-Chiffre (ROT-X) die Anzahl der verschobenen Zeichen der Schlüssel. Am Beispiel der Jägerzaun Chiffre können wir den Begriff der symmetrischen Verschlüsselungsverfahren ausdehnen auf alle Verfahren, bei denen bei Kenntnis der Verschlüsselungsmethode mit geringem Aufwand der Entschlüsselungsalgorithmus bestimmt werden kann.
Alle diese Verfahren haben das grosse Problem, dass der geheime Schlüssel vor der Kommunikation auf sicherem Weg vereinbart werden muss. Ohne bereits existierenden, sicheren Kanal muss man dann bald einmal auf den persönlichen Kontakt zurückfallen. Offensichtlich ist das weder für die länderübergreifende Kommunikation, noch für das Aufrufen einer verschlüsselten Webseite (z.B. geocaching.com, siehe HTTPS) praktikabel.

Zum Glück gibt es seit einem guten halben Jahrhundert auch asymmetrische Verschlüsselungsverfahren. Hierbei gibt es nicht einen, sondern zwei verschiedene Schlüssel: Der Public Key ist öffentlich und kann von allen zur Verschlüsselung benutzt werden, während die Entschlüsselung nur mit dem geheimem Private Key möglich ist. Die Tatsache, dass es möglich ist, jemanden anzuleiten eine Nachricht zu verschlüsseln, sodass die Entschlüsselung für niemand anderen (ja nicht einmal die verschlüsselnde Person) möglich ist, grenzte für mich erstmals an Magie.
Erfreulicherweise ist aber die Mathematik, um mindestens den Kern der Anwendung dieser für die moderne Kommunikation unentbehrlichen Verfahren zu verstehen, überraschend einfach und genau damit geht es weiter unten für Interessierte weiter.

Public-Key Verschlüsselung

Wir benutzen eine vereinfachte Version von RSA, dem ersten veröffentlichten asymmetrischen Verschlüsselungsverfahren. Nachfolgend sind die relevanten Definitionen links in den blauen Boxen und ein einfaches Beispiel zur Illustration rechts in den grünen. Zusätzlichen, für das Rätsel aber nicht notwendigen Kontext findet sich in den Fussnoten.

Generieren der Schlüssel

In einem ersten Schritt müssen die beiden Schlüssel generiert werden. Dazu wählen wir zwei grosse, zufällige Primzahlen [1] und multiplizieren sie zum RSA-Modul N.

Davon berechnen wir die Carmichael-Funktion. Da wir wissen, dass N das Produkt zweier Primzahlen ist, können wir dies vereinfachen und brauchen bloss das kleinste gemeinsame Vielfache (kgV).

Nun wählen wir eine Zahl e mit den Eigenschaften:

Wobei die zweite Bedingung mit dem ggT, dem grössten gemeinsamen Teiler, bedeutet, dass die beiden Zahlen keine gemeinsamen Faktoren haben, also coprim sind [2]. Nun müssen wir noch eine Zahl berechnen, nämlich die modulare multiplikative Inverse von e (mod φ[N]):

D.h. man finde eine Zahl d, sodass das Produkt von d und e geteilt durch φ[N] exakt einen Rest von 1 ergibt. Somit haben wir alle Zahlen für die beiden Schlüssel:

Den öffentlichen Schlüssel können wir nun allen Kommunikationspartnern mitteilen oder auch publizieren. Der private Schlüssel muss sicher aufbewahrt werden. φ[N], p und q benötigen wir nicht mehr. Sie müssen aber geheim gehalten werden, da damit die Berechnung von d möglich würde.

Verschlüsseln und Entschlüsseln

Um die Sache möglichst einfach zu halten, beschränken wir die Nachrichten auf reine Dezimalzahlen [3]. Die Verschlüsselung einer Nachricht m mit dem Public Key (N, e) zum Chiffrat c ist nun:

Die Entschlüsselung von c zurück zu m ist praktisch identisch, benötigt aber den Private Key (N, d) [4]:

Doch warum ist dies sicher? Unter der Voraussetzung, dass die Verschlüsselung korrekt implementiert ist, kann mathematisch bewiesen werden, dass es keinen wesentlich effizienteren Weg gibt, die Verschlüsselung zu knacken, als das im Public Key enthaltene N in die beiden Primfaktoren p und q zu faktorisieren, um im Anschluss den Private Key zu berechnen. Dies ist eine klassische Einwegfunktion, d.h. die Multiplikation der beiden Faktoren ist einfach, aber die Faktorisierung eines grossen Produkts nur schwer zu berechnen [5]. Wobei gross natürlich relativ zur Rechenleistung der Computer zu verstehen ist, N sollte heutzutage mindestens 600 Stellen haben.

Signieren und Verifizieren

Public und Private Keys können noch mehr als bloss verschlüsseln und entschlüsseln. Man kann damit auch Nachrichten signieren und so deren Echtheit überprüfen [6]. Um den Absender zu verifizieren, kann dieser mit seinem Private Key eine auf der Nachricht basierte Signatur erstellen und mitschicken. Der Empfänger kann dann mit dem Public Key des Absenders überprüfen, dass die Signatur stimmt. Analog zum Ver- und Entschlüsseln kann also nur der Private Key signieren, aber alle mit dem Public Key diese Signatur überprüfen.
Dazu berechnet der Absender den Wert einer allgemein bekannten Hashfunktion [7] mit der Nachricht als Input. Auf das Resultat wird nun mit dem Private Key dieselbe Operation angewendet, die fürs Entschlüsseln der Nachrichten verwendet wird, und man erhält so die Signatur. Grundsätzlich funktioniert dies für verschlüsselte Nachrichten und auch Klartext.
Der Empfänger berechnet basierend auf der eigentlichen Nachricht wiederum den Hashwert. Zusätzlich nimmt er die Signatur und wendet darauf mit dem Public Key des Absenders die Operation analog zum Verschlüsseln an. Stimmt dieses Resultat mit dem Hashwert überein, wurde die Nachricht korrekt übermittelt (Integrität) und vom Inhaber des Private Keys signiert (Authentizität).

Fussnoten & Bemerkungen

1. Die Grösse der Primzahlen ist für die Sicherheit entscheidend, diejenigen des Beispiels sind klar zu klein. Auch sollten die beiden Zahlen genügend unterschiedlich gross sein, da ansonsten die Faktorisierung des Produkts ausgehend von der Quadratwurzel zu einfach sein kann.
2. Die beiden Bedingungen lassen grundsätzlich sehr kleine e zu. In der Praxis wird oft 65537 gewählt, kleinere Zahlen sind unter Umständen weniger sicher.
3. Wir lassen also einige Probleme weg, wie z.B. die Umwandlung von Text in Zahlen (ASCII, Unicode), der Umgang mit Nachrichten, die länger sind als das RSA-Modul N, oder die Frage des Padding. Es ist wichtig festzuhalten, dass wir so nur Nachrichten verschlüsseln können, die kleiner als N sind.
4. Diese Exponentialrechnungen mit Modulus mögen für uns ungewohnt sein, können aber von Computern effizient berechnet werden, siehe Modular Exponentiation.
5. Oft hört man, dass funktionierende Quantencomputer einige der heute weitverbreiteten Verschlüsselungen aushebeln könnten. Im Kern ist exakt diese Einwegfunktion gemeint, denn mit dem Shor-Algorithmus könnten grosse Zahlen effizient faktorisiert werden. Noch basieren die schnellsten, klassischen Algorithmen auf einem Zahlkörpersieb (general number field sieve). In der Zukunft werden wir wohl neue Algorithmen benötigen, z.B. solche, die mit Basisvektoren von Kristallgittern funktionieren.
6. Oft benützt man für die Signatur einen leicht anderen Algorithmus, denn gerade RSA ist dafür in der Praxis nur begrenzt geeignet. Auch werden oftmals separate Schlüsselpaare verwendet. Wir vereinfachen und lassen dies hier weg.
7. Bei langen Nachrichten kann mit der Hashfunktion verhindert werden, dass eine Signatur, die ähnlich lang ist wie die originale Nachricht, mitgesendet werden muss. Die Signatur lediglich auf den kurzen Hashwert zu machen, ist also effizienter.

• Obschon Computer effizient mit asymmetrischen Verschlüsselungen umgehen können, sind sie rechenaufwändiger als symmetrische Verfahren. Daher werden Public-Key-Verfahren oft nur für den Erstkontakt verwendet, um einen nur den Kommunikationspartnern bekannten, symmetrischen Schlüssel auszuhandeln. Danach wird lediglich dieser verwendet. Siehe Diffie-Hellman-Schlüsselaustausch.

Rätsel

Ich habe gemäss obiger Anleitung ein Schlüsselpaar generiert und die Zahlenfolge der Finalkoordinaten (inklusive führender Nullen, aber ohne Buchstaben oder Sonderzeichen) mit dem Public Key verschlüsselt. Obschon die Ankerkoordinaten bei der Liegenschaft Schlossberg liegen, findet Ihr dort nichts, was beim Finden des Schlüssels helfen würde.