Schnelles Verfahren fuer Faktorisierung

[curiosity81]

Moin,

wollt mal nachfragen ob Zahlentheoretiker anwesend sind? Desweiteren meine Frage:

Wie hoch ist die Wahrscheinlichkeit fuer einen schnellen Algorithmus zur Primfaktorzerlegung von Zahlen?

Aktuell ist nicht bewiesen, dass das Problem schwer ist - so wie nicht bewiesen ist, dass NP != P - es koennte also mglw einen Algorithmus geben welcher ein Produkt aus zwei sehr grossen Primzahlen in seine zwei Primfaktoren in polynomieller Zeit zerlegt. Dann waeren die aktuellen Kryptowaehrungen nur noch Makulatur. Logisch, wenn die Beantwortung dieser Frage einfach waere, dann wuesste die NSA als erste davon, und ich bezweifel, dass die bessere Methoden haben als zb Bruce Schneier:

http://www.schneierfacts.com/.

Was denkt ihr darueber?

[klabaki]

Der Shor-Algorithmus löst das Faktorisierungsproblem in Polynomialzeit.
Im Prinzip könnte es sogar einen Algorithmus geben, der das ohne Quantencomputer schafft. Das Gegenteil ist wie gesagt noch nicht bewiesen.

Was mich aber mehr interessiert als dieses P-NP-Problem ist die Frage nach den physikalischen Grenzen der Berechenbarkeit.

Das Universum ist bekanntlich quantisiert. Und durch die Quanten ist eine obere Grenze für die Anzahl der Rechenschritte festgelegt, die in einer bestimmten Zeit durchgeführt werden können.
Wenn die Komplexität eines Kryptosystems größer ist als diese Grenze, dann halte ich es für sicher. Und dann ist es mir auch egal, ob die Komplexität durch ein Polynom beschrieben wird oder exponentiell ist.

[curiosity81]

Richtig, der Quantencomputer ist wohl aktuell am erfolgsversprechendsten. Wobei ja bisher, wenn ich mich richtig entsinn, nicht mehr als die Zahl 15 faktorisiert wurde.

Die Empfindlichkeit eines solchen verschraenkten Systems scheint ja quadratisch anzusteigen (siehe http://www.golem.de/1104/82516.html), wobei ich nicht sicher bin ob dies ein gutes Zeichen ist. Schlechter als ein lineares Antsteigen allemal.

In gewisser Weise schlagen zwei Herzen in meiner Brust, einerseits sind QCs in vielen Wissenschaftszweigen sinnvoll, sie koennen aber, so glaube ich, ein exponentielles Problem trotzdem nicht in polynomieller Zeit entscheiden. Soll heissen, eine echte nichtdeterministische TM ist wohl auch mit dem QC nicht machbar (wenn das Unsinn ist was ich schreibe, verbessert mich). Auf der anderen Seite waere ein Umstieg auf neue Kryptosysteme unangenehm.

Edit:

Das Universum ist bekanntlich quantisiert. Und durch die Quanten ist eine obere Grenze für die Anzahl der Rechenschritte festgelegt, die in einer bestimmten Zeit durchgeführt werden können.
Wenn die Komplexität eines Kryptosystems größer ist als diese Grenze, dann halte ich es für sicher. Und dann ist es mir auch egal, ob die Komplexität durch ein Polynom beschrieben wird oder exponentiell ist.

Nun, man kann sicherlich eine obere Schranke angeben, unter der Annahme man wuerde das gesamte Universum als QC missbrauchen. Wenn du solch eine Kryptosystem erschaffen koenntest, dann waerst du wahrscheinlich sicher. Aber wiederum muss bei der Abschaetzung bekannt sein, was die beste Methode zum Brechen des Systems ist und welche Komplexitaet sie aufweist. Ohne dieses Wissen kann man nur spekulieren, nach dem Motto: es ist nicht bewiesen ob es eine bessere mathematische (!) Methode gibt.

[Polarstorm]

Ohne wirklich mehr als 1% verstanden zu haben von dem was ihr so schreibt:

Ist die "Lösung" bzw die "Antwort" nicht eindeutig ? Und zwar die Plankzeit ?

Da es keine kleinere physikalisch sinnvolle Zeit/Größe gibt, sind die Grenzen doch klar vorgegeben oder nicht ?

[curiosity81]

Ohne wirklich mehr als 1% verstanden zu haben von dem was ihr so schreibt:

Ist die "Lösung" bzw die "Antwort" nicht eindeutig ? Und zwar die Plankzeit ?

Da es keine kleinere physikalisch sinnvolle Zeit/Größe gibt, sind die Grenzen doch klar vorgegeben oder nicht ?

Soweit ich weiss liegt den Planckgroessen die aktuelle Physik zu grunde. D.h. wenn du z.B. einen Teilchenbeschleuniger baust welcher als Mikroskop die Plancklaenge aufloesen koennte, dann wuerde nach unserer aktuellen Physik die Menge der dazu notwendigen Energie zu einer Singularitaet, einem schwarzen Loch kolabieren. Bei diesen Skalen hoert einfach unsere Physik auf. Das bedeutet aber nicht, dass dort auch die reale Physik aufhoert, nur wir koennen mit der Mathematik, welche unserer aktuellen Physik zugrunde liegt, diesen Zustand nicht sinnvoll beschreiben. Das heisst aber nicht das dort nichts beschreibbares existiert, das richtige Modell fehlt halt noch.

Und nochmals, ja, man koennte bestimmt alles was man weiss ueber das Universum nutzen um eine Abschaetzung zu machen, jedoch ist einfach zuviel unbekannt, physikalisch (so aehnlich wie bei der Drake-Formel) und mathematisch.

[Polarstorm]

Na gut, da driften wir dann aber schon ins philisophische ab würde ich sagen. Denn die "reale" Physik ist nunmal unsere Physik (ich weiß, du meinst mit "real" das was quasi "hinter dem Vorhang" ist).

Die Frage ist doch ob es überhaupt sinnvoll ist über das "hinter dem Vorhang" zu spekulieren, denn "unsere" Physik ist nicht "falsch" wenn sie das wäre dann wäre die Welt nicht so wie sie ist.  Sie ist vielleicht noch nicht komplett, aber innerhalb ihrer Grenzen funktioniert sie und was ausserhalb ihrer Grenzn liegt wäre eine "neue" Physik.

Von daher halte ich es für müßig sich dieses Problem überhaupt zu stellen. Denn um es zu lösen müsste erstmal eine "neue" Physik erdacht werden und das passiert nicht "morgen".


Aber wie dem auch sei, ich wollte das eh nur mal einwerfen mit Planck, weil es euch vielleicht in euren Überlegungen weiterhilft.



Nachtrag: Über eine Frage mit den Mitteln unserer Physik nachzudenken, deren Antwort ausserhalb der uns bekannten Physik liegt ist hoffnungslos. Denn das "Werkzeug" das einem zur Konstruktion der Antwort an die Hand gegeben wird ist nicht geeignet um die Antwort zu konstruieren.

[curiosity81]

Na gut, da driften wir dann aber schon ins philisophische ab würde ich sagen. Denn die "reale" Physik ist nunmal unsere Physik (ich weiß, du meinst mit "real" das was quasi "hinter dem Vorhang" ist).

Die Frage ist doch ob es überhaupt sinnvoll ist über das "hinter dem Vorhang" zu spekulieren, denn "unsere" Physik ist nicht "falsch" wenn sie das wäre dann wäre die Welt nicht so wie sie ist.  Sie ist vielleicht noch nicht komplett, aber innerhalb ihrer Grenzen funktioniert sie und was ausserhalb ihrer Grenzn liegt wäre eine "neue" Physik.

Naja, das mit der Physik hat klabaki in die Diskussion gebracht. Mir ging es urspruenglich um die Mathematik. Da wurden ja z.B. erst vor kurzem Ergebnisse zur schwachen goldbachschen Vermutung veroeffentlicht. Hat sowas Konsequenzen fuer das Problem der Faktorisierung?

[lame.duck]

Wieso sollte die NSA, die Russen oder die Chinesen  nicht 'mehr' wissen können als Bruce Schneier? Ich glaube auch nicht das jemand mit entsprechenden Verbindungen derartiges Können (sp überhaupt möglich) für die Kompromittierung des Bitcoins verplempern würde. Spionage dürfte das eine sehr viel lukrativere Anwendung sein.

Hinzu kommt das das Verfahren allein noch lange nicht  hinreichend für hohe Sicherheit ist, es gibt offensichtlich Möglichkeiten valide aber für einen Angreifer schwache Schlüssel zu generieren.

http://de.wikipedia.org/wiki/Kleptographie

Zumindest bei SSL wurden da schon einige Implementationen als 'schwächlich' eingestuft.

[Chefin]

Wenn wir uns der realität etwas nähern ist es ziemlich leicht eine Aussage bzgl unknackbarer Verschlüsselungen zu finden.

Wir müssen dazu allerdings eine Annahme zugrunde legen: das alles Verschlüsselte irgendwann irrelevant wird. Sei es, weil alle Betroffenen tot sind oder es keine Strafe mehr dafür gibt. Oder sonst wie egal wird. Und als maximale Dauer solcher Zeiträume dürfte man ein Leben veranschlagen. Also 100 Jahre dürfte ausreichend sein.

Ich hatte mal einen Bericht eines Studenten gelesen der sich folgende Kette aufgebaut hat.

Jedes Atom ist ein Rechenkern, es gibt X Atome im Universum
Unsere Sonne hat eine Lebensdauer die momentan mit Y Jahren kalkuliert wird.
Ein Rechenkern kann maximal mit der Frequenz des Lichtes Z rechnen.

Z = 750THz = 7,5 * 10^14
Y = 11milliarden Jahre = 1,1 * 10^10
X = 10^80 aus den bisherigen Schätzungen abgeleitet.

Wir kommen also auf rund 9 * 10^104 Zyklen das entspricht dann 2^348. Es dürfte also nicht mehr möglich sein ein Passwort mit 2^349 Möglichkeiten zu brutforcen.

Asymetrische Verschlüsselung hat aber leider Einschränkungen, welche Schlüssel überhaupt möglich sind. Ein RSA1024 hat nicht 2^1024 Mögliche Schlüssel sondern bedeutend weniger.  Zusätzlich reduziert sich diese Anzahl durch Designfehler bzw Unzulänglichkeiten. Es ist schwer hier eine genaue Aussage zu machen, aber man geht davon aus, das RSA4096 ausreichend Reserven hat um auch in Zukunft real unknackbar zu sein.

Theoretisch ist jede Verschlüsselung knackbar. Aber wenn man reale Bedingungen zugrunde legt bzgl Rechengeschwindigkeit und Zeit, dann muss man auch den realen Bezug zum Sinn zugrunde legen. Und der Sinn endet ganz sicher mit dem Ende unserer Sonne. Wobei da nicht unbedingt auch unsere Zivilisation zuende sein muss. Aber das ist nun doch zu spekulativ und SF.

Daher mache ich mir keine Sorge um die Verschlüsselung des Bitcoins. Jedenfalls nicht real, höchstens theoretisiert.