Dies ist der zweite Cache einer Mysterie-Serie rund um die Themen

Viel Spaß beim Lösen!

Warum Verschlüsselung

Verschlüsselung ist eine technische Methode, bei der ein Klartext – also eine verständliche Nachricht – mithilfe eines bestimmten Schlüssels in eine unleserliche Form, den sogenannten Geheimtext oder Chiffretext, umgewandelt wird. Das Ziel besteht darin, Informationen so zu schützen, dass nur Personen, die den entsprechenden Schlüssel besitzen, die ursprüngliche Nachricht wiederherstellen und lesen können.

Im Kontext des Geocachings wird Verschlüsselung häufig eingesetzt. Ein einfaches Beispiel ist ROT13, eine Methode, bei der Buchstaben durch eine Verschiebung im Alphabet verschlüsselt werden. Ebenso kommen andere Code-Tabellen zum Einsatz. Bei diesen Verfahren wird die gleiche Tabelle – also der gleiche Schlüssel – sowohl zum Verschlüsseln als auch zum Entschlüsseln verwendet. Dieses Verfahren wird als „symmetrische Verschlüsselung“ bezeichnet.

Für die sichere Kommunikation ist es notwendig, dass beide Parteien den Schlüssel im Vorfeld austauschen. Dabei besteht die Gefahr, dass der Schlüssel während des Transports abgefangen wird, was die Sicherheit gefährdet.

Das Problem des sicheren Schlüsselaustauschs wird durch die sogenannte „asymmetrische Verschlüsselung“ gelöst.

Asymmetrische Verschlüsselung

Bei der asymmetrischen Verschlüsselung existieren zwei Schlüssel: ein öffentlicher Schlüssel und ein privater Schlüssel. Der öffentliche Schlüssel darf frei verteilt werden, sodass andere Personen damit Nachrichten verschlüsseln können. Der private Schlüssel bleibt hingegen geheim und wird nur vom Besitzer verwendet.

Eine Nachricht, die mit dem öffentlichen Schlüssel verschlüsselt wurde, kann nur mit dem dazugehörigen privaten Schlüssel wieder entschlüsselt werden. Umgekehrt kann eine Nachricht, die mit dem privaten Schlüssel signiert wurde, mit dem öffentlichen Schlüssel überprüft werden.
Der Vorteil dieser Methode liegt darin, dass der geheime Schlüssel nicht vorab sicher ausgetauscht werden muss. Es genügt, den öffentlichen Schlüssel zu teilen, was die Sicherheit erhöht, da kein Risiko besteht, dass der geheime Schlüssel beim Übertragen abgefangen wird.

Ablauf Nachrichten verschlüsselt versenden

Stellen wir uns vor, Alice möchte Bob eine verschlüsselte Nachricht senden. Bob besitzt dazu ein Schlüsselpaar: einen öffentlichen und einen privaten Schlüssel. Der öffentliche Schlüssel wird allgemein zugänglich gemacht. Alice nutzt diesen, um ihre Nachricht zu verschlüsseln und sendet die verschlüsselte Nachricht an Bob. Da nur Bob den privaten Schlüssel besitzt, kann nur er die Nachricht wieder in den ursprünglichen Text umwandeln und lesen. Für einen Angreifer, der den privaten Schlüssel nicht besitzt, ist das Entschlüsseln der Nachricht mit vertretbarem Aufwand nicht möglich, wodurch die Kommunikation geschützt bleibt.

Digitale Signaturen

Mit asymmetrischer Verschlüsselung ist es auch möglich, Nachrichten zu signieren. Während das Verschlüsseln sicherstellt, dass nur eine bestimmte Person die Nachricht lesen kann, dient das Signieren dazu, die Authentizität des Absenders zu gewährleisten und Manipulationen während der Übertragung zu erkennen. Der Absender „unterschreibt“ die Nachricht mit seinem privaten Schlüssel. Diese Signatur kann von jedem mit dem öffentlichen Schlüssel überprüft werden. Nur der Besitzer des privaten Schlüssels kann eine zum öffentlichen Schlüssel passende Signatur erstellen, was die Echtheit und Unversehrtheit der Nachricht bestätigt.

Das RSA-Verfahren

RSA ist ein asymmetrisches Verschlüsselungsverfahren, das im Jahr 1977 von den Mathematikern Rivest, Shamir und Adleman entwickelt wurde. Es basiert auf einer besonderen mathematischen Eigenschaft, die als „Falltürfunktion“ oder „Einwegfunktion“ bezeichnet wird. Diese Funktionen sind so konstruiert, dass sie in eine Richtung relativ einfach zu berechnen sind, während die Umkehrung – also die Rückführung in die ursprünglichen Werte – äußerst schwierig ist.

Ein anschauliches Beispiel: Es ist vergleichsweise einfach, zwei große Primzahlen miteinander zu multiplizieren. Im Gegensatz dazu ist es äußerst aufwendig, eine große Zahl in ihre ursprünglichen Primfaktoren zu zerlegen, sofern diese nicht bereits bekannt sind. Diese Eigenschaft wird im RSA-Verfahren genutzt, um die Sicherheit der Verschlüsselung zu gewährleisten.

Funktionsweise

Die zugrunde liegende mathematische Theorie ist komplex und erfordert fortgeschrittene Kenntnisse in der Zahlentheorie. Für das prinzipielle Verständnis kann es jedoch hilfreich sein, den Ablauf anhand kleinerer Zahlen nachzuvollziehen.

Im Folgenden wird der Algorithmus schrittweise anhand eines Beispiels erläutert.

Erzeugung der Schlüssel

1. Auswahl der Primzahlen

Zur Generierung der Schlüssel werden zunächst zwei Primzahlen ausgewählt. In der Praxis sind diese Zahlen meist sehr groß, oft mehrere hundert Stellen lang, um die Sicherheit des Verfahrens zu gewährleisten. Für das vorliegende Beispiel verwenden wir jedoch kleinere Zahlen:

2. Berechnung des Produkts

Das Produkt der beiden Primzahlen wird ermittelt:

Es ist leicht erkennbar, dass 33 das Produkt von 3 und 11 ist. Bei sehr großen Zahlen ist es jedoch äußerst schwierig, die ursprünglichen Primzahlen p und q aus N wieder zu bestimmen. Dieses Problem bildet die Grundlage für die Sicherheit des RSA-Verfahrens und wird als sogenannte Einwegfunktion bezeichnet.

3.    Berechnung des Hilfswerts

Der sogenannte Hilfswert M wird berechnet als:

Für Fachleute: Dieser Wert entspricht der eulerschen Phi-Funktion φ(N). Hier gilt: φ(33) = 20. Diese Funktion gibt an, wie viele Zahlen zwischen 1 und N teilerfremd zu N sind.

4.    Auswahl des öffentlichen Schlüssels

Es wird eine Zahl e gewählt, die kleiner als M ist und keinen gemeinsamen Teiler außer 1 mit M hat. Für dieses Beispiel wählen wir:

5.    Berechnung des privaten Schlüssels

Der private Schlüssel d wird gesucht, sodass gilt:

Das bedeutet, man multipliziert ( e * d ) und das Ergebnis muss durch M mit Rest 1 teilbar sein. Mit kleinen Zahlen kann diese Gleichung durch Probieren gelöst werden:

Da bei d = 7 der Rest 1 auftritt, ist:

Zusammenfassung der Schlüssel:

Öffentlicher Schlüssel: (N=33, e=3)
Privater Schlüssel: (N=33, d=7)

Jemand der die Verschlüsselung knacken möchte, könnte versuchen, die ursprünglichen Primzahlen p und q aus dem öffentlichen N = 33 zu ermitteln. Gelingt dies, kann ab Schritt 3 die Berechnung des privaten Schlüssels erfolgen, wodurch die Entschlüsselung der Nachrichten möglich wird.

Nachricht verschlüsseln

Um eine Nachricht zu verschlüsseln, verwenden wir den öffentlichen Schlüssel mit den Werten e = 3 und N = 33 und führen folgende Rechnung durch:

Das bedeutet: wir nehmen die Zahl (a), die wir verschlüsseln möchten, und berechnen sie hoch e. Anschließend bestimmen wir den Rest (b), wenn wir dieses Ergebnis durch (N) teilen. Zum Beispiel, wenn die Nachricht die Zahlen 4 und 8 sind:

Wir interessieren uns nur für die Reste: 4 wird zu 31, 8 wird zu 17:

Entschlüsselung der Nachricht

Zur Entschlüsselung der Nachricht wird die gleiche Methode wie bei der Verschlüsselung angewandt, jedoch mit dem privaten Schlüssel d = 7 und N = 33. Dabei werden die verschlüsselten Werte (b) hoch d genommen und der Rest bei Division durch N ermittelt:

Es ist wichtig zu beachten, dass nur die Reste dieser Divisionen relevant sind. Die Reste 4 und 8 entsprechen den ursprünglichen Nachrichten.

Einschränkungen

Das hier beschriebene RSA-Verfahren wird auch als „Textbook-RSA“ bezeichnet. In dieser vereinfachten Form ist es jedoch nicht ausreichend sicher für den praktischen Einsatz. Ein wesentlicher Nachteil besteht darin, dass bei dieser Methode jede Klartextzahl stets in dieselbe Geheimtextzahl umgewandelt wird. Zudem bleibt die Zahl 0 im Klartext immer 0 im Geheimtext (da 0^x = 0), und die Zahl 1 bleibt ebenfalls unverändert (1^x = 1).

Diese Eigenschaften können es Angreifern ermöglichen, bei bekannten Teilen der Klartext- und Geheimtext-Daten relativ schnell mögliche Klartext-Kombinationen zu identifizieren. Dadurch besteht die Gefahr, dass der restliche Klartext durch Raten erschlossen werden könnte.

Final-Koordinaten

Du hast einen verschlüsselten Text sowie den öffentlichen Schlüssel, mit welchem der Text verschlüsselt wurde. Um die ursprüngliche Nachricht zu rekonstruieren, sind folgende Schritte erforderlich:

1. Den öffentlichen Schlüssel (bestehend aus N und e) zu knacken, um den geheimen Schlüssel (d) zu ermitteln.
2. Die verschlüsselte Nachricht mithilfe des privaten Schlüssels (d) zu entschlüsseln (wobei Leerzeichen = 0, A = 1, B = 2, ...) .

N = 943 und e = 503
[717] [1] [873] [904] [0] [1] [0] [700] [565] [834] [904] [0] [515] [1] [578]

Hier kannst Du Deine Lösung überprüfen: