A new attack on the KMOV cryptosystem
Bull. Korean Math. Soc. 2014 Vol. 51, No. 5, 1347-1356
https://doi.org/10.4134/BKMS.2014.51.5.1347
Printed September 30, 2014
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
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd