International Association for Cryptologic Research

International Association
for Cryptologic Research


M. Jason Hinek


Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice)
M. Jason Hinek Charles C. Y. Lam
In this work we re-examine two common modulus attacks on RSA. First, we show that Guo's continued fraction attack works much better in practice than previously expected. Given three instances of RSA with a common modulus $N$ and private exponents each smaller than $N^{0.33}$ the attack can factor the modulus about $93\%$ of the time in practice. The success rate of the attack can be increased up to almost $100\%$ by including a relatively small exhaustive search. Next, we consider Howgrave-Graham and Seifert's lattice-based attack and show that a second necessary condition for the attack exists that limits the bounds (beyond the original bounds) once $n \geq 7$ instances of RSA are used. In particular, by construction, the attack can only succeed when the private exponents are each smaller than $N^{0.5-\epsilon}$, given sufficiently many instances, instead of the original bound of $N^{1-\epsilon}$. In addition, we also consider the effectiveness of the attacks when mounted against multi-prime RSA and Tagaki's variant of RSA. For multi-prime RSA, we show three (or more) instances with a common modulus and private exponents smaller than $N^{1/3-\epsilon}$ is unsafe. For Takagi's variant, we show that three or more instances with a common modulus $N=p^rq$ is unsafe when all the private exponents are smaller than $N^{2/(3(r+1))-\epsilon}$. The results, for both variants, is obtained using Guo's method and are successful almost always with the inclusion of a small exhaustive search. When only two instances are available, Howgrave-Graham and Seifert's attack can be mounted on multi-prime RSA when the private exponents are smaller than $N^{(3+r)/7r-\epsilon}$ when there are $r$ primes in the modulus.
Attribute-Based Encryption with Key Cloning Protection
In this work, we consider the problem of key cloning in attribute-based encryption schemes. We introduce a new type of attribute-based encryption scheme, called token-based attribute-based encryption, that provides strong deterrence for key cloning, in the sense that delegation of keys reveals some personal information about the user. We formalize the security requirements for such a scheme in terms of indistinguishability of the ciphertexts and two new security requirements which we call uncloneability and privacy-preserving. We construct a privacy-preserving uncloneable token-based attribute-based encryption scheme based on Cheung and Newport's ciphertext-policy attribute-based encryption scheme and prove the scheme satisfies the above three security requirements. We discuss our results and show directions for future research.
On some Attacks on Multi-prime RSA
M Jason Hinek Mo King Low Edlyn Teske
Using more than two factors in the modulus of the RSA cryptosystem has the arithmetic advantage that the private key computations can be speeded up using Chinese remaindering. At the same time, with a proper choice of parameters, one does not have to work with a larger modulus to achieve the same level of security in terms of the difficulty of the integer factorization problem. However, numerous attacks on specific instances on the RSA cryptosystem are known that apply if, for example, the decryption or encryption exponent are chosen too small, or if partial knowledge of the private key is available. Little work is known on how such attacks perform in the multi-prime case. It turns out that for most of these attacks it is crucial that the modulus contains exactly two primes. They become much less effective, or fail, when the modulus factors into more than two distinct primes.