## Cryptology ePrint Archive: Report 2019/1052

Improved Cryptanalysis of the KMOV Elliptic Curve Cryptosystem

Abderrahmane Nitaj and 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.

Category / Keywords: public-key cryptography /

Original Publication (with minor differences): ProvSec 2019