##
**
Generating RSA keys on the Palm Pilot With the
Help of an Untrusted Server
**

**People**

Dan Boneh, Nagendra Modadugu, Mike Kim

**Description**

Palm size devices are gradually getting more and more popular in authentication
and eCommerce applications. However, they have limited computing power for
cryptographic operations. For example generating a 1024 bit RSA key on a
Palm Pilot can take upto 20 minutes, while it takes under half a minute on
most modern Pentium class desktops.

The motivation for the project is to reduce the RSA key generation time on the
palm size devices by seeking help from server(s) with the constraint the factorization
of the RSA modulus remains unknown to the aiding server(s).
We implement our protocols on the Palm Pilot and demonstrate how the
generation of *unbalanced* RSA keys may be speeded up
with the aid of either one or two servers.

**Publications**

Generating
RSA keys on the PalmPilot with the help of an untrusted server. by N. Modadugu, D. Boneh, and M. Kim.

To appear in *RSA Data Security Conference and Expo 2000.*

Full paper: PostScript.

**Technical Summary**

The project involves server aided RSA key generation for low power computing
devices such as handhelds. It is desirable that there is a significant
improvement in generation times and also that the servers involved have no
information about the key at the end of the computation.
We explore means by which servers may aid in key generation:

- the RSA key is generated on a
*trusted* server and sent to the Pilot over
a secure channel.
- an
*unbalanced* RSA key is generated with the aid of two
*untrusted* servers.
- an
*unbalanced* RSA key is generated with the aid of one
*untrusted* server.
- an RSA key is generated with the aid of two
*untrusted* servers.

*Unbalanced* here means the RSA modulus *n = pR*, where *p*
is prime, but *R* is a random number of size approximately eight times the
number of bits of *p*.
When RSA keys are generated locally on the pilot, majority of the time is
spent on determining whether a number is prime. We show that this step may
be speeded up with the aid of servers.

In all three cases, the pilot begins by picking random integers and
carries out a 'sieving' step. Sieving here means that candidates are
checked for having small factors, and are discarded if so. Once this step
is done, we show how exponentiation, the computationally heavy step, may
be off-loaded to server(s) without revealing any information about the
factorization of *n* itself. If the candidate turns out to be
composite, the entire process is repeated.

**Download**

Go to the distribution page for details

nagendra at cs.stanford.edu
Last modified: Fri Oct 15 13:04:54 PDT 1999