A Fast RSA-Type Public-Key Primitive Modulo pkq Using Hensel Lifting

Tsuyoshi TAKAGI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A    No.1    pp.94-101
Publication Date: 2004/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Asymmetric Cipher
RSA cryptosystem,  PKCS #1 version 2.1,  factoring,  modular inverse,  fast decryption,  smart cards,  

Full Text: PDF(244.8KB)>>
Buy this Article

We propose a public-key primitive modulo pkq based on the RSA primitive. The decryption process of the proposed scheme is faster than those of two variants of PKCS #1 version 2.1, namely the RSA cryptosystem using Chinese remainder theorem (CRT) and the Multi-Prime RSA. The message M of the proposed scheme is decrypted from M mod pk and M mod q using the CRT, where we apply the Hensel lifting to calculate M mod pk from M mod p that requires only quadratic complexity ((log2p)2). Moreover, we propose a trick that avoids modular inversions used for the Hensel lifting, and thus the proposed algorithm can be computed without modular inversion. We implemented in software both the proposed scheme with 1024-bit modulus p2q and the 1024-bit Multi-Prime RSA for modulus p1p2p3, where p,q,p1,p2,p3 are 342 bits. The improvements of the proposed scheme over the Multi-Prime RSA are as follows: The key generation is about 49% faster, the decryption time is about 42% faster, and the total secret key size is 33% smaller.