Go Down

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

lienhard

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

...and that's why we ask you to use code tags when posting code

MrHello123

@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