This simple C program shows how to generate random prime numbers using openssl bignum libraries; it takes as argument the length of the primes in bits.Here’s the source
Version: 0.1
[viewcode]src=”/pub/maths/openssl_primes_random.txt” lang=”C”[/viewcode]
Please explain what is the purpose of the “#include ”
in your header file?
fredi
“Don’t ask me no questions and I wont tell you no lies”
#include
General purpose input/output routines
#include
Some UNIX standard
None of the above are required, but use to be a good idea to include them, since these are probably the most common headers.
#include
Another standard UNIX header, which declares free, malloc etc…
(more info at http://en.wikipedia.org/wiki/Stdlib.h)
#include
This one is very useful, contains functions, macros and routines to work with (char *) as strings (includes strlen, strtol, memset and much more things)
#include
Openssl BIGNUM declarations, for arithmetics with huge numbers (such as the primes needed to implement RSA algorithm)
Hmm, OK, compiling with OpenSSL ver 0.9.8h on a Sparc 5 running Solaris 2.5.1 yields the following:
# ./genprimes 56
Prime generator by (c) 2004 Paolo Ardoino
usage: ./genprimes [num_bits]
Generating 56 bits primes.
Wait…
69834779657420543
61474498444152383
66239213586814127
61351200631567103
71739027417375587
59701796016635783
65300592723857159
59533171614579239
55576223021154503
^C#
so far looks impressive…
# ./genprimes 8
Prime generator by (c) 2004 Paolo Ardoino
usage: ./genprimes [num_bits]
Generating 8 bits primes.
Wait…
35879
35879
35879
35879
35879
^X35879
^C#
# ./genprimes 4
Prime generator by (c) 2004 Paolo Ardoino
usage: ./genprimes [num_bits]
Generating 4 bits primes.
Wait…
35879
35879
^C# ./genprimes 1
Prime generator by (c) 2004 Paolo Ardoino
usage: ./genprimes [num_bits]
Generating 1 bits primes.
Wait…
35879
35879
^C# l
Hmmmmm……
Well, I found this:
http://www.openssl.org/docs/apps/genrsa.html
“…BUGS
A quirk of the prime generation algorithm is that it cannot generate small primes. Therefore the number of bits should not be less that 64. For typical private keys this will not matter because for security reasons they will be much larger (typically 1024 bits). …”
I wonder if this is the issue?
Yes, it think this should be the problem. It works for higher number of bits, isn’t it? :)
yes it is…so how to make it work with smaller number of bits?
There are much easier ways to generate “small” primes – hell, you might as well just get a list of them for the very small ones from a reputable source (say the source code from the OpenSSL library!
Next up from that there are the various sieves – you only really need to use a random generator if you need really enormous primes; and then you should get a number from somewhere like Random.org (and make sure it’s odd) before running one of the prime tests on it.
when i compiled your prog, i got the following error:
/tmp/ccrD1sfQ.o: In function `main’:
prime.c:(.text 0xd0): undefined reference to `BN_new’
prime.c:(.text 0×111): undefined reference to `BN_generate_prime’
prime.c:(.text 0x11d): undefined reference to `BN_num_bits’
prime.c:(.text 0×146): undefined reference to `BN_bn2dec’
collect2: ld returned 1 exit status
can you tell what could be the problem ?