Now I can generate a 512 bit rsa keypair in 2278 ms on a Tennsy 3.2
Crypting a 110 byte message costs 17ms, decrypting 856ms.

Well this library is not C++, just C, but in contrairy to BigNumber Library the Integers are stored binary instead of BCD and thatsfor much fastesr an fewer ram consuming.
Here a short example of generating a keypair:


/* ************************************************** ************************************** */
void generate_keys(private_key* ku)
{

char buf[BUFFER_SIZE];
int i;
mpz_t phi; mpz_init(phi);
mpz_t tmp1; mpz_init(tmp1);
mpz_t tmp2; mpz_init(tmp2);

mpz_set_ui(ku->e, 65537);

for(i = 0; i < BUFFER_SIZE; i++)
buf[i] = random(255) % 0xFF;
buf[0] |= 0xC0;
buf[BUFFER_SIZE - 1] |= 0x01;
mpz_import(tmp1, BUFFER_SIZE, 1, sizeof(buf[0]), 0, 0, buf);
mpz_nextprime(ku->p, tmp1);
mpz_mod(tmp2, ku->p, ku->e); /* If p mod e == 1, gcd(phi, e) != 1 */
while(!mpz_cmp_ui(tmp2, 1))
{
mpz_nextprime(ku->p, ku->p); /* so choose the next prime */
mpz_mod(tmp2, ku->p, ku->e);
}
do {
for(i = 0; i < BUFFER_SIZE; i++)
buf[i] = random(255) % 0xFF;
buf[0] |= 0xC0;
buf[BUFFER_SIZE - 1] |= 0x01;
mpz_import(tmp1, (BUFFER_SIZE), 1, sizeof(buf[0]), 0, 0, buf);
mpz_nextprime(ku->q, tmp1);
mpz_mod(tmp2, ku->q, ku->e);
while(!mpz_cmp_ui(tmp2, 1))
{
mpz_nextprime(ku->q, ku->q);
mpz_mod(tmp2, ku->q, ku->e);
}
} while(mpz_cmp(ku->p, ku->q) == 0); /* If we have identical primes (unlikely), try again */

mpz_mul(ku->n, ku->p, ku->q);

mpz_sub_ui(tmp1, ku->p, 1);
mpz_sub_ui(tmp2, ku->q, 1);
mpz_mul(phi, tmp1, tmp2);

if(mpz_invert(ku->d, ku->e, phi) == 0)
{
mpz_gcd(tmp1, ku->e, phi);
sprintf(sbuf,"gcd(e, phi) = [%s]\n", mpz_get_str(NULL, 16, tmp1));
Serial.print(sbuf);
sprintf(sbuf,"Invert failed\n");
Serial.print(sbuf);
}
mpz_clear(phi);
mpz_clear(tmp1);
mpz_clear(tmp2);
return;
}

I'am willing to publisch the entire code, is somebodey interseted