From dawagner@tucson.princeton.edu Wed Nov 23 23:10:50 EST 1994
Article: 30625 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Subject: Re: Secure Voice is Here NOW!
Message-ID: <1994Nov24.040930.15509@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: tucson.princeton.edu
Organization: Princeton University
References: <3ag744$1f4@news1.delphi.com> <3amrig$pb4@news.umbc.edu> <1994Nov20.181245.21965@Princeton.EDU> <3as1m4$fri@news1.shell>
Date: Thu, 24 Nov 1994 04:09:30 GMT
Lines: 70

In article <3as1m4$fri@news1.shell>, Hal <hfinney@shell.portal.com> wrote:
> dawagner@tucson.princeton.edu (David A. Wagner) writes:
> 
> >We know |x - kq| < sqrt(q) for some k.  Divide by n=pq to see
> >|x/n - k/p| < 1/(p sqrt(q)).  If p and q are approximately the
> >same size, this means that |x/n - k/p| < O(p^(-3/2)).  Note that
> >x/n is known to the cryptanalyst. Also, the continued fractions
> >expansion of x/n will generate all approximants a/b to x/n which
> >have error at most O(1/b), since x/n is rational.  Thus the
> >continued fractions algorithm will generate k/p as one of its
> >approximants.
> 
> Without commenting on the rest of David's post, I don't think this
> is necessarily true of continued fractions.
> 

You're absolutely correct; I should've looked it up in a number
theory textbook instead of relying on my memory.  My bad.

My notes from my number theory class say (yes, this time I
actually checked! :-) that the continued fractions algorithm
will only generate approximants a/b which have error at most
c b^(-2) [NOT O(1/b) as I erroneously stated before].  Here c
is a small positive constant -- something like 1/2 or 2/(1+sqrt(5))
or somesuch.

I also took the time to code up a simulation using the GNU mp
package.  In fact, my proposed method does not succeed in factoring
n given the pair (x,n) when p,q have approximately the same size.
Hal's objections were correct.  Thank you, Hal, for pointing
out the flaw.

Note that if q ~ p^2, then the error will be ~ 1 / p^2, so in
this case, the continued fractions approach should succeed in
factoring n.  In fact, my simulations bear this out.  On the
other hand, everyone already knew that one should pick p,q to
be approximately the same size, anyhow, so this "attack" is
only of academic interest, and even then, only of interest to
one particular academic: me!  <smirk>

To go off on a tangent...  Does anyone understand multiple
approximation?  Are there any algorithms analogous to continued
fractions which solve the generalized multiple Diophantine
approximation problem?

For those who haven't been inducted into the jargon, I'll
explain.  The continued fractions algorithm finds a,b with
	|y - a/b| < c b^(-2)
for some given y.  The multiple approximation problem is to
find a_1, ..., a_k, b such that
	|y_j - a_j/b| < c b^u	for j=1,2,...,k
for some given y_1, ..., y_k.  [Here u = -(1 + 1/k).]  Does
anyone know if there are any efficient algorithms to solve
the multiple approximation problem?

Here's why I'm asking: suppose I have n, x_1, and x_2 such
that n=pq is a RSA modulus and x_1, x_2 are within sqrt(q) of
a multiple of q.  Then note that
	|x_j/n - a_j/p| < c q^(-3/2)	for j=1,2
if p,q are of approximately the same size; thus, if we can
find all multiple Diophantine approximations, we should encounter
p as denominator of one of the approximations.  I think.

Then again, maybe it's not worth wasting time on this approach
if the amazing Don Coppersmith will show us how his attack works. :-)

[Newsgroups trimmed; this has nothing to do with politics...]

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu