RSA-Algorithmus

[@jonasluhrs3644]

Vielen Dank für den ganzen Aufwand! Das ist sehr inspirierend.

[@rwd420]

Sehr schön demonstriert, vielen Dank!

[@joerg_koeln]

Bravo, super erklärt!

[@rwd420]

Wie passiert eigentlich die Auswahl der Primzahlen? Greift da der Rechner auf bekannte Tabellen zurück?

[@holzmaurer1319]

Nein. Eine feste Tabelle von Primzahlen, die in den Arbeitsspeicher passt, hätte ein Angreifer auch. Es wären zu wenige mögliche Primzahlen. Der Angreifer könnte dann alle Fälle durchrechnen. Tatsächlich werden vereinfacht gesagt schlicht große Zahlen zufällig geraten und dann getestet, ob sie prim sind, so lange bis eine Primzahl gefunden ist. Das geht, weil erstens die Dichte der Primzahlen nur logarithmisch abnimmt (Primzahlsatz von Gauß), so dass es auch unter sehr großen Zahlen immer noch recht viele Primzahlen gibt. Zweitens existieren schnelle Primzahltests. Da ist z.B. der AKS-Primzahltest, der in polynomialer Zeit (abhängig von der Zahl der Ziffern) sicher entscheidet, ob eine vorgelegte Zahl prim ist oder nicht. Dieser Algorithmus sagt nur Ja (ist prim) oder Nein (ist zusammengesetzt). Er kann jedoch im Fall einer Nein-Antwort keinen Teiler liefern. Das Finden eines Teilers einer als zusammengesetzt erkannten Zahl dauert nach heutigem Wissen immer noch exponentiell lange. Nun ist selbst der AKS-Test für die Praxis immer noch zu langsam, weswegen man pobabilistische Tests einsetzt: Den Miller-Rabin-Test. Dieser kann jedoch mit geringer Wahrscheinlichkeit daneben liegen und falsch positive Ergebnisse liefern. D.h. die Primzahlen, die in der Praxis zum Einsatz kommen, sind nur mit sehr hoher Wahrscheinlichkeit wirklich prim. Dabei kann die Fehlerwahrscheinlichkeit, dass man irrtümlich doch eine zusammengesetzte Zahl verwendet, beliebig klein (aber nicht 0) gemacht werden, je nachdem wieviel Rechenaufwand man bereit ist zu investieren.

[@Jonas-h4w3q]

@holzmaurer1319 Danke für deine Ausführung! Denn darin sah ich bisher immer die potenzielle Schwäche der RSA Verschlüsselung, dass eben nur eine begrenzte Anzahl dieser riesigen Primzahlen bekannt sein dürfte. Aber wenn man, wie du beschreibst, in relativ kurzer Zeit eine neue Primzahl "erraten" kann, dann ist die Herstellung eines neuen und einzigartigen privaten Schlüssels wohl doch problemlos möglich. Die Frage ist dann aber immer noch: Wie oft wird dieser Schlüssel dann durch einen neuen ausgetauscht. Täglich? Wöchentlich? oder alle 15 Sekunden?

[@SM-ii9bb]

Ich glaube, ich habe das noch nicht verstanden. Wenn z.B. ein vierstelliger PIN übertragen wird, ist es doch egal wie groß p und q sind, da es immer nur 10^4 Möglichkeiten für den PIN gibt und n und e ja durch den Public Key bekannt sind. Man müsste dann nur exakt wissen, wann der PIN übertragen wird. Sorry, falls das eine blöde Frage ist.

[@luhna_lp5326]

Naja du kannst den vierstelligen pin aber z.b. mit Modulo 2^4096 verschlüsseln d.h. wenn du z.b. sagen wir 1337 verschlüsseln willst dann werden aus 1337 1 = 1 3 = 28374748347837474934747484848484 7= 8284848483889907796838834938 Und genau da liegt am ende das Problem die Zahlen sind so groß das es Jahrzehnte bräuchte um es zu knacken weil du als Angreifer nicht weisst welche Primzahlen genommen wurden Um es einfacher zu machen: stell dir eine Zahl vor die sagen wir 32 bit lang ist und verschlüssel die mit dem Verfahren oder 64bit oder oder oder es wird halt immer absurder hoffe ich konnte helfen 😅

[@holzmaurer1319]

Du hast recht. Die Nachricht darf bei (egal welcher) Publik-Key-Verschlüsselung nicht zu kurz sein. Sie muss hinreichend viele einem potenziellen Angreifer unbekannte Bits enthalten. Sonst kann der Angreifer durch Brute-Force die wenigen möglichen Fälle durchrechnen und damit entschlüsseln. Wenn du die PIN z.B. durch 13 Bits kodierst, dann könntest du die Nachricht einfach mit ein paar tausend weiteren zufälligen Bits verlängern (die der Empfänger ignoriert). Beachte, dass in der Praxis der RSA-Algorithmus nur zu Beginn einer verschlüsselten Verbindung verwendet wird, um einen geheimen symmetrischen AES-Schlüssel zu übertragen. Denn AES ist wesentlich schneller als RSA. Der AES-Schlüssel ist aber so groß, dass Brute-Force bei seiner Übertragung nicht mehr möglich ist.

[@holzmaurer1319]

@@luhna_lp5326 Das hilft nicht, da dieses Verfahren dem Angreifer bekannt ist (soll ja zwischen Sender und Empfänger kein Geheimnis geben)! Es gibt dann immer noch nur 10000 mögliche Nachrichten. Die kann der Angreifer aber in kurzer Zeit in einer Schleife durchrechnen und damit entschlüsseln. Du musst die zu verschlüsselnde Nachricht mit mehr Entropie anreichern.

[@holzmaurer1319]

@@luhna_lp5326 Verstehe ehrlich gesagt nicht, was du genau meinst. Was ist das für eine Modulo-Rechnung? Und was heißt, der Angreifer wüsste die Primzahlen nicht. Der Verschlüssler weiß sie doch auch nicht!?

[@SM-ii9bb]

@luhna_lp5326 Danke für deine Antwort. Klar, werden die Zahlen groß aber der Empfänger muss ja auch mit der Zahl arbeiten, um sie dekodieren zu können. Das sollte dann also möglich sein. Da ja der Public Key bekannt ist, ordnet man jeder Zahl einen anderen bekannten Wert zu, weshalb mir das Prinzip der Verschlüsselung nicht klar ist. Vielleicht stehe ich einfach auf dem Schlauch.