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 curvesObviously 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 workWe 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.