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

41–50 of 89 posts

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

#41

Post by jcalvinowens »

One line of inline assembler makes the bignum school multiplication trivial: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...

If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication. It's a shame Rust doesn't have it either. Hardware support is everywhere: hell, the Cortex M0 doesn't do division, but it has an expanding multiply!

This is from a very ugly little toy implementation of RSA I wrote a long time ago: https://github.com/jcalvinowens/toy-rsa

I found I could get away with the Fermat test, because the algorithm doesn't work if the primes aren't actually prime: the Fermat test is fast, and an encrypt/decrypt eliminates the extremely minuscule chance either prime is a fermat liar.

But I don't know if it can be proven there do not exist non-prime P/Q values which produce an RSA keypair which can successfully encrypt/decrypt messages. I'm sure this isn't kosher for a real implementation, but I've never found an answer.

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

#42

Post by tzs »

tzs wrote: post #31
glitchcomet wrote: post #17

Earlier quoted context omitted.

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

Here is prime.py if anyone wants to play around with it: https://pastebin.com/FFw4qrvU

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

#43

Post by TheDudeMan »

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.

Another option is to do N sequential candidate tests for each fresh random candidate. Where N is something that gets you most of the speed advantage of doing all sequential tests. Maybe like N=16.

Nice write-up!

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

#44

Post by AceJohnny2 »

This sends me back.

My first-year college project, a few decades ago, was to implement 4096-bit RSA encryption, the idea of my project-mate and friend (and later valedectorian) who implemented the core math.

I recall how slow prime number generation was in our final implementation, taking ~20 minutes to generate on PA-RISC workstations. My friend, a math nerd, took it upon themselves to continue optimizing the code long after the project was over. I remember them reading papers on prime number detection, and bignum math implementations. For example, one huge improvement came when the code would detect if a number in a component multiplication was 0, then skip the multiplication and give a 0 result!

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

#45

Post by lifthrasiir »

jcalvinowens wrote: post #41

One line of inline assembler makes the bignum school multiplication trivial: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4... If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication. It's a shame Rust doesn't have it either. Hardware support is everywhere: hell, the Cortex M0 doesn't do division, but it has an expanding multiply! This is…

I believe that both in most C compilers and in Rust, casting to a bigger type and multiplying does produce the exact opcode.

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

#46

Post by AceJohnny2 »

jcalvinowens wrote: post #41

One line of inline assembler makes the bignum school multiplication trivial: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4... If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication. It's a shame Rust doesn't have it either. Hardware support is everywhere: hell, the Cortex M0 doesn't do division, but it has an expanding multiply! This is…

> I would add some notion of expanding multiplication.

C type promotion is complicated enough!

Intrinsics expose this adequately, don't you think?

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

#47

Post by lifthrasiir »

tzs wrote: post #31
glitchcomet wrote: post #17

Earlier quoted context omitted.

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

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

Unfortunately this limit depends on the currently unproven conjecture (a subset of the generalized Riemann hypothesis). You have to check all n bases to be unconditionally correct.

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

#48

Post by Dylan16807 »

> My binary implementation was probably spending almost all of its time waiting to read or write numbers from RAM due to L1 cache misses. I did not know at the time how to actually test this, but I thought let's try a more memory efficient version anyway and see if it improves things.

The text never comes back to this, but the answer is that a handful of 1-2KB numbers fit into L1 just fine, and even if they didn't there's a megabyte or more of L2 that takes about 3ns to access.

> It goes without saying that probably none of this is actually cryptographically secure, but that was never the point anyway.

Hmm. This is just the prime generation, so it avoids most RSA pitfalls, and urandom had better be secure. So if this code works at all then there's not much that could go wrong. RSA has a few issues with weak primes to avoid but I don't know if they're likely enough to matter here.

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

#49

Post by nullc »

lifthrasiir wrote: post #45
jcalvinowens wrote: post #41

One line of inline assembler makes the bignum school multiplication trivial: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4... If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication. It's a shame Rust doesn't have it either. Hardware support is everywhere: hell, the Cortex M0 doesn't do division, but it has an expanding multiply! This is…

I believe that both in most C compilers and in Rust, casting to a bigger type and multiplying does produce the exact opcode.

On 64-bit hosts using the full widening multiplier requires that you use 128 bit integers-- which aren't portable. :( (in particular, MSVC doesn't have it last I checked). It's the obvious thing to do where they exist however.

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

#50

Post by kevin_thibedeau »

AceJohnny2 wrote: post #44

This sends me back. My first-year college project, a few decades ago, was to implement 4096-bit RSA encryption, the idea of my project-mate and friend (and later valedectorian) who implemented the core math. I recall how slow prime number generation was in our final implementation, taking ~20 minutes to generate on PA-RISC workstations. My friend, a math nerd, took it upon themselves to continue optimizing the code l…

On slow hardware you're much better off generating elliptic curve keys. Otherwise you wait a long time or compromise on future proof security.
Post reply on HN