RSA-Verschlüsselung

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Pythonaya
User
Beiträge: 90
Registriert: Sonntag 26. Januar 2003, 11:34
Wohnort: Großbeeren (nahe Berlin)

Freitag 7. Mai 2004, 16:24

Kennt ihr das RSA-Verschlüsselungssystem?

Mit Hilfe der RSA-Formeln kann man nämlich Nachrichten über einen "public key", der aus zwei primzahlen besteht verschlüsseln.
Bisher gibt es noch kein bekanntes Entschlüsselungsverfahren, welches ohne diese beiden Primzahlen auskommt.
Die Entschlüsselung durch Bruteforcer dauert zu lange.

Jetzt sagt ihr euch wahrscheinlich: Tolles System!
Das Ding hat nur einen Haken, dass wenn du es wirklich sicher benutzen willst, du mindestens zwei primzahlen a 100 Stellen brauchst.
Und hier die Tüftelaufgabe: "Baut mal ein Programm, welches 100 Stellen lange Primzahlen berechnet!!!"

Viel Spaß, der Code würde mich interessieren,
Flo
Zuletzt geändert von Pythonaya am Samstag 8. Mai 2004, 09:02, insgesamt 2-mal geändert.
lionking
User
Beiträge: 28
Registriert: Mittwoch 28. April 2004, 16:03

Freitag 7. Mai 2004, 16:49

tja das problem ist wohl, dass python nur 16-stellige real-zahlen unterstützt...
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Freitag 7. Mai 2004, 17:29

keine programmiersprache unterstützt eine Zahl mit 100 signifikante stellen

da musst du schon über andere wege die primzahl berechnen

nur wie musst du mich nicht fragen :)

hab zwar ein buch in dem "factoring into primes" beschrieben ist, leider versteh ich nicht gerade viel davon :/.

gruss
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Freitag 7. Mai 2004, 18:05

Hi rayo,
keine programmiersprache unterstützt eine Zahl mit 100 signifikante stellen
bei Python könnens auch 1000 stellen sein :)

Code: Alles auswählen

In [20]: a=10**1000
 
In [21]: print a
100000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000

Gruß

Dookie

[edit]Zwecks Übersichtlichkeit des Threads die Zahl auf mehrere Zeilen zerteilt[/edit]
Zuletzt geändert von Dookie am Samstag 8. Mai 2004, 00:00, insgesamt 1-mal geändert.
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Freitag 7. Mai 2004, 18:11

uiiii wie macht das python?

normalerweise hört doch die zahl bei 32 oder 64bit auf.

mmm setzt python intern automatisch mehrere Zahlen aneinander?

gruss
lionking
User
Beiträge: 28
Registriert: Mittwoch 28. April 2004, 16:03

Freitag 7. Mai 2004, 18:19

http://www.uni-mainz.de/~pommeren/Krypt ... aksalg.pdf

da gibts was ich weiss nich ob du damit was anfangen kannst, ich konnte es jedenfalls nicht...

vlt. kann mir ja jemand helfen, abe ich denke übers i-net wird das zu kompliziert :?

http://fsmat.at/~pdoersek/files/fba-pzidazt.pdf
nochwas allgemeiner über primzahlen, auch aks algoritmus und rsa-verschlüsselung
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Freitag 7. Mai 2004, 19:06

Hi. Vielleicht hilft dir ja auch das hier weiter:
http://de.wikipedia.org/wiki/Primzahlen
http://de.wikipedia.org/wiki/Mersenne-Primzahl

Die größte bisher bekannte Primzahl ist übrigens (2**20996011)-1 . Die Meldung dazu hab ich damals bei heise gelesen und versucht, diese Zahl einmal ganz genau auszurechen. Das lustige: ausgerechnet ist die Zahl in ca. 5 Sekunden, aber wenn ich die Zahl in einen String umwandeln will, damit ich sie in eine Datei speichern kann, bräuchte ich über 3 Tage. Ich habs dann abgebrochen gehabt... :wink:
Pythonaya
User
Beiträge: 90
Registriert: Sonntag 26. Januar 2003, 11:34
Wohnort: Großbeeren (nahe Berlin)

Freitag 7. Mai 2004, 22:52

Tja,
bisher kam ja eine Menge feedback zu dem Thema an!
Ich bastel jetzt schon seit nem knappen Tag an einer ersten zur Berechnung von extrem langen Primzahlen.

Das Problem mit der Speichergrenze von Variablen könnte man z.B lösen, indem man einfach .txt Dateien benutzt.
So ergibt sich aber das Problem, dass die rechnerischen Kapazitäten ebenfalls ein starkes Minimum an Speicher für diese kompexe Rechnung aufweisen. Dieses Problem könnte man mit Hilfe von divisionen und float-Zahlen lösen, indem man die Zahlen, die an der Rechnung teilnehmen z.B. dividiert werden, um sie dann später "in eine Datei zu multiplizieren"

Trotzdem kann das Problem der Speichergrenze nicht vollständig gelöst werden, oder?
Hat jemand vielleicht eine Idee für einen Sourcecode um eine 100-stellige Primzahl auszurechnen (eigentlich müsste sie ca. 125 Stellen haben, um die Entschlüsselug vollständig auszuschließen)

MFG,
Flo
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Freitag 7. Mai 2004, 23:27

bleibt noch eine Frage offen, 100 Dezimalstellen oder 100 Binärstellen?


Gruß

Dookie
hans
User
Beiträge: 728
Registriert: Sonntag 22. September 2002, 08:32
Wohnort: Sauerland
Kontaktdaten:

Freitag 7. Mai 2004, 23:34

Dookie hat geschrieben:bei Python könnens auch 1000 stellen sein :)
Hi Dookie

ich hoffe du hast die Nullen nachgezählt.

Code: Alles auswählen

echo "0000....0000" | wc  -c
hat mir erzählt dass das 1001 sind? Das wäre dann eine zuviel oder? Zu deiner Rettung sei gesagt, dass echo ein CR erzeugt. Ich glaub, ich geh erst mal schlafen :wink:

Hans[/code]
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Samstag 8. Mai 2004, 00:05

google spuckt zur "grosse primzahlen" ja auch ne ganze Menge aus :)
http://www.google.de/search?q=grosse%20primzahlen

Gruß

Dookie
Pythonaya
User
Beiträge: 90
Registriert: Sonntag 26. Januar 2003, 11:34
Wohnort: Großbeeren (nahe Berlin)

Samstag 8. Mai 2004, 09:01

Jaaa, aber selber generieren macht schlauer!
Und außerdem ist es sicherer, wenn das Programm zum ent- und verschlüsseln die Keys selbst generiert!
bleibt noch eine Frage offen, 100 Dezimalstellen oder 100 Binärstellen?
Ich meinte Dezimalstellen!

Bisher habe ich zwar einen Generator gebastelt, welcher auch funzt und den ich dann die Primzahlen in eine Datei schreiben lassen wollte, aber leider ist mein PC dann nach ca. 6 Stunden generieren kläglich krepiert!
NEIIIIIIN 6 Stunden keinen PC für umsonst!

Schade, dass es für Primzahlen keine Formel gibt *ggg*
aber das macht ja die Primzahlen so unberechenbar und interessant!

MFG,
Flo
Dakkareth
User
Beiträge: 5
Registriert: Freitag 14. Mai 2004, 20:57

Freitag 14. Mai 2004, 21:08

Ich habs noch nicht selbst probiert, aber eigentlich dürfte es kein Problem sein - mit einem L am Ende definierte Zahlen können was weiß ich wie viele tausend dezimalstellen haben. Sie zu verarbeiten kann zwar je nach operation etwas dauern, aber es geht ziemlich gut.

a= 19234<200 stellen>2987
print a**15

Gibt nen ziemlichen Wust an Zahlen aber dauert nur Bruchteile von Sekunden. Wenn man den Trick des stufenweisen Potenzierens modulo n anwendet, sollte die Rechenzeit nicht das größte Problem darstellen, zumindest auf den heutigen Rechnern.

Zum Finden von so großen Primzahlen gibt es glücklicherweise probabilistische Verfahren wie den Miller-Rabin-Test, mit dem man zwar nicht die Primalität einer Zahl beweisen kann, aber doch dafür sorgen kann, dass eine was-weiß-ich-wie-große Zahl mit 99,99999% (beliebige Sicherheit) Wahrscheinlichkeit eine Primzahl ist.


Eine eigene RSA-Implementation zu schreiben steht auch auf meiner Liste irgendwo ;)
reggid
User
Beiträge: 120
Registriert: Dienstag 8. Oktober 2002, 19:04
Wohnort: Dinslaken
Kontaktdaten:

Samstag 15. Mai 2004, 07:45

Dieser Javascript sieht doch recht hilfreich aus:
http://www.jjam.de/JavaScript/Mathemati ... ahlen.html
Zumindestens kann das Programm ne Menge und auch große Primzahlen finden!

PS: Mit solchen Algorithmen kann man nicht viel anfangen, hol dir dein Buch über Zahlentheorie und eine gute Tasse Kaffee, aber was besonders wichtig ist, viel Zeit und Geduld
Dakkareth
User
Beiträge: 5
Registriert: Freitag 14. Mai 2004, 20:57

Samstag 15. Mai 2004, 11:13

Wenn Englisch kein Problem ist, kann ich zum Beispiel folgendes Buch empfehlen:
Countinho, S.C., The mathematics of ciphers – number theory and RSA cryptography, Natick, Massachusetts, Verlag A K Peters, 1999
Antworten