Forum:  Kryptologie
Thema: RSA-Verfahren
Themen-Übersicht
Dina123
Neu
Dabei seit: 18.09.2020
Mitteilungen: 4
Aus:
Themenstart: 2020-09-18 23:48

Hallo,

Mich beschäftigt die ganze Zeit, warum im rsa-verfahren als Bedingung 1<e,d<phi(n) angenommen wird ?

(n=p*q, e öffentlicher exponent und d privater)

Ich bedanke mich im Voraus,

Liebe Grüße Dina :)


StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3708
Aus: Raun
Beitrag No.1, eingetragen 2020-09-19 07:20

Hallo Dina,
herzlich willkommen auf dem Matheplanet!

Größere \(e\) und \(d\) haben auf das Ergebnis keinen Einfluss, weil für beliebige natürliche Zahlen \(m\) aus dem Satz von Euler \(m^e=m^{e-\varphi(n)} \mod{n}\) folgt, ebenso bei \(d\). Es reicht aus, mit \(e\) und \(d\) kleiner \(\varphi(n)\) zu rechnen.

Viele Grüße,
  Stefan


Dina123
Neu
Dabei seit: 18.09.2020
Mitteilungen: 4
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2020-09-19 13:38

Hallo Stefan,

Vielen Dank für deine Antwort :)!


Ich hätte da noch eine weitere Frage. Der Korrekturbeweis bezieht sich ja auf ein x aus (Z_n)*, d.h. Ich kann den Satz von Euler anwenden und beweisen.

Jetzt gibt es aber noch den Fall: x ist nicht aus (Z_n)*

Hier habe ich mir folgendes überlegt:

Ich weiß dann, dass mein x nicht teilerfremd zu p bzw. q ist und dass mein x somit ein Vielfaches von q bzw. p ist. Jetzt habe ich im Internet gelesen,dass man den chinesischen restsatz verwendet und dann auf x^ed kongruent x mod n kommt. Ich verstehe aber nicht wie :(



2020-09-19 07:20 - StefanVogel in Beitrag No. 1 schreibt:
Hallo Dina,
herzlich willkommen auf dem Matheplanet!

Größere \(e\) und \(d\) haben auf das Ergebnis keinen Einfluss, weil für beliebige natürliche Zahlen \(m\) aus dem Satz von Euler \(m^e=m^{e-\varphi(n)} \mod{n}\) folgt, ebenso bei \(d\). Es reicht aus, mit \(e\) und \(d\) kleiner \(\varphi(n)\) zu rechnen.

Viele Grüße,
  Stefan



StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3708
Aus: Raun
Beitrag No.3, eingetragen 2020-09-19 13:54

Genau bis zu der Stelle, wo x ein Vielfaches von p oder q ist, bin ich auch gekommen. Dort habe ich paar Beispiele ausprobiert, und es hat gestimmt. Dass die Aussage stimmt, daran zweifle ich nicht, kenne aber auch den Beweis nicht. Weißt du die Internetstelle noch? Ansonsten müssen wir beide weitersuchen oder knobeln.


Dina123
Neu
Dabei seit: 18.09.2020
Mitteilungen: 4
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2020-09-19 14:01


Hier in diesem link events.ccc.de/sigint/2009/Fahrplan/attachments/1297_pesco09ascrypto.pdf
S.2 ff

:)

2020-09-19 13:54 - StefanVogel in Beitrag No. 3 schreibt:
Genau bis zu der Stelle, wo x ein Vielfaches von p oder q ist, bin ich auch gekommen. Dort habe ich paar Beispiele ausprobiert, und es hat gestimmt. Dass die Aussage stimmt, daran zweifle ich nicht, kenne aber auch den Beweis nicht. Weißt du die Internetstelle noch? Ansonsten müssen wir beide weitersuchen oder knobeln.



StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3708
Aus: Raun
Beitrag No.5, eingetragen 2020-09-19 14:09

Danke (ich habe mich bei der Suche in immerwiederkehrender Werbung verheddert) das sieht gut aus. Jetzt nochmal genau anschauen...


Dina123
Neu
Dabei seit: 18.09.2020
Mitteilungen: 4
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2020-09-19 14:16



Ich habe leider keine Ahnung :(


2020-09-19 14:09 - StefanVogel in Beitrag No. 5 schreibt:
Danke (ich habe mich bei der Suche in immerwiederkehrender Werbung verheddert) das sieht gut aus. Jetzt nochmal genau anschauen...


StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3708
Aus: Raun
Beitrag No.7, eingetragen 2020-09-19 14:54

2020-09-19 14:09 - StefanVogel in Beitrag No. 5 schreibt:
Jetzt nochmal genau anschauen...
Ja, das war auch für mich mit gemeint.

\(d\) wird so gewählt, dass \(ed = 1 \mod{\varphi(n)}\) erfüllt ist.

Dass stets so ein \(d\) existiert, ist dadurch garantiert, dass \(e\) teilerfremd zu \(\varphi(n)\) festgelegt wurde.

Nach Definition von \(\mod{}\) gilt \(ed = 1 \mod{\varphi(n)}\) genau dann, wenn ein \(k\) existiert, so dass \(ed = 1  + k \varphi(n)\) erfüllt ist.

Für \(n=pq\) mit primen \(p\) und \(q\) gilt \(\varphi(n)=\varphi(p)\varphi(q)\). Das muss auch irgendwo mal bewiesen werden, wird in dem .pdf aber als bekannt vorausgesetzt.

Beides zusammen ergibt \(ed = 1 + k \varphi(p) \varphi(q)\).

Das als Exponent zu einem beliebigen m verwendet ergibt \(m^{ed} = m^{1+k \varphi(p) \varphi(q)} = m \cdot m^{k \varphi(p) \varphi(q)}\). Ich habe jetzt wie im .pdf die Bezeichnung m verwendet anstelle von x.

Zitat Ende von Seite 1: "Und zwar gilt ... falls m teilerfremd zu p ist: \(m^{ed} = m \cdot \left(m^{k \varphi(q)}\right)^{\varphi(p)} = m \cdot 1 \mod{p}\)" Ende Zitat. Hier wird nur die zusätzliche runde Klammer eingefügt und weil das Innere dieser Klammer teilerfremd zu p ist, kann man den Satz von Euler für p anwenden, wonach \((\ldots)^{\varphi(p)} = 1 \mod{p}\) ist.

weiter Zitat Anfang Seite 2: "Diese Kongruenz gilt aber auch falls \(m\) nicht teilerfremd zu \(p\) ist: Dann ist \(m\) ein Vielfaches von \(p\) und beide Seiten kongruent 0." Ende Zitat.

Dann folgt noch gleiche Überlegung modulo \(q\) und Anwendung des Chinesischen Restsatzes, welcher auch in dem .pdf als bekannt vorausgesetzt wird.

Soweit mein Versuch das zu verstehen, vielleicht hilft es hier oder da etwas.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249471=5106
Druckdatum: 2020-11-29 23:38