| |
| Autor |
 Hilfe bei der Erklärung des RSA-Beweises |
|
Alpha187
Junior 
Dabei seit: 07.01.2023
Mitteilungen: 7
 |  Themenstart: 2023-01-07
|
Hallo zusammen. Ich bin auf diesen Beweis von RSA gestoßen:
Für den Beweis benötigen wir den Satz von Euler-Fermat. Dieser sagt nämlich aus, dass für zwei natürliche teilerfremde Zahlen a und n, folgende Gleichung gilt: aφ(n) ≡ 1 mod n (aφ(n) mod n = 1 mod n). Dabei ist n: 1< a < n und φ(n) die Anzahl der zu n teilerfremden Zahlen. Hiermit folgt nun:
c^d mod N = (m^e mod N)^d mod N
= (m^e)^d mod N
= m^ed mod N
Das „e*d“ können wir ersetzten durch die Gleichung des multiplikativen Inversen. Diese lautet, da ein k aus den ganzen Zahlen existiert, folgendermaßen: e*d = k * φ(N) + 1.
Also folgt:
= m^k•φ(N)+1 mod N
= m^k•φ(N) • m mod N
= (m^φ(N))^k • m mod N
= ((m^φ(N))^k mod N) • (m mod N) mod N
= (m^φ(N) mod N)^k • (m mod N) mod N
= (1^k mod N) • (m mod N) mod N => wegen des Satzes von Euler-
Fermat (vorausgesetzt das m und N
teilerfremd zueinander sind)
= 1 • m mod N
= m => wegen m < N
und wollte fragen, ob dem Schritt = (m^φ(N))^k • m mod N auf = ((m^φ(N))^k mod N) • (m mod N) mod N, die Rechenregel von Multiplikation von der Modulo-Funktion angewendet wurde. Außerdem würde mich noch interessieren, warum der Satz von Euler-Fermat verwendbar ist, zu ersetzen von (m^φ(N) mod N). Vielen Dank für eine Rückmeldung.
|
 Profil
|
StrgAltEntf
Senior 
Dabei seit: 19.01.2013
Mitteilungen: 8203
Wohnort: Milchstraße
 | Beitrag No.1, eingetragen 2023-01-07
|
Hallo Alpha187,
das lässt sich alles wirklich sehr schwer entziffern. Ein paar Klammern solltest du ebenfalls spendieren.
\quoteon(2023-01-07 18:28 - Alpha187 im Themenstart)
Dieser sagt nämlich aus, dass für zwei natürliche teilerfremde Zahlen a und n, folgende Gleichung gilt: aφ(n) ≡ 1 mod n
\quoteoff
Das glaubst du doch wohl selbst nicht?!
|
Profil
|
Alpha187
Junior
Dabei seit: 07.01.2023
Mitteilungen: 7
| Beitrag No.2, vom Themenstarter, eingetragen 2023-01-07
|
Ich habe den Beweis wiedergefunden. Hier ist ein Bild davon: https://matheplanet.com/matheplanet/nuke/html/uploads/c/56084_AF284F9F-134F-4B58-95E6-7722412FDC21.png
|
Profil
|
| Alpha187 hat die Antworten auf ihre/seine Frage gesehen. | | Alpha187 wird per Mail über neue Antworten informiert. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
