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



Relevant Pages

  • Re: central limit theory question
    ... Binomial distribution, and that is different from the very general CLT ... Earth that using the normal approximation makes any kind of sense in ... Going with a poisson approximation of the binomial ... The original question should read: ...
    (sci.math)
  • Re: An exact 1-D summation challenge - 3
    ... I have not a vestige of doubt that you realize that a numeric ... approximation of this series is fairly trivial;-) ... The original question is about the exact summation. ...
    (sci.math.symbolic)
  • Re: An exact 1-D summation challenge - 3
    ... I have not a vestige of doubt that you realize that a numeric ... approximation of this series is fairly trivial;-) ... The original question is about the exact summation. ...
    (sci.math)
  • Re: Symmetric rational approximations of the surface area of an ellipsoid
    ... > A remarkable approximation for the surface area of an ellipsoid is ... But if, as I suspect, the maxima of |relative error| would not be ... be symmetric extreme-perfect rational approximations which are ...
    (sci.math)
  • Re: Approximating a function over an interval
    ... I'm using a microcontroller to measure a voltage by timing the charge of a capacitor. ... Considering the limitations of my platform, I need to find an approximation of this function, using only polynoms. ... I tried to apply Taylor's theorem to the problem, but it does not fit very well because the approximation is good at only one point, but pretty bad over the whole interval. ... for making absolute or relative error smaller in a desired sense. ...
    (sci.math)