0 Daumen
92 Aufrufe

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

1 Antwort
2 Antworten
Gefragt 21 Dez 2022 von Bombe
0 Antworten
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community