Realization of coprocessor which supports counting of discrete logarithm on elliptic curves with partial knowledge

In: Bulletin of the Military University of Technology, Band 66, Heft 4, S. 61-78

Abstract

In this paper we analyse realization of a coprocessor which supports counting of discrete logarithm on elliptic curves over the field , where is the large prime, in FPGA. Main idea of the realization is based on using modules which are able to add the points and have relatively small resources' requirements. We showed the simplified case in which we know most significant bits of key and we used one-dimensional Gaudry–Schost method. We also generalize that case and analyse the case when unknown bits are given in many disjoint intervals. To do this we propose using a multidimen-sional Gaudry–Schost method. At the end of this article we show the solution which provides best trade-off between throughput and price of a device.
Keywords: cryptology, elliptic curves, discrete logarithm on elliptic curves (ECDLP), attacks with partial knowledge, multi-dimensional Gaudry-Schost algorithm.