Fast RSA-type cryptosystem modulo \(p^k q\). (English) Zbl 0931.94041

Krawczyk, Hugo (ed.), Advances in cryptology - CRYPTO ’98. 18th annual international cryptology conference, Santa Barbara, CA, USA, August 23–27, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1462, 318-326 (1998).
Summary: The author proposes a cryptosystem modulo \(p^k q\) based on the RSA cryptosystem. He chooses an appropriate modulus \(p^k q\) which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method. He also applies the fast decryption algorithm modulo \(p^k\) proposed by T. Takagi [Advances in Cryptology – CRYPTO’97, Lect. Notes Comput. Sci. 1294, 372-384 (1997; Zbl 0890.94025)]. The decryption process of the proposed cryptosystems is faster than the RSA cryptosystem using Chinese remainder theorem, known as the Quisquater-Couvreur method [J.-J. Quisquater and C. Couvreur, “Fast decipherment algorithm for RSA public-key cryptosystem”, Electronic Lett. 18, 905-907 (1982)].
For example, if one chooses the 768-bit modulus \(p^2 q\) for 256-bit primes \(p\) and \(q\), then the decryption process of the proposed cryptosystem is about 3 times faster than that of RSA cryptosystem using the Quisquater-Couvreur method.
For the entire collection see [Zbl 0895.00067].


94A60 Cryptography


Zbl 0890.94025