mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2021-03-24, 17:50   #56
charybdis
 
charybdis's Avatar
 
Apr 2020

1111110012 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
charybdis is offline   Reply With Quote
Old 2021-03-24, 17:52   #57
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·1,789 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
bsquared is offline   Reply With Quote
Old 2021-03-24, 21:02   #58
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2021-03-24, 21:14   #59
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

67728 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
bsquared is offline   Reply With Quote
Old 2021-03-24, 21:18   #60
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

11·43 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
Till is offline   Reply With Quote
Old 2021-03-24, 22:48   #61
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×13×23 Posts
Default

Quote:
Originally Posted by Till View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2021-03-25, 14:03   #62
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,181 Posts
Default

Quote:
Originally Posted by Till View Post
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
jasonp is offline   Reply With Quote
Old 2021-03-25, 21:23   #63
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

7318 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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 View Post
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...
Till is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where do I send my PRP primes with large k? Trilo Riesel Prime Search 3 2013-08-20 00:32
48-bit large primes! jasonp Msieve 24 2010-06-01 19:14
NFS with 5 and 6 large primes jasonp Factoring 4 2007-12-04 18:32
Why only three large primes fivemack Factoring 18 2007-05-10 12:14
What is the use of these large primes Prime Monster Lounge 34 2004-06-10 18:12

All times are UTC. The time now is 19:41.


Tue Oct 26 19:41:02 UTC 2021 up 95 days, 14:10, 0 users, load averages: 1.69, 1.85, 2.22

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.