Beweis des RSA-Verfahrens |
28.12.2022, 21:53 | Delta121 | Auf diesen Beitrag antworten » |
Beweis des RSA-Verfahrens Hallo zusammen. Ich brauche eure Hilfe bei dem Beweis des RSA-Verfahren. Uns zwar ist mein Problem, dass ich nicht genau verstehe warum beim letzten Schritt das mod n wegfällt, bei m < N. Ich hatte gedacht, da ich auf der einen Seite schon mod n habe fliegt es auf der anderen Seite raus, aber irgendwie bezweifel ich das, dass die Erklärung ist. Kann mir jemand weiter helfen. Vielen Dank im voraus. Falls es nicht aus dem Aufschrieb erkennbar ist, hier ist der Link wo es besser erkennbar ist:https://www.scai.fraunhofer.de/content/d...thek/Mathematik für die Praxis/rsa_skript_und_arbeitsblaetter.pdf Ist auf Seite 14 und 15 zufinden. Dieser komischer smile soll die eulerische Phi-Funktion sein. Meine Ideen: Formel: m = c^d mod N (1) mit ihrem privaten Schlüssel. Um RSA zu verstehen, müssen wir nichts anderes tun als diese Gleichung (1) mathematisch zu beweisen. 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. Hiermt 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 laut, 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 |
||
28.12.2022, 22:33 | URL | Auf diesen Beitrag antworten » |
RE: Hilfe bei dem Beweis des RSA-Verfahren Bedenke, dass es sich um Division mit Rest handelt. 3 dividiert durch 7 ergibt Rest 3 |
||
29.12.2022, 22:07 | Delta121 | Auf diesen Beitrag antworten » |
RE: Hilfe bei dem Beweis des RSA-Verfahren Das weiß ich ja. Mir geht es darum, wie er von: = 1 * m mod N, auf = m => wegen m < N kommt , dass verstehe ich nicht. Kann einer von euch mir, da weiter Helfen. |
||
30.12.2022, 10:10 | URL | Auf diesen Beitrag antworten » |
RE: Hilfe bei dem Beweis des RSA-Verfahren Dann weißt du es, hast es aber nicht verstanden. Also nochmal: m mod N ist der Rest bei Division von m durch N. Nehmen wir mal m=3, N=7. Was ist dann m mod N? |
||
30.12.2022, 17:06 | Delta121 | Auf diesen Beitrag antworten » |
RE: Hilfe bei dem Beweis des RSA-Verfahren Ich habs jetzt verstanden. Daran das man definiert, dass m < N ist, wird wenn man durch N teilt immer m rausbekommen. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|