Improvements to RSA Key Generation and CRT on Embedded Devices

摘要

RSA key generation requires devices to generate large prime numbers. The naieve 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~kq. 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.