ANSI INCITS ISO IEC 15946-1-2002 Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1 General (Adopted by INCITS).pdf

1、 Reference numberISO/IEC 15946-1:2002(E)ISO/IEC 2002INTERNATIONAL STANDARD ISO/IEC15946-1First edition2002-12-01Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General Technologies de linformation Techniques de scurit Techniques cryptographiques b

2、ases sur les courbes elliptiques Partie 1: Gnralits Adopted by INCITS (InterNational Committee for Information Technology Standards) as an American National Standard.Date of ANSI Approval: 7/7/2003Published by American National Standards Institute,25 West 43rd Street, New York, New York 10036Copyrig

3、ht 2003 by Information Technology Industry Council (ITI).All rights reserved.These materials are subject to copyright claims of International Standardization Organization (ISO), InternationalElectrotechnical Commission (IEC), American National Standards Institute (ANSI), and Information Technology I

4、ndustry Council(ITI). Not for resale. No part of this publication may be reproduced in any form, including an electronic retrieval system, withoutthe prior written permission of ITI. All requests pertaining to this standard should be submitted to ITI, 1250 Eye Street NW,Washington, DC 20005.Printed

5、in the United States of AmericaISO/IEC 15946-1:2002(E) PDF disclaimer This PDF file may contain embedded typefaces. In accordance with Adobes 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 comp

6、uter performing the editing. In downloading this file, parties accept therein the responsibility of not infringing Adobes 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 crea

7、te 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

8、 Central Secretariat at the address given below. ISO/IEC 2002 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 eit

9、her ISO at the address below or ISOs 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 copyrightiso.org Web www.iso.org Published in Switzerland ii ISO/IEC 2002 All rights reservedISO/IEC 15946-1:20

10、02(E) ISO/IEC 2002 All rights reserved iiiContents Page Foreword . v Introduction vi 1 Scope 1 2 Normative references 1 3 Symbols (and abbreviated terms) . 2 4 Definition of fields and curves. 2 4.1 Finite fields 2 4.1.1 Finite prime fields 2 4.1.2 Finite fields of order 2m. 3 4.1.3 Finite fields of

11、 F(pm) 4 4.2 Elliptic curves over F(p), F(2m) and F(pm) . 4 4.2.1 Definition of elliptic curves over F(p) 4 4.2.2 Definition of elliptic curves over F(2m) 4 4.2.3 Definition of elliptic curves over F(pm) 5 4.2.4 Definition of the term weak curve 5 4.2.5 The group law on elliptic curves . 5 4.2.6 Neg

12、ative of a Point over F(p) and F(pm) 5 4.2.7 Negative of a Point on an elliptic curve over F(2m) 5 4.2.8 Integer multiplication and the Discrete Logarithm Problem on elliptic curves 5 4.2.9 Elliptic curve point to integer conversion 5 5 Elliptic Curve Domain Parameters and their Validation 6 5.1 Ell

13、iptic Curve Domain Parameters and their Validation Over F(p) and F(pm) . 6 5.1.1 Elliptic curve domain parameters over F(p) and F(pm) 6 5.2 Elliptic curve domain parameter validation over F(p) and F(pm) (Optional) 7 5.3 Elliptic Curve Domain Parameters and their Validation Over F(2m). 7 5.3.1 Ellipt

14、ic curve domain parameters over F(2m) . 7 5.3.2 Elliptic curve domain parameter validation over F(2m) (Optional) . 8 6 Elliptic Curve Key Pair Generation and Public Key Validation. 8 6.1 Key Generation I 8 6.1.1 Key Generation II. 9 7 Public Key Validation (Optional) 9 Annex A (informative) Backgrou

15、nd Information on Elliptic Curves 10 A.1 The finite prime field F(p) . 10 A.1.1 Definition of F(p) 10 A.1.2 Elliptic Curves over F(p). 11 A.1.3 The order of an elliptic curve E defined over F(p) . 13 A.2 The finite field F(2m) 13 A.2.1 Definition of F(2m) 13 A.2.2 Elliptic Curves over F(2m) . 14 A.2

16、.3 The order of an elliptic curve E defined over F(2m) . 16 A.3 The finite field F(pm) 17 A.3.1 Definition of F(pm) 17 A.3.2 Elliptic Curves over F(pm). 18 A.3.3 The order of an elliptic curve E defined over F(pm) . 20 A.4 Integer multiplication on an elliptic curve 20 A.4.1 Evaluating the integer m

17、ultiplication 20 A.5 Methods to determine discrete logarithms on elliptic curves 21 A.5.1 The MOV Condition. 21 ISO/IEC 15946-1:2002(E) iv ISO/IEC 2002 All rights reservedA.6 Point Compression (Optional) . 22 A.6.1 Point Compression and decompression Techniques for Elliptic Curves over F(p) (Optiona

18、l). 22 A.6.2 Point Compression Technique for Elliptic Curves over F(2m) (Optional) 22 A.6.3 Point Compression and Decompression Techniques for Elliptic Curves over (pm)(Optional) . 23 Annex B (informative) Examples . 24 B.1 Curves over Binary Fields (GF(2m) 24 Bibliography 26 ISO/IEC 15946-1:2002(E)

19、 ISO/IEC 2002 All rights reserved vForeword 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 Int

20、ernational 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 liais

21、on 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 3. The main task of the joint techn

22、ical 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-

23、1 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology Subcommittee SC 27, IT Security techniques. ISO/IEC 15946 consists of the following parts, under the general title Information technology Security techniques Cryptographic techniques based on elliptic curves: Part 1: G

24、eneral Part 2: Digital signatures Part 3: Key establishment Part 4: Digital signatures giving message recovery Annexes A and B of this part of ISO/IEC 15946 are for information only. ISO/IEC 15946-1:2002(E) vi ISO/IEC 2002 All rights reservedIntroduction One of the most interesting alternatives to t

25、he RSA and GF(p) based systems 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 rather simple: Every elliptic curve is endowed with a binary operation “+“ under which it forms a finit

26、e 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 Diffie-

27、Hellman and ElGamal type. The security of such a public key system 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 logari

28、thms in a finite field. Indeed, since Miller and Koblitz in 1985 independently suggested the use of elliptic curves for public-key cryptographic systems, no substantial progress in tackling the elliptic curve discrete logarithm problem has been reported. In general, only algorithms which take expone

29、ntial time are known to determine elliptic curve discrete logarithms. 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.

30、This yields significantly shorter digital signatures and system parameters and avoids the use of extra large integer arithmetic completely. This part of ISO/IEC 15946 describes the mathematical background and general techniques necessary for implementing any of the mechanisms described in other part

31、s of ISO/IEC 15946. It is the purpose of this document to meet the increasing interest in elliptic curve based public key technology and describe the components that are necessary to implement a secure digital signature system based on elliptic curves. Schemes are described for key-exchange, key-tra

32、nsport and digital signatures that are based on the elliptic curve discrete logarithm problem. The International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC) draw attention to the fact that it is claimed that compliance with this International Standard m

33、ay involve the use of patents. ISO and IEC take no position concerning the evidence, validity and scope of these patent rights. The holders of these patent rights have assured ISO and IEC that they are willing to negotiate licences under reasonable and non-discriminatory terms and conditions with ap

34、plicants throughout the world. In this respect, the statements of the holders of these patent rights are registered with 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.din.de/ni/sc27 Attentio

35、n is drawn to the possibility that some of the elements of this International Standard 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. INTERNATIONAL STANDARD ISO/IEC 15946-1:2002(E) ISO/IE

36、C 2002 All rights reserved 1Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General 1 Scope International Standard ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. They include the establishment of keys for sec

37、ret-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. The scope of this standard is restricted to cryptographic techniques

38、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 (i.e. which basis is used) is outside the scope of this standard. International Standard ISO/IEC

39、 15946 does not specify the implementation of the techniques it defines. Interoperability of products complying to this international standard will not be guaranteed. 2 Normative references The following normative documents contain provisions which, through reference in this text, constitute provisi

40、ons of this part of ISO 15946. For dated references, subsequent amendments to, or revisions of, any of these publications do not apply. However, parties to agreements based on this part of ISO 15946 are encouraged to investigate the possibility of applying the most recent editions of the normative d

41、ocuments indicated below. For undated references, the latest edition of the normative document referred to applies. Members of ISO and IEC maintain registers of currently valid International Standards. ISO/IEC 9796 (all parts), Information technology Security techniques Digital signature schemes giv

42、ing message recovery ISO/IEC 9797 (all parts), Information technology Security techniques Message Authentication Codes (MACs) ISO/IEC 10118 (all parts), Information technology Security techniques Hash-functions ISO/IEC 11770-3:1999, Information technology Security techniques Key management Part 3: M

43、echanisms using asymmetric techniques ISO/IEC 14888 (all parts), Information technology Security techniques Digital signatures with appendix ISO/IEC 15946-2:2002, Information technology Security techniques Cryptographic techniques based on elliptic curves Part 2: Digital signatures ISO/IEC 15946-3:2

44、002, Information technology Security techniques Cryptographic techniques based on elliptic curves Part 3: Key establishment ISO/IEC 15946-4, Information technology Security techniques Cryptographic techniques based on elliptic curves Part 4: Digital signatures giving message recovery (to be publishe

45、d) ISO/IEC 15946-1:2002(E) 2 ISO/IEC 2002 All rights reserved3 Symbols (and abbreviated terms) In the remainder of this document the following notation will be used to describe public key systems based on elliptic curve technology: p A prime number not equal to 3. NOTE p=3 is not part of this standa

46、rd for simplicity and not because of security reasons. F(p)The finite prime field consisting of exactly p elements. F(2m) The finite field consisting of exactly 2melements. F(pm) The finite field consisting of exactly pmelements. E An elliptic curve, either given by an equation of the form Y2= X3+ a

47、X+ b over the field F(pm) for p3 or by an equation of the form Y2+ XY = X3+ aX2+ b over the field F(2m), together with an extra point 0E refered to as the point of infinity. #(E) The order (or cardinality) of E. q A prime power, pmfor some integer m 1. n A prime divisor of #(E). Q A point on E. xQTh

48、e x-coordinate of Q. yQThe y-coordinate of Q. Q1+Q2The elliptic curve sum of two points Q1and Q2. kQ The k-th multiple of some point Q of E, i.e. Q+Q+ +Q, k summands, with 0Q = 0Eand (k)Q = k(-Q). G A point on E generating a cyclic group of cardinality n. A, B Two entities making use of the public k

49、ey system. dAThe private key of entity A. (In all schemes dA is a random integer in the set 1,n-1.) PAThe public key of entity A. (In all schemes PA is an elliptic curve point.) (Q) The integer obtained from the point Q by the conversion . 0EThe point at infinity. 4 Definition of fields and curves 4.1 Finite fields 4.1.1 Finite prime fields For any prime p there exists a finite field consisting of exactly p elements. This field is uniquely determined up to isomor