On the security of RSA with primes sharing least-significant bits (Q1762562)

An \((\alpha,\beta,\gamma)\)-LSBS-RSA system is one that satisfies the following conditions. (1) The prime factors \(p\) and \(q\) of the public RSA modulus \(N=pq\) have exactly \(\alpha\) equal least-significant bits, that is, \(p-q=r\cdot2^\alpha\) for some odd integer \(r\). An RSA modulus \(N\) with this property is called an \(\alpha\)-Least-Significant-Bit-Symmetric modulus, or simply, \(\alpha\)-LSBS. (2) The \(\beta\) least-significant bits of the RSA secret exponent \(d\) are available to the attacker (e.g. they are included as part of the public-key). For this reason, this setting is called a Partial Key Exposure (PKE) attack scenario. (3) The RSA public-exponent \(e\) has bit length \(\gamma\). When the length \(\gamma\) of the public exponent \(e\) is a small constant, the system is called a low-public-exponent system. The authors show that the latter system is resistant to the PKE attacks in which least-significant bits of the secret exponent are revealed to the attacker. When \(\gamma\) is a constant fraction of the modulus length \(n\), the system is called a large-public-exponent system. The authors show that this type of system is more vulnerable to the PKE attacks than standard RSA.