Probleme bei RSA-Kryptographie |
| 24.03.2006, 14:58 | Bebbo | Auf diesen Beitrag antworten » | ||
| Probleme bei RSA-Kryptographie Ich bin jetzt an einem Punkt wo ich am RSA-Algorithmus verzweifelt bin.... Ich beschreibe mal kurz wie man dabei allgemein vorgeht, mit meinem Problembeispiel... Schlüsselerzeugung Wähle zwei Primzahlen p und q. Beipsiel: p = 421; q = 211 Bestimmte n = p * q Beispiel: n = 421 * 211 = = 88831 Wähle eine kleine ungerade natürliche Zahl e, die zu phi(n) teilerfremd ist(Das phi() soll hier die Eulersche phi-Funktion darstellen). Beispiel: e = 17 Berechne d als Lösung der Gleichung e*d mod phi(n) = 1 durch den EEA. (d ist also das modulare Inverse zu e mod phi(n). Beispiel: Dummerweise weiß ich nicht wieso, aber ich erhalte für d jetzt den Wert 20753. Vorher hatte ich für d den Wert 3113 heraus... phi(n) ist hierbei 88200. e und n soll nun der öffentliche Schlüssel sein. d und n ist der geheime Schlüssel. Verschlüsslung c = m^e mod n m... zu verschlüsselnde Zahl c... verschlüsselte Zahl für m Beispiel: c = 15^17 mod 88831 = 70460 Entschlüsslung m = c^e mod n m... ursprüngliche Zahl c... verschlüsselte Zahl für m Beispiel: Obwohl (3113*17) mod 88200 != 1, klappt die entschlüsslung trotzdem für jedes m, wenn ich für d diese 3113 einsetze: m = 70460^3113 mod 88831 = 15 Aber wieso klappt das für dieses d, obwohl es nicht invers zu 17 mod 88831 ist? ....und nochetwas... Angeblich sei d und n ja der geheime Schlüssel. Aber wieso soll ich den nicht rausbekommen, wenn ich e und n als öffentlichen Schlüssel kenne? Ich brauch doch dazu nur d als Inverse zu e mod phi(n) berechnen. Irgendwo müssen da denkfehler von mir drin sein, aber ich bin zu verzweifelt als dass ich da noch durchblicke.... Ich hoffe ihr könnt mir helfen. Danke. |
||||
| 24.03.2006, 15:34 | quarague | Auf diesen Beitrag antworten » | ||
deine zweite Frage kann ich beantworten n hat zwei Primfaktoren, sagen wir p und q. Dann ist phi(n)=phi(o)*phi(q)=(p-1)(q-1) und das brauchst du, um e zu berechnen. Aber dafür brauchst du eben die beiden Primfaktoren p und q und die zu bekommen ist das Schwierige. Wenn du sie einmal hast kann man e algorithmisch relativ leicht berechnen. zu der ersten Frage würde ich sagen: Zufall? hast du mal versucht andere Werte als 15 zu verschlüsseln? |
||||
| 24.03.2006, 16:02 | Bebbo | Auf diesen Beitrag antworten » | ||
Ich glaube, ich habs jetzt auch verstanden. Man kann ja wenn man nur n hat, auch phi(n) bestimmen und damit auch e. Aber es wäre ja wesentlich leichter, wenn man p und q kennt. Doch ich denke die eigendliche Sicherheit von RSA basier darauf, phi(n) zu bestimmen, ohne das man p und q kennt. Man müsste ja dann jede teilerfremde zahl ermitteln und das wäre bei relativ großen Werten für n eine Schwierigkeit. Liege ich mit dem Gedanken richtig? Dann hätte sich das zweite geklärt. Ich hab das mit d auch für die Zahl 2 probiert und es klappt auch. Vorher hatte ich d auch mithilfe des EEA berechnet, aber ich weiß nicht mehr welche zahlen ich genommen habe. Vielleicht hast du recht und es ist zufall, dann hätte sich das auch eklärt. Kennt ihr ein Rechenprogramm mit dem man äußerst große Zahlen darstellen kann(größere als mit dem windows-standart-rechner)? |
||||
| 24.03.2006, 20:21 | AD | Auf diesen Beitrag antworten » | ||
Die Erklärung ist ganz einfach, aber ich habe auch eine Weile gebraucht: Für alle zu 88831=211*421 teilerfremden Zahlen gilt nach Fermat sowohl als auch . Aus letzterem folgt durch Quadrieren auch . Beides zusammen ergibt nach chinesischem Restsatz . Das heißt also, die Ordnung aller solcher innerhalb der primen Restklassengruppe ist ein Teiler von 420, das ist natürlich viel drastischer als nur Teiler von . Schließlich erhält man woraus dein Effekt sofort folgt. Summa summarum: Deine gewählten Primfaktoren 211 und 421 sind über 421=2*211-1 verbandelt, was zu dem beschriebenen Effekt führte. P.S.: d=173 statt d=3113 hätte es auch getan. 
|
||||
| 25.03.2006, 02:03 | 20_Cent | Auf diesen Beitrag antworten » | ||
Guck mal ins Software Forum, es gibt einige Programme, die kostenpflichtig sind, aber auch einiges an Freeware... Stichworte: Derive, Maple, Mathematica, Mupad, Matlab, usw... (hoffentlich ohne rechtschreibfehler). mfG 20 |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
