Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2014; 51(5): 1347-1356

Printed September 30, 2014

https://doi.org/10.4134/BKMS.2014.51.5.1347

Copyright © The Korean Mathematical Society.

A new attack on the KMOV cryptosystem

Abderrahmane Nitaj

Universit\'e de Caen

Abstract

In this paper, we analyze the security of the KMOV public key cryptosystem. KMOV is based on elliptic curves over the ring $\mathbb{Z}_n$ where $n=pq$ is the product of two large unknown primes of equal bit-size. We consider KMOV with a public key $(n,e)$ where the exponent $e$ satisfies an equation $ ex-(p+1)(q+1)y=z, $ with unknown parameters $x$, $y$, $z$. Using Diophantine approximations and lattice reduction techniques, we show that KMOV is insecure when $x$, $y$, $z$ are suitably small.

Keywords: cryptanalysis, factorization, Coppersmith's method, continued fraction

MSC numbers: 11T71, 94A60, 14G50