nicht angemeldet
Klass. Kryptographie und Quantencomputer
Hi allerseits!
Mit Quantencomputern soll es ja irgendwann möglich sein, klassische Kryptographie zu knacken. Ich interessiere mich jetzt nicht sonderlich für die neuen Möglichkeiten, die Quantencomputer *für* die Kryptographie bieten werden (Quantenkryptographie), sondern für die Gefahren für die "klassische", also eigentlich (?) die gegenwärtige Kryptographie.
Auf den einschlägigen Webseiten findet man immer wieder Hinweise darauf, dass das hauptsächliche Angriffsziel der Forscher wohl die Primfaktorzerlegung ist, und dass ein Forscher wohl auch schon einen für Quantencomputer optimierten Algorithmus erfunden hat. Jetzt braucht man nur noch einen leistungsfähigen Quantencomputer. ;-)
Nach meinem Verständnis ist es aber nun so, dass die Primfaktorzerlegung "nur" für die asymmetrischen Verschlüsselung relevant ist.
Meine Frage ist daher, sind denn auch symmetrische Verfahren, z.B. Blowfish, von Quantencomputern gefährdet? Mir ist klar, dass man in diesen Bereichen nichts mit Sicherheit sagen kann, und dass es immer unvorhergesehene Entwicklungen und Durchbrüche geben kann, aber ich meine hier: "Nach dem heutigen Wissensstand". Diese Frage ist auf keiner der von mir besuchten Seiten angesprochen worden, und mir fehlen die mathematischen Kenntnisse, um das auch nur annähernd einschätzen zu können.
Über Antworten würde ich mich sehr freuen.
FooBar
-
Moin!
Auf den einschlägigen Webseiten findet man immer wieder Hinweise darauf, dass das hauptsächliche Angriffsziel der Forscher wohl die Primfaktorzerlegung ist, und dass ein Forscher wohl auch schon einen für Quantencomputer optimierten Algorithmus erfunden hat. Jetzt braucht man nur noch einen leistungsfähigen Quantencomputer. ;-)
Nach meinem Verständnis ist es aber nun so, dass die Primfaktorzerlegung "nur" für die asymmetrischen Verschlüsselung relevant ist.
Meine Frage ist daher, sind denn auch symmetrische Verfahren, z.B. Blowfish, von Quantencomputern gefährdet?Alle Kryptographieverfahren sind grundsätzlich erstmal durch die Steigerung der Rechengeschwindigkeit gefährdet.
Wau Holland hat das mal in folgender Geschichte umschrieben:
"Da kam einmal bei einer Besichtigung ein Bankdirektor zu mir und erzählte stolz, die Verschlüsselung seiner Bankseite wäre so stark, da würde man tausend Jahre dran rechnen müssen. Woraufhin ich entgegnete: 'Toll, dann ist die Seite ja in 16 Jahren knackbar!'. Der Direktor wurde etwas weiß und fragte, wie ich darauf käme. Und ich rechnete ihm vor: '15 Jahre tue ich nichts, sondern warte darauf, dass die Rechner, die heute noch 1000 Jahre brauchen, alle 18 Monate doppelt so schnell werden. Nach 15 Jahren sind sie 1024mal so schnell und brauchen dann nur noch ein Jahr rechnen'."Auch Quantencomputer sind in dieser Beziehung kein Hexenwerk, sondern einfach nur ziemlich schnell - und auch ziemlich parallel, weil in einer Rechenoperation aus allen Eingangswerten gleichzeitig alle Ergebnisse entstehen. Funktionierende Quantencomputer würden also die Rechengeschwindigkeit extrem steigern und erst dadurch gewisse Angriffe gegen Kryptographie praktikabel werden lassen.
Insofern kommt es eigentlich nur darauf an, für das mathematische Problem "Blowfish" einen passenden Quantenalgorithmus zu finden, der von den Eigenschaften des Quantencomputers profitiert. Und natürlich braucht man auch den Quantencomputer selbst. :)
- Sven Rautenberg
--
"Love your nation - respect the others."-
Hi Sven,
herzlichen Dank für deine Einschätzung!
Grüße
FooBar -
Hallo Sven,
Ich hab' mich noch nicht viel mit Quantencomputern beschäftig, da ich gerade eine Vorlesung dazu höre, könnte ich in einem halben Jahr sicher mehr dazu sagen.
Dennoch halte ich Deine Einschätzung für teilweise falsch.Quantencomputer stellen ein neues Rechenmodell zur Verfügung, das so mit herkömmlichen Rechnern nicht realisierbar ist. Das Modell kann zwar nicht mehr entscheiden, die Zeit- und Platzschranken für manche Probleme ändern sich jedoch. Wenn nun ein Verschlüsselungsverfahren auf einem Problem basiert, für das das gilt, so ist das Verschlüsselungsverfahren möglicherweise unsicher.
Bei RSA ist genau das der Fall, mit einem Quantencomputer lässt sich das Faktorisierungsproblem in Polynomialzeit lösen, mit einem herkömmlichen ist das (bislang) nicht möglich.Für andere Verschlüsselungsverfahren muss das erstmal nicht gelten.
Auch Quantencomputer sind in dieser Beziehung kein Hexenwerk, sondern einfach nur ziemlich schnell - und auch ziemlich parallel, weil in einer Rechenoperation aus allen Eingangswerten gleichzeitig alle Ergebnisse entstehen. Funktionierende Quantencomputer würden also die Rechengeschwindigkeit extrem steigern und erst dadurch gewisse Angriffe gegen Kryptographie praktikabel werden lassen.
Genau diese Aussage ist falsch. Quantencomputer wären wohl erstmal überhaupt nicht extrem schnell, wenn man das in Opterationen/Sekunde misst. Lediglich für bestimmte Probleme (bisher meines Wissens Suchen in unsortierten Mengen und eben Faktorisierung) existieren für sie Algorithmen, die in weniger Schritten zum Ziel kommen.
Insofern kommt es eigentlich nur darauf an, für das mathematische Problem "Blowfish" einen passenden Quantenalgorithmus zu finden, der von den Eigenschaften des Quantencomputers profitiert.
Ob das überhaupt geht, ist wohl alles andere als sicher.
Grüße
Daniel
-
Hallo Daniel,
Deine Kritik an Svens Ausführungen geht zum Teil am Thema vorbei, ich zitiere den OP:
Meine Frage ist daher, sind denn auch symmetrische Verfahren, z.B. Blowfish, von Quantencomputern gefährdet?
Insofern gehe ich davon aus, dass Sven sich auf symmetrische Verfahren bezieht und ...
Bei RSA ist genau das der Fall, mit einem Quantencomputer lässt sich das Faktorisierungsproblem in Polynomialzeit lösen, mit einem herkömmlichen ist das (bislang) nicht möglich.
... RSA natürlich überhaupt nicht zur Debatte steht, da es sich dabei um ein asymmetrisches Verfahren handelt - und diese Problematik ist dem OP bekannt:
Nach meinem Verständnis ist es aber nun so, dass die Primfaktorzerlegung "nur" für die asymmetrischen Verschlüsselung relevant ist.
[...]
sonst stimmst Du doch Sven zu:
Insofern kommt es eigentlich nur darauf an, für das mathematische Problem "Blowfish" einen passenden Quantenalgorithmus zu finden, der von den Eigenschaften des Quantencomputers profitiert.
Ob das überhaupt geht, ist wohl alles andere als sicher.Dafür bietet der Quantencomputer möglicherweise neue Einwegfunktionen, deren Wert "leicht" zu berechnen ist, während dem Endergebnis die Ausgangswerte nur "schwer" zu entnehmen sind - die klassische Grundlage asymmetrischer Verfahren.
Freundliche Grüße
Vinzenz
-
Hallo Vinzenz,
Insofern kommt es eigentlich nur darauf an, für das mathematische Problem "Blowfish" einen passenden Quantenalgorithmus zu finden, der von den Eigenschaften des Quantencomputers profitiert.
Ob das überhaupt geht, ist wohl alles andere als sicher.Dafür bietet der Quantencomputer möglicherweise neue Einwegfunktionen, deren Wert "leicht" zu berechnen ist, während dem Endergebnis die Ausgangswerte nur "schwer" zu entnehmen sind - die klassische Grundlage asymmetrischer Verfahren.
Gibt es denn irgendwelche Empfehlungen, ob und wie stark man heutzutage die Schlüssellänge erhöhen sollte, um die potenziellen Gefahren zu minimieren? Oder wären solche Empfehlungen sowieso völlig bedeutungslos, weil
- die heutigen Computer mangels Rechenleistung sowieso nicht in praktikabler Rechenzeit dazu in der Lage wären?
- weil kein Mensch auch nur annähernd einschätzen könnte, welche Leistungsfähigkeit in Quantencomputern und den zugehörigen Algorithmen stecken wird?
- weil bisher noch nicht mal ein brauchbarer Quantencomputer gebaut wurde und das sowieso alles nur Paranoia ist? ;-)
Daniels Antwort deute ich so, dass es seiner Meinung nicht einmal sicher sei, *ob* es tatsächlich einen Algorithmus *gibt*, der symmetrische Kryptoverfahren knackt *und* der die Möglichkeiten der Quantencomputer optimal nutzt. Und selbst wenn es einen gebe, es nicht unbedingt trivial sei, ihn zu finden.
Und, bitte nicht lachen, meine Ursprungsfrage ergab sich aus der Überlegung, ob es besonders schlau wäre, im Hinblick auf Quantencomputer schon heute auf symmetrische Verfahren auszuweichen, wo es möglich und praktikabel ist. Ähm... ;-)
FooBar
-
-
Moin!
Dennoch halte ich Deine Einschätzung für teilweise falsch.
Ich beziehe meine Informationen nur aus der Wikipedia. Deshalb kann es natürlich sein, dass diese populärwissenschaftliche Zusammenfassung eines komplexen Forschungsgebiets ihre Fehler hat.
Aber die Darstellung und meine Interpretation derselben passen prima in mein restliches Weltbild, also gehe ich erstmal von dessen Gültigkeit aus. :)
Quantencomputer stellen ein neues Rechenmodell zur Verfügung, das so mit herkömmlichen Rechnern nicht realisierbar ist.
Es wird behauptet, man könne Quantencomputer mit normalen Computern simulieren. Das geht natürlich nicht mit der mit Quanteneffekt erzielbaren Geschwindigkeit, erfolgt aber im Ergebnis vollständig.
Somit muß ich davon ausgehen, dass Quantencomputer keine neue Mathematik erfinden, sondern die bestehende nur etwas anders anwenden. Sozusagen das "MMX", diesmal nur eben mit Quantenmechanik statt mit SIMD-CPU-Befehlen.
Das Modell kann zwar nicht mehr entscheiden, die Zeit- und Platzschranken für manche Probleme ändern sich jedoch. Wenn nun ein Verschlüsselungsverfahren auf einem Problem basiert, für das das gilt, so ist das Verschlüsselungsverfahren möglicherweise unsicher.
Bei RSA ist genau das der Fall, mit einem Quantencomputer lässt sich das Faktorisierungsproblem in Polynomialzeit lösen, mit einem herkömmlichen ist das (bislang) nicht möglich.Und mit der Simulation eines Quantencomputers geht's eben auch nicht in polynomialer Zeit, sondern nur in exponentieller.
Das ändert aber nichts am Sinn meiner Aussage: Quantencomputer sind (wenn auch nur für manche Probleme) schneller, als die bisher bekannten CPUs. Und das ist für den Laien eigentlich auch eine vollkommen ausreichende Aussage, denn der wird Kryptoprogramme einfach nur anwenden und fragt sich binär: Ist das jetzt sicher, oder nicht?
Für andere Verschlüsselungsverfahren muss das erstmal nicht gelten.
Der Wikipedia-Artikel schreibt, dass man beispielsweise ein 8-Qubit-System mit allen 256 8-Bitkombinationen aufladen und damit dann eine Rechenoperation durchführen kann, die am Ende alle 256 Ergebnisse enthält.
Wenn ich mir das mal so vorstelle: Man baut einen Quantencomputer, der soviele Qubits hat, dass man in der Rechenzeit von "einmal MD5" alle Hashwerte von Strings mit bis zu 128 Zeichen berechnen kann, um so den korrekten Eingangswert zum vorliegenden Ausgangswert zu finden.
Natürlich muß man das erstmal quantenkompatibel bauen, aber der Beschleunigungseffekt wird doch recht deutlich. Und ich glaube kaum, dass soetwas nicht irgendwann Wahrheit werden kann.
- Sven Rautenberg
--
"Love your nation - respect the others."-
Hallo Sven,
Und mit der Simulation eines Quantencomputers geht's eben auch nicht in polynomialer Zeit, sondern nur in exponentieller.
Ja, aber der exponentielle Aufwand entsteht gerade bei der Simulation, weil Du zur Darstellung eines Q-Bits exponentiell viele Bits benötigst. (Exponentiell in der Anzahl der darauf ausgeführten Operationen).
Wie gesagt kann man mit Quantenkomputern nichts neues berechnen, daher kann man sie auch simulieren. Die Simulation aber ist extrem aufwendig.Sagen Dir Nicht-Deterministische Maschinen etwas? Mit denen kann man z.B. alle NP-Vollständingen Probleme in Polynomialzeit lösen. Man kann diese Maschinen auch simulieren, aber diese Simulation benötigt dann wieder exponentiellen Aufwand. (Jedenfalls wie bei all diesen Dingen nach bisherigem Kenntnisstand, es ist ja durchaus möglich, dass es schnelle deterministische Algorithmen gibt.)
Quantencomputer stellen so eine Art abgeschwächten Nichtdeterminismus zur Verfügung.Der Wikipedia-Artikel schreibt, dass man beispielsweise ein 8-Qubit-System mit allen 256 8-Bitkombinationen aufladen und damit dann eine Rechenoperation durchführen kann, die am Ende alle 256 Ergebnisse enthält.
Das ist wohl eine sehr vereinfachende Vorstellung. In der Praxis ist es wohl sehr schwierig, aus diesen Ergebnissen dann eines herauszubekommen, dass man haben will.
Wenn man einen Quantenzustand misst, bekommt man ja prinzipiell erst mal einen der möglichen Zustände zufällig. Wenn nun eines der exponentiell vielen Ergebnisse die Lösung ist, die man haben will, bekommt man die da so ohne weiteres nicht raus.Natürlich muß man das erstmal quantenkompatibel bauen, aber der Beschleunigungseffekt wird doch recht deutlich. Und ich glaube kaum, dass soetwas nicht irgendwann Wahrheit werden kann.
Nun, das ist eben nicht so sicher. Quantencomputer sind ein weiterer Ansatz um solche Probleme zu lösen. Ob und für welche Probleme das Funktionieren wird ist aber meines Wissens kaum absehbar.
Und wenn es tatsächlich gelingt, Quantencomputer zu bauen und einen entsprechenden Algorithmus für ein Verschlüsselungsverfahren zu finden, dann kann man das Verfahren wegwerfen. Dann ist Knacken nämlich vergleichbar schnell wie Verschlüsseln. Es ist also nicht wie bei schnelleren Rechnern, dass man einfach die Schlüssellänge verdoppeln kann oder so.
Grüße
Daniel
-
-
Hallo Daniel,
Bei RSA ist genau das der Fall, mit einem Quantencomputer lässt sich das Faktorisierungsproblem in Polynomialzeit lösen, mit einem herkömmlichen ist das (bislang) nicht möglich.
Für andere Verschlüsselungsverfahren muss das erstmal nicht gelten.
Ich bin nicht wirklich "drin" in der Materie, aber ich hatte mal gelesen, dass das Faktorisieren bisher nur bis zur Zahl 15 klappt (d.h. es für größere Zahlen gar keinen Quantenalgorithmus gibt), weswegen das Knacken von RSA trotz Quantencomputer erstmal noch in ferner Zukunft liegen würde.
Viele Grüße,
Christian--
"I have always wished for my computer to be as easy to use as my telephone; my wish has come true because I can no longer figure out how to use my telephone." - Bjarne Stroustrup-
Hallo Christian,
Ich kann dir einen Algorithmus bieten, der alle Zahlen <= 15 in konstanzer Zeit faktorisiert ;-)
Der Algorithmus funktioniert wohl schon für beliebige Zahlen (sonst wäre er auch ein Witz). Nur hat man bisher nur einen Quantencomputer gebaut, mit dem man mit dem Algorithmus 15 faktorisieren konnte.
Grüße
Daniel
-
Hallo Daniel,
Ich kann dir einen Algorithmus bieten, der alle Zahlen <= 15 in konstanzer Zeit faktorisiert ;-)
D'oh. ;-)
Der Algorithmus funktioniert wohl schon für beliebige Zahlen (sonst wäre er auch ein Witz). Nur hat man bisher nur einen Quantencomputer gebaut, mit dem man mit dem Algorithmus 15 faktorisieren konnte.
Ah, wieder was gelernt. Nur noch eine Frage: Gibt es prinzipielle Probleme, einen Quantencomputer herzustellen (d.h. man hat noch keinen theoretischen Weg gefunden, genügend Q-Bits zu verbinden oder sonstwas), der mehr kann oder waren das bisher nur technische Probleme (d.h. man weiß zwar, wie man Atome etc. anordnen müsste, bekommt's bisher nur nicht hin)?
Viele Grüße,
Christian--
"I have always wished for my computer to be as easy to use as my telephone; my wish has come true because I can no longer figure out how to use my telephone." - Bjarne Stroustrup-
Hallo Christian,
Ah, wieder was gelernt. Nur noch eine Frage: Gibt es prinzipielle Probleme, einen Quantencomputer herzustellen (d.h. man hat noch keinen theoretischen Weg gefunden, genügend Q-Bits zu verbinden oder sonstwas), der mehr kann oder waren das bisher nur technische Probleme (d.h. man weiß zwar, wie man Atome etc. anordnen müsste, bekommt's bisher nur nicht hin)?
Ich meine, da gäbe es auch noch theoretische Probleme, abgesehen davon können praktische Probleme da natürlich auch noch auf theoretische Probleme führen, weil man erst noch merkt, dass die bisherige Theorie ab einer gewissen größe nicht mehr so richtig funktioniert.
Von der Physik dahinter habe ich aber praktisch keine Ahnung.Grüße
Daniel
-
-
-
-
-
-
Meine Frage ist daher, sind denn auch symmetrische Verfahren, z.B. Blowfish, von Quantencomputern gefährdet?
Es geht um einen Angriff auf asymmetrische Verfahren, da ist Rechenleistung wichtig. So weit ich weiss wird per asymmetrisches Verfahren nur ein neuer Schlüssel ausgetauscht, der Rest ist dann wieder symmetrisch.
Ein Freund von mir arbeitet im Uni Forschungszentrum Karlsruhe im Bereich Nanotechnologie, der meint, dass Quantencomputer noch einige Zeit (50 Jahre?) auf sich warten lassen dürften.
BTW - der hat ein "lustiges" Szenario für den Weltuntergang entwickelt: Kleine sich selbst reproduzierende Nano-Maschinen zerfressen die gesamte Erde und zurück bleibt ein Haufen nichtstuender Nano-Maschinen, ein Killer-Planet so zu sagen.
-
Tach,
BTW - der hat ein "lustiges" Szenario für den Weltuntergang entwickelt: Kleine sich selbst reproduzierende Nano-Maschinen zerfressen die gesamte Erde und zurück bleibt ein Haufen nichtstuender Nano-Maschinen, ein Killer-Planet so zu sagen.
ich vermute eher, er hat es schonmal an anderen Orten gelesen: http://en.wikipedia.org/wiki/Grey_goo.
mfg
Woodfighter
-