Seite 1 von 1
Gesucht: BigNum Modul
Verfasst: Montag 22. Juni 2009, 18:28
von Darkelf
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
Verfasst: Montag 22. Juni 2009, 19:01
von Leonidas
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.
Verfasst: Montag 22. Juni 2009, 19:04
von Darkelf
Hi Leonidas,
danke, du hast mir meine Frage beantwortet.
Dein Link verweist ja auf ein RSA modul (welches einer BigLib gleichkommt). Ich habe RSA selbst implementiert und daher fehlte mir das.
Vielen Dank.
Gruß
darkelf
Verfasst: Montag 22. Juni 2009, 19:09
von problembär
Verfasst: Montag 22. Juni 2009, 19:11
von Leonidas
Darkelf hat geschrieben:Dein Link verweist ja auf ein RSA modul (welches einer BigLib gleichkommt).
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:Ich habe RSA selbst implementiert und daher fehlte mir das.
Die haben RSA auch selbst implementiert, genauso wie du. Nur dass deren Implementation drastisch schneller ist.
Re: Gesucht: BigNum Modul
Verfasst: Montag 22. Juni 2009, 19:45
von numerix
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
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 ...
Verfasst: Sonntag 28. Juni 2009, 17:13
von sma
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
Verfasst: Sonntag 28. Juni 2009, 19:03
von BlackJack
@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).
Verfasst: Montag 29. Juni 2009, 09:17
von numerix
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 ...
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:
Jetzt hast du's verraten ...
Verfasst: Mittwoch 1. Juli 2009, 09:30
von sma
BlackJack hat geschrieben:Python ist aber viel toller, denn die `pow()`-Funktion kann das auch
Cool. Wieder was gelernt.
Stefan
Verfasst: Mittwoch 1. Juli 2009, 10:35
von snafu
Mache ich etwas falsch, oder woher kommen die Werte?
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
Oh, das ist schon schneller:
Code: Alles auswählen
In [12]: timeit.Timer("pow(123,123,2)").timeit()
Out[12]: 1.877849817276001
Verfasst: Mittwoch 1. Juli 2009, 10:49
von Dill
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ß.
Verfasst: Mittwoch 1. Juli 2009, 13:27
von numerix
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
Output:
Verfasst: Mittwoch 1. Juli 2009, 14:05
von Leonidas
Ich glaube der OP hat das Interesse am BigNum-Modul verloren...
Verfasst: Mittwoch 1. Juli 2009, 14:55
von hendrikS
@numerix: Bemerkenswerter Vergleich. Der Performanceunterschied ist gewaltig. Gut zu wissen.
Verfasst: Mittwoch 1. Juli 2009, 15:43
von numerix
hendrikS hat geschrieben:@numerix: Bemerkenswerter Vergleich. Der Performanceunterschied ist gewaltig. Gut zu wissen.
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.