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

People

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