Hallo zusammen,
da ich gerade dabei bin ein RSA-Programm in Python zu implementieren, möchte ich mal fragen, ob es ein BigNum Modul für Python gibt. Ich weiß das Python schon von Haus aus mit großen Zahlen umgehen kann, aber es ist sehr, sehr langsam.
Schon bei RSA64 dauert das Entschlüsseln eines! (1) Zeichens bis über die Grenze der Lächerlichkeit hinaus lange. Um genau zu sein: auf einem Core Duo (3.3GHz) mit 4GB Arbeitsspeicher dauert es 22 min. Wohlgemerkt, für ein Zeichen! Das Verschlüsseln hingegen funktioniert nahezu in Nullzeit. Um die Fragen vorzubeugen - nein, ich mache nichts falsch. Bei RSA ist das auch kaum möglich.
zum Verschlüsseln: (k ** e) % n
zum Entschlüsseln: (c ** d) % n
Falls jemand also ein BigNum Modul kennt, würde cih mich freuen, davon zu erfahren.
Danke schon mal.
Gruß
darkelf
Gesucht: BigNum Modul
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Da stimmt irgendwas nicht: rsa benötigt bei mir zwar 3 Minuten zum generieren von 1024-Bit-Keys, aber das Verschlüsseln funktioniert ohne sichtbare Zeitverzögerung (für "foo") und das Entschlüsseln dauert auch weit weniger als 1 Sekunde.
Und dabei hat mein Laptop die Hälfte deines RAMs und gerade mal 1.5 GHz, also nichtmal die Hälfte deiner CPU-Leistung.
Und dabei hat mein Laptop die Hälfte deines RAMs und gerade mal 1.5 GHz, also nichtmal die Hälfte deiner CPU-Leistung.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Hier geht es auch um sowas:
http://www.python-forum.de/topic-19235.html
http://www.cypherspace.org/adam/rsa/python.html
http://www.amk.ca/python/code/crypto.html
HTH
http://www.python-forum.de/topic-19235.html
http://www.cypherspace.org/adam/rsa/python.html
http://www.amk.ca/python/code/crypto.html
HTH
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Nein, die nutzen da auch nur die Datentypen, die Python mitbringt (das siehst du auch daran, dass dort kein C-Code dabei ist und dass dort wirklich nur die in Python miegelieferten Sachen importiert werden). Die Python Datentypen sind schnell genug wenn man es nur mal ausprobieren will.Darkelf hat geschrieben:Dein Link verweist ja auf ein RSA modul (welches einer BigLib gleichkommt).
Die haben RSA auch selbst implementiert, genauso wie du. Nur dass deren Implementation drastisch schneller ist.Darkelf hat geschrieben:Ich habe RSA selbst implementiert und daher fehlte mir das.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Oh doch, du machst was falsch. Das ist nämlich die denkbar schlechteste Möglichkeit, um a^b mod n zu berechnen. Das Stichwort lautet "modular binary exponentiation". Das wird z.B. in dem von Leonidas erwähnten rsa-Modul verwendet. Und wenn deren Algorithmus erheblich schneller ist als deiner, dann muss deiner wirklich schlecht sein, denn deren Implementation ist äußerst schwach optimiert - da ist noch eine Menge herauszuholen. Meine eigene Implementation der modularen Exponentation ist dreimal so schnell wie die aus dem rsa-Modul und damit fast genauso schnell wie die in Python schon eingebaute - lies dir doch mal die Liste der builtin-functions von Python durch, dann findest du sie selbst ...Darkelf hat geschrieben:Um die Fragen vorzubeugen - nein, ich mache nichts falsch. Bei RSA ist das auch kaum möglich.
zum Verschlüsseln: (k ** e) % n
zum Entschlüsseln: (c ** d) % n
Noch ein Gedanke: Man könnte Jython benutzen, um da die Java-BigInteger-Implementierung zu benutzen. Diese hat eine modPow()-Methode, mit der man effizient RSA implementieren kann. Natürlich könnte man bei Java dann auch gleich den "echten" RSA-Algorithmus (und viele weitere Cryptofunktionen der JCA) benutzen. Und wenn das nicht reicht, gibt es noch BouncyCastle...
Stefan
Stefan
@sma: Wir wissen mittlerweile das Du Java ganz toll findest. Python ist aber viel toller, denn die `pow()`-Funktion kann das auch:
Code: Alles auswählen
In [250]: pow?
Type: builtin_function_or_method
Base Class: <type 'builtin_function_or_method'>
String Form: <built-in function pow>
Namespace: Python builtin
Docstring:
pow(x, y[, z]) -> number
With two arguments, equivalent to x**y. With three arguments,
equivalent to (x**y) % z, but may be more efficient (e.g. for longs).
numerix hat geschrieben:... die in Python schon eingebaute - lies dir doch mal die Liste der builtin-functions von Python durch, dann findest du sie selbst ...
Jetzt hast du's verraten ...BlackJack hat geschrieben:@sma: Wir wissen mittlerweile das Du Java ganz toll findest. Python ist aber viel toller, denn die `pow()`-Funktion kann das auch:
Mache ich etwas falsch, oder woher kommen die Werte?
Oh, das ist schon schneller:
Code: Alles auswählen
In [6]: timeit.Timer("pow(123,123)").timeit()
Out[6]: 8.4111371040344238
In [7]: timeit.Timer("pow(123,123) % 2").timeit()
Out[7]: 9.8553869724273682
In [8]: timeit.Timer("123**123").timeit()
Out[8]: 0.23765897750854492
In [9]: timeit.Timer("123**123 % 2").timeit()
Out[9]: 0.22961616516113281
Code: Alles auswählen
In [12]: timeit.Timer("pow(123,123,2)").timeit()
Out[12]: 1.877849817276001
wenn du pow einen 3. parameter 'm' mitgibst wird eine modulare exponentiation durchgeführt. das ist nicht dasselbe wie
wo ja erstmal normal exponiert wird.
deine zahlen sind übrigens nicht wirklich groß.
Code: Alles auswählen
c = a**b
c = c % m
deine zahlen sind übrigens nicht wirklich groß.
http://www.kinderpornos.info
Code: Alles auswählen
from time import time
t0 = time()
for b in xrange(1,10):
for e in xrange(1000,100000,100):
r = pow(b,e,17)
print time()-t0
t0 = time()
for b in xrange(1,10):
for e in xrange(1000,100000,100):
r = b**e % 17
print time()-t0
Code: Alles auswählen
0.025866985321
167.054143906
Und pow(a,b,m) ist so gut optimiert, dass eine eigene Implementation - leider - nicht lohnt. Vor einiger Zeit haben jerch und ich im Zuge der Lösung von PRIC unabhängig voneinander einige Zeit in die Optimierung einer eigenen Implementation hineingesteckt und sind beide zu dem Ergebnis gekommen, dass man selbst bei Verwendung von psyco gerade so (nicht ganz) an die Performance von pow() herankommt.hendrikS hat geschrieben:@numerix: Bemerkenswerter Vergleich. Der Performanceunterschied ist gewaltig. Gut zu wissen.