(Twitter)
0
Wollte n schreiben
─
astroboy187
07.01.2023 um 23:25
Du hast mir damit sehr geholfen. Ich habe noch eine Frage und zwar kann ich dann mit a^ϕ(n) mod n = 1 einfach, dort wo (m^φ(N) mod N)^k steht, es damit ersetzen oder? Dabei handelt es sich um den RSA-Beweis. Vielen Dank im Voraus.
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 Euler-Fermat
= 1 • m mod N
= m => wegen m < N ─ astroboy187 07.01.2023 um 23:39
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 Euler-Fermat
= 1 • m mod N
= m => wegen m < N ─ astroboy187 07.01.2023 um 23:39
Ich habe vergessen zu erwähnen, dass vorausgesetzt wird, dass m und N teilerfremd sind. Somit kann ich es doch ersetzen durch die Gleichung: a^ϕ(n) mod n = 1, sodass (1^k mod N) ensteht.
─
astroboy187
08.01.2023 um 00:07