diff options
| -rw-r--r-- | ChangeLog | 8 | ||||
| -rw-r--r-- | PublicKey/RSA.py | 38 | ||||
| -rwxr-xr-x | src/_fastmath.c | 72 |
3 files changed, 94 insertions, 24 deletions
@@ -12,9 +12,11 @@ * Merged the _rsa.c and _dsa.c files into a single accelerator module, _fastmath.c. - * Added fast isPrime() function to _fastmath, cutting the time to - generate a 1024-bit prime by a factor of 10. (Contributed by - Joris Bontje.) + * Speed improvements: Added fast isPrime() function to _fastmath, + cutting the time to generate a 1024-bit prime by a factor of 10. + Optimized the C version of RSA decryption to use a longer series + of operations that's roughly 3x faster than a single + exponentiation. (Contributed by Joris Bontje.) * Added support to RSA key objects for blinding and unblinding data. (Contributed by Joris Bontje.) diff --git a/PublicKey/RSA.py b/PublicKey/RSA.py index a9149d7..6613910 100644 --- a/PublicKey/RSA.py +++ b/PublicKey/RSA.py @@ -10,7 +10,7 @@ # or implied. Use at your own risk or not at all. # -__revision__ = "$Id: RSA.py,v 1.15 2003-04-03 20:36:13 akuchling Exp $" +__revision__ = "$Id: RSA.py,v 1.16 2003-04-04 14:59:19 akuchling Exp $" from Crypto.PublicKey import pubkey @@ -38,6 +38,11 @@ def generate(bits, randfunc, progress_func=None): obj.p=pubkey.getPrime(bits/2, randfunc) if progress_func: progress_func('q\n') obj.q=pubkey.getPrime((bits/2)+difference, randfunc) + # p shall be smaller than q (for calc of u) + if obj.p>obj.q: + (obj.p, obj.q)=(obj.q, obj.p) + if progress_func: progress_func('u\n') + obj.u=pubkey.inverse(obj.p, obj.q) obj.n=obj.p*obj.q # Generate encryption exponent @@ -48,21 +53,29 @@ def generate(bits, randfunc, progress_func=None): return obj def construct(tuple): - """construct(tuple:(long,long)|(long,long,long)|(long,long,long,long,long)) - : RSAobj - Construct an RSA object from a 2-, 3-, or 5-tuple of numbers. + """construct(tuple:(long,) : RSAobj + Construct an RSA object from a 2-, 3-, 5-, or 6-tuple of numbers. """ obj=RSAobj() - if len(tuple) not in [2,3,5]: + if len(tuple) not in [2,3,5,6]: raise error, 'argument for construct() wrong length' for i in range(len(tuple)): field = obj.keydata[i] setattr(obj, field, tuple[i]) + if len(tuple) >= 5: + # Ensure p is smaller than q + if obj.p>obj.q: + (obj.p, obj.q)=(obj.q, obj.p) + + if len(tuple) == 5: + # u not supplied, so we're going to have to compute it. + obj.u=pubkey.inverse(obj.p, obj.q) + return obj class RSAobj(pubkey.pubkey): - keydata=['n', 'e', 'd', 'p','q'] + keydata = ['n', 'e', 'd', 'p', 'q', 'u'] def _encrypt(self, plaintext, K=''): if self.n<=plaintext: raise error, 'Plaintext too large' @@ -123,7 +136,7 @@ class RSAobj(pubkey.pubkey): return construct((self.n, self.e)) class RSAobj_c(pubkey.pubkey): - keydata = ['n', 'e', 'd', 'p', 'q'] + keydata = ['n', 'e', 'd', 'p', 'q', 'u'] def __init__(self, key): self.key = key @@ -153,8 +166,8 @@ class RSAobj_c(pubkey.pubkey): if 'q' not in state: self.key = _fastmath.rsa_construct(n,e,d) else: - p, q = state['p'], state['q'] - self.key = _fastmath.rsa_construct(n,e,d,p,q) + p, q, u = state['p'], state['q'], state['u'] + self.key = _fastmath.rsa_construct(n,e,d,p,q,u) def _encrypt(self, plain, K): return (self.key._encrypt(plain),) @@ -194,6 +207,11 @@ def generate_c(bits, randfunc, progress_func = None): p=pubkey.getPrime(bits/2, randfunc) if progress_func: progress_func('q\n') q=pubkey.getPrime((bits/2)+difference, randfunc) + # p shall be smaller than q (for calc of u) + if p>q: + (p, q)=(q, p) + if progress_func: progress_func('u\n') + u=pubkey.inverse(p, q) n=p*q # Generate encryption exponent @@ -201,7 +219,7 @@ def generate_c(bits, randfunc, progress_func = None): e=pubkey.getPrime(17, randfunc) if progress_func: progress_func('d\n') d=pubkey.inverse(e, (p-1)*(q-1)) - key = _fastmath.rsa_construct(n,e,d,p,q) + key = _fastmath.rsa_construct(n,e,d,p,q,u) return RSAobj_c(key) def construct_c(tuple): diff --git a/src/_fastmath.c b/src/_fastmath.c index f658b6b..08480e7 100755 --- a/src/_fastmath.c +++ b/src/_fastmath.c @@ -8,7 +8,7 @@ * dissemination and usage except those imposed by the laws of your * country of residence. * - * $Id: _fastmath.c,v 1.10 2003-04-04 14:28:39 akuchling Exp $ + * $Id: _fastmath.c,v 1.11 2003-04-04 14:59:19 akuchling Exp $ */ #include <stdio.h> @@ -79,6 +79,7 @@ typedef struct mpz_t d; mpz_t p; mpz_t q; + mpz_t u; } rsaKey; @@ -172,6 +173,7 @@ rsaEncrypt (rsaKey * key, mpz_t v) static int rsaDecrypt (rsaKey * key, mpz_t v) { + mpz_t m1, m2, h; if (mpz_cmp (v, key->n) >= 0) { return 1; @@ -180,6 +182,41 @@ rsaDecrypt (rsaKey * key, mpz_t v) { return 2; } + + if ((mpz_size (key->p) != 0) && (mpz_size (key->q) != 0) && + (mpz_size (key->u) != 0)) + { + /* fast path */ + mpz_init(m1); + mpz_init(m2); + mpz_init(h); + + /* m1 = c ^ (d mod (p-1)) mod p */ + mpz_sub_ui(h, key->p, 1); + mpz_fdiv_r(h, key->d, h); + mpz_powm(m1, v, h, key->p); + /* m2 = c ^ (d mod (q-1)) mod q */ + mpz_sub_ui(h, key->q, 1); + mpz_fdiv_r(h, key->d, h); + mpz_powm(m2, v, h, key->q); + /* h = u * ( m2 - m1 ) mod q */ + mpz_sub(h, m2, m1); + if (mpz_sgn(h)==-1) + mpz_add(h, h, key->q); + mpz_mul(h, key->u, h); + mpz_mod(h, h, key->q); + /* m = m2 + h * p */ + mpz_mul(h, h, key->p); + mpz_add(v, m1, h); + /* ready */ + + mpz_clear(m1); + mpz_clear(m2); + mpz_clear(h); + return 0; + } + + /* slow */ mpz_powm (v, v, key->d, key->n); return 0; } @@ -449,12 +486,14 @@ dsaKey_has_private (dsaKey * key, PyObject * args) PyObject * rsaKey_new (PyObject * self, PyObject * args) { - PyLongObject *n = NULL, *e = NULL, *d = NULL, *p = NULL, *q = NULL; + PyLongObject *n = NULL, *e = NULL, *d = NULL, *p = NULL, *q = NULL, + *u = NULL; rsaKey *key; - if (!PyArg_ParseTuple(args, "O!O!|O!O!O!", &PyLong_Type, &n, + if (!PyArg_ParseTuple(args, "O!O!|O!O!O!O!", &PyLong_Type, &n, &PyLong_Type, &e, &PyLong_Type, &d, - &PyLong_Type, &p, &PyLong_Type, &q)) + &PyLong_Type, &p, &PyLong_Type, &q, + &PyLong_Type, &u)) return NULL; key = PyObject_New (rsaKey, &rsaKeyType); @@ -463,6 +502,7 @@ rsaKey_new (PyObject * self, PyObject * args) mpz_init (key->d); mpz_init (key->p); mpz_init (key->q); + mpz_init (key->u); longObjToMPZ (key->n, n); longObjToMPZ (key->e, e); if (!d) @@ -470,19 +510,18 @@ rsaKey_new (PyObject * self, PyObject * args) return (PyObject *) key; } longObjToMPZ (key->d, d); - if (p) + if (p && q && u) { - if (q) - { - longObjToMPZ (key->p, p); - longObjToMPZ (key->q, q); - } + longObjToMPZ (key->p, p); + longObjToMPZ (key->q, q); + longObjToMPZ (key->u, u); } /*Py_XDECREF(n); Py_XDECREF(e); Py_XDECREF(d); Py_XDECREF(p); - Py_XDECREF(q); */ + Py_XDECREF(q); + Py_XDECREF(u); */ return (PyObject *) key; } @@ -494,6 +533,7 @@ rsaKey_dealloc (rsaKey * key) mpz_clear (key->d); mpz_clear (key->p); mpz_clear (key->q); + mpz_clear (key->u); PyObject_Del (key); } @@ -534,6 +574,16 @@ rsaKey_getattr (rsaKey * key, char *attr) } return mpzToLongObj (key->q); } + else if (strcmp (attr, "u") == 0) + { + if (mpz_size (key->u) == 0) + { + PyErr_SetString(PyExc_AttributeError, + "rsaKey instance has no attribute 'u'"); + return NULL; + } + return mpzToLongObj (key->u); + } else { return Py_FindMethod (rsaKey__methods__, |