[PEN-TEST] Off-topic: mathematics of RSA (was Re: RC4)

[Bennett Todd <bet () RAHUL NET>]

2000-11-29-23:35:08 Caskey:
> For some reason most people (including myself) often use the
> expression "one must ... factor ... large prime number[s]" to
> break public key encryption when giving quick explanations of PKE
> but this ends up confusing people. I really don't understand why
> we say this but when you re-read it you realizes you meant to say
> 'one must factor the _product_ of two large prime numbers'. All of
> us can factor arbitrarily long primes in our head :-).

That's a good catch. I didn't even notice this one, and now that you
point it out, I've been guilty of it myself, including the final
reference to factoring in my crypto summary[1] (now fixed:-).

But if you want to be _really_ strictly precisely accurate, RSA (not
other public key algorithms) is based on the difficulty of factoring
composites of two large pseudoprimes; as primality proving is itself
rather expensive, the key generation process doesn't end up actually
proving the primality of the factors, but rather applies a series
of heuristic tests that are almost independant of one and other (an
obscure class of numbers isn't prime and passes all the tests), and
applies them enough times to reduce the odds that the factors are
themselves composite low enough that it can be neglected.

-Bennett

[1] <URL:http://people.oven.com/bet/crypto/>

Attachment: _bin
Description: