GM/T 0003.1-2012_English: PDF (GM/T0003.1-2012)
Standard ID | Contents [version] | USD | STEP2 | [PDF] delivered in | Standard Title (Description) | Status | PDF |
GM/T 0003.1-2012 | English | 175 |
Add to Cart
|
0--9 seconds. Auto-delivery
|
Public key cryptographic algorithm SM2 based on elliptic curves - Part 1: General
| Valid |
GM/T 0003.1-2012
|
Standard ID | GM/T 0003.1-2012 (GM/T0003.1-2012) | Description (Translated English) | Public key cryptographic algorithm SM2 based on elliptic curves - Part 1: General | Sector / Industry | Chinese Industry Standard (Recommended) | Classification of Chinese Standard | L80 | Word Count Estimation | 47,470 | Date of Issue | 2012/3/21 | Date of Implementation | 2012/3/21 |
GM/T 0003.1-2012
GM
CRYPTOGRAPHY INDUSTRY STANDARD
OF THE PEOPLE’S REPUBLIC OF CHINA
ICS 35.040
L 80
File No.. 36826-2012
Public key cryptographic algorithm SM2
based on elliptic curves - Part 1. General
ISSUED ON. MARCH 21, 2012
IMPLEMENTED ON. MARCH 21, 2012
Issued by. State Cryptography Administration
Table of Contents
Foreword ... 3
Introduction ... 4
1 Scope ... 5
2 Symbols and abbreviations ... 5
3 Field and elliptic curve ... 7
4 Data type and its conversion ... 13
5 Elliptic curve’s system parameters and verification ... 19
6 Key pair generation and public key verification ... 22
Annex A (Informative) Background knowledge about elliptic curves ... 24
Annex B (Informative) Number theory algorithm ... 57
Annex C (Informative) Curve examples ... 71
Annex D (Informative) Quasi-random generation and verification of parameters
of elliptic curve equation ... 74
Bibliography ... 77
Introduction
In 1985, N. Koblitz and V. Miller independently proposed the application of
elliptic curves to cryptographic algorithm. The nature of the curve on which the
elliptic curve’s public key cryptography is based is as follows.
- elliptic curves on a finite field form a finite exchange group under point
addition; the order is similar to the base field;
- similar to the power operation in the finite field multiplication group, the
elliptic curve multi-point-multiplication operation constitutes a one-way
function.
In the multiple-point-multiplication operation, the multiple-point-multiplication
and the base point are known, and the problem of solving the multiplication is
called the elliptic curve’s discrete logarithm problem. For the discrete logarithm
problem of general elliptic curves, there is only a solution method for
exponential computational complexity. Compared with the large number
decomposition problem and the discrete logarithm problem on the finite field,
the elliptic curve’s discrete logarithm problem is much more difficult to solve.
Therefore, elliptic curve ciphers are much smaller than other public key ciphers
required for the same level of security.
This Part describes the necessary mathematical basics and general techniques
to help implement the cryptographic mechanisms specified in the various
sections.
Public key cryptographic algorithm SM2
based on elliptic curves - Part 1. General
1 Scope
This Part of GM/T 0003 gives the necessary mathematical basics and
associated cryptography techniques for the SM2 elliptic curve’s public key
cryptographic algorithm to help implement the cryptographic mechanisms
specified in other parts.
This Part is applicable to the elliptic curve’s public key cryptographic algorithm
with the base field as the prime field and the binary extension field.
2 Symbols and abbreviations
The following symbols and abbreviations apply to this Part.
a, b. elements in Fq; they define an elliptic curve E on Fq.
B. M( )V threshold; positive number B makes it difficult to find the discrete
logarithm on at least as much as the discrete logarithm of the elliptic curve
on Fq.
deg (f). the number of polynomials f(x).
E. an elliptic curve defined by a and b over a finite field.
E(Fq). a set of all rational points of elliptic curve E on Fq (including infinity point
O).
ECDLP. elliptic curve’s discrete logarithm problem.
Fp. a prime field containing p elements.
Fq. a finite field containing q elements.
. multiplicative group consisting of all non-zero elements in Fq.
. binary extension field containing 2m elements.
b) The multiplication unit is an integer 1.
c) The addition of field elements is an integer modulo p addition, that is, if
, then a + b = (a + b) mod p.
d) The multiplication of field elements is the modulo p multiplication of
integers, that is, if , then .
3.1.3 Binary field
When q is a power of 2m, the binary extension can be regarded as an m-
dimensional vector space on F2, and its elements can be represented by a bit
string of length m.
There are many ways to represent elements in . The two most commonly
used methods are the polynomial base (PB) representation (see Annex A.2.1.1)
and the normal base (NB) representation (see Annex A.2.1.3). The principle of
base is to make the operation efficiency in as high as possible. This
Standard does not specify the choice of base. The following is a polynomial
base representation as an example to illustrate the binary extension field .
Let the irreducible polynomial
(where , i = 0, 1, ..., m-1) to the m power on F2 be a reduced polynomial
of the binary extension . consists of all polynomials on F2 that are less
than m. The polynomial set {xm-1, xm-2, ..., x,1} is a set of bases of on F2,
called polynomial base. The coefficient of any element
in on F2 just constitutes a bit string of length
m, represented as .
a) Zero 0 is represented by an all-zero string.
b) Multiplication unit 1 is represented by bit string .
The known elliptic curve E(Fp), point with order of n and
, elliptic curve’s discrete logarithm problem refer that determining the
integer to make .
Elliptic curve’s discrete logarithm problem is related to the security of elliptic
curve’s cryptosystem, so it must choose a safe elliptic curve. For information on
how to choose a safe elliptic curve, see A.4 of Annex A.
3.2.6 Weak elliptic curve
If an elliptic curve has an attack method superior to level (n is the order of
the base point), the graph is a weak elliptic curve. It is forbidden to use weak
elliptic curve in this Standard.
The hypersingular curve on Fq (the characteristic divisible of
finite field Fq) and the Anomalous curve on Fq are weak elliptic
curves.
4 Data type and its conversion
4.1 Data type
In this Standard, data types include bit strings, byte strings, field elements,
points and integers on elliptic curves.
Bit string. ordered sequence of 0 and 1.
Byte string. an ordered sequence of bytes, where 8 bits are 1 byte.
Field element. Element in finite field Fq.
Point on elliptic curve. the point on the elliptic curve or a pair of
field elements ( ), where the field elements and satisfy the elliptic
curve equation, or the infinity point O.
The byte string representation of a point has multiple forms, which are identified
by a one-byte PC. The byte string representation of infinity point O is a single
zero byte PC=00. The non-infinity point has the following three
4.2.6 Conversion from field element to byte string
Input. element a in Fq.
Output. byte string S of length , where .
a) If q is an odd prime number, then a must be an integer in the interval [0,
q-1]. Convert a to a byte string S of length l according to the method of
4.2.2.
b) If q=2m, then a must be a bit string of length m. Convert a to a byte string
S of length l according to the method of 4.2.4.
4.2.7 Conversion from byte string to field element
Input. type of Fq, byte string S with length , where .
Output. element a in Fq.
a) If q is an odd prime number, convert S to an integer a according to the
method of 4.2.3. If , then report an error.
b) If q=2m, convert S to a bit string α of length m according to the method of
4.2.5.
4.2.8 Conversion from field element to integer
Input. element a in Fq.
Output. integer x.
a) If q is an odd prime, then x=a (no conversion required).
b) If q=2m, α must be a bit string of length m. Let sm-1, sm-2, ..., s0 be the
leftmost to rightmost bit of α, convert α to an integer x.
4.2.9 Conversion from point to byte string
Input. point on the elliptic curve, and P≠O.
uncompressed representation or mixed representation is used, the length of the
byte string S is . If compressed representation is selected, the length of
the byte string PO is .
Output. point on the elliptic curve, and P≠O.
a) If compressed representation is selected, then S=PC||X1. If uncompressed
representation or mixed representation, then S=PC||X1||Y1, where PC is a
single byte, X1 and Y1 are both byte strings of length l.
b) Convert byte string X1 to field element according to 4.2.7.
c) If compressed representation is chosen, then.
c.1) check PC=02 or PC=03, if not, report an error;
c.2) if PC=02, then let ; if PC=03, then let ;
c.3) convert to a point on the elliptic curve ( ) (see A.5 of
Annex A).
d) If uncompressed representation is chosen, then.
d.1) check PC=04; if not, report an error;
d.2) convert byte string Y1 to field element according to 4.2.7.
e) If mixed representation is chosen, then.
e.1) check PC=06 or PC=07; if not, report an error;
e.2) perform steps e.2.1) and e.2.2).
e.2.1) convert byte string Y1 to field element according to the details
of 4.2.7;
e.2.2) if PC=06, then let , otherwise ;
e.3) Convert to a point on the elliptic curve ( ) (see A.5,
Annex A).
f) If q is an odd prime number, then verify ; if not,
report an error;
if q=2m, then verify in ; if not, report an
error.
g) .
5 Elliptic curve’s system parameters and verification
5.1 General
Elliptic curve’s system parameters are publicly available. System security does
not depend on the secrecy of these parameters. This Standard does not specify
the method for generating elliptic curve’s system parameters, but specifies the
verification method for system parameters. The calculation of the elliptic curve
order and the selection method of the base point can be found in Annex B, B.3.
See Annex D for how to generate curve parameters.
Elliptic curve’s system parameters can be divided into two cases according to
the different base fields.
- elliptic curve’s system parameters on Fp when the base field is Fp (p is a
prime number greater than 3);
- elliptic curve’s system parameters on when the base field is .
5.2 Elliptic curve’s system parameters on Fp and verification
5.2.1 Elliptic curve’s system parameters on Fp
Elliptic curve’s system parameters on Fp include.
a) the size of the field is q=p, and p is a prime number greater than 3;
b) (optional) a bit string SEED of at least 192 (if an elliptic curve is generated
as described in Annex D);
c) two elements a and b in Fp, which define the equation of elliptic curve E.
y2=x3+ax+b;
d) base point ;
c) If the elliptic curve is randomly generated according to the method
described in Annex D, verify that SEED is a bit string with a length of at
least 192, and a, b are derived from SEED.
d) Verify b≠0.
e) Verify in .
f) Verify that n is a prime number, and (see B.1.10 of
Annex B).
g) Verify (see Annex A.3.2).
h) (optional) calculate and verify h=h’.
i) Verify that anti-MOV attack conditions are met (see Annex A, A.4.2.1).
j) If any of the above verifications fail, the output is "invalid"; otherwise the
output is "valid".
6 Key pair generation and public key verification
6.1 Key pair generation
Input. a set of valid elliptic curve’s system parameters for a valid Fq (q=p and p
is a prime number greater than 3, or q=2m).
Output. a key pair (d, P) associated with the elliptic curve’s system parameters.
a) Generate integer with a random number generator.
b) G is the base point, and the calculation point (see
Annex A, A.3.2).
c) The key pair is (d, P), where d is the private key and P is the public key.
6.2 Public key verification
6.2.1 Verification of elliptic curve’s public key on Fp
Input. a set of elliptic curve’s system parameters on a valid Fp (p is a prime
number greater than 3) and an associated public key P.
Gaussian normal base exists in when m cannot be divisible by 8. The
type T of the Gaussian normal base is a positive integer that measures the
complexity of the multiplication operation at this base. In general, the smaller
the type T, the higher the multiplication efficiency.
For given m and T, the field has at most one Gaussian normal base of type
T. In all normal bases, Gaussian normal bases of type 1 and type 2 have the
most efficient multiplication operations, and are therefore also referred to as
optimal normal bases. Type 1 Gaussian normal base is Type I optimal normal
base. Type 2 Gaussian normal base is Type II optimal normal base.
The element a in the finite field can be represented by a bit string of length
m (αm-1αm-2... α1α0) under a Gaussian normal base.
a) Multiplication unit element 1 is represented by m 1 bit strings.
b) Zero 0 is represented by m 0 bit strings.
c) The addition of two field elements is done by bit string alignment XOR
operation.
d) The multiplication of field elements is described in Annex A.2.1.4.3.
A.2.1.4.1 Rules for choosing a normal base
Select the smallest type of Gaussian normal base that exists in .
Table A.5 lists the types of upper Gaussian normal bases of prime
numbers m in [192, 512].
using the formula of the first term c0 of the product of two elements. The three
parts are described in detail below.
- Multiplication precalculation
Input. an integer m greater than 1, a positive integer T, where there is a
Gaussian normal base B of type T on .
Output. relative to B's sequence f(l), f(2),...,f(p-1).
a) Calculate .
b) Generate an integer u with a modulo p-order T (see Annex B.1.9).
c) Calculate the sequence f(1), f(2),...,f(p-1).
c.1) Set w=1;
c.2) From j=0 to T-1, execute.
c.2.1) Set n=w;
c.2.2) From i=0 to m-1, execute.
c.2.2.1) Set f(n)=i;
c.2.2.2) Set n=2n mod p;
c.2.2.3) Set w=u•w mod p.
d) Output sequences f(1), f(2), ..., f(p-1).
- Given two field elements a and b under the Gaussian normal base B
representation, formula of the first term c0 of the product
Note c0=F(a, b).
Input. an integer m greater than 1, a positive integer T (where there is a
Gaussian normal base B of type T on ) and two field elements a, b under
the Gaussian normal base B representation.
Output. formula of the first term c0 of the product of the two field elements a, b
under the Gaussian normal base B.
a) Use the multiplication pre-calculation to get the output sequence f(1),
f(2),...,f/(p-1).
Note c=(c0c1c2c3c4), then c=a•b=(11111).
A.2.2 Definition of elliptic curve on
A.2.2.1 General
There are two common representations of elliptic curves on . affine
coordinate representation and projective coordinate representation.
A.2.2.2 Affine coordinate representation
The non-super singular elliptic curve equation on can be simplified to
y2+xy=x3+ax2+b in the affine coordinate system,
where , and b≠0. The set of points on the elliptic curve are denoted
as , and satisfies the curve equation
, where O is the infinity point of the elliptic
curve, also known as the zero point.
The points on E( ) form an Abelian group according to the following addition
rules.
a) O=O=O.
b) .
c) , the inverse element of P.
d) Two non-reciprocal rules for adding different points.
Complexity under Jacobian aggravated projective
coordinates
Algorithm 3
Base field is prime field.
Complexity under affine coordinates
Complexity under standard projective coordinates
Complexity under Jacobian aggravated projective
coordinates
Base field is binary expansion field.
Complexity under affine coordinates
Complexity under standard projective coordinates
Complexity under Jacobian aggravated projective
coordinates
A.4 Method for solving discrete logarithm problem of elliptic curve
A.4.1 Solving methods for elliptic curve’s discrete logarithm
With known elliptic curve E(Fq) and the point P∈E(Fq) and Q∈< P> of which
the order is n, the elliptic curve’s discrete logarithm problem is to determine the
integer k∈[0,n-1] to make Q= [k]P established.
ECDLP has existing attack methods.
● Pohlig-Hellman method. let l be the largest prime factor of n, then the
algorithm complexity is ;
● BSGS method. time complexity and space complexity are both ;
● Pollard method. algorithm complexity is ;
● Parallel Pollard method. let r be the number of parallel processors, and the
algorithm complexity is reduced to ;
● MOV-method. discrete logarithm problem for reducing the EDDLP of super-
singular elliptic curves and curves with similar properties to the small spread of
Fq (sub-exponential computational complexity algorithm);
● Discrete logarithm solution method for abnormal curve. effective attack
method for the anomaly curve (#E(Fp)=p curve) (polynomial-level
computational complexity algorithm);
● GHS-method. Weil descent technique is used to solve the discrete logarithm
problem of the elliptic curve on the binary expansion field with the expansion
number as the composite number, and the ECDLP is transformed into the
discrete logarithm problem of the hyperelliptic curve, and the discrete logarithm
of the hyperelliptic curve for solving the high genus has the sub-index. Level
computational complexity algorithm.
For the discrete logarithm problem of general curves, the current solution
methods are exponential computational complexity, and no general sub-
exponential computational complexity is found. For discrete logarithm problems
of some special curves, there are polynomial computational complexity or sub-
exponential computational complexity algorithms.
When selecting curves, avoid using weak ellipses in the cryptographic sense
that are vulnerable to the above methods.
A.4.2 Conditions for safe elliptic curve
A.4.2.1 Conditions for anti-MOV attack
A.Menczes, T.Okamoto, S.Vanstone.G.Frey and H.Rück's reduced attacks
reduce the elliptic curve’s discrete logarithm problem on the finite field Fq to the
discrete logarithm problem on . This attack method is practical only
when B is small, and most elliptic curves do not match this situation. Anti-MOV
attack conditions ensure that an elliptic curve is not vulnerable to this reduction.
The elliptic curve on most Fq does meet the anti-MOV attack conditions.
A MOV threshold must be selected before verifying anti-MOV attack conditions.
It is a positive integer B that makes the discrete logarithm problem at least as
difficult as finding the discrete logarithm problem of the elliptic curve on Fq. For
q>2191, B≥27 is required. Choosing B≥27 also limits the selection of non-super
singular elliptic curves.
The following algorithm is used to verify whether the elliptic curve’s system
parameters meet the anti-MOV attack conditions.
Input. MOV threshold B, prime power q and prime number n (n is a prime factor
of #E(Fq), where E(Fq) is an elliptic curve on Fq).
Output. if the elliptic curve containing the nth base point on Fq satisfies the anti-
MOV attack condition, the output is "correct"; otherwise, the output "error".
a) Set t=1.
b) Execute i from 1 to B.
b.1) set ;
b.2) if t=1, output "error" and end.
c) Output “correct”.
A.4.2.2 Conditions for anti-abnormal curve attack
Let E(Fp) be an elliptic curve defined on the prime field Fp. If #E(Fp)=p, the
elliptic curve E(Fp) is called an abnormal curve. N.Smart, T.Satoh and K.Araki
prove that the discrete logarithm of the anomaly curve can be solved in
polynomial time. The anti-abnormal curve attack condition is #E(Fp) ≠p, which
satisfies this condition to ensure that the elliptic curve is not attacked by the
abnormal curve. The vast majority of elliptic curves on Fp do meet the anti-
abnormal curve attack conditions.
The following algorithm is used to verify whether the elliptic curve’s system
parameters meet the anti-abnormal curve attack conditions.
Input. elliptic curve E(Fp) on Fp, order N=#E(Fp).
Output. if E(Fp) satisfies the anti-abnormal curve attack condition, the output
message is "correct"; otherwise, the output message "error".
a) If N=p, output "error"; otherwise the output is "correct".
A.4.2.3 Other conditions
In order to avoid the attack of the Pohlig-Heilman method and the Pollard
method, the order n of the base point must be a sufficiently large prime number.
In order to avoid the attack of GHS method, m in shall choose prime
number.
A.5 Compression of points on elliptic curve
A.5.1 Genreal
For any non-infinity point on the elliptic curve E(Fq), the point can
be succinctly represented by storing only the x-coordinate and a
specific bit derived from and , called as compression representation of
points.
Annex B
(Informative)
Number theory algorithm
B.1 Finite field and modular operation
B.1.1 Exponential operation in finite field
Let a be a positive integer, g be an element on the field Fq, and the exponential
operation is the operation of calculating ga. The exponential operation can be
performed efficiently by the binary method outlined below.
Input. positive integer a, field Fq, field element g.
Output. ga.
a) Let e=a mod (q-1), if e=0, output 1.
b) Let the binary representation of e be e=erer-1...e1e0, with the highest er
being 1.
c) Set x=g.
d) Execute i from r-1 to 0.
d.1) Set x=x2;
d.2) If ei=1, then set .
e) Output x.
B.1.2 Inverse operation in finite field
Let g be a non-zero element on the field Fq, then the inverse element g-1 is the
field element c that makes true. Since c=gq-2, the inversion can be
achieved by exponential operation. Note that if q is a prime number and g is an
integer satisfying 1≤g≤g-1, then g-1 is an integer c, 1≤c≤ q-1 and g·c≡1 (mod
q).
Input. field Fq, non-zero element g in field Fq.
Output. inverse element g-1.
square roots (mod p), if y is one of the square roots, then the other square root
is p-y.
The following algorithm can determine if g has a square root (mod p), and if so,
calculate one of the roots.
Input. odd prime number p, integer g, 0< g< p.
Output. If there is a square root of g, then a square root mod p is output,
otherwise the output "no square root exists".
Algorithm 1. For p≡3(mod 4), i.e. there is a positive integer u such that p=4u+3.
a) Calculate y=gu+1 mod p (see B.1.1).
b) Calculate z=y2 mod p.
c) If z=g, output y; otherwise the output "no square root exists".
Algorithm 2. For p≡5(mod 8), there is a positive integer u such that p=8u+5.
a) Calculate z=g2n+1 mod p (see B.1.1).
b) If , calculate y=gu+1 mod p, output y, terminate the algorithm.
c) If , calculate y=(2g·4g)u) mod p), output y, terminate the
algorithm.
d) Output "no square root exists".
Algorithm 3. For , there is a positive integer u to make p=8u+l.
a) Set Y=g.
b) Generate random number X, 0< X< p.
c) Calculate the Lucas sequence element (see B.1.3). U=U4u+1 mod p,
V=V4u+1 mod p.
d) If V2≡4Y(mod p), output y=(V/2) mod p and terminate.
e) If U mod p≠1 and U mod p≠p-1, the output "no square root exists" and
terminate.
f) Back to step b).
b) Set z=0, w=β.
c) Execute i from 1 to m-1.
c.1) ;
c.2) .
d) If w≠0, the output "no solution" and terminate.
e) Output z.
B.1.7 Check of integer modulus prime order
Let p be a prime number, the integer g satisfies l< g< p, and the order of g mod
p refers to the smallest positive integer k such that gk≡(mod p). The following
algorithm tests whether the order of g mod p is k.
Input. prime number p, divide by positive integer k of P-1, integer g satisfies
1< g< p.
Output. if k is the order of g mod p, the output is "correct", otherwise the output
is "error".
a) Determine the prime factor of k.
b) If gk mod p≠1, output "error", terminate.
c) For each prime factor l of k, execute.
c.1) if gk/1 mod p=1, output "error", terminate.
d) Output “correct”.
B.1.8 Calculation of integer modulus prime order
Let p be a prime number and the integer g satisfy 1< g< p. The following
algorithm determines the order of g mod p. This algorithm is only valid when p
is small.
Input. prime number p and integer g satisfying 1< g< p.
Output. k -- the order of g mod p.
a) Set b=g, j=1.
b) .
b.4.4) next i;
b.5) output "combination" and terminate;
b.6) next j.
c) Output "probability prime number".
If the algorithm outputs "combination", then u is a composite number. If the
algorithm outputs "probability prime number", the probability that u is a
composite number is less than 2-2T. Thus, by choosing a sufficiently large T, the
error can be ignored.
B.1.11 Approximate prime detection
Give a trial bound lmax. If each prime factor of the positive integer h does not
exceed lmax, then h is called lmax - smooth. Give a positive integer rmin. If there is
a prime number v≥rmin such that the positive integer u = h·v, and the integer h
is lmax - smooth, then u is called an approximate prime number. The following
algorithm checks the approximate prime of u.
Input. positive integer u, lmax and rmin.
Output. if h is an approximate prime number, output h and v; otherwise the
output is "not approximate prime".
a) Set v=u, h=1.
b) Execute l from 2 to lmax.
b.1) if l is a composite number, go to step b.3);
b.2) perform loop execution when l divides v.
b.2.1) set v=v/l and h=h·l;
b.2.2) if v< rmin, the output is "not approximate prime" and terminate;
b.3) next l.
c) If v is a probability prime, output h and v and terminate.
d) Output "not approximate prime number".
B.2 Polynomial on finite field
B.2.1 Maximum common factor
If f(t) ≠0 and g(t) ≠0 are two polynomials of the coefficient in the field Fq, then
Annex D
(Informative)
Quasi-random generation and verification of parameters of elliptic curve
equation
D.1 Quasi-random generation of parameters of elliptic curve equation
D.1.1 Quasi-random generation of parameters of elliptic curve equation
on Fp
Method 1.
Input. the size of the prime field p.
Output. the elements a, b in the bit string SEED and Fp.
a) Optionally select a bit string SEED with a length of at least 192.
b) Calculate H=H256(SEED) and record H=(h255, h254, ..., h0).
c) Set .
d) Set r=R mod p.
e) Arbitrarily select the elements a and b in Fp so that r·b2≡a3(mod p).
f) If (4a3+27b2) mod p=0, go to step a).
g) The elliptic curve on the selected Fp is E. y2=x3+ax+b.
h) Output (SEED, a, b).
Method 2.
Input. the size of the prime field p.
Output. the elements a, b in the bit string SEED and Fp.
a) Optionally select a bit string SEED with a length of at least 192.
b) Calculate H=H256(SEED) and record H=(h255, h254, ..., h0).
Method 1
Input. the elements a, b in the bit string SEED and Fp.
Output. Input parameters "valid" or "invalid".
a) Calculate H'=H256(SEED) and record H'=(h255, h254, ..., h0).
b) Set .
c) Set r’=R’ mod p.
d) If r'·b2≡a3(mod p), "valid" is output; otherwise, "invalid" is output.
Method 2
Input. bit string SEED and element b in Fp.
Output. input parameters "valid" or "invalid".
a) Calculate H'=H256(SEED) and record H'=(h255, h254, ..., h0).
b) Set .
c) Set r’=R’ mod p.
d) If r'=b, the output is "active"; otherwise the output is "invalid".
D.2.2 Verification of parameters of elliptic curve equation on
Input. bit string SEED and element b in .
Output. input parameters "valid" or "invalid".
a) Calculate H'=H256(SEED) and record H'=(h255, h254, ..., h0).
b) If i≥256, let hi=1, set the bit string HH' = (hm-1, hm-2, ..., h0), b' is the element
in corresponding to HH'.
c) If b'=b, the output is "valid"; otherwise the output is "invalid".
NOTE. The function H256 ( ) in this appendix is a cryptographic hash function with an output length of 256
bits.
......
|