🚀 go-pugleaf

>May I ask an ignorant newbie question please?  It was my understanding that
>the two primes used in most of these public key systems weren't real primes
>at all, but were usually pseudo-primes that had been picked at random and
>tested with statistical methods to give a high *probability* of being prime.
>
>If that is the case, factoring a 500-bit product into two 250-bit primes may
>well reduce to factoring it into 2 125-bit primes and a 250-bit prime, which
>might well be *much* easier.
>
>Am i mistaken?

You are correct in that the "pseudo-primes" used in such systems have not
been proven to be true primes by an exhaustive, theroretically 100% accurate,
analysis.  Any known algorithm that would accomplish this would require so
much computer time as to make it infeasible to run.  The pseudo-primes have,
however, passed stochastic tests which, when applied iteratively, can
guarantee primality to some chosen level of confidence.  Obviously, the
more iterations run, the higher the level of confidence, and it is not
difficult to achieve very high levels of confidence.

You are further correct that, in those rare cases that a composite number gets
past these probabalistic tests, the keys chosen are weaker than the norm, and
most likely significantly weaker.  I have heard it stated, though, that for
the length of primes we are talking about, the probabalistic approach is
provably superior to an exhaustive search.  This is because the exhaustive
approach takes so much more real time that, when you factor in the reliability
of today's best hardware platforms (the chance that the hardware, after going
through all the motions, would not have made a glitch so as to cause an
incorrect result), it is actually easy to achieve a higher confidence with
probabalistic methods.

No one is going to certify completely that your public key will not turn
out to be easily breakable, but statistics is on your side.
-- 
Rob Stampfli  rob@colnet.cmhnet.org      The neat thing about standards:
614-864-9377  HAM RADIO: kd8wk@n8jyv.oh  There are so many to choose from.