[nando] ------- Forwarded Message Date: Mon, 14 Jun 93 11:21:38 PDT From: burt@RSA.COM (Burt Kaliski) Message-Id: <9306141821.AA06771@RSA.COM> To: rsaref-users@RSA.COM, pem-dev@TIS.COM Subject: Anderson's RSA Trapdoor Can Be Broken Sender: pem-dev-relay@TIS.COM In a recent issue of Electronics Letters, Ross Anderson proposes a trapdoor in RSA whereby a hardware device generates special RSA keys that the device's manufacturer can break easily. The following note, just submitted to EL, shows that the special keys can be broken by anyone, not just the manufacturer. The trapdoor is ineffective. - -- Burt Kaliski RSA Laboratories - ---------------------------------------------------------------------- \documentstyle[12pt]{article} \newcommand{\mat}[2] {\left( \begin{array}{#1}#2 \end{array} \right)} \begin{document} \title{Anderson's RSA Trapdoor Can Be Broken} \author{Burton S. Kaliski Jr.\thanks{RSA Laboratories, 100 Marine Parkway, Redwood City, CA 94065. Email address: {\tt burt@rsa.com}.}} \date{June 11, 1993} \maketitle \begin{abstract} The RSA trapdoor proposed in Ross Anderson's recent letter can be broken. \end{abstract} \section{Introduction} A recent letter by Ross Anderson \cite{anderson-trapdoor} proposes a ``trapdoor'' in the RSA public-key cryptosystem \cite{rsa} whereby a hardware device generates RSA primes $p$ and $p'$ in such a way that the hardware manufacturer can easily factor the RSA modulus $n = pp'$. Factoring the modulus hopefully remains difficult for all other parties. The proposed trapdoor is based on a secret value $A$ known only to the manufacturer. For 256-bit RSA primes, the secret value $A$ is 200 bits long. The device generates primes $p$ of the form \begin{equation} \label{prime-form} p = rA + q = r(q,A)A + q, \end{equation} where $q$ is at most about 100 bits long, and $r$ is 56 bits long and a function of $A$ and $q$. To factor the RSA modulus $n = pp'$, the manufacturer reduces the modulus modulo $A$ to recover the product $qq'$, following the relationship \begin{equation} \label{modulus-form} n = pp' = rr'A^2 + (rq'+r'q)A + qq'. \end{equation} The 200-bit product $qq'$ is easily factored, and the manufacturer recovers the primes $p$ and $p'$ according to Equation \ref{prime-form}. \section{Breaking the trapdoor} While the trapdoor is indeed practical, it can be broken: Factoring such ``trapped'' moduli is easy. Let $n_0, \ldots, n_k$ be a set of such moduli, and let $r_0,r_0', \ldots, r_k,r_k'$ be the corresponding parameters from Equation \ref{modulus-form}. It is easy to show the following inequalities for the given parameter lengths: \begin{equation} \left\| r_0r_0' \frac{n_i}{n_0} - r_ir_i' \right\| \le 2^{-41}, \quad 1 \le i \le k. \end{equation} Such inequalities are called ``simultaneous Diophantine approximations,'' and they are classified as ``unusually good'' if the error term is less than $n_0^{-1/k}$ \cite{lagarias-approx}. For the given parameter lengths, this is so when $k$ is 13 or more. Given a set of moduli known to have such approximations, finding the approximations is straightforward. Following techniques for breaking knapsack cryptosystems (see \cite{brickell-survey}, \cite{lagarias-approx}, \cite{lll}), one finds a set of short vectors in the lattice generated by the basis \begin{equation} \mat{ccccc} {\lambda n_0 & 0 & 0 & \cdots & 0 \\ 0 & \lambda n_0 & 0 & \cdots & \vdots \\ \vdots & 0 & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & \lambda n_0 & 0 \\ - -\lambda n_1 & -\lambda n_2 & \cdots & -\lambda n_k & 1}, \end{equation} where $\lambda$ is an integer near $n_0^{-1/k}$. In most cases, the short vector \begin{equation} \mat{ccccc}{\lambda(r_1r_1'n_0-r_0r_0'n_1) & \cdots & \lambda(r_kr_k'n_0-r_0r_0'n_k) & r_0r_0'} \end{equation} is a member of the set. The secret value $A$ follows from $r_0r_0'$, since, by Equation \ref{modulus-form}, the integer nearest to $n_0/(r_0r_0')$ is $A^2$. One way to overcome this attack is to assign a different secret value to each device, a precaution Anderson has suggested for another purpose. Then a user can only factor his or her own moduli. The user does not need 14 moduli to find $A$, however. Two prime factors $p$ and $p'$ suffice, since the fraction $r'/r$ is such a good approximation to the fraction $p'/p$ that it is guaranteed to be a convergent in the continued fraction expansion of $p'/p$. The user can therefore detect a trapdoor even if the device generates each modulus with a different secret value. \section{Conclusion} The manufacturer's only recourse, at least as far as the proposed trapdoor is concerned, is for the device to generate each modulus with a different secret value and to keep the prime factors secret. In such a situation, the manufacturer may as well preload the device with the primes and escrow copies---a practical ``trapdoor'' to which all cryptosystems, not just RSA, are vulnerable. \section{Acknowledgements} Matt Robshaw offered helpful comments and suggestions. I also thank God (Col. 3:17). \bibliographystyle{plain} \begin{thebibliography}{1} \bibitem{anderson-trapdoor} Ross Anderson. \newblock A practical {RSA} trapdoor. \newblock {\it Electronics Letters}, 29(11):995, 27 May 1993. \bibitem{brickell-survey} E.F. Brickell and A.M. Odlyzko. \newblock Cryptanalysis: {A} survey of recent results. \newblock {\it Proceedings of the IEEE}, 76:578--593, 1988. \bibitem{lagarias-approx} J.C. Lagarias. \newblock Knapsack public key cryptosystems and diophantine approximation. \newblock In D. Chaum, editor, {\it Advances in Cryptology: Proceedings of CRYPTO '83}, pages~3--23, Plenum Press, New York, 1984. \bibitem{lll} A.K. Lenstra, H.W. {Lenstra Jr.}, and L. Lovasz. \newblock Factoring polynomials with rational coefficients. \newblock {\it Math. Annalen}, 261:513--534, 1982. \bibitem{rsa} R.L. Rivest, A. Shamir, and L. Adleman. \newblock A method for obtaining digital signatures and public-key cryptosystems. \newblock {\it Communications of the ACM}, 21(2):120--126, February 1978. \end{thebibliography} \end{document} ------- End of Forwarded Message