Fast generation of prime numbers on portable devices: An update. Extended version of this work. Available on http://eprint.iacr.org

Abstract. The generation of prime numbers underlies the use of most public-key cryptosystems, essentially as a primitive needed for the cre-ation 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 re-main scarcely investigated and most real-life implementations are of dra-matically poor performance. We show simple techniques that substantially improve all algorithms previously suggested or extend their capabilities. We derive fast imple-mentations 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