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