n-bit prime generator filter_list Author Message
n-bit prime generator #1
Potential baseplate for a cryptography tutorial, here's a small program that can be used to generate 2 random prime numbers that are exactly n bits (n is limited only by the amount of RAM you have).

It's not really "secure random", as the IV (Initialization Vector) is computed using simple clib rand. This could easily be converted to use a better entropy source, but it's good enough for demonstration.

Code:
```#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <gmp.h> mpz_t *GetPrime(uint32_t bits, mpz_t *initial) {        mpz_t *prime;        mpz_t min;        mpz_t max;        char *bitBuffer;        /* set up buffer for min/max easy checks */        bitBuffer = malloc(bits + 1);        memset(bitBuffer + 1, '0', bits - 2);        bitBuffer[0] = '1';        bitBuffer[bits] = 0x00;        /* init and set min number */        mpz_init2(min, bits);        mpz_set_str(min, bitBuffer, 2);        /* set buf for max, init, and set number */        memset(bitBuffer, '1', bits);        mpz_init2(max, bits);        mpz_set_str(max, bitBuffer, 2);        free(bitBuffer);        /* start rand */        prime = malloc(sizeof(mpz_t));        mpz_init2(*prime, bits);        if (initial != NULL)                mpz_nextprime(*prime, *initial); /* start at init if exists */        else                mpz_nextprime(*prime, min); /* start at min otherwise */        if (mpz_cmpabs(*prime, max) > 0 || mpz_cmpabs(*prime, min) < 0) /* failed */        {                mpz_clear(*prime);                free(prime);                prime = NULL;        }        mpz_clears(min, max, NULL);        return prime; } void GenerateIV(char *IV, uint32_t bits) {        uint32_t i;        srand(time(NULL));        for (i = 0; i < (bits - 2); i++)                IV[i] = rand() % 2 + '0'; } mpz_t *GenerateSecurePrime(uint32_t nbits) {        mpz_t *prime, *lastprime, IVmpz;        char *IV;        int i, n;        IV = malloc(nbits);        memset(IV, '0', nbits - 1);        IV[nbits - 1] = 0;        GenerateIV(IV, nbits);        mpz_init2(IVmpz, nbits);        mpz_set_str(IVmpz, IV, 2);        gmp_printf("IV: %Zx\n", IVmpz);        lastprime = malloc(sizeof(mpz_t));        mpz_init2(*lastprime, nbits);        mpz_set(*lastprime, IVmpz);        mpz_clear(IVmpz);        n = rand() % 25;        for (i = 0; i < n; i++)        {                if ((prime = GetPrime(nbits, lastprime)) == NULL)                {                        printf("ERR: no primes left\n");                        goto cleanup;                }                printf("%d/%d\n", i, n);                if (i < n - 1)                        mpz_clear(*prime);                mpz_set(*lastprime, *prime);        } cleanup:        mpz_clear(*lastprime);        free(lastprime);        return prime; } main(int argc, char * const *argv) {         mpz_t *prime1, *prime2;         uint32_t nbits;         if (argc > 1)                 sscanf(argv[1], "%u", &nbits);         else                 nbits = 8;         prime2 = NULL;         if ((prime1 = GenerateSecurePrime(nbits)) == NULL)                 goto cleanup;         if ((prime2 = GenerateSecurePrime(nbits)) == NULL)                 goto cleanup;         gmp_printf("1: %Zx\n\n", *prime1);         gmp_printf("2: %Zx\n", *prime2); cleanup:         if (prime1 != NULL) mpz_clear(*prime1);         if (prime2 != NULL) mpz_clear(*prime2);         return 0; }```

Compile:

Code:
`gcc --std=c89 -lgmp -lc prime.c`

Requires libgmp