RSA/DSA in C

#include <stdio.h>
#include <string.h>
#include <Python.h>
#include <longintrepr.h> // for conversions
#include <gmp.h>

PyObject* _dsa_module;
PyObject* _dsa_dict;

void longObjToMPZ(mpz_t m, PyLongObject *p) {
  int size, i;
  mpz_t temp, temp2;
  mpz_init(temp);
  mpz_init(temp2);
  if (p->ob_size>0)
    size = p->ob_size;
  else
    size = -p->ob_size;
  for (i=0; i<size; i++) {
    mpz_set_ui(temp, p->ob_digit[i]);
    mpz_mul_2exp(temp2, temp, SHIFT * i);
    mpz_add(m, m, temp2);
  }
  mpz_clear(temp);
  mpz_clear(temp2);
}

PyObject* mpzToLongObj(mpz_t m) {
  // borrowed from gmpy
  int size = (mpz_sizeinbase(m, 2) + SHIFT - 1) / SHIFT;
  int i;
  PyLongObject *l = _PyLong_New(size);
  if (!l) {return NULL;}
  mpz_t temp;
  mpz_init_set(temp, m);
  for (i=0;i<size;i++){
    l->ob_digit[i] = (digit) (mpz_get_ui(temp) & MASK);
    mpz_fdiv_q_2exp(temp, temp, SHIFT);
  }
  i=size;
  while ((i>0) && (l->ob_digit[i-1] == 0)) i--;
  l->ob_size = i;
  mpz_clear(temp);
  return (PyObject*)l;
}

PyObject* dsaKey_new(PyObject*, PyObject*);

static PyMethodDef _dsa__methods__[] =
  {
    { "construct", dsaKey_new, METH_VARARGS },
    { NULL, NULL }
  };

typedef struct {
  PyObject_HEAD
  mpz_t y;
  mpz_t g;
  mpz_t p;
  mpz_t q;
  mpz_t x;
} dsaKey;

static int dsaSign(dsaKey *key, mpz_t m, mpz_t k, mpz_t r, mpz_t s) {
  if (mpz_cmp_ui(k, 2)<0 || mpz_cmp(k, key->q)>=0) {
    return 1;
  }
  mpz_t temp;
  mpz_init(temp);
  mpz_powm(r, key->g, k, key->p);
  mpz_mod(r, r, key->q);
  mpz_invert(s, k, key->q);
  mpz_mul(temp, key->x, r);
  mpz_add(temp, m, temp);
  mpz_mul(s, s, temp);
  mpz_mod(s, s, key->q);
  mpz_clear(temp);
  return 0;
}

static int dsaVerify(dsaKey *key, mpz_t m, mpz_t r, mpz_t s) {
  if (mpz_cmp_ui(r, 0)<=0 || mpz_cmp(r, key->q)>=0 ||
      mpz_cmp_ui(s, 0)<=0 || mpz_cmp(s, key->q)>=0)
    return 0;
  int result;
  mpz_t u1, u2, v1, v2, w;
  mpz_init(u1);
  mpz_init(u2);
  mpz_init(v1);
  mpz_init(v2);
  mpz_init(w);
  mpz_invert(w, s, key->q);
  mpz_mul(u1, m, w);
  mpz_mod(u1, u1, key->q);
  mpz_mul(u2, r, w);
  mpz_mod(u2, u2, key->q);
  mpz_powm(v1, key->g, u1, key->p);
  mpz_powm(v2, key->y, u2, key->p);
  mpz_mul(w, v1, v2);
  mpz_mod(w, w, key->p);
  mpz_mod(w, w, key->q);
  if (mpz_cmp(r, w) == 0)
    result=1;
  else
    result=0;
  mpz_clear(u1);
  mpz_clear(u2);
  mpz_clear(v1);
  mpz_clear(v2);
  mpz_clear(w);
  return result;
}

static void dsaKey_dealloc(dsaKey*);
static PyObject * dsaKey_getattr(dsaKey*, char*);
static PyObject * dsaKey__sign(dsaKey*, PyObject*);
static PyObject * dsaKey__verify(dsaKey*, PyObject*);
static PyObject * dsaKey_size(dsaKey*);
static PyObject * dsaKey_hasprivate(dsaKey*);

PyObject *dsaError; // raised on erros

static PyTypeObject dsaKeyType = {
  PyObject_HEAD_INIT(NULL)
  0,
  "dsaKey",
  sizeof(dsaKey),
  0,
  (destructor)dsaKey_dealloc, /* dealloc */
  0, /* print */
  (getattrfunc)dsaKey_getattr, /* getattr */
  0, /* setattr */
  0, /* compare */
  0, /* repr */
  0, /* as_number */
  0, /* as_sequence */
  0, /* as_mapping */
  0, /* hash */
  0, /* call */
};

static PyMethodDef dsaKey__methods__[] = {
  {"_sign", (PyCFunction)dsaKey__sign, METH_VARARGS, "Sign the given long."},
  {"_verify", (PyCFunction)dsaKey__verify, METH_VARARGS, "Verify that the signature is valid."},
  {"size", (PyCFunction)dsaKey_size, METH_NOARGS, "Return the number of bits that this key can handle."},
  {"hasprivate", (PyCFunction)dsaKey_hasprivate, METH_NOARGS, "Return 1 or 0 if this key does/doesn't have a private key."},
  {NULL, NULL, 0, NULL}
};

PyObject * dsaKey_new(PyObject *self, PyObject *args) {
  PyLongObject *y = NULL, *g = NULL, *p = NULL, *q = NULL, *x = NULL;
  dsaKey* key;
  key = PyObject_New(dsaKey, &dsaKeyType);
  mpz_init(key->y);
  mpz_init(key->g);
  mpz_init(key->p);
  mpz_init(key->q);
  mpz_init(key->x);
  PyArg_ParseTuple(args, "O!O!O!O!|O!", &PyLong_Type, &y,
                                        &PyLong_Type, &g,
                                        &PyLong_Type, &p,
                                        &PyLong_Type, &q,
                                        &PyLong_Type, &x);
  longObjToMPZ(key->y, y);
  longObjToMPZ(key->g, g);
  longObjToMPZ(key->p, p);
  longObjToMPZ(key->q, q);
  if (x) {
    longObjToMPZ(key->x, x);
  }
  /*Py_XDECREF(n);
  Py_XDECREF(e);
  Py_XDECREF(d);
  Py_XDECREF(p);
  Py_XDECREF(q);*/
  return (PyObject*) key;
}

static void dsaKey_dealloc(dsaKey* key) {
  mpz_clear(key->y);
  mpz_clear(key->g);
  mpz_clear(key->p);
  mpz_clear(key->q);
  mpz_clear(key->x);
  PyObject_Del(key);
}

static PyObject* dsaKey_getattr(dsaKey* key, char* attr) {
  if (strcmp(attr, "y") == 0)
    return mpzToLongObj(key->y);
  else if (strcmp(attr, "g") == 0)
    return mpzToLongObj(key->g);
  else if (strcmp(attr, "p") == 0)
    return mpzToLongObj(key->p);
  else if (strcmp(attr, "q") == 0)
    return mpzToLongObj(key->q);
  else if (strcmp(attr, "x") == 0) {
    if (mpz_size(key->x) == 0) {
      PyErr_SetString(PyExc_AttributeError, "rsaKey instance has no attribute 'x'");
      return NULL;
    }
    return mpzToLongObj(key->x);
  }
  else {
    return Py_FindMethod(dsaKey__methods__, (PyObject*) key, attr);
  }
}

PyObject* dsaKey__sign(dsaKey *key, PyObject *args) {
  PyObject *lm, *lk, *lr, *ls;
  if (!(PyArg_ParseTuple(args, "O!O!", &PyLong_Type, &lm,
                                       &PyLong_Type, &lk))) {
    return NULL;
  }
  mpz_t m;
  mpz_t k;
  mpz_t r;
  mpz_t s;
  mpz_init(m);
  mpz_init(k);
  mpz_init(r);
  mpz_init(s);
  longObjToMPZ(m, (PyLongObject*)lm);
  longObjToMPZ(k, (PyLongObject*)lk);
  int result = dsaSign(key, m, k, r, s);
  if (result == 1) {
    PyErr_SetString(dsaError, "K not between 2 and q");
    return NULL;
  }
  lr = mpzToLongObj(r);
  ls = mpzToLongObj(s);
  mpz_clear(m);
  mpz_clear(k);
  mpz_clear(r);
  mpz_clear(s);
  return Py_BuildValue("(NN)", lr, ls);
}

PyObject* dsaKey__verify(dsaKey *key, PyObject *args) {
  PyObject *lm, *lr, *ls;
  if (!(PyArg_ParseTuple(args, "O!O!O!", &PyLong_Type, &lm,
                                         &PyLong_Type, &lr,
                                         &PyLong_Type, &ls))) {
    return NULL;
  }
  mpz_t m, r, s;
  mpz_init(m);
  mpz_init(r);
  mpz_init(s);
  longObjToMPZ(m, (PyLongObject*)lm);
  longObjToMPZ(r, (PyLongObject*)lr);
  longObjToMPZ(s, (PyLongObject*)ls);
  int result = dsaVerify(key, m, r, s);
  mpz_clear(m);
  mpz_clear(r);
  mpz_clear(s);
  return Py_BuildValue("i", result);
}

PyObject* dsaKey_size(dsaKey *key) {
  return Py_BuildValue("i", mpz_sizeinbase(key->p,2)-1);
}

PyObject* dsaKey_hasprivate(dsaKey *key) {
  if (mpz_size(key->x) == 0)
    return Py_BuildValue("i", 0);
  else
    return Py_BuildValue("i", 1);
}


void init_dsa(void) {
  dsaKeyType.ob_type = &PyType_Type;
  _dsa_module = Py_InitModule("_dsa", _dsa__methods__);
  _dsa_dict = PyModule_GetDict(_dsa_module);
  dsaError = PyErr_NewException("_dsa.error", NULL, NULL);
  PyDict_SetItemString(_dsa_dict, "error", dsaError);
}

#include <stdio.h>
#include <string.h>
#include <Python.h>
#include <longintrepr.h> // for conversions
#include <gmp.h>

PyObject* _rsa_module;
PyObject* _rsa_dict;

void longObjToMPZ(mpz_t m, PyLongObject *p) {
  int size, i;
  mpz_t temp, temp2;
  mpz_init(temp);
  mpz_init(temp2);
  if (p->ob_size>0)
    size = p->ob_size;
  else
    size = -p->ob_size;
  for (i=0; i<size; i++) {
    mpz_set_ui(temp, p->ob_digit[i]);
    mpz_mul_2exp(temp2, temp, SHIFT * i);
    mpz_add(m, m, temp2);
  }
  mpz_clear(temp);
  mpz_clear(temp2);
}

PyObject* mpzToLongObj(mpz_t m) {
  // borrowed from gmpy
  int size = (mpz_sizeinbase(m, 2) + SHIFT - 1) / SHIFT;
  int i;
  PyLongObject *l = _PyLong_New(size);
  if (!l) {return NULL;}
  mpz_t temp;
  mpz_init_set(temp, m);
  for (i=0;i<size;i++){
    l->ob_digit[i] = (digit) (mpz_get_ui(temp) & MASK);
    mpz_fdiv_q_2exp(temp, temp, SHIFT);
  }
  i=size;
  while ((i>0) && (l->ob_digit[i-1] == 0)) i--;
  l->ob_size = i;
  mpz_clear(temp);
  return (PyObject*)l;
}

PyObject* rsaKey_new(PyObject*, PyObject*);

static PyMethodDef _rsa__methods__[] =
  {
    { "construct", rsaKey_new, METH_VARARGS },
    { NULL, NULL }
  };

typedef struct {
  PyObject_HEAD
  mpz_t n;
  mpz_t e;
  mpz_t d;
  mpz_t p;
  mpz_t q;
} rsaKey;

static int rsaEncrypt(rsaKey *key, mpz_t v) {
  if (mpz_cmp(v, key->n)>=0) {
    return 1;
  }
  mpz_powm(v, v, key->e, key->n);
  return 0;
}

static int rsaDecrypt(rsaKey *key, mpz_t v) {
  if (mpz_cmp(v, key->n)>=0) {
    return 1;
  }
  if (mpz_size(key->d)==0) {
    return 2;
  }
  mpz_powm(v, v, key->d, key->n);
  return 0;
}

static void rsaKey_dealloc(rsaKey*);
static PyObject * rsaKey_getattr(rsaKey*, char*);
static PyObject * rsaKey__encrypt(rsaKey*, PyObject*);
static PyObject * rsaKey__decrypt(rsaKey*, PyObject*);
static PyObject * rsaKey__verify(rsaKey*, PyObject*);
static PyObject * rsaKey_size(rsaKey*);
static PyObject * rsaKey_hasprivate(rsaKey*);

PyObject *rsaError; // raised on erros

static PyTypeObject rsaKeyType = {
  PyObject_HEAD_INIT(NULL)
  0,
  "rsaKey",
  sizeof(rsaKey),
  0,
  (destructor)rsaKey_dealloc, /* dealloc */
  0, /* print */
  (getattrfunc)rsaKey_getattr, /* getattr */
  0, /* setattr */
  0, /* compare */
  0, /* repr */
  0, /* as_number */
  0, /* as_sequence */
  0, /* as_mapping */
  0, /* hash */
  0, /* call */
};

static PyMethodDef rsaKey__methods__[] = {
  {"_encrypt", (PyCFunction)rsaKey__encrypt, METH_VARARGS, "Encrypt the given long."},
  {"_decrypt", (PyCFunction)rsaKey__decrypt, METH_VARARGS, "Decrypt the given long."},
  {"_sign", (PyCFunction)rsaKey__decrypt, METH_VARARGS, "Sign the given long."},
  {"_verify", (PyCFunction)rsaKey__verify, METH_VARARGS, "Verify that the signature is valid."},
  {"size", (PyCFunction)rsaKey_size, METH_NOARGS, "Return the number of bits that this key can handle."},
  {"hasprivate", (PyCFunction)rsaKey_hasprivate, METH_NOARGS, "Return 1 or 0 if this key does/doesn't have a private key."},
  {NULL, NULL, 0, NULL}
};

PyObject * rsaKey_new(PyObject *self, PyObject *args) {
  PyLongObject *n = NULL, *e = NULL, *d = NULL, *p = NULL, *q = NULL;
  rsaKey* key;
  key = PyObject_New(rsaKey, &rsaKeyType);
  mpz_init(key->n);
  mpz_init(key->e);
  mpz_init(key->d);
  mpz_init(key->p);
  mpz_init(key->q);
  PyArg_ParseTuple(args, "O!O!|O!O!O!", &PyLong_Type, &n,
                                        &PyLong_Type, &e,
                                        &PyLong_Type, &d,
                                        &PyLong_Type, &p,
                                        &PyLong_Type, &q);
  longObjToMPZ(key->n, n);
  longObjToMPZ(key->e, e);
  if (!d) {
    return (PyObject*) key;
  }
  longObjToMPZ(key->d, d);
  if (p) {
    if (q) {
      longObjToMPZ(key->p, p);
      longObjToMPZ(key->q, q);
    }
  }
  /*Py_XDECREF(n);
  Py_XDECREF(e);
  Py_XDECREF(d);
  Py_XDECREF(p);
  Py_XDECREF(q);*/
  return (PyObject*) key; // ingore p and q for now
}

static void rsaKey_dealloc(rsaKey* key) {
  mpz_clear(key->n);
  mpz_clear(key->e);
  mpz_clear(key->d);
  mpz_clear(key->p);
  mpz_clear(key->q);
  PyObject_Del(key);
}

static PyObject* rsaKey_getattr(rsaKey* key, char* attr) {
  if (strcmp(attr, "n") == 0)
    return mpzToLongObj(key->n);
  else if (strcmp(attr, "e") == 0)
    return mpzToLongObj(key->e);
  else if (strcmp(attr, "d") == 0) {
    if (mpz_size(key->d)==0) {
      PyErr_SetString(PyExc_AttributeError, "rsaKey instance has no attribute 'd'");
      return NULL;
    }
    return mpzToLongObj(key->d);
  }
  else if (strcmp(attr, "p") == 0) {
    if (mpz_size(key->p)==0) {
      PyErr_SetString(PyExc_AttributeError, "rsaKey instance has no attribute 'p'");
      return NULL;
    }
    return mpzToLongObj(key->p);
  }
  else if (strcmp(attr, "q") == 0) {
    if (mpz_size(key->q)==0) {
      PyErr_SetString(PyExc_AttributeError, "rsaKey instance has no attribute 'q'");
      return NULL;
    }
    return mpzToLongObj(key->q);
  }
  else {
    return Py_FindMethod(rsaKey__methods__, (PyObject*) key, attr);
  }
}

PyObject* rsaKey__encrypt(rsaKey *key, PyObject *args) {
  PyObject *l, *r;
  if (!(PyArg_ParseTuple(args, "O!", &PyLong_Type, &l))) {
    return NULL;
  }
  mpz_t v;
  mpz_init(v);
  longObjToMPZ(v, (PyLongObject*)l);
  int result = rsaEncrypt(key, v);
  if (result == 1) { // plaintext too big
    PyErr_SetString(rsaError, "Plaintext too large");
    return NULL;
  }
  r = (PyObject*)mpzToLongObj(v);
  mpz_clear(v);
  return Py_BuildValue("N", r);
}

PyObject* rsaKey__decrypt(rsaKey *key, PyObject *args) {
  PyObject *l, *r;
  if (!(PyArg_ParseTuple(args, "O!", &PyLong_Type, &l))) {
    return NULL;
  }
  mpz_t v;
  mpz_init(v);
  longObjToMPZ(v, (PyLongObject*)l);
  int result = rsaDecrypt(key, v);
  if (result == 1) { // ciphertext too big
    PyErr_SetString(rsaError, "Ciphertext too large");
    return NULL;
  }
  else if (result == 2) { // no private key
    PyErr_SetString(rsaError, "Private key not available in this object");
    return NULL;
  }
  r = mpzToLongObj(v);
  mpz_clear(v);
  return Py_BuildValue("N", r);
}

// PyObject* rsaKey__sign(rsaKey *key, PyObject *args) {} // same as __decrypt

PyObject* rsaKey__verify(rsaKey *key, PyObject *args) {
  PyObject *l, *lsig;
  if (!(PyArg_ParseTuple(args, "O!O!", &PyLong_Type, &l, &PyLong_Type, &lsig))) {
    return NULL;
  }
  mpz_t v, vsig;
  mpz_init(v);
  mpz_init(vsig);
  longObjToMPZ(v, (PyLongObject*)l);
  longObjToMPZ(vsig, (PyLongObject*)lsig);
  rsaEncrypt(key, vsig);
  if (mpz_cmp(v, vsig) == 0)
    return Py_BuildValue("i", 1);
  else
    return Py_BuildValue("i", 0);
}

PyObject* rsaKey_size(rsaKey *key) {
  return Py_BuildValue("i", mpz_sizeinbase(key->n,2)-1);
}

PyObject* rsaKey_hasprivate(rsaKey *key) {
  if (mpz_size(key->d) == 0)
    return Py_BuildValue("i", 0);
  else
    return Py_BuildValue("i", 1);
}


void init_rsa(void) {
  rsaKeyType.ob_type = &PyType_Type;
  _rsa_module = Py_InitModule("_rsa", _rsa__methods__);
  _rsa_dict = PyModule_GetDict(_rsa_module);
  rsaError = PyErr_NewException("_rsa.error", NULL, NULL);
  PyDict_SetItemString(_rsa_dict, "error", rsaError);
}

Index: setup.py
===================================================================
RCS file: /cvsroot/pycrypto/crypto/setup.py,v
retrieving revision 1.16
diff -u -r1.16 setup.py
--- setup.py    18 Jul 2002 13:05:37 -0000      1.16
+++ setup.py    18 Nov 2002 23:20:27 -0000
@@ -71,7 +71,16 @@
                      Extension("Crypto.Cipher.XOR",
                                include_dirs=['src/'],
                                sources=["src/XOR.c"]),
-
+
+                     # Public Key crypto
+                     Extension("Crypto.PublicKey._rsa",
+                               include_dirs=['src/'],
+                               libraries=['gmp'],
+                               sources=["src/_rsa.c"]),
+                     Extension("Crypto.PublicKey._dsa",
+                               include_dirs=['src/'],
+                               libraries=['gmp'],
+                               sources=["src/_dsa.c"]),
                     ]
      )

Index: DSA.py
===================================================================
RCS file: /cvsroot/pycrypto/crypto/PublicKey/DSA.py,v
retrieving revision 1.4
diff -u -r1.4 DSA.py
--- DSA.py      11 Jul 2002 14:31:19 -0000      1.4
+++ DSA.py      19 Nov 2002 02:30:24 -0000
@@ -17,6 +17,11 @@
 from Crypto.Util.number import bytes_to_long, long_to_bytes
 from Crypto.Hash import SHA

+try:
+    from Crypto.PublicKey import _dsa
+except:
+    _dsa = None
+
 class error (Exception):
     pass

@@ -145,4 +150,54 @@

 object=DSAobj

+generate_py = generate
+construct_py = construct
+
+class DSAobj_c(DSAobj):
+    def __init__(self, key):
+        self.key = key
+
+    def __getstate__(self):
+        d = {}
+        for k in self.keydata:
+            if hasattr(self.key, k):
+                d[k]=getattr(self.key, k)
+        return d
+
+    def __setstate__(self, state):
+        y,g,p,q = state['y'], state['g'], state['p'], state['q']
+        if 'x' not in state:
+            self.key = _dsa.construct(y,g,p,q)
+        else:
+            x = state['x']
+            self.key = _dsa.construct(y,g,p,q,x)
+
+    def _sign(self, M, K):
+        return self.key._sign(M, K)
+
+    def _verify(self, M, (r, s)):
+        return self.key._verify(M, r, s)
+
+    def size(self):
+        return self.key.size()
+
+    def hasprivate(self):
+        return self.key.hasprivate()
+
+    def publickey(self):
+        return construct_c((self.key.y, self.key.g, self.key.p, self.key.q))

+def generate_c(bits, randfunc, progress_func=None):
+    obj = generate_py(bits, randfunc, progress_func)
+    y,g,p,q,x = obj.y, obj.g, obj.p, obj.q, obj.x
+    return construct_c((y,g,p,q,x))
+
+def construct_c(tuple):
+    key = apply(_dsa.construct, tuple)
+    return DSAobj_c(key)
+
+if _dsa:
+    #print "using C version of DSA"
+    generate = generate_c
+    construct = construct_c
+    error = _dsa.error

Index: RSA.py
===================================================================
RCS file: /cvsroot/pycrypto/crypto/PublicKey/RSA.py,v
retrieving revision 1.5
diff -u -r1.5 RSA.py
--- RSA.py      11 Jul 2002 14:33:05 -0000      1.5
+++ RSA.py      19 Nov 2002 02:29:33 -0000
@@ -14,6 +14,11 @@

 from Crypto.PublicKey import pubkey

+try:
+    from Crypto.PublicKey import _rsa
+except:
+    _rsa = None
+
 class error (Exception):
     pass

@@ -101,7 +105,80 @@
         """
         return construct((self.n, self.e))

+class RSAobj_c(pubkey.pubkey):
+    keydata = ['n', 'e', 'd', 'p', 'q']
+    n = property(lambda s:s.key.n)
+    e = property(lambda s:s.key.e)
+    d = property(lambda s:s.key.d)
+    p = property(lambda s:s.key.p)
+    q = property(lambda s:s.key.q)
+
+    def __init__(self, key):
+        self.key = key
+
+    def __getstate__(self):
+        d = {}
+        for k in self.keydata:
+            if hasattr(self.key, k):
+                d[k]=getattr(self.key, k)
+        return d
+
+    def __setstate__(self, state):
+        n,e = state['n'], state['e']
+        if 'd' not in state:
+            self.key = _rsa.construct(n,e)
+        else:
+            d = state['d']
+            if 'q' not in state:
+                self.key = _rsa.construct(n,e,d)
+            else:
+                p, q = state['p'], state['q']
+                self.key = _rsa.construct(n,e,d,p,q)
+
+    def _encrypt(self, plain, K):
+        return (self.key._encrypt(plain),)
+    def _decrypt(self, cipher):
+        return self.key._decrypt(cipher[0])
+    def _sign(self, M, K):
+        return (self.key._sign(M),)
+    def _verify(self, M, sig):
+        return self.key._verify(M, sig[0])
+    def size(self):
+        return self.key.size()
+    def hasprivate(self):
+        return self.key.hasprivate()
+    def publickey(self):
+        return construct_c((self.key.n, self.key.e))
+
+def generate_c(bits, randfunc, progress_func = None):
+    difference=ord(randfunc(1)) & 7
+
+    # Generate the prime factors of n
+    if progress_func: progress_func('p\n')
+    p=pubkey.getPrime(bits/2, randfunc)
+    if progress_func: progress_func('q\n')
+    q=pubkey.getPrime((bits/2)+difference, randfunc)
+    n=p*q
+
+    # Generate encryption exponent
+    if progress_func: progress_func('e\n')
+    e=pubkey.getPrime(17, randfunc)
+    if progress_func: progress_func('d\n')
+    d=pubkey.inverse(e, (p-1)*(q-1))
+    key = _rsa.construct(n,e,d,p,q)
+    return RSAobj_c(key)
+
+def construct_c(tuple):
+    key = apply(_rsa.construct, tuple)
+    return RSAobj_c(key)

 object = RSAobj

+generate_py = generate
+construct_py = construct

+if _rsa:
+    #print "using C version of RSA"
+    generate = generate_c
+    construct = construct_c
+    error = _rsa.error