RSA-Verschlüsselung

Pythonaya · 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

lionking · Freitag 7. Mai 2004, 16:49

tja das problem ist wohl, dass python nur 16-stellige real-zahlen unterstützt...

rayo · 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 · 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]

rayo · 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 · 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 · 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...

Pythonaya · 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 · Freitag 7. Mai 2004, 23:27

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

Gruß

Dookie

hans · 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

Hans[/code]

Dookie · 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 · 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 · 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 · 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 · 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

Pythonaya · Sonntag 11. Juli 2004, 12:54

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

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

Für Verbesserungsvorschläge bin ich immer offen

MFG,
Flo