Rabin Cryptosystem and Its Extension

Abstract

The Rabin cryptosystem is an asymmetric cryptographic algorithm. Its security is based on the problem of integer factorization [4]. Rabin cryptosystem has the advantage that the problem on which its security depends is proved to be as hard as factorization [5]. Its minor disadvantage is that each output of the Rabin algorithm is generated by any of four possible inputs. If each output is a cipher text, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext. The process was published in January 1979 by Michael O. Rabin [2]. The Rabin cryptosystem was the first asymmetric cryptosystem where recovering the entire plaintext from the cipher text could be proven to be as hard as integer factorization.