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
RSA-Verschlüsselung
-
- User
- Beiträge: 773
- Registriert: Mittwoch 5. November 2003, 18:06
- Wohnort: Schweiz
- Kontaktdaten:
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
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
-
- Python-Forum Veteran
- Beiträge: 2010
- Registriert: Freitag 11. Oktober 2002, 18:00
- Wohnort: Salzburg
- Kontaktdaten:
Hi rayo,
Gruß
Dookie
[edit]Zwecks Übersichtlichkeit des Threads die Zahl auf mehrere Zeilen zerteilt[/edit]
bei Python könnens auch 1000 stellen seinkeine programmiersprache unterstützt eine Zahl mit 100 signifikante stellen
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.
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
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
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...
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...
-
- User
- Beiträge: 90
- Registriert: Sonntag 26. Januar 2003, 11:34
- Wohnort: Großbeeren (nahe Berlin)
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
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
-
- User
- Beiträge: 728
- Registriert: Sonntag 22. September 2002, 08:32
- Wohnort: Sauerland
- Kontaktdaten:
Hi DookieDookie hat geschrieben:bei Python könnens auch 1000 stellen sein
ich hoffe du hast die Nullen nachgezählt.
Code: Alles auswählen
echo "0000....0000" | wc -c
Hans[/code]
-
- Python-Forum Veteran
- Beiträge: 2010
- Registriert: Freitag 11. Oktober 2002, 18:00
- Wohnort: Salzburg
- Kontaktdaten:
google spuckt zur "grosse primzahlen" ja auch ne ganze Menge aus
http://www.google.de/search?q=grosse%20primzahlen
Gruß
Dookie
http://www.google.de/search?q=grosse%20primzahlen
Gruß
Dookie
-
- User
- Beiträge: 90
- Registriert: Sonntag 26. Januar 2003, 11:34
- Wohnort: Großbeeren (nahe Berlin)
Jaaa, aber selber generieren macht schlauer!
Und außerdem ist es sicherer, wenn das Programm zum ent- und verschlüsseln die Keys selbst generiert!
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
Und außerdem ist es sicherer, wenn das Programm zum ent- und verschlüsseln die Keys selbst generiert!
Ich meinte Dezimalstellen!bleibt noch eine Frage offen, 100 Dezimalstellen oder 100 Binärstellen?
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
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
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
-
- User
- Beiträge: 120
- Registriert: Dienstag 8. Oktober 2002, 19:04
- Wohnort: Dinslaken
- Kontaktdaten:
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
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
-
- User
- Beiträge: 90
- Registriert: Sonntag 26. Januar 2003, 11:34
- Wohnort: Großbeeren (nahe Berlin)
Hey,
ich habe grad mal ein kleines Programm
für die Verschlüsselung gebastelt...
Leider habe ich noch ein Problem,
was auch diese komische Ausgabe erklähren sollte...
Der Code ist auch kürzbar und nicht perfekt...
Für Verbesserungsvorschläge bin ich immer offen
MFG,
Flo
ich habe grad mal ein kleines Programm
für die Verschlüsselung gebastelt...
Leider habe ich noch ein Problem,
was auch diese komische Ausgabe erklähren sollte...
Der Code ist auch kürzbar und nicht perfekt...
Code: Alles auswählen
from string import find, printable
def Teilerfremd(a,b):
for c in range(2,b):
if a%c==b%c==0:
return 0
else:
return 1
p=input("p eingeben: ")
q=input("q eingeben: ")
print " ----------------------- "
n=q*p
fi=(p-1)*(q-1)
print "Daraus ergeben sich:"
print " n =",n
print "fi =",fi
print " ----------------------- "
print "Für e kommen in Frage:"
a=2
while 1:
if Teilerfremd(a,fi)==1 and a!=p and a!=q:
print a,
if a==1000:
break
a+=1
print
e=input("e eingeben: ")
print " ----------------------- "
d=0
while (e*d%fi)!=1:
d+=1
if d==e:
d+=1
print "Daraus ergibt sich d:"
print " d = ",d
print " ----------------------- "
text=raw_input("Geben sie den Text ein:\n")
for zeichen in text:
print zeichen,":",find(printable,zeichen),"**",e,"%",n
MFG,
Flo