Wer findet meine Primzahlen?

3124756
Erstie
Erstie
Beiträge: 17
Registriert: 18. Apr 2008 00:49

Wer findet meine Primzahlen?

Beitrag von 3124756 »

Ich habe hier das Produkt von zwei Primzahlen:

9944465363065134066379168192246982204369431689711920667061483862787527305659696242680585634845800116120470096976215782210989169662587507735721048944534267

Wer kann mir sagen was die Faktoren sind?

LucasR
Kernelcompilierer
Kernelcompilierer
Beiträge: 474
Registriert: 9. Jun 2009 09:55

Re: Wer findet meine Primzahlen?

Beitrag 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.

kbraden
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 15. Okt 2010 20:35

Re: Wer findet meine Primzahlen?

Beitrag 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

3124756
Erstie
Erstie
Beiträge: 17
Registriert: 18. Apr 2008 00:49

Re: Wer findet meine Primzahlen?

Beitrag von 3124756 »

p = 88653280850666539553299020942736413624552255495923312267925970594571706662243
q = 112172558845467326200076015125506219499787364755814322257682583151977987826569


n = 994446536306513406637916819224698220436943168971192066706148386278752730565969624268
0585634845800116120470096976215782210989169662587507735721048944534267

3124756
Erstie
Erstie
Beiträge: 17
Registriert: 18. Apr 2008 00:49

Re: Wer findet meine Primzahlen?

Beitrag 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.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Wer findet meine Primzahlen?

Beitrag 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 :?:
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Wer findet meine Primzahlen?

Beitrag 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.)

3124756
Erstie
Erstie
Beiträge: 17
Registriert: 18. Apr 2008 00:49

Re: Wer findet meine Primzahlen?

Beitrag 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.

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Wer findet meine Primzahlen?

Beitrag 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.

3124756
Erstie
Erstie
Beiträge: 17
Registriert: 18. Apr 2008 00:49

Re: Wer findet meine Primzahlen?

Beitrag 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.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Wer findet meine Primzahlen?

Beitrag 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 ;-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

fetzer
Kernelcompilierer
Kernelcompilierer
Beiträge: 522
Registriert: 1. Okt 2008 17:18

Re: Wer findet meine Primzahlen?

Beitrag 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

Benutzeravatar
kroimon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Okt 2009 00:12

Re: Wer findet meine Primzahlen?

Beitrag 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 :-)
~Stefan

Antworten

Zurück zu „Archiv“