### 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.ProvSec 2019
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
Short URL
https://ia.cr/2019/1052

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.