How hard can generating 1024-bit primes be?
glitchcomet.com
How hard can generating 1024-bit primes be?
1–10 of 89 posts
Re: How hard can generating 1024-bit primes be?
#2Beautiful article. Nice research
Re: How hard can generating 1024-bit primes be?
#3I remember first trying out PGP in the early 1990s on a 80386 or 80486 on Linux and it took forever to generate a new key.
Re: How hard can generating 1024-bit primes be?
#4> The random number returned is OR-ed with 0b1000000000000001 to set its first and last bit to 1. The last bit set to 1 makes it an odd number and the first bit set to 1 ensures that it is a sufficiently large number which covers the entire range of bits I need.
I can understand setting the low bit to 1 since an even number will never be a prime (edit: obviously except 2). But why set the high bit to 1 as well? Admittedly I don't know much about prime numbers or crypto, but it seems to me like this is just giving up a bit of entropy unnecessarily. What am I missing here?
Re: How hard can generating 1024-bit primes be?
#5> This is where things start to get interesting. At first, I found the concept of probabilistic primality tests strange and tried to look for deterministic algorithms that could handle huge numbers. I did find two - APR-CL and ECPP. Both of these are so mathematically complex that I could not make sense of their research papers at all, and there isn't much accessible information about them on the internet for someone like me who is bad at math.
> After taking a look at discussions online, OpenSSL's source code and recommendations by NIST, I realized that almost everyone including RSA uses probabilistic algorithms. The catch is that if implemented properly, these algorithms have an extremely low error rate which is negligible.
For a given maximum number range, it's trivial to make Miller-Rabin actually deterministic. You just choose bases that have been proven to together exclude all pseudoprimes in the given range.
(It doesn't even end up being a long list, Miller-Rabin kicks ass)
Re: How hard can generating 1024-bit primes be?
#6> The random number returned is OR-ed with 0b1000000000000001 to set its first and last bit to 1. The last bit set to 1 makes it an odd number and the first bit set to 1 ensures that it is a sufficiently large number which covers the entire range of bits I need. I can understand setting the low bit to 1 since an even number will never be a prime (edit: obviously except 2). But why set the high bit to 1 as well? Admit…
Same as generating a 2 digit number. If the first digit is a zero, it is not a 2 digit number.
Re: How hard can generating 1024-bit primes be?
#7> The random number returned is OR-ed with 0b1000000000000001 to set its first and last bit to 1. The last bit set to 1 makes it an odd number and the first bit set to 1 ensures that it is a sufficiently large number which covers the entire range of bits I need. I can understand setting the low bit to 1 since an even number will never be a prime (edit: obviously except 2). But why set the high bit to 1 as well? Admit…
You are giving up a bit of entropy, yeah, but you still have 1022, it's probably safer than wondering if a 1020 bit prime is fine even if they asked for a 1024 bit one. Eg we usually don't consider 00042 a 5-digit number.
Technically probably depends on exactly what you're using it for which choice is optimal, but I'd think the one in the article is the safer default.
Re: How hard can generating 1024-bit primes be?
#8> The random number returned is OR-ed with 0b1000000000000001 to set its first and last bit to 1. The last bit set to 1 makes it an odd number and the first bit set to 1 ensures that it is a sufficiently large number which covers the entire range of bits I need. I can understand setting the low bit to 1 since an even number will never be a prime (edit: obviously except 2). But why set the high bit to 1 as well? Admit…
Same as generating a 2 digit number. If the first digit is a zero, it is not a 2 digit number.
For the purposes of key generation, however, wouldn't you want the full n bits of entropy? Otherwise the search space for a brute force factorization (haha right) is 2^(n-1) instead of 2^n, or half as many possibilities. The domain of the product is still [0..2^(2n)] so the resulting key is the desired 2^(2n) bits.
I guess another way to pose my question would be: is there an issue with sampling the entire 2^n space that makes us only take the highest 2^(n-1) subset of integers instead when selecting factors for a key?
Re: How hard can generating 1024-bit primes be?
#9note that your last optimization of increasing the number by 2 if it fails rather than generating a new random number actually breaks the security slightly. Primes aren't evenly distributed, so doing this biases you towards primes that are directly after large prime gaps.
Re: How hard can generating 1024-bit primes be?
#10I remember first trying out PGP in the early 1990s on a 80386 or 80486 on Linux and it took forever to generate a new key.
If you try to generate a PGP key using GPG on a fresh Linux system, it may flatout refuse to do so claiming there is not sufficient entropy. Or at least it was like that some years ago.