[Cryptography] factoring small(ish) numbers

Tom Mitchell mitch at niftyegg.com
Tue Oct 14 14:53:48 EDT 2014

On Tue, Oct 14, 2014 at 10:09 AM, Viktor Dukhovni <cryptography at dukhovni.org
> wrote:

> On Mon, Oct 13, 2014 at 07:23:24PM -0400, Jonathan Katz wrote:
> > I'm curious if anyone can point me to references that would indicate
> values
> > of n for which n-bit numbers can be factored "easily."
......good stuff snipped.

> It is only at that point that any large composites with no small
> factors

This may open door number two.
Many key pairs depend on pairs of large primes.
However discovering large pairs is problematic so
large pseudo primes get used.

This does open an attack family because finding
large primes that have not been found by others
seems less likely and pseudo primes present a false
view of the number of valuable underlying bits.

For a laptop or desktop to generate sufficiently interesting
prime number dependent key pairs seems difficult perhaps as difficult
as factoring large pseudo primes.   Perhaps I misjudge difficulty however
we cannot misjudge the importance of the generation and test process.

The method as well as chain and lists of tests used to select pseudo prime
numbers to use
in place of primes can be long or short and if understood well enough could
to be a fruitful  attack path.   <end-two-cents>

  T o m    M i t c h e l l
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141014/96bd2902/attachment.html>

More information about the cryptography mailing list