RSA: Beispiel Teil 1
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Part Number | 6 | |
| Number of Parts | 7 | |
| Author | 0000-0002-7299-4943 (ORCID) | |
| License | CC Attribution 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/19813 (DOI) | |
| Publisher | 0044w3h23 (ROR) 0000-0002-7299-4943 (ORCID) | |
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
Verschlüsselung6 / 7
1
2
3
6
7
00:00
Inverse elementPrime numberOrder (biology)Moment (mathematics)ZahlEuklidischer AlgorithmusComputer animationLecture/Conference
05:30
GradientNumberDivision (mathematics)Diophantische GleichungLecture/Conference
Transcript: German(auto-generated)
00:04
Wir rechnen jetzt mal ein Beispiel RSA, ja? Also RSA-Beispiel.
00:34
Oh, jetzt sehe ich gerade das Beispiel, das ich mir überlegt habe. Das funktioniert ja gar nicht so. Müssen wir uns ad hoc ein anderes überlegen, oder?
00:48
Eine der Zahlen, die ich ausgewählt habe, war gar keine Primzahl. Ja, ist natürlich peinlich, ist klar. Naja, machen wir folgendes, komm.
01:05
Welche zwei Primzahlen nehmen wir mal? Zwei riesige Primzahlen. 13 und 17 sind wir schon zu groß, ehrlich gesagt, als Beispiel. 3 und 5 sind wir ein bisschen klein. 7 und 11?
01:22
Ja, wollen wir 7 und 11 nehmen? Sie sind schuld, wenn es kompliziert wird. Ok, P gleich 7, Q gleich 11, N gleich 77, ne? Also wir haben unser RSA-Modul bestimmt N gleich 77.
01:44
Was machen wir jetzt? Was machen wir jetzt? Wir haben N bestimmt. Ja?
02:03
Phi von N. Ok, wie machen wir das? Phi von 77, ist wie groß? 60, genau. 6 mal 10.
02:22
So, jetzt brauchen wir unser E. Unser E, das bezüglich 60, das der GGT mit 60 gleich 1 hat. Nehmen wir mal irgendeine Primzahl am besten, durch die 60 nicht teilbar ist. Ja?
02:42
47. Sie sind wirklich wagemutig, ja? Nö, das kann kein Problem sein.
03:17
Sie sollten halt nur vielleicht nicht unbedingt eine dieser beiden Primzahlen, die Sie verwendet haben,
03:20
weil ansonsten jemand die vielleicht einfach mal ausprobiert. Ok, also nehmen wir die nicht, sondern nehmen wir 47, oder? E gleich 47. So, das heißt, der öffentliche Schlüssel haben wir jetzt schon.
03:47
Öffentlicher Schlüssel ist 47 und 60. So, wir bestimmen D. Und zwar mit 47.
04:12
47. Bitte? Oh, stimmt, Sie haben recht. Entschuldigung. Ganz falsch. 47 und 77.
04:32
Sie fallen wirklich auf keinen Test von mir rein. Sehr gut. So, 47 mal D ist Konkurrent 1 modulo 60.
04:45
Also, wir müssen gucken, dass unser D das Inverse von 47 modulo 60 ist. Wir haben ja 47 so ausgewählt, dass es ein Inverses gibt. So, Sie haben 47 ausgesucht. Jetzt bestimmen Sie bitte das Inverse.
05:05
Naja, was machen wir? Erweitert euer klinischer Algorithmus. Komm, machen wir mal schnell, oder? Da können wir den auch nochmal üben. Ja, da probiert man nicht aus. Da probiert man nicht aus.
05:24
Erweitert euer klinischer Algorithmus. Was müssen wir lösen? Wir müssen 47 mal x, machen wir so, 47 mal x plus 60 mal y ist gleich 1 lösen.
05:40
So, diese diophantische Gleichung. Also, los geht's. A, B, Q, R, X, Y. Ein schönes Tabellchen hier.
06:08
Schön gerade Linien. So, ganz stupide machen wir es. 47 durch 60.
06:21
Die Division mit Rest ist 0 Rest 47. So, dadurch werden die beiden Zahlen erst mal vertauscht, damit die größere vorne steht. 60 durch 47. Sie kontrollieren bitte immer schön mit. 60 durch 47 ist 2 Rest 13.
06:44
Ah, sehr gut. Ja, immer schön wachsam bleiben. 1 Rest 13. 47, 13. Was ist 47 durch 13?
07:01
2, nein Quatsch, 3. 3 Rest 8, genau. 13 und 8. 1 Rest 4. 5, genau.
07:32
1, genau, 1 Rest 5. So, jetzt sind wir bei der 8 und 5 ist 1 Rest 3.
07:41
5 und 3. Also wirklich bis zum Exzess immer mit 1 und 2. So, jetzt kommt glaube ich 3, 2, 1 Rest 1. So, 2, 1, die geht 2 mal rein, Rest 0.
08:06
So, schon lange kein extrem erweiterten ökidischen Algorithmus wäre gerechnet. Ja, jetzt geht es rückwärts. So, das machen Sie bitte mal als Hausaufgabe.
08:23
Okay, also los geht's. GGT ist 1. Das ist 0 mal a plus 1 mal b. 0 mal a plus 1 mal b. Das kann man schon mal reinschreiben. So, die 1 hole ich rüber. So, und hier steht drin 0 minus das mal das ist minus 1.
08:44
Bitte immer schön mitkontrollieren jetzt. 0 minus das mal das ist minus 1. Minus 1 hier rüber. 1 minus 1 mal minus 1 ist 2. Minus 1 minus 1 mal 2 ist minus 3.
09:03
2 minus 1 mal minus 3 ist 5. Minus 3 minus 3 mal 5 ist minus 18.
09:24
5 minus 1 mal minus 18 ist 23. Okay, 23 minus 18. Also unser d scheint zu sein 23.
09:47
So, gucken wir mal ob es stimmt. Sicherheitshalber. D gleich 23. Machen wir eine Probe, oder? 47 mal 23.
10:00
2 mal 7 ist 14. 9, 21, 14. 1, 8, 1081, oder? 1081 durch 60. 600 können wir rausziehen. 300 können wir rausziehen. 180 können wir rausziehen. Bleibt 1 übrig.
10:24
600 können wir rausziehen. Das ist 6thalber. Dann 300, dann bleibt 181 übrig. 180, 1 kommt raus. Modulo 60. So, okay. Also stimmt. Ja, die 23. So, damit ist der private Schlüssel 23 und 77.