FORWARD: Burt Kaliski: Anderson's RSA Trapdoor Can Be Broken

[Henry Strickland]

[nando]
------- Forwarded Message

Date: Mon, 14 Jun 93 11:21:38 PDT
From: burt at RSA.COM (Burt Kaliski)
Message-Id: <9306141821.AA06771 at RSA.COM>
To: rsaref-users at RSA.COM, pem-dev at TIS.COM
Subject: Anderson's RSA Trapdoor Can Be Broken
Sender: pem-dev-relay at 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 at 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