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

.

**Follow-Ups**:**Re: How to detect RSA keys that are weak?***From:*Mok-Kong Shen

**References**:**How to detect RSA keys that are weak?***From:*Mok-Kong 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:*Mok-Kong Shen

**Re: How to detect RSA keys that are weak?***From:*unruh

- 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):