It also seems unusual that what appears to be a generic function call in
the bignum library is in fact a helper function for a specific application
and as such not useful for others. Writing my own prime generator is
simple enough, but perhaps BN_generate_prime would be more appropriately
named BN_generate_rsa_prime or something.
Thanks for the help,
Matt Raibert
On Fri, 29 Jul 2005, Michael Sierchio wrote:
Nils Larsch wrote:
Matthew Julius Raibert wrote:
I'm working on a project for which I need to generate big primes. Along
the way I noticed that when I run BN_generate_prime() it seems to always
set the two most significant bits to one. In other words, if I ask for a
thousand 16 bit primes, I get a thousand primes that lie between hex C000
and hex 10000 and not a single prime that lies between hex 8000 and hex
C000.
yep, that's intentional. It should ensure that the product of two
q bits prime numbers is 2*q bits long (useful for rsa key generation).
Intentional or otherwise, it's NOT the correct way of solving
the problem. It introduces an unneccesary bias.
The problem, in case it isn't obvious to everyone, is that the product
of two n-bit numbers may be 2n bits or 2n-1 bits in length. In order
to guarantee that the result will have 2n bits, the proper thing to do
is generate two primes in the range (2^(n-2) * sqrt(2), 2^(n-1)).
So, if you're searching for a 2048-bit product N = pq, look for
prime numbers between (if I typed correctly)
5A827999FCEF32422AC06224B2789C917FB42383BCB512CA35DF19C7305BEEFE0778\
08545794DFFD2C6A54760CA620E1F7A845D93AB2412F48D99975B0C7A5FA2F34C9EB\
2FC77497318B0C4A5E3F3286D0A5C327C499C534CE88B38A4750BDE174F204C3FB06\
7D933FAB7F40FDEDED12C1DA238312C00F946CD75736BFCE3CCE
and
80000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000
etc.
- Michael Sierchio
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager [EMAIL PROTECTED]
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager [EMAIL PROTECTED]
