3.1 Elliptic curves over F2m - format and examples 3.1.1 The finite field F2m 3.1.2 Elliptic curves over F2m 3.1.3 Format for challenge parameters (the F2m case) 3.2.4 Random elliptic curves and points (the F2m case) 3.1.1 The finite field F2m There are many ways to represent the elements of a finite field with 2m elements. The particular method used in this challenge is called a polynomial basis representation. Let f(x) = xm + fm-1xm-1 + fm-2xm-2 + ... + f2x2 + f1x + f0 (where fi {0,1} for i = 0, 1, ..., m-1) be an irreducible polynomial of degree m over F2 . That is, f(x) cannot be factored as a product of two polynomials over F2, each of degree less than m. The polynomial f(x) is called the reduction polynomial. The finite field F2m is comprised of all polynomials over F2 of degree less than m: F2m = {am-1xm-1 + am-2xm-2 + . . . + a1x + a0 :ai {0,1}}. The field element am-1xm-1 + am-2xm-2 + . . . + a1x + a0 is usually denoted by the binary string (am-1 am-2 ... a1 a0) of length m, so that F2m = {(am-1 am-2 ... a1 a0) : ai {0,1}}. Thus the elements of F2m can be represented by the set of all binary strings of length m. The multiplicative identity element (1) is represented by the bit string (00 . . . 01), while the zero element is represented by the bit string of all 0's. The following arithmetic operations are defined on the elements of F2m: Addition: If a = (am-1 am-2 ... a1 a0) and b = (bm-1 bm-2 ... b1 b0) are elements of F2m, then a + b = c = (cm-1 cm-2 ... c1 c0) where ci = (ai + bi) mod 2. That is, field addition is performed bitwise. Multiplication: If a = (am-1 am-2 ... a1 a0) and b = (bm-1 bm-2 ... b1 b0) are elements of F2m, then a . b = r = (rm-1 rm-2 ... r1 r0) where the polynomial rm-1xm-1 + rm-2xm-2 + ... + r1x + r0 is the remainder when the polynomial (am-1xm-1 + am-2xm-2 + . . . + a1x + a0 ) . (bm-1xm-1 + bm-2xm-2 + . . . + b1x + b0 ) is divided by f(x) over F2. Inversion: If a is a non-zero element in F2m, the inverse of a, denoted a-1, is the unique element c F2m for which a . c = 1. Example (The finite field F24) Let f(x) = x4 + x + 1 be the reduction polynomial. Then the elements of F24 are: (0000) (1000) (0100) (1100) (0010) (1010) (0110) (1110) (0001) (1001) (0101) (1101) (0011) (1011) (0111) (1111) Examples of the arithmetic operations in F24 are: (1101) + (1001) = (0100). (1101) . (1001) = (1111). (1101)-1 = (0100) 3.1.2 Elliptic curves over F2m A (non-supersingular) elliptic curve E(F2m) over F2m defined by the parameters a, b F2m , b 0, is the set of all solutions (x, y), x, y F2m , to the equation y2 + xy = x3 + ax2 + b, together with an extra point O, the point at infinity. The set of points E(F2m) forms a group with the following addition rules: 1. O + O = O . 2. (x, y) + O = O + (x, y) = (x, y) for all (x, y) E(F2m). 3. (x, y) + (x, x + y) = O for all (x, y) E(F2m) (i.e., the negative of the point (x, y) is -(x, y) = (x, x + y)). 4. (Rule for adding two distinct points that are not inverses of each other) Let P = (x1, y1) E(F2m) and Q = (x2, y2) E(F2m) be two points such that x1 x2. Then P + Q = (x3, y3), where x3 = 2 + + x1 + x2 + a, y3 = (x1 + x3) + x3 + y1, and = ( y2 + y1) / (x2 + x1). 5. (Rule for doubling a point) Let P = (x1, y1) E(F2m) be a point with x1 0. (If x1 = 0, then P = -P and so 2P = O.) Then 2P = (x3, y3), where x3 = 2 + + a, y3 = x12 + ( + 1)x3 , and = x1 + ( y1 / x1) . Example (An elliptic curve over F24) Consider the finite field F24 defined by the reduction polynomial f(x) = x4 + x + 1. y2 + xy = x3 + (0011)x2 + (0001) is an equation for an elliptic curve E over F24. Here a = (0011) and b = (0001). The solutions over F24 to this equation are: (0000,0001) (0001,1100) (0001,1101) (1000,0101) (1000,1101) (0110,1000) (0110,1110) (1100,0101) (1100,1001) (1010,0111) (1010,1101) (0111,0010) (0111,0101) (1111,0000) (1111,1111) E(F24) has 16 points, including the point at infinity O . The following are examples of the addition law: (1100, 0101) + (1000, 1101) = (0001, 1101). 2(1100, 0101) = (0111, 0101). 3.1.3 Format for challenge parameters (the F2m case) This subsection describes the conventions used for representing the challenge parameters for elliptic curves over F2m. Two types of elliptic curves over F2m are included in the challenge: random curves and Koblitz curves. Koblitz curves over F2m are special types of elliptic curves E defined over F2 which have exactly 2 points in E(F2). They were first proposed for use in elliptic curve cryptography by Koblitz [Koblitz2]; see also [Solinas]. Apart from the -fold speed-up that can be obtained with the improved parallelized rho method (see Section 2.2), there have not been any mathematical discoveries to date to suggest that the ECDLP for randomly generated elliptic curves is any easier or harder than the ECDLP for Koblitz curves. Challenge parameters (random curves) m - the order of the finite field is 2m . f(x) - the reduction polynomial which defines the polynomial basis representation of F2m. seedE - the seed that was used to generate the parameters a and b (see Algorithm 1 in Section 3.1.4). a, b - the field elements which define the elliptic curve E : y2 + xy = x3 + ax2 + b. seedP - the seed that was used to generate the point P (see Algorithm 3 in Section 3.1.4). xP , yP - the x- and y-coordinates of the base point P. n - the order of the point P; n is a prime number. h - the co-factor h (the number of points in E(F2m) divided by n). seedQ - the seed that was used to generate the point Q (see Algorithm 3 in Section 3.1.4). xQ , yQ - the x- and y-coordinates of the public key point Q. Challenge parameters (Koblitz curves) m - the order of the finite field is 2m . f(x) - the reduction polynomial which defines the polynomial basis representation of F2m. a, b - the field elements which define the elliptic curve E : y2 + xy = x3 + ax2 + b. seedP - the seed that was used to generate the point P (see Algorithm 3 in Section 3.1.4). xP , yP - the x- and y-coordinates of the base point P. n - the order of the point P; n is a prime number. h - the co-factor h (the number of points in E(F2m) divided by n). seedQ - the seed that was used to generate the point Q (see Algorithm 3 in Section 3.1.4). xQ , yQ - the x- and y-coordinates of the public key point Q. Data formats Integers are represented in hexadecimal, the rightmost bit being the least significant bit. Example: The decimal integer 123456789 is represented in hexadecimal as 075BCD15. Field elements (of F2m) are represented in hexadecimal, padded with 0's on the left. Example: Suppose m = 23. The field element a= x22 + x21 + x19 + x17 + x5 +1 is represented in binary as (11010100000000000100001), or in hexadecimal as 006A0021. Seeds for generating random elliptic curves and random elliptic curve points (see Section 3.1.4) are 160-bit strings and are represented in hexadecimal. 3.1.4 Random elliptic curves and points (the F2m case) This subsection describes the method that is used for verifiably selecting elliptic curves and points at random. The defining parameters of the elliptic curve or point are defined to be outputs of the one-way hash function SHA-1 (as specified in FIPS 180-1 [SHA-1]). The input seed to SHA-1 then serves as proof (under the assumption that SHA-1 cannot be inverted) that the elliptic curve or point were indeed generated at random. The following notation is used: s = (m - 1) / 160 and h = m - 160 . s. Algorithm 1: Generating a random elliptic curve over F2m Input: A field size q = 2m . Output: A 160-bit bit string seedE and field elements a, b F2m which define an elliptic curve E over F2m. 1. Choose an arbitrary bit string seedE of length 160 bits. 2. Compute H = SHA-1(seedE), and let b0 denote the bit string of length h bits obtained by taking the h rightmost bits of H. 3. For i from 1 to s do: Compute bi = SHA-1((seedE + i) mod 2160 ). 4. Let b be the field element obtained by the concatenation of b0 , b1 , ... , bs as follows: b = b0 b1 . . . bs. 5. If b = 0 then go to step 1. 6. Let a be an arbitrary element of F2m. (Note: For a fixed b there are only two essentially different choices for a -- other values of a give rise to isomorphic elliptic curves. Hence the choice of a is essentially without loss of generality.) 7. The elliptic curve chosen over F2m is E: y2 + xy = x3 + ax2 + b. 8. Output(seedE, a, b). Algorithm 2: Verifying that an elliptic curve was randomly generated Input: A field size q = 2m, a bit string seedE of length 160 bits, and field elements a, b F2m which define an elliptic curve E: y2 + xy = x3 + ax2 + b over F2m. Output: Acceptance or rejection that E was randomly generated using Algorithm 1. 1. Compute H = SHA-1(seedE), and let b0 denote the bit string of length h bits obtained by taking the h rightmost bits of H. 2. For i from 1 to s do: Compute bi = SHA-1((seedE + i) mod 2160). 3. Let b' be the field element obtained by the concatenation of b0 , b1 , ... , bs as follows: b' = b0 b1 ... bs. 4. If b = b' then accept; otherwise reject. Algorithm 3: Generating a random elliptic curve point Input: Field elements a, b F2m which define an elliptic curve E: y2 + xy = x3 + ax2 + b over F2m. The order of E(F2m) is n . h, where n is a prime. Output: A bit string seedP, a field element yU, and a point P E(F2m) of order n. 1. Choose an arbitrary bit string seedP of length 160 bits. 2. Compute H = SHA-1(seedP), and let x0 denote the bit string of length h bits obtained by taking the h rightmost bits of H. 3. For i from 1 to s do: Compute xi = SHA-1((seedP + i) mod 2160 ). 4. Let xU be the field element obtained by the concatenation of x0 , x1 , ... , xs as follows: xU = x0 x1 ... xs. 5. If the equation y2 + xU y = xU3 + axU2 + b does not have a solution y F2m, then go to step 1. 6. Select an arbitrary solution yU F2m to the equation y2 + xU y = xU3 + axU2 + b. (Note: This equation will have either 1 or 2 distinct solutions. Hence the choice of yU is essentially without loss of generality.) 7. Let U be the point (xU , yU). 8. Compute P = hU. 9. If P = O, then go to step 1. 10. Output(seedP, yU , P). Algorithm 4: Verifying that an elliptic curve point was randomly generated Input: A field size q = 2m, field elements a, b F2m which define an elliptic curve E: y2 + xy = x3 + ax2 + b over F2m, a bit string seedP of length 160 bits, a field element yU F2m, and an elliptic curve point P = (xP , yP). The order of E(F2m) is n . h, where n is a prime. Output: Acceptance or rejection that P was randomly generated using Algorithm 3. 1. Compute H = SHA-1(seedP), and let x0 denote the bit string of length h bits obtained by taking the h rightmost bits of H. 2. For i from 1 to s do: Compute xi = SHA-1((seedP + i) mod 2160). 3. Let xU be the field element obtained by the concatenation of x0 , x1 , ... , xs as follows: xU = x0 x1 ... xs. 4. Let U be the point (xU , yU). 5. Verify that U satisfies the equation y2 + xy = x3 + ax2 + b . 6. Compute P' = hU. 7. If P P' then reject. 8. Accept.

Copyright © Certicom Corp., 1997-2000. All rights reserved. Information subject to change. http://www.certicom.com