Verschlüsselung 2 |
16.03.2011, 01:44 | tigerbine | Auf diesen Beitrag antworten » | ||
Verschlüsselung 2 Es ist N aus . Da p und q teilerfremd sind, gilt (*). Des weiteren weiß man . Nun zur Argumentation. Es ist wegen p und q prim . mit p prim hat die Ordnung (p-1). Für ein m mit gilt dann , also . Analog folgt und damit dann auch wegen (*). Stimmt das so? |
||||
16.03.2011, 02:30 | Bjoern1982 | Auf diesen Beitrag antworten » | ||
Sollte vielleicht nochmal ein etwas erfahrenerer User drüber schauen, aber ich finde es sehr gut nachvollziehbar. Würde nur das k noch etwas weiter mitschleppen und erst nach dem vierten Gleichheitszeichen wegfallen lassen. |
||||
16.03.2011, 02:32 | tigerbine | Auf diesen Beitrag antworten » | ||
Ups, hab ich gar nicht mehr nachgeschaut. , also |
||||
16.03.2011, 08:43 | Mystic | Auf diesen Beitrag antworten » | ||
Ich habe da eine gute und eine schlechte Nachricht für dich: 1. Die schlechte zuerst: Diese Argumentation ist total falsch. 2. Und nun die "gute", zumindestens für dich: Dieser Fehler ist so üblich, dass man ihn sogar in sehr vielen Lehrbüchern und vor allem auch in unzähligen Darstellungen zu RSA im Internet findet (z.B. auch im letzten Vortrag zum Thema "Primzahlen" im Archiv auf dieser Seite) Der Trugschluss bei dieser Argumentation besteht darin, dass eben nicht gilt, sondern nur das schwächere was aber hier auch vollkommen ausreicht... |
||||
16.03.2011, 23:32 | tigerbine | Auf diesen Beitrag antworten » | ||
Hallo Mystic, meinen Fehler, dass ich den Fall 0 (mod p) nicht beachtet habe, habe ich inzwischen gefunden. Mit einer Fallunterscheidung komme ich dann auch auf die Lösung. Allerdings kann ich noch nicht nachvollziehen, wie mir hier weiterhilft. Der zu betrachtende Exponent ist ja von der Gestalt: 1+k(p-1)(q-1). Danke für deine Hilfe. Grüße vom Lemming. |
||||
16.03.2011, 23:49 | Bjoern1982 | Auf diesen Beitrag antworten » | ||
Sorry wenn ich kurz etwas dazwischen poste (falls das stört können wir das auch am Ende klären wenn ihr fertig seid).
Nun ist aber doch m ein Element aus der primen Restklasse , welche ja schon davon ausgeht bzw so definiert ist, dass alle Elemente teilerfremd zu p sind. Oder missverstehe ich den Hinweis von Mystic ? |
||||
Anzeige | ||||
|
||||
16.03.2011, 23:56 | tigerbine | Auf diesen Beitrag antworten » | ||
Für m gilt einfach nur: Für ein m mit . Es könnte also auch m=0 sein.
Imho nein, es war gerade mein Fehler in zu denken anstatt in . Wenn du den Buchlink anklickst und das erste Verfahren anschaust, dort wurde genommen. Verschlüsselung 1 |
||||
17.03.2011, 00:08 | Bjoern1982 | Auf diesen Beitrag antworten » | ||
Ok, geklärt |
||||
17.03.2011, 10:36 | Mystic | Auf diesen Beitrag antworten » | ||
Ja, diese Fallunterunterscheidung sieht man in der Literatur leider auch immer wieder... Sie ist aber ebenso unelegant wie leicht vermeidbar... Sei dazu im Folgenden M die Menge der natürlichen Zahlen n für welche gilt Zu M gehören insbesondere die Primzahlen, aber auch unendlich viele zusammengesetzte Zahlen, die sog. Carmichaelzahlen... Der folgende Satz ist dann in gewisser Weise eine Verallgemeinerung des "Kleinen Fermatschen Satzes" und enthält genau das, was eigentlich hier gebraucht wird... Satz: Sei beliebig. Dann gilt Der Beweis erfolgt natürlich durch vollständige Induktion nach k. Der Fall k=0 ist dabei trivial und der Schluss ist ebenfalls nur ein Einzeiler: Insbesondere ergibt sich daraus die im Zusammenhang mit RSA wichtige Folgerung: Seien und ggT(p,q)=1, dann gilt Beim RSA sind dann natürlich p und q immer Primzahlen und die Teilerfremdheit ist schon dadurch garantiert, dass sie verschieden sind... Wie ferner aus der Folgerung noch hervorgeht, müssen der öffentliche Schlüssel e und der private Schlüssel d nur so gewählt werden, dass ist... Wenn man sich die obigen Ausführungen noch einmal aufmerksam durchliest und sieht wie selbst bei größtmöglicher Allgemeinheit alles noch sehr einfach (und insbesondere ohne Fallunterscheidungen!) abläuft, muss man sich nur einmal mehr wundern, wie unglaublich stümperhaft diese Dinge in der Literatur oft dargestellt werden... |
||||
17.03.2011, 14:03 | tigerbine | Auf diesen Beitrag antworten » | ||
Dankeschön. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|