🚀 go-pugleaf

In article <skyhawk.712690763@milton> skyhawk@u.washington.edu writes:
:In some recent message, mrr@scss3.cl.msu.edu (Mark Riordan) writes:
:>avalon@coombs.anu.edu.au (Darren Reed) writes:
:>: Hi, I've been looking at implementing RSA encrpytion and have found that
:>: generating the initial keys is a somewhat tricky.  
:>
:>The principal challenge is in finding the two prime numbers that
:>constitute (most of) the private key.  Though there are restrictive
:>guidelines for choosing these if you're really concerned about security,
:>choosing random primes will work.
 
I have posted repeatedly that the restrictions are not necessary.

:Okay, I'll bite.  What are the restrictive guidelines?  All I could find was:
:  p-1 and q-1 should have large prime factors
 
This will be true for arbitrary large primes p & q.

:  gcd(p-1,q-1) should be small
 
This reduces the number of stationary points.

:  p and q should differ in length by a few decimal digits
 
OK, but not really necessary.

: I used:   p = 2xy + 1  (x and y are pseudoprimes)
:
:Pick two psuedoprimes, crank out a candidate for p, and test for primality.
 
You are misusing the term 'pseudoprime'. What you mean is 'probable prime'.
A 'pseudoprime' is actually a probable prime that is composite, e.g. a
Carmichael number.

It is not really necessary that x & y be prime. Further, I recommend
that you make p a strong probable prime.

:Loop until p is prime, repeat for q.  Is this a reasonable method?
 
Expensive.

:Is there something else that should be done to get good p and q?
 
Yes. I have repeatedly discussed the procedure for doing so. 
Briefly:

Select an inteval(s) near the size you want, e.g. 10^100. (and say 10^102)
Sieve out composites divisible by small primes.
Select two strong probable primes p & q such that p-q is reasonably
large (at least 10^25). [This defeats difference of squares methods].
ECM makes restrictions on p-1 and q-1 useless.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"