RSA Weak?

[Robert J. Hansen]

Alexander W. Janssen wrote:
> I'm not too familiar with prime- or number-theory. Does that scale in
> the same factor in all keyspaces?

A good first-order approximation for the number of primes with a certain
number of bits is given by the formula:

  X = 2**number of bits
  Y = 2**(number of bits - 1)

  (X ln Y - Y ln X) / ((X ln Y) * (Y ln X))

I don't know what you mean by 'scale by the same factor'.  But hey, if
you want approximations, there you go.  For small numbers this will be
off by a significant amount, but it asymptotically grows better.

> However, the fact that primes get more rare when the keyspace is
> expanded isn't necessarily connected to that point that you still need
> to check the whole keyspace - which stills grows linearly?

If the keyspace grew linearly, it would be a trivial problem to factor.
 Just throw more cycles at it.

The entire point is that the keyspace grows exponentially.  You were
arguing the exponential factor is two, which it's definitely not.  In
reality the exponential factor of difficulty added per bit changes
depending on how large your key already is.  If your key is small,
adding one bit can substantially increase your security.  If your key is
large, adding one bit is a who-cares? proposition.

If it helps, the National Institutes of Science and Technology (NIST)
has estimated a 1024-bit key is roughly equivalent in computational
complexity to an 80-bit symmetric key.

> In cleartest: Even if primes get more rare, you still need to find
> your whole way through *all* numbers as long as you don't find a
> better algorithm.

Such as, say, the generalized number field sieve?

> Putting probalistic prime-tests aside.

This has no connection whatsoever with factoring.  Miller-Rabin is used
to test primality; it does not give you any useful information about the
factors of a number.