Paper 2014/274
Weak instances of composite order protocols
Sorina Ionica and Malika Izabachëne
Abstract
In pairing-based cryptography, the security of protocols using composite order groups relies on the difficulty of factoring a composite number $N$. Boneh~etal~proposed the Cocks-Pinch method to construct ordinary pairing-friendly elliptic curves having a subgroup of composite order $N$. Displaying such a curve as a public parameter implies revealing a square root of the complex multiplication discriminant $-D$ modulo $N$. We exploit this information leak and the structure of the endomorphism ring of the curve to factor the RSA modulus, by computing a square root $\lambda$ of $-D$ modulo one of its factors. Our attack is based on a generic discrete logarithm algorithm. We recommend that $\lambda$ should be chosen as a high entropy input parameter when running the Cocks-Pinch algorithm, in order to ensure protection from our attack.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- composite order groupinteger factorizationelliptic curveendomorphismCoppersmith's algorithm
- Contact author(s)
- sorina ionica @ m4x org
- History
- 2019-08-11: last of 4 revisions
- 2014-04-21: received
- See all versions
- Short URL
- https://ia.cr/2014/274
- License
-
CC BY