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)).
It might be a problem of marketing to claim RSA modulus is a product
of two exactly n-bit primes.
Primes are not required to be of the same bit size.
And modulus is not required to be of exactly two primes:
there could be multi-power (p^k q)
and multi-prime (3 and more different primes) RSA variants.
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]
