BS ISO IEC 15946-5 pdf – Information technology — Security techniques — Crytographic technique based on elliptic curves Part 5: Elliptic curve generation

BS ISO IEC 15946-5 pdf – Information technology — Security techniques — Crytographic technique based on elliptic curves Part 5: Elliptic curve generation
Set n = n/l and r = rl.
⎯ If n < n min then output ―not nearly prime‖ and stop. 3) Next l. c) Test n for primality. d) If n is prime then output r and n and stop. e) Output ―not nearly prime‖. NOTE Methods to test for primality are described in [3] and [4]. 6.1.3 Finding a Point of Large Prime Order If the order #E(F(q)) of an elliptic curve E is nearly prime, the following algorithm efficiently produces a random point in E(F(q)) whose order is the large prime factor n of #E(F(q)) = rn. Input: an elliptic curve E over the field F(q), a prime n, and a positive integer r not divisible by n. Output: if #E(F(q)) = rn, a point G on E of order n; if not, the message ―wrong order.‖ a) Generate a random point P (not O E ) on E. b) Set G = rP. c) If G = O E then go to Step a). d) Set Q = nG. e) If Q ≠ O E then output ―wrong order‖ and stop. f) Output G. 6.1.4 Verification of Elliptic Curve Pseudo-Randomness The following algorithm determines whether an elliptic curve over F(p) was generated using the method of 6.1 .1 . The quantities L Hash , L, v, s, and w, and the hash function H, are as in 6.1 .1 . Input: a bit string X of length L, EC parameters q = p, a, b, n, and G = (x G , y G ), and a positive integer n min . Output: ―True‖ or ―False‖. a) Compute h = H (X). b) Let W 0 be the bit string obtained by taking the w rightmost bits of h. c) Convert X to an integer Z = BS2IP(X). d) For i from 1 to s do: 1 ) Compute Z = Z + i mod 2 L . 2) Convert Z mod (2 L ) to a bit string X i = I2BSP(Z). 3) Compute W i = H (X i ). e) Let W be the bit string obtained by the concatenation of W 0 , W 1 , …, W s as follows: W = W 0 || W 1 || … || W s . f) Convert W to a finite field element c = OS2FEP (BS2OSP (W)). g) Verify the following conditions. ⎯ n ≥ n min ⎯ n is a prime. ⎯ c ≠ 0 F ⎯ 4c + 27 ≠ 0 F . ⎯ b ≠ 0 F ⎯ cb 2 - a 3 = 0 F . ⎯ G ≠ O E G = x G + ax G + b. ⎯ nG = O E h) If all the conditions in Step g) hold, then output ―True‖; otherwise output ―False‖. 6.2 Constructing Verifiably Pseudo-Random Elliptic Curves (binary case) 6.2.1 Construction algorithm The following algorithm produces a set of elliptic curve parameters for a pseudo-random curve over a field F(2 m ), along with sufficient information for others to verify that the curve was indeed chosen pseudo-randomly. NOTE 1 The algorithm is consistent with [1 6]. It is assumed that the following quantities have been chosen: ⎯ a field F(2 m ) ⎯ a lower bound n min for the order of the base point ⎯ a cryptographic hash function H with output length L Hash bits ⎯ the bit length L of inputs to H, satisfying L ≥ L Hash . The following notation is adopted below: ⎯ s = ⎣ (m - 1)/ L Hash ⎦ , ⎯ w = m - sL Hash . Input: a field F(2 m ); a lower bound n min for n; a trial division bound l max . Output: a bit string X; EC parameters a, b, n, and G.