[This article contains some observations on my efforts working with the Atkin Morain method for setting up non isomorphic prime order elliptic curves, mainly for the use of cryptographic software development teams.
The main references on the Atkin Morain method are refs. 3 and 5. The latter was the original reference, but Ref. 3 provides a better source for software writers wanting to get an Atkin Morain capability up and running.
This article is not intended to cover the Atkin Morain method in detail, although I do touch on the highlights so that beginners can follow it.
To understand this article you will only need to know enough 'Number Theory' to know what finite Fields and quadratic residues are; but little beyond this.]

  With many authorities now recommending minimum bit sizes up to 4000 bits and beyond for the RSA public key algorithm, and this figure increasing rapidly, the practicality of the RSA algorithm has faded away. The most obvious replacement is the elliptic curve (E.C.) public key method. For comparable security, elliptic curves can be smaller in size and are faster in operation.

  In recent times, cipher systems conventionally use a two stage procedure :- The first stage uses a 'public key cipher' technique to 'arrange' a session key between the communicating parties, and the second stage a 'block cipher' which actually carries out message encryption/decryption using the session key. Block cipher techniques are typically several hundred times faster than public key cipher techniques, hence this 2 stage approach achieves a good balance between convenience in operation and speed. Clearly, both ciphers have to be of comparable cryptographic strength, since overall security depends on the weaker of the two.

  There are, in the public domain, estimates of computer effort needed to 'break' ciphers, and in ref. 2, pg. 19 these estimates are used to obtain the following table of bit sizes needed for a balanced security cipher system when either RSA or an elliptic curve provides the public key first stage :-

Block cipher algorithm	SKIPJACK	Triple DES	AES small	AES medium	AES large
Block Strength (Bits)	80	112	128	192	256
req. E.C. Field bit size	160	224	256	384	512
req. RSA 'N' bit size	1024	2048	3072	8192	15360!!!

  The RSA parameter 'N' bit size of 15360 bits, needed to balance a 256 bit AES (large) key, should be noted. Very few cipher packages support RSA bit sizes anywhere approaching that! (and those that don't are 'not fit for purpose'). Even if they did, the RSA stage would be impracticably slow.

  Notice from this table that, for balanced security, the Field bit size of the elliptic curve has to be double the bit strength of the block cipher which it is paired with. [This is a 'rule-of-thumb' rather than an iron law, but it is unwise to deviate far from it.]

[From an inspection of the table above, it would be easy to get a false impression of RSA vs elliptic curve speed performance. Very roughly RSA encryption time goes up as the cube of the bit size of 'N', and elliptic curve encryption time as 12-15 times the cube of the bit size of the Field prime. Hence elliptic curves out speed RSA for all the bit sizes in the table, and the speed ratio increases as bit size increases. However, the speed ratio is not quite as great as a casual inspection of the table might suggest.]

[Note that AES is short for the Advanced Encryption Standard competition to select a replacement for the DES block cipher. There were 5 finalists in this competition - MARS, RC6, Rijndael, Serpent and Twofish. All these finalists were found to provide satisfactory security. Rijndael was selected (late 2000) as the winner (largely on considerations of utility), but the other 4 entrants were not rejected. Today, AES and Rijndael are synonymous, but the other entries are worthy of consideration. Of particular interest is that Serpent is widely quoted in the literature as being the most secure, if a little slow running in software. If security is an over arching consideration, Serpent may be for you.]
[Note also that the AES competition was to provide encryption for "... sensitive but not classified information." If you plan to rule the world! none of the AES finalists will do. (see rt_home.html for a fast Rijndael implementation and some suggestions for extending it.) (see also ref 4, Chapter 15 for methods to combine block ciphers to produce stronger encryption.)]

  Anyone setting up a new cryptographic software package using an elliptic curve first stage needs to find a suitable elliptic curve. Many elliptic curves are available in the literature, but those in the Federal Information Processing Standards publication FIPS PUB 186-2 are particularly noteworthy. In 186-2 (amongst other elliptic curves) a 521 bit Field prime of special format is given for pairing with AES large. The special format of this prime enables a fast 'mod' operation when doing Field arithmetic (see Ref. 4 for a detailed discussion of the software implementation of these elliptic curves for best performance.) However all cryptographic systems are susceptible to 'attrition' attacks, whereby regular patterns in their characteristics and operational use are sought by analysts and then used to weaken and eventually break them. In this way the security of all cryptographic systems slowly decays. (I should add here that I know of no 'attrition' attack against elliptic curve systems; but what I know and what the professionals of national intelligence agencies know are 2 different things!) It is expedient to factor this possibility into security planning. The greater the damage that would result from a break into a cryptographic system, the greater the need to change public key system parameters regularly, so as to contain it.

  Many sensitive applications of cryptography require public key system changes perhaps every few weeks, or less, and this must be easy to accomplish. With elliptic curve public key systems, this is conventionally achieved by changing to a new 'base point' on a fixed elliptic curve; but a technically superior tactic would be to move to a new elliptic curve over, possibly, a new Field prime as well. A problem that has prevented this obvious defensive tactic being employed in the past, is the difficulty of setting up suitable new elliptic curves quickly. The great difficulty to be overcome is that of finding the number of points on an elliptic curve (what mathematicians call the 'order' of an elliptic curve) This number should ideally be a prime number. Elliptic curves with non prime orders may have cryptographically weak sub-group structures. Just obtaining the order of a random elliptic curve over a random Field prime is a computationally severe task; and since the order of a random elliptic curve once found is unlikely to be a prime, the sub-group structure then needs checking and this is a further computationally severe task.

  A major factor in assessing the cryptographic security of an elliptic curve public key package, is the group structure of the points on the EC. It can be proven (see ref. 2, section 3.1 or ref. 6 section 2.6) that the sub-group structure consists of either a single group (containing all the EC points) (mathematicians call this an EC of rank 1) or a direct sum of 2 (and no more than 2) sub-groups (a rank 2 EC). [In other words EC's never have ranks of 3 or more.]
  If a curve has a rank of 2, with sub-group orders (the number of elements in the sub-group) of say n₁ and n₂ then the following equations would apply :-
(a) The number of points on the EC (the order of the EC - label it  #E(Fp) )  = n₁ x  n₂
(b) If   n₂ < n₁   then  n₂  divides both  n₁ and  (p-1).
On this web site I only consider the case with the order of the EC a prime. When this is the case, n₂ = 1 and n₁ = #E(Fp) is the only possible solution to the equations above.
[Note that there is always a trivial sub-group of order 1 for any group. For an EC this sub-group contains the single element O - the 'point at infinity' (the group identity element). Avoidance of the use of the group identity element in any cryptosystem, is both obvious and necessary.]
[If n₂ was not 1, (i.e. the curve was of rank 2) special efforts would be required by a cryptographic package development team to exclude members of this small sub-group. Failure to do so can wreck cryptographic security.]
[If n₁ is a prime a few bits smaller than #E(Fp), then n₂ will again be 1 i.e. the EC will again be rank 1. This is a common and satisfactory scheme in cryptographic products, but not discussed on this web site. Clearly, curves of this type will be far more numerous than prime order EC's.]
  On this web site, only prime order (hence rank 1) curves are considered. For such curves the possible malignant sub-group problem does not exist. Also for rank 1 curves the values #E(Fp) and n₁ are interchangeable. On this web site, I shall use the phrase 'order of the curve' in preference to 'group order'.

  Elliptic curves can be categorized as supersingular or non supersingular. A supersingular curve has a 'trace' value such that its square equals one of {0, q, 2.q, 3.q or 4.q} (see ref. 6 corollary 2.1.1).
[Recall that the 'trace' is defined from :-
     #E(Fq) = q + 1 + trace,
     where   -2.SQRT(q) <= trace <=  2.SQRT(q)  (Hasse's Theorem)]
  When m = 1 (i.e. q = p), an EC can only be supersingular if the trace = 0. In this case #E(Fp) = (p+1); but this is an even number and hence not prime. Hence when q = p and #E(Fp) is a prime the resultant EC can never be supersingular. Put another way, on this web site only non supersingular curves are being considered.
  The importance of the point above is that, for cryptographic purposes, not all EC's are of the same quality. When used for some cryptographic purpose, EC's (usually) 'hide behind' the difficulty of calculating discrete logarithms, This is the so-called DLP or discrete logarithm problem. The difficulty of solving the DLP varies with the underlying entity in which arithmetic is being done. For instance, the DLP within finite Fields has roughly the same difficulty as factoring composite integers (bit sizes being equal). Roughly, this means that, for comparable security, if a security product were to 'hide' behind the DLP in a finite Field, the Field bit size would need to be roughly the same as the bit size of parameter 'N' in the RSA algorithm - but the table above makes clear that the RSA algorithm is now so weak that huge bit sizes are needed to achieve balanced security even with the block ciphers currently in use. The same general trend is present with public key components that exploit the DLP over a finite Field. They are (more or less) equally incompetent. An ugly fact is now needed - some types of EC can be mapped onto finite Fields, whereupon an attacker can (possibly) solve the weaker DLP in a finite Field, and hence solve the EC DLP! In particular supersingular EC's are of this type. Clearly a supersingular EC used in a cryptographic product is a 'sheep in wolf's clothing' - potentially very dangerous. Considering that the 'number crunching' to drive an EC is 12-15 times that of an RSA module of the same bit size, without additional security benefit, use of supersingular curves is ridiculous.
The table above is only valid when the EC's in use are those for which no 'shortcut' attack is known.
  That begs another question : What type of EC has no 'shortcut' attack. Another ugly fact - no one knows! Although certain types of EC have been found to be weak, no one knows whether all the weak types have been discovered! What to do about this? The best that can be done is to find an expert, gather his recommendations and then hope that he is right. Since new methods of attack are constantly being produced, the visits to your expert will need to be both regular and often.
  So what expert advice can we find. In ref. 1 Chapter V known methods of attacking EC's are analyzed and 3 properties for cryptographic EC's are given. All 3 properties are always met by all the EC's that I produce. A fourth property is suggested within Ref. 1 - that h(D) should not be too small. (See below for the meaning of this.) This can be accommodated by the Atkin Morain method.

  The statements above are axiomatic on this web site. They may not be axiomatic for other elliptic curves.

3 methods for deriving elliptic curves are in use :-

 (b) Set up an elliptic curve for a 'small' prime of perhaps 64 or 32 bits in size, and then 'extend' this small Field to something more relevant to cryptography. Use method (a) to determine the elliptic curve order over the small Field, then use a standard formula to calculate the order over the extended Field. Elliptic curve text books all give details of this calculation : e.g. see e.g. ref 1 Art VI.4 on this so called 'Subfield Curve' technique. The method is easy to implement, and the bulk of elliptic curve cryptographic packages in use today employ it. A problem with this technique is that it is almost impossible to control the sub-group structure - potentially dangerous in a cryptographic application and something the vendors of such systems tend to gloss over.

 (c) Use the Atkin Morain method. This method is quick and can be adjusted easily to provide elliptic curves with orders to meet all kinds of specifications. The 'gold standard' recommendation for cryptographic work is to use non isomorphic prime order elliptic curves; when this is done the potential problem of malignant subgroup structures vanishes - there are no subgroups! The method has to overcome 1 major problem and several non-trivial problems. The major problem is that access to Hilbert class polynomials is required. These are special polynomials over Z[x] (i.e. a polynomial over 'x' with integer coefficients - elements of 'Z') which are difficult to calculate. They also have very large, trending towards massive, coefficients.

  To get a feel for Hilbert class polynomial coefficient sizes consider the following.

The Hilbert class polynomial for Discriminant = -191, is a degree 13 polynomial as follows :-
x^13
+  7178 87448 95557 70070.x^12
-     1 44121 29900 79007 68222 58611.x^11
+   515 36266 75067 98038 54633 55177 18402 60203.x^10
- 10338 62393 96269 08702 07419 74285 55478 99174 53508.x^9
+     1 99518 44035 98858 37424 15322 73278 26660 33695 53705 46108.x^8
-     1 47686 38405 83089 41349 72427 62217 10241 41266 12994 26501 81658.x^7
+ 54180 82309 10284 08339 04560 00848 31435 50285 31599 10494 27281 73485.x^6
-   832 81822 05715 86800 39216 47440 00358 27031 95321 31590 07837 94717 35694.x^5
+   152 53788 70196 04812 84921 39149 31589 19700 25579 75594 66559 31129 63232 32498.x^4
-     4 93759 11707 91174 34329 17242 20761 53221 74325 42761 12377 41682 02648 88466 12521.x^3
+  1406 12343 26903 81462 11762 26216 07615 97792 71092 62399 58270 91347 30974 35548 98127.x^2
+    42 31275 30364 11362 23023 04503 05478 67287 08034 75782 95165 77060 05442 30443 43418 69586.x
+ 58256 74934 83045 23248 14496 98888 37463 34016 00939 69294 53274 21465 56156 00052 10348 02783

  You may think that the polynomial above is not too grim - they are only numbers after all. They are more or less impossible to do hand calculations with, but computers can handle them with ease. However the one above is from the 'tame' end of the spectrum. If I were to substitute a 'big boomer' above, you would have to press 'Page Down' 10, 20 or more times to reach the end; by which time most people would have backed out of this site! (For some bigger, but still only moderate sized Hilbert class polynomials, try big_hp.html. The constant coefficient for the last polynomial in the h(D)=72 set has 1930 decimal digits!)

[Definition of 'discriminant', used above :-
The term is used in many mathematical topics; but for this subject it was introduced by Lagrange when he started studying binary quadratic forms (QF's) - expressions of the type :-

  At first glance this expression might appear uninteresting; what sparks the theory into life is the study of the characteristics of the set of OP values - label it {OP}. (I may add an 'Introduction to QF's' page to this site in the future. For now I shall sidestep the topic.)
  It can also be shown to be possible to map an {a, b, c} triple to another triple {a', b', c'} that will generate an identical {OP} set. If a mapping can be found which preserves the value of (b²- 4.a.c) (which is the discriminant of the Quadratic Form) then {OP} is unchanged.
Modern treatments of QF's tend to use 2-by-2 matrices to represent them. When this is done, a suitable mapping uses elements from set SL₂[Z] (aka the classical modular group Gamma) which comprises 2-by-2 matrices with integer coefficients and with a determinant of +1. (Recall from matrix theory that the determinant of the product of 2 matrices is the product of the individual determinants - hence operations of this type leave the original determinant unchanged). The SL₂[Z] set is infinite in size.
The set of {a,b,c} triples derived from a 'base' triple, by mapping using elements of SL₂[Z]  is thus infinite in size and to simplify the situation it is helpful to select just one of them, called the 'reduced' form, to act as a representative for the whole set of triples.
[For the definition of a reduced form and a method to calculate them use e.g. ref. 3 algorithm 5.6.2 and adjacent text. This algorithm is due to Gauss himself.]
  If one now generates random triples {a, b, c}, while holding the discriminant fixed, and finds the 'reduced form' from them, it will be found that (in general) any discriminant has several reduced forms associated with it.
[Definition :- the number of reduced forms associated with any discriminant is a fixed and finite number and given the symbol h(D) :- thus for a discriminant of  D = -191,  h(-191) = 13. For D = -191 the set of reduced quadratic forms is :-
{{1, 1, 48}, {2, +-1, 24}, {3, +-1, 16}, {4, +-1, 12}, {6, +-1, 8}, {5, +-3, 10}, {6, +-5, 9}}]
  Each of the h(D) in number reduced forms contributes a linear factor towards the Hilbert class polynomial, and hence the final degree of the polynomial associated with D = -191 is 13 (as was seen above). The classical technique for calculating Hilbert class polynomials requires finding the set of reduced forms associated with a discriminant, then processing them to arrive at the polynomial.
  Clearly, the terms 'Hilbert class polynomial degree' and 'h(D)' are interchangeable.]

[The theory of QF's fundamentally splits depending on whether the discriminant is positive or negative, and only negative discriminants lead to Hilbert class polynomials. Furthermore, the theory leading from QF's to Hilbert class polynomials uses only a subset of the negative discriminants - those negative discriminants which are called 'fundamental'. On this web site, my use of the word 'discriminant' can be taken as shorthand for 'fundamental negative discriminant'. In many places where discriminants are discussed, I just give the absolute value of the discriminant - but a negative sign is always implied.]

  The algorithm to generate the Hilbert class polynomials is not overly complex (see ref.. 3 Chapter 7, algorithm 7.5.8), but unfortunately the calculations have to be done to a very high precision. Variables of 1000's or even 100's of thousands of bits in size have to be used. Real, Complex and Integer data types, able to perform arithmetic to this precision, have to be available, and this prospect has daunted most software writers who contemplate exploiting Atkin Morain. Perhaps 2-3 man years of effort by experienced software writers are needed to calculate a suitably large set of Hilbert class polynomials. Such a commitment would be excessive for most cryptographic software development teams. Fortunately, I have them for sale, so this expense can be side-stepped. Once these Hilbert class polynomials have been purchased, a further several man months of effort might be needed by a cryptographic software house to develop an Atkin Morain capability.

[Once lists of Hilbert class polynomials have been obtained, setting up an Atkin Morain capability requires no more than fitting together classes and subroutines that will almost certainly exist in any cryptographic software development office. A few 'odd ball' subroutines will probably be unavailable and need to be written; but ref. 3 provides all the guidance needed to write these. If you are seriously contemplating setting up an Atkin Morain capability, I would suggest that you obtain a copy of Ref. 3, and form your own estimate of the work ahead of you. It will probably be less than you think. In particular the very high precision data types mentioned above are not required.]

  The coefficients of Hilbert class polynomials grow very sharply with both increasing degree and increasing absolute discriminant value, and the coefficients displayed above are surpassed by more, and yet more, massive ones. There are an infinite number of Hilbert class polynomials, but handling them gets harder and harder as the degree and/or the absolute discriminant increases.
 

An outline of the Atkin Morain method for deriving elliptic curves

 (ii) A discriminant is selected. (Lists of discriminants grouped by  h(D) value are needed here.)
Two checks on the selected discriminant are then made :-
    (a) The discriminant has to be a quadratic residue for the Field prime.
    (b) A solution to the equation   4.p = u² + |Discriminant|.v²     has to be both possible and found.
[p is the Field prime from (i), here, with u and v any integers]
A majority of discriminants fail these tests, and when this occurs the next discriminant has to be tried.
[If the end of the discriminant lists is reached, or if some upper limit of h(D) is being used and exceeded, return to step (i) to start again with a new prime. It can be proven that all primes can generate many prime order elliptic curves; but this jump may be needed since the discriminant lists are necessarily a finite resource.]
[Checks (a) and (b) form the origins of the 1/(2.degree) success ratio discussed below.]

  (iii) The orders of two elliptic curves will result after stage (iv) is completed :- (p+1+u) and (p+1-u). These can be tested for primality (or perhaps some other specification for the order). [the discriminants -3, -4 are special cases which I will side step, since they have their own formulae]. If either of these orders is satisfactory, move to step (iv), if not return to step (ii).
Note that, with the Atkin Morain method, the order of the elliptic curve is obtained before the elliptic curve coefficients themselves!

  Note that the Hilbert class polynomials play no part in proceedings up to this point.

  (iv) Find the Hilbert class polynomial corresponding to the satisfactory discriminant found in (ii) above. If it is available from a look up table, all well and good; if not calculate it from scratch. Now find the elliptic curve coefficients from this polynomial. This is done in the following steps :-
    (a) Transform the Hilbert class polynomial (el Z[x]) to a polynomial from Fp[x] by performing a 'mod p' operation on each integer coefficient.
    (b) Find a root of the Fp[x] from (a).
[This root finding is the difficult part of Atkin Morain, since no deterministic algorithm is known. The Fp[x] polynomial has to be split (by taking the GCD of the exponential of a random first degree polynomial) several times until a degree 1 or 2 polynomial is left, whereupon a root is obvious. This random splitting has a 50-50 chance of failing and if this occurs has to be retried, possibly several times. This step has an execution time comparable to stages (ii) and (iii), probably longer and, if a high degree Hilbert class polynomial is in play, much longer. On the plus side, once stage (iv) is started, a solution will always be found, hence stage (iv) takes place only once for each elliptic curve derivation.]
  If required, this root can be divided out of Fp[x] and another factor obtained from the quotient Fp[x] polynomial to yield another elliptic curve, etc. etc. until the degree of the quotient Fp[x] is reduced to zero.
    (c) Derive the elliptic curve coefficients from the root(s) from (b) - this only involves a few Field multiplication's.

 (v) (optional) Anyone who wants to sleep nights will want to verify that the order from stage (iii) checks with the order derived from the elliptic curve coefficients found in stage (iv). This, unlike calculating the order in the first place, is a simple task covered in any elliptic curve textbook. This step is always done in my software as an error check.

  Note that the order of the final elliptic curve is found fairly quickly in stages (i) - (iii). The slower part of Atkin Morain, stage (iv), (finding the roots) takes place just once. Even though stage (iv) is slower than the others, it is only oppressive if the degree of the Hilbert class polynomial is greater than about 32-40.
  I can supply a DOS based demonstration of the algorithm above to anyone who requests it, for no charge.

Notes on Atkin Morain method stages (ii) and (iii)
  A fuller discussion of stage (i) takes place below and stages (iv) and (v) are just number crunching; but stages (ii) and (iii) require the operator to have a good grasp of the contents of this section to efficiently achieve any specific objective.

  The Hilbert class polynomials of any given degree are finite in number - there are 9 of degree 1, 18 of degree 2, 16 of degree 3, 54 of degree 4, 25 of degree 5, 51 of degree 6 ... . As the Hilbert class polynomial degree increases, so the number of Hilbert class polynomials increases as a 'noisy' sequence. Thus there are 114 of degree 53, 427 of degree 54, 163 of degree 55, 1205 of degree 56 ... . Sadly, the chances of a successful Atkin Morain solution from any Hilbert class polynomial falls off  in the ratio of 1/(2.h(D)). This strong reduction in the chance of success with increasing Hilbert class polynomial degree actually means that, when an upper limit in polynomial degree is being used, a 'no Atkin Morain solution' outcome for any prime is a significant possibility.

[Restrictions on discriminant when prime order elliptic curves are sought :-

  Stage (iv) of the Atkin Morain method slows down sharply when a high degree Hilbert class polynomial is being exploited. Hence, for Field primes that are common, it generally makes sense to impose an upper limit on the polynomial degree to be searched; perhaps 8 - 32 or so. Then if some common type of Field prime yields 'no solution', simply find another prime and try that.
  Other primes such as Mersenne primes and what I call below FIPS type primes are both rare and  particularly useful as finite Field primes for elliptic curve cryptographic packages. For such primes, the imposed upper limit on Hilbert class polynomial degree has to be increased, possibly considerably, since 'no solution' is an unacceptable outcome. In this case, stage (iv) may take a good deal of extra time to complete. (See web page topfips.html for discriminants that yield prime order elliptic curves for Mersenne primes and some particularly useful FIPS type primes up to a maximum polynomial degree of 256.)

Atkin Morain method success probabilities when prime order elliptic curves are sought

  These nearly constant 'bunch numbers' exert a profound influence on the tactics to be adopted by any team intent on using the Atkin Morain method.

Consider further the tactics, from above, when assessing restrictions on maximum polynomial degree for common and for rare Field primes :-

Notes on using the Atkin Morain method with common Field primes

[A cautionary note :- In ref. 1 section VIII.2, elliptic curves derived from 'low' degree polynomials are called "... in some sense 'special'." This may make them susceptible to attack from "... a future, as yet unknown, discrete logarithm algorithm". This comment appears to be based on nothing stronger than 'gut feeling'! However, the opinion of these respected authors is not without weight and elliptic curves derived from high Hilbert class polynomial degrees might be more secure than those from low ones. If this statement is adopted, search among the degree 9-16 polynomials, perhaps higher.]
[If a search of the Internet is made for guidance on the point above, you will find comments such as "... h(D)>200 is required for top class work..."! This may be needed if you are intent on invading Moscow ...]
[If the cautionary notes above are rejected, then use of ref. 3, algorithm 7.5.10 may be attractive. This algorithm just exploits the degree 1 and 2 polynomials without needing their explicit presence. With this technique several dozen random primes would have to be tried before a prime order elliptic curve was obtained. This technique would, however, be very quick. Algorithm 7.5.10 also offers the potential for 'pushing back the boundaries' of the 'SubField Curve' technique mentioned above.]

Notes on using the Atkin Morain method with rare Field primes

[More Mersenne prime solution points can be found in topfips.html.]
[A knowledge of {discriminant, h(D)} Atkin Morain solution point pairs is very useful for project planning. They can be derived quickly by using stages (ii) and (iii) only. I can derive lists of pairs like this for you, for any specific prime.]
  This 'rare prime' tactic is also needed if :-
(a) A project needs a large number of elliptic curves over a fixed Field prime. (the operational advantages of doing this are discussed below)
(b) A network has had a Field prime in use for some time (which it would prefer to leave unchanged to minimize the cost of software changes) simultaneously with a need to improve security by introducing new non isomorphic elliptic curves.

[In this report, it is assumed that prime order elliptic curves are the objective. The reader should be aware that elliptic curve orders of the form

Notes on the Selection of a Field prime in stage (i)

  The speed of elliptic curve processing is dominated by the time to perform the finite Field multiplication operation. This operation requires a large (multi-word) integer multiplication followed by a 'mod' operation by the Field prime. (Recall that a 'mod' operation is just the remainder from a division.) The integer multiply might take 40% and the 'mod' 60% of total Field multiplication time. Text books on numerical methods contain many cunning algorithms for reducing the large integer multiply time (most of which do not deliver in the event!); but the 'mod' operation is much harder to speed up merely by numerical tricks. However, speed gains can be found by using primes of special formats.

  In the Federal Information Processing Standards Publication 186-2 a set of elliptic curves approved for the transmission of data in the USA is given. In each case, the underlying Field prime is a 'sparse' prime i.e. a prime with few set bits. Consider P-192 from FIPS 186-2; an elliptic curve over this prime is of a strength suitable for use with block algorithm SKIPJACK. This prime can be written in exponential format as   P-192 = 2¹⁹²  -  2⁶⁴  -  1 i.e. only 3 bits need be specified. Such a prime is capable of reducing the mod time to a few percent of that required for a random 192 bit prime. Sparse primes, similar to P-192, are called FIPS type primes on this web site.
[To understand why these primes deliver a fast 'mod', I recommend you evaluate a mod in binary by long division as a pencil and paper exercise. It will rapidly become apparent that the operation reduces to a sequence of multi-word shifts followed by multi-word adds/subtracts (note a division is not required) and the reason for the fast 'mod' will become obvious.]

[Note that the term 'sparse' is stretching the word a little. In hex P-192 is 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF FFFFFFFF - every bit bar 1 is set! In this report 'sparse' indicates that only a 'few' bits in the number's exponential format are needed for a full specification.]

Primes of the FIPS type are not nearly so rare as Mersenne primes, but neither are they common. There may be a few tens for any bit size; this number rising as the exponent of the most-significant-bit (msbit) increases and as the number of bits in the exponential expression increases.

Definition of the phrase 'FIPS type primes' used in this report :-

Everywhere on this web site I use a form of code to specify a FIPS type prime. This code just gives the bit exponents and the bit 'sign' :-
Hence   P-192 = 2¹⁹²  -  2⁶⁴  -  1  would be coded as  {192, -64, -0}.

  When FIPS type primes are used for the Field prime for elliptic curves, the total Field multiplication time (and hence elliptic curve processing time) can be halved. Other Field prime types are also capable of providing significant speed gains but (excluding the Mersenne primes) FIPS type primes give the fastest 'mod'.

[If you are new to the ideas for 'mod'ing introduced above, a note of caution is needed here to curb any excess of enthusiasm. To perform calculations with FIPS type primes I required a high level C code 'mod' subroutine. I wrote this subroutine with the mind-set that 'the subroutine would be quick' irrespective of any efforts on my part. In the event, when timed against a regular 'mod' subroutine, generally only a small speed gain was found, and on occasion a speed decrease was found. The problem is that the tedious, and apparently trivial, problem of handling carries and borrows can easily grow to overwhelm the 'obvious' speed gain. By introducing 'cute' tricks like carry and borrow prediction the performance of this subroutine was improved somewhat; but it is still fairly poor compared to the potential gains.]
  To get near to the full speed gain offered by FIPS type primes the procedure for the FIPS 186-2 primes given in ref. 4 must be followed. In brief, given some specific FIPS type prime, it is necessary to derive a formula summarizing the mod operation in terms of 32 bit word shifts and adds/subtracts; then implement this formula in assembler. The use of assembler is essential to prevent speed loss from handling carries/borrows. Such a subroutine is, of course, locked to a specific FIPS type prime; and if the prime changes the whole procedure has to be repeated! Today, few software writers can write in assembler, so this is expensive. However, I can do all of this work for you. (see the 'sales' section of this site)

  The expense of an assembler written 'mod' for FIPS type primes can be mitigated by the following characteristics of the elliptic curves generated by the Atkin Morain method :-
  (a) After some FIPS type (or any type) prime has been decided upon, and then passed to the Atkin Morain subroutine to derive an elliptic curve over it, the lowest degree Hilbert class polynomial which yields a prime order elliptic curve might be of any degree, say 16 for the sake of discussion. For a degree 16 Hilbert class polynomial, 16 elliptic curves can be derived. Furthermore these elliptic curves, although all of identical order (i.e. have an identical number of points on them) are non isomorphic. This means that they are cryptographically independent entities. This means that should it be necessary to change to a new elliptic curve system from time to time (a common and sensible defensive security tactic) one can just move to another of the elliptic curves, without having to change the assembler based 'mod' subroutine. This is a trivial software upgrade, probably requiring the alteration of only a few lines of code. In other words, the expense of writing an assembler based 'mod' can be amortized over a greater time span than might appear the case, while keeping security levels high.
  (b) Many large networks have a need to partition their encrypted (i.e. sensitive) 'data' so that individuals can only access a subset of it. In the same vein as (a), each of these partitions can be allocated one of the non isomorphic elliptic curves, enabling the whole network to use the same 'mod' subroutine.

  If the features above were attractive for some network, hundreds, or potentially even thousands, of non isomorphic prime order elliptic curves over the same Field prime could be found by the Atkin Morain method. If non prime order elliptic curves were acceptable, this number might rise to several 10's of thousands.

  Some FIPS type primes offer greater speed gains than others. The following points affect their performance. Note that if the 'mod' routine is written in assembler then the significance of some of these points is reduced.
  If one spends a little time with pencil-and-paper doing a mod by division in binary, the following points will become apparent :-

  (a) The best possible FIPS type prime (from the 'mod' viewpoint) is one with just 2 set bits. P-521 in FIPS 186-2 is a Mersenne prime of this form : P-521 = 2⁵²¹ - 1. Mersenne primes that attract current cryptographic interest have exponents of {... 127, 521, 607, 1279, 2203 ...}. 'Mod'ing with Mersenne primes entails a single shift followed by a single (multi-word) add. (a trivial adjustment for a 'carry' may also be needed). I shall call this a single pass mod. These primes give the fastest possible 'mod' and set the benchmark speed for all others. Note that there are very large gaps between Mersenne primes which makes fine adjustment of cryptographic security strength impossible. Furthermore, having to move to a much larger Mersenne prime than security demands will cause the run-time of the large integer multiply to grow sharply so as to overwhelm the speed gains from the fast 'mod' rendering the whole tactic pointless.

  (b) Retreating from the rare 'ideal' Mersenne primes, the next best FIPS type primes are those that give a 2 pass 'mod' i.e. 2 stages of multi-word (shifts and add/subtracts) are required per 'mod'. For this to be possible the lesser exponent bits have to be clustered in the right half of the prime - in other terms, the exponent of the penultimate most significant bit should be less than or equal to half the exponent of the msbit. These primes give a 'mod' time not much greater than that of the Mersenne primes with the added benefit that there are large numbers of all sizes of them. This enables fine tuning of security level and also enables users to adopt the defensive tactic of moving from prime to prime.
[It is only necessary to contemplate the systemic damage that would result worldwide from a successful attack on the FIPS 186-2 elliptic curve based on P-521, to realize that FIPS 186-2 is flawed - it is a classic case of all one's eggs in one basket. The use of 2 pass FIPS type primes would result in a far more reliable security environment worldwide, all for the price of a minor loss of speed.]
  In the 'sales' section of this site I offer a CD containing lists of non isomorphic prime order elliptic curves over FIPS type primes with bit sizes from 256 - 767. I have forced the bulk of the primes in these lists to be 2 pass FIPS types. These elliptic curves are probably the cryptographically strongest elliptic curves currently available for sale to the public. They are so strong that I have felt obliged to develop a block cipher I call RijnType  (an extension of block cipher Rijndael) to go with them, since block ciphers of the strength necessary to 'match' them are hard to find.
[Not all the FIPS type primes listed on topfips.html are represented on the CD at this time. I am working to remedy this, and any purchasers of the EC curves CD will automatically receive the upgrade without additional cost.]
[It is my view that the range of prime sizes represented on the CD covers the needs of commercial networks for at least the next 10 years.]

  (c) The following are lesser considerations :-
   (i) The fewer the number of set bits (written in the exponential format) in a FIPS type prime the faster will be the 'mod'. Unfortunately, the fewer the number of set bits, the fewer the number of such primes available. Hence greater security reliability requires more set bits, not fewer.
   (ii) The speed of a large integer multiplication subroutine rises as the square of the number of 32 bit computer words (#word32's) needed to hold the integer (slightly less for sophisticated algorithms). Also, cryptographic security strength depends on the bit size of the Field prime. Putting these 2 statements together we come to the conclusion that the best speed strength balance is achieved when #word32 is full, or very nearly full, of meaningful bits. This will be the case when the FIPS type prime is of either of these forms :-
    [A]  p = 2^{(k * 32)}  -  2^(?) ...   [the 'minus' sign reduces #word32 to hold 'p' from k to k-1]
    [B]  p = 2^{((k * 32) + 31)}  +/- ...  [the '31' figure might be 30 or 29 ...]
The FIPS type primes on the EC curves CD have been forcibly biased towards these 2 formats, but some primes with msbits in the 'middle' of the most significant computer word are also given.
[Note that P-521 from above fails recommendation (ii)! From this consideration it is not ideal. It needs 17 word32 to hold it with a multiplication time proportional to 17² = 289, whereas a prime of the form [A] or [B] would have a multiplication time proportional to 16² = 256, a time saving of 12% without any loss of security.]
 

A Typical set of non isomorphic prime order Elliptic Curves from the CD available for sale

        -------- ######## --------
Field Prime [#1] : 2^261 - 2^160 - 2^128 + 1
  = 1F FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 00000000 00000001
[Solutions for this prime from Discriminant=-25435 with h(D)=18.]
Prime order for all [#1-?] curves
  = 1F FFFFFFFF FFFFFFFF FFFFFFFF 0000000A 180217E2 70DBC07D 076B7DB3 AF9A7939

<<< 2 isomorphs with a=-3 available from this solution. >>>
Curve [#1-1]
  a = 19 2D3C0E3C 8B599CB2 18ED9F09 D560F831 0C552976 54EEC751 AB9576DF 022843BE
  b =  E B58B4418 C2E21231 FBF02DBB 9CFC9360 C137A6B5 8B1697B2 109D3F5B B17A95C3
        - - - - - -
A random point on the curve above is :-
  x = 19 419AD397 ACC6E3F0 15541C44 213ABC05 441ED165 4C7E5E21 1A8273CF AD16CCA2
  y = 18 AF09E426 64003626 366A7789 53E06105 EFCDDEA3 6D863506 B5AD25AE 0E840C1D
       = = = = = =
The curve isomorphic to curve [#1-1] (above) with a=-3 is :-
  a = -3
  b = 18 9E23067B F6AC10CC D4B74131 18F8CE81 8BC7DDC3 F47B6BE2 962AC02A 69FB6E76
       ++++++++++++++++++
Curve [#1-2]
  a =  6 C4F7B664 A5F25F60 6BDEE657 E2E64D29 B871C64A 9A0BA091 E51A8D74 A4DBA8C7
  b =  6 275ADBBC E6B3C06A 62C0BBC5 13667739 2FB42678 EEA2EA49 6743A1B2 3CC2E4D1
        - - - - - -
A random point on the curve above is :-
  x =  2 F3ADA3C9 BB32AA89 BA9D1B4F BD7EF2A3 CBBEFD84 2AF3D0BD 112C7C85 675229EB
  y = 10 F5ECABEE 397A985C 83D12CFD C7513039 67E1E950 9FEE3451 7004F8F7 A92B1CED
        = = = = = =
The curve isomorphic to curve [#1-2] (above) with a=-3 is :-
  a = -3
  b = 17 54F00F6B B61594AF 53006EC9 940E1293 3E61E6E7 74D3B0BF E595497D C05B2CA7

      <<< The [#1-?] curves following have no a=-3 isomorph. >>>
Curve [#1-3]
  a = 1D 22A10965 3082126A B21E7C7A 73928852 07259DF0 F392AC37 AB845498 5B3E0C75
  b =  C 9394A467 34FE9E63 89410258 0848FA72 FB3C415F 5D9E37DA E2FD1CEF C32BF7B3
        - - - - - -
A random point on the curve above is :-
  x =   92D0C925 F849423A 718B6F69 3FBB76E0 2765025F C734C349 AB054196 B7309FFD
  y = C 86DED43B 39C1C9B9 ACF9EBD7 0C26420E 28B51218 88213F13 3A99D516 890D9DBB
        ++++++++++++++++++
Curve [#1-4]
  a =  1 F495E837 A6DFDA12 2C0A2D49 35E3E7A1 55D8D218 48E3F7C5 9BC8724A C1EBB235
  b = 14 079C0FDA E6156E9E 8D4E8C79 3168103E 716F73EF CF68057C 42CFB3CE 2962DE88
        - - - - - -
A random point on the curve above is :-
  x = 16 3BF1B16F 4CFDA013 EF941D48 CAA974D8 10D7A9DE 42F774EC 50141B7F 7C24DB58
  y =  A 24A58230 796073F8 ED7F1443 948C2664 4E1CAFCC 3079C091 3DC5C912 3EC8BCC9
        #++++++++#+++++++#

  The following comments can be made on the sample above :-
  (A) The Field prime here is cryptographically of moderate size. The results on the CD are biased to Field primes over 500 bits in size, as currently required by 'strong' commercial grade security. Nevertheless, not all security tasks need intense security, so a few lower security solutions are included on the CD.

  (B) Inspection of the Field prime indicates that a 3 pass 'mod' is required with this prime, and the most significant word32 is neither fully, nor nearly fully packed. This makes the elliptic curves over this prime less attractive than most results on the CD. The bulk of the results on the CD have been biased towards being capable of a 2 pass 'mod', and towards having a msbit exponent close to a multiple of 32 so that they can be fully packed.

  (C) Moving down a little, we see that the Atkin Morain solution is obtained from a discriminant with h(D) = 18. This means that 18 prime order elliptic curves can potentially be derived over this prime. On the CD only a maximum of 4 elliptic curves are ever supplied over any prime.

  (D) My software proceeds by searching for a solution among the h(D) = 1 discriminants, then the 2's, ... and so on. Hence the discriminant with the lowest h(D) that yields prime order elliptic curves is used to generate the results on the CD. Only this first solution is used - the software then moves to the next entry in a list of FIPS type primes. It would be possible to move on and use discriminants with higher and higher h(D) values to derive more and more prime order elliptic curves (hundreds, or even thousands of them) all over the same Field prime. This may be an important attribute of the Atkin Morain method for some networks.
[For the Field prime in the sample CD entry, and for h(D)'s <= 256, all the prime order elliptic curve Atkin Morain solutions occur with {discriminant, h(D)} pairs of    {-25435, 18}, {-223339, 85}, {-1903555, 224} and {-1871731, 246}.
Evaluating all of these solutions would yield a total of 573 prime order elliptic curves! However, the last 3 entries are beyond my current polynomial look up table limit of 72; and even after the Hilbert class polynomials had been evaluated, factoring a degree 246 Fp[x] would probably take many days on a PC!]

  (E) Two curves with a=-3 isomorphs were found for this prime.
[There is a small speed gain to be had by using an elliptic curve with a=-3 as any textbook on elliptic curve arithmetic (e.g. ref. 2) will demonstrate, hence elliptic curves with a=-3 are slightly more valuable than those elliptic curves that have no such isomorph.]
  My software operates by extracting simple root after simple root, searching for all the a=-3 solutions among all h(D) solutions and only stops when either 4 have been found (the maximum number of elliptic curves listed on the CD for any Field prime) or no more roots are available. In other words, for the sample, all 18 simple roots would have been evaluated, but only 2 of these 18 were found to possess an a=-3 isomorph.

A note on isomorphic elliptic curves. (see ref. 2 for full details)

    Two elliptic curves over the same Field prime are isomorphic if
        (i) The number of points on the elliptic curves is identical.
        (ii) If the 2 elliptic curves are :-

  Isomorphic elliptic curves are cryptographically very dangerous for the following reason :- Assume some attacker has broken into some elliptic curve. There is no publicly known method for doing this, but it is probably wise to assume the possibility when an elliptic curve has been in use for some time. If a network changed it's elliptic curve to an isomorphic elliptic curve, then all the attacker has to do is map the new data values back to the old elliptic curve; use his old elliptic curve breaking techniques to 'solve' for the mapped values; then map the solution found from the 'old' elliptic curve back to the new elliptic curve. This is a trivial task. However if the security update is done with a non isomorphic elliptic curve, the attacker must start afresh to break the new elliptic curve, since no mapping expression is believed to exist. This considerably increases the attacker's workload and costs.

  As a matter of interest, my software 'flags' whenever elliptic curves derived by the Atkin Morain method are found to be isomorphic. In all the many thousands of elliptic curves that I have derived, not a single isomorph has been flagged. There is surely a theorem somewhere to the effect that all Atkin Morain solutions are non isomorphic, but I have not seen it. All my experimental evidence indicates that the Atkin Morain method only generates non isomorphic elliptic curves.

[go to site Home page]