RSA-Verfahren, warum existiert immer ein solches d?

16.03.2013, 01:19

Duude

RSA-Verfahren, warum existiert immer ein solches d?

Hallo,
ich beschäftige mich gerade mit dem RSA-Verfahren und habe an einer Stelle Verständnisschwierigkeiten.

Wir wählen p, q Primzahlen und berechnen n=pq. Ferner wählen wir ein $\begin{eqnarray*} 1<e< \varphi(n) \end{eqnarray*}$ . mit $\begin{eqnarray*} ggT(e, \varphi(n))=1 \end{eqnarray*}$ .
Für $\begin{eqnarray*} x \in \mathbb{Z}/n \mathbb{Z} \end{eqnarray*}$ berechnen wir nun $\begin{eqnarray*} x^e \end{eqnarray*}$ .

Nach Voraussetzung existiert dann ein $\begin{eqnarray*} d \in \mathbb{N} \end{eqnarray*}$ mit de= 1 (modulo) $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ und für $\begin{eqnarray*} y=x^e \end{eqnarray*}$ gilt dann $\begin{eqnarray*} y^d=x^{de}=x (mod n) \end{eqnarray*}$ .

Aber warum existiert immer ein solches d? Ich würde verstehen, dass immer ein solches d existiert, wenn wir uns in einem Körper befinden würden (z.B. in $\begin{eqnarray*} \mathbb{Z}/p \mathbb{Z} \end{eqnarray*}$ mit p prim, denn dann hat ja jedes Element ein Inverses. Aber wir rechnen hier modulo $\begin{eqnarray*} \varphi (n) \end{eqnarray*}$ , was nicht unbedingt eine Primzahl sein muss.. Also warum gilt das?

noch zur Ergänzung: n und e sind der öffentliche Schlüssel. d wird vom Empfänger geheim gehalten (bzw. aus $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ berechnet, um den Code wieder entschlüsseln zu können.

Würde mich über Hilfe freuen.

lg duude

16.03.2013, 01:59

RavenOnJ

Auf diesen Beitrag antworten »

Da $\begin{eqnarray*} \operatorname{ggT}(e,\phi(n))=1 \end{eqnarray*}$ , gehört $\begin{eqnarray*} e \end{eqnarray*}$ zur Einheitengruppe $\begin{eqnarray*} \mathbb Z^*_{\phi(n)} \end{eqnarray*}$ von $\begin{eqnarray*} \mathbb Z_{\phi(n)} \end{eqnarray*}$ , d.h. es existiert ein $\begin{eqnarray*} d \end{eqnarray*}$ mit $\begin{eqnarray*} de=1 \!\!\!\mod \phi(n) \end{eqnarray*}$ .

16.03.2013, 17:01

Duude

Auf diesen Beitrag antworten »

Hallo RavenOnJ

erstmal danke für die Antwort. Der zweite Teil ist klar. Den ersten kann ich aber nicht direkt nachvollziehen:

Zitat:

Mal ein Beispiel:
ggT(3,7)=1, also gehört 3 zur Einheitengruppe in $\begin{eqnarray*} \mathbb{Z}/7\mathbb{Z} \end{eqnarray*}$
Dies ist tatsächlich so, denn 3*5=15=1 (modulo 7)

Aber woher weiß ich, dass diese allgemein Aussage gilt? Kann man das einfach so sehen/verstehen, oder steckt da ein komplizierter Beweis dahinter?

16.03.2013, 17:27

RavenOnJ

Auf diesen Beitrag antworten »

Wenn $\begin{eqnarray*} \operatorname{ggT}(a,b) = 1 \end{eqnarray*}$ , dann folgt ganz allgemein, dass die Gleichung $\begin{eqnarray*} ax+by=1 \end{eqnarray*}$ ganzzahlige Lösungen für $\begin{eqnarray*} x,y \end{eqnarray*}$ hat. In deinem Fall soll gelten $\begin{eqnarray*} \operatorname{ggT}(e,\phi(n)) = 1 \end{eqnarray*}$ . Es gibt also ganzzahlige Lösungen für die Gleichung $\begin{eqnarray*} ex+\phi(n)y=1 \end{eqnarray*}$ . Diese Gleichung kann man auch schreiben als

$\begin{eqnarray*} ex = 1 \!\!\!\mod \phi(n) \end{eqnarray*}$ ,

für die es also eine ganzzahlige Lösung $\begin{eqnarray*} 0 < x < \phi(n) \end{eqnarray*}$ gibt. Zur Einheitengruppe von $\begin{eqnarray*} \mathbb Z_{\phi(n)} \end{eqnarray*}$ gehören alle Zahlen, die zu $\begin{eqnarray*} \phi(n) \end{eqnarray*}$ teilerfremd sind, für die also $\begin{eqnarray*} \operatorname{ggT}(e,\phi(n)) = 1 \end{eqnarray*}$ gilt. Ist $\begin{eqnarray*} \phi(n) \end{eqnarray*}$ prim, dann gehören dazu alle Zahlen aus $\begin{eqnarray*} \mathbb Z_{\phi(n)}\setminus\{0\} \end{eqnarray*}$ . Das ist natürlich für n prim und größer 2 nicht der Fall, da ja

$\begin{eqnarray*} \phi(n) = n-1\Leftrightarrow n\small\text{ prim} \end{eqnarray*}$

gilt und $\begin{eqnarray*} 2\mid n -1, \forall n>2,n\small\text{ ungerade} \end{eqnarray*}$ .

17.03.2013, 12:23

Duude

Auf diesen Beitrag antworten »

Aah, jetzt versteh ich das. Irgendwie war ich überhaupt nicht auf die diophantischen Gleichungen und deren Lösbarkeit gekommen, da ich mich so in meine anderen Überlegungen verrannt hatte...

Es gibt immer ein solches d (bei dir ist das das x), weil $\begin{eqnarray*} ggT(e, \varphi(n))=1 \end{eqnarray*}$ und der daraus von dir beschriebenen Folgerungen.

Vielen Dank für die tolle Hilfe smile

Duude

17.03.2013, 12:27

RavenOnJ

Auf diesen Beitrag antworten »

Bitte sehr, gern geschehen. Wink

Neue Frage »

Antworten »

RSA-Verfahren, warum existiert immer ein solches d?

Verwandte Themen