The attached report contains a comprehensive survey of our results on
distributed generation of shared RSA keys.  These results are a central
component of our Intrusion Tolerance project. 

A private RSA key is often stored (encrypted) at a single location
such as a user's machine. The machine then becomes a prime target for a
hacker who wishes to obtain the private key.  To protect a highly
sensitive private key (such as the one belonging to a root
Certification Authority) one may wish to split the key into a number
of pieces and store each piece at a separate location. Fortunately,
for the RSA cryptosystem it is possible to share the private key among
several sites without having to reconstruct the key in order to use it
--- a root CA can issue certificates without reconstructing its
private key at a single location. To explain how this is done we
briefly recall the details of the RSA system.  Let $N=pq$ be a product
of two large prime. Let $e$ be a public certificate verification
exponent.  Let $d$ be a private certificate issuing exponent. We have
that $d \cdot e = 1 \bmod \phi(N)$ where $\phi(N) = N-p-q+1$. A public
RSA key is made up of $\lcat e,N \rcat$. A private key is made up of
$\lcat d,N \rcat$ (the private key often includes other information
such as $p$ and $q$ for efficient signature generation).
To share its private key among four sites, the root CA does the
following: it picks four random integers $d_1,\ldots,d_4$ in the range
$1, \ldots, N$ such that $d_1+d_2+d_3+d_4 = d$. Each of these shares
is then stored (encrypted) in a separate location. To issue a
certificate, the CA can create a signature on a message $m$ by having
each site compute $s_i = m^{d_i} \bmod N$. Each site then sends $s_i$
to the entity requesting the certificate. The requesting entity can
multiply the four $s_i$'s to obtain $s = m^{d_1+d_2+d_3+d_4} =m^d \bmod N$.  
Thus, a valid signature is
obtained.  The beauty of this simple procedure is that the private key
$d$ is never reconstructed at a single location.  If a hacker
penetrates even three of the four sites, he obtains no information
about the private key.  To achieve fault-tolerance the above scheme
may be slightly modified so that any 3-out-of-4 sites can issue
a certificate.

An important issue left out of the above discussion is key generation.
Who generates the modulus $N$ and the private key $d$?  
A simple solution is to ask a {\em trusted dealer} to generate two
primes $p$ and $q$, multiply them to get $N$ and then generate $e,d$. Finally,
the dealer splits $d$ into four pieces and sends each piece to each
of the sites. Unfortunately, a trusted dealer introduces a {\em single point
of attack}: the dealer, or anyone who compromises the dealer, knows the
private key and can issue false certificates. Our research on distributed
generation of shared RSA keys eliminates the need for a trusted dealer.
The four sites can jointly generate a shared key such that neither one
of them known the private key $d$ or the factorization of $N$.
Our algorithms are useful also in other contexts, such as the
Fiat-Shamir authentication scheme where a number of entities use
a modulus $N=pq$ for authentication, but none of them should know the
factorization of $N$. The original Fiat-Shamir scheme called for a
trusted dealer to generate $N$. Our research eliminates the need for
a trusted dealer.

We briefly outline our approach. Our goal is to have $k$ machines generate
a modulus $N=pq$ and exponents $e$ and $d$. At the end of the computation
all parties should be convinced that $N$ is the product of two primes,
however none of them should know the factorization. Furthermore, $e$ should
be public while $d$ should be shared among the machines in a way that
enables $t$-out-of-$k$ threshold signature generation. That is, any $t$
machines should be able to issue a certificate. At the same time,
an attacker who penetrates at most $t-1$ machines should not be able to
obtain any information about the private key. Our key generation algorithm
proceeds in a number of steps. At a high level these steps are as follows:

\begin{description}
\item[(1) pick candidates:] 
Each of the $k$ machines picks two random $n$-bit integers $p_i,q_i$
and keeps them secret.

\item[(2) compute $N$:]
Using a private distributed computation the $k$ machines compute
\[  N = (p_1+\ldots+p_k) \cdot (q_1+\ldots+q_k) \]
Other than the value of $N$, this step
reveals no information about the secret values
$p_1,\ldots,p_k$ and $q_1,\ldots,q_k$  (!)
Now that $N$ is public, the $k$ machines apply trial division 
to ensure that $N$ is not divisible by small primes.

\item[(3) primality test:] The $k$ machines engage in a private
distributed computation to test that $N$ is 
the product of two primes.  If the test fails, then the protocol
is restarted from step 1.   As before, this step reveals no information
about the private shares.

\item[(4) key generation:] Given a public encryption exponent $e$,
the machines use a private distributed computation to generate a
{\em shared} secret decryption exponent $d$. 
\end{description}

Part I of the attached report gives the full details of each of these steps.
A number of practical optimizations that we used in the
implementation of the algorithm are presented. A description of our
implementation including timing measurements is given in~\cite{MWB98}. 
Part II describes an 
extension of our algorithm enabling $k$ machines to generate a modulus
$N$ which is the product of {\em three} large primes $N=pqr$. Generating
an RSA modulus with three primes has some advantages over standard RSA
and is occasionally used. The two parts are expanded versions of
our papers that recently appeared in technical conferences.


