Re: How to detect RSA keys that are weak?
 From: Pubkeybreaker <pubkeybreaker@xxxxxxx>
 Date: Wed, 1 Dec 2010 07:19:27 0800 (PST)
On Dec 1, 9:54 am, unruh <un...@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
On 20101201, MokKong Shen <mokkong.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 followup 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.
.
 FollowUps:
 Re: How to detect RSA keys that are weak?
 From: MokKong Shen
 Re: How to detect RSA keys that are weak?
 References:
 How to detect RSA keys that are weak?
 From: MokKong Shen
 Re: How to detect RSA keys that are weak?
 From: Pubkeybreaker
 Re: How to detect RSA keys that are weak?
 From: Pubkeybreaker
 Re: How to detect RSA keys that are weak?
 From: Pubkeybreaker
 Re: How to detect RSA keys that are weak?
 From: MokKong Shen
 Re: How to detect RSA keys that are weak?
 From: unruh
 How to detect RSA keys that are weak?
 Prev by Date: Re: How to detect RSA keys that are weak?
 Next by Date: Re: How to detect RSA keys that are weak?
 Previous by thread: Re: How to detect RSA keys that are weak?
 Next by thread: Re: How to detect RSA keys that are weak?
 Index(es):
Relevant Pages
