chevron_left chevron_right
Login Register invert_colors photo_library


Stay updated and chat with others! - Join the Discord!
Thread Rating:
  • 0 Vote(s) - 0 Average


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
(This post was last modified: 03-22-2019, 05:55 PM by phyrrus9.)

Reply






Users browsing this thread: 1 Guest(s)