Jul,03

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.

www.standard-codes.com