How hard can generating 1024-bit primes really be?
How hard can generating 1024-bit primes really be?
11 comments
-
This is a pretty lame article. The idea is just use a bignum library, or a language with native bignums. While a few optimizations help, basically just generate random 1024 bit random numbers until you something that passes a pseudoprime test, and call it a day. The rest of the article converts the above into a beginning Rust exercise but I think it's preferable to not mix up the two.
From the prime number theorem, around 1/700th of numbers at that size are prime. By filtering out numbers with small divisors you may end up doing 100 or so pseudoprime tests, let's say Fermat tests (3**n mod n == 3). A reasonable library on today's machines can do one of those tests in around 1ms, so you are good.
RSA is deprecated in favor of elliptic curve cryptography these days anyway.
-
The author pointed out they also could've just called
openssl prime -generate -bits 1024if they weren't trying to learn anything. Rebuilding something from scratch and sharing the experience is valuable.-
There's two things going on in the exercise: 1) some introductory Rust programming; 2) some introductory math and crypto.
Maybe it's just me but I think it's better to separate the two. If you're going to do a prime number generation exercise, it will be easier in (e.g.) Python since the bignum arithmetic is built in, you don't have all the memory management headache, etc. If you're going to do a Rust exercise, imho it is better to focus on Rust stuff.
-
-
-
Nice article, I enjoyed it. Why float sqrt has been used? Integer sqrt is way faster and easily supports integers of any lengths
-
The builtin
u64.isqrtseems to be available in nightly only, and additionally I guess the author didn't want to use any external crates as part of their self-imposed challenge. Though I think there may be an off-by-one result withf64.sqrtI don't think this functionally breaks their u64 code because they loop toroot_n + 1.https://doc.rust-lang.org/std/primitive.u64.html#method.isqrt
-
11 comments