Go Down

### Topic: BigIntegers versus ,mini-gmp (Read 439 times)previous topic - next topic

#### lienhard

##### Feb 25, 2019, 06:20 pm
Gnu has a library call GMP (Multiple Precision Arithmetic Library). In this Library there is a small sublibrary mini-gmp. Here I did some few modifications and now it runs on my teensy. I can genarate 512 bit RSA keys, and crypt and decrypt.

mini-gmp is much faster but the BigNumber Library, because the integers are stored binary and not in BCD.
And even better, because the integers are binary, they use not so much space like BCDs.
The bad thing is, they have only a C Interface, not C++, so no overloading is possible (or just with a great programming effort).
Here is a sample Code for generating the private RSA key.

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 = 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 = 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;
}

#### AWOL

#1
##### Feb 25, 2019, 06:33 pm
...and that's why we ask you to use code tags when posting code

#### MrHello123

#2
##### Mar 05, 2019, 04:16 pm
@Lienhard, could you send the minigmp, C and header file? I've tried downloading the minigmp, but it throws error in my arduin IDE, and I can't really fix the errors tbh?

Go Up