Information Hiding in the RSA Modulus

The manufacturer of an asymmetric backdoor for a public key cryptosystem manipulates the key generation process in such a way that he can extract the private key or other secret information from the user's public key by involving his own public/private key pair. All asymmetric backdoors in major public key cryptosystems including RSA differ substantially in their implementation approaches and in their quality in satisfying backdoor related properties like confidentiality and concealment. While some of them meet neither of these two properties very well, others provide a high level of confidentiality but none of them is concealing, which limits their use for covert implementation. In this paper we introduce two novel asymmetric RSA backdoors, both following the approach to embed bits of one of the RSA prime factors in the user's public RSA modulus. While our first backdoor provides confidentiality for a sufficiently large key length, it might be detected under certain circumstances. The second backdoor extends the first one such that it additionally provides concealment and is thus particularly suitable for covert implementation.