Small Secret CRT-Exponent Attacks on Takagis RSA

概要

論文の詳細を見る
CRT-RSA is a variant of RSA, which uses integers dp = d mod(p - 1) and dq = d mod(q - 1) (CRT-exponents), where d,p,q are the secret keys of RSA. May proposed a method to obtain the secret key in polynomial time if a CRT-exponent is small, moreover Bleichenbacher and May improved this method. On the other hand, Takagis RSA is a variant of CRT-RSA, whose public key N is of the form prq for a given positive integer r. In this paper, we extend the Mays method and the Bleichenbacher-Mays method to Takagis RSA, and we show that we obtain p in polynomial time if $p < N^{3/(4 + 2 \\sqrt{r(r+3)})}$ by the extended Mays method, and if $p < N^{6/(5r + \\sqrt{13r^2 + 48r})}$ by the extended Bleichenbacher-Mays method, when dq is arbitrary small. If r=1, these upper bounds conform to Mays and Bleichenbacher-Mays results respectively. Moreover, we also show that the upper bound of pr increase with an increase in r. Since these attacks are heuristic algorithms, we provide several experiments which show that we can obtain the secret key in practice.