RSA knacken?
Hallo, zunächst einmal habe ich folgendes Rätsel gefunden: https://www.mathe.online/rsa-challenge
Da ich mich noch nie mit dem RSA Algorithmus beschäftigt habe, frage ich mich gerade, wie er unterschiedliche Schlüssel mit dem selben Text erzeugt? Erfüllt dann jeder von denen die selbe Funktion? Und wie zeigt er damit wie schlecht der Zufallsgenerator ist?
2 Antworten
Jeder Teilnehmer hat zwei Schlüssel: den Schlüssel C zum Kodieren und den Schlüssel D zum Dekodieren.
Den Schlüssel D hält jeder Teilnehmer geheim. Den Schlüssel C macht jeder Teilnehmer öffentlich zugänglich.
Möchte Teilnehmer A eine Nachricht an Teilnehmer B versenden, greift A auf den öffentlichen Schlüssel von B zu und verschlüsselt damit seine Nachricht an B.
Nur B kann mit seinem geheimen Schlüssel D diesen Text wieder entschlüsseln.
Kommt ein neuer Teilnehmer hinzu, wird wieder ein neuer Schlüssel C öffentlich gemacht. Alle anderen Teilnehmer können dann sofort mit dem neuen Teilnehmer kommunizieren, da ein Schlüsseltausch wie bei symmetrischen Verfahren nicht erforderlich ist.
In der Challenge ist also folgendes abgelaufen. Ein Text wurde mit einem öffentlichen Schlüssel C (eines fiktiven Teilnehmers) verschlüsselt und nun soll der dazu passende private Schlüssel D ermittelt werden. Dieser private Schlüssel D befände sich normalerweise nur in der Hand des fiktiven Teilnehmers.
Als Hilfestellung hat der Autor weitere fünf öffentliche Schlüssel des fiktiven Teilnehmers C1,...,C5 generiert und veröffentlicht. Scheinbar soll aus der Schlüsselstruktur das Verfahren zur Bestimmung der Primzahlen herauszufinden sein. Eben dieses Verfahren würde ja der fiktive Teilnehmer zur Erstellung der eigenen beiden Schlüssel nutzen.
Für jeden neuen öffentlichen Schlüssel sähe der codierte Text anders aus. Das ist richtig. Aber darum geht es nicht. Erstellt der fiktive Teilnehmer die beiden Schlüssel C und D, werden über einen Zufallsgenerator zwei Primzahlen generiert. Ist dieser Generator schlecht, könnte er z.B. bei jedem Lauf direkt aufeinander folgende Primzahlen ausgeben. Einfaches Beispiel (nicht für RSA geeignet) : eine Teilfolge der Primzahlen lautet 13,17,19,23,29,31,37. Wählt der Generator beim ersten mal die 13 und die 17, geht das Produkt 13*17 = 221 in den ersten Schlüssel ein. Nimmt der Generator beim nächsten mal die 19 und die 23, geht das Produkt 19*23= 437 in den zweiten Schlüssel usw. Aus der Differenz der beiden Produkte kann man eventuell solche Muster erkennen und die beiden Primzahlen leichter bestimmen.
Das ist mit schon klar, aber ich verstehe gerade nicht wie man beim selben Text den man verschlüsselt unterschiedliche Schlüssel bekommt?
Zuerst braucht man den Schlüssel, erst dann kann man einen Text kodieren. Mit den zusätzlichen 5 Schlüsseln wurde der Text nicht neu kodiert, sondern Du sollst aus den 5 Schlüsseln gewisse Gesetzmässigkeiten des Schlüsselgenerators herausfinden.
In guten Implementierungen wird ein Device genommen, das echte Zufallszahlen generiert durch die Erzeugung und Messung von Rauschen.
Jetzt stell Dir mal das andere Extrem vor, nämlich Pseudozufallszahlen. Das sind Zahlen, die sich für die meisten Zwecke zufällig "anfühlen", d.h. statistische Eigenschaften haben, die wahrem Zufall entsprechen. Tatsächlich sind sie aber feste Folgen und mit dem gleichen Anfangswert wird man immer die gleiche Zahlenfolge bekommen.
D.h. man muss nicht mehr alle 2^1024 Möglichkeiten durchprobieren, um Schlüssel zu finden, sondern vielleicht nur die Menge der Anfangswerte des Zufallszahlengenerators, beispielswiese 2^64.
Ebenso ist es denkbar, dass der Zufallszahlengenerator bestimmte Eigenschaften hat, die die Zufälligkeit einschränken, so dass ein Teil der Möglichkeiten ausfallen oder sehr unwahrscheinlich werden. Die müssen dann bei einem Angriff nicht mehr betrachtet werden.
Danke für die ausführliche Antwort, aber müsste der erzeugte Schlüssel nicht immer der selbe sein und weshalb schreibt er, dass man daran den schlechten Zufallsgenerator erkennt?