RSA private key d bestimmen |
| 06.04.2012, 20:05 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
| RSA private key d bestimmen ich habe leider wieder einmal ein Problem mit Mathe 
Ich muss eine Dokumentation + Präsentation über das RSA Verfahren bearbeiten. Jedoch komme ich an einer Stelle nicht weiter. Und zwar bei der Bestimmung von dem Private Key d. Dazu werden ja laut meinen Recherchen folgende Mittel benötigt: Euklidischer Algorithmus und erweiterer Euklidischer Algorithmus. Das Problem ist auch noch, dass ich das vor Schülern präsentieren muss und die das dann auch verstehen müssen. Nehmen wir mal ein Beispiel: p = 5 q = 11 e = 7 Euklidischer Algorithmus: 1) 40 = 5 * 7 + 5 2) 7 = 1 * 5 + 2 3) 5 = 2 * 2 + 1 4) 2 = 2 * 1 + 0 Der ggt ist also 1. Und jetzt soll ich irgendwie auf die Vielfachensummen-Darstellung kommen in der Form: 1 = _____ * 40 + _____ * 7 Ich habe also zwei Unbekannte, dazu brauch ich zwei Gleichungen, oder nicht? Ich hoffe ihr könnt mir weiter helfen. Vielen Dank im Voraus Mit freundlichen Grüßen mathelover |
||||||||||
| 06.04.2012, 20:24 | Mystic | Auf diesen Beitrag antworten » | ||||||||
RE: RSA private key d bestimmen
Du musst von der vorletzten Gleichung ausgehend solange rückwärts einsetzen, bis du eine derartige Darstellung gefunden hast... Ich mach nachfolgend für dich den Anfang: 1= 5 - 2*2=5-2*(7-5)=3*5-2*7 = ...
Nein, nicht wenn man irgendeine Lösung (von den unendlich vielen) sucht... |
||||||||||
| 06.04.2012, 20:45 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
| RE: RSA private key d bestimmen Vielen Dank zunächst für deine Antwort Mystic
Rückwärts betrachtet ergeben sich folgende Gleichungen: 1) 5 = 40-5*7 2) 2 = 7-1*5 3) 1 = 5-2*2 1= 5 - 2*2=5-2*(7-5)=3*5-2*7 = Du beginnst also mit der 3) 1 = 5 -2 * 2 //jetzt wird die letzte 2 mit Gleichung 2) erweitert -> 1 = 5 -2 * 7-5 //und jetzt müsste ich die letzte 5 mit Gleichung 1) erweitern? -> 1 = 5 -2 * 7- (40-5*7) // diese Gleichung ist aber nicht richtig Das habe ich aber unter rückwärts einsetzten verstanden... Ich hoffe du hast noch einen Tipp für mich. Gibt es denn keinen bestimmten Weg, an dem man sich halten kann. Ich finde nämlich dieses "Gesuche/Probiere" in der Mathematik richtig nervig... |
||||||||||
| 06.04.2012, 22:32 | Mystic | Auf diesen Beitrag antworten » | ||||||||
| RE: RSA private key d bestimmen Ja, es gibt schon einen bestimmten Weg, aber du musst dich auch auf diesem Weg bleiben, sonst wird das nichts... Z.B. hab ich nirgendwo von "erweitern" etwas gesagt, sondern...
Was du "einsetzen" sollst,sind dabei immer die Reste bei den Divisionen, nichts anderes, angefangen von der vorletzten Gleichung, also dann in deiner Nummerierung: 3) 5 = 2 * 2 + 1 => 1=5 - 2*2 2) 7 = 1 * 5 + 2 => 2 = 7 - 5 (in 3) für 2 einsetzen, wodurch man einen neue Gleichung 3' erhält, siehe mein voriges Posting) 1) 40 = 5 * 7 + 5 => 5 = 40 - 5*7 (in die neue Gleichung 3' für 5 einsetzen, was gewünschte Linearkombination von 40 und 7 dann liefert) Also rechne mir das bitte mal vor und ich sag dir dann, wie's weiter geht... |
||||||||||
| 07.04.2012, 00:09 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Vielen Dank Mystic, also nach meiner Berechnung kommt dann folgende Gleichung raus: 1 = 3 * ( 40-5*7 ) - 2*7 wobei ich nicht verstehe wie du auf 1 = 3 * 5 -2*7 gekommen bist. |
||||||||||
| 07.04.2012, 08:30 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Naja, es ist im Grunde genommen der gleiche Schritt, den du auch hier nicht gemacht hast: 1 = 3 * ( 40-5*7 ) - 2*7 =3*40 - 15*7 - 2*7=3*40 + (-17)*7 |
||||||||||
| Anzeige | ||||||||||
|
|
||||||||||
| 07.04.2012, 12:35 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Hmmmmm Ich verstehe nicht wie du von dieser Gleichung: 5-2*(7-5) auf diese Gleichung kommst: 3*5-2*7 Das habe ich jetzt verstanden : 1 = 3 * ( 40-5*7 ) - 2*7 =3*40 - 15*7 - 2*7=3*40 + (-17)*7 Aber das erste was ich genannt habe, verstehe ich immernoch nicht... Die für mich relevanten Zahlen sind ja, 3 und (-17), aber d ist immer >0 soweit ich weiß. 3 kann nicht mein d sein und -17 ist <0, was ist dann mein d? Könntest du mir bitte später noch ein paar Zahlen geben, die ich dir dann hier vorrechne? |
||||||||||
| 07.04.2012, 12:49 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Fällt dir die Umformung leichter? Wenn deine Antwort ja lautet, dann brauchst du darin nur x=5, y=7 zu setzen...
-17 ist also Lösung der Kongruenz ... Aber jede andere Zahl, die zu -17 mod 40 kongruent ist, doch genauso... Also such dir doch von diesen eine passende aus... 
|
||||||||||
| 07.04.2012, 13:32 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Hahahaha, man bin ich blöd 
Die Umformung war klasse! Danke dafür. -17 mod 40 ergibt 23, also ist 23 mein d und somit mein privater Schlüssel
Suuuuuuuuuuper danke für Mystic
bekomm ich jetzt noch zwei andere Zahlen bitte? |
||||||||||
| 07.04.2012, 13:49 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Ok, wenn du eine kleine Herausforderung willst, hier ist sie: p= 13, q=31, e=61 Was ist hier der private Schlüssel d?... |
||||||||||
| 07.04.2012, 17:28 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Der private Schlüssel d ist 6. Begründung: (p-1)*(q-1)=phi 12*30=phi 360=phi 61=e ->1) Euklidischer Algorithmus: 360 = 5 *61 +55 61 = 1*55 +5 55 = 11*5 +0 ggt(360,61) = 5 -> 2) Erweiterter Euklidischer Algorithmus: 5 = 61 - 1*55 = 1*61 - 1* (360 -5*61) = 1*61 - 1*360 +1* 5*61 = -1*360 + 1*6*61 Somit ist 6 unser private Key, nicht wahr? Aber auch 5, denn -1 mod 6 = 5 ergibt, oder? |
||||||||||
| 07.04.2012, 19:10 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Wäre er, wenn, ja wenn 1. 5 wirklich der ggT(360,61) wäre (dazu müsste er aber mindestens 61 teilen!) 2. Die Darstellung 5=-360+6*61 stimmen würde (tut sie aber nicht!)
Diesen Satz verstehe ich nun gar nicht... Sollte nicht ein Inverses von 61 mod 360 berechnet werden? Warum rechnest du hier plötzlich mod 6? 
|
||||||||||
| 07.04.2012, 19:29 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Tut mir leid, hab mich verrechnet 
->1) Euklidischer Algorithmus: 360 = 5 *61 +55 61 = 1*55 +6 6 = 1*6 +0 ggt(360,61) = 6 edit// wobei 6, 61 nicht teilt??? -> 2) Erweiterter Euklidischer Algorithmus: 6 = 61 - 1*55 = 1*61 - 1* (360 -5*61) = 1*61 - 1*360 +1* 5*61 = -1*360 + 1*6*61 Den letzten Satz hab ich auf diese Aussage bezogen:
Es sollte eigentlich -1 mod 360 lauten, gibt aber glaub ich auch keinen Sinn. |
||||||||||
| 07.04.2012, 19:36 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Dein ggT ist leider noch immer kein Teiler von 61, daher kann auch der Rest dann nicht stimmen!...
|
||||||||||
| 07.04.2012, 19:55 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
->1) Euklidischer Algorithmus: 360 = 5 *61 +55 61 = 1*55 +6 55 = 9* 6 +1 6 = 6*1 +0 ggt(360,61) = 1 -> 2) Erweiterter Euklidischer Algorithmus: 1 = 55 - 9*6 = 1*55 - 9* (61-1*55) = 1*55 - 9*61 + 9*55 = 10*55 - 9*61 = 10* (360 - 5*61) - 9*61 = 10*360 - 50*61 - 9*61 1 = 10*360 - 59*61 Der private Schlüssel d lautet somit -59 mod 360 = 301 Geht folgendes auch : -59 mod 61 = 2 ? |
||||||||||
| 07.04.2012, 20:07 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Ja, deine Rechnung war diesmal richtig... 
So wie RSA in der Literatur meist beschrieben wird, würde hier tatsächlich 301 herauskommen (deine andere Lösung -59 mod 61 =2 stimmt dagegen natürlich nicht!)...Aber ich verrate dir jetzt ein großes Geheimnis, das vermutlich nicht einmal dein Lehrer kennt... Es gibt noch einen kleineren privaten Schlüssel, nämlich d=1... Die Verschlüsselungsabbildung ist nämlich gar keine, sondern die identische Abbildung, d.h., das Chiffrat ist gleich dem Klartext... 
Du kannst das ja selbst an einigen Beispielen ausprobieren!
|
||||||||||
| 07.04.2012, 20:15 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Heißt das dann nicht, dass jeder Angreifer die Nachricht entziffern kann, da er den private key d=1 kennt?
Meinst du etwa, wenn C = M ist? |
||||||||||
| 07.04.2012, 20:28 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Ja, genau das sagte ich eben... Überprüf das mal an einem Beispiel, z.B. für die Nachricht m=2... Allerdings brauchst dafür ein CAS... |
||||||||||
| 08.04.2012, 14:35 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Ok danke, ich werde das bis heute Abend ausprobieren -zudem könnte ich das dann auch noch mit in die Präsentation einbringen, um den Lehrer zu überzeugen
- mache gerade das Geschichtliche meiner Dokumentation, dann folgt noch die Idee der Kryptologie und dann werd ich mich an deine Aufgabe machen
Bis später MfG mathelover |
||||||||||
| 08.04.2012, 14:43 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Ok, dann kann nur hoffen, dass du einen guten Mathe-Lehrer hast, der seinen eigenen 5 Sinnen mehr traut, als dem, was in den (meisten) Büchern über RSA steht...
|
||||||||||
| 08.04.2012, 14:48 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Haha, ich werde dir dann berichten, ob er dazu fähig war, seinen 5 Sinnen mehr zu trauen
|
||||||||||
| 12.04.2012, 15:29 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Welches p und q und e soll für dieses Beispiel verwenden? |
||||||||||
| 12.04.2012, 15:49 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Wie bitte?
Ich sehe ja ein, dass nach deinem letzten Posting eine kleine Pause verstrichen ist, warum auch immer, aber da ja hier alles dokumentiert ist, hättest ja dafür nur die letzten Postings zu lesen brauchen, z.B. dieses hier
|
||||||||||
| 12.04.2012, 16:56 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Kann es sein, dass man für alle M < N, den geheimen Schlüssel d=1 benutzen muss. Denn es gibt Fälle wie z.B. M=400, N=403, nach dem Verschlüsseln: -> c= 400 Entschlüsseln: ergibt dann plötzlich m=0 bei Verwendung von d = 301 aber bei Verwendung von d=1 gilt m=400. Wie lässt sich das erklären? |
||||||||||
| 12.04.2012, 17:55 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Und ich dachte, das hätten wir schon längst geklärt, dass sowohl die Verschlüsselung, als auch die Entschlüsselung hier die identische Abbildung sind...
Oder worüber ging es eigentlich hier?
|
||||||||||
| 12.04.2012, 19:08 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Ich glaube wir reden an uns vorbei. Mir geht es darum, dass mir bei dieser Beispielaufgabe mein zuvor errechneter privater Schlüssel d=301 überhaupt nichts bringt, denn für alle m < n ergibt sich c = m. Und da das m kleiner sein muss als das RSA MODUL n kann ich also den den errechneten privaten Schlüssel d=301 wegwerfen, da ich ja d=1 verwenden muss, denn Ver-und Entschlüsselung haben ja die identische Abbildung... Ich glaube ich habe einen großen Denkfehler, bitte helf mir Mystic...
|
||||||||||
| 12.04.2012, 20:00 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Also ausnahmsweise liegt die Schuld hier nicht bei dir, sondern in einer Art "Konstruktionsfehler" für das klassische RSA, der sich bei großen RSA-Moduln n mit einigen hundert Stellen praktisch nicht auswirkt, aber bei "kleinem" n, wie in unserem Beispiel, verheerende Auswirkungen haben kann... Sind nämlich p und q die beiden Primfaktoren des RSA-Moduls n, so sollte man e und d so wählen, dass gilt, d.h., ich habe überall das Produkt (p-1)(q-1) durch das kgV(p-1,q-1) ersetzt, das in unserem Fall 60 beträgt... Wir dürften also e=61, d=301 gar nicht wählen bzw. würden, wenn wir es dennoch tun, sofort merken, dass ja gilt, d.h., es wird de facto gar nicht verschlüsselt... |
||||||||||
| 12.04.2012, 20:16 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Alles klar vielen Dank Mystic
Gibt es eine mathematische Begründung, warum e teilerfremd zu phi(n) sein muss. Liegt die Begründung darin, dass man auf die Vielfachensummendarstellung kommen muss und diese eben mit ggT(e,phi)=1 beginnt? |
||||||||||
| 12.04.2012, 20:21 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Naja, egal ob man jetzt m= (p-1)(q-1) oder m=kgV(p-1,q-1) wählt, ist es ja prinzipiell so, dass die Kongruenz genau dann lösbar ist, wenn e zu m teilerfremd ist... Wenn e klein ist, z.B. e=3, muss man u.U. etwas herumprobieren, bevor man ein e findet, das zu m, d.h., also dann zu p-1 und zu q-1 teilerfremd ist, bei großem e ist das i.d.R. kein Problem... |
||||||||||
| 12.04.2012, 20:24 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Ich werde jetzt erstmal recherchieren was Kongruenz heißt, vielleicht verstehe ich dann deine Aussage
|
||||||||||
| 12.04.2012, 20:27 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Und ich dachte, wir reden schon die längste Zeit von Kongruenzen?...
Was genau irritiert dich daran plötzlich? Dass ich x statt d geschrieben habe, weil ja d hier gesucht ist? |
||||||||||
| 12.04.2012, 20:43 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Achso also ist mit x d gemeint. Darf ich dann eigentlich die Formel so umformen, dass folgende Formel entsteht: e*x mod m = 1 ? Dann würde ich nämlich sagen, dass e zu m teilerfremd sein muss, damit die obige Gleichung also = 1 rauskommen kann, denn teilerfremd heißt ja dass der ggT = 1 ist, und bei der Modulo Rechnung kommt eine 1 raus laut obiger Gleichung und somit ist ggT=1 damit erfüllt. Das wäre meine Begründung stimmt diese so? Danke für deine Hilfe Mystic
|
||||||||||
| 12.04.2012, 20:50 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Naja, die Begründung ist eigentlich die, dass man die Kungruenz auch als Gleichung für eine gewisse ganze Zahl y schreiben kann... Daraus sieht man sofort, das e und m teilerfremd sein müssen, da ja jeder gem. Teiler auch 1 teilen muss... Sind sie umgekehrt teilerfremd, so kann man mithilfe des Erweiterten Euklidischen Algorithmus die Zahlen x und y auch finden... |
||||||||||
| 12.04.2012, 20:54 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Ja das ist doch die Vielfachensummendarstellung, die ich vorhin erwähnt habe
|
||||||||||
| 12.04.2012, 22:31 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Aha, hab mich eh schon gewundert, was das sein soll...
|
||||||||||
| 12.04.2012, 22:51 | Mathelover | Auf diesen Beitrag antworten » | ||||||||
Jaja lach mich nur aus
|
||||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
