Ein Problem zum Verständnis des RSA-Verfahrens

09.03.2009, 17:11

exoskelett

Ein Problem zum Verständnis des RSA-Verfahrens

Hallo,

ich hoffe, das ist hier der richtige Bereich für eine solche Frage.

Ich habe mich in den letzten Tagen tiefer mit der RSA-Verschlüsselung auseinandergesetzt, weil es einer meiner Schwerpunkte in meiner Facharbeit werden soll. Nun bin ich kurz davor, den Beweis des Verfahrens zu verstehen. Es hapert nur an einer Stelle. Ich hoffe, ihr könnt mir helfen:

Man geht im Beweis davon aus, dass der Satz von Euler gilt.
Hier ist mein Problem:

Voraussetzung für den Satz ist doch, dass die beiden Zahlen teilerfremd sind (in unserem Fall der Verschlüsselung also die zu verschlüsselnde Zahl x und das Produkt unserer Primzahlen N). N = p*q, wenn jedoch eine der beiden Primzahlen auch Teiler von x ist, dann wären die beiden Zahlen doch gar nicht mehr teilerfremd, oder?

Aber trotzdem funktioniert das ganze, ich hab es mit einigen Beispielen ausprobiert.

Ich hoffe, ihr versteht mein Problem xD

Danke schonmal!

Exo

27.10.2009, 08:58

Mystic

Auf diesen Beitrag antworten »

Bin durch Zufall auf diesen Thread gestoßen, der mehr als ein halbes Jahr alt ist und auf den erstaunlicherweise damals niemand geantwortet hat...

Dabei ist die hier angeschnittenene Frage nur zu berechtigt, da es hier immer wieder zu unglaublichen Fehlinterpretationen kommt... Einen besonders spektakulären Fall dieser Art kann man z.B. in diesem Video sehen (man muss dazu im Archiv auf den letzten Vortrag der Serie über Primzahlen gehen), wo der Vortragende RSA am Beispiel n=11*13 vorführen möchte und genau dem hier angesprochenen Trugschluss aufsitzt...

Tatsächlich braucht man den Satz von Euler-Fermat beim Beweis, dass RSA funktioniert, in einer etwas anderen Form, nämlich dass

$\begin{eqnarray*} a^{\varphi(n)+1} \equiv a \mod n \quad (*) \end{eqnarray*}$

für alle $\begin{eqnarray*} a \in \mathbb Z \end{eqnarray*}$ gilt, die mit n keinen Primfaktor p mit $\begin{eqnarray*} p^2 \mid n \end{eqnarray*}$ gemeinsam haben. (Profis würden hier überhaupt $\begin{eqnarray*} \lambda(n) \end{eqnarray*}$ statt $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ nehmen, wo $\begin{eqnarray*} \lambda(n) \end{eqnarray*}$ die Carmichaelfunktion bedeutet, aber das ist wieder ein anderes Thema!)... Im Fall von RSA is n überhaupt quadratfrei, womit (*) dann tatsächlich für alle ganzen Zahlen a gilt...

10.03.2015, 16:45

Neo19

Auf diesen Beitrag antworten »

Hallo,
ich stehe vor demselben Problem.

Zitat:

Original von Mystic
Tatsächlich braucht man den Satz von Euler-Fermat beim Beweis, dass RSA funktioniert, in einer etwas anderen Form, nämlich dass

$\begin{eqnarray*} a^{\varphi(n)+1} \equiv a \mod n \quad (*) \end{eqnarray*}$

für alle $\begin{eqnarray*} a \in \mathbb Z \end{eqnarray*}$ gilt, die mit n keinen Primfaktor p mit $\begin{eqnarray*} p^2 \mid n \end{eqnarray*}$ gemeinsam haben.

Kann das jemand erklären? Also die unterschiedlichen Bedingungen von a und n bei $\begin{eqnarray*} a^{\varphi(n)} \equiv 1 \mod n \end{eqnarray*}$ und $\begin{eqnarray*} a^{\varphi(n)+1} \equiv a \mod n \end{eqnarray*}$ .

Das bedeutet doch, daß ich auch x=p und x=q korrekt ver- und entschlüsseln kann? und auch alle x>=n, oder?

Neue Frage »

Antworten »

Ein Problem zum Verständnis des RSA-Verfahrens

Verwandte Themen