Cryptology ePrint Archive: Report 2020/1507

Improvements to RSA key generation and CRT on embedded devices

Mike Hamburg and Mike Tunstall and Qinglai Xiao

Abstract: RSA key generation requires devices to generate large prime numbers. The na\"ive approach is to generate candidates at random, and then test each one for (probable) primality. However, it is faster to use a sieve method, where the candidates are chosen so as not to be divisible by a list of small prime numbers $\{p_i\}$.

Sieve methods can be somewhat complex and time-consuming, at least by the standards of embedded and hardware implementations, and they can be tricky to defend against side-channel analysis. Here we describe an improvement on Joye et al.'s sieve based on the Chinese Remainder Theorem (CRT). We also describe a new sieve method using quadratic residuosity which is simpler and faster than previously known methods, and which can produce values in desired RSA parameter ranges such as $(2^{n-1/2}, 2^n)$ with minimal additional work. The same methods can be used to generate strong primes and DSA moduli.

We also demonstrate a technique for RSA private key operations using the Chinese Remainder Theorem (RSA-CRT) without $q^{-1}$ mod $p$. This technique also leads to inversion-free batch RSA and inversion-free RSA mod $p^k q$.

We demonstrate how an embedded device can use our key generation and RSA-CRT techniques to perform RSA efficiently without storing the private key itself: only a symmetric seed and one or two short hints are required.

Category / Keywords: public-key cryptography / RSA, prime generation

Original Publication (with minor differences): CT-RSA 2021

Date: received 1 Dec 2020, last revised 30 Mar 2021

Contact author: mhamburg at rambus com

Available format(s): PDF | BibTeX Citation

Note: This version includes proofs omitted from the CT-RSA proceedings version.

Version: 20210330:201202 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]