Hallo, Ich habe am laut dieser Flash Animation RSA gelernt und wollte daher Fragen, wozu das Variable a oder bei anderen (komplizierteren) Anleitungen das Variable e gut ist. Was muss bei der Definierung dieses Variables beachtet werden, dass es sicher ist. Und bitte nicht zu Kompliziert Antworten. Ich bin erst 13.

Ich danke schon einmal im Vorhinein.:Thomas Zach

Nun, da ich leider nicht wirklich die Zeit habe mich durch die Flash-Animation zu klicken, hier die Erklärung anhand Wikipedia.

e ist ein Teil es öffentlichen Schlüssels und muss so gewählt werden, dass es Teilerfremd zur Eulerschen Funktion für das Produkt der beiden gewählten Primzahlen ist. Das heißt das der GGT von e und dem Ergebnis von φ(p*q) = 1 sein muss.

Thomas131 schrieb:

Hallo, Ich habe am laut dieser Flash Animation RSA gelernt und wollte daher Fragen, wozu das Variable a oder bei anderen (komplizierteren) Anleitungen das Variable e gut ist.

Verschlüsselung basiert meistens auf mathematischen „Einwegproblemen”. Das sind Probleme, die in eine Richtung sehr leicht zu berechnen sind, in die andere Richtung aber sehr schwer bzw. gar nicht lösbar sind. Ein Beispiel dafür ist die Modulo-Operation, also das Teilen mit Rest.

Stell dir eine Division vor: 6 / 3 = 2, wenn ich dir 3 und 2 gebe, kannst du sehr schnell auf 6 kommen. Das ist eine einfache Rechnung die umkehrbar ist.

Stelle dir hingegen eine Modulo-Operation vor und ich gebe dir den Divisor 3 und den Rest 2. Von welcher Zahl bin ich ausgegangen? Es könnte 14 mod 3 = 2 sein, oder vielleicht auch 17 mod 3 = 2 … es gibt beliebig viele Möglichkeiten für x mod 3 = 2. Um das korrekte x zu bestimmen kann man nur raten und eins nach dem anderen durchprobieren. (x = 3·k + 2 für alle natürlichen Zahlen k)

Ein weiteres schwer lösbares Problem ist die Primfaktorzerlegung. Jede Zahl lässt sich in Primzahlen zerlegen. 35 zum Beispiel lässt sich durch zwei Primzahlen darstellen: 35 = 5 · 7. In diesem Fall ist es noch einfach, aber für sehr große Primzahlen mit ~500 Stellen und mehr wird das extrem schwierig.

Genau das sind die zwei Probleme, die sich RSA zu nutze macht.

Zuerst wird der Schlüssel erzeugt.

1. N: Man wählt zwei große Primzahlen p und q und berechnet damit N = p · q

2. φ(N):Man berechnet außerdem φ(N) = (p-1) · (q-1)

3. e: Man wählt einen Exponenten e, der nicht größer sein darf als φ(N) und außerdem zu φ(N) teilerfremd sein muss.

4. d: Zuletzt berechnet man noch d als Inverse von e. Also man löst die Formel e·d + k·φ(N) = 1. Das ist der einzige wirklich komplizierte Schritt und ich kann ihn dir hier auch nicht einfacher erklären. Zur Berechnung dient der erweiterte Euklidische Algorithmus

5. Die vier Zahlen werden jetzt aufgeteilt:
   N und e sind der öffentliche Schlüssel, den jeder kennen darf
   φ(N) und d stellen unseren privaten Schlüssel dar und müssen geheim bleiben.

Hier haben wir schon eines der Probleme benutzt. N ist eine große Zahl, die aus zwei großen Primzahlen besteht. Diese kann man weitergeben, da wir darauf vertrauen, dass es einen Angreifer Jahre an Rechenzeit kosten würde, die beiden Primzahlen zu finden. Deshalb vertrauen wir auch darauf, dass ein Angreifer unser φ(N) nicht (oder jedenfalls nicht schnell) berechnen kann. Damit bleibt unser privater Schlüssel sicher.

Soll nun ein Klartext K verschlüsselt werden, dann berechnet der Absender einfach K^e mod N = C. Hier wird sozusagen das zweite schwere Problem benutzt. Aus dem Ergebnis der Modulo-Operation (C) ist auch bei Kenntnis von e und N nicht auf den Klartext K zu schließen. Man kann dieses C also auch wieder „veröffentlichen“ – das darf praktisch abgehört werden.

Und wie kommt der Empfänger nun an das K? Modulo-Operationen lassen sich doch nicht einfach umkehren? Doch, für den Besitzer des privaten Schlüssels ist das sehr leicht lösbar. Wir haben nämlich das d gerade so konstruiert, dass es die Modulo-Operation umkehren kann. Der Empfänger muss also lediglich C^d mod N = K berechnen.

Der ganze Trick liegt darin, dass die beiden Primzahlen und daraus folgend auch φ(N) geheim bleiben. Einem Angreifer ist es deshalb nicht möglich d zu berechnen und die Modulo-Operation umzukehren.

Was muss bei der Definierung dieses Variables beachtet werden, dass es sicher ist. Und bitte nicht zu Kompliziert Antworten. Ich bin erst 13.

Verschlüsselung ist ein kompliziertes Thema, da gibt es keine einfachen Antworten.

Wie ich weiter oben schon schrieb ist e einfach eine beliebig gewählte Zahl. Die einzigen wirklichen Voraussetzungen sind, dass e kleiner als φ(N) und darüber hinaus auch teilerfremd zu φ(N) sein muss. Man wählt hier auch häufig kleine Zahlen, weil es ein Exponent ist – würde man große Zahlen wählen, dann würden die Zwischenergebnisse (K^e) noch riesiger. Hier will man ein wenig Rechenzeit sparen. Zu klein darf die Zahl natürlich nicht werden. Wenn du da aber wirklich tiefer einsteigen willst, dann wird es mathematisch höchst komplex. Wikipedia sagt, ein Wert von 2¹⁶ + 1 = 65537 für e sei „üblich“.

~jug

Heist das jetzt, dass der Wert von e oder a sozosagen egal ist. Häufig wird halt 65537 verwendet.

m.f.G.:Thomas Zach

Thomas131 schrieb:

Heist das jetzt, dass der Wert von e oder a sozosagen egal ist.

Nein, egal ist er nicht. Aber seine Wahl kann relativ frei erfolgen, solange die genannten Bedingungen erfüllt sind.

Häufig wird halt 65537 verwendet.

Ja. Darauf solltest du dich aber nicht konzentrieren. Für das Verstehen von RSA ist das Konzept wichtig, nicht welche Zahlen tatsächlich benutzt werden. Hier gilt, wie in der Mathematik (überspitzt gesagt): „Formeln mit Buchstaben sind toll, Zahlen sind blöd”.

Hefeweiz3n schrieb:

Ja. Darauf solltest du dich aber nicht konzentrieren. Für das Verstehen von RSA ist das Konzept wichtig, nicht welche Zahlen tatsächlich benutzt werden. Hier gilt, wie in der Mathematik (überspitzt gesagt): „Formeln mit Buchstaben sind toll, Zahlen sind blöd”.

Daher habe ich ja auch die noch nicht so ganz gelöste Frage, wozu das Variable gut ist. Bei Privaten und Öffentlichen Schlüssel ist es mir klar. Aber bei dem Variable nicht ganz.

Thomas131 schrieb:

Daher habe ich ja auch die noch nicht so ganz gelöste Frage, wozu das Variable gut ist. Bei Privaten und Öffentlichen Schlüssel ist es mir klar. Aber bei dem Variable nicht ganz.

Deine Frage ist mir auch nicht ganz verständlich.

1. Die Variable e ist ein Teil des öffentlichen Schlüssels

2. Sie wird sowohl bei der Schlüsselerzeugung als auch beim Verschlüsseln verwendet, wo genau kannst du ja oben in den Formeln sehen.

Wenn deine Frage damit nicht beantwortet ist, dann versuche diese anders zu formulieren oder erkläre warum deine Frage damit nicht beantwortet ist.

~jug