Introduction⌗

The Sophie Germain Prime Project primarily aims to collect, analyse and distribute Sophie Germain primes.

I have started this project in order to facilitate research on the Blum-Blum-Shub random number generator and related cryptographic algorithms (like the Blum-Goldwasser cryptosystem). Large Sophie Germain primes (as big as 4096 bits) are used in the BBS generator to fulfill elementary security requirements; unfortunately they also take a long and generally unpredictable amount of time to find.

Users may submit primes to the project, which will be verified and stored in a database. The project also provides a web interface to search for Sophie Germain primes satisfying given criteria, statistics on the currently recorded primes. There are plans to create periodic torrent dumps of the database.

The project is open to technical and theoretical contributions, which can be submitted to me via e-mail. Alternative means of hosting the project are also welcome from parties interested in donating the server space and bandwidth.

How to contribute⌗

The following C language program can be used to generate large, n−1n-1-bit Sophie Germain primes that can be submitted to the project.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
void get_random_safe_prime(mpz_t p, mpz_t q, size_t bits) {
  FILE * f;
  if (bits < 3 || !(f = fopen("/dev/urandom", "rb"))) exit(1);
  unsigned mask = 1<<((bits+7)&7);
  size_t nbytes = (bits+7)>>3;
  uint8_t buf[nbytes];
  mpz_t two; mpz_init_set_ui(two, 2);
  for(;;) {
    if (fread(buf, 1, nbytes, f) != nbytes) exit(1);
    buf[0] = (buf[0] & (mask-1)) | mask;
    mpz_import(p, nbytes, 1, 1, 0, 0, buf);
    if (bits > 4) {
      mpz_sub_ui(p, p, ((unsigned)mpz_fdiv_ui(p, 12)+1u)%12u);
      if (bits > 9) {
        unsigned long r;
        r = mpz_fdiv_ui(p,  5ul* 7ul*11ul*13ul*17ul*19ul*23ul*37ul);
        if ((r% 5u)>>1==0||(r% 7u)>>1==0||(r%11u)>>1==0||(r%13u)>>1==0||(r%17u)>>1==0||(r%19u)>>1==0||(r%23u)>>1==0||(r%37u)>>1==0)
          continue;
        r = mpz_fdiv_ui(p, 29ul*31ul*41ul*43ul*47ul*53ul);
        if ((r%29u)>>1==0||(r%31u)>>1==0||(r%41u)>>1==0||(r%43u)>>1==0||(r%47u)>>1==0||(r%53u)>>1==0)
          continue;
        r = mpz_fdiv_ui(p, 59ul*61ul*67ul*71ul*73ul);
        if ((r%59u)>>1==0||(r%61u)>>1==0||(r%67u)>>1==0||(r%71u)>>1==0||(r%73u)>>1==0)
          continue;
      }
      mpz_powm(q, two, p, p);
      if (mpz_cmp(q,two)!=0) continue;
    }
    mpz_fdiv_q_2exp(q,p,1);
    if (mpz_tstbit(p, bits-1) && mpz_probab_prime_p(q, 40) && mpz_probab_prime_p(p, 50))
      break;
  }
  mpz_clear(two);
  fclose(f);
}
int main(int argc, char * argv[]) {
  mpz_t p, q; mpz_inits(p, q, NULL);
  get_random_safe_prime(p, q, atoi(argv[1]));
  printf("Safe prime: ");           mpz_out_str(stdout, 10, p); printf("\n");
  printf("Sophie Germain prime: "); mpz_out_str(stdout, 10, q); printf("\n");
  return 0;
}

Roadmap for the project⌗

The following technical enhancements are planned:

  • A more efficient backend for the database, recording more information about the primes such as their record date and submitter.
  • Set up a separate hosting platform for the project, which will allow for more efficient data distribution and backups.
  • Set up a way for clients to download database dump (perhaps via Torrent).
  • Finish the initial insertion batch of all Mersenne primes under 2322^{32} is complete.