Potenzieren modulo, Kongruenzen, RSA

11.12.2014, 21:20

Shalec

Potenzieren modulo, Kongruenzen, RSA

Hallo allerseits,

ich bin gerade an folgender Aufgabe

Seien $\begin{eqnarray*} p,q \end{eqnarray*}$ verschiedene, ungerade Primzahlen, $\begin{eqnarray*} p\cdot q=n,e\in\mathbb{N},\ m\in \{0,1,...,n-1\} \end{eqnarray*}$ mit $\begin{eqnarray*} 1<e<\varphi(n) \end{eqnarray*}$ teilerfremd zu $\begin{eqnarray*} \varphi(n)=(p-1)(q-1) \end{eqnarray*}$ .

Behauptung: $\begin{eqnarray*} \exists k\in\mathbb{N}\ :\ m^{(e^k)} \equiv m (mod\ n)* \end{eqnarray*}$

Ich bin mir sicher, dass der Beweis sehr einfach ist. Mir sind nur nicht die notwendigen Grundlagen klar. (ist 3 Jahre her, seit meinem letzten Zahlentheoriekurs)

Ich hatte mir gedacht, dass ich über den Satz von Euler argumentieren könnte und nur zeigen muss, dass ein k existiert, sodass $\begin{eqnarray*} e^k = h\cdot \varphi(n)+1 \end{eqnarray*}$ für ein $\begin{eqnarray*} h\in\mathbb{Z} \end{eqnarray*}$ .

Um die Aufgabe zu lösen:
Könnte mir jemand die Grundlagen sagen, die ich wissen sollte? (Schlagwörter genügen)
(Ich erinnere mich noch an Ausschnitte, im Detail aber an nichts weiter. )

(Für $\begin{eqnarray*} k=0 \end{eqnarray*}$ folgt die Behauptung bereits. Ich weiß aber nicht, wie der Dozent die natürlichen Zahlen definiert. Sinnvollerweise gehe ich mal von $\begin{eqnarray*} k>0 \end{eqnarray*}$ aus.)

Vielen Dank und viele Grüße

Edit:
bei $\begin{eqnarray*} *: m^{(ek)} \to m^{(e^k)} \end{eqnarray*}$

11.12.2014, 21:50

URL

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA
$\begin{eqnarray*} e \end{eqnarray*}$ ist teilerfremd zu $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ , es gibt also $\begin{eqnarray*} d \end{eqnarray*}$ mit $\begin{eqnarray*} de\equiv 1 \bmod \varphi(n) \end{eqnarray*}$ .
Jetzt muss man nur noch zeigen, dass damit $\begin{eqnarray*} m^{ed}\equiv 1 \bmod n \end{eqnarray*}$ ist und da hilft der kleine Fermat.

12.12.2014, 16:23

Shalec

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA

Zitat:

Original von URL
$\begin{eqnarray*} e \end{eqnarray*}$ ist teilerfremd zu $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ , es gibt also $\begin{eqnarray*} d \end{eqnarray*}$ mit $\begin{eqnarray*} de\equiv 1 \bmod \varphi(n) \end{eqnarray*}$ .
Jetzt muss man nur noch zeigen, dass damit $\begin{eqnarray*} m^{ed}\equiv 1 \bmod n \end{eqnarray*}$ ist und da hilft der kleine Fermat.

Danke erstmal, aber wie kann ich daraus die Existenz eines $\begin{eqnarray*} k\in\mathbb{N} \end{eqnarray*}$ folgern, sodass dann $\begin{eqnarray*} d=e^{k-1} \end{eqnarray*}$ gilt?
Die Aufgabe sieht ja direkt vor, die Existenz eines solchen k's zu bestimmen, sodass $\begin{eqnarray*} m^{(e^k)} \equiv m (mod\ n) \end{eqnarray*}$ gilt.

Ach...ich sehe gerade den Tippfehler.. das "^" wurde nicht getippt.. ich korrigiere eben. Auf meine vorherige Anfrage ist dies dann ja korrekt. ^^'

12.12.2014, 16:27

URL

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA
Pardon, statt $\begin{eqnarray*} m^{ed}\equiv 1 \bmod n \end{eqnarray*}$
muss es natürlich heißen $\begin{eqnarray*} m^{ed}\equiv m \bmod n \end{eqnarray*}$ .
Das d ist dein gesuchtes k, ich habe nur die übliche Notation (d für decrypt) beibehalten.

12.12.2014, 16:48

Shalec

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA

Zitat:

Original von URL
Das d ist dein gesuchtes k, ich habe nur die übliche Notation (d für decrypt) beibehalten.

Das hatte ich schon nachvollzogen :-)
Ich hatte mich aber auch in der Aufgabe vertippt. Es sollte eine Potenz von e gefunden werden, sodass auf m abgebildet wird.

12.12.2014, 17:09

URL

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA
Reicht es dafür nicht, dass $\begin{eqnarray*} e^k \equiv 1 \bmod \varphi(n) \end{eqnarray*}$ ist?

12.12.2014, 17:31

Shalec

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA

Zitat:

Original von URL
Reicht es dafür nicht, dass $\begin{eqnarray*} e^k \equiv 1 \bmod \varphi(n) \end{eqnarray*}$ ist?

Das habe ich gerade nachgelesen. Nach einer Folgerung aus dem Satz von Euler (bis jetzt unbekannt gewesen ^^') gilt:

$\begin{eqnarray*} m^{(e^k)} \equiv m^{h\cdot \varphi(n) +1} \equiv m (mod\ n)<br /> \Leftrightarrow e^k \equiv 1\ (mod\ \varphi(n))<br /> \end{eqnarray*}$

auf die letzte Zeile dann einfach den Satz von Euler erneut anwenden. Die Voraussetzungen sind ja gegeben, da e teilerfremd zu $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ . Dann ist doch $\begin{eqnarray*} k \equiv \varphi(\varphi(n))\in\mathbb{N} \end{eqnarray*}$

Muss jetzt leider los, lese aber später weiter.

12.12.2014, 17:33

URL

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA
k ist einfach die Ordnung von e.

12.12.2014, 19:22

Shalec

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA

Zitat:

Original von URL
k ist einfach die Ordnung von e.

Existiert denn in $\begin{eqnarray*} \mathbb{Z}/\varphi(n)\mathbb{Z} \end{eqnarray*}$ zu jedem e ein k? Was ist, wenn e^2=0? (D.h. Nullteiler, wie z.B. 2 in $\begin{eqnarray*} \mathbb{Z}_4 \end{eqnarray*}$ )

Ich kann mir irgendwie keinen sinnvollen Zusammenhang bzgl. der Ordnung von e und der Aufgaben herstellen. (Gerade bzgl. der Existenz zu jeden e eines öffentlichen Schlüssels (n,e))

Könntest du das bitte ein wenig mehr erläutern oder auf Texte verweisen, die das erklären?

Vielen Dank schonmal.

Edit: Mein Beispiel hinkt.. 2 ist ja nicht Teilerfremd zu 4.
Offenbar ist hier eine wichtige Eigenschaft, warum gerade dann eine Ordnung existiert..

12.12.2014, 20:05

URL

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA
$\begin{eqnarray*} e \end{eqnarray*}$ ist teilerfremd zu $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ , also Element der endlichen Gruppe $\begin{eqnarray*} (\mathbb{Z}/\varphi(n)\mathbb{Z})^* \end{eqnarray*}$ .
Jedes Element $\begin{eqnarray*} a \end{eqnarray*}$ einer Gruppe $\begin{eqnarray*} G \end{eqnarray*}$ hat eine Ordnung. Im Fall einer endlichen Gruppe $\begin{eqnarray*} G \end{eqnarray*}$ ist sie auch auch endlich und die kleinste positive Zahl $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} a^k=1 \end{eqnarray*}$ .
Also hat auch $\begin{eqnarray*} e \end{eqnarray*}$ eine endliche Ordnung $\begin{eqnarray*} k \end{eqnarray*}$
Soweit klar?

12.12.2014, 20:17

Shalec

Auf diesen Beitrag antworten »

RE: Potenzieren modulo, Kongruenzen, RSA
Ah. Das in deinem ersten Satz wusste ich gar nicht. Dadurch ist auch dann der Rest klar. Danke.

Neue Frage »

Antworten »

Potenzieren modulo, Kongruenzen, RSA

Verwandte Themen