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

31–40 of 89 posts

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

#31

Post by tzs »

glitchcomet wrote: post #17
GaggiX wrote: post #14

Earlier quoted context omitted.

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

Just testing all the bases from 2 through 2 log(N)^2 doesn't actually seem to be too bad for N around 2^1024. It would be a little under 1007600 bases.

I've got a Miller-Rabin implementation in Python 3. Testing 2^1024 + 643, which is the first prime greater than 2^1024 with 65 random bases takes about 0.25 seconds on my Mac Studio. This is with no attempts at optimization or at using multiple cores.

At that rate testing 1007600 bases would take under 65 minutes.

Certainly way longer than you'd want to wait around for something like key generation, but if you didn't actually need your prime for an hour and really wanted to be certain it was a prime its not outrageous.

EDIT: I modified my Miller-Rabin to be the deterministic version, and made it take two parameters: cores and worker. I modified the loop that runs through the bases from 2 to floor(2 log(N)^2) to only actually test when "cores == 1 or base % cores == worker". I made my test program take cores and worker on the command line.

Then I ran this shell script, where prime.py is a program that checks 2^1024 + 643 for primality with the aforementioned deterministic Rabin-Miller:

  ./prime.py 8 0 &
  ./prime.py 8 1 &
  ./prime.py 8 2 &
  ./prime.py 8 3 &
  ./prime.py 8 4 &
  ./prime.py 8 5 &
  ./prime.py 8 6 &
  ./prime.py 8 7 &
  wait
Each of those 8 copies is testing a different 1/8th of the bases that need to be tested. My computer has 8 performance cores and the hope was that MacOS would run each on a different core. That did seem to be the case.

It took 392 seconds for them all to complete, with each correctly reporting that 2^1024 + 643 has passed for all their bases.

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

#35

Post by kwantam »

dgacmu wrote: post #18

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 o…

Great stuff dga :)

Turns out, Niall was also involved in one of the winning ZPrize submissions for fast multi-scalar multiplication (closely related to batch modexp, although over an elliptic curve rather than mod a prime); I assume it inherits from his work on CGBN.

He give a very nice talk about it last year at a Stanford crypto lunch, and it turns out the slides and recording are online!

https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...

https://www.youtube.com/watch?v=KAWlySN7Hm8

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

#36

Post by toast0 »

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…

Another factor is if your high bit is always set, and you encode the prime with that bit, your prime always takes the same number of byte to encode.

Variable byte encoding can lead to problems, if you need to exchange the data between different software, unless the specifications are very clear, and well tested. (See problems with RSA based DHE if the server public key has leading zeros)

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

#37

Post by dgacmu »

kwantam wrote: post #35
dgacmu wrote: post #18

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 o…

Great stuff dga :) Turns out, Niall was also involved in one of the winning ZPrize submissions for fast multi-scalar multiplication (closely related to batch modexp, although over an elliptic curve rather than mod a prime); I assume it inherits from his work on CGBN. He give a very nice talk about it last year at a Stanford crypto lunch, and it turns out the slides and recording are online! https://cbr.stanford.edu/s…

Howdy, neighbor! Thanks for this - I'm glad to hear he's still doing cool stuff. I'm off to watch that now, in fact... :-)

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

#39

Post by pclmulqdq »

One quick thing to add to this: /dev/urandom does not generate "true" random numbers. TRNGs generate 1 bit out per bit of entropy they collect from the environment, while /dev/urandom will not stop generating random bits when it runs out of entropy. That makes it a CSPRNG that is seeded by a TRNG.

For all practical purposes, a CSPRNG seeded by a TRNG is almost as good as a TRNG, but it isn't quite the same.

Linux used to recommend /dev/random which actually was a TRNG (although its entropy collection would sometimes overestimate how much entropy it got, particularly on servers), but it wasn't practical to use as your primary cryptographic RNG because it was very slow.

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

#40

Post by adgjlsfhk1 »

glitchcomet wrote: post #19
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.

IMO you really shouldn't be bottle-necked by random number generation speed. If the kernel calls are what's slowing you down, you could use a strong user space PRNG (e.g. aes based) that is seeded with urandom. The other approach that would be not perfect but a lot better would be to re-randomize the lower 64 or 128 bits each time. That would cut down your rng requirements by a factor of ~10 while keeping much better uniformity since your jumps would be random and much bigger than the gap between primes.
Post reply on HN