On the efficiency of elliptic curves arising in French literature
Steven D Galbraith
September 21, 2000
Introduction.
The cryptography world has recently been amazed by
the impressive work of Mireille Fouquet, Robert
Harley, Pierrick Gaudry and François Morain.
This team of researchers have managed to crush
existing records for counting points on elliptic
curves over finite fields of characteristic two.
The previous record was held by Frederik Vercauteren
using algorithms based on the ideas of Schoof, Atkin,
Elkies, Couveignes and Lercier. His record was to
count the number of points on an elliptic curve over
the field GF( 2^1999 ).
The work of Fouquet, Harley, Gaudry and Morain [FGHM]
utilises new ideas of Takakazu Satoh. It has allowed
the computation of the number of points on certain
elliptic curves over fields GF( 2^3001 ), GF( 2^3511 ),
GF( 2^4001 ) and GF( 2^5003 ).
The crucial observation we make is that:
The elliptic curves handled by [FGHM] have equations
derived from passages selected from French literature.
The natural conclusion is that:
It is more efficient to count points on elliptic
curves whose curve parameters are derived from French
literature than to count points on random curves.
In this paper we will exploit this new principle to
design elliptic curve cryptosystems with greater
efficiency.
It is worth noting the previous work on point counting
of elliptic curves over finite fields had used curve
parameters chosen from post codes of mathematical
institutes. The main examples of this are the postcodes
of INRIA, Polytechnique France and ENS. The fact that
the records obtained were not as impressive as the
records obtained by considering curves whose parameters
are derived from French literature is further evidence
to support our hypothesis.
Section 1. Elliptic curves from French literature.
We first study the curves used by [FGHM] more closely.
Let F be the finite field GF( 2^n ). For the cases
n = 3001, 3511 and 4001 the elliptic curve chosen was
of the form
y^2 + x y = x^3 + A
and A is a field element represented by a bitstring
which is the ASCII encoding of the quotation
"N'es-tu pas l'oasis où je rêve?"
from Charles Baudelaire (April 9, 1821--August 31, 1867).
For the n = 5003 example the same method was used but
the quotation chosen was
"L'amour est tout, l'amour et la vie au soleil.
Aimer est le grand point, qu'importe la maîtresse?
Qu'importe le flacon, pourvu qu'on ait l'ivresse?"
from Alfred de Musset (December 11 1810--May 2 1857).
The strategy for constructing elliptic curves which are
particularly easy to count points on is apparent. All
that is required is to select a suitable quotation from
19th century French literature, encode it into a bitstring
using ASCII, and then interpret this as an element of the
finite field in the standard way.
2. Implementation of the new scheme
We want to be able to produce French literary curves
provably at random. The usual approach to produce
elliptic curves at random is to choose a random seed S,
apply a cryptographic hash function such as SHA-I to S to
obtain S', and then determine the curve parameters from S'.
This method is not suitable as the output of SHA-I does not
produce bitstrings which arise as ASCII encodings of passages
from French literature. In the next section we propose a new
hash function which we call SHAM (for Secure Hash Algorithm
Modified) which will achieve this goal.
Our protocol is therefore as follows:
(a) Choose a field F = GF( 2^n ), n > 180 prime.
(b) REPEAT
(c) Choose a random seed S.
(d) Define A = SHAM( S )
(e) Construct the elliptic curve E : y^2 + xy = x^3 + A
(f) Compute the number of points N = #E(F) using the
algorithm of [FGHM].
(g) UNTIL N is a small number (< 10 bits) times a prime.
3. The new hash function SHAM
We describe how to compute the bitstring SHAM( S ),
where S is a random seed.
Let S" be the 160-bit output of SHA-I on S. By the
collision resistance and non-invertibility of SHA-I
we see that the cryptographic demand of randomness
will be upheld.
Break S" into three portions P1, P2, P3 as follows:
Let P1 be the rightmost 5 bits, P2 the middle 121 bits
and P3 the leftmost 35 bits. Note that 121 = 11^2 (mod 35).
Define the number m1 to be the integer corresponding
to the bitstring P3 taken modulo the prime 997.
Define the number m2 to be the integer corresponding
to the bitstring P1.
Open "Oeuvres complètes" of Charles Baudelaire
(Robert Laffont (Bouquins); ISBN : 2221502019, 1001
pages; available from www.amazon.fr for 21.57 Euro).
The output of SHAM is defined to be the ASCII encoding
of line number m2 on page number m1.
The bitstring P2 is obviously just random and is only
there to confuse the cryptanalyst.
One Potential fault with this definition of SHAM is that
the line in question may not form a complete sentence.
In fact, this incomplete sentence may have almost no
poetic value at all. This is a problem which we intend
to work a great deal on for our next version of the
paper.
4. Security of the curves
Obviously there will be those skeptics who will argue that
elliptic curves whose parameters are selected from French
literature must be weaker than the general case. These
doomsayers will claim that the speed of point counting
illustrates some hidden structure which could be used to
solve the elliptic curve discrete logarithm problem.
What these curmudgeons will fail to realise is that, due
to the protocol for curve selection outlined in Section 2,
the elliptic curves can be chosen AT RANDOM from the
available set of elliptic curves. They can therefore
not have any more cryptographic weakness than the general
case.
Furthermore, there is a precedent for the security of
elliptic curves whose parameters have been selected by
passages from literature. In the extremely well-argued
paper "Who's afraid of Virginia Woolf elliptic curves"
by Edward Albee (note that many editions of this volume
appear inexplicably with an abbreviated title) it was
proven without doubt (assuming the ABC conjecture for
well-ordering of alphabets and the well-known Wiener-Schinzel
hypothesis) that elliptic curves chosen from the writings
of Virginia Woolf do not suffer reduced security from
among the space of all elliptic curves.
We are confident that similar arguments will apply to our
case. Of course, the extended ABC conjecture for the French
language is well-known to be ambiguous due to the existence
of so-called `accent automorphisms', but we hope a coarse
version of it will suffice.
5. Conclusions and further work
We have described a system to generate elliptic curve
parameters provably at random in a manner which is more
efficient than previous systems. This is obviously of
great benefit in practical elliptic curve applications.
We had hoped to be able to provide a smart-card implementation
for elliptic curve generation but this was not possible for
two reasons:
(a) Our copy of the collected writings of Baudelaire was
larger than 0.5 square cm.
(b) Nigel Smart would not lend us his card.
We stress that the new method is guaranteed not to infringe
any patents or copyright as long as the literature has been
chosen to be old enough.
We are obviously very concerned about the issue of incomplete
sentences as mentioned in Section 3. As is well-known,
incomplete sentences are a great obstacle to
We will be performing further experiments to determine the
security in these cases.
It remains to perform further experiments to see if other
literature in other languages can be used in a similar way.
Our first job will be to consider earlier French literature,
perhaps Voltaire, to see if the performance improvements
hold in this case also. Another candidate for future research
would be the works of Goethe which have the added advantage
of a significantly more enormous keyspace.
Note added in proof: The latest work by FGHM has used an elliptic
curve whose coefficients are derived from the famous Bugs Bunny
catchphrase "What's up doc?". Their success with this curve
suggests hitherto unexpected connections between French literature
and the world of animated cartoons. These connections will surely
provide a rich seam for further investigations.
[FGHM] M. Fouquet, R. Harley, P. Gaudry, F. Morain, various
posts to the NMBRTHRY mailing list. More information can be
found on their web page.