[HN Gopher] How hard can generating 1024-bit primes be?
___________________________________________________________________
How hard can generating 1024-bit primes be?
Author : techedlaksh
Score : 60 points
Date : 2024-05-03 18:06 UTC (4 hours ago)
(HTM) web link (glitchcomet.com)
(TXT) w3m dump (glitchcomet.com)
| timmy777 wrote:
| Beautiful article. Nice research
| glitchcomet wrote:
| Thanks a lot!
| throw0101b wrote:
| I 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.
| sva_ wrote:
| 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.
| opticfluorine wrote:
| > 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?
| lordnacho wrote:
| Same as generating a 2 digit number. If the first digit is a
| zero, it is not a 2 digit number.
| opticfluorine wrote:
| 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?
| adgjlsfhk1 wrote:
| you want the nth bit to be set because otherwise there is a
| small but noticable chance that you generate a surprisingly
| weak prime.
| opticfluorine wrote:
| Out of curiosity, if it is known that the nth bit is set,
| don't I also have the same risk but in (n-1) bits?
| Genuinely curious here.
|
| Edit: Ah, nevermind, I see now why I don't have that
| issue. It's because I can't easily iterate the primes in
| that domain even though I can iterate the reduced number
| of bits. Thanks!
| kadoban wrote:
| 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.
| bobbylarrybobby wrote:
| Losing one bit of entropy to generate a prime that's definitely
| not only 50 bits long seems like a worthy tradeoff.
| glitchcomet wrote:
| As the other comments have mentioned, by setting the first bit
| to one it looses a bit of entropy but ensures that the prime is
| large enough. Another thing to add is that in RSA two primes
| are multiplied together. If one of them is 1024 bits the other
| can be ~200 bits (if i remember correctly) and still reach the
| required number of entropy bits for the key. So, having both
| primes be 1024-bit adds a bit of wiggle room too.
| kadoban wrote:
| > 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)
| GaggiX wrote:
| >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.
|
| What are the bases for the range of 1024-bit numbers? I
| couldn't find an answer online.
| glitchcomet wrote:
| You can find the bases for N < 3x10^21 on wikipedia [0] which
| make Miller-Rabin deterministic. 1024 bit numbers have ~300
| digits and as far as i know, no known bases exist for that
| range.
|
| [0]: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_prima
| lity...
| kadoban wrote:
| Oh, woops. I thought the list went way higher, my bad.
|
| I did read that I think if you do up to 2*ln(n)^2 you're
| always good, but that's not _that_ short of a list.
| Probably better off just keeping it probabalistic, negating
| my original post :(
| mateo1 wrote:
| Besides, when you're just looking for a prime, you can spot
| things that look like a prime and test them deterministically.
| adgjlsfhk1 wrote:
| note 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.
| glitchcomet wrote:
| Yeah i read about this in my research. It is a tradeoff between
| execution speed vs randomness of primes, i choose to go with
| speed assuming that 16 threads all starting from a random
| number and competing to find the prime would add enough
| randomness. If someone preferred more randomness in place of
| speed it's an easy change to replace the +=2 with a rng() call.
| dullcrisp wrote:
| I don't think the parallelism really helps with this; you'll
| still never find the second of two twin primes for instance.
|
| Are there any easy ways to mitigate this though? What about
| say adding 2^64 at each step instead of 2?
| dgacmu wrote:
| Related, there are a few cryptocurrencies that used things
| related to finding large primes as part of their proof of work
| functions. It turns out that ~8 years ago, a really fast
| primality test implementation could make you a lot of money. (For
| some period of time I was the author and maintainer of mining
| software for riecoin. Why, I have no idea, except that I like
| prime numbers.)
|
| This article omits the number one optimization for fast primality
| testing: Montgomery multiplication
|
| https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
|
| It forms the basis of fast practical modular exponentiation
| implementations.
|
| Niall Emmart, then in academia and now I believe at Nvidia,
| released a really, spectacularly fast GPU bigint library, CGBN:
| https://github.com/NVlabs/CGBN
|
| It's still the fastest batch modexp implentation that I'm aware
| of. It's breathtaking, if I can gush in geek for a moment.
|
| (Someday I should write up the story of how that helped me
| dominate production of a small cryptocurrency for about 5 years.
| Thanks, Niall - owe you a beer if we ever cross paths!)
|
| Also worth noting that python includes an entirely fine modexp in
| the three-argument form of pow(x, y, m) --> compute x^y % m
|
| With that, you can very easily implement a fermat or miller-rabin
| primality test if you want to roll your own, which is quite fun.
| If you don't, the gmp library provides a very nice
| mpz_probab_prime() function. Gmp is obviously faster, but it's
| hard to beat the fun of a two liner fermat test for playing with
| big primes.
| mxwsn wrote:
| I'd love to read that story. Please do write it up!
___________________________________________________________________
(page generated 2024-05-03 23:00 UTC)