3.2 Elliptic curves over Fp - format and examples 3.2.1 The finite field Fp 3.2.2 Elliptic curves over Fp 3.2.3 Format for challenge parameters (the Fp case) 3.2.4 Random elliptic curves and points (the Fp case) 3.2.1 The finite field Fp Let p be a prime number. The finite field Fp is comprised of the set of integers {0, 1, 2, . . . , p - 1} with the following arithmetic operations: Addition: If a, b Fp, then a + b = r, where r is the remainder when a + b is divided by p and 0 r p - 1. This is known as addition modulo p. Multiplication: If a, b Fp, then a . b = s, where s is the remainder when a . b is divided by p and 0 s p - 1. This is known as multiplication modulo p. Inversion: If a is a non-zero element in Fp, the inverse of a modulo p, denoted a-1 , is the unique integer c Fp for which a . c = 1. Example (The finite field F23) The elements of F23 are {0, 1, 2, ... ,22 }. Examples of the arithmetic operations in F23 are: 12 + 20 = 9. 8 . 9 = 3. 8-1 = 3. 3.2.2 Elliptic curves over Fp Let p > 3 be a prime number. Let a, b Fp be such that 4a3 + 27b2 0 in Fp. An elliptic curve E(Fp) over Fp defined by the parameters a and b is the set of all solutions (x, y), x, y Fp, to the equation y2 = x3 + ax + b, together with an extra point O, the point at infinity. The set of points E(Fp) 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(Fp). 3. (x, y) + (x, -y) = O for all (x, y) E(Fp) (i.e., the negative of the point (x, y) is -(x, y) = (x, -y)). 4. (Rule for adding two distinct points that are not inverses of each other) Let P = (x1, y1) E(Fp) and Q = (x2, y2) E(Fp) be two points such that x1 x2. Then P + Q = (x3, y3), where x3 = 2 - x1 - x2, y3 = (x1 - x3) - y1 , and = (y2 - y1) / (x2 - x1). 5. (Rule for doubling a point) Let P = (x1, y1) E(Fp) be a point with y1 0. ( If y1 = 0, then P = -P and so 2P = O.) Then 2P = (x3, y3), where x3 = 2 - 2x1, y3 = (x1 - x3) - y1, and = (3x12 + a) / 2 y1. Example (An elliptic curve over F23) y2 = x3 + x + 1 is an equation for an elliptic curve E over F23. Here a = 1 and b = 1. The solutions over F23 to this equation are: (0, 1) (0, 22) (1, 7) (1, 16) (3, 10) (3, 13) (4, 0) (5, 4) (5, 19) (6, 4) (6, 19) (7, 11) (7, 12) (9, 7) (9, 16) (11, 3) (11, 20) (12, 4) (12, 19) (13, 7) (13, 16) (17, 3) (17, 20) (18, 3) (18, 20) (19, 5) (19, 18) E(F23) has 28 points, including the point at infinity O . The following are examples of the addition law: (3, 10) + (9, 7) = (17, 20). 2(3, 10) = (7, 12). 3.2.3 Format for challenge parameters (the Fp case) This subsection describes the conventions used for representing the challenge parameters for elliptic curves over Fp. Challenge parameters p - the order of the finite field; p is a prime number. seedE - the seed that was used to generate the parameters a and b (see Algorithm 5 in Section 3.2.4). a, b - the field elements which define the elliptic curve E : y2 = x3 + ax + b. seedP - the seed that was used to generate the point P (see Algorithm 7 in Section 3.2.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(Fp) divided by n). seedQ - the seed that was used to generate the point Q (see Algorithm 7 in Section 3.2.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 Fp) are represented as hexadecimal integers. Seeds for generating random elliptic curves and random elliptic curve points (see Section 3.2.4) are 160-bit strings and are represented in hexadecimal. 3.2.4 Random elliptic curves and points (the Fp 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: t = log2 p , s = (t - 1) / 160 and h = t - 160 . s. Algorithm 5: Generating a random elliptic curve over Fp Input: A field size p, where p is prime. Output: A 160-bit bit string seedE and field elements a, b Fp which defines an elliptic curve E over Fp. 1. Choose an arbitrary bit string seedE of length 160 bits. 2. Compute H = SHA-1(seedE), and let c0 denote the bit string of length h bits obtained by taking the h rightmost bits of H. 3. Let W0 denote the bit string of length h bits obtained by setting the leftmost bit of c0 to 0. (This ensures that r < p.) 4. For i from 1 to s do: Compute Wi = SHA-1((seedE + i) mod 2160). 5. Let W be the bit string obtained by the concatenation of W0 ,W1 , ... ,Ws as follows: W = W0 W1 ... Ws. 6. Let w1, w2, ... ,wt be the bits of W from leftmost to rightmost. Let r be the integer r = wi 2t-1. 7. Choose arbitrary integers a, b Fp such that r . b2 a3 mod p. (Note: For a fixed r 0, there are only 2 essentially different choices for a and b -- other values of a and b give rise to isomorphic elliptic curves. Hence the choice of a and b are essentially without loss of generality.) 8. If 4a3 + 27b2 0 (mod p) then go to step 1. 9. The elliptic curve chosen over Fp is E: y2 = x3 + ax + b. 10. Output(seedE, a, b). Algorithm 6: Verifying that an elliptic curve was randomly generated Input: A field size p (a prime), a bit string seedE of length 160 bits, and field elements a, b Fp which define an elliptic curve E : y2 = x3 + ax + b over Fp. Output: Acceptance or rejection that E was randomly generated using Algorithm 5. 1. Compute H = SHA-1(seedE), and let c0 denote the bit string of length h bits obtained by taking the h rightmost bits of H. 2. Let W0 denote the bit string of length h bits obtained by setting the leftmost bit of c0 to 0. 3. For i from 1 to s do: Compute Wi = SHA-1((seedE + i) mod 2160). 4. Let W' be the bit string obtained by the concatenation of W0 ,W1 , ... ,Ws as follows: W' = W0 W1 ... Ws. 5. Let w1, w2, ... ,wt be the bits of W from leftmost to rightmost. Let r' be the integer r' = wi 2t-1. 6. If r' . b2 a3 (mod p) then accept; otherwise reject. Algorithm 7: Generating a random elliptic curve point Input: Field elements a, b Fp which define an elliptic curve E : y2 = x3 + ax + b over Fp. The order of E(Fp) is n . h, where n is a prime. Output: A bit string seedP, a field element yU, and a point P E(Fp) of order n. 1. Choose an arbitrary bit string seedP of length 160 bits. 2. Compute H = SHA-1(seedP), and let c0 denote the bit string of length h bits obtained by taking the h rightmost bits of H. 3. Let x0 denote the bit string of length h bits obtained by setting the leftmost bit of c0 to 0. 4. For i from 1 to s do: Compute xi = SHA-1((seedE + i) mod 2160). 5. Let xU be the bit string obtained by the concatenation of x0 , x1 , ... , xs as follows: xU = x0 x1 ... xs. 6. If the equation y2 = xU3 + axU + b does not have a solution y Fp, then go to step 1. 7. Select an arbitrary solution yU Fp to the equation y2 = xU3 + axU + b. (Note: This equation will have either 1 or 2 distinct solutions. Hence the choice of yU is essentially without loss of generality.) 8. Let U be the point (xU, yU). 9. Compute P = hU. 10. If P = O, then go to step 1. 11. Output(seedP, yU , P). Algorithm 8: Verifying that an elliptic curve point was randomly generated Input: A field size p (a prime), field elements a, b Fp which define an elliptic curve E : y2 = x3 + ax + b over Fp, a bit string seedP of length 160 bits, a field element yU Fp, and an elliptic curve point P = (xP , yP). The order of E(Fp) is n . h, where n is a prime. Output: Acceptance or rejection that P was randomly generated using Algorithm 7. 1. Compute H = SHA-1(seedP), and let c0 denote the bit string of length h bits obtained by taking the h rightmost bits of H. 2. Let x0 denote the bit string of length h bits obtained by setting the leftmost bit of c0 to 0. 3. For i from 1 to s do: Compute xi = SHA-1((seedE + i) mod 2160). 4. Let xU be the bit string obtained by the concatenation of x0 , x1 , ... , xs as follows: xU = x0 x1 ... xs. 5. Let U be the point (xU , yU). 6. Verify that U satisfies the equation y2 = x3 + ax + b. 7. Compute P' = hU. 8. If P P' then reject. 9. Accept.

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