Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How hard can generating 1024-bit primes be?

glitchcomet.com

Post reply on HN
Print view View original

11–20 of 89 posts

Re: How hard can generating 1024-bit primes be?

#11

Post by adgjlsfhk1 »

opticfluorine wrote: post #8
lordnacho wrote: post #6

Earlier quoted context omitted.

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…

you want the nth bit to be set because otherwise there is a small but noticable chance that you generate a surprisingly weak prime.

Re: How hard can generating 1024-bit primes be?

#12

Post by opticfluorine »

adgjlsfhk1 wrote: post #11
opticfluorine wrote: post #8

Earlier quoted context omitted.

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…

you want the nth bit to be set because otherwise there is a small but noticable chance that you generate a surprisingly weak prime.

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!

Re: How hard can generating 1024-bit primes be?

#13

Post by bobbylarrybobby »

opticfluorine wrote: post #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? Admit…

Losing one bit of entropy to generate a prime that's definitely not only 50 bits long seems like a worthy tradeoff.

Re: How hard can generating 1024-bit primes be?

#14

Post by GaggiX »

kadoban wrote: post #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…

>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.

Re: How hard can generating 1024-bit primes be?

#15

Post by glitchcomet »

opticfluorine wrote: post #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? Admit…

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.

Re: How hard can generating 1024-bit primes be?

#17

Post by glitchcomet »

GaggiX wrote: post #14
kadoban wrote: post #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…

>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.

You can find the bases for N [0]: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...

Re: How hard can generating 1024-bit primes be?

#18

Post by dgacmu »

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.

Re: How hard can generating 1024-bit primes be?

#19

Post by glitchcomet »

adgjlsfhk1 wrote: post #9

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.

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.

Re: How hard can generating 1024-bit primes be?

#20

Post by mateo1 »

kadoban wrote: post #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…

Besides, when you're just looking for a prime, you can spot things that look like a prime and test them deterministically.
Post reply on HN