Paper 2019/1052

Improved Cryptanalysis of the KMOV Elliptic Curve Cryptosystem

Abderrahmane Nitaj, Willy Susilo, and Joseph Tonien

Abstract

This paper presents two new improved attacks on the KMOV cryptosystem. KMOV is an encryption algorithm based on elliptic curves over the ring ${\mathbb{Z}}_N$ where $N=pq$ is a product of two large primes of equal bit size. The first attack uses the properties of the convergents of the continued fraction expansion of a specific value derived from the KMOV public key. The second attack is based on Coppersmith's method for finding small solutions of a multivariate polynomial modular equation. Both attacks improve the existing attacks on the KMOV cryptosystem.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.ProvSec 2019
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
2019-09-18: received
Short URL
https://ia.cr/2019/1052
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1052,
      author = {Abderrahmane Nitaj and Willy Susilo and Joseph Tonien},
      title = {Improved Cryptanalysis of the KMOV Elliptic Curve Cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1052},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1052}},
      url = {https://eprint.iacr.org/2019/1052}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.