Re: How to detect RSA keys that are weak?



On Dec 1, 9:54 am, unruh <un...@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
On 2010-12-01, Mok-Kong Shen <mok-kong.s...@xxxxxxxxxxx> wrote:





Pubkeybreaker wrote:

"But
suppose the bad guy wants to leak the factors,
and can somehow arrange that q is approximately
2.25 times p. So N = pq ~= 2.25p^2; since N is
known, sqrt(N) is approximately 1.5p! A search of
about log N around that point will quickly reveal
the factors. "

Note the words "approximately 2.25 times p".  This
is DIFFERENT  from "first prime greater than exactly 2.25p"

I don't understand the energy spent in this dispute. If an opponent
knows that q is approximately r*p OR has the quality of the other
variant mentioned, with r known to him, then he evidently has an
edge of advantage over another that has no knowledge of that.

ONLY if (and it is a bif *if*) a direct search via trial division has
a search
space small enough to be faster than a general factoring method such
as GNFS.

(This
was what you wanted me to explain in your last follow-up to my post.)

His point was that if all you know is that q is somewhere between 1.25
times p or 1.26 times q, that .01p still contains 10^148  numbers which is
far far too many to search. (assuming p and q are 512 bits)


One can get a far better approximation to r than an error of .01
and it will
STILL leave a search space that is too big. Depending on the amount
of
computational resources, one needs to know r to an error of no more
than (say)
10^-100 before the information becomes useful.


However since approximately was being used in the sense of 1.025p and
(1.025+ln(p)/p)p as was clear from the statement of how many numbers
there were to search(ln(N)),

This was not stated as part of the original question, it was stated as
a proposed
ANSWER.

The original statement essentially said "approximately rp". In
computational number theory
this normally means "rp with bounded relative error", but you and
MKS
have chosen to interpret it as "rp with bounded o(1) error". i.e.
you want the relative error
to go to 0 as p -->oo and this is not what "approximately" usually
means.
.