From: iang@cs.berkeley.edu (Ian Goldberg)
Date: Sun, 5 Oct 1997 07:29:29 +0800
To: cypherpunks@cyberpass.net
Subject: Re: Peter Landrock's CRYPTO 97 rump session
In-Reply-To: <199709261614.KAA00562@asylum.cs.colorado.edu>
Message-ID: <616iik$rjv$1@abraham.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain



In article <199709261614.KAA00562@asylum.cs.colorado.edu>,
Chris Hall  <hall@counterpane.com> wrote:
>
>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).

IIRC, it only worked for e=3.  In that case, since gcd(e,(p-1)(q-1)) = 1,
we must have that p and q are each 2 mod 3.  Then, since (p-1)(q-1) | de-1,
we have that e d - r (p-1)(q-1) = 1 for some positive integer r.
Taking this mod 3, we see that r is 2 mod 3.  But r = (ed-1)/[(p-1)(q-1)]
< (3(p-1)(q-1)-1)/[(p-1)(q-1)] < 3, so r=2.  Thus d = [2(p-1)(q-1)+1]/3
= 2(n-p-q)/3 + 1.  If p and q are each about half the length of n, then
d agrees with 2(n-1)/3 for about its first half.

   - Ian