ich halte in Mathematik ein Referat über Verschlüsselung. Und soll zeigen warum Primzahlen denn für die RSA verschlüsselung so wichtig sind. Wenn ich unseren Mathematik Lehrer richtig verstanden habe, dann meinte er auch, dass RSA nur mit Primzahlen funktioniert.
Ich bitte euch keinen Link und wenn nur gute zu posten, denn ich habe wirklich schon sehr viele Seiten, egal ob Wiki, Uni-Seiten oder sonstige Informatik bezogene Seiten durch, bin aber noch nicht auf die 100%ige Lösung gestoßen.
Es wäre super, wenn mir jemand von euch einen Tipp oder Anhaltspunkt nennen kann.
Meine Idee wäre, dass es mit der Euklidischen-Phi-Funktion zusammenhängt. Da man die Teilerfremden Zahlen dann ja wahrscheinlich nicht mehr so leicht berechnen kann. Sicherlich hängt es auch damit zusammen, dass noch keine effiziente Methode zur Primfaktorenzerlegung gefunden wurde. Ich denke allerdings, dass es da noch mehr gibt.
Für jeden Teilnehmer werden zwei große Primzahlen generiert (p, q) deren Produkt (n) und die Zahl z [(p-1)*(q-1)]. Man wählt nun eine natürliche Zahl, die Teilerfremd zu z ist aus (e) und berechnet nun d wie folgt:
ed mod z = 1 -> also ed = 1+ k (q-1)(p-1) für k Element der natürlichen Zahlen
Nun bilden e und n den öffentlichen Schlüssel und d den privaten.
Das zum Verfahren…
Warum nimmt man Primzahlen?
Ich bin da jetzt auch nicht der beste drin, aber ich erkläre es mal so weit wie ich es verstanden habe. Man nimmt Primzahlen, da man, wenn man nun auf den privaten Schlüssel versucht zu kommen, eine primfaktorzerlegung vornehmen muss. Das ist bei solch großen Zahlen sehr sehr rechenintensiv und auch zeitaufwendig. Das ist wahrscheinlich nicht der einzige Grund, aber der einzige, den ich kenne.
Hoffe mal dass das geholfen hat.
Weshalb es Primzahlen sein müssen, kann ich dir nicht sagen. Es liegt wohl daran, dass man einen Restklassenring braucht, damit das Verfahren funktioniert. Und Primzahlen haben gewisse Eigenschaften, sodass man mit der Bildungsvorschrift für N einen Restklassenring erzeugen kann.
Die Primzahlen haben also nicht direkt etwas mit der Sicherheit der Verschlüsselung zu tun (da gingen ja auch Carmichael-Zahlen, siehe obiger Link). Die Sicherheit hängt mit dem Faktorisierungsproblem zusammen.
*** Edit ***
P. S.: um auf meine Ausgangsaussage zurückzukommen (wie man drauf kommt, das in der Schule zu verlangen): es macht keinen Sinn, sich mit diesem Thema zu beschäftigen, wenn man keine fundierten Kenntnisse in Algebra (wer dazu Vorlesungen gehört hat, weiß, dass das nicht das ist, was man sich landläufig darunter vorstellt) hat. Das ist definitiv kein Schulstoff.
Soweit ich weiss müssen das Primzahlen sein, weil Zahlen die keine Primzahlen sind haben Teiler, daher kann man dann die kleinen Teiler rausfinden und die paar Kombinationen dann ausprobieren (wenn zum beispiel die 56 eine deiner Zahlen ist dann findest du beim suchen der primzahlen sehr viel schneller die 7 und 8)
Erstmal danke für die Antworten, wenn sich noch jemand damit auskennt, bin für jede Hilfe offen.
[QUOTE=cmrudolph]
P. S.: um auf meine Ausgangsaussage zurückzukommen (wie man drauf kommt, das in der Schule zu verlangen): es macht keinen Sinn, sich mit diesem Thema zu beschäftigen, wenn man keine fundierten Kenntnisse in Algebra (wer dazu Vorlesungen gehört hat, weiß, dass das nicht das ist, was man sich landläufig darunter vorstellt) hat. Das ist definitiv kein Schulstoff.[/QUOTE]
Ja da hast du Recht, die Schuld muss ich aber mir selbst zuschieben. Ich konnte das Thema “relativ” frei Wählen, es musste nur irgendwas mit Mathe sein.
Mein Anfangsgedanke war dabei auch nur die Unterschiede von der symmetrischen, asymmetrisches und hybriden Verschlüsselung aufzuzeigen. Doch dann meinte unser Lehrer ich sollte dann aber schon auch die Mathematik mit reinbringen. Und er meinte ich sollte aufzeigen warum Primzahlen in der Verschlüsselung so wichtig sind.
Meiner Erinnerung nach sind Primzahlen deshalb so bedeutend, weil man mit ihnen sehr leicht Restklassenringe (und auch Körper) bilden kann. Die haben nur eine endliche Anzahl Elemente, sind also dazu geeignet, um Bit-Blöcke darin abzubilden. Wenn man im Restklassenring dann ein bisschen durch die Gegend multipliziert oder potenziert, kommt etwas heraus, was man nicht so leicht vorhersagen kann, wenn man den Ring und / oder die Faktoren bzw. Exponenten nicht kennt.
Ggf. wird es auch noch ein bisschen weniger vorhersagbar, wenn man eine Primzahl zum Erzeugen des Ringes verwendet.
Die sorge die bei RSA besteht, sind Quantencomputer. Auf diesen kann man den shor-algorithmus effizient laufen lassen. Dieser kann grosse Zahlen sehr effizient Faktorisieren, wofür es sonst immer langer laufzeiten bedarf.
Für jeden Teilnehmer werden zwei große Primzahlen generiert (p, q) deren Produkt (n) und die Zahl z [(p-1)*(q-1)]. Man wählt nun eine natürliche Zahl, die Teilerfremd zu z ist aus (e) und berechnet nun d wie folgt:
ed mod z = 1 -> also ed = 1+ k (q-1)(p-1) für k Element der natürlichen Zahlen
Nun bilden e und n den öffentlichen Schlüssel und d den privaten.
Das zum Verfahren…
Warum nimmt man Primzahlen?[/QUOTE]
Weil sonst p und q nicht eindeutig wären. Wenn man p = 4 und q = 15 wählt, hat man n = p*q = 60. Das gleiche Ergebnis hätte man aber auch mit p = 6 und q = 10. Die Berechnung mit z funktioniert dann auch nicht, denn z muss der Wert von phi(n) sein, für den obige Formel nur zutrifft, wenn p und q prim sind.
Zur Faktorisierung wurde hier ja nun schon einiges gesagt. Ich möchte nur noch ergänzend auf die RSA Factoring Challenge verweisen, wo die Komplexität einer solchen Faktorisierung deutlich werden dürfte. Für große Zahlen hat eine solche Primfaktorzerlegung mehr als 10(!) Jahre gedauert. Nach so langer Zeit dürften die meisten Informationen, die man verschlüsselt hat, unwichtig geworden sein.
Ich hatte zu diesem Thema auch einmal einen Vortrag gehalten (ebenfalls in der Schule ;)) und mir damals dazu das Buch Geheime Botschaften von Simon Singh durchgelesen. Sehr empfehlenswert, auch, wenn ich annehme, dass deine Zeit bis zum Vortrag dafür nicht mehr ausreichen wird. Vieles wird anschaulich erklärt und in einen historischen Zusammenhang gesetzt, wie z.B. die Hinrichtung von Maria Stuart oder die Entschlüsselung der Enigma.
Hab gerade mal meine alten Vortragsstichpunkte durchgeblättert und ich hatte mir damals unter anderem aufgeschrieben, dass für eine sichere RSA-Verschlüsselung N > 10^308 sein sollte. Davon sind die oben ausgeschriebenen Zahlen noch ein Stückchen entfernt.
Das ist aber egal, weil p und q nur Generatoren sind. p, q und [tex]\varphi(N)[/tex] werden nach der Schlüsselerzeugung verworfen und werden nicht mehr benötigt.
Edit: bzgl. der Primzahlproblematik und deren Erforderlichkeit verweise ich nochmal auf die Carmichael-Zahlen. Die Primalität ist keine notwendige Eigenschaft!
Ich möchte euch allen für eure Lösungen danken. Der Grund warum man Primzahlen bzw. Carmichael-Zahlen verwendet liegt glaub ich im öffentlichen Schlüssel, ja immernoch glauben, hab noch keine Bestätigung. Die Begründung hat wohl was mit dem kleinen Satz von Fermat zu tun. Dieses Video zeigt das glaub ich sehr gut. http://www.youtube.com/watch?v=M7kEpw1tn50 Sollte jemand eine andere Meinung haben, bin noch immer für fast alles offen
Soweit ich das überblicke, erschwert die Verwendung von Primzahlen nur die Faktorisierung des Moduls N. Hat man N korrekt faktorisiert bekommt man daraus relativ schnell phi(n) und über das Inverse mit e genau so schnell d. Das wichtigste scheint also phi(n) zu sein, welches bei Primzahlen außer 2 ( also p und q ungerade) stets durch 4 teilbar ist. Was ist wohl schneller? Von einem oberen Grenzwert (N - (N % 4)) per Bruteforce immer 4 abziehen (schnellere Verfahren kann man ja noch entwickeln) oder N faktorisieren?
Mir ist übrigens klar, dass es beim Abziehen viel mehr Möglichkeiten als eim Faktorisieren gibt, aber man spart sich zumindest schon mal die dauernde Berechnung der nächsten Primzahl.
Mich würde nun noch interessieren, was der Lehrer dazu sagt, weshalb die Primzahlen wichtig sind. Ich habe meinen Tipp oben ja bereits abgegeben und glaube noch immer, dass der Hauptgrund in der Generatoreigenschaft liegt. Vielleicht hat ja auch jemand Lust sich durch Vorlesungsunterlagen oder wissenschaftliche Papers zu arbeiten.
