Verschlüsselung 2

16.03.2011, 01:44

tigerbine

Verschlüsselung 2

Nächste Frage kommt zum RSA-Verfahren. Hier geht es um den entscheidenden Punkt, dass gilt $\begin{eqnarray*} N^{ed}=N \end{eqnarray*}$

Es ist N aus $\begin{eqnarray*} Z_n=Z_{pq} \end{eqnarray*}$ . Da p und q teilerfremd sind, gilt $\begin{eqnarray*} Z_{pq} \cong Z_p \times Z_q \end{eqnarray*}$ (*). Des weiteren weiß man $\begin{eqnarray*} ed \equiv 1 \mod \varphi(pq) \end{eqnarray*}$ .

Nun zur Argumentation. Es ist wegen p und q prim $\begin{eqnarray*} \varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1) \end{eqnarray*}$ .

$\begin{eqnarray*} Z_p \end{eqnarray*}$ mit p prim hat die Ordnung (p-1). Für ein m mit $\begin{eqnarray*} 0 \leq m <n \end{eqnarray*}$ gilt dann

$\begin{eqnarray*} m^{ed} = m^{1+k(p-1)(q-1)} = m \cdot (m^{(p-1)})^{(q-1)} = m\cdot 1^{q-1}=m \end{eqnarray*}$ , also $\begin{eqnarray*} m^{ed} \equiv m \mod p \end{eqnarray*}$ .

Analog folgt $\begin{eqnarray*} m^{ed} \equiv m \mod q \end{eqnarray*}$ und damit dann auch $\begin{eqnarray*} m^{ed} \equiv m \mod pq \end{eqnarray*}$ wegen (*).

Stimmt das so?

16.03.2011, 02:30

Bjoern1982

Auf diesen Beitrag antworten »

Sollte vielleicht nochmal ein etwas erfahrenerer User drüber schauen, aber ich finde es sehr gut nachvollziehbar.
Würde nur das k noch etwas weiter mitschleppen und erst nach dem vierten Gleichheitszeichen wegfallen lassen.

16.03.2011, 02:32

tigerbine

Auf diesen Beitrag antworten »

Ups, hab ich gar nicht mehr nachgeschaut.

$\begin{eqnarray*} m^{ed} = m^{1+k(p-1)(q-1)} = m \cdot (m^{(p-1)})^{k(q-1)} = m\cdot 1^{k(q-1)}=m \end{eqnarray*}$ , also $\begin{eqnarray*} m^{ed} \equiv m \mod p \end{eqnarray*}$

16.03.2011, 08:43

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Ups, hab ich gar nicht mehr nachgeschaut.

$\begin{eqnarray*} m^{ed} = m^{1+k(p-1)(q-1)} = m \cdot (m^{(p-1)})^{k(q-1)} = m\cdot 1^{k(q-1)}=m \end{eqnarray*}$ , also $\begin{eqnarray*} m^{ed} \equiv m \mod p \end{eqnarray*}$

Ich habe da eine gute und eine schlechte Nachricht für dich:

1. Die schlechte zuerst: Diese Argumentation ist total falsch.
2. Und nun die "gute", zumindestens für dich: Dieser Fehler ist so üblich, dass man ihn sogar in sehr vielen Lehrbüchern und vor allem auch in unzähligen Darstellungen zu RSA im Internet findet (z.B. auch im letzten Vortrag zum Thema "Primzahlen" im Archiv auf dieser Seite)

Der Trugschluss bei dieser Argumentation besteht darin, dass eben nicht

$\begin{eqnarray*} \forall m \in \mathbb Z : m^{p-1} \equiv 1 \mod p \end{eqnarray*}$

gilt, sondern nur das schwächere

$\begin{eqnarray*} \forall m \in \mathbb Z : m^p \equiv m \mod p \end{eqnarray*}$

was aber hier auch vollkommen ausreicht...

16.03.2011, 23:32

tigerbine

Auf diesen Beitrag antworten »

Hallo Mystic,

meinen Fehler, dass ich den Fall 0 (mod p) nicht beachtet habe, habe ich inzwischen gefunden. Mit einer Fallunterscheidung komme ich dann auch auf die Lösung. Allerdings kann ich noch nicht nachvollziehen, wie mir

$\begin{eqnarray*} \forall m \in \mathbb Z : m^p \equiv m \mod p \end{eqnarray*}$

hier weiterhilft. Der zu betrachtende Exponent ist ja von der Gestalt: 1+k(p-1)(q-1). verwirrt

Danke für deine Hilfe. Grüße vom Lemming.

16.03.2011, 23:49

Bjoern1982

Auf diesen Beitrag antworten »

Sorry wenn ich kurz etwas dazwischen poste (falls das stört können wir das auch am Ende klären wenn ihr fertig seid).

Zitat:

Der Trugschluss bei dieser Argumentation besteht darin, dass eben nicht

$\begin{eqnarray*} \forall m \in \mathbb Z : m^{p-1} \equiv 1 \mod p \end{eqnarray*}$

Nun ist aber doch m ein Element aus der primen Restklasse $\begin{eqnarray*} Z_p \end{eqnarray*}$ , welche ja schon davon ausgeht bzw so definiert ist, dass alle Elemente teilerfremd zu p sind.
Oder missverstehe ich den Hinweis von Mystic ?

16.03.2011, 23:56

tigerbine

Auf diesen Beitrag antworten »

Für m gilt einfach nur: Für ein m mit $\begin{eqnarray*} 0 \leq m <n \end{eqnarray*}$ . Es könnte also auch m=0 sein.

Zitat:

Nun ist aber doch m ein Element aus der primen Restklasse $\begin{eqnarray*} Z_p \end{eqnarray*}$ , welche ja schon davon ausgeht bzw so definiert ist, dass alle Elemente teilerfremd zu p sind.

Imho nein, es war gerade mein Fehler in $\begin{eqnarray*} Z_p^{\times} \end{eqnarray*}$ zu denken anstatt in $\begin{eqnarray*} Z_p \end{eqnarray*}$ . Wenn du den Buchlink anklickst und das erste Verfahren anschaust, dort wurde $\begin{eqnarray*} Z_p^{\times} \end{eqnarray*}$ genommen. Verschlüsselung 1

17.03.2011, 00:08

Bjoern1982

Auf diesen Beitrag antworten »

Ok, geklärt Wink

17.03.2011, 10:36

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
meinen Fehler, dass ich den Fall 0 (mod p) nicht beachtet habe, habe ich inzwischen gefunden. Mit einer Fallunterscheidung komme ich dann auch auf die Lösung. Allerdings kann ich noch nicht nachvollziehen, wie mir

$\begin{eqnarray*} \forall m \in \mathbb Z : m^p \equiv m \mod p \end{eqnarray*}$

hier weiterhilft. Der zu betrachtende Exponent ist ja von der Gestalt: 1+k(p-1)(q-1). verwirrt

Ja, diese Fallunterunterscheidung sieht man in der Literatur leider auch immer wieder... Sie ist aber ebenso unelegant wie leicht vermeidbar... Sei dazu im Folgenden M die Menge der natürlichen Zahlen n für welche gilt

$\begin{eqnarray*} \forall a \in \mathbb Z: \ a^n \equiv a \mod n \end{eqnarray*}$

Zu M gehören insbesondere die Primzahlen, aber auch unendlich viele zusammengesetzte Zahlen, die sog. Carmichaelzahlen... Der folgende Satz ist dann in gewisser Weise eine Verallgemeinerung des "Kleinen Fermatschen Satzes" und enthält genau das, was eigentlich hier gebraucht wird...

Satz: Sei $\begin{eqnarray*} p \in M \end{eqnarray*}$ beliebig. Dann gilt

$\begin{eqnarray*} \forall k \in \mathbb N \ \forall a \in \mathbb Z : \ a^{1+k(p-1)} \equiv a \mod p \end{eqnarray*}$

Der Beweis erfolgt natürlich durch vollständige Induktion nach k. Der Fall k=0 ist dabei trivial und der Schluss $\begin{eqnarray*} k \rightarrow k+1 \end{eqnarray*}$ ist ebenfalls nur ein Einzeiler:

$\begin{eqnarray*} a^{1+(k+1)(p-1)} \equiv a^p a^{k(p-1)} \equiv a a^{k(p-1)} \equiv a^{1+k(p-1)} \equiv a \mod p \end{eqnarray*}$

Insbesondere ergibt sich daraus die im Zusammenhang mit RSA wichtige

Folgerung: Seien $\begin{eqnarray*} p,q \in M \end{eqnarray*}$ und ggT(p,q)=1, dann gilt $\begin{eqnarray*} \quad \forall k \in \mathbb N \ \forall a \in \mathbb Z: \ a^{1+k \ kgV(p-1,q-1)} \equiv a \mod pq \end{eqnarray*}$

Beim RSA sind dann natürlich p und q immer Primzahlen und die Teilerfremdheit ist schon dadurch garantiert, dass sie verschieden sind... Wie ferner aus der Folgerung noch hervorgeht, müssen der öffentliche Schlüssel e und der private Schlüssel d nur so gewählt werden, dass

$\begin{eqnarray*} de \equiv 1 \mod kgV(p-1,q-1) \end{eqnarray*}$

ist... Wenn man sich die obigen Ausführungen noch einmal aufmerksam durchliest und sieht wie selbst bei größtmöglicher Allgemeinheit alles noch sehr einfach (und insbesondere ohne Fallunterscheidungen!) abläuft, muss man sich nur einmal mehr wundern, wie unglaublich stümperhaft diese Dinge in der Literatur oft dargestellt werden... unglücklich

17.03.2011, 14:03

tigerbine

Auf diesen Beitrag antworten »

Dankeschön.

Neue Frage »

Antworten »

Verschlüsselung 2

Verwandte Themen