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

51–60 of 89 posts

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

#51

Post by lifthrasiir »

nullc wrote: post #49
lifthrasiir wrote: post #45

Earlier quoted context omitted.

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.

Yeah, a lack of guaranteed existence of uint128_t is problematic for C. (But __int128 is reasonably portable!) Rust always has u128/i128 in comparison.

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

#52

Post by jcalvinowens »

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.

Of course. But that's ugly and hard to follow compared to the C implementation I linked (at least, in my opinion).

And int128 support isn't ubiquitous.

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

#53

Post by jcalvinowens »

AceJohnny2 wrote: post #46
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?

I want an explicit operation that gives the upper and lower half of the result separately. This is ugly, but like:

  hi, lo = val1 *** val2;
It isn't necessarily intrinsically supported on all platforms: int128 is not part of the original standard. Sometimes long long is the same width as long.

I think the concept generalizes to non-binary and non-twos-complement CPUs easily enough.

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

#55

Post by Jerrrry »

sva_ wrote: post #10
throw0101b wrote: post #3

I remember first trying out PGP in the early 1990s on a 80386 or 80486 on Linux and it took forever to generate a new key.

If you try to generate a PGP key using GPG on a fresh Linux system, it may flatout refuse to do so claiming there is not sufficient entropy. Or at least it was like that some years ago.

On a millisecond old, virtual machine, sure.

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

#56

Post by Jerrrry »

pclmulqdq wrote: post #39

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

[flagged]

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

#57

Post by cbright »

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…

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

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.

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

#59

Post by winternewt »

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…

The original Pretty Good Privacy (PGP) by Philip Zimmermann in 1994 used only a sieve that divided by all known 16-bit primes (this table was produced using the Sieve of Eratosthenes), followed by the Fermat test.

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

#60

Post by tails4e »

Really nice writeup. For the test, could Fermat's method be used to find candidates and then trial division to weed out the false positives? Given they are rare this should not cost much extra time as the trial division (with some precomputed divisiors) is rarely used.
Post reply on HN