Folgerung aus chinesischem Restsatz für RSA

18.06.2018, 19:56

MatheN00bine

Folgerung aus chinesischem Restsatz für RSA

Hallo, ich beschäftige mich mit dem Beweis der Richtigkeit des RSA. Grundsätzlich habe ich den auch komplett verstanden, nur an einer Stelle habe ich ein Problem.
In meinem Buch steht:
"Nun benutzen wir eine einfache Folgerung des chinesischen Restsatzes, die aussagt, dass für Primzahlen p und q gilt:
$\begin{eqnarray*} x \equiv a \bmod p \wedge x \equiv a \bmod q \Leftrightarrow x \equiv \bmod pq \end{eqnarray*}$

Diese Folgerung haben wir in der Vorlesung im Skript als eigenes Lemma früher gemacht als den Chinesischen Restsatz (und dementsprechend ohne ihn bewiesen) und der Chinesische Restsatz lautet:
Für alle $\begin{eqnarray*} m,n \in \mathbb{N}, m,n \ge 2 \text{ und } ggt(m,n)=1 \text{ und alle } a \in \mathbb{Z}_m , b \in \mathbb{Z}_n \end{eqnarray*}$ gibt es ein eindeutig bestimmtes $\begin{eqnarray*} t \in \mathbb{Z}_{mn} \end{eqnarray*}$ , so dass
$\begin{eqnarray*} t \equiv a \bmod m \text{ und } t \equiv b \bmod n \end{eqnarray*}$

Leider habe ich gar keine Ahnung wieso das aus dem chinesischen Restsatz folgert. Das oben genannte Lemma habe ich auch außer in unserem Skript nirgendwo explizit gefunden, nicht in "Mathematik für Informatiker" von Hartmann und auch nicht in "Diskrete Strukturen Band 1" von Steger. Idealerweise bräuchte ich eine Quelle, wo das Lemma explizit steht oder ich brauche Hilfe, es selbst zu folgern. Habe ein bisschen mit den Definitionen und Rechenregeln rumjongliert aber nix gefunden was brauchbar war.

18.06.2018, 20:11

HAL 9000

Auf diesen Beitrag antworten »

Zunächst mal muss noch $\begin{eqnarray*} p\neq q \end{eqnarray*}$ gefordert werden, sonst stimmt die Aussage nicht!

Dies berücksichtigend ist der Beweis ist doch sehr einfach: Die Rückrichtung ist eh klar.

Zur Hinrichtung: $\begin{eqnarray*} x\equiv a\bmod p \end{eqnarray*}$ ist gleichbedeutend mit $\begin{eqnarray*} p\mid (x-a) \end{eqnarray*}$ , entsprechend auch $\begin{eqnarray*} x\equiv a\bmod q \end{eqnarray*}$ gleichbedeutend mit $\begin{eqnarray*} q\mid (x-a) \end{eqnarray*}$ . Dass daraus nun auch $\begin{eqnarray*} pq \mid (x-a) \end{eqnarray*}$ folgt, kann man nun entweder mit der dicken Keule (Existenz und Eindeutigkeit der Primfaktorzerlegung von $\begin{eqnarray*} x-a \end{eqnarray*}$ ) oder mit einem einfacheren Teilbarkeitslemma begründen - weiß nicht, was ihr da alles so hattet.

18.06.2018, 20:22

MatheN00bine

Auf diesen Beitrag antworten »

den Beweis für das Lemma habe ich. Ich sehe nur keinerlei Zusammenhang zwischen diesem Lemma und dem chinesischen Restsatz. Aber der ist ja laut Literatur vorhanden.

Mein Problem ist eigentlich, dass ich den RSA in einer schriftlichen Arbeit beweise. Das ist kein Problem. Nur diese eine Stelle ist ein Problem, denn die Literatur sagt "das folgt aus dem chinesischen Restsatz". Ich sehe aber nicht wieso es daraus folgt. Und ich schreibe nichts in meine Arbeit was ich nicht verstehe. Ich brauche also den direkten Zusammenhang zwischen diesen Dingen.

Ich könnte natürlich auch das Lemma benutzen aber ich glaube es ist keine gute Idee, aus dem Skript zu zitieren, also wäre eine alternative, dass ich das Lemma selbst irgendwo finde in der Literatur, dann darf ich es benutzen. Habe es aber nirgendwo gefunden... daher die Frage mit dem Restsatz.

18.06.2018, 20:33

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MatheN00bine
den Beweis für das Lemma habe ich.

Dann war diese Aussage hier Verarsche:

Zitat:

Original von MatheN00bine
Das oben genannte Lemma habe ich auch außer in unserem Skript nirgendwo explizit gefunden, nicht in "Mathematik für Informatiker" von Hartmann und auch nicht in "Diskrete Strukturen Band 1" von Steger. Idealerweise bräuchte ich eine Quelle, wo das Lemma explizit steht oder ich brauche Hilfe, es selbst zu folgern.

18.06.2018, 20:43

MatheN00bine

Auf diesen Beitrag antworten »

Entschuldigung, ich meinte "es selbst aus dem chinesischen Restsatz zu folgern"

18.06.2018, 20:52

HAL 9000

Auf diesen Beitrag antworten »

Gewisse Aspekte mögen aus dem Chinesischen Restsatz folgerbar sein. Das heißt aber nicht, dass man das Gehirn für andere logische Argumente ausschalten muss. unglücklich

Wähle $\begin{eqnarray*} m=p,n=q,a=b \end{eqnarray*}$ für den chinesischen Restsatz, dann sagt der, dass es genau ein $\begin{eqnarray*} c\in \mathbb{Z}_{mn} \end{eqnarray*}$ mit $\begin{eqnarray*} x\equiv c\bmod pq \end{eqnarray*}$ gibt.

Da andererseits $\begin{eqnarray*} x\equiv a\bmod pq \end{eqnarray*}$ die Gültigkeit von $\begin{eqnarray*} x\equiv a\bmod p \end{eqnarray*}$ und $\begin{eqnarray*} x\equiv a\bmod q \end{eqnarray*}$ nach sich zieht, kann für dieses eindeutige $\begin{eqnarray*} c \end{eqnarray*}$ nur $\begin{eqnarray*} c=a \end{eqnarray*}$ gelten.

Neue Frage »

Antworten »

Folgerung aus chinesischem Restsatz für RSA

Verwandte Themen