Finding Good Random Elliptic Curves
for Cryptosystems Defined Over GF(2n).
In W. Fumy, editor, Advances in Cryptology -
EUROCRYPT '97: International Conference on the Theory and Application of
Cryptographic Techniques, Konstanz, Germany, May 1997. Proceedings, volume
1233 of Lecture Notes in Computer Science, pages 379-392. Springer Berlin
/ Heidelberg, May 1997..
One of the main difficulties for implementing cryptographic
schemes based on elliptic curves defined over finite fields
is the necessary computation of the cardinality of these
curves. In the case of finite fields GF(2n), recent
theoretical breakthroughs yield a significant speed up of
the computations. Once described some of these ideas in the
first part of this paper, we show that our current
implementation runs from 2 up to 10 times faster than what
was done previously. In the second part, we exhibit a slight
change of Schoof's algorithm to choose curves with a number
of points “nearly” prime and so construct cryptosystems
based on random elliptic curves instead of specific curves
as it used to be.
[ bib |