0 Daumen
159 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:

cd mod N = (me mod N)d mod N
    = (me)d mod N
    = med 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:
    = mk•φ(N)+1 mod N
    = mk•φ(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
    = (1k 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

0 Daumen
1 Antwort
0 Daumen
2 Antworten
0 Daumen
0 Antworten