Was tun mit Primzahlenformel?

[blobbo]

Hi, ich dachte das passt hier am besten rein
Mich würde mal interessieren, was genau man alles machen könnte wenn man eine Formel für alle Primzahlen findet..
Dabei weiß ich schon, dass, und auch ungefähr wie, bestimme Verschlüsselungen funktionieren und das diese dann leicht geknackt werden könnten. Nun interessiert mich aber eher konkret was man dann lustiges anstellen könnte ^^
Also z.B. könnte man dann einem Bankautomat was anhaben wenn man Zugang zu den Leitungen hätte? Oder könnte man usw... mir fällt gerade nichts mehr ein aber basiert vielleicht noch mehr auf der "Sicherheit" von Primzahlen und wo könnte man den größten Schaden anstellen oder das meiste Geld absahnen, illegal versteht sich, ich will jetzt nicht hören das man damit die Prämie für den Nobelpreis abräumt ^^

Bei guten Tips verrat ich euch auch die Formel ;p

 

[Corni]

"Einen Nobelpreis für Mathematik gibt es nicht" Wikipedia
Musste jetzt sein ^^

gruß Corni

 

[Heinzelotto]

Original von blobbo
Hi, ich dachte das passt hier am besten rein
Mich würde mal interessieren, was genau man alles machen könnte wenn man eine Formel für alle Primzahlen findet..
Dabei weiß ich schon, dass, und auch ungefähr wie, bestimme Verschlüsselungen funktionieren und das diese dann leicht geknackt werden könnten. Nun interessiert mich aber eher konkret was man dann lustiges anstellen könnte ^^
Also z.B. könnte man dann einem Bankautomat was anhaben wenn man Zugang zu den Leitungen hätte? Oder könnte man usw... mir fällt gerade nichts mehr ein aber basiert vielleicht noch mehr auf der "Sicherheit" von Primzahlen und wo könnte man den größten Schaden anstellen oder das meiste Geld absahnen, illegal versteht sich, ich will jetzt nicht hören das man damit die Prämie für den Nobelpreis abräumt ^^

Bei guten Tips verrat ich euch auch die Formel ;p

1. gibt keinen Nobelpreis, nur die Fields-Medaille
2. es gibt ziemlich viele algorithmen, um alle primzahlen herauszufinden. Dauert bloß manchmal lange.
3. Wenn deine Formel wirklich so toll ist und wunderbar erscheint, hast du (mit 99,999%iger Wahrscheinlichkeit) einen Fehler gemacht. Das musste ich am eigenen Leib erfahren, als ich dachte, einen Beweis zum Problem der Zwillingsprimzahlen gefunden zu haben
4. hat deine Methode zufällig was mit der sog. "Primfakultät" zu tun?

 

[blobbo]

Sorry nein ich hab eigentlich gar nichts das sollte ein Scherz sein
Aber ich wollt mich in den Ferien mal aus Interesse etwas dran probieren, nicht das ich glaub ich finde was Ich dachte vielleicht an die Abstände zwischen den Zahlen oder so... mal schaun
Naja aber trotzdem würd ich jetzt einfach gerne mal wissen was man (angenommen man kann jede Primzahl konstant schnell finden) für Möglichkeiten hätte Spaß zu haben und Geld zu machen.
Beispiele: Kann man dann vielleicht alle Handytelefonate abhören? Oder kann man theoretisch Onlinebanking Server hacken (ich hab irgendwie mal gelesen da wechselt irgendwas sehr schnell, vielleicht hat das ja was mit Primzahlen zu tun [sehr dummes Beispiel ] )?

 

[beavisbee]

Original von blobbo
[sehr dummes Beispiel ]

schön, dass du das selbst einsiehst...

Was erwartest du dir davon? Nur weil du einen Algorithmus baust, der Primzahlen findet, bist du nicht gleich irgend ein Ober-Hacker mit einem Schlüssel zur Macht oder so....

 

[blobbo]

Oho ja, bla...
Das waren alles schlechte Beispiele und ich hab auch nie behauptet dass man durch eine Primzahlformel zum Superhacker aufsteigt... nur weil meine Beispiele etwas in richtung schlechter Hackerfilm gehen musst du ja nicht gleich zickig werden
Aalso nochmal anders:

In welchen Bereichen würde durch die Entdeckung einer Primzahlenformel die meiste Panik ausgelöst und am schnellsten ein neues Sicherheitskonzept erdacht werden müssen? Und wo/wie könnte dort ein Bösewicht evtl. noch kommerziellen Nutzen draus ziehen?

PS: Ich hab nicht mal ansatzweise eine solche Formel und werde wohl auch nie eine finden aber es interessiert mich nunmal was man damit machen könnte bzw. wie groß die Schäden wären wenn eine solche Formel gefunden wird.

 

[Elderan]

Hallo,
was kann man machen, wenn man eine Formel findet die schnell alle Primzahlen liefert:
Gar nichts.


1. Es gibt genügend Verfahren, die dir sehr schnell Primzahlen liefern.

2.
Man kann die Anzahl der Primzahlen abschätzen, und zwar mit x/ln(x).

Ein 1024 Bit RSA-Key verwendet 512 Bit Primzahlen, mit der Abschätzung gibts als rund 10^151 Primzahlen zwischen 2^512 und 2^513.

Angenommen du findest eine Formel, die mit 1 Instruktion (1 Takt) die nächste Primzahl finden würde, und du würdest alle Primzahlen von 2^512 bis 2^513 durchlaufen, dann bräuchest du 10^151 Taktzyklen.
Bei 4 Kernen mit 3 Ghz pro Kern würdest du rund 10^130 Jahre brauche um alle Primzahlen zu durchlaufen, zum Vergleich, das Universium ist nur rund 10^10 Jahre alt, also brauchst du 10^120 mal länger als das Universum alt ist.
Bzw., viele symmetrischen Verfahren nutzen nur 128 Bit Keys.


Wie du siehst, ist so eine Formel absolut wertlos um irgendeinen Key oder ähnliches damit zu knacken.

Oder kann man theoretisch Onlinebanking Server hacken

Was hat das finden von Primzahlen bitte mit dem hacken (denke du verstehst darunter einbrechen) von Servern zu tun?

Kann man dann vielleicht alle Handytelefonate abhören?

Alle zwar nicht, aber die in der Nähe kann man mit dem richtigen Equipment schon heute abhören, sofern noch GSM verwendet wird (meistens der Fall).

Bevor da aber Fragen in die Richtung kommen: Bitte erstmal die Grundlagen in Kryptographie, Netzwerke, Betriebssysteme, Rechnerarchitektur, Programmierung anlesen.

Mich würde mal interessieren, was genau man alles machen könnte wenn man eine Formel für alle Primzahlen findet..

Du würdest dir einen Namen in der mathematischen Fachwelt machen, da schon seit vielen tausend Jahren nach solch einer Formel gesucht wird Formeln zur Generierung von Primzahlen
Nur bezweifel ich sehr, das du was finden wirst. Viele Personen mit sehr fundierten Kenntnissen in der Zahlentheorie haben es versucht und nicht das gefunden, was du dir erhoffst.

 

[metax.]

Eine Formel zum Finden von Primzahlen allein bringt dir nicht viel.

Viel fataler dagegen wäre es, wenn du schnelle Formeln für das Faktorisierungsproblem oder den diskreten Logarithmus hättest.

mfg, metax.

 

[blobbo]

Mh nagut, irgendwie hatte ich mir den Verlauf dieses Themas anders vorgestellt. Mein Professor (ja ich studiere 8o) meinte halt neulich, dass man sich viele Feinde machen würde wenn man eine solche Formel findet und ich dachte, das sich die gängigen Verschlüsselungen und die damit verbundenen Sicherheitssysteme dann wohl knacken lassen müssten. Ich hatte/hab halt nur keine Ahnung wo genau besagte Verschlüsselungen eingesetzt werden.
Aber danke Elderan, die Abschätzung bei 2. widerlegt dann wohl die Aussage mit den "vielen Feinden"...

 

[Heinzelotto]

du würdest dir allerdings auch viele freunde machen, da du mit einer formel zur Erzeugung beliebig großer Primzahlen auch beliebig lange Schlüssel für die asynchrone Verschlüsselung herstellen könntest.
Einen anderen 'Freund', den du dir machen könntest, ist die NSA

 

[Elderan]

Hallo,

Original von Heinzelotto
du würdest dir allerdings auch viele freunde machen, da du mit einer formel zur Erzeugung beliebig großer Primzahlen auch beliebig lange Schlüssel für die asynchrone Verschlüsselung herstellen könntest.

Das erstellen von Schlüsseln ist normalerweise das geringere Problem, man kann recht schnell 16 Kbit RSA-Keys finden. Da die Erzeugung von Keys relativ selten benötigt wird, wäre der Gewinn nicht so groß.

Viel problematischer bei der Public Key Kryptographie bzgl. großer Keys ist, dass der Rechenaufwand für die Verschlüsselung und besonders für die Entschlüsselung stark wächst, da der private Key eben vom public Key abhängt.
Und x^[1 kBit Zahl] lässt sich schneller berechnen als x^[10 kBit Zahl].

Wie gesagt, das finden von Keys ist eher unproblematisch, nur der Rechenaufwand für Ver/Entschlüsselung wächst entsprechend stark an.

Verschlüsselt man z.B. mit RSA 250 mal den selben Text/Wert, ergibt sich für die Keylängen folgende Zeit:
512: 0,015 Sek
1024: 0,031 Sek
2048: 0,125 Sek
4096: 0,421 Sek
8192: 1,562 Sek


Entschlüsselung mit RSA 10 mal den selben Text/Wert:
512: 0,006
1024: 0,03
2048: 0,21
4096: 1,29
8192: 10,7 Sek (!!)

Einen anderen 'Freund', den du dir machen könntest, ist die NSA

Erklär dies mal bitte genauer.

dass man sich viele Feinde machen würde wenn man eine solche Formel findet und ich dachte, das sich die gängigen Verschlüsselungen und die damit verbundenen Sicherheitssysteme dann wohl knacken lassen müssten.

Frag doch einfach den Prof., was für Feinde man sich machen würde.

Oder hat er evt. von einer Formel zur schnellen Primfaktorzerlegung gesprochen?

 

[Heinzelotto]

Original von Elderan
Erklär dies mal bitte genauer.

Das war eher scherzhaft gemeint, ist also nicht ganz ernst zu nehmen
Ich wollte darauf hinaus, dass irgendwelche Nachrichtendienste doch bestimmt sehr großes Interesse an Methoden zeigen würden, die in irgendeiner Weise das Entschlüsseln von Nachrichten vereinfachen würden

 

[blobbo]

Mh nein ich glaub nicht, er hatte irgendwas über die Laufzeit von Algorithmen erzählt und meinte beiläufig, dass für einen Primzahlalgorithmus eine logarithmische Laufzeit schon super wäre, am besten aber natürlich eine konstante und das man sich dann viele Feinde machen würde und man die Fields-Medaille oder irgendwas anderes gewinnen würde.
Mit einem konstanten Primalgorithmus könnte man doch einfach alle möglichen Zerlegungen recht schnell durchgehen oder nicht?
Und was würde sich denn in Bezug auf meine ursprüngliche Frage ändern wenn er von Primfaktorzerlegung gesprochen hätte?

 

[Elderan]

Hallo,

Original von blobbo
Mit einem konstanten Primalgorithmus könnte man doch einfach alle möglichen Zerlegungen recht schnell durchgehen oder nicht?

Orginal von Elderan
Man kann die Anzahl der Primzahlen abschätzen, und zwar mit x/ln(x).

Ein 1024 Bit RSA-Key verwendet 512 Bit Primzahlen, mit der Abschätzung gibts als rund 10^151 Primzahlen zwischen 2^512 und 2^513.

Angenommen du findest eine Formel, die mit 1 Instruktion (1 Takt) die nächste Primzahl finden würde, und du würdest alle Primzahlen von 2^512 bis 2^513 durchlaufen, dann bräuchest du 10^151 Taktzyklen.
Bei 4 Kernen mit 3 Ghz pro Kern würdest du rund 10^130 Jahre brauche um alle Primzahlen zu durchlaufen, zum Vergleich, das Universium ist nur rund 10^10 Jahre alt, also brauchst du 10^120 mal länger als das Universum alt ist.

Einfach alle fraglichen Primzahlen durchzutesten scheidet aus, es sind einfach zuviele für den doch relativ kruzen 1024 Bit Key.

Und was würde sich denn in Bezug auf meine ursprüngliche Frage ändern wenn er von Primfaktorzerlegung gesprochen hätte?

Es gibt Algorithmen die das können, die erfordern aber den Einsatz von Quantencomputern ^^.

Würdest du aber solch eine Formel finden, mit der man eine Zahl in deren Primfaktoren zerlegen könnte, wobei die Formel schnell ist (z.B. kurze+konstante Zeit für beliebige Zahlen), dann könntest du damit sehr viel anfangen.
Dann wäre kein asymmetrisches Verfahren, zumindest keins was heutzutage bekannt ist, noch sicher.
E-Banking/E-Commerce wäre unsicher, da SSL nicht mehr wirkt. Banknetzwerke müssten dann von asymmetrischer wieder auf symmetrische Verschlüsselung zurücksatteln.
SSH, VPN wäre so nicht mehr sicher, und und und
Eben überalle wo asymmetrische Verschlüsselung drin steckt, ließe sich knacken.

 

[Mechanius]

Ich denk wenn die Formel fertig ist und hier OpenSource veröffentlicht wurde, findet bestimmt einer eine mehr oder weniger sinnvolle Anwendung.

Also mach dich an die Arbeit!

MfG M

 

[jmc]

afaik wurde das schon soo lange versucht und es gibt keine Resultate ausser Ansätze, dass es nicht möglich ist...

 

[Lesco]

Original von Elderan
Eben überalle wo asymmetrische Verschlüsselung drin steckt, ließe sich knacken.

Genauer: überall wo das Faktorisierungsproblem für die Sicherheit sorgt, ECC oder Systeme, die den diskreten Logarithmus nutzen, wären dadurch nicht zwangsweise(auch wenn die Algorithmen _manchmal_ übertragbar sind) betroffen.

 

[blobbo]

Ok, danke euch dann meinte er wohl das Faktorisieren von Primzahlen. Da werd ich mich in den Ferien mal reinlesen =)

Achso und es ist ja mal dermaßen balastend wie hier immer gleich irgendwer ankommt und sagt, "öh hacken is nicht wie im fernsehn du hast ja keine Ahnung" oder "glaub mir mal da gibts genug Leute die das schon probiert haben, du kannst es gleich lassen" usw.
Damit ist wirklich keinem geholfen und ich seh auch kein Problem darin sich mit Dingen zu beschäftigen, die andere schon gemacht haben oder die vermeindlich sinnlos sind. Manmanman...