Matroids Matheplanet Forum Index
Moderiert von Florian
Informatik » Kryptologie » RSA-Verfahren
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule RSA-Verfahren
Dina123
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 18.09.2020
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-18


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 :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2005
Mitteilungen: 3650
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-19


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dina123
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 18.09.2020
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-09-19


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




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2005
Mitteilungen: 3650
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-09-19


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dina123
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 18.09.2020
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-09-19



Hier in diesem link
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.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2005
Mitteilungen: 3650
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-09-19


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dina123
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 18.09.2020
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-09-19




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...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2005
Mitteilungen: 3650
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-09-19


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dina123 hat die Antworten auf ihre/seine Frage gesehen.
Dina123 wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]