The following technical report is available from http://aib.informatik.rwth-aachen.de:
Information Hiding in the Public RSA Modulus Stefan Wüller, Marián Kühnel, and Ulrike Meyer AIB 2015-11
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 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 or 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 work 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.