RSA Weak?

[Alexander W. Janssen]

On 11/2/07, Robert J. Hansen <rjh at sixdemonbag.org> wrote:
> 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))

Thanks. Though I must admit I must think about it before making a comment on it.

> 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.

Was meant to be read as:
As you add a bit you double the keyspace, but you said something else
about it more below.
But you're argument that it "asymptotically grows better" worries me
when I think of my concept of asympotic - you mean, that the length of
the key and the probabilty of finding the factors converge?

> > 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.

Not really; if it scale exponentially, it wouldn't worry me.

> The entire point is that the keyspace grows exponentially.

That's what I meant.

> You were
> arguing the exponential factor is two, which it's definitely not.

Uh. Did I say this?
Yes, "doubles the keyspace"... Unlucky statement. Yet true?

> 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.

Is that related to the approximated formular - density of primes - you
gave above?
Must think of it.

> 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.

I read about it without further thinking about it.
Hey. I ain't no mathematician and last math-session at my Uni is years ago... :)

> > 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?

No, like in runtime, finding your way through the problem. But see below:

> > 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.

And that was my problem: You are absolutely right: I was implying
(wrongly) that finding a prime is in the same class as *factoring*
primes. Which is absolutely wrong.

Thanks for your clarification. Makes more sense now, although I'm not
entirely enlighted yet...

Alex.


-- 
"I am tired of all this sort of thing called science here... We have spent
millions in that sort of thing for the last few years, and it is time it
should be stopped."
 -- Simon Cameron, U.S. Senator, on the Smithsonian Institution, 1901.


.