How hard can generating 1024-bit primes be?
glitchcomet.com
glitchcomet.com
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.
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_...
All pow functions are just about proving that you wasted work, so there's nothing really inherently wrong with using something prime number based. The problem is that you don't really want to have mathematically and implementation intricate proof-of-work functions, because then some jerk like me comes along and is able to create a much more optimized miner, keep it private, and make money at the cost of having the other miners feel like the game is unfair. New coins in particular depend on those miners acting as marketers to shill the coin, so if they are grumpy, you lose part of your marketing team.
Isn't that the definition of a pyramid scheme?
> 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)
What are the bases for the range of 1024-bit numbers? I couldn't find an answer online.
[0]: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...
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
It took 392 seconds for them all to complete, with each correctly reporting that 2^1024 + 643 has passed for all their 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.
A reference for this material is "Explicit bounds for primality testing and related problems" by Eric Bach, Math. Comp. 55 (191), July 1990, pp. 355-380.
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 :(
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.
The compiler support for that is limited, though. To let N be >128 in Clang, -fexperimental-max-bitint-width=N flag can be provided. If N>128 and _BitInt(N) is divided by something, the compiler will just crash, but +, -, * all work as expected.
Zig makes this relatively easy: it has a @mulWithOverflow intrinsic, which returns an overflow bit with the result, and it has integers up to (u|i)65535. So depending on what you're doing, you can either detect overflow and then upcast, or upcast first and then optionally truncate.
It also has saturating multiply as a separate operator *|, or wrapping with *%, for when those are the semantics you want. Otherwise overflow is safety-checked undefined behavior, which will panic in Debug and ReleaseSafe build modes.
As for returning an overflow bit, Rust has had this since forever with its overflowing_OP() methods, and C23 has recently added an <stdckdint.h> header with a bunch of ckd_OP() macros that return an overflow bit.
If p and q are coprime Carmichael numbers then RSA will still successfully encrypt and decrypt messages, though this will be less secure as p*q will have smaller prime factors and thus be easier to factor.
And int128 support isn't ubiquitous.
See the generated code for these two alternative implementations: https://godbolt.org/z/3vno6G46j
With that fixed, it's the same: https://godbolt.org/z/M571P371K
But after staring at this for a little while, I realized simply reversing the order of the fields in the dword struct will make the result from the multiply instruction already match the way 128-bit structs are returned in registers under the x86_64 calling convention! This is quite a bit better: https://godbolt.org/z/MbfG63vej
Also worth noting the asm makes nicer code on arm64: https://godbolt.org/z/7eas6s9vK
https://github.com/jcalvinowens/toy-rsa/commit/59ef9ea905dbd... https://github.com/jcalvinowens/toy-rsa/commit/ceaa8a4dd0834...
As for the codegen on ARM, I don't think your asm implementation is correct there either. As far as I can tell the UMULL instruction only cares about the least significant 32 bits in the source registers, regardless if you're on a 64-bit CPU: https://developer.arm.com/documentation/ddi0602/2024-03/Base...
Case in point: counting the f's in your constants took me longer than finding that constraint bug did. You would argue ULLONG_MAX would fix that, I suppose.
You're right, that's the 32-bit arm instruction, doh. In my defense, this code was written before 64-bit ARM existed!
C type promotion is complicated enough!
Intrinsics expose this adequately, don't you think?
hi, lo = val1 *** val2;
I think the concept generalizes to non-binary and non-twos-complement CPUs easily enough.
FYI the link on your page reads 4025051 instead of 40250519.
I do have a small quibble, though:
> At this point, the BigInt is using base-(2^64-1) or base-18446744073709551615 and it only needs 16 "digits" to represent a number that uses 309 digits in base-10!
If you use the full range of a u64, then your number will be in base 2^64, with each word ranging from 0 to 2^64-1, in the same way that base-10 digits range from 0 to 9.
Are there any easy ways to mitigate this though? What about say adding 2^64 at each step instead of 2?
Probably the most reasonable thing to do would be to use a Mersenne twister or other PRNG to generate a stream of random bytes. Would be plenty fast and should hopefully have no relevant pattern. No reason you should need real randomness from the OS after the initial seed.
Nice write-up!
> My code from attempt #3 was effectively using base-255, with each byte acting as a single "digit".
I think the author means base-256, not base-255.
1) Naming things
2) Cach3) Concurr invalidation
ency
4) Off-by-one errorsThe 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.
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!
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?
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)
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?
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!
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.
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.
Urandom also takes entropy from things like mouse movements, inter-onset intervals of key presses, and (on servers) hard drive seek times, so it actually does take in some of its own entropy in addition to that provided by the CPU.