RSA, Satz von Euler

17.04.2012, 20:20

Philipp Imhof

RSA, Satz von Euler

Hallo allerseits

Bei uns im Kurs wird zuerst der Satz von Euler eingeführt, danach der kleine Fermat, der dann gleich als Spezialfall vom Satz von Euler bewiesen wird. Als drittes kommt dann noch eine Verallgemeinerung des kleinen Fermats, nämlich dass für zwei unterschiedliche Primzahlen p,q und eine Zahl $\begin{eqnarray*} c\equiv1\pmod{pq} \end{eqnarray*}$ gilt: $\begin{eqnarray*} a^c\equiv a\pmod{pq} \end{eqnarray*}$ für alle natürlichen Zahlen a.

Später wird RSA erklärt und bei der Begründung, warum die Entschlüsselung funktioniert, wird nun diese Verallgemeinerung angeführt. Ich frage mich, warum das so gemacht wird. Diese Verallgemeinerung wird später im ganzen Kurs nicht mehr verwendet. Und für RSA würde es meiner Meinung nach reichen, den Satz von Euler anzugeben. Denn seien n der RSA-Modul, e der öffentliche und d der private Schlüssel, sodass $\begin{eqnarray*} ed\equiv1\pmod{\varphi(n)} \end{eqnarray*}$ gilt. Dann gilt doch für ein passendes k
$\begin{eqnarray*} x^{ed}=x^{k\varphi(n)+1}=(\underbrace{x^{\varphi(n)}}_{\equiv1})^k\cdot x\equiv x\pmod n \end{eqnarray*}$

Sehe ich das falsch?

Danke & Gruss

EDIT: Ich sehe grad, dass meine Variante voraussetzt, dass x und n teilerfremd sein müssen. Mit dem Umweg über die Verallgemeinerung des kleinen Fermat fällt diese Einschränkung weg.

17.04.2012, 20:26

Mystic

Auf diesen Beitrag antworten »

RE: RSA, Satz von Euler

Zitat:

Original von Philipp Imhof
Bei uns im Kurs wird zuerst der Satz von Euler eingeführt, danach der kleine Fermat, der dann gleich als Spezialfall vom Satz von Euler bewiesen wird. Als drittes kommt dann noch eine Verallgemeinerung des kleinen Fermats, nämlich dass für zwei unterschiedliche Primzahlen p,q und eine Zahl $\begin{eqnarray*} c\equiv1\pmod{pq} \end{eqnarray*}$ gilt: $\begin{eqnarray*} a^c\equiv a\pmod{pq} \end{eqnarray*}$ für alle natürlichen Zahlen a.

Richtig ist

$\begin{eqnarray*} c \equiv 1 \mod kgV(p-1,q-1) \Rightarrow a^c\equiv a\pmod{pq} \end{eqnarray*}$

Dein Modul pq ist also komplett falsch, manchmal sieht man (leider!) an dieser Stelle (p-1)(q-1)...

Zitat:

Original von Philipp Imhof
Dann gilt doch für ein passendes k
$\begin{eqnarray*} x^{ed}=x^{k\varphi(n)+1}=(\underbrace{x^{\varphi(n)}}_{\equiv1})^k\cdot x\equiv x\pmod n \end{eqnarray*}$

Sehe ich das falsch?

Ja, denn deine Unterklammerung gilt ja nur, wenn x weder durch p, noch durch q teilbar ist...

17.04.2012, 20:50

Philipp Imhof

Auf diesen Beitrag antworten »

RE: RSA, Satz von Euler
Ja, ich hatte mich da verschrieben. Im Skript steht natürlich
$\begin{eqnarray*} c\equiv 1\pmod{\varphi(pq)} \end{eqnarray*}$

Danke

17.04.2012, 21:40

Mystic

Auf diesen Beitrag antworten »

RE: RSA, Satz von Euler

Zitat:

Original von Philipp Imhof
Ja, ich hatte mich da verschrieben. Im Skript steht natürlich
$\begin{eqnarray*} c\equiv 1\pmod{\varphi(pq)} \end{eqnarray*}$

Danke

Wie gesagt, $\begin{eqnarray*} \lambda(n)=kgV(p-1,q-1) \end{eqnarray*}$ wäre genauer... Wie in diesem Thread an einem Beispiel näher ausgeführt wurde, kann es sonst bei kleinen Zahlen p und q und spezieller Wahl von e zu bösen Überraschungen kommen... Big Laugh

Neue Frage »

Antworten »

RSA, Satz von Euler

Verwandte Themen