Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Asymmetrische Verschlüsselung erklärt
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 93 Zeilen
- Public Key, Private Key. Jeder benutzt diese Begriffe, aber fast niemand erklärt, was da mathematisch wirklich passiert. Warum gibt es überhaupt zwei
- Schlüssel? Warum reicht nicht einfach ein Passwort? Und wie kann es sein, dass ein Schlüssel verschlüsselt, aber nicht entschlüsseln kann? Willkommen zurück
- bei Hutz Informatik. Fangen wir mal ganz vorne an. Verschlüsselung an sich ist simpel. Du nimmst eine Nachricht und ein Schlüssel und rauskommt unlesbarer
- Datenmüll. Und wer den gleichen Schlüssel hat, kann entschlüsseln. Ein Schlüssel zwei Richtungen, das nennt man symmetrische Verschlüsselung. AES
- funktioniert so, chcha funktioniert so und ganz viel andere auch. Das einfachste Beispiel ist hier aber vermutlich die Cesarverschlüsselung.
- Nehmen wir einfach mal unser Alphabet. A ist der erste Buchstabe, B der zweite und so weiter. Wir können jetzt jeden Buchstaben um beliebige Positionen
- verschieben. Sagen wir mal, jeden Buchstaben verschieben wir um drei Positionen. Dann hätten wir aus der folgenden Nachricht hallo nämlich
- folgendes getan. K D O R. Wir haben also das H genommen und sind drei Buchstaben weitergesprungen. Das heißt H I J K und dasselbe für jeden anderen Buchstaben
- auch. Was muss aber unser Gegenüber jetzt wissen, um diese verschlüsselte Geheimnachricht zu entschlüsseln? Genau, die Zahl 3. Die Zahl 3 ist in unserem
- Fall nämlich der Schlüssel, sowohl zum Entschlüsseln als auch zum Verschlüsseln. Unser Gegenüber kann jetzt nämlich unsere Nachricht nehmen,
- nämlich Kdo OO und drei Buchstaben zurückgehen, um so die Nachricht wieder zu entschlüsseln. Dieser Mechanismus ist natürlich viel zu simpel und könnte
- einfach erraten bzw. ausprobiert werden. Aber symmetrische Verschlüsselung hat ein ganz anderes, fundamentaleres Problem. Beide Seiten müssen denselben
- Schlüssel kennen. In unserem Beispiel müsste unser Partner also wissen, dass es sich um den Schlüssel 3 handelt. Aber ich kann es ihm nicht einfach mitteilen,
- denn jeder, der uns dabei abhört, könnte mit dieser Info alles entschlüsseln, was wir danach hin und her schicken. Und im Grunde wäre der ganze Verschlüsselungs
- und Entschlüssungskram dann für die Cuts. Aber dafür gibt es Lösungen, z.B. Diffi Helmann. Ich habe euch oben rechts mal ein Short markiert, wo ich die
- Hellmann erklärt habe. Aber selbst wenn ihr das Austauschproblem löst, bleiben zwei Fragen offen. Wie schickt ihr jemanden eine verschlüsselte Nachricht,
- mit dem ihr vorher noch nie Kontakt hattet? Symmetrische Kryptografie funktioniert nämlich nur, wenn beide Seiten bereits denselben geheimen
- Schlüssel teilen. Und genau deshalb gibt es asymmetrische Kryptografie mit Public und Private Keys. Ihr merkt schon, woher der Name kommt. Symmetrisch, weil ihr
- auf beiden Seiten denselben bzw. nur einen Schlüssel habt und asymmetrisch, weil es eben nicht mehr symmetrisch ist, sondern zwei unterschiedliche Schlüssel
- existieren. Wenn ihr nach diesem Video dieses Konzept versteht, werdet ihr einen Großteil der Dinge, die ihr alltäglich nutzt, wie z.B. Apple Pay,
- https oder Ende zu Ende Verschlüsselung verstehen, denn all das basiert zu großen Teilen auf asymmetrischer Kryptografie. Also statt einem Schlüssel
- gibt es zwei. Die werden zusammenzeugt und sie sind mathematisch verwandt. Aber man kann den einen nicht aus dem anderen berechnen. Der eine ist öffentlich, der
- sogenannte Public Key und den darf jeder sehen. Ihr könnt ihn auf Twitter posten, ihn ausdrucken, auf eure Visitenkarte packen und ihn an die Wand schreiben.
- Ist vollkommen egal. Der andere ist privat, das ist euer Private Key und der bleibt bei euch. Der verlässt niemals euren Rechner und sollte nicht mit
- Fremden geteilt werden. Und jetzt kommt die Magie. Was mit dem einen Schlüssel verschlüsselt wurde, kann nur mit dem anderen entschlüsselt werden. Wenn ich
- euch eine verschlüsselte Nachricht schicken will, nehme ich euren Public Key, den kennt jeder, und verschlüssele damit. Ab diesem Moment könnt nur noch
- ihr die Nachricht lesen, weil nur ihr den Private Key habt, mit dem ihr das Ganze wieder entschlüsseln könnt. Okay, aber lass uns mal tiefer reingehen.
- Warum funktioniert das Ganze? Warum kann ein Schlüssel nicht beides? Dafür müssen wir in die Mathematik und ich zeige euch das am Beispiel von RSA. Alles beginnt
- mit zwei zufällig gewählten großen Primzahlen. Eine Primzahl ist eine Zahl, die sich nur durch ein oder durch sich selbst teilen lässt, wie z.B. 3, 5, 7,
- 11 und so weiter. Wir nennen diese zwei zufällig gewählten großen Primzahlen P und Q. In der Realität haben sie hunderte von Stellen, aber für unser
- Beispiel nehmen wir sehr kleine. Z.B. p = 61 und Q = 53. Diese multiplizieren wir miteinander und packen das Ergebnis in N. Das Ergebnis von P* Q wäre in dem
- Fall 3233. Und jetzt kommt die wichtigste Zahl im ganzen Verfahren. Sie heißt F von N. Klingt nach Unimathe, ist aber
- eigentlich ganz simpel. F von N beantwortet eine einzige Frage. Wie viele Zahlen unterhalb von n, wir erinnern uns, dass es das Ergebnis der
- Multiplikation von den zwei Primzahlen, haben mit n nichts gemeinsam. Was heißt nichts gemeinsam? Zwei Zahlen haben dann nichts gemeinsam, wenn man sie durch
- keine gemeinsame Zahl teilen kann, außer durch eins. Mathematiker sagen dazu: Teiler fremd. Machen wir es mal an einem Minispiel. Nehmen wir die Zahl 10.
- Welche Zahlen darunter sind Teilerfremd zu ze? Nehmen wir z.B. die zwei. Die zwei teilt sich die zwei mit der zehn, weil beide sind durch zwei teilbar. Sie
- sind also nicht teilerfremd. Die fünf teilt sich die fünf mit der zehn, denn beide sind durch fünf teilbar. Das heißt auch hier nicht teilerfremd. Die drei
- hingegen hat mit Zeh nichts gemeinsam. Du kannst Zehen nicht durch drei teilen, ohne einen Rest zu behalten. Das heißt, sie sind teilerfremd. Wenn man alle
- durchgeht, bleiben bei der 10 genau vier solcher Zahlen übrig. 1 3 7 und 9. Also wäre vi von 10 = 4. Bei kleinen Zahlen zählt man das einfach so ab bzw. man
- kann es einfach ausprobieren. Aber jetzt kommt der Clue. Bei unserer Zahl n, also 3233, alles durchzuzählen wäre die Hölle. Aber es gibt eine Abkürzung und
- die funktioniert immer dann, wenn n aus genau zwei Primzahlen gebaut ist. Und das Gute ist, unser n wurde aus Primzahlen gebaut. Das war ja unsere
- Grundvoraussetzung. F n kann man in unserem Fall also so berechnen. P -1* Q -1, also 60* 52 = 3120. Eine einzige Multiplikation und fertig.
- Wir müssen also nicht einzeln durchgehen, sondern berechnen einfach diese Formel. Und genau hier passiert das Entscheidende und auch der Grund,
- warum RSA überhaupt sicher ist. Diese Abkürzung kann nämlich nur benutzen, wer P und Q kennt. Ich, der die Schlüssel erzeugt hat, kenne beide. Für mich ist P
- von N Sekunde Arbeit. Ein Angreifer dagegen sieht nur die fertige Zahl n, also 3233 und kennt P und Q nicht. Und um sie zu
- finden, müsste er 3233 wieder in 61 x 53 zerlegen, also faktorisieren. Bei dieser kleinen Zahl ginge das noch, aber bei den riesigen
- Zahlen, die in der Praxis genutzt werden, geht das nicht mehr. Aber warum brauchen wir F von N überhaupt? Weil wir damit gleich den privaten Schlüssel
- berechnen. Ohne F von N kein private Key und F von N kriegt nur wer P und Q hat. Wir wählen jetzt eine Zahl E, die teilerfremd zur P von N ist. Standard in
- der Praxis für E ist in der Regel 65537. Wir nehmen für unser Beispiel aber mal E = 17. Aber ich will hier noch mal kurz erzählen, warum man oft die 65537
- wählt. E muss nämlich zwei Bedingungen erfüllen. Es muss teilerfremd zu F n sein und zwischen 1 und F von n liegen. Jede Zahl, die das erfüllt, funktioniert
- grundsätzlich. Und die 65537 ist eine bewusste Wahl, aber keinen Zwang. 65537 ist beliebt, weil es eine Primzahl ist,
- also so gut wie immer Teilerfremd so viel von N und in der Binärdarstellung nur zwei Einsen hat. Das macht die Verschlüsselung rechnerisch sehr
- schnell. Es ist also ein guter Kompromiss aus Sicherheit und Performance und deshalb der de facto Standard. In unserem Beispiel nehmen wir
- der Einfachheit halber, aber einfach mal E = 17. Unser public key also jetzt en, also 17 und 3233. Wie wir damit fair oder entschlüsseln,
- dazu kommen wir gleich. Jetzt bauen wir aber erstmal noch den privaten Schlüssel. Wir suchen eine Zahl, die wir D nennen und dieses D ist der
- Gegenspieler zu unserem E von eben. Das Grundprinzip vorweg, damit ihr wisst, worauf das alles hinausläuft. Beim Verschlüsseln nehmen wir die Nachricht,
- die wir verschlüsseln wollen, hoch eine Zahl E. Und beim entschlüsseln nehmen wir das Ergebnis hoch eine andere Zahl D. Die ganze Mathematik der nächsten
- Minuten dreht sich nur darum, ein passendes E und D zu finden und zu verstehen, warum niemand sonst das D ausrechnen kann. Die Bedingung dafür ist
- diese e* Dφ von N muss den Rest 1 lassen. Dafür setzen wir einfach mal unsere Werte ein. 17 x D. D suchen wir ja noch geteilt durch 3120 soll Rest 1
- ergeben. Wir suchen also die eine Zahl D, die diese Gleichung erfüllt. Man könnte sturprobieren, aber dafür gibt es ein schnelles Standardverfahren, das
- einem das Direkt ausrechnet. Dieses Verfahren heißt erweiterter Eukitsche Algorithmus. Im Grunde macht euer Computer das in Millisekunden. Für unser
- Beispiel kommt dabei raus, D = 2753. Und lass uns mal kurz gucken, ob das passt. 17 x 2753 = 46801
- und 4680120 geht 15 mal auf mit Rest 1. Also genau was wir wollten. Damit steht unser
- privater Schlüssel fest. D und N sind hier 2753 und 3233. Und jetzt seht ihr auch, warum D geheim
- bleiben muss. D auszurechnen geht nur mit F n und F von N hat nur wer P und Q kennt. Die ganze Kette hängt also zusammen. Wer P und Q nicht hat, kommt
- an D niemals ran. Und wie verschlüsselt man damit jetzt? Sagen wir mal, unsere Nachricht ist der Buchstabe A. In ASKI umgerechnet wäre das die Zahl 65. Also
- sagen wir einfach mal m = 65. Wir verschlüsseln m jetzt, indem wir m hoch E modulo n rechnen. Also 65 hoch 17 unser E modulo 3233
- ergibt 2790. Jetzt nehmen wir mal die 2790, die sozusagen unser verschlüsselter Text werden und versuchen es zu
- entschlüsseln. Dafür nutzen wir die Formel C, also unser verschlüsselter Text hoch d Modulu N. Das wäre 2790 hoch 2753
- modulo 3233 ergibt = 65. Also wieder unsere Nachricht, die wir verschlüsselt haben. Unsere Nachricht [räuspern] ist also
- wiederhergestellt. Aber warum geht das? Weil E und D so gewählt wurden, dass ihre Kombination Modulu Phi von N genau die ursprüngliche Zahl wiederherstellt.
- Der Satz von Euler garantiert uns das nämlich. Und warum kann man den Private Key nicht berechnen? Um D zu berechnen, braucht man F von N. Und um vi von n zu
- berechnen, braucht man P und Q. Und um P und Q aus N zu bekommen, müsste man n faktorisieren. Also 3233 zurück in 61 x 53 zerlegen. Bei diesen
- kleinen Zahlen ist das wie gesagt trivial, aber bei Zahlen mit 600 oder mehr Stellen kennen wir keinen effizienten Algorithmus. Mit heutiger
- Technik gilt das als praktisch unmöglich. Und genau das ist der Kern von RSA. Multiplizieren ist einfach, aber faktorisieren ist unglaublich
- schwer. Das nennt man eine Einwegfunktion und vieles in der Kryptografie basiert tatsächlich auf sowas. Also leicht in die eine Richtung
- zu berechnen, aber praktisch unmöglich zurück. Wir haben bis jetzt nur über eine Richtung geredet und zwar Verschlüsseln mit dem Public Key und
- entschlüsseln mit dem Private Key. Aber asymmetrische Kryptografie kann noch was zweites und das ist mindestens genauso wichtig und zwar digitale Signaturen.
- Die Frage dahinter ist eine ganz andere. Beim Verschlüsseln geht es um Geheimhaltung. Niemand soll mitlesen. Bei Signaturen geht's um etwas anderes
- und zwar kommt diese Nachricht wirklich von der Person, die behauptet, sie geschickt zu haben und wurde sie unterwegs verändert oder nicht? Und hier
- kommt der Trick. Dafür drehen wir die Schlüssel einfach um. Bei der Verschlüsselung war es: "Jeder verschlüsselt mit einem Public Key und
- nur ich entschlüssel mit meinem Private Key." Bei der Signatur ist es genau andersrum. Ich erzeuge mit meinem Private Key eine Signatur und jeder kann
- sie mit meinem Public Key überprüfen. Aber warum beweist das irgendwas? weil nur ich meinen Private Key habe. Eine Signatur, die sich mit meinem Public Key
- verifizieren lässt, kann nur mit meinem Private Key erzeugt worden sein. Niemand sonst hätte das gekonnt. Und das ist die digitale Signatur. Und die Signatur
- hängt nicht nur an mir, sondern auch an der konkreten Nachricht. Ändert jemand auch nur ein einziges Zeichen, ein Komma, ein Leerzeichen und so weiter,
- passt die Signatur nicht mehr. Die Überprüfung schlägt dann fehl und ihr wisst sofort, da wurde was manipuliert. Damit habt ihr zwei Garantien auf
- einmal. Authentizität, also die Nachricht kommt wirklich von mir und Integrität. Sie wurde seit der Unterschrift nicht verändert und genau
- das nutzt ihr ständig ohne es zu merken. Wenn euer Handy ein Update installiert, prüft es die Signatur des Herstellers. Software, App Store, Crypto Wallets,
- überall unterschreibt ein Private Key und ein Public Key verifiziert. Also symmetrische Verschlüsselung ist schnell und sicher, aber sie funktioniert nur,
- wenn beide Seiten bereits einen gemeinsamen Schlüssel haben. Asymmetrische Krypto löst genau dieses Problem auf Kosten von Performance. In
- der Praxis benutzen wir deshalb beides zusammen. Jedes Protokoll, das ihr täglich nutzt, ist ein Zusammenspiel dieser Bausteine. Und das Fundament von
- allem ist ein simples mathematisches Prinzip. Multiplizieren ist leicht und faktorisieren ist schwer. So simpel und doch so mächtig. Falls euch solche
- Videos gefallen und ihr mehr davon sehen wollt, lasst gerne ein Abo da und lik das Video. Und damit stay safe und bis zum nächsten Mal. Yeah.