From: Chris Hall <hall@counterpane.com>
Date: Sat, 27 Sep 1997 00:34:30 +0800
To: cypherpunks@cyberpass.net
Subject: Peter Landrock's CRYPTO 97 rump session
Message-ID: <199709261614.KAA00562@asylum.cs.colorado.edu>
MIME-Version: 1.0
Content-Type: text/plain




I know that many of you attended this years CRYPTO and probably went to the
rump session too.  Does anyone remember the details of Peter Landrock's
presentation?  If I recall correctly, he presented an amusing talk in which
an attacker tried to blackmail a bank by claiming knowledge of the bank's
RSA private exponent.  He did this by revealing successive bytes of the
exponent starting with the most significant.  The ransom doubled with each
successive byte revealed (and I believe he got up to 52 in his example). 
The catch was that any person can do this for the first X number of bytes
of the exponent *without actually knowing d* (where X varies depending at
least upon n).

What I would like to know is what the details of the attack were:

1)  Am I out of my mind and there was no such attack?

2)  Given an RSA modulus n and public exponent e, can someone determine the
    X most significant bytes of e (presumably X is less than half of the
    byte length of e)?

3)  If so, what are the restrictions on e?  Are there choices of e which
    make this attack infeasible?

4)  If so, does one get only the most significant bits of d that are
    non-zero (i.e. if d=0x0078... then one gets 0xF000 back as the result)?
    Or does one actually get the "length" of d (i.e. log_2(d) can be
    derived)?

Please post any response to the list (so other people can have the info),
but please Cc me too.  I am subscribed to a filtered version of the list
and may not see the reply.

							Thanks,
							Chris Hall