Hilfe beim RSA-Verfahren?
Hallo, ich lerne gerade für eine Klausur, aber leider gibt es eine Rechenart bei welcher ich an manchen stellen nicht weiterkomme. Auf einem Zettel meiner Lehrerin habe ich alle stellen markiert, die ich nicht verstehe. Falls möglich kann sich ja jemand etwas Zeit erübrigen, um mir zu helfen :)
1 Antwort
Es handelt sich um den erweiterten euklidischen Algorithmus. In dem Fall sucht man nach eindem d in {0, ..., 59}, sodass 17*d = 1 (mod 60). Da 17 und 60 teilerfremd sind, d.h. ggt(60, 17) = 1 gibt es eine Lösung. Das d ist dann auch wieder teilerfremd mit 60. Man sucht also Faktoren k und d, sodass k*60 + d*17 = 1
Im euklidischen Algorithmus zieht man immer wieder die kleinere Zahl von der großen Zahl ab. Der größte gemeinsame Teiler von der kleinere Zahl und der Differenz ist der gleiche wie von den beiden ursprünglichen Zahlen.
Bei 60 und 17 kann man die 17 dreimal von der 60 abziehen. Also 60 = 3*17 + 9. Und die 9 geht dann wiederum einmal in die 17 rein. Also 17 = 1*9 + 8. Der nächste Schritt ist dann die 8, die einmal in die 9 reingeht und man bekommt 9 = 1*8 + 1. Insgesamt hat man die Folge 60, 17, 9, 8, 1. Das Ziel ist nun k und d zu finden, sodass k*60 + d*17 = 1. Im letzten Schritt wurde die 8 von der 9 abgezogen mit 1 als Ergebnis und die Gleichung wird rückwärts zusammengebaut.
1* 9 - 1*8 = 1. Die 8 war das Ergebnis aus 17 - 1*9 also nimmt man den Term für die 8 ein: 1*9 -1*(17 - 9) = 1. Zuvor wurde die 1 als Linearkombination von 9 und 8 dargestellt.
Im nächsten Schritt stellt man die 1 als Linearkombination von 17 und 9 dar: 1*9 - 1*(17 - 9) = 2*9 - 1*17 = 1
Dann als Linearkombination von 60 und 17. Dabei war 9 = 60 - 3*17. Also 2*(60 - 3*17) - 1*17 = 2*60 - 7*17 = 1.
Zum Schluss werden die -7 als positive Zahl geschrieben mit -7 = 53 - 60.
2*60 - 7*17 = 2*60 + (53 - 60)*17 = -58*60 + 53*17 = 1
Somit d = 53.
Vielen vielen Dank für diese Antwort, hat mir sehr geholfen!