Peter Landrock's CRYPTO 97 rump session

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

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
participants (2)
-
Chris Hall
-
iang@cs.berkeley.edu