ISO/IEC 15946-1:2008
(Main)Information technology — Security techniques — Cryptographic techniques based on elliptic curves — Part 1: General
Information technology — Security techniques — Cryptographic techniques based on elliptic curves — Part 1: General
ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. It consists of five parts and includes the establishment of keys for symmetric cryptographic techniques, and digital signature mechanisms. ISO/IEC 15946-1:2008 specifically addresses the general techniques based on elliptic curves. It describes the mathematical background and specifies the general techniques necessary for implementing mechanisms based on elliptic curves defined over finite fields or pairings based on elliptic curves. ISO/IEC 15946-1:2008 specifies conventional functions, elliptic curves over any finite field such as a prime field and an extension field with characteristic two or three together with coordinates, pairings over an elliptic curve.
Technologies de l'information — Techniques de sécurité — Techniques cryptographiques basées sur les courbes elliptiques — Partie 1: Généralités
General Information
Relations
Standards Content (Sample)
INTERNATIONAL ISO/IEC
STANDARD 15946-1
Second edition
2008-04-15
Information technology — Security
techniques — Cryptographic techniques
based on elliptic curves —
Part 1:
General
Technologies de l'information — Techniques de sécurité — Techniques
cryptographiques basées sur les courbes elliptiques —
Partie 1: Généralités
Reference number
ISO/IEC 15946-1:2008(E)
©
ISO/IEC 2008
---------------------- Page: 1 ----------------------
ISO/IEC 15946-1:2008(E)
PDF disclaimer
This PDF file may contain embedded typefaces. In accordance with Adobe's licensing policy, this file may be printed or viewed but
shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In
downloading this file, parties accept therein the responsibility of not infringing Adobe's licensing policy. The ISO Central Secretariat
accepts no liability in this area.
Adobe is a trademark of Adobe Systems Incorporated.
Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation
parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In
the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below.
COPYRIGHT PROTECTED DOCUMENT
© ISO/IEC 2008
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2008 – All rights reserved
---------------------- Page: 2 ----------------------
ISO/IEC 15946-1:2008(E)
Contents Page
Foreword. iv
Introduction . v
1 Scope .1
2 Terms and definitions.1
3 Symbols .2
4 Conventions of fields .3
4.1 Finite prime fields F(p).3
m
4.2 Finite fields F(p ).3
5 Conventions of elliptic curves.4
5.1 Definition of elliptic curves.4
5.2 The group law on elliptic curves.5
5.3 Cryptographic bilinear map .5
6 Conversion functions.5
6.1 Octet string / bit string conversion: OS2BSP and BS2OSP.5
6.2 Bit string / integer conversion: BS2IP and I2BSP.5
6.3 Octet string / integer conversion: OS2IP and I2OSP .6
6.4 Finite field element / integer conversion: FE2IP .6
F
6.5 Octet string / finite field element conversion: OS2FEP and FE2OSP .6
F F
6.6 Elliptic curve point / octet string conversion: EC2OSP and OS2ECP .7
E E
6.7 Integer / elliptic curve conversion: I2ECP .8
7 Elliptic curve domain parameters and public key .8
7.1 Elliptic curve domain parameters over F(q) .8
7.2 Elliptic curve key generation .9
Annex A (informative) Background information on finite fields .10
A.1 Bit strings .10
A.2 Octet strings.10
A.3 The finite field F(q).10
Annex B (informative) Background information on elliptic curves.12
B.1 Properties of elliptic curves.12
B.2 The group law for elliptic curves E over F(q) with p > 3.12
m
B.3 The group law for elliptic curves over F(2 ) .16
m
B.4 The group law for elliptic curves over F(3 ) .17
B.5 The existence condition of an elliptic curve E.19
Annex C (informative) Background information on elliptic curve cryptosystems.21
C.1 Definition of cryptographic problems.21
C.2 Algorithms to determine discrete logarithms on elliptic curves.21
C.3 Scalar multiplication algorithms of elliptic curve points.22
C.4 Algorithms to compute pairings.24
C.5 Elliptic curve domain parameters and public key validation (optional).25
Bibliography .30
© ISO/IEC 2008 – All rights reserved iii
---------------------- Page: 3 ----------------------
ISO/IEC 15946-1:2008(E)
Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that are members of
ISO or IEC participate in the development of International Standards through technical committees established
by the respective organization to deal with particular fields of technical activity. ISO and IEC technical
committees collaborate in fields of mutual interest. Other international organizations, governmental and non-
governmental, in liaison with ISO and IEC, also take part in the work. In the field of information technology, ISO
and IEC have established a joint technical committee, ISO/IEC JTC 1.
International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2.
The main task of the joint technical committee is to prepare International Standards. Draft International
Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as
an International Standard requires approval by at least 75 % of the national bodies casting a vote.
ISO/IEC 15946-1 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
This second edition cancels and replaces the first edition (ISO/IEC 15946-1:2002), which has been technically
revised.
ISO/IEC 15946 consists of the following parts, under the general title Information technology — Security
techniques — Cryptographic techniques based on elliptic curves:
⎯ Part 1: General
⎯ Part 3: Key establishment
Elliptic curve generation will form the subject of a future Part 5.
iv © ISO/IEC 2008 – All rights reserved
---------------------- Page: 4 ----------------------
ISO/IEC 15946-1:2008(E)
Introduction
One of the most interesting alternatives to the RSA and F(p) based cryptosystems that are currently available
are cryptosystems based on elliptic curves defined over finite fields. The concept of an elliptic curve based
public-key cryptosystem is quite simple.
⎯ Every elliptic curve over a finite field is endowed with an addition "+" under which it forms a finite abelian
group.
⎯ The group law on elliptic curves extends in a natural way to a "discrete exponentiation" on the point group
of the elliptic curve.
⎯ Based on the discrete exponentiation on an elliptic curve, one can easily derive elliptic curve analogues of
the well-known public-key schemes of the Diffie–Hellman and ElGamal type.
The security of such a public-key cryptosystem depends on the difficulty of determining discrete logarithms in
the group of points of an elliptic curve. This problem is, with current knowledge, much harder than the
factorisation of integers or the computation of discrete logarithms in a finite field. Indeed, since Miller and
Koblitz independently suggested the use of elliptic curves for public-key cryptographic systems in 1985, the
elliptic curve discrete logarithm problem has only been shown to be solvable in certain specific, and easily
recognisable, cases. There has been no substantial progress in finding a method for solving the elliptic curve
discrete logarithm problem on arbitrary elliptic curves. Thus, it is possible for elliptic curve based public-key
systems to use much shorter parameters than the RSA system or the classical discrete logarithm based
systems that make use of the multiplicative group of some finite field. This yields significantly shorter digital
signatures and system parameters and the integers to be handled by a cryptosystem are much smaller.
This part of ISO/IEC 15946 describes the mathematical background and general techniques necessary for
implementing any of the mechanisms described in other parts of ISO/IEC 15946 and other ISO/IEC standards.
It is the purpose of this part of ISO/IEC 15946 to meet the increasing interest in elliptic curve based public-key
technology and describe the components that are necessary to implement secure elliptic curve cryptosystems
such as key-exchange, key-transport and digital signatures.
The International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC)
draw attention to the fact that it is claimed that compliance with this document may involve the use of patents.
The ISO and IEC take no position concerning the evidence, validity and scope of these patent rights.
The holders of these patent rights have assured the ISO and IEC that they are willing to negotiate licences
under reasonable and non-discriminatory terms and conditions with applicants throughout the world. In this
respect, the statements of the holders of these patent rights are registered with the ISO and IEC. Information
may be obtained from:
ISO/IEC JTC 1/SC 27 Standing Document 8 (SD 8) “Patent Information”
SD 8 is publicly available at: http://www.ni.din.de/sc27
Attention is drawn to the possibility that some of the elements of this document may be the subject of patent
rights other than those identified above. ISO and IEC shall not be held responsible for identifying any or all
such patent rights.
© ISO/IEC 2008 – All rights reserved v
---------------------- Page: 5 ----------------------
INTERNATIONAL STANDARD ISO/IEC 15946-1:2008(E)
Information technology — Security techniques — Cryptographic
techniques based on elliptic curves —
Part 1:
General
1 Scope
ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. These include the
establishment of keys for secret-key systems, and digital signature mechanisms.
This part of ISO/IEC 15946 describes the mathematical background and general techniques necessary for
implementing any of the mechanisms described in other parts of ISO/IEC 15946 and other ISO/IEC standards.
The scope of this part of ISO/IEC 15946 is restricted to cryptographic techniques based on elliptic curves
defined over finite fields of prime power order (including the special cases of prime order and characteristic
two). The representation of elements of the underlying finite field when the field is not of prime order (i.e. which
basis is used) is outside the scope of this part of ISO/IEC 15946.
ISO/IEC 15946 does not specify the implementation of the techniques it defines. Interoperability of products
complying with this part of ISO/IEC 15946 will not be guaranteed.
2 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
2.1
finite field
any field containing a finite number of elements
m
NOTE For any positive integer m and a prime p, there exists a finite field containing exactly p elements. This field is
m m
unique up to isomorphism and is denoted by F(p ), where p is called the characteristic of F(p ).
2.2
elliptic curve
any cubic curve E without any singular point
NOTE The set of points of E is an abelian group. The field that includes all coefficients of the equation describing E
is called the definition field of E. In this part of ISO/IEC 15946, we deal with only finite fields F as the definition field. When
we describe the definition field F of E explicitly, we denote the curve as E/F.
2.3
cryptographic bilinear map
cryptographic bilinear map e satisfying the non-degeneracy, bilinearity, and computability
n
© ISO/IEC 2008 – All rights reserved 1
---------------------- Page: 6 ----------------------
ISO/IEC 15946-1:2008(E)
3 Symbols
In this document, the following notation is used to describe public-key systems based on elliptic curve
technology.
d The private key of a user. (d is a random integer in the set [2, n-2].)
2 3 m
E An elliptic curve, either given by an equation of the form Y = X + aX + b over the field F(p )for
2 3 2 m
p>3, by an equation of the form Y + XY = X + aX + b over the field F(2 ), or by an equation of the
2 3 2 m
form Y = X + aX + b over the field F(3 ), together with an extra point O referred to as the point
E
m m m
at infinity. The curve is denoted by E/F(p ), E/F(2 ), or E/F(3 ), respectively.
E(F(q)) The set of F(q)-valued points of E and O .
E
#E(F(q)) The order (or cardinality) of E(F(q)).
E[n] The n-torsion group of E, that is { Q ∈ E | nQ = O }.
E
|F | The bit size of a finite field F.
m m
F(q) The finite field consisting of exactly q elements. This includes the cases of F(p), F(2 ), and F(p ).
F(q)* F(q)\{0 }
F
G The base point on E with order n.
The group generated by G with cardinality n.
kQ The k-th multiple of some point Q of E, i.e. kQ = Q+ …+Q (k summands) if k > 0, kQ = (–k)(–Q) if k
< 0, and kQ = O if k = 0.
E
µ The cyclic group of order n comprised of the n-th roots of unity in the algebraic closure of F(q).
n
n A prime divisor of #E(F(q)).
O The elliptic curve point at infinity.
E
p A prime number.
P The public key of a user. (P is an elliptic curve point in .)
m
q A prime power, p for some prime p and some integer m ≥1.
Q A point on E with coordinates (x , y ).
Q Q
Q +Q The elliptic curve sum of two points Q and Q .
1 2 1 2
x The x-coordinates of Q ≠ O .
Q
E
y
The y-coordinates of Q ≠ O .
Q
E
[0, k] The set of integers from 0 to k inclusive.
0 The identity element of F(q) for addition.
F
1 The identity element of F(q) for multiplication.
F
NOTE Oct(m) and L(m) are defined in Clauses 6.2 and 6.3, respectively.
2 © ISO/IEC 2008 – All rights reserved
---------------------- Page: 7 ----------------------
ISO/IEC 15946-1:2008(E)
4 Conventions of fields
4.1 Finite prime fields F(p)
For any prime p there exists a finite field consisting of exactly p elements. This field is uniquely determined up
to isomorphism and in this document it is referred to as the finite prime field F(p).
The elements of a finite prime field F(p) may be identified with the set [0, p - 1] of all non-negative integers less
than p. F(p) is endowed with two operations called addition and multiplication such that the following conditions
hold:
⎯ F(p) is an abelian group with respect to the addition operation “+”.
For a, b ∈ F(p) the sum a + b is given as a + b := r, where r ∈ F(p) is the remainder obtained when the
integer sum a + b is divided by p.
⎯ F(p)\{0} denoted as F(p)* is an abelian group with respect to the multiplication operation “×”.
For a, b ∈ F(p) the product a × b is given as a × b := r, where r ∈ F(p) is the remainder obtained when the
integer product a × b is divided by p. When it does not cause confusion, × is omitted and the notation ab is
used or the notation a⋅b is used.
m
4.2 Finite fields F(p )
m
For any positive integer m and prime p, there exists a finite field of exactly p elements. This field is unique up
m
to isomorphism and in this document it is referred to as the finite field F(p ).
m m
NOTE 1 (1) F(p ) is the general definition including F(p) for m = 1 and F(2 ) for p = 2
(2) If p = 2, then field elements may be identified with bit strings of length m and the sum of two field elements
is the bit-wise XOR of the two bit strings.
m
The finite field F(p ) may be identified with the set of p-ary strings of length m in the following way. Every finite
m m
field F(p ) contains at least one basis {ξ , ξ ,···, ξ } over F(p) such that every element α ∈ F(p ) has a unique
1 2 m
representation of the form α = a ξ + a ξ + ··· + a ξ , with a ∈ F(p) for i = 1, 2,···, m. The element α can then be
1 1 2 2 m m i
m
identified with the p-ary string (a , a ,···, a ). The choice of basis is beyond the scope of this document. F(p ) is
1 2 m
endowed with two operations called addition and multiplication such that the following conditions hold:
m
⎯ F (p ) is an abelian group with respect to the addition operation “+”.
For α = (a , a ,···, a ) and β = (b , b ,···, b ) the sum a + β is given by a + β := γ = (c , c ,···, c ), where c =
1 2 m 1 2 m 1 2 m i
a + b is the sum in F (p). The identity element for addition is 0 = (0,···, 0).
i i F
*
m m
⎯ F(p )\{0}, denoted by F(p ) , is an abelian group with respect to the multiplication operation “×”.
For α = (a , a ,···, a ) and β = (b , b ,···, b ) the product α × β is given by a p-ary string a × β :=γ = (c , c ,···,
1 2 m 1 2 m 1 2
c ), where c = a b d for ξ ξ = d ξ + d ξ + . + d ξ (1 ≤ j, k ≤ m). When it does not cause
m i ∑1≤ j,k ≤m j k i,j,k j k 1,j,k 1 2,j,k 2 m,j,k m
confusion, × is omitted and the notation ab is used. The basis can be chosen in such a way that the
identity element for multiplication is 1 = (1,0,···, 0).
F
NOTE 2 The choice of basis is described in [7].
© ISO/IEC 2008 – All rights reserved 3
---------------------- Page: 8 ----------------------
ISO/IEC 15946-1:2008(E)
5 Conventions of elliptic curves
5.1 Definition of elliptic curves
m
5.1.1 Elliptic curves over F(p )
m
Let F(p ) be a finite field with a prime p > 3 and a positive integer m. In this document it is assumed that E is
described by a “short (affine) Weierstrass equation”, that is an equation of type
2 3 m
Y = X + aX + b with a, b ∈ F(p )
3 2 m
such that 4a + 27b ≠ 0 holds in F(p ).
F
3 2
NOTE The above curve with 4a + 27b = 0 is called a singular curve, which is not an elliptic curve.
F
m
The set of F(p )-valued points of E is given by
m m m 2 3
E(F(p )) = {Q = (x , y ) ∈ F(p ) × F(p ) | y = x + ax + b } ∪ { O },
Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
E
m
5.1.2 Elliptic curves over F(2 )
m
Let F(2 ), for some m ≥ 1, be a finite field. In this document it is assumed that E is described by an equation of
the type
2 3 2 m
Y + XY = X + aX + b with a, b ∈ F(2 )
m
such that b ≠ 0 holds in F(2 ).
F
For cryptographic use, m shall be a prime to prevent certain kinds of attacks on the cryptosystem.
NOTE The above curve with b = 0 is called a singular curve, which is not an elliptic curve.
F
m
The set of F(2 )-valued points of E is given by
m m m 2 3 2
E(F(2 )) = {Q = (x , y ) ∈ F(2 ) × F(2 ) | y + x y = x + ax + b} ∪ { O },
Q Q Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
E
m
5.1.3 Elliptic curves over F(3 )
m
Let F(3 ) be a finite field with a positive integer m. In this document it is assumed that E is described by an
equation of the type
2 3 2 m
Y = X + aX + b with a, b ∈ F(3 )
m
such that a, b ≠ 0 holds in F(3 ).
F
NOTE The above curve with a or b = 0 is called a singular curve, which is not an elliptic curve.
F
m
The set of F(3 )-valued points of E is given by
m m m 2 3 2
E(F(3 )) = {Q = (x , y ) ∈ F(3 ) × F(3 ) | y = x + ax + b } ∪ { O },
Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
E
4 © ISO/IEC 2008 – All rights reserved
---------------------- Page: 9 ----------------------
ISO/IEC 15946-1:2008(E)
5.2 The group law on elliptic curves
Elliptic curves are endowed with the addition operation +: E × E → E, defining for each pair (Q , Q ) of points on
1 2
E a third point Q + Q . With respect to this addition, E is an abelian group with identity element O . The k-th
1 2 E
multiple of Q is given as kQ, where kQ = Q+ …+Q (k summands) if k > 0, kQ = (-k)(-Q) if k < 0, and kQ = O if
E
k = 0. The smallest positive k with kQ = O is called the order of Q.
E
NOTE Formulae of the group law and Q are given in Clauses B.2, B.3, and B.4.
5.3 Cryptographic bilinear map
A cryptographic bilinear map e is used in some cryptographic applications such as signature schemes or key
n
agreement schemes. The cryptographic bilinear map e is realized by restricting the domain of the Weil or Tate
n
pairings as follows:
e : < G >×< G > → µ
n 1 2 n
The cryptographic bilinear map e satisfies the following properties:
n
ab
⎯ Bilinear : e (aG , bG ) = e(G , G ) (∀a,b ∈ [0, n-1]).
n 1 2 1 2
⎯ Non-degenerate : e (G , G ) ≠ 1.
n 1 2
⎯ Computabilty : There exists an efficient algorithm to compute e .
n
NOTE 1 The relation between the cryptographic bilinear map and the Weil or Tate pairing is given in Clause B.6.
NOTE 2 Formulae for the Weil and Tate pairings are given in Clause C.4.
NOTE 3 There are two types of pairings:
⎯ the case of G = G ,
1 2
⎯ the case of G ≠ G .
1 2
6 Conversion functions
6.1 Octet string / bit string conversion: OS2BSP and BS2OSP
Primitives OS2BSP and BS2OSP to convert between octet strings and bit strings are defined as follows:
⎯ The function OS2BSP(x) takes as input an octet string x, interprets it as a bit string y (in the natural way)
and outputs the bit string y.
⎯ The function BS2OSP(y) takes as input a bit string y, whose length is a multiple of 8, and outputs the
unique octet string x such that y = OS2BSP(x).
8
* *
NOTE The set of finite bit strings is {0, 1} . The set of finite octet strings is {0, 1} .
6.2 Bit string / integer conversion: BS2IP and I2BSP
Primitives BS2IP and I2BSP to convert between bit strings and integers are defined as follows:
⎯ The function BS2IP(x) maps a bit string x to an integer value x′, as follows. If x = 〈x , . . . , x 〉 where
l−1 0
i
x , . . . , x are bits, then the value x′ is defined as x′ = 2 , and
0 l−1 0 ≤ i < l, x = ‘1’
∑
i
© ISO/IEC 2008 – All rights reserved 5
---------------------- Page: 10 ----------------------
ISO/IEC 15946-1:2008(E)
⎯ The function I2BSP(m, l ) takes as input two non-negative integers m and l, and outputs the unique bit
string x of length l such that BS2IP(x) = m, if such an x exists. Otherwise, the function outputs an error
message.
The length in bits of a non-negative integer m is the number of bits in its binary representation, i.e.
⎡log (m + 1)⎤. As a notational convenience, Oct(m) is defined as Oct(m) = I2BSP(m, 8).
2
NOTE I2BSP(m, l ) fails if and only if the length of m in bits is greater than l.
6.3 Octet string / integer conversion: OS2IP and I2OSP
Primitives OS2IP and I2OSP to convert between octet strings and integers are defined as follows:
⎯ The function OS2IP(x) takes as input an octet string x, and outputs the integer BS2IP(OS2BSP(x)).
⎯ The function I2OSP(m, l ) takes as input two non-negative integers m and l, and outputs the unique octet
string x of length l in octets such that OS2IP(x) = m, if such an x exists. Otherwise, the function outputs an
error message.
The length in octets of a non-negative integer m is the number of digits in its representation base 256, i.e.
⎡log (m + 1)⎤.
256
NOTE 1 I2OSP(m, l ) fails if and only if the length of m in octets is greater than l.
NOTE 2 An octet x is often written in its hexadecimal format of length 2; when OS2IP(x) < 16, “0”, representing the bit
string 0000, is prepended. For example, an integer 15 is written as 0e in its hexadecimal format.
NOTE 3 The length in octets of a non-negative integer m is denoted by L(m).
6.4 Finite field element / integer conversion: FE2IP
F
The primitive FE2IP to convert elements of F to integer values is defined as follows:
F
⎯ The function FE2IP maps an element a ∈ F to an integer value a′, as follows. If an element a of F is
F
m
identified with an m-tuple (a , . . . , a ), where the cardinality of F is q = p and a ∈ [0, p-1] for 1 ≤ i ≤ m, then
1 m i
i − 1
the value a′ is defined as a′ = a p .
1 ≤ i ≤ m i
∑
6.5 Octet string / finite field element conversion: OS2FEP and FE2OSP
F F
Primitives OS2FEP and FE2OSP to convert between octet strings and elements of an explicitly given finite
F F
field F are defined as follows:
⎯ The function FE2OSP (a) takes as input an element a of the field F and outputs the octet string
F
I2OSP(a′, l ), where a′ = FE2IP (a) and l = L(|F |−1). Thus, the output of FE2OSP (a) is always an octet
F F
string of length exactly ⎡log |F |⎤.
256
NOTE 1 L(x) represents the length in octets of integer x or octet string x (non-negative integer).
⎯ The function OS2FEP (x) takes as input an octet string x, and outputs the (unique) field element a ∈ F
F
such that FE2OSP (a) = x, if such an a exists, and otherwise fails.
F
NOTE 2 OS2FEP (x) fails if and only if either x does not have length exactly ⎡log |F |⎤, or OS2IP(x) ≥ |F |.
F 256
6 © ISO/IEC 2008 – All rights reserved
---------------------- Page: 11 ----------------------
ISO/IEC 15946-1:2008(E)
6.6 Elliptic curve point / octet string conversion: EC2OSP and OS2ECP
E E
6.6.1 Compressed elliptic curve points
Let E be an elliptic curve over an explicitly given finite field F, where F has characteristic p. A point P ≠ O can
E
be represented in either compressed, uncompressed, or hybrid form. If P = (x, y), then (x, y) is the
uncompressed form of P. The compressed form of P is the pair (x, ỹ), where ỹ ∈ {0, 1} is determined as
follows:
⎯ If p ≠ 2 and y = 0 , then ỹ = 0.
F
f
⎯ If p ≠ 2 and y ≠ 0 , then ỹ = ((y′/p ) mod p) mod 2, where y′ = FE2IP (y), and where f is the largest non-
F F
f
negative integer such that p | y′.
NOTE 1 If p ≠ 2 and y = (y , . . . , y ) ≠ 0 , this is equivalent to letting j be the smallest index with y ≠ 0 and define ỹ = y
1 m F j j
mod 2.
⎯ If p = 2 and x = 0 , then ỹ = 0.
F
f
⎯ If p = 2 and x ≠ 0 , then ỹ = ⎣z′/2 ⎦ mod 2, where z = y/x, where z′ = FE2IP (z), and where f is the largest non-
F F
f
negative integer such that 2 divides FE2IP (1 ).
F F
NOTE 2 If p = 2 and x ≠ 0, this is equivalent to letting y/x = (z , . . . , z ) and define ỹ = z .
1 m 1
The hybrid form of P = (x, y) is the triple (x, ỹ, y), where ỹ is as in the previous paragraph.
6.6.2 Point decompression algorithms
There exist efficient procedures for point decompression, i.e. computing y from (x, ỹ). These are briefly
described here:
⎯ If p ≠ 2, then let (x, ỹ) be the compressed form of (x, y). The point (x, y) satisfies the Weierstrass equation
2
y = f (x) defined in Clause 5.1.1 or 5.1.3. If f (x) = 0 , then there is only one possible choice for y, namely,
F
y = 0 . Otherwise, if f (x) ≠ 0 , then there are two possible choices of y, which differ only in sign, and the
F F
correct choice is determined by ỹ. There are well-known algorithms for computing square roo
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.