On the uniformity of distribution of the decryption exponent in fixed encryption exponent RSA

Let us fix a security parameter n and a sufficiently large encryption exponent e. We show that for a random choice of the RSA modulus m = pq, where p and q are n-bit primes, the decryption exponent d, defined by ed equivalent to 1 (mod phi(m)) is uniformly distributed modulo phi(m). It is known, due to recent work of Boneh, Durfee and Frankel, that additional information about some bits of d may turn out to be dramatic for the security of the whole cryptosystem. Our uniformity of distribution result implies that sufficiently long strings of the most and the least significant bits of d, which are vulnerable to such attacks, behave as random binary vectors. (C) 2004 Elsevier B.V. All rights reserved.