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.
