Fast Generation of Prime Numbers on Portable Devices: An Update

The generation of prime numbers underlies the use of most public-key cryptosystems, essentially as a primitive needed for the creation of RSA key pairs. Surprisingly enough, despite decades of intense mathematical studies on primality testing and an observed progressive intensification of cryptography, prime number generation algorithms remain scarcely investigated and most real-life implementations are of dramatically poor performance.

We show simple techniques that substantially improve all algorithms previously suggested or extend their capabilities. We derive fast implementations on appropriately equipped portable devices like smart-cards embedding a cryptographic coprocessor. This allows onboard generation of RSA keys featuring a very attractive (average) processing time.

Our motivation here is to help transferring this task from terminals where this operation usually took place so far, to portable devices themselves in near future for more confidence, security, and compliance with network-scaled distributed protocols such as electronic cash or mobile commerce.