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

Date: received 16 Sep 2019

Contact author: abderrahmane nitaj at unicaen fr

Available format(s): PDF | BibTeX Citation

Version: 20190918:123841 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]