Santanu Sarkar

In this paper, we analyze the security of two variants of the RSA public key cryptosystem where multiple encryption and decryption exponents are used with a common modulus. For the most well known variant, CRT-RSA, assume that n encryption and decryption exponents (el, dpl, dql), where l = 1, …, n, are used with a common CRT-RSA modulus N. By utilizing a Minkowski sum based lattice construction and combining several modular equations which share a common variable, we prove that one can factor N when (Formula presented) for all l = 1, …, n. We further improve this bound to (Formula presented) for all l = 1, …, n. Moreover, our experiments do better than previous works by Jochemsz-May (Crypto 2007) and Herrmann-May (PKC 2010) when multiple exponents are used. For Takagi’s variant of RSA, assume that n key pairs (el, dl) for l = 1, …, n are available for a common modulus N = prq where r ≥ 2. By solving several simultaneous modular univariate linear equations, we show that when (Formula presented), for all l = 1, …, n, one can factor the common modulus N.

Let (N, e) be an RSA public key, where N= pq is the product of equal bitsize primes p, q. Let dp, dq be the corresponding secret CRT-RSA exponents. Using a Coppersmith-type attack, Takayasu, Lu and Peng (TLP) recently showed that one obtains the factorization of N in polynomial time, provided that dp, dq≤ N0.122. Building on the TLP attack, we show the first Partial Key Exposure attack on short secret exponent CRT-RSA. Namely, let N0.122≤ dp, dq≤ N0.5. Then we show that a constant known fraction of the least significant bits (LSBs) of both dp, dq suffices to factor N in polynomial time. Naturally, the larger dp, dq, the more LSBs are required. E.g. if dp, dq are of size N0.13, then we have to know roughly a 15 -fraction of their LSBs, whereas for dp, dq of size N0.2 we require already knowledge of a 23 -LSB fraction. Eventually, if dp, dq are of full size N0.5, we have to know all of their bits. Notice that as a side-product of our result we obtain a heuristic deterministic polynomial time factorization algorithm on input (N, e, dp, dq).

We address Partial Key Exposure attacks on CRT-RSA on secret exponents dp, dq with small public exponent e. For constant e it is known that the knowledge of half of the bits of one of dp, dq suffices to factor the RSA modulus N by Coppersmith’s famous factoring with a hint result. We extend this setting to non-constant e. Somewhat surprisingly, our attack shows that RSA with e of size N112 is most vulnerable to Partial Key Exposure, since in this case only a third of the bits of both dp, dq suffices to factor N in polynomial time, knowing either most significant bits (MSB) or least significant bits (LSB). Let edp= 1 + k(p- 1 ) and edq= 1 + ℓ(q- 1 ). On the technical side, we find the factorization of N in a novel two-step approach. In a first step we recover k and ℓ in polynomial time, in the MSB case completely elementary and in the LSB case using Coppersmith’s lattice-based method. We then obtain the prime factorization of N by computing the root of a univariate polynomial modulo kp for our known k. This can be seen as an extension of Howgrave-Graham’s approximate divisor algorithm to the case of approximate divisor multiples for some known multiple k of an unknown divisor p of N. The point of approximate divisor multiples is that the unknown that is recoverable in polynomial time grows linearly with the size of the multiple k. Our resulting Partial Key Exposure attack with known MSBs is completely rigorous, whereas in the LSB case we rely on a standard Coppersmith-type heuristic. We experimentally verify our heuristic, thereby showing that in practice we reach our asymptotic bounds already using small lattice dimensions. Thus, our attack is highly efficient.