three large primes

[charybdis]

Originally Posted by chris2be8

What is the first digit of RSA100 compared to your C100's? If it starts with 8 or 9 and yours mostly start with a smaller digit that would explain it. (I'm assuming they are all the same number of digits).

Chris

RSA100 begins with a 1. And in any case, the size of the number has nothing to do with the number of small primes in the factor base, which is unusually low for RSA100, making it harder to find relations.

[bsquared]

Originally Posted by chris2be8

What is the first digit of RSA100 compared to your C100's? If it starts with 8 or 9 and yours mostly start with a smaller digit that would explain it. (I'm assuming they are all the same number of digits).

Chris

In the data set I collected, all C100's started with a 1 or 2. But the metric I'm measuring is independent of input size as it just looks at the factor base primes < 1000. I gathered essentially the same data on a group of random C110s and C120s.

[jasonp]

Anyone who wants to delve into the standard methods for generating RSA key pairs should read NIST SP800-56B, which references FIPS 186-4. There are size requirerments on both primes (not just their top bit being set) that force their product to have bit N set in an N-bit modulus.

None of the standards mandate engineering in any resistance to particular subexponential factoring algorithms; that's just a deviation from randomness that could backfire later if those algorithms ever change, and distracts from using key size to provide cryptographic strength.

[bsquared]

Originally Posted by jasonp

Anyone who wants to delve into the standard methods for generating RSA key pairs should read NIST SP800-56B, which references FIPS 186-4. There are size requirerments on both primes (not just their top bit being set) that force their product to have bit N set in an N-bit modulus.

None of the standards mandate engineering in any resistance to particular subexponential factoring algorithms; that's just a deviation from randomness that could backfire later if those algorithms ever change, and distracts from using key size to provide cryptographic strength.

Thanks for the references. I should maybe (re)mention that yafu's rsa() function is not and never was intended to generate a cryptographic-strength rsa modulus. It is just useful to generate semiprimes with particular bit-lengths.

[Till]

Originally Posted by jasonp

None of the standards mandate engineering in any resistance to particular subexponential factoring algorithms; that's just a deviation from randomness that could backfire later if those algorithms ever change, and distracts from using key size to provide cryptographic strength.

Maybe "safe" or "strong" primes may have played a role nonetheless? https://en.wikipedia.org/wiki/Safe_a...s#Cryptography



Admittedly, I did not read many posts where RDS explained the selection procedure and can't even find the one I read before. Any references?

[R. Gerbicz]

Originally Posted by Till

Admittedly, I did not read many posts where RDS explained the selection procedure and can't even find the one I read before. Any references?

Found these two posts from different threads:
https://www.mersenneforum.org/showpo...7&postcount=33
https://www.mersenneforum.org/showpo...2&postcount=23

[jasonp]

Originally Posted by Till

Maybe "safe" or "strong" primes may have played a role nonetheless? https://en.wikipedia.org/wiki/Safe_a...s#Cryptography

Admittedly, I did not read many posts where RDS explained the selection procedure and can't even find the one I read before. Any references?

The standards I'm familiar with do mandate choosing a prime P constructed so that P+-1 have large factors, though some authors consider that a waste of time at cryptographic sizes since ECM will factor any semiprime where P+-d is smooth, for quite large d. FIPS-186 in particular has a lot of detail about what you should do, written in a way that can be implemented virtually verbatim. Apparently the method is a copy of material from ANSI X9.31, which is not publicly available as far as I know.

This is a very heavyweight process; for example, if you choose to use pseudoprimes that pass the strong Rabin-Miller test, the bases to use must be the output of a cryptographic quality random number generator just like P and Q are.

There are loads of random bit generators that can be used, and anybody interested in this subject can start with NIST SP800-90

[Till]

Originally Posted by R. Gerbicz

Found these two posts from different threads:
https://www.mersenneforum.org/showpo...7&postcount=33
https://www.mersenneforum.org/showpo...2&postcount=23

Thanks for the links. From https://www.mersenneforum.org/showpo...&postcount=33:
"We used a hardware RNG with calls to BSAFE to generate the primes"
The kind of calls to BSAFE would be interesting, too.
https://en.wikipedia.org/wiki/BSAFE

Originally Posted by jasonp

The standards I'm familiar with do mandate choosing a prime P constructed so that P+-1 have large factors, ...

That's just what I was talking about, I think...