Asymmetrische Verschlüsselung erklärt
Hood Informatik
https://www.youtube.com/watch?v=Hp2bT4BlXsI

Transkript (automatisch erstellt)

0:00 Public Key, Private Key. Jeder benutzt diese Begriffe, aber fast niemand erklärt, was da mathematisch wirklich passiert. Warum gibt es überhaupt zwei
0:07 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
0:15 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
0:22 Datenmüll. Und wer den gleichen Schlüssel hat, kann entschlüsseln. Ein Schlüssel zwei Richtungen, das nennt man symmetrische Verschlüsselung. AES
0:30 funktioniert so, chcha funktioniert so und ganz viel andere auch. Das einfachste Beispiel ist hier aber vermutlich die Cesarverschlüsselung.
0:38 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
0:45 verschieben. Sagen wir mal, jeden Buchstaben verschieben wir um drei Positionen. Dann hätten wir aus der folgenden Nachricht hallo nämlich
0:52 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
1:02 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
1:11 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,
1:18 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
1:27 einfach erraten bzw. ausprobiert werden. Aber symmetrische Verschlüsselung hat ein ganz anderes, fundamentaleres Problem. Beide Seiten müssen denselben
1:35 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,
1:43 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
1:50 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
1:58 Hellmann erklärt habe. Aber selbst wenn ihr das Austauschproblem löst, bleiben zwei Fragen offen. Wie schickt ihr jemanden eine verschlüsselte Nachricht,
2:06 mit dem ihr vorher noch nie Kontakt hattet? Symmetrische Kryptografie funktioniert nämlich nur, wenn beide Seiten bereits denselben geheimen
2:13 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
2:22 auf beiden Seiten denselben bzw. nur einen Schlüssel habt und asymmetrisch, weil es eben nicht mehr symmetrisch ist, sondern zwei unterschiedliche Schlüssel
2:30 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,
2:37 https oder Ende zu Ende Verschlüsselung verstehen, denn all das basiert zu großen Teilen auf asymmetrischer Kryptografie. Also statt einem Schlüssel
2:46 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
2:54 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.
3:02 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
3:10 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
3:18 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
3:26 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.
3:33 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
3:41 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,
3:50 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
3:58 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
4:10 Fall 3233. Und jetzt kommt die wichtigste Zahl im ganzen Verfahren. Sie heißt F von N. Klingt nach Unimathe, ist aber
4:18 eigentlich ganz simpel. F von N beantwortet eine einzige Frage. Wie viele Zahlen unterhalb von n, wir erinnern uns, dass es das Ergebnis der
4:26 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
4:35 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.
4:43 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
4:52 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
5:01 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
5:08 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
5:20 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
5:29 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
5:38 Grundvoraussetzung. F n kann man in unserem Fall also so berechnen. P -1* Q -1, also 60* 52 = 3120. Eine einzige Multiplikation und fertig.
5:52 Wir müssen also nicht einzeln durchgehen, sondern berechnen einfach diese Formel. Und genau hier passiert das Entscheidende und auch der Grund,
5:58 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
6:08 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
6:17 finden, müsste er 3233 wieder in 61 x 53 zerlegen, also faktorisieren. Bei dieser kleinen Zahl ginge das noch, aber bei den riesigen
6:28 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
6:35 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
6:45 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
6:56 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
7:04 grundsätzlich. Und die 65537 ist eine bewusste Wahl, aber keinen Zwang. 65537 ist beliebt, weil es eine Primzahl ist,
7:14 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
7:21 schnell. Es ist also ein guter Kompromiss aus Sicherheit und Performance und deshalb der de facto Standard. In unserem Beispiel nehmen wir
7:28 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,
7:37 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
7:44 Gegenspieler zu unserem E von eben. Das Grundprinzip vorweg, damit ihr wisst, worauf das alles hinausläuft. Beim Verschlüsseln nehmen wir die Nachricht,
7:52 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
8:00 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
8:09 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
8:21 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
8:29 einem das Direkt ausrechnet. Dieses Verfahren heißt erweiterter Eukitsche Algorithmus. Im Grunde macht euer Computer das in Millisekunden. Für unser
8:36 Beispiel kommt dabei raus, D = 2753. Und lass uns mal kurz gucken, ob das passt. 17 x 2753 = 46801
8:48 und 4680120 geht 15 mal auf mit Rest 1. Also genau was wir wollten. Damit steht unser
8:57 privater Schlüssel fest. D und N sind hier 2753 und 3233. Und jetzt seht ihr auch, warum D geheim
9:06 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
9:16 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
9:25 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
9:38 ergibt 2790. Jetzt nehmen wir mal die 2790, die sozusagen unser verschlüsselter Text werden und versuchen es zu
9:46 entschlüsseln. Dafür nutzen wir die Formel C, also unser verschlüsselter Text hoch d Modulu N. Das wäre 2790 hoch 2753
9:56 modulo 3233 ergibt = 65. Also wieder unsere Nachricht, die wir verschlüsselt haben. Unsere Nachricht [räuspern] ist also
10:03 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.
10:13 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
10:21 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
10:33 kleinen Zahlen ist das wie gesagt trivial, aber bei Zahlen mit 600 oder mehr Stellen kennen wir keinen effizienten Algorithmus. Mit heutiger
10:40 Technik gilt das als praktisch unmöglich. Und genau das ist der Kern von RSA. Multiplizieren ist einfach, aber faktorisieren ist unglaublich
10:48 schwer. Das nennt man eine Einwegfunktion und vieles in der Kryptografie basiert tatsächlich auf sowas. Also leicht in die eine Richtung
10:54 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
11:01 entschlüsseln mit dem Private Key. Aber asymmetrische Kryptografie kann noch was zweites und das ist mindestens genauso wichtig und zwar digitale Signaturen.
11:10 Die Frage dahinter ist eine ganz andere. Beim Verschlüsseln geht es um Geheimhaltung. Niemand soll mitlesen. Bei Signaturen geht's um etwas anderes
11:17 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
11:25 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
11:31 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
11:39 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
11:47 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
11:56 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,
12:03 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
12:10 einmal. Authentizität, also die Nachricht kommt wirklich von mir und Integrität. Sie wurde seit der Unterschrift nicht verändert und genau
12:17 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,
12:25 überall unterschreibt ein Private Key und ein Public Key verifiziert. Also symmetrische Verschlüsselung ist schnell und sicher, aber sie funktioniert nur,
12:33 wenn beide Seiten bereits einen gemeinsamen Schlüssel haben. Asymmetrische Krypto löst genau dieses Problem auf Kosten von Performance. In
12:39 der Praxis benutzen wir deshalb beides zusammen. Jedes Protokoll, das ihr täglich nutzt, ist ein Zusammenspiel dieser Bausteine. Und das Fundament von
12:47 allem ist ein simples mathematisches Prinzip. Multiplizieren ist leicht und faktorisieren ist schwer. So simpel und doch so mächtig. Falls euch solche
12:54 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.