Seite 1 von 1

Wer findet meine Primzahlen?

Verfasst: 11. Dez 2011 22:05
von 3124756
Ich habe hier das Produkt von zwei Primzahlen:

9944465363065134066379168192246982204369431689711920667061483862787527305659696242680585634845800116120470096976215782210989169662587507735721048944534267

Wer kann mir sagen was die Faktoren sind?

Re: Wer findet meine Primzahlen?

Verfasst: 11. Dez 2011 23:35
von LucasR
Bei einer Zahl der Größenordnung 10^154? Ich glaub das machen jetzt hier die wenigsten mal eben so... Auch wenn es wahrscheinlich inzwischen immerhin berechenbar ist.

Re: Wer findet meine Primzahlen?

Verfasst: 12. Dez 2011 01:08
von kbraden
2007 wurde eine Faktorisierung einer 512-Bit Zahl in einem Monat berechnet. Das war damals aktuelle Hardware, aber mehrere davon und vmtl. auch kein ganz einfacher trial&error-Algorithmus (ist schon spaet, keine Lust mehr einzulesen). Ich schaetze jedenfalls dass das heute auf aktueller Hardware auch noch ne Weile dauert... ;)

Quelle

Re: Wer findet meine Primzahlen?

Verfasst: 15. Dez 2011 02:41
von 3124756
p = 88653280850666539553299020942736413624552255495923312267925970594571706662243
q = 112172558845467326200076015125506219499787364755814322257682583151977987826569


n = 994446536306513406637916819224698220436943168971192066706148386278752730565969624268
0585634845800116120470096976215782210989169662587507735721048944534267

Re: Wer findet meine Primzahlen?

Verfasst: 15. Dez 2011 02:51
von 3124756
Ich bin von der Sicherheit von RSA überhaupt nicht überzeugt.

Mit ein paar IBM Blade Serverschränken und einer Datenbank, kann jeder einfach das Produkt aller 512bit oder 1024bit Primzahlen ausrechnen und mit den Faktoren speichern. Es gibt einen Chatmitschnitt von Manning (der in Militärhaft) in dem er Angibt, das RSA gebrochen werden kann, wenn es wichtig genug ist.

Meiner Meinung nach müsste die gesamte Fachwelt von einer Kryptokrise reden.

Re: Wer findet meine Primzahlen?

Verfasst: 15. Dez 2011 12:02
von oren78
3124756 hat geschrieben:Ich bin von der Sicherheit von RSA überhaupt nicht überzeugt.
Da bist du garantiert nicht der erste :idea:
3124756 hat geschrieben:Mit ein paar IBM Blade Serverschränken (...), kann jeder...
Zum Glück hat auch jeder sowas in seiner 1x1 m Abstellkammer rumstehen ;-)
3124756 hat geschrieben:Meiner Meinung nach müsste die gesamte Fachwelt von einer Kryptokrise reden.
Dann wende dich doch an DIE und nicht an das d120.de Forum :?:

Re: Wer findet meine Primzahlen?

Verfasst: 15. Dez 2011 14:23
von Maeher
Mit ein paar IBM Blade Serverschränken und einer Datenbank, kann jeder einfach das Produkt aller 512bit oder 1024bit Primzahlen ausrechnen und mit den Faktoren speichern.
Viel Spaß :)

Das sind ziemlich viele Primzahlen und selbst mit ein paar mehr IBM Blade Serverschränken brauchst du da etwas länger als man sich Gedanken drüber machen muss.

Ganz davon abgesehen, dass der nötige Speicherplatz für deine Datenbank bei weitem alles übersteigt was auch nur theoretisch möglich ist. (Die Anzahl an zu speichernden bits übersteigt bei weitem die Anzahl der Atome im Universum.)

Re: Wer findet meine Primzahlen?

Verfasst: 15. Dez 2011 16:04
von 3124756
hast du dazu auch nen beweis ?

und was wenn ich mich darauf einschränke die Produkte und Fraktoren von den gängigen Implementationen zu brechnen. bitlänge 512 1024 2048 und 4096 und dazu beschränke ich mich noch auf die primzahlen die so ein Primzahlfinde Algorithmus ausspuckt. Dann ist meine Menge schon sehr viel kleiner und ich kann meine Datenbank aufbauen.

Re: Wer findet meine Primzahlen?

Verfasst: 15. Dez 2011 18:25
von Maeher
Nur die Primzahlen für 512bit reichen schon aus um dir jede Möglichkeit das zu speichern zu zerhauen.

Die "Primzahlfinde Algorithmen" wählen gängiger Weise zufällige Zahlen und prüfen ob sie prim sind, das hilft dir Also auch nicht weiter.

Es gibt deutlich effizientere Verfahren, RSA zu brechen als das, welches du vorschlägst. Insbesondere kann in subexponentieller Zeit faktorisiert werden.

Selbst diese Verfahren sind allerdings bisher für empfohlene Sicherheitsparameter nicht wirklich durchführbar.


Es ist durchaus denkbar, dass irgendjemand einmal einen Polynomilazeit-Algorithmus für die Faktorisierung findet und damit (unter anderem) RSA bricht, keine Frage.
Da auch keine Reduktion von RSA auf das Faktorisierungsproblem bekannt ist, wäre es sogar denkbar, dass man RSA bricht ohne Faktorisierung zu brechen.

In keinem Fall aber wird es durch stupide Auflistung möglicher Faktoren passieren.

Re: Wer findet meine Primzahlen?

Verfasst: 18. Dez 2011 04:09
von 3124756
der primzahlenfindealgorithmus von openssl, macht ein paar einschränkungen bei den möglichen zahlen. er sucht zahlen bei denen das produkt schwer zu faktorisieren ist. also er wählt zahlen bei denen davon ausgegangen wird, das gängige faktorisierungsalgorithmen besonders lange brauchen.

Es kann sein das du recht hast, das es nicht möglich sein kann alle Produkte auch nur von 512 bit Zahlen zu berechnen. Aber ich kann das erst glauben wenn ich das mal nachgerechnet habe. Blöderweise lag mir Wahrscheinlichkeitsrechnung noch nie besonders am Herzen.

Und was ist wenn ich mich weiter einschränke, dann rechne ich eben nur im abstand von 100 Primzahlen alle produkte aus. dann hab ich das Problem der Faktorzerlegung effektiv verkleinert.

Re: Wer findet meine Primzahlen?

Verfasst: 18. Dez 2011 11:45
von oren78
3124756 hat geschrieben:Und was ist wenn ich mich weiter einschränke, dann rechne ich eben nur im abstand von 100 Primzahlen alle produkte aus. dann hab ich das Problem der Faktorzerlegung effektiv verkleinert.
Ist dir bewusst was du da sagst? Also zunächst haben wir 512 Bit, bzw.: \(2^{512}\) Faktorisierungsmöglichkeiten, als Ausgangslage.
So jetzt kommst du mit dem "Trick" die Produkte zu eliminieren, dann haben wir \(2^{512-\lambda}\), mit \(\lambda << 256\).
Zur Erinnerung, die Anzahl der Atome im Universum ist ca. \(2^{80}\), noch weitere Fragen oder Vorschläge...???

Mal GANNNNNNNNNZ abgesehen davon, ich kenn keine Institution die allen ernstes RSA mit weniger als 2048 Bit einsetzt,
von daher überdenke nochmal deine Idee ;-)

Re: Wer findet meine Primzahlen?

Verfasst: 18. Dez 2011 11:53
von fetzer
Du kannst mit dem Primzahlsatz[1] einfach bestimmen, wieviele Primzahlen du ungefähr bei 512 Bit hast: \(\pi(2^{512}) = \frac{2^{512}}{ln(2^{512})} = 1.9*10^{151}\). Jetzt hast du die Anzahl und kannst damit weiterrechnen, wie lange du brauchen würdest, um alle Zahlen miteinander zu multiplizieren (wenn meine Erinnerung an Komibinatorik noch richtig ist müsste das \(n+k-1 \choose k\) sein, wobei k=2 und \(n=1.9*10^{151}\)) und wie viel Platz ein solcher Index einnehmen würde (eine Zeile hat 3*512Bit: 1536*1.805*10^382=2.77248*10^385 Bit = 3.4656*10^384 Byte = 3.4656*10^378 MB = 3.4656*10^375 GB)
Das Problem ist aber insofern bekannt, dass es inzwischen von jeder Regierung Empfehlungen an Schlüsselgrößen gibt, die sich nach den aktuellen technischen Möglichkeiten richten. 512Bit als Schlüsselgröße ist in diesem Zusammenhang deutlich zu klein und von der Verwendung wird auch überall abgeraten. Einen guten Überblick findest du beispielsweise unter [2].

[1] http://de.wikipedia.org/wiki/Primzahlsatz
[2] http://www.keylength.com

Re: Wer findet meine Primzahlen?

Verfasst: 19. Dez 2011 01:12
von kroimon
fetzer hat geschrieben:Du kannst ... snip ... 3.4656*10^375 GB ...
:!: In diesem Forum fehlt definitiv der Like-Button! Danke für die Mühe :-)