A Novel and Efficient Design for an RSA Cryptosystem With a Very Large Key Size

This brief presents a novel and efficient design for a Rivest-Shamir-Adleman (RSA) cryptosystem with a very large key size. A new modular multiplier architecture is proposed by combining the fast Fourier transform-based Strassen multiplication algorithm and Montgomery reduction, which is different from the interleaved version of Montgomery multiplications used in traditional RSA designs. Anew modular exponentiation algorithm is also proposed for the RSA design. Applying this method, we have implemented 8K/12K-bit and 48K-bit RSA on application-specific integrated circuit designs. The results show that the proposed method gains more advantage as the key size increases, which matches the complexity analysis. Performance comparisons show that the 48K-bit design, which is applicable for both RSA and fully homomorphic encryption, outperforms the previous works with respect to throughput and efficiency.