Quantencomputer RSA und AES

Aleve · Anmeldungsdatum: 30.09.2017 Beiträge: 15

Hallo,

RSA basiert ja darauf, dass ein privater Schlüssel (p * q) - beides Primfaktoren - zu einer sehr großen Primzahl multipliziert werden (N) N ist gleichzeitig der öffentliche Schlüssel.

Es ist in relevanter Zeit nicht möglich p und q aus N zu ermitteln. Aber da stelle ich mir die Frage, wenn es so sicher ist, wieso es 2010 gelungen ist einen RSA-768 zu entschlüsseln, in etwa 2000 Prozessorjahren.

Ist es dann nicht eine Frage der Zeit, bis man auch RSA 1024 bzw RSA 2048 entschlüsselt? Wie lange bräuchte man theoretisch mit einem Rechnerverbund aus Superleistungs PCs?

Stellen Quantencomputer womöglich eine Gefahr dar?

Und wieso sind Quantencomputer kein Sicherheitsrisiko für symmetrische Verschlüsselung wie AES? Einen 256 Bit Schlüssel durch brute force zu knacken (2^256) dauert ja 3 * 10^57 Jahre, dies sind etwa 3 Nonilliarden Jahre, wenn man einen PC-Cluster mit 800 Milliarden Schlüssel pro Sekunde Rechenleistung nutzt,

wie lange bräuchte ein Quantencomputer dafür?

Und wieso sind Quantencomputer aufgrund der Superposition überhaupt schneller als Hochleistungs PCs? Ich kann mir das nicht so recht vorstellen..

würde mich über leichte/anschauliche Erklärungen freuen

G4mm4G0bl1n · Anmeldungsdatum: 10.05.2017 Beiträge: 93 Wohnort: Darmstadt

Zu ersterem, das stimmt so, bis auf den letzten Teil. N kann keine Primzahl sein, weil sie sich auf einen Primfaktor zerlegen lässt, ansonsten würde p×q nicht zu N führen.

Beispiel:
11 = Prim
13 = Prim
11×13 = 143
143 ist nicht Prim, da die Faktoren größer als 1, aber kleiner als 143 sind. Denn z.b 15 oder 35 sind auch keine Primzahlen, obwohl ihre Faktoren Prim sind.

Du hast recht, wenn du sagst, dass es mathematisch sehr kompliziert ist aus N seine Primfaktoren zu extrahieren. Es gibt einen anderen Weg, der wesentlich effizienter ist. Denn es ist möglich N durch p×q zu verifizieren, in dem man das Leibniz Kriterium nutzt um die Geraden von den Ungeraden Zahlen zu trennen. Anschließend wendet man das Sieb des Eratosthenes auf die ungeraden Zahlen an. Dadurch verkürzt sich der Rechenaufwand um einige MegaFLOP/s und man erhält eine sehr große Tabelle an Primzahlen. Danach werden alle Primzahlen ausgefiltert die in keiner multiplikativen Kombination N ergeben können und schon erhält man mögliche Primfaktoren für N. Diese sind aber überschaubar und lassen sich in kürzester Zeit überprüfen.

Ganz einfach, weil RSA nichts anderes als ein mathematischer Trick ist, der ausnutzt, dass die arithmetisch logische Einheit sprich, das Rechenwerk des Computers eine Ungenauigkeit bei Divisionen mit Primzahlen aufweist. Rechnet man diese Ungenauigkeit mit ein, kann man über den Kehrwert (1/n) von N einen großen Kreis an Primfaktoren ausgrenzen und würde p & q relativ schnell finden. Es gibt noch andere mathematische Angriffe auf das RSA Kryptographiesystem und mit Einigen ist es möglich RSA effizient zu knacken solange der Zeichensatz eine bestimmte Größe nicht überschreitet.

Ebenfalls wird beim AES auch ausgenutzt, dass die ALU (arithmetisch logische Einheit) ein Problem mit einigen Divisionen hat. Aus diesem Grund wird beim AES-PK (Advanced Encryption Standard - Personal Key) beim errechnen des Schlüssel gerundet. Allerdings liegt hier auch die Schwachstelle in der Kryptographietechnik, weil es dadurch möglich ist, gerundete Schlüssel zu erraten. Im übrigen gillt AES ohne PK schon lange nicht mehr als sicher und mit dem richtigen Permutationsverfahren lässt sich AES in kürzester Zeit auch mit PK überwinden. Die Rechenzeit dafür ist außerordentlich gering, wenn geeignete Zahlenräume verwendet werden.

Jetzt sprichst du sogar 3 Dinge an die miteinander zusammenhängen. Ein Rechencluster dessen Rechenleistung multiplikativ mit der Anzahl der Rechner einhergeht ist ein Quantencomputer. Zur Zeit ist es nicht möglich einen Cluster so zu bauen, dass er z.b einen komplexen Rechenweg auf mehrere Computer verteilt. Diesen Vorgang nennt man in der Informatik auch "Parallelisierung". Die einzige Anwendung die wir zur Zeit haben bei der dies gemacht wird ist das Rendering mit GPU's. Allerdings kann sich jeder vorstellen, dass es hierfür einen einfachen Grund gibt. Gehen wir davon aus, ein Film mit einer Länge von 90min muss gerendet werden. Dann werden die 90min Film auf z.b 2000 GPU's verteilt. Somit bekommt jede GPU einen bestimmten Fetzen des Films und rendert diesen. Später wird der komplette Film einfach digital zusammengeklebt. Die Parallelisierung ist hier sehr einfach, aber genau hier liegt das Problem. Gehen wir mal rein von mathematischen Berechnungen aus. Dann müsste der Cluster die Polynominalzeit kennen in der jeder CPU sein Ergebnis errechnet hat um dieses dann zur Weiterberechnungen an einen anderen CPU innerhalb des Clusters weiterzugeben und das am besten ohne Wartezeit, weil diese Wartezeit sich auf jeden weiteren CPU der an der Berechnung beteiligt ist ausbreiten wird. Die momentanen CPU's können die Operation: Addition, Subtraktion & Multiplikation ohne Polynominalzeit berechnen. Allerdings sind alle anderen mathematischen Funktionen mit einer Polynominalzeit behaftet die sich daran orientiert wie schwer die Lösung für den CPU zu finden ist.

Hier sind mal 3 Beispiele für Polynominalzeit und dem NPN-Problem. Du kannst die Rechnung so wie sie ist in deinen Windows Taschenrechner kopieren und selbst sehen was passiert. smile

(Keine Angst! Es sind keine Schäden an der CPU zu erwarten, da ein CPU nur bestimmt oft versucht die Lösung zu finden und den User dann fragt ob er die Berechnung fortsetzen oder anhalten möchte.) Die Berechnungen sind übrigens von mir selbst!

NP-leichtes Problem, keine Polynominalzeit, Ergebnis wird unter 1ms ermittelt.
cosd(1,8e+2325)

NP-mittleres Problem, Polynominalzeit, Ergebnis wird über 1ms ermittelt.
cosd(2,4e+1001)

NP-schweres Problem, unendliche Polynominalzeit, Ergebnis kann nicht ermittelt werden.
cosd(6,e+995)

Bevor ich jetzt hier weitermache, frage ich dich erstmal ob du denn überhaupt eine Vorstellung davon hast, was eine "Superposition" überhaupt ist? Denn dies ist maßgeben dafür zu verstehen wie Parallelisierung durch Superpositionierung bewerkstelligt wird um die Polynominalzeit von komplexen Operationen zu umgehen.

Aleve · Anmeldungsdatum: 30.09.2017 Beiträge: 15

Hallo,

wow, vielen Dank für diese ausführliche und schnellle Antwort. Ich muss ganz ehrlich sagen, du bist wie ein lebender Google.... Big Laugh

Also die Superposition ist ein Wesenszug der Quantenmechanik, der besagt, dass ein Quantenobjekt bezüglich einer Eigenschaft mehrere Zustände gleichzeitig, also eine Überlagerung aller Zustände sein kann. Und erst mit einer Messung wird die Superposition aufgehoben und das QO wird auf einen bestimmten Zustand festgelegt.

So wie ich es verstanden habe, basieren Quantencomputer auf eine Superposition von 1 und 0, sodass es möglich ist, mehrere Rechnungen gleichzeitig durchzuführen. Allerdings sind diese Rechner nicht praktikabel, da die diese Rechenleistung nur so lange gilt, wie die Superposition anhält und sie hält mit bisherigen technischen Standards nur für eine sehr geringe Zeit an.

Ich versuche aus einer möglichen Gefahr durch Quantencomputer die Notwendigkeit der Quantenkryptographie abzuleiten, da diese ja absolut sicher ist, da es alle Voraussetzungen erfüllen kann, die zum One-Time-Pad führen (absoluter Zufall, einmalige Verwendung, Schlüssel genauso lang, wie die Nachricht selbst)

Aber gleichzeitig lese ich in vielen Artikeln, dass es unmöglich ist mit (selbst mit Quantencomputern mittels brute force attacks einen AES Schlüssel von 256 Bit zu knacken, denn man könnte einfach die Bitlänge erhöhen) Aber dann braucht man ja die Quantenkryptographie nicht, es sei denn Quantencomputer wären irgendwann in der Lage, alle Sicherheitsstandards zu brechen.

Ich habe aber wenig Kenntnis über praktische Nutzung von kryptographischen Verfahren als dass ich das beurteilen könnte. Wie ich es verstanden habe, basieren heute alle öffentlichen Netwerkverschlüsselung und Übertragungsprotokolle (z.B. für Banktransaktionen oder Online Shopping, aber auch E-Mails) auf asymmetrische Verschlüsselungsverfahren, denn symmetrische Verschlüsselungsverfahren basieren auf Schlüsselaustausch und dieser ist problematisch in einem öffentlichen Netwerk, weshalb man symmetrische Verschlüsselungsverfahren z.B. AES eher in geschlossenen Systemen nutzt, wo man Schlüssel 100% sicher austauschen kann z.B. innerhalb einer Bank.

D.h. würde man einen Quantencomputer bauen der z.B. den Shor-Algorithmus ausführen könnte, dann wäre es möglich diese öffentlichen Netzwerkverschlüsselungen zu brechen und sich dann in eine Online Bankingtransaktion einzuschleichen und die Daten abzufangen: Konsequenz: Man müsste das Internet abschalten. Denn wie gesagt, Verfahren wie AES basieren auf Schlüsselaustausch und das ist alleine in öffentlichen Netwerken nicht praktikabel oder?

Und das One Time Pad selbst kann man ja auch nicht nutzen, um eine sichere Kommunikation zu ermöglichen, auch wenn es theoretisch 100% sicher ist, denn 1. Man braucht für jede Übertragung einen neuen Schlüssel 2. Der Schlüssel muss genauso lang sein wie die Nachricht

Stell dir vor du hast eine Bank mit 600.000 Kunden. Jeder führt im Monat 3 Transaktionen online durch, dann müsste man 1,8 Millionen sehr lange Schlüssel im Monat generieren und übertragen und das jetzt nochmal multiplizieren mit 30 Millionen, es gibt ja nicht nur diese eine Bank in Deutschland und das würde doch sehr große Datenmengen beanspruchen oder? Denn z.B. über derzeitige asymmetrische Verschlüsselungen werden die Transaktionen durch einen verschlüsselten Kanal gesichert, man muss nicht für jede Nachricht einen neuen Schlüssel generieren.

Das heißt sollte es dazu kommen wäre dann die Quantenkryptographie das einzige, was uns gegen Quantencomputer schützen könnte. AES ist zwar auch (wie ich es gelesen habe) sicher gegen 256 Bit Schlüssel aber trotzdem kann es ja sein, dass irgendwann ein Quantencomputer gebaut wird und ein Algortihmus, der es schafft, solche großen Schlüssel durch brute force herauszufinden. Der Mensch kann ja zur Zeit auch nicht bemannte Raketen auf Planeten außerhalb dieser Galaxie schicken, aber wer sagt dass das auch in 1000 Jahren immer noch so sein wird? Genauso sehe ich das mit Quantencomputern.

Danke für deine kompetenten und hilfreichen Antworten und deine Geduld