Gesucht: BigNum Modul

[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

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

[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

[problembär]

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

[Leonidas]

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.

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.

[numerix]

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

[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

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

[numerix]

... die in Python schon eingebaute - lies dir doch mal die Liste der builtin-functions von Python durch, dann findest du sie selbst ...

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

[sma]

Python ist aber viel toller, denn die `pow()`-Funktion kann das auch

Cool. Wieder was gelernt.

Stefan

[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

[Dill]

wenn du pow einen 3. parameter 'm' mitgibst wird eine modulare exponentiation durchgeführt. das ist nicht dasselbe wie

Code: Alles auswählen

c = a**b 
c = c % m

wo ja erstmal normal exponiert wird.

deine zahlen sind übrigens nicht wirklich groß.

[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:

Code: Alles auswählen

0.025866985321
167.054143906

[Leonidas]

Ich glaube der OP hat das Interesse am BigNum-Modul verloren...

[hendrikS]

@numerix: Bemerkenswerter Vergleich. Der Performanceunterschied ist gewaltig. Gut zu wissen.

[numerix]

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