Antworte auf:  RSA-Verfahren von Dina123
Forum:  Kryptologie, moderiert von: Florian

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3688
Herkunft: Raun
 Beitrag No.7, eingetragen 2020-09-19 14:54    [Diesen Beitrag zitieren]

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.


Dina123
Neu
Dabei seit: 18.09.2020
Mitteilungen: 4
Herkunft:
 Beitrag No.6, eingetragen 2020-09-19 14:16    [Diesen Beitrag zitieren]



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: 3688
Herkunft: Raun
 Beitrag No.5, eingetragen 2020-09-19 14:09    [Diesen Beitrag zitieren]

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
Herkunft:
 Beitrag No.4, eingetragen 2020-09-19 14:01    [Diesen Beitrag zitieren]


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: 3688
Herkunft: Raun
 Beitrag No.3, eingetragen 2020-09-19 13:54    [Diesen Beitrag zitieren]

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
Herkunft:
 Beitrag No.2, eingetragen 2020-09-19 13:38    [Diesen Beitrag zitieren]

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: 3688
Herkunft: Raun
 Beitrag No.1, eingetragen 2020-09-19 07:20    [Diesen Beitrag zitieren]

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
Herkunft:
 Themenstart: 2020-09-18 23:48    [Diesen Beitrag zitieren]

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


 
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]