mersenneforum.org > YAFU three large primes
 Register FAQ Search Today's Posts Mark Forums Read

2021-03-24, 17:50   #56
charybdis

Apr 2020

26410 Posts

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

2021-03-24, 17:52   #57
bsquared

"Ben"
Feb 2007

2×32×191 Posts

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

 2021-03-24, 21:02 #58 jasonp Tribal Bullet     Oct 2004 2·29·61 Posts 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. Last fiddled with by jasonp on 2021-03-24 at 21:04
2021-03-24, 21:14   #59
bsquared

"Ben"
Feb 2007

2·32·191 Posts

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

2021-03-24, 21:18   #60
Till

"Tilman Neumann"
Jan 2016
Germany

22×109 Posts

Quote:
 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?

2021-03-24, 22:48   #61
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5BB16 Posts

Quote:
 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

2021-03-25, 14:03   #62
jasonp
Tribal Bullet

Oct 2004

1101110100102 Posts

Quote:
 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

2021-03-25, 21:23   #63
Till

"Tilman Neumann"
Jan 2016
Germany

6648 Posts

Quote:
 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

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Riesel Prime Search 3 2013-08-20 00:32 jasonp Msieve 24 2010-06-01 19:14 jasonp Factoring 4 2007-12-04 18:32 fivemack Factoring 18 2007-05-10 12:14 Prime Monster Lounge 34 2004-06-10 18:12

All times are UTC. The time now is 03:16.

Sat May 15 03:16:59 UTC 2021 up 36 days, 21:57, 0 users, load averages: 2.11, 2.12, 2.23