[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Peter Landrock's CRYPTO 97 rump session
In article <[email protected]>,
Chris Hall <[email protected]> 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