Abstract: In many cryptographic applications it is
necessary to generate ellipticcurves (ECs) whose order
possesses certain properties. The method that is usually
employed for the generation of such ECs is the
so-called Complex Multiplication method. This method
requires the use of the roots of certain class field polynomials
defined on a specific parameter called the discriminant.
The most commonly used polynomials are
the Hilbert and Weber ones. The former can be used
to generate directly the EC, but they are characterized
by high computational demands. The latter have usually
much lower computational requirements, but they
do not directly construct the desired EC. This can be
achieved if transformations of their roots to the roots of the corresponding (generated by the same discriminant)
Hilbert polynomials are provided. In this paper we present
a variant of the Complex Multiplicationmethod that
generates ECs of cryptographically strong order. Our
variant is based on the computation of Weber polynomials.
We present in a simple and unifying manner a
complete set of transformations of the roots of aWeber
polynomial to the roots of its corresponding Hilbert
polynomial for all values of the discriminant. In addition,
we prove a theoretical estimate of the precision required
for the computation ofWeber polynomials for all values
of the discriminant.We present an extensive experimental
assessment of the computational efficiency of the
Hilbert and Weber polynomials along with their precision
requirements for various discriminant values and
we compare them with the theoretical estimates.We further
investigate the time efficiency of the new Complex
Multiplication variant under different implementations
of a crucial step of the variant. Our results can serve as
useful guidelines to potential implementers of EC cryptosystems
involving generation of ECs of a desirable
order on resource limited hardware devices or in systems
operating under strict timing response constraints
Abstract: We consider the generation of prime order ellipticcurves
(ECs) over a prime field Fp using the Complex Multiplication (CM)
method. A crucial step of this method is to compute the roots of a special
type of class field polynomials with the most commonly used being the
Hilbert and Weber ones, uniquely determined by the CM discriminant
D. In attempting to construct prime order ECs using Weber polynomials
two difficulties arise (in addition to the necessary transformations of the
roots of such polynomials to those of their Hilbert counterparts). The
first one is that the requirement of prime order necessitates that D ≡ 3
(mod 8), which gives Weber polynomials with degree three times larger
than the degree of their corresponding Hilbert polynomials (a fact that
could affect efficiency). The second difficulty is that these Weber polynomials
do not have roots in Fp. In this paper we show how to overcome
the above difficulties and provide efficient methods for generating ECs of
prime order supported by a thorough experimental study. In particular,
we show that such Weber polynomials have roots in F
p3 and present a
set of transformations for mapping roots of Weber polynomials in F
p3
to roots of their corresponding Hilbert polynomials in Fp. We also show
how a new class of polynomials, with degree equal to their corresponding
Hilbert counterparts (and hence having roots in Fp), can be used
in the CM method to generate prime order ECs. Finally, we compare
experimentally the efficiency of using this new class against the use of
the aforementioned Weber polynomials.
Keywords: EllipticCurveCryptosystems,
Abstract: We present a variant of the complex multiplication method
that generates ellipticcurves of cryptographically strong order. Our variant
is based on the computation ofWeber polynomials that require significantly
less time and space resources than their Hilbert counterparts. We
investigate the time efficiency and precision requirements for generating
off-line Weber polynomials and its comparison to another variant based
on the off-line generation of Hilbert polynomials. We also investigate the
efficiency of our variant when the computation of Weber polynomials
should be made on-line due to limitations in resources (e.g., hardware
devices of limited space).We present trade-offs that could be useful to potential
implementors of ellipticcurvecryptosystems on resource-limited
hardware devices.